1.图论

1.1 岛屿数量

代码实现（C++/Java）

typedef pair<int,int> PII;
class Solution {
public:
    int res;
    int dx[4]={1,0,0,-1};
    int dy[4]={0,1,-1,0};
    int numIslands(vector<vector<char>>& grid) {
        int n=grid.size();
        int m=grid[0].size();
        vector<vector<bool>> status(n,vector<bool>(m,false));
        for(int i=0;i<n;i++){
            for(int j=0;j<m;j++){
                if(!status[i][j] && grid[i][j]=='1'){
                    bfs(i,j,status,grid);
                    res++;
                }
            }
        }
        return res;
    }
    void bfs(int x,int y,vector<vector<bool>>& status,vector<vector<char>>& grid){
        int n=status.size();
        int m=status[0].size();
        status[x][y]=true;
        queue<PII> q;
        q.push({x,y});
        while(!q.empty()){
            auto t=q.front();
            q.pop();
            for(int i=0;i<4;i++){
                x=t.first+dx[i];
                y=t.second+dy[i];
                if(x>=0 && x<n && y>=0 && y<m && !status[x][y] && grid[x][y]=='1'){
                    status[x][y]=true;
                    q.push({x,y});
                }
            }
        }
    }
};

class Node{
    int x,y;
    public Node(int x,int y){
        this.x=x;
        this.y=y;
    }
}
class Solution {
    public static boolean[][] status;
    public static int res;
    public static int[] dx={1,-1,0,0};
    public static int[] dy={0,0,1,-1};
    public int numIslands(char[][] grid) {
        int n=grid.length;
        int m=grid[0].length;
        status=new boolean[n][m];
        res=0;
        for(int i=0;i<n;i++){
            for(int j=0;j<m;j++){
                if(!status[i][j] && grid[i][j]=='1'){
                    bfs(i,j,grid);
                    res++;
                }
            }
        }
        return res;
    }
    public static void bfs(int x,int y,char[][]grid){
        int n=grid.length;
        int m=grid[0].length;
        status[x][y]=true;
        Queue<Node> q=new LinkedList<>();
        q.offer(new Node(x,y));
        while(!q.isEmpty()){
            Node t=q.poll();
            for(int i=0;i<4;i++){
                x=t.x+dx[i];
                y=t.y+dy[i];
                if(x>=0 && x<n && y>=0 && y<m && !status[x][y] && grid[x][y]=='1'){
                    status[x][y]=true;
                    q.offer(new Node(x,y));
                }
            }
        }
    }
}

1.2 腐烂的橘子

994. 腐烂的橘子 - 力扣（LeetCode）

代码实现（C++/Java）

typedef pair<int,int> PII;
class Solution {
public:
    int dx[4]={0,0,1,-1};
    int dy[4]={1,-1,0,0};
    int orangesRotting(vector<vector<int>>& grid) {
        int n=grid.size();
        int m=grid[0].size();
        queue<PII> q;
        int fresh=0;//新鲜的数量
        for(int i=0;i<n;i++){
            for(int j=0;j<m;j++){
                if(grid[i][j]==2){
                    q.push({i,j});
                }else if(grid[i][j]==1){
                    fresh++;
                }
            }
        }
        if(fresh==0) return 0;
        int res=0;
        while(!q.empty()){
            int size=q.size();
            bool flag=false;
            for(int i=0;i<size;i++){
                auto t=q.front();
                q.pop();
                for(int j=0;j<4;j++){
                    int x=t.first+dx[j];
                    int y=t.second+dy[j];
                    if(x>=0 && x<n && y>=0 && y<m && grid[x][y]==1){
                        grid[x][y]=2;
                        fresh--;
                        q.push({x,y});
                        flag=true;
                    }
                }
            }
            if(flag) res++;
        }
        if(fresh>0) return -1;
        else return res;
    }
};

class Node{
    int x,y;
    public Node(int x,int y){
        this.x=x;
        this.y=y;
    }
}
class Solution {
    public static int[]dx={1,-1,0,0};
    public static int[]dy={0,0,1,-1};
    public int orangesRotting(int[][] grid) {
        int m=grid.length;
        int n=grid[0].length;
        Queue<Node> q=new LinkedList<>();
        int fresh=0;
        for(int i=0;i<m;i++){
            for(int j=0;j<n;j++){
                if(grid[i][j]==2){
                    q.offer(new Node(i,j));
                }else if(grid[i][j]==1){
                    fresh++;
                }
            }
        }
        int res=0;
        while(!q.isEmpty()){
            int size=q.size();
            boolean flag=false;
            for(int i=0;i<size;i++){
                Node t=q.poll();
                for(int j=0;j<4;j++){
                    int x=t.x+dx[j];
                    int y=t.y+dy[j];
                    if(x>=0 &&x<m && y>=0 && y<n && grid[x][y]==1){
                        grid[x][y]=2;
                        fresh--;
                        q.offer(new Node(x,y));
                        flag=true;
                    }
                }
            }
            if(flag) res++;
        }
        if(fresh>0) return -1;
        else return res;    
    }
}

1.3 课程表

207. 课程表 - 力扣（LeetCode）

代码实现（C++/Java）

class Solution {
public:
    bool canFinish(int numCourses, vector<vector<int>>& prerequisites) {
        //建图和统计入度
        vector<vector<int>> g(numCourses);
        vector<int> indegree(numCourses,0);
        //学习p[0]前要完成p[1] p[1]->p[0]
        for(auto &p:prerequisites){
            g[p[1]].push_back(p[0]);
            indegree[p[0]]++;
        }
        //将入度为0的点加入队列
        queue<int> q;
        for(int i=0;i<numCourses;i++){
            if(indegree[i]==0) q.push(i);
        }
        int cnt=0;
        while(!q.empty()){
            int t=q.front();
            q.pop();
            cnt++;
            //遍历所有依赖t的课程
            for(int x:g[t]){
                if(--indegree[x]==0){
                    q.push(x);
                }
            }
        }
        return cnt==numCourses;
    } 
};

class Solution {
    public boolean canFinish(int numCourses, int[][] prerequisites) {
        List<List<Integer>> g=new ArrayList<>();
        int[] indegree=new int[numCourses];
        for(int i=0;i<numCourses;i++){
            g.add(new ArrayList<>());
        }
        for(int[]p:prerequisites){
            //p[1]->p[0]
            g.get(p[1]).add(p[0]);
            indegree[p[0]]++;
        }
        Queue<Integer> q=new LinkedList<>();
        for(int i=0;i<numCourses;i++){
            if(indegree[i]==0) q.offer(i);
        }
        int cnt=0;
        while(!q.isEmpty()){
            int t=q.poll();
            cnt++;
            for(int x:g.get(t)){
                if(--indegree[x]==0){
                    q.offer(x);
                }
            }
        }
        return cnt==numCourses;
    }
}

1.4 实现Tire树

208. 实现 Trie (前缀树) - 力扣（LeetCode）

代码实现（C++/Java）

const int N=3e6+10;
class Trie {
public:
    int son[N][26];
    bool status[N];
    int idx;
    Trie() {
        idx=0;
        memset(son,0,sizeof(son));
        memset(status,false,sizeof(status));
    }
    
    void insert(string word) {
        int p=0;
        for(int i=0;word[i];i++){
            int x=word[i]-'a';
            if(!son[p][x]){
                son[p][x]=++idx;
            }
            p=son[p][x];
        }
        status[p]=true;
    }
    
    bool search(string word) {
        int p=0;
        for(int i=0;word[i];i++){
            int x=word[i]-'a';
            if(!son[p][x]) return false;
            p=son[p][x];
        }
        return status[p];
    }
    
    bool startsWith(string prefix) {
        int p=0;
        for(int i=0;prefix[i];i++){
            int x=prefix[i]-'a';
            if(!son[p][x]) return false;
            p=son[p][x];
        }
        return true;
    }
};

class Trie {
    public static final int N=(int)3e5+10;
    public static int[][]son;
    public static boolean[]status;
    public static int idx;
    public Trie() {
        idx=0;
        son=new int[N][26];
        status=new boolean[N];
    }
    
