**经常考？
剪枝
1.从大到小枚举：分支数会少一些，越往下都剪枝越少，也越快
2.如果搜的时候，当前搜的这个数和前一个数相等并且失败了，当前也一定失败。
也就是说如果ai无解，那么后面和他相等的数应该也是无解的；
所以可以跳过。
3.如果某一组第一个数失败了，那么后面的数一定无解；
4.如果某一组最后一个数失败了，那么后面的数一定无解；

当前组的最后一个元素ai (注意此时当前子数组的其他元素与ai的和一定是sum / k) 的搜索结果是失败(即当前组后面的所有组全部搜索完后是失败), 那么最终的结果是失败.
**

class Solution {
public:
    int len;
    vector<int>nums;
    vector<bool>st;
    bool dfs(int start,int cur,int k)
    {
        if(k==0) return true;
        if(cur==len) return dfs(0,0,k-1);
        for(int i=start;i<nums.size();i++) //起点要从start开始
        {
            if(st[i]) continue;
            if(cur+nums[i]<=len)
            {
                st[i]=true;
                if(dfs(i+1,cur+nums[i],k)) return true;
                st[i]=false;
            }
            while(i+1<nums.size() && nums[i]==nums[i+1]) i++; //如果当前元素和后面元素重复，跳过，前面不行后面也不行
            if(!cur || cur+nums[i]==len) return false;//如果是当前组的第一个元素不行或者加上最后一个元素正好等于分组的大小的话，那么也是错误的
        }
        return false;
    }
    bool canPartitionKSubsets(vector<int>& _nums, int k) {
        nums=_nums;
        st.resize(nums.size());
        int sum=accumulate(nums.begin(),nums.end(),0);
        if(sum%k) return false;
        len=sum/k;
        sort(nums.begin(),nums.end(),greater<int>()); //从大到小排序，注意！
        return dfs(0,0,k);
    }
};

**经常考？
剪枝
1.从大到小枚举：分支数会少一些，越往下都剪枝越少，也越快
2.如果搜的时候，当前搜的这个数和前一个数相等并且失败了，当前也一定失败。
也就是说如果ai无解，那么后面和他相等的数应该也是无解的；
所以可以跳过。
3.如果某一组第一个数失败了，那么后面的数一定无解；
4.如果某一组最后一个数失败了，那么后面的数一定无解；

当前组的最后一个元素ai (注意此时当前子数组的其他元素与ai的和一定是sum / k) 的搜索结果是失败(即当前组后面的所有组全部搜索完后是失败), 那么最终的结果是失败.
**

class Solution {
public:
    int len;
    vector<int>nums;
    vector<bool>st;
    bool dfs(int start,int cur,int k)
    {
        if(k==0) return true;
        if(cur==len) return dfs(0,0,k-1);
        for(int i=start;i<nums.size();i++) //起点要从start开始
        {
            if(st[i]) continue;
            if(cur+nums[i]<=len)
            {
                st[i]=true;
                if(dfs(i+1,cur+nums[i],k)) return true;
                st[i]=false;
            }
            while(i+1<nums.size() && nums[i]==nums[i+1]) i++; //如果当前元素和后面元素重复，跳过，前面不行后面也不行
            if(!cur || cur+nums[i]==len) return false;//如果是当前组的第一个元素不行或者加上最后一个元素正好等于分组的大小的话，那么也是错误的
        }
        return false;
    }
    bool canPartitionKSubsets(vector<int>& _nums, int k) {
        nums=_nums;
        st.resize(nums.size());
        int sum=accumulate(nums.begin(),nums.end(),0);
        if(sum%k) return false;
        len=sum/k;
        sort(nums.begin(),nums.end(),greater<int>()); //从大到小排序，注意！
        return dfs(0,0,k);
    }
};

class Solution {
public:
    int longestOnes(vector<int>& nums, int k) {
       int res=0;
       for(int i=0,j=0,cnt=0;i<nums.size();i++)
       {
           if(nums[i]==0) cnt++;
           while(cnt>k)
           {
               if(nums[j]==0) cnt--;
               j++;
           }
           res=max(res,i-j+1);
       }
       return res;
    }
};

这题也是典型的通过枚举某些信息来来产生单调性，从而应用双指针算法。

首先枚举26个大写字母，设这个变量是c。对于双指针的右侧指针i，找的是最左侧的一个指针j，使得i到j这个区间里不等于c的字符数量不超过k，这样j指针随着i指针的移动一定是单调地向右移动的。

区间里维护的就是c出现的次数。

