本系列為筆者的?Leetcode 刷題記錄，順序為 Hot 100 題官方順序，根據標簽命名，記錄筆者總結的做題思路，附部分代碼解釋和疑問解答。
目錄
01 最大子數組和
方法一：動態規劃（卡達尼算法）
方法二：二分 + 遞推
02 合并區間
方法：排序
03 輪轉數組
方法：新建數組
04 除自身以外數組的乘積
方法一：左右乘積列表
方法二：左右乘積列表Plus
05 缺失的第一個正數
方法一：哈希映射
方法二：枚舉
方法三：數組改造哈希表
方法四：置換
01 最大子數組和
class Solution {
public:int maxSubArray(vector<int>& nums) {}
};方法一：動態規劃（卡達尼算法）
-
聲明
pre，存儲x之前的最大子數組和，pre = max(pre+x, x)
class Solution {
public:int maxSubArray(vector<int>& nums) {int pre = 0, ans = nums[0];for(const auto& x: nums){pre = max(pre+x, x);ans = max(ans, pre);}return ans;}
};方法二：二分 + 遞推
-
建立結構體
Status，包含iSum, lSum, rSum, mSum -
-
采用二分，不斷切割區間
[l, r]，進行遞歸，快速下降后緩慢回升 -
注：
if(l == r) return (Status) {a[l], a[l], a[l], a[l]};
class Solution {
public:struct Status{int iSum, lSum, rSum, mSum;};//緩慢回升：遞推Status pushUp(Status l, Status r){int iSum = l.iSum + r.iSum;int lSum = max(l.lSum, l.iSum + r.lSum);int rSum = max(r.rSum, r.iSum + l.rSum);int mSum = max(max(l.mSum, r.mSum), l.rSum + r.lSum);return (Status) {iSum, lSum, rSum, mSum};}//快速下降：二分Status get(vector<int>& a, int l, int r){if(l == r) return (Status) {a[l], a[l], a[l], a[l]};int m = (l + r) >> 1;Status lSub = get(a, l, m);Status rSub = get(a, m + 1, r);return pushUp(lSub, rSub);}int maxSubArray(vector<int>& nums) {return get(nums, 0, nums.size() - 1).mSum;}
};02 合并區間
class Solution {
public:vector<vector<int>> merge(vector<vector<int>>& intervals) {}
};方法：排序
-
sort原數組 -
-
判斷
merged.back()[1] < L，若成立，則添加區間，若不成立，則更新原區間右端點 -
注：
if(intervals.size() == 0) return {};?
class Solution {
public:vector<vector<int>> merge(vector<vector<int>>& intervals) {if(intervals.size() == 0) return {};sort(intervals.begin(), intervals.end());vector<vector<int>> merged;for(int i=0; i<intervals.size(); ++i){int L = intervals[i][0];int R = intervals[i][1];if(!merged.size() || merged.back()[1] < L) merged.push_back({L, R});else merged.back()[1] = max(merged.back()[1], R);}return merged;}
};03 輪轉數組
class Solution {
public:void rotate(vector<int>& nums, int k) {}
};方法：新建數組
-
建立新數組
newArr(n)，存儲輪轉結果newArr[(i+k)%n] = nums[i];
class Solution {
public:void rotate(vector<int>& nums, int k) {int n = nums.size();vector<int> newArr(n);for(int i=0; i<n; ++i){newArr[(i+k)%n] = nums[i];}nums.assign(newArr.begin(), newArr.end());}
};nums.assign(newArr.begin(), newArr.end())?意味著用 newArr 中由 begin() 和 end() 界定的元素范圍替換 nums 中原有的元素。
04 除自身以外數組的乘積
class Solution {
public:vector<int> productExceptSelf(vector<int>& nums) {}
};方法一：左右乘積列表
-
建立兩個數組
leftSup(n)和rightSup(n)，存儲i左側和右側元素乘積
class Solution {
public:vector<int> productExceptSelf(vector<int>& nums) {int n = nums.size();vector<int> leftSup(n);leftSup[0] = 1;for(int i=1; i<n; ++i){leftSup[i] = leftSup[i-1] * nums[i-1];}vector<int> rightSup(n);rightSup[n-1] = 1;for(int i=n-2; i>=0; --i){rightSup[i] = rightSup[i+1] * nums[i+1];}vector<int> ans(n);for(int i=0; i<n; ++i){ans[i] = leftSup[i] * rightSup[i];}return ans;}
};方法二：左右乘積列表Plus
-
建立一個數組
ans(n)，初始存儲i左側元素乘積 -
從右至左，計算
ans(n)最終值
class Solution {
public:vector<int> productExceptSelf(vector<int>& nums) {int n = nums.size();vector<int> ans(n);ans[0] = 1;for(int i=1; i<n; ++i){ans[i] = ans[i-1] * nums[i-1];}int R = 1;for(int i=n-1; i>=0; --i){ans[i] = ans[i] * R;R *= nums[i];}return ans;}
};05 缺失的第一個正數
class Solution {
public:int firstMissingPositive(vector<int>& nums) {}
};方法一：哈希映射
時間復雜度 O(n)、空間復雜度 O(n)
方法二：枚舉
時間復雜度 O(n^2)、空間復雜度 O(1)
方法三：數組改造哈希表
時間復雜度 O(n)、空間復雜度 O(1)
-
遍歷數組，所有復數改為
n + 1 -
遍歷數組，判斷
abs(nums[i]) <= n，執行nums[flag - 1] = -abs(nums[flag - 1]); -
遍歷數組，若每個數都是負數，則答案為
n + 1，否則為第一個整數位置加一
class Solution {
public:int firstMissingPositive(vector<int>& nums) {int n = nums.size();//改負數for(int i=0; i<n; ++i){if(nums[i] <= 0) nums[i] = n + 1;}//添負號for(int i=0; i<n; ++i){int flag = abs(nums[i]);if(flag <= n) nums[flag - 1] = -abs(nums[flag - 1]);}for(int i=0; i<n; ++i){if(nums[i] > 0) return i + 1; //精髓在負號}return n + 1;}
};方法四：置換
-
遍歷數組，判斷
nums[i] > 0 && nums[i] <= n && nums[nums[i] - 1] != nums[i]，交換兩數，執行swap(nums[nums[i] - 1], nums[i]) -
遍歷數組，若
nums[i] != i + 1，則答案為i + 1, 否則為n + 1
class Solution {
public:int firstMissingPositive(vector<int>& nums) {int n = nums.size();for(int i=0; i<n; ++i){while(nums[i] > 0 && nums[i] <= n && nums[nums[i] - 1] != nums[i]){swap(nums[nums[i] - 1], nums[i]);}}for(int i=0; i<n; ++i){if(nums[i] != i + 1){return i + 1;}}return n + 1;}
};① 為什么 nums[nums[i] - 1] != nums[i] 改成 nums[i] - 1 != i會導致執行超過時間限制？
nums[nums[i] - 1] != nums[i] 可能是位置不同但數值相同，導致無限循環交換。
② 為什么 nums[i] != i + 1 改成 nums[i] - 1 != i會導致執行錯誤？
以 nums[i] - 1 作為索引進行比較時，可能會涉及到為負數或超出范圍的索引，若 nums[i] 是負數或 0，nums[i] - 1 是非法索引，可能導致未定義行為。
文章部分代碼來源于力扣（LeetCode）