    public void insert(String word) {
        int p=0;
        for(int i=0;i<word.length();i++){
            int x=word.charAt(i)-'a';
            if(son[p][x]==0){
                son[p][x]=++idx;
            }
            p=son[p][x];
        }
        status[p]=true;
    }
    
    public boolean search(String word) {
        int p=0;
        for(int i=0;i<word.length();i++){
            int x=word.charAt(i)-'a';
            if(son[p][x]==0)return false;
            p=son[p][x];
        }
        return status[p];
    }
    
    public boolean startsWith(String prefix) {
        int p=0;
        for(int i=0;i<prefix.length();i++){
            int x=prefix.charAt(i)-'a';
            if(son[p][x]==0) return false;
            p=son[p][x];
        }
        return true;
    }
}

2.回溯

2.1 全排列

46. 全排列 - 力扣（LeetCode）

代码实现（C++/Java）

const int N=12;
class Solution {
public:
    vector<vector<int>> res;
    int arr[N];
    bool status[N];
    void dfs(int x,vector<int>& nums){
        if(x==nums.size()){
            vector<int> t;
            for(int i=0;i<nums.size();i++){
                t.push_back(arr[i]);
            }
            res.push_back(t);
            return;
        }
        for(int i=0;i<nums.size();i++){
            if(!status[i]){
                arr[x]=nums[i];
                status[i]=true;
                dfs(x+1,nums);
                status[i]=false;
                arr[x]=0;
            }
        }
    }
    vector<vector<int>> permute(vector<int>& nums) {
        dfs(0,nums);
        return res;
    }
};

class Solution {
    public static List<List<Integer>> res;
    public static int[]arr;
    public static boolean[]status;
    public List<List<Integer>> permute(int[] nums) {
        int n=nums.length;
        arr=new int[n];
        status=new boolean[n];
        res=new ArrayList<>();
        dfs(0,nums);
        return res;
    }
    public static void dfs(int x,int[] nums){
        if(x==nums.length){
            ArrayList<Integer> t=new ArrayList<>();
            for(int i=0;i<nums.length;i++){
                t.add(arr[i]);
            }
            res.add(t);
            return;
        }
        for(int i=0;i<nums.length;i++){
            if(!status[i]){
                status[i]=true;
                arr[x]=nums[i];
                dfs(x+1,nums);
                arr[x]=0;
                status[i]=false;
            }
        }
    }
}

2.2 子集

78. 子集 - 力扣（LeetCode）

代码实现（C++/Java）

const int N=12;
class Solution {
public:
    vector<vector<int>> res;
    int status[N];
    vector<vector<int>> subsets(vector<int>& nums) {
        dfs(0,nums);
        return res;
    }
    void dfs(int x,vector<int> &nums){
        if(x==nums.size()){
            vector<int> t;
            for(int i=0;i<nums.size();i++){
                if(!status[i]) t.push_back(nums[i]);
            }
            res.push_back(t);
            return;
        }
        status[x]=true;
        dfs(x+1,nums);
        status[x]=false;
        dfs(x+1,nums);
    }
};

class Solution {
    public static List<List<Integer>> res;
    public static boolean[] status;
    public List<List<Integer>> subsets(int[] nums) {
        res=new ArrayList<>();
        status=new boolean[nums.length];
        dfs(0,nums);
        return res;
    }
    public static void dfs(int x,int[]nums){
        if(x==nums.length){
            ArrayList<Integer> t=new ArrayList<>();
            for(int i=0;i<nums.length;i++){
                if(!status[i]) t.add(nums[i]);
            }
            res.add(t);
            return;
        }
        status[x]=true;
        dfs(x+1,nums);
        status[x]=false;
        dfs(x+1,nums);
    }
}

2.3 电话号码的字母组合

17. 电话号码的字母组合 - 力扣（LeetCode）

代码实现（C++/Java）

class Solution {
public:
    unordered_map<char,string> map={
         {'2', "abc"}, {'3', "def"}, {'4', "ghi"}, {'5', "jkl"},
        {'6', "mno"}, {'7', "pqrs"}, {'8', "tuv"}, {'9', "wxyz"}
    };
    vector<string> res;
    vector<string> letterCombinations(string digits) {
        dfs(digits,0,"");
        return res;
    }
    void dfs(string digits,int x,string cur){
        if(x==digits.size()){
            res.push_back(cur);
            return;
        }
        string letters=map[digits[x]];
        for(char c:letters){
            dfs(digits,x+1,cur+c);
        }
    }
};

class Solution {
   public static final Map<Character, String> map = Map.of(
        '2', "abc", '3', "def", '4', "ghi", '5', "jkl",
        '6', "mno", '7', "pqrs", '8', "tuv", '9', "wxyz"
    );
    public static List<String> res;
    public List<String> letterCombinations(String digits) {
        res=new ArrayList<>();
        dfs(digits,0,"");
        return res;
    }
    public static void dfs(String digits,int x,String cur){
        if(x==digits.length()){
            res.add(cur);
            return;
        }
        String letters=map.get(digits.charAt(x));
        for(char l:letters.toCharArray()){
            dfs(digits,x+1,cur+l);
        }
        
    }
}

2.4 组合总和

39. 组合总和 - 力扣（LeetCode）

代码实现（C++/Java）

class Solution {
public:
    vector<vector<int>> res;
    vector<vector<int>> combinationSum(vector<int>& candidates, int target) {
        vector<int> cur;
        dfs(candidates,0,0,target,cur);
        return res;
    }
    void dfs(vector<int>& candidates,int start,int sum,int target,vector<int>& cur){
        if(sum==target){
            res.push_back(cur);
            return;
        }
        if(sum>target) return;
        for(int i=start;i<candidates.size();i++){
            cur.push_back(candidates[i]);
            dfs(candidates,i,sum+candidates[i],target,cur);
            cur.pop_back();
        }
    }
};

class Solution {
    public static List<List<Integer>> res;
    public List<List<Integer>> combinationSum(int[] candidates, int target) {
        res=new ArrayList<>();
        ArrayList<Integer> cur=new ArrayList<>();
        dfs(candidates,0,0,target,cur);
        return res;
    }
    public static void dfs(int[] candidates,int start,int sum,int target,List<Integer> cur){
        if(sum==target){
            res.add(new ArrayList<>(cur));
            return;
        }
        if(sum>target) return;
        for(int i=start;i<candidates.length;i++){
            cur.add(candidates[i]);
            dfs(candidates,i,sum+candidates[i],target,cur);
            cur.remove(cur.size()-1);
        }
    }
}

2.5 括号生成

22. 括号生成 - 力扣（LeetCode）

代码实现（C++/Java）

class Solution {
public:
    vector<string> res;
    vector<string> generateParenthesis(int n) {
        string line;
        dfs(n,0,0,line);
        return res;
    }
    void dfs(int n,int lcnt,int rcnt,string line){
        if(lcnt==n && rcnt==n){
            res.push_back(line);
            return;
        }
        if(lcnt<n) dfs(n,lcnt+1,rcnt,line+"(");
        if(rcnt<lcnt) dfs(n,lcnt,rcnt+1,line+")");
    }
};

class Solution {
    public static List<String> res;
    public List<String> generateParenthesis(int n) {
        res=new ArrayList<>();
        String line="";
        dfs(n,0,0,line);
        return res;
    }
    public static void dfs(int n,int lcnt,int rcnt,String line){
        if(lcnt==n && rcnt==n){
            res.add(line);
            return;
        }
        if(lcnt<n) dfs(n,lcnt+1,rcnt,line+"(");
        if(rcnt<lcnt) dfs(n,lcnt,rcnt+1,line+")");
    }
}

2.6 单词搜索

79. 单词搜索 - 力扣（LeetCode）

代码实现（C++/Java）

