class Solution {
public:
    vector<vector<int>> res;
    void dfs(int u,vector<int>& vec,vector<int>& path,int start){
        if(u == 0){
            res.push_back(path);
            return;
        }

        for(int i = start; i < vec.size(); i++){
            if(u - vec[i] < 0) {
                break;
            }
            if(i>start&&vec[i] == vec[i-1]) continue;//如果i不是第一次出现的数，跳过
            path.push_back(vec[i]);
            dfs(u - vec[i], vec, path, i + 1);
            path.pop_back();
        }
    }
    vector<vector<int>> combinationSum2(vector<int>& candidates, int target) {
        vector<int> v;
        sort(candidates.begin(),candidates.end());
        dfs(target,candidates,v,0);
        return res;
    }
};

注意判断

class Solution {
public:
    vector<vector<int>> res;
    void dfs(int u,vector<int>& vec,vector<int>& path,int start){
        if(u == 0){
            res.push_back(path);
            return;
        }

        for(int i = start; i < vec.size(); i++){
            if(u - vec[i] < 0) {
                break;
            }
            if(i>start&&vec[i] == vec[i-1]) continue;//如果i不是第一次出现的数，跳过
            path.push_back(vec[i]);
            dfs(u - vec[i], vec, path, i + 1);
            path.pop_back();
        }
    }
    vector<vector<int>> combinationSum2(vector<int>& candidates, int target) {
        vector<int> v;
        sort(candidates.begin(),candidates.end());
        dfs(target,candidates,v,0);
        return res;
    }
};

class Solution {
public:
    vector<vector<int>> res;
    void dfs(int u,vector<int>& vec,vector<int>& path,int start){
        if(u == 0){
            res.push_back(path);
            return;
        }

        for(int i = start; i < vec.size(); i++){
            if(u - vec[i] < 0) {
                break;
            }
            path.push_back(vec[i]);
            dfs(u - vec[i], vec, path, i);
            path.pop_back();
        }
    }
    vector<vector<int>> combinationSum(vector<int>& candidates, int target) {
        vector<int> v;
        sort(candidates.begin(),candidates.end());
        dfs(target,candidates,v,0);
        return res;
    }
};

class Solution {
public:
    string func(string s){
        string res = "";
        for(int i = 0; i < s.size();){
            char k = '0';
            char ct = s[i];
            while(i < s.size() && s[i] == ct) {
                i++,k++;
            }
            res += k;
            res += ct;
        }
        return res;
    }
    string dfs(int n){
        if(n == 1) return "1";
        return func(dfs(n-1));
    }
    string countAndSay(int n) {
        return dfs(n);
    }

};

class Solution {
public:
    bool isValidSudoku(vector<vector<char>>& board) {

        for(int i = 0; i < board.size(); i++){
            vector<int> latter(10);
            for(int j = 0; j < board[i].size(); j++){
                if(board[i][j] == '.') continue;
                int k = board[i][j] - '0';
                latter[k]++;
                if(latter[k] > 1) return false;
            }
        }

        for(int i = 0; i < board.size(); i++){
            vector<int> latter(10);
            for(int j = 0; j < board[i].size(); j++){
                if(board[j][i] == '.') continue;
                int k = board[j][i] - '0';
                latter[k]++;
                if(latter[k] > 1) return false;
            }
        }

        for(int i = 0; i < board.size(); i+=3){
            for(int j = 0; j < board[i].size(); j+=3){
                vector<int> latter(10);
                for(int x = 0; x < 3; x++){
                    for(int y = 0; y < 3; y++){
                        if(board[i + x][j + y] == '.') continue;
                        int k = board[i + x][j + y] - '0';
                        latter[k]++;
                        if(latter[k] > 1) return false;
                    }
                }
            }
        }
        return true;
    }
};


// [[".",".","."  ,".","5","."  ,".","1","."]
// ,[".","4","."  ,"3",".","."  ,".",".","."]
// ,[".",".","."  ,".",".","3"  ,".",".","1"]
// ,["8",".",".",".",".",".",".","2","."]
// ,[".",".","2",".","7",".",".",".","."]
// ,[".","1","5",".",".",".",".",".","."]
// ,[".",".",".",".",".","2",".",".","."]
// ,[".","2",".","9",".",".",".",".","."]
// ,[".",".","4",".",".",".",".",".","."]]

class Solution {
public:
    int searchInsert(vector<int>& nums, int target) {

        int n = nums.size();
        if(target > nums[n-1]) return n;

        int l = 0, r = n - 1;
        while(l <r){
            int mid = (l+r)>>1;
            if(nums[mid] >= target) r = mid;
            else l = mid + 1;
        }

        return l;
    }
};

class Solution {
public:
    vector<int> searchRange(vector<int>& nums, int target) {

        vector<int> res;
        int l = 0, r = nums.size() - 1;
        while(l<r){
            int mid = (l+r)>>1;
            if(nums[mid] >= target) r=mid;
            else l = mid + 1;
        }

        if(nums.size() == 0 || nums[l] != target) return {-1,-1};
        res.push_back(l);

        l = 0, r = nums.size() - 1; 
        while(l<r){
            int mid = (l+r+1)>>1;
            if(nums[mid] <= target) l = mid;
            else r = mid - 1; 
        }
        res.push_back(l);
        return res;
    }
};