class Solution {
public:
    int characterReplacement(string s, int k) {
        int n = s.size();
        int res = 0;
        for (char c = 'A'; c <= 'Z'; c ++ ) {
            // 双指针，cnt维护当前窗口里面c出现的次数
            for (int i = 0, j = 0, cnt = 0; i < n; i ++ ) {
                // 每次判断新加入的字符
                if (s[i] == c) cnt ++ ;
                // 当窗口里其它字符出现次数超过k的时候，就要一直移动j指针，同时维护出现次数
                while (i - j + 1 - cnt > k) {
                    if (s[j] == c) cnt -- ;
                    j ++ ;
                }
                res = max(res, i - j + 1);
            }
        }
        return res;
    }
};

c b a
比a大的话，c=b,b=a;
在a，b之间的话 c=b,b=x;
在b，c之间 c=x

a是最大的数
c就是要找的第三大的数

class Solution {
public:
    int thirdMax(vector<int>& nums) {
        long long INF=1e10,a=-INF,b=-INF,c=-INF,s=0;
         //防止边界问题出现
        for(auto x:nums)
        {
            if(x>a) s++,c=b,b=a,a=x;
            else if(x<a && x>b) s++,c=b,b=x;
            else if(x<b && x>c) s++,c=x;
        }
        if(s<3) return a;
        else return c;
    }
};

class Solution {
public:
    void reverseString(vector<char>& s) {
        for(int i=0,j=s.size()-1;i<j;i++,j--) swap(s[i],s[j]);
    }
};

https://www.nowcoder.com/discuss/978398
作者：牛客6800171号
链接：https://www.nowcoder.com/discuss/978398
来源：牛客网

20 有效的括号【哈希表+栈】

32 最长有效括号【前后两趟遍历 / 栈 / 动态规划】

53 最大（连续）子数组和【贪心】

70 爬楼梯【动态规划（滚动数组）】

102 二叉树的层序遍历【队列】

213 打家劫舍Ⅱ【动态规划】

236 二叉树的最近公共祖先【后序遍历的递归变形】

268 丢失的数字【位元算异或 / 数学】

344 反转字符串【双指针】

409 最长回文串【贪心】

414 第三大的数【set / 滚动数组】

424 替换后的最长重复字符【滑动窗口】

687 最长同值路径【后序遍历的递归变形】

698 划分为k个相等的子集【DFS】

724 寻找数组的中心下标【前缀和】

1004 最大连续1的个数 Ⅲ（类似424）【滑动窗口】

1790 仅执行一次字符串交换能否使两个字符串相等【一次遍历】

剑指Offer 35 复杂链表的复制【链表】

剑指Offer 41 数据流的中位数【两个排序规则相反的优先级队列】

剑指Offer 56-Ⅱ 数组中数字出现的次数Ⅱ【位运算异或】

/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode() : val(0), left(nullptr), right(nullptr) {}
 *     TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
 *     TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
 * };
 */
class Solution {
public:
    int res;
    int longestUnivaluePath(TreeNode* root) {
        res=0;
        dfs(root);
        return res;
    }
    int dfs(TreeNode* root)
    {
        if(!root) return 0;
        auto l=dfs(root->left),r=dfs(root->right);
        if(!root->left || root->left->val!=root->val) l=0;
        if(!root->right || root->right->val!=root->val) r=0;
        res=max(res,l+r);
        return max(l,r)+1;
    }
};

/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode(int x) : val(x), next(NULL) {}
 * };
 */
class Solution {
public:
    void deleteNode(ListNode* node) {

       node->val=node->next->val;  
       node->next=node->next->next;
    }
};

二叉搜索树

/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode(int x) : val(x), left(NULL), right(NULL) {}
 * };
 */
class Solution {
public:
    TreeNode* lowestCommonAncestor(TreeNode* root, TreeNode* p, TreeNode* q) {
        if(!root) return NULL;
        if(p->val<root->val && q->val<root->val) return lowestCommonAncestor(root->left,p,q);
        if(p->val>root->val && q->val>root->val) return lowestCommonAncestor(root->right,p,q);
        return root;
    }
};

二叉树

/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode(int x) : val(x), left(NULL), right(NULL) {}
 * };
 */
class Solution {
public:
    TreeNode* lowestCommonAncestor(TreeNode* root, TreeNode* p, TreeNode* q) {
        if(!root) return NULL;
        if(root==p || root==q) return root;
        auto left=lowestCommonAncestor(root->left,p,q);
        auto right=lowestCommonAncestor(root->right,p,q);
        if(left && right) return root;
        if(left) return left;
        else return right;
    }
};