class Solution {
public:
    vector<vector<bool>> status;
    bool exist(vector<vector<char>>& board, string word) {
        int m = board.size(), n = board[0].size();
        status.resize(m, vector<bool>(n, false));
        for(int i=0;i<board.size();i++){
            for(int j=0;j<board[0].size();j++){
                if(dfs(board,word,i,j,0)) return true;
            }
        }
        return false;
    }
    bool dfs(vector<vector<char>>& board,string word,int x,int y,int k){
        if(x>=0 && x<board.size() && y>=0 && y<board[0].size() && !status[x][y] && word[k]==board[x][y]){
            if(k==word.size()-1) return true;
            status[x][y]=true;
            bool res=dfs(board,word,x+1,y,k+1)
                    || dfs(board,word,x-1,y,k+1)
                    || dfs(board,word,x,y+1,k+1)
                    || dfs(board,word,x,y-1,k+1);
            status[x][y]=false;
            return res;
        }
        return false;
    }
};

class Solution {
    public static boolean[][] status;
    public boolean exist(char[][] board, String word) {
        status=new boolean[board.length][board[0].length];
        for(int i=0;i<board.length;i++){
            for(int j=0;j<board[0].length;j++){
                if(dfs(board,word,i,j,0)) return true;
            }
        }
        return false;
    }
    public static boolean dfs(char[][] board,String word,int x,int y,int k){
        if(x>=0 && x<board.length && y>=0 && y<board[0].length && !status[x][y] && word.charAt(k)==board[x][y]){
            if(k==word.length()-1) return true;
            status[x][y]=true;
            boolean res=dfs(board,word,x+1,y,k+1)
                        || dfs(board,word,x-1,y,k+1)
                        || dfs(board,word,x,y+1,k+1)
                        || dfs(board,word,x,y-1,k+1);
            status[x][y]=false;
            return res;
        }
        return false;
    }
}

2.7 分割回文子串

131. 分割回文串 - 力扣（LeetCode）

代码实现（C++/Java）

class Solution {
public:
    vector<vector<string>> res;
    string str;
    vector<vector<string>> partition(string s) {
        res.clear();
        str=s;
        vector<string> cur;
        dfs(0,cur);
        return res;
    }
    void dfs(int start,vector<string> &cur){
        if(start>=str.size()){
            res.push_back(cur);
            return;
        }
        for(int i=start;i<str.size();i++){
            if(fun(start,i)){
                //(起点，长度)
                cur.push_back(str.substr(start,i-start+1));
                dfs(i+1,cur);
                cur.pop_back();
            }
        }
    }
    bool fun(int l,int r){
        while(r>l){
            if(str[l]!=str[r]) return false;
            r--;
            l++;
        }
        return true;
    }
};

class Solution {
    public static List<List<String>> res;
    public static char[] str;
    public List<List<String>> partition(String s) {
        res=new ArrayList<>();
        str=s.toCharArray();
        ArrayList<String> cur=new ArrayList<>();
        dfs(0,cur);
        return res;
    }
    public static void dfs(int start,ArrayList<String> cur){
        if(start>=str.length){
            res.add(new ArrayList<>(cur));
            return;
        }
        for(int i=start;i<str.length;i++){
            if(fun(start,i)){
                cur.add(new String(str,start,i-start+1));
                dfs(i+1,cur);
                cur.remove(cur.size()-1);
            }
        }
    }
    public static boolean fun(int l,int r){
        while(r>l){
            if(str[l]!=str[r]) return false;
            l++;
            r--;
        }
        return true;
    }
}

2.8 N皇后

51. N 皇后 - 力扣（LeetCode）

代码实现（C++/Java）

const int N=11;
class Solution {
public:
    vector<vector<string>> res;
    string graph[N];
    bool col[N];
    bool zuo[N*2];
    bool you[N*2];
    vector<vector<string>> solveNQueens(int n) {
        for(int i=0;i<n;i++){
            graph[i]=string(n,'.');
        }
        dfs(0,n);
        return res;
    }
    void dfs(int x,int n){
        if(x==n){
            vector<string> t;
            for(int i=0;i<n;i++){
                t.push_back(graph[i]);
            }
            res.push_back(t);
            return;
        }
        for(int i=0;i<n;i++){
            if(!col[i] && !zuo[x-i+n] && !you[x+i]){
                graph[x][i]='Q';
                col[i]=zuo[x-i+n]=you[x+i]=true;
                dfs(x+1,n);
                graph[x][i]='.';
                col[i]=zuo[x-i+n]=you[x+i]=false;
            }
        }
    }
};

class Solution {
    public static List<List<String>> res;
    public static boolean[]col;
    public static boolean[]zuo;
    public static boolean[]you;
    public static char[][]graph;
    public List<List<String>> solveNQueens(int n) {
        res=new ArrayList<>();
        col=new boolean[n]; 
        zuo=new boolean[2*n]; //行加列
        you=new boolean[2*n]; //行-列+n
        graph=new char[n][n];
        for(int i=0;i<n;i++){
            for(int j=0;j<n;j++){
                graph[i][j]='.';
            }
        }
        dfs(0,n);
        return res;
    }
    //遍历每一行
    public static void dfs(int x,int n){
        if(x==n){
            ArrayList<String> list=new ArrayList<>();
            for(int i=0;i<n;i++){
                list.add(new String(graph[i]));
            }
            res.add(list);
            return;
        }
        for(int i=0;i<n;i++){
            if(!col[i] && !zuo[x+i] && !you[x-i+n]){
                graph[x][i]='Q';
                col[i]=zuo[x+i]=you[x-i+n]=true;
                dfs(x+1,n);
                graph[x][i]='.';
                col[i]=zuo[x+i]=you[x-i+n]=false;
            }
        }
    }
}

3.二分

3.1 搜索插入位置

35. 搜索插入位置 - 力扣（LeetCode）

代码实现（C++/Java）

class Solution {
public:
    int searchInsert(vector<int>& nums, int target) {
        int n=nums.size();
        int l=0,r=n;
        while(r>l){
            int mid=(l+r)>>1;
            if(nums[mid]>=target){
                r=mid;
            } else {
                l=mid+1;
            }
        }
        return l;
    }
};

class Solution {
    public int searchInsert(int[] nums, int target) {
        int l=0,r=nums.length;
        while(r>l){
            int mid=(l+r-1)>>1;
            if(nums[mid]>=target){
                r=mid;
            }else {
                l=mid+1;
            }
        }
        return l;
    }
}

3.2 搜索二维矩阵

74. 搜索二维矩阵 - 力扣（LeetCode）

代码实现（C++/Java）

class Solution {
public:
    bool searchMatrix(vector<vector<int>>& matrix, int target) {
        int m=matrix.size();
        if(m==0) return false;
        int n=matrix[0].size();
        int l=0,r=m*n-1;
        while(r>l){
            int mid=(l+r)>>1;
            int num=matrix[mid/n][mid%n];
            if(num>=target){
                r=mid;
            } else {
                l=mid+1;
            }
        }
        return matrix[l/n][l%n]==target;
    }
};

class Solution {
    public boolean searchMatrix(int[][] matrix, int target) {
        int m=matrix.length;
        int n=matrix[0].length;
        int l=0,r=m*n-1;
        while(r>l){
            int mid=(l+r)>>1;
            if(matrix[mid/n][mid%n]>=target){
                r=mid;
            }else {
                l=mid+1;
            }
        }
        return matrix[l/n][l%n]==target;
    }
}

3.3 在排序数组中查找元素的第一个和最后一个位置

34. 在排序数组中查找元素的第一个和最后一个位置 - 力扣（LeetCode）

代码实现（C++/Java）

class Solution {
public:
    vector<int> searchRange(vector<int>& nums, int target) {
        int n=nums.size();
        if(n==0)  return {-1,-1};
        int l1=0,r1=n-1;
        while(r1>l1){
            int mid=(l1+r1)>>1;
            if(nums[mid]>=target){
                r1=mid;
            }else {
                l1=mid+1;
            }
        }
        if(nums[l1]!=target){
            return {-1,-1};
        }else {
            int l2=0,r2=n-1;
            while(r2>l2){
                int mid=(l2+r2+1)>>1;
                if(nums[mid]<=target){
                    l2=mid;
                }else {
                    r2=mid-1;
                }
            }
            return {l1,l2};
        }
        
    }
};