class Solution {
public:
    int find(int l, int r, vector<int>& nums){
        while(l<r){
            int mid = (l+r)>>1;
            if(nums[mid] >= nums[0]){
                l = mid + 1; 
            }
            else{
                r = mid;
            }
        }
        return l;
    }
    int find2(int l, int r, vector<int>& nums, int target){
        while(l<r){
            int mid = (l+r)>>1;
            if(nums[mid] >= target){
                r = mid;
            }
            else{
                l = mid + 1; 
            }
            //cout<<mid<<endl;
        }
        return l;
    }
    int search(vector<int>& nums, int target) {
        int k = find(0, nums.size()-1, nums);//通过第一段大于等于nums[0]二分
        //cout<<k<<endl;
        int a = find2(0,k-1, nums, target);
        int b = find2(k,nums.size()-1, nums, target);
        //cout<<a<<endl;
        if(nums[a] == target) return a;
        else if(nums[b] == target) return b;
        else return -1;
    }
};

//4 5 6 7 0 1 2
//5 6 7 0 1 2 4
//2 4 5 6 7 0 1
//6 7 0 1 2 4 5

class Solution {
public:
    int find(int l, int r, vector<int>& nums){
        while(l<r){
            int mid = (l+r)>>1;
            if(nums[mid] >= nums[0]){
                l = mid + 1; 
            }
            else{
                r = mid;
            }
        }
        return l;
    }
    int find2(int l, int r, vector<int>& nums, int target){
        while(l<r){
            int mid = (l+r)>>1;
            if(nums[mid] >= target){
                r = mid;
            }
            else{
                l = mid + 1; 
            }
            //cout<<mid<<endl;
        }
        return l;
    }
    int search(vector<int>& nums, int target) {
        int k = find(0, nums.size()-1, nums);//通过第一段大于等于nums[0]二分
        //cout<<k<<endl;
        int a = find2(0,k-1, nums, target);
        int b = find2(k,nums.size()-1, nums, target);
        //cout<<a<<endl;
        if(nums[a] == target) return a;
        else if(nums[b] == target) return b;
        else return -1;
    }
};

//4 5 6 7 0 1 2
//5 6 7 0 1 2 4
//2 4 5 6 7 0 1
//6 7 0 1 2 4 5

1. 贪心，两次线性扫描

class Solution {
public:
    int longestValidParentheses(string s) {
        //条件：有效括号所有前缀满足  左括号数大于等于右括号数
        //两次线性扫描，若当前区间不符合条件则更新start
        int res = 0;
        int val = 0;
        for(int i = 0, start = 0; i<s.size(); i++)
        {   
            if(s[i] == '(') val += 1;
            else {
                val -= 1;
            }

            if(val == 0) res = max(res, i - start + 1);
            else if(val < 0) start = i + 1,val = 0;
        }
        //反着来一遍

        val = 0;
        for(int i = s.size() - 1, start = s.size() - 1; i >= 0; i--){
            if(s[i] == ')') val += 1;
            else val -= 1;

            if(val <0 ) start = i - 1, val = 0;
            else if(val == 0) res = max(res, start - i + 1);
        }
        return res;
    }
};

2. 栈做法

class Solution {
public:
    int longestValidParentheses(string s) {
        //1. 前缀的左括号数大于等于右括号数

        //将字符串分成几段，每个线为第一次右括号数大于左括号数的位置右边（可以证明，有效括号不能横跨两段），则除了每段最后的右括号，每个右括号都满足条件1.
        stack<int> stk;
        int res = 0;
        for(int i = 0, start = -1; i<s.size(); i++)//start为每段的开始
        {
            if(s[i] == '(') stk.push(i);
            else {
                if(stk.size())//若栈中有左括号
                {
                    stk.pop();
                    if(stk.size())//若不为空，则此有效括号起始位置为栈中左括号的右边一个元素，截至位置为i
                    {
                        res = max(res, i - stk.top());
                    }
                    else//若为空，则起始位置为start
                    {
                        res = max(res, i - start);
                    }
                }
                else//栈为空且这个元素为右括号，则更新start
                {
                    start = i;
                }
            }
        }
        return res;

    }
};

3. 动态规划

class Solution {
public:
    int longestValidParentheses(string s) {
        //f[i] 表示以i结尾的最大有效括号长度
        //状态转移： 仅考虑），若s[i-1]为左括号，则fi = f(i-2) +2
        //                     否则，看s[i- f[i-1] -1]为左括号，则fi = f[i-1] + 2 + f[i- f[i-1] -2]
        int n = s.size();
        int f[n+5];
        s = " " + s;
        memset(f,0,sizeof f);
        for(int i = 2; i <= n; i++){
            if(s[i] == '(') continue;

            if(s[i-1] == '(') 
                f[i] = f[i-2] + 2;
            else {
                if(s[i - f[i-1] -1] == '(') {
                    f[i] = f[i-1] + 2 + f[i - f[i-1] -2]; 
                }
            }
        }
        int res = 0;
        for(int i = 0; i <= n; i++){
            //cout<<f[i]<<endl;
            res = max(res, f[i]);
        }
        return res;
    }
};