52.哀家要长脑子了！

1.75. 颜色分类 - 力扣（LeetCode）

 方法一

把0 和 1排好剩下的2就不用管了。

p0记录下一个0放置的位置，p1记录下一个1放置的位置。所以p0 肯定一直是要小于等于p1的。当遍历到1的时候，放到此时1应该放的位置，即跟p1指针指向的位置交换。当遍历到0的时候，将0放到此时0可以放的位置，如果此时p0小于p1说明什么，说明之前已经处理好0 和 1了，最后一个0后接着就是1，现在交换过后肯定就把一个1给换到后面去了，所以要额外操作一次换回来。

class Solution {
public:
    void sortColors(vector<int>& nums) {
        int p0 = 0, p1 = 0;
        for(int i = 0; i < nums.size(); i++){
            if(nums[i] == 1)
                swap(nums[i], nums[p1++]);
            else if(nums[i] == 0){
                swap(nums[i], nums[p0]);
                
                if(p0 < p1)
                    swap(nums[i], nums[p1]);
                
                p0++, p1++;
            }
        }
        return;
    }
};

方法二

指针a指向0应该放置的位置，指针b指向2应该放置的位置。用一个while把所有的2都放到它们应该放的位置上。放在前面的就是0

class Solution {
public:
    void sortColors(vector<int>& nums) {
        int a = 0, b = nums.size()-1;
        for(int i = 0 ; i <= b; i++){
            while(i <= b && nums[i] == 2){
                swap(nums[i], nums[b--]);
            }
            if(nums[i] == 0) 
                swap(nums[i], nums[a++]);
        }
    }
};

2.28. 找出字符串中第一个匹配项的下标 - 力扣（LeetCode）

BF算法

从haystack的每一位开始匹配看能不能成功匹配needle，那么每次就要从needle的第一位开始进行模拟，所以每次进行循环都要对a,b指针进行赋值。

class Solution {
public:
    int strStr(string haystack, string needle) {
        int n = haystack.size(), m = needle.size();
        for(int i = 0; i < n; i ++){
            int a = i, b = 0;
            while(b < m && haystack[a] == needle[b])
                a++, b++;
            if(b == m) 
                return a - b;    
//          if(haystack[a] != needle[b])
//              b = 0;
        }
        return -1;
    }
};

 KMP算法

class Solution {
public:
    int strStr(string haystack, string needle) {
        int n = haystack.size(), m = needle.size();
       
        haystack.insert(haystack.begin(), ' ');
        needle.insert(needle.begin(), ' ');

        vector<int> next(m+1);
        for(int i = 2, j = 0; i <= m; i++){
            while(j && needle[i] != needle[j+1]) 
                j = next[j];
            if(needle[i] == needle[j+1])
                j++;
            next[i] = j;
        }

        for(int i = 1, j = 0; i <= n; i++){
            while(j && haystack[i] != needle[j+1])
                j  = next[j];
            if(haystack[i] == needle[j+1])
                j++;
            if(j == m)
                return i - j;
        }
        return -1;
    }
};

3.416. 分割等和子集 - 力扣（LeetCode）

 分割两个子集使得两个子集得元素和相等。可以判断

1.如果给出数组nums的长度小于2，那肯定是不能分成两个子集的

2.如果nums的元素总和是个奇数，肯定是不能被2整除，两个子集的元素和不可能相等

3.分成的两个子集各自的元素和都要等于nums元素总和的一半，如果最大的元素值还要小于这个一半，那肯定也是不行的

用动态规划做，定义dp数组，dp[i][j]代表着：前 i 个元素是否存在一个子集 其元素之和等于 j

初始化：

dp[i][0]：对于前i个元素，其目标之和等于0，那么是存在这样的子集的。空集

dp[0][nums[0]]：如果只考虑前0个元素即元素nums[0]，当其目标总和为nums[0]时也是存在这样的子集满足要求，即nums[0]

class Solution {
public:
    bool canPartition(vector<int> &nums) {
        int n = nums.size();
        
        int sum = accumulate(nums.begin(), nums.end(), 0);
        int maxNum = *max_element(nums.begin(), nums.end());
        int target = sum / 2;
        
        if(n < 2 || (sum&1) || maxNum > target)
            return false;

        vector<vector<int>> dp(n, vector<int>(target+1, 0));
        for(int i = 0; i < n; i++)
            dp[i][0] = true;
        dp[0][nums[0]]  = true;

        for(int i = 1; i < n; i++){
            int num = nums[i];
            for(int j = 1; j <= target; j++){
                if(j >= num)
                    dp[i][j] = dp[i-1][j] || dp[i-1][j-num];
                else
                    dp[i][i] = dp[i-1][j];
            }
        }
        return dp[n-1][target];
    }
};