class Solution {
    public int[] searchRange(int[] nums, int target) {
        int n=nums.length;
        if(n==0) return new int[]{-1,-1};
        int l1=0,r1=n-1;
        while(r1>l1){
            int mid=(l1+r1)>>1;
            if(nums[mid]>=target){
                r1=mid;
            }else{
                l1=mid+1;
            }
        }
        if(nums[l1]!=target){
            return new int[]{-1,-1};
        }else{
            int l2=0,r2=n-1;
            while(r2>l2){
                int mid=(l2+r2+1)>>1;
                if(nums[mid]<=target){
                    l2=mid;
                }else{
                    r2=mid-1;
                }
            }
            return new int[]{l1,l2};
        }
        
    }
}

3.4 搜索旋转排序数组

33. 搜索旋转排序数组 - 力扣（LeetCode）

代码实现（C++/Java）

class Solution {
public:
    int search(vector<int>& nums, int target) {
        int n=nums.size();
        int l=0,r=n-1;
        while(r>l){
            int mid=(l+r)>>1;
            //左区间有序
            if(nums[mid]>=nums[l]){
                if(nums[mid]>=target && target>=nums[l]){
                    r=mid;
                }else {
                    l=mid+1;
                }        
            }else{
                //右区间有序
                if(nums[mid]<=target && target<=nums[r]){
                    l=mid;
                }else {
                    r=mid-1;
                }
            }
        }
        if(nums[l]==target) return l;
        else return -1;
        
    }
};

class Solution {
    public int search(int[] nums, int target) {
        int n=nums.length;
        int l=0,r=n-1;
        while(r>l){
            int mid=(l+r)>>1;
            //左区间
            if(nums[mid]>=nums[l]){
                if(nums[mid]>=target && target>=nums[l]){
                    r=mid;
                }else {
                    l=mid+1;
                }
            }else {
                //右区间
                if(nums[mid]<=target && target<=nums[r]){
                    l=mid;
                }else {
                    r=mid-1;
                }
            }
        }
        if(nums[l]==target) return l;
        else return -1;
    }
}

3.5 寻找旋转排序数组中的最小值

153. 寻找旋转排序数组中的最小值 - 力扣（LeetCode）

代码实现（C++/Java）

class Solution {
public:
    int findMin(vector<int>& nums) {
        int n=nums.size();
        int l=0,r=n-1;
        while(r>l){
            int mid=(l+r)>>1;
            if(nums[mid]>nums[r]){
                //最小值在右半段，缩小左边界
                l=mid+1;
            }else{
                r=mid;
            }
        }
        return nums[l];
    }
};

class Solution {
    public int findMin(int[] nums) {
        int n=nums.length;
        int l=0,r=n-1;
        while(r>l){
            int mid=(l+r)>>1;
            if(nums[mid]>nums[r]){
                l=mid+1;
            }else {
                r=mid;
            }
        }
        return nums[l];
    }
}

3.5 寻找两个正序数组的中位数

4. 寻找两个正序数组的中位数 - 力扣（LeetCode）

代码实现（C++/Java）

class Solution {
public:
    double findMedianSortedArrays(vector<int>& nums1, vector<int>& nums2) {
        int total = nums1.size() + nums2.size();
        // 奇数：找第(total+1)/2小的数
        if (total % 2 == 1) {
            return findKthSmallest(nums1, nums2, (total + 1) / 2);
        } else {
            // 偶数：找第total/2和total/2+1小的数，取平均
            int k1 = total / 2;
            int k2 = total / 2 + 1;
            return (findKthSmallest(nums1, nums2, k1) + findKthSmallest(nums1, nums2, k2)) / 2.0;
        }
    }
private:
    // 核心函数：找两个有序数组中第k小的数（完全贴合二分模板逻辑）
    int findKthSmallest(vector<int>& nums1, vector<int>& nums2, int k) {
        // 初始化两个数组的当前左边界（贴合你的模板：l=0）
        int l1 = 0, l2 = 0;
        int m = nums1.size(), n = nums2.size();
        // 循环缩边界（核心：每次排除k/2个不可能的数，贴合你的r>l循环逻辑）
        while (true) {
            // 边界情况1：nums1已空，直接返回nums2的第k小
            if (l1 == m) return nums2[l2 + k - 1];
            // 边界情况2：nums2已空，直接返回nums1的第k小
            if (l2 == n) return nums1[l1 + k - 1];
            // 边界情况3：k=1，返回当前首元素的最小值（循环终止条件）
            if (k == 1) return min(nums1[l1], nums2[l2]);
            // 计算mid（贴合你的mid=(l+r)>>1，这里是k/2）
            int mid = k >> 1; // 等价于k/2
            // 确定要比较的位置（避免越界）
            int idx1 = min(l1 + mid - 1, m - 1);
            int idx2 = min(l2 + mid - 1, n - 1);
            // 核心：比较两个mid位置的值，缩边界（排除不可能的区间）
            if (nums1[idx1] <= nums2[idx2]) {
                // 排除nums1[l1..idx1]，缩nums1的左边界（贴合你的l=mid+1）
                k -= (idx1 - l1 + 1);
                l1 = idx1 + 1;
            } else {
                // 排除nums2[l2..idx2]，缩nums2的左边界
                k -= (idx2 - l2 + 1);
                l2 = idx2 + 1;
            }
        }
    }
};

class Solution {
    public double findMedianSortedArrays(int[] nums1, int[] nums2) {
        int total = nums1.length + nums2.length;
        // 奇数：找第(total+1)/2小的数
        if (total % 2 == 1) {
            return findKthSmallest(nums1, nums2, (total + 1) / 2);
        } else {
            // 偶数：找第total/2和total/2+1小的数，取平均
            int k1 = total / 2;
            int k2 = total / 2 + 1;
            return (findKthSmallest(nums1, nums2, k1) + findKthSmallest(nums1, nums2, k2)) / 2.0;
        }
    }
    // 核心函数：找两个有序数组中第k小的数（完全贴合二分模板逻辑）
    private int findKthSmallest(int[] nums1, int[] nums2, int k) {
        // 初始化两个数组的当前左边界（贴合你的模板：l=0）
        int l1 = 0, l2 = 0;
        int m = nums1.length, n = nums2.length;
        // 循环缩边界（核心：每次排除k/2个不可能的数，贴合你的r>l循环逻辑）
        while (true) {
            // 边界情况1：nums1已空，直接返回nums2的第k小
            if (l1 == m) return nums2[l2 + k - 1];
            // 边界情况2：nums2已空，直接返回nums1的第k小
            if (l2 == n) return nums1[l1 + k - 1];
            // 边界情况3：k=1，返回当前首元素的最小值（循环终止条件）
            if (k == 1) return Math.min(nums1[l1], nums2[l2]);
            // 计算mid（贴合你的mid=(l+r)>>1，这里是k/2）
            int mid = k >> 1; // 等价于k/2
            // 确定要比较的位置（避免越界）
            int idx1 = Math.min(l1 + mid - 1, m - 1);
            int idx2 = Math.min(l2 + mid - 1, n - 1);
            // 核心：比较两个mid位置的值，缩边界（排除不可能的区间）
            if (nums1[idx1] <= nums2[idx2]) {
                // 排除nums1[l1..idx1]，缩nums1的左边界（贴合你的l=mid+1）
                k -= (idx1 - l1 + 1);
                l1 = idx1 + 1;
            } else {
                // 排除nums2[l2..idx2]，缩nums2的左边界
                k -= (idx2 - l2 + 1);
                l2 = idx2 + 1;
            }
        }
    }
}

4.栈

4.1 有效的括号

20. 有效的括号 - 力扣（LeetCode）

代码实现（C++/Java）

class Solution {
public:
    bool isValid(string s) {
        stack<char> stk;
        for(int i=0;s[i];i++){
            char c=s[i];
            if(c=='(') stk.push(')');
            else if(c=='[') stk.push(']');
            else if(c=='{') stk.push('}');
            else if(stk.empty() || stk.top()!=c) return false;
            else stk.pop();
        }
        return stk.empty();
    }
};

class Solution {
    public boolean isValid(String s) {
        Stack<Character> stk=new Stack<>();
        for(int i=0;i<s.length();i++){
            char c=s.charAt(i);
            if(c=='(') stk.push(')');
            else if(c=='{') stk.push('}');
            else if(c=='[') stk.push(']');
            else if(stk.isEmpty() || stk.peek()!=c) return false;
            else stk.pop();
        }
        return stk.isEmpty();
    }
}

4.2 最小栈

155. 最小栈 - 力扣（LeetCode）

代码实现（C++/Java）

class MinStack {
public:
    stack<int> stk;
    stack<int> mstk;
    MinStack() {
    }
    
    void push(int val) {
        stk.push(val);
        //第一个元素
        if(mstk.empty()){
            mstk.push(val);
        }else {
            mstk.push(min(val,mstk.top()));
        }
    }
    
    void pop() {
        stk.pop();
        mstk.pop();
    }
    
    int top() {
        return stk.top();
    }
    
    int getMin() {
        return mstk.top();
    }
};

class MinStack {
    public Stack<Integer> stk;
    public Stack<Integer> mstk;
    public MinStack() {
        stk=new Stack<>();
        mstk=new Stack<>();
    }
    
    public void push(int val) {
        stk.push(val);
        if(mstk.isEmpty()){
            mstk.push(val);
        }else {
            mstk.push(Math.min(val,mstk.peek()));
        }
    }
    
    public void pop() {
        stk.pop();
        mstk.pop();
    }
    
    public int top() {
        return stk.peek();
    }
    
    public int getMin() {
        return mstk.peek();
    }
}

4.6 最长有效括号

32. 最长有效括号 - 力扣（LeetCode）

代码实现（C++/Java）

class Solution {
public:
    int longestValidParentheses(string s) {
        stack<int> stk;
        stk.push(-1);
        int res=0;
        for(int i=0;i<s.size();i++){
            if(s[i]=='('){
                stk.push(i);
            }else {
                stk.pop();
                if(stk.empty()){
                    stk.push(i);
                }else{
                    res=max(res,i-stk.top());
                }
            }
        }
        return res;
    }
};

class Solution {
    public int longestValidParentheses(String s) {
        Stack<Integer> stk=new Stack<>();
        stk.push(-1);
        int res=0;
        for(int i=0;i<s.length();i++){
            if(s.charAt(i)=='('){
                stk.push(i);
            }else {
                stk.pop();
                if(stk.isEmpty()){
                    stk.push(i);
                }else {
                    res=Math.max(res,i-stk.peek());
                }
            }
        }
        return res;
    }
}

5.堆

5.1 数组中的第K个最大元素

215. 数组中的第K个最大元素 - 力扣（LeetCode）

代码实现（C++/Java）

class Solution {
public:
    vector<int> heap;
    int cnt;
    void down(int u){
        int t=u;
        if(u*2<=cnt && heap[u*2]>heap[t]) t=u*2;
        if(u*2+1<=cnt && heap[u*2+1]>heap[t]) t=u*2+1;
        if(t!=u){
            swap(heap[t],heap[u]);
            down(t);
        }
    }
    int findKthLargest(vector<int>& nums, int k) {
        int n=nums.size();
        heap.resize(n+1);
        heap[0]=-1;
        cnt=n;
        for(int i=0;i<n;i++) heap[i+1]=nums[i];
        for(int i=n/2;i>=1;i--) down(i);
        for(int i=1;i<k;i++){
            heap[1]=heap[cnt];
            cnt--;
            down(1);
        }
        return heap[1];
    }
};

class Solution {
    public static final int N=(int)1e5+10;
    public static int[] heap=new int[N];
    public static int cnt;
    public int findKthLargest(int[] nums, int k) {
        int n=nums.length;
        cnt=n;
        for(int i=0;i<n;i++) heap[i+1]=nums[i];
        for(int i=n/2;i>=1;i--){
            down(i);
        }
        for(int i=1;i<k;i++){
            heap[1]=heap[cnt];
            cnt--;
            down(1);
        }
        return heap[1];
    }
    public static void down(int u){
        int t=u;
        if(u*2<=cnt && heap[u*2]>heap[t]) t=u*2;
        if(u*2+1<=cnt && heap[u*2+1]>heap[t]) t=u*2+1;
        if(t!=u){
            int a=heap[t];
            heap[t]=heap[u];
            heap[u]=a;
            down(t);
        }
    }
}

5.2 前K个高频元素

347. 前 K 个高频元素 - 力扣（LeetCode）

代码实现（C++/Java）

typedef pair<int,int> PII;
class Solution { 
public:
    vector<PII> heap;
    int cnt;
    void down(int u){
        int t=u;
        if(u*2<=cnt && heap[u*2].second>heap[t].second) t=u*2;
        if(u*2+1<=cnt && heap[u*2+1].second>heap[t].second) t=u*2+1;
        if(u!=t){
            swap(heap[t],heap[u]);
            down(t);
        }
    }
    vector<int> topKFrequent(vector<int>& nums, int k) {
        unordered_map<int,int> freq;
        for(int num:nums) freq[num]++;
        int n=freq.size();
        heap.resize(n+10);
        cnt=n;
        int idx=1;
        for(auto &t:freq) heap[idx++]=t;
        for(int i=n/2;i>=1;i--) down(i);
        vector<int> res;
        for(int i=1;i<=k;i++){
            res.push_back(heap[1].first);
            heap[1]=heap[cnt];
            cnt--;
            down(1);
        }
        return res;
        
    }
};

class Solution {
    public static int[][] heap;
    public static int cnt;
    public int[] topKFrequent(int[] nums, int k) {
        Map<Integer,Integer> freq=new HashMap<>();
        for(int num:nums){
            freq.put(num,freq.getOrDefault(num,0)+1);
        }
        int n=freq.size();
        heap=new int[n+10][2];
        cnt=n;
        int idx=1;
        for(Map.Entry<Integer,Integer> entry:freq.entrySet()){
            heap[idx][0]=entry.getKey();
            heap[idx][1]=entry.getValue();
            idx++;
        }
        for(int i=n/2;i>=1;i--) down(i);
        int[]res=new int[k];
        for(int i=0;i<k;i++){
            res[i]=heap[1][0];
            heap[1]=heap[cnt];
            cnt--;
            down(1);
        }
        return res;
    }
    public static void down(int u){
        int t=u;
        if(u*2<=cnt && heap[u*2][1]>heap[t][1]){
            t=u*2;
        }
        if(u*2+1<=cnt && heap[u*2+1][1]>heap[t][1]){
            t=u*2+1;
        }
        if(u!=t){
            int[] tmp=heap[t];
            heap[t]=heap[u];
            heap[u]=tmp;
            down(t);
        }
    }
}

5.3 数据流的中位数

295. 数据流的中位数 - 力扣（LeetCode）

代码实现（C++/Java）

class MedianFinder {
public:
    priority_queue<int,vector<int>,less<int>> max_heap;//大根堆
    priority_queue<int,vector<int>,greater<int>> min_heap;//小根堆
    MedianFinder() {
        
    }
    
    void addNum(int num) {
        //优先往大根堆存
        if(max_heap.empty()||num<=max_heap.top()){
            max_heap.push(num);
        }else {
            min_heap.push(num);
        }
        //平衡
        if(max_heap.size()>=min_heap.size()+1){
            min_heap.push(max_heap.top());
            max_heap.pop();
        }
        if(min_heap.size()>=max_heap.size()+1){
            max_heap.push(min_heap.top());
            min_heap.pop();
        }
    }
    
    double findMedian() {
        if(max_heap.size()>min_heap.size()){
            return (double)max_heap.top();
        }else if(min_heap.size()>max_heap.size()){
            return (double)min_heap.top();
        }else {
            return (min_heap.top()+max_heap.top())/2.0;
        }
    }
};

class MedianFinder {
    private PriorityQueue<Integer> maxHeap;
    private PriorityQueue<Integer> minHeap;
    public MedianFinder() {
        minHeap=new PriorityQueue<>();//默认小根堆
        maxHeap=new PriorityQueue<>(Comparator.reverseOrder());//大根堆
    }
    
    public void addNum(int num) {
        if(maxHeap.isEmpty() || num<=maxHeap.peek()){
            maxHeap.offer(num);
        }else {
            minHeap.offer(num);
        }
        //平衡
        if(maxHeap.size()>minHeap.size()+1){
            minHeap.offer(maxHeap.poll());
        }else if(minHeap.size()>maxHeap.size()+1){
            maxHeap.offer(minHeap.poll());
        }
        
    }
    
    public double findMedian() {
        if(maxHeap.size()>minHeap.size()){
            return (double)maxHeap.peek();
        }else if(minHeap.size()>maxHeap.size()){
            return (double)minHeap.peek();
        }else {
            return (minHeap.peek()+maxHeap.peek())/2.0;
        }
    }
}

6.贪心算法

6.1 买卖股票的最佳时机

121. 买卖股票的最佳时机 - 力扣（LeetCode）

代码实现（C++/Java）

const int MAX=0x3f3f3f3f;
class Solution {
public:
    int maxProfit(vector<int>& prices) {
        int minPrice=MAX;
        int res=0;
        for(int i=0;i<prices.size();i++){
            minPrice=min(prices[i],minPrice);
            res=max(res,prices[i]-minPrice);
        }
        return res;
    }
};

class Solution {
    public int maxProfit(int[] prices) {
        int minPrice=0x3f3f3f3f;
        int res=0;
        for(int i=0;i<prices.length;i++){
            minPrice=Math.min(minPrice,prices[i]);
            res=Math.max(res,prices[i]-minPrice);
        }
        return res;
    }
}

6.2 跳跃游戏

55. 跳跃游戏 - 力扣（LeetCode）

代码实现（C++/Java）

class Solution {
public:
    bool canJump(vector<int>& nums) {
        int cover=0;
        for(int i=0;i<=cover;i++){
            cover=max(cover,i+nums[i]);
            if(cover>=nums.size()-1) return true;
        }
        return false;
    }
};

class Solution {
    public boolean canJump(int[] nums) {
        int cover=0;
        for(int i=0;i<=cover;i++){
            cover=Math.max(cover,i+nums[i]);
            if(cover>=nums.length-1) return true;
        }
        return false;
    }
}

6.3 跳跃游戏2

45. 跳跃游戏 II - 力扣（LeetCode）

代码实现（C++/Java）

class Solution {
public:
    int jump(vector<int>& nums) {
        if(nums.size()==1) return 0;
        int cur=0;//在当前圈内能跳到的最远距离
        int next=0;//在当前圈内，能向外跳到的最远距离
        int res=0;//跳的次数
        for(int i=0;i<nums.size();i++){
            //在当前范围内，寻找能跳到圈外的最优解
            next=max(next,nums[i]+i);
            //走到圈边界必须进行一次跳跃
            if(i==cur){
                res++;
                cur=next;
                if(next>=nums.size()-1) break;
            }
        }
        return res;
    }
};

class Solution {
    public int jump(int[] nums) {
       if(nums.length==1) return 0;
       int cur=0;
       int next=0;
       int res=0;
       for(int i=0;i<nums.length;i++){
            next=Math.max(next,i+nums[i]);
            if(i==cur){
                cur=next;
                res++;
                if(next>=nums.length-1) break;
            }
       }
       return res;
    }
}

6.4 划分字母区间

763. 划分字母区间 - 力扣（LeetCode）

代码实现（C++/Java）

class Solution {
public:
    vector<int> partitionLabels(string s) {
        vector<int> res;
        vector<int> hash(27,0);
        for(int i=0;i<s.size();i++) hash[s[i]-'a']=i;
        int l=0,r=0;
        for(int i=0;i<s.size();i++){
            r=max(r,hash[s[i]-'a']);
            if(i==r){
                res.push_back(r-l+1);
                l=i+1;
            }
        }
        return res;
    }
};

class Solution {
    public List<Integer> partitionLabels(String s) {
        List<Integer> res=new ArrayList<>();
        int[] hash=new int[27]; 
        for(int i=0;i<s.length();i++) hash[s.charAt(i)-'a']=i;
        int l=0,r=0;
        for(int i=0;i<s.length();i++){
            r=Math.max(r,hash[s.charAt(i)-'a']);
            if(i==r){
                res.add(r-l+1);
                l=i+1;
            }
        }
        return res;
    }
}

7. 动态规划

7.1 爬楼梯

70. 爬楼梯 - 力扣（LeetCode）

代码实现（C++/Java）

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

class Solution {
    public int climbStairs(int n) {
        int[]dp=new int[n+10];
        dp[0]=1;
        dp[1]=1;
        for(int i=2;i<=n;i++)dp[i]=dp[i-1]+dp[i-2];
        return dp[n];
    }
}

7.2 杨辉三角

118. 杨辉三角 - 力扣（LeetCode）

代码实现（C++/Java）

class Solution {
public:
    vector<vector<int>> generate(int numRows) {
        vector<vector<int>> res;
        vector<vector<int>> dp(numRows+10,vector<int>(numRows+10,0));
        dp[1][1]=1;
        vector<int> head;
        head.push_back(dp[1][1]);
        res.push_back(head);
        for(int i=2;i<=numRows;i++){
            vector<int> list;
            for(int j=1;j<=i;j++){
                dp[i][j]=dp[i-1][j]+dp[i-1][j-1];
                list.push_back(dp[i][j]);
            }
            res.push_back(list);
        }
        return res;
    }
};

class Solution {
    public List<List<Integer>> generate(int numRows) {
        List<List<Integer>> res=new ArrayList<>();
        int[][] dp=new int[numRows+10][numRows+10];
        dp[1][1]=1;
        List<Integer> head=new ArrayList<>();
        head.add(dp[1][1]);
        res.add(head);
        for(int i=2;i<=numRows;i++){
            ArrayList<Integer> list=new ArrayList<>();
            for(int j=1;j<=i;j++){
                dp[i][j]=dp[i-1][j-1]+dp[i-1][j];
                list.add(dp[i][j]);
            }
            res.add(list);
        }
        return res;
    }
}

7.3 打家劫舍

198. 打家劫舍 - 力扣（LeetCode）

代码实现（C++/Java）

class Solution {
public:
    int rob(vector<int>& nums) {
        if(nums.size()==0) return 0;
        if(nums.size()==1) return nums[0];
        vector<int> dp(nums.size()+10,0);
        dp[0]=nums[0];
        dp[1]=max(nums[0],nums[1]);
        for(int i=2;i<nums.size();i++){
            dp[i]=max(dp[i-1],dp[i-2]+nums[i]);
        }
        return dp[nums.size()-1];
    }
};

class Solution {
    public int rob(int[] nums) {
        if(nums.length==0) return 0;
        if(nums.length==1) return nums[0];
        int[] dp=new int[nums.length+10];
        dp[0]=nums[0];
        dp[1]=Math.max(nums[0],nums[1]);
        for(int i=2;i<nums.length;i++){
            dp[i]=Math.max(dp[i-1],dp[i-2]+nums[i]);
        }
        return dp[nums.length-1];
    }
}

7.4 完全平方数

279. 完全平方数 - 力扣（LeetCode）

代码实现（C++/Java）

class Solution {
public:
    int numSquares(int n) {
        vector<int> dp(n+10,0x3f3f3f3f);
        dp[0]=0;
        for(int i=1;i*i<=n;i++){
            for(int j=i*i;j<=n;j++){
                dp[j]=min(dp[j],dp[j-i*i]+1);
            }
        }
        return dp[n];
    }
};

class Solution {
    public int numSquares(int n) {
        int[] dp=new int[n+10];
        Arrays.fill(dp,0x3f3f3f3f);
        dp[0]=0;
        for(int i=1;i*i<=n;i++){
            for(int j=i*i;j<=n;j++){
                dp[j]=Math.min(dp[j],dp[j-i*i]+1);
            }
        }
        return dp[n];
    }
}

7.5 零钱兑换

322. 零钱兑换 - 力扣（LeetCode）

代码实现（C++/Java）

class Solution {
public:
    int coinChange(vector<int>& coins, int amount) {
        vector<int> dp(amount+10,0x3f3f3f3f);
        dp[0]=0;
        for(int i=0;i<coins.size();i++){
            for(int j=coins[i];j<=amount;j++){
                dp[j]=min(dp[j],dp[j-coins[i]]+1);
            }
        }
        if(dp[amount]==0x3f3f3f3f) return -1;
        else return dp[amount];
    }
};

class Solution {
    public int coinChange(int[] coins, int amount) {
        int[] dp=new int[amount+10];
        Arrays.fill(dp,0x3f3f3f3f);
        dp[0]=0;
        for(int i=0;i<coins.length;i++){
            for(int j=coins[i];j<=amount;j++){
                dp[j]=Math.min(dp[j],dp[j-coins[i]]+1);
            }
        }
        if(dp[amount]==0x3f3f3f3f) return -1;
        else return dp[amount];
    }
}

7.6 单词拆分

139. 单词拆分 - 力扣（LeetCode）

代码实现（C++/Java）

class Solution {
public:
    bool wordBreak(string s, vector<string>& wordDict) {
        unordered_set<string> set(wordDict.begin(),wordDict.end());
        int n=s.size();
        vector<int> dp(n+1,false);
        dp[0]=true;
        for(int i=1;i<=n;i++){
            for(int j=0;j<i;j++){
                if(dp[j] && set.find(s.substr(j,i-j))!=set.end()){
                    dp[i]=true;
                    break;
                }
            }
        }
        return dp[n];
    }
};

class Solution {
    public boolean wordBreak(String s, List<String> wordDict) {
        Set<String> set=new HashSet<>(wordDict);
        boolean[] dp=new boolean[s.length()+10];
        dp[0]=true;
        for(int i=1;i<=s.length();i++){
            for(int j=0;j<i;j++){
                String word=s.substring(j,i);
                if(dp[j] && set.contains(word)){
                    dp[i]=true;
                    break;
                }
            }
        }
        return dp[s.length()];
    }
}

7.7 最长递增子序列

300. 最长递增子序列 - 力扣（LeetCode）

代码实现（C++/Java）

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

class Solution {
    public int lengthOfLIS(int[] nums) {
        int n=nums.length;
        int []dp=new int[n];
        Arrays.fill(dp,1);
        for(int i=1;i<n;i++){
            for(int j=0;j<i;j++){
                if(nums[j]<nums[i]){
                    dp[i]=Math.max(dp[i],dp[j]+1);
                }
            }
        }
        int res=-1;
        for(int i=0;i<n;i++){
            res=Math.max(res,dp[i]);
        }
        return res;
    }
}

7.8 乘积最大子数组

152. 乘积最大子数组 - 力扣（LeetCode）

代码实现（C++/Java）

class Solution {
public:
    int maxProduct(vector<int>& nums) {
        int maxF=nums[0];
        int minF=nums[0];
        int res=nums[0];
        for(int i=1;i<nums.size();i++){
            if(nums[i]<0) swap(maxF,minF);
            maxF=max(nums[i],maxF*nums[i]);
            minF=min(nums[i],minF*nums[i]);
            res=max(res,maxF);
        }
        return res;
    }
};

class Solution {
    public int maxProduct(int[] nums) {
        int maxF=nums[0];
        int minF=nums[0];
        int res=nums[0];
        for(int i=1;i<nums.length;i++){
            if(nums[i]<0){
                int t=maxF;
                maxF=minF;
                minF=t;
            }
            maxF=Math.max(nums[i],maxF*nums[i]);
            minF=Math.min(nums[i],minF*nums[i]);
            res=Math.max(res,maxF);
        }
        return res;
    }
}

7.9 分割等和子集

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

代码实现（C++/Java）

class Solution {
public:
    bool canPartition(vector<int>& nums) {
        int sum=0;
        for(int i=0;i<nums.size();i++) sum+=nums[i];
        if(sum%2!=0) return false;
        int target=sum/2;
        vector<int> dp(target+10,0);
        for(int i=0;i<nums.size();i++){
            for(int j=target;j>=nums[i];j--){
                dp[j]=max(dp[j],dp[j-nums[i]]+nums[i]);
            }
        }
        return dp[target]==target;
    }
};

class Solution {
    public boolean canPartition(int[] nums) {
        int sum=0;
        for(int i=0;i<nums.length;i++) sum+=nums[i];
        if(sum%2!=0) return false;
        int target=sum/2;
        int []dp=new int[target+10];
        for(int i=0;i<nums.length;i++){
            for(int j=target;j>=nums[i];j--){
                dp[j]=Math.max(dp[j],dp[j-nums[i]]+nums[i]);
            }
        }
        return dp[target]==target;
    }
}

8.多维动态规划

8.1 不同路径

62. 不同路径 - 力扣（LeetCode）

代码实现（C++/Java）

class Solution {
public:
    int uniquePaths(int m, int n) {
        int dp[m+10][n+10];
        for(int i=0;i<m;i++) dp[i][0]=1;
        for(int i=0;i<n;i++) dp[0][i]=1;
        for(int i=1;i<m;i++){
            for(int j=1;j<n;j++){
                dp[i][j]=dp[i][j-1]+dp[i-1][j];
            }
        }
        return dp[m-1][n-1];
    }
};

class Solution {
    public int uniquePaths(int m, int n) {
        int[][] dp=new int[m+10][n+10];
        for(int i=0;i<m;i++) dp[i][0]=1;
        for(int i=0;i<n;i++) dp[0][i]=1;
        for(int i=1;i<m;i++){
            for(int j=1;j<n;j++){
                dp[i][j]=dp[i-1][j]+dp[i][j-1];
            }
        }
        return dp[m-1][n-1];
    }
}

8.2 最小路径和

64. 最小路径和 - 力扣（LeetCode）

代码实现（C++/Java）

class Solution {
public:
    int minPathSum(vector<vector<int>>& grid) {
        int m=grid.size();
        int n=grid[0].size();
        int dp[m+10][n+10];
        dp[0][0]=grid[0][0];
        for(int i=1;i<m;i++) dp[i][0]=dp[i-1][0]+grid[i][0];
        for(int i=1;i<n;i++) dp[0][i]=dp[0][i-1]+grid[0][i];
        for(int i=1;i<m;i++){
            for(int j=1;j<n;j++){
                dp[i][j]=grid[i][j]+min(dp[i-1][j],dp[i][j-1]);
            }
        } 
        return dp[m-1][n-1];
    }
};

class Solution {
    public int minPathSum(int[][] grid) {
        int m=grid.length;
        int n=grid[0].length;
        int[][] dp=new int[m+10][n+10];
        dp[0][0]=grid[0][0];
        for(int i=1;i<m;i++) dp[i][0]=dp[i-1][0]+grid[i][0];
        for(int i=1;i<n;i++) dp[0][i]=dp[0][i-1]+grid[0][i];
        for(int i=1;i<m;i++){
            for(int j=1;j<n;j++){
                dp[i][j]=grid[i][j]+Math.min(dp[i-1][j],dp[i][j-1]);
            }
        }
        return dp[m-1][n-1];
    }
}

8.3 最长回文子串

5. 最长回文子串 - 力扣（LeetCode）

代码实现（C++/Java）

class Solution {
public:
    string longestPalindrome(string s) {
        int n=s.size();
        //s[i,j]是否为回文子串
        vector<vector<bool>> dp(n,vector<bool>(n,false));
        int maxLen=1,begin=0;
        for(int i=0;i<n;i++) dp[i][i]=true;
        for(int l=2;l<=n;l++){ //枚举子串长度
            for(int i=0;i<n;i++){ //枚举左边界
                int j=i+l-1;//右边界
                if(j>=n) break;//越界
                if(s[i]==s[j]){
                    if(l==2) dp[i][j]=true;
                    else dp[i][j]=dp[i+1][j-1];
                }
                //更新
                if(dp[i][j] && l>maxLen){
                    maxLen=l;
                    begin=i;
                }
            }
        }
        return s.substr(begin, maxLen);
    }
};

class Solution {
    public String longestPalindrome(String str) {
       int n=str.length();
       boolean[][] dp=new boolean[n][n];
       for(int i=0;i<n;i++){
            dp[i][i]=true;
       }
       int maxLen=1,begin=0;
       for(int l=2;l<=n;l++){//长度
            for(int i=0;i<n;i++){//左端点
                int j=i+l-1;
                if(j>=n) break;
                if(str.charAt(i)==str.charAt(j)){
                    if(l==2) dp[i][j]=true;
                    else dp[i][j]=dp[i+1][j-1];
                } 
            if(dp[i][j] && l>maxLen){
                maxLen=l;
                begin=i;
            }
            }
       }
       return str.substring(begin,begin+maxLen);
    }
}

8.4 最长公共子序列

1143. 最长公共子序列 - 力扣（LeetCode）

代码实现（C++/Java）

class Solution {
public:
    int longestCommonSubsequence(string text1, string text2) {
        int n1=text1.size();
        int n2=text2.size();
        vector<vector<int>> dp(n1+10,vector<int>(n2+10,0));
        for(int i=1;i<=n1;i++){
            for(int j=1;j<=n2;j++){
                if(text1[i-1]==text2[j-1]){
                    dp[i][j]=dp[i-1][j-1]+1;
                }else {
                    dp[i][j]=max(dp[i-1][j],dp[i][j-1]);
                }
            }
        }
        return dp[n1][n2];
    }
};

class Solution {
    public int longestCommonSubsequence(String text1, String text2) {
       int n1=text1.length();
       int n2=text2.length();
       int[][] dp=new int[n1+10][n2+10];
       for(int i=1;i<=n1;i++){
            for(int j=1;j<=n2;j++){
                if(text1.charAt(i-1)==text2.charAt(j-1)){
                    dp[i][j]=dp[i-1][j-1]+1;
                }else {
                    dp[i][j]=Math.max(dp[i-1][j],dp[i][j-1]);
                }
            }
       }
       return dp[n1][n2];
    }
}

8.5 编辑距离

72. 编辑距离 - 力扣（LeetCode）

代码实现（C++/Java）

class Solution {
public:
    int minDistance(string word1, string word2) {
        int n1=word1.size();
        int n2=word2.size();
        vector<vector<int>> dp(n1+10,vector<int>(n2+10,0));
        for(int i=0;i<=n1;i++) dp[i][0]=i;
        for(int i=0;i<=n2;i++) dp[0][i]=i;
        for(int i=1;i<=n1;i++){
            for(int j=1;j<=n2;j++){
                if(word1[i-1]==word2[j-1]){
                    dp[i][j]=dp[i-1][j-1];
                }else {
                    dp[i][j]=min({dp[i-1][j-1]+1,dp[i-1][j]+1,dp[i][j-1]+1});
                }
            }
        }
        return dp[n1][n2];
    }
};

class Solution {
    public int minDistance(String word1, String word2) {
        int n1=word1.length();
        int n2=word2.length();
        int[][] dp=new int[n1+10][n2+10];
        for(int i=0;i<=n1;i++) dp[i][0]=i;
        for(int i=0;i<=n2;i++) dp[0][i]=i;
        for(int i=1;i<=n1;i++){
            for(int j=1;j<=n2;j++){
                if(word1.charAt(i-1)==word2.charAt(j-1)){
                    dp[i][j]=dp[i-1][j-1];
                }else {
                    dp[i][j]=Math.min(dp[i-1][j-1]+1,Math.min(dp[i-1][j]+1,dp[i][j-1]+1));
                }
            }
        }
        return dp[n1][n2];
    }
}

9.技巧

9.1 只出现一次的数字

136. 只出现一次的数字 - 力扣（LeetCode）

代码实现（C++/Java）

class Solution {
public:
    //异或性质：相同为0，不同为1，1^1=0,0^0=0,1^0=1
    int singleNumber(vector<int>& nums) {
        int cur=0;
        for(int i=0;i<nums.size();i++){
            cur=cur^nums[i];
        }
        return cur;
    }
};

class Solution {
    public int singleNumber(int[] nums) {
        int cur=0;
        for(int i=0;i<nums.length;i++){
            cur=cur^nums[i];
        }
        return cur;
    }
}

9.2 多数元素

169. 多数元素 - 力扣（LeetCode）

代码实现（C++/Java）

class Solution {
public:
    int majorityElement(vector<int>& nums) {
        unordered_map<int,int> map;
        int n=nums.size();
        for(int num:nums){
            map[num]++;
            if(map[num]>n/2) return num;
        }
        return -1;
    }
};

class Solution {
    public int majorityElement(int[] nums) {
        Map<Integer,Integer> map=new HashMap<>();
        int n=nums.length;
        for(int num:nums){
            map.put(num,map.getOrDefault(num,0)+1);
            if(map.get(num)>n/2) return num;
        }
        return -1;
    }
}

9.3 颜色分类

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

代码实现（C++/Java）

class Solution {
public:
    void sortColors(vector<int>& nums) {
        int cnt0=0,cnt1=0,cnt2=0;
        for(int i=0;i<nums.size();i++){
            if(nums[i]==0) cnt0++;
            else if(nums[i]==1) cnt1++;
            else cnt2++;
        }
        int idx=0;
        for(int i=1;i<=cnt0;i++) nums[idx++]=0;
        for(int i=1;i<=cnt1;i++) nums[idx++]=1;
        for(int i=1;i<=cnt2;i++) nums[idx++]=2;
        
    }
};

class Solution {
    public void sortColors(int[] nums) {
        int cnt0=0,cnt1=0,cnt2=0;
        for(int i=0;i<nums.length;i++){
            if(nums[i]==0) cnt0++;
            else if(nums[i]==1) cnt1++;
            else cnt2++;
        }
        int idx=0;
        for(int i=1;i<=cnt0;i++) nums[idx++]=0;
        for(int i=1;i<=cnt1;i++) nums[idx++]=1;
        for(int i=1;i<=cnt2;i++) nums[idx++]=2;
    }
}

9.4 下一个排列

31. 下一个排列 - 力扣（LeetCode）

代码实现（C++/Java）

9.5 寻找重复数

287. 寻找重复数 - 力扣（LeetCode）

代码实现（C++/Java）

class Solution {
public:
    int findDuplicate(vector<int>& nums) {
        int slow=0,fast=0;
        while(true){
            slow=nums[slow];
            fast=nums[nums[fast]];
            if(fast==slow) break;
        }
        slow=0;
        while(fast!=slow){
            slow=nums[slow];
            fast=nums[fast];
        }
        return slow;
    
    }
};

class Solution {
    public int findDuplicate(int[] nums) {
        int slow=0,fast=0;
        while(true){
            slow=nums[slow];
            fast=nums[nums[fast]];
            if(fast==slow) break;
        }
        slow=0;
        while(fast!=slow){
            slow=nums[slow];
            fast=nums[fast];
        }
        return slow;
    }
}

探索云世界

热门

云计算

大数据

云原生

人工智能

数据库

开发与运维

活动广场

任务中心

训练营

直播

乘风者计划

下载

镜像站

技术资料

程序员算法圣经-LeetCode Hot100下

1.图论

1.1 岛屿数量

1.2 腐烂的橘子

1.3 课程表

1.4 实现Tire树

2.回溯

2.1 全排列

2.2 子集

2.3 电话号码的字母组合

2.4 组合总和

2.5 括号生成

2.6 单词搜索

2.7 分割回文子串

2.8 N皇后

3.二分

3.1 搜索插入位置

3.2 搜索二维矩阵

3.3 在排序数组中查找元素的第一个和最后一个位置

3.4 搜索旋转排序数组

3.5 寻找旋转排序数组中的最小值

3.5 寻找两个正序数组的中位数

4.栈

4.1 有效的括号

4.2 最小栈

4.6 最长有效括号

5.堆

5.1 数组中的第K个最大元素

5.2 前K个高频元素

5.3 数据流的中位数

6.贪心算法

6.1 买卖股票的最佳时机

6.2 跳跃游戏

6.3 跳跃游戏2

6.4 划分字母区间

7. 动态规划

7.1 爬楼梯

7.2 杨辉三角

7.3 打家劫舍

7.4 完全平方数

7.5 零钱兑换

7.6 单词拆分

7.7 最长递增子序列

7.8 乘积最大子数组

7.9 分割等和子集

8.多维动态规划

8.1 不同路径

8.2 最小路径和

8.3 最长回文子串

8.4 最长公共子序列

8.5 编辑距离

9.技巧

9.1 只出现一次的数字

9.2 多数元素

9.3 颜色分类

9.4 下一个排列

9.5 寻找重复数

热门文章

最新文章

相关电子书