1-數組

1 - 移動元素

283. 移動零

解法一：使用 zeroCnt 變量來記錄 0 目前出現的次數，對于非零元素，使其前移 zeroCnt 個位置；然後統一從後往前複制 zeroCnt 個零元素。

void moveZeroes(vector<int>& nums) {
        int zeroCnt = 0, len = nums.size();
        for(int i = 0; i < len; i++) {
            if(nums[i] == 0)
                zeroCnt++;
            else 
                nums[i - zeroCnt] = nums[i];
        }
        for(int i = 0; i < zeroCnt; i++) 
            nums[len - 1 - i] = 0;        
    }
           

解法二：使用 index 變量記錄非零元素的個數，如果周遊指針 i 所指向位置不能于 index 時，說明其出現過零元素，将其指派為 0

void moveZeroes(vector<int>& nums) {
        int index = 0, len = nums.size();
        for(int i = 0; i < len; i++) {
            if(nums[i] != 0) {
                nums[index] = nums[i];
                if(i != index) 
                    nums[i] = 0;
                index++;                
            }
        }
    }
           

2 - 雙指針的思想

11. 盛最多水的容器

解法一：窮舉的思想，兩層 for 循環不斷地疊代更新

class Solution {
public:     
    int maxArea(vector<int>& height) {       
       int len = height.size(), area = 0, max = 0;
       for(int i = 0; i < len - 1; i++) {
           for(int j = i + 1; j < len; j++) {
           	   // 利用三目表達式得到桶的高度，然後
               int h = (height[i] < height[j]) ? height[i] : height[j];
               area = (j - i) * h;
               if(max < area)
                    max = area; 
           }
       }
       return max;
    }
};
           

class Solution {
public:     
    int maxArea(vector<int>& height) {       
       int l = 0, r = height.size() - 1, ar ea = 0, max = 0;
       while(l < r) {
           if(height[l] < height[r]) {
               area = (r - l) * height[l];
               l++;
           }
           else {
               area = (r - l) * height[r];
               r--;
           }
           if(max < area)
                max = area; 
       }
       return max;
    }
};
           

1.兩數之和

解法一：使用暴力解法，兩層 for 循環疊代計算，輸出

class Solution {
public:
    vector<int> twoSum(vector<int>& nums, int target) {
        vector<int> ans;
        int len = nums.size();
        for(int i = 0; i < len - 1; i++) {
            for(int j = i + 1; j < len; j++) {
                if(nums[i] + nums[j] == target) {
                    ans.push_back(i);
                    ans.push_back(j);                   
                }                    
            }
        }
        return ans;     
    }
};
           

15. 三數之和

class Solution {
public:
    vector<vector<int>> threeSum(vector<int>& nums) {
        vector<vector<int>> ans;
        sort(nums.begin(), nums.end());
        int len = nums.size();
        for(int i = 0; i < len; i++) { 
            if (nums[i] > 0)                     return ans;  
            if (i > 0 && nums[i] == nums[i-1])   continue;
            int l = i + 1, r = len - 1;
            while(l < r) {                
                int sum = nums[i] + nums[l] + nums[r];
                if(sum < 0) {
                    l++;
                    while(l < r && nums[l] == nums[l - 1]) l++;
                }             
                else if(sum > 0) {
                    r--;
                    while(l < r && nums[r] == nums[r + 1]) r--;
                }                    
                else {
                    ans.push_back({nums[i], nums[l], nums[r]});
                    l++;  r--;
                    while(l < r && nums[l] == nums[l - 1]) l++;
                    while(l < r && nums[r] == nums[r + 1]) r--;
                }                     
            }
        }
	    
        return ans;
    }
};
           

3、dp 數組動态規劃

70. 爬樓梯

class Solution {
public:
    int climbStairs(int n) {
        if(n == 1)  return 1;
        vector<int> dp(n + 1, 0);
        dp[1] = 1;  dp[2] = 2;
        for(int i = 3; i <= n; i++) 
            dp[i] = dp[i - 1] + dp[i - 2];
        return dp[n];
    }
};