leetcode刷题笔记_loliiiiipop99视频

1. 算法

1.1 动态规划

1.1.1 简单题目

53.最大子序和

给定一个整数数组 nums ，找到一个具有最大和的连续子数组（子数组最少包含一个元素），返回其最大和。

• 方法一

class Solution {
    public int maxSubArray(int[] nums) {
        /*
            思路：
                1.确定dp数组下标及其含义
                    dp[i]表示第i个数结尾的连续子数组的最大和
                    int[] dp = new int[nums.length];
                2.确定递推公式
                    可知dp[i]与dp[i-1]有关，
                    如果dp[i-1]<=0，则dp[i]=nums[i]
                    如果dp[i-1]>0,则dp[i]=dp[i-1]+nums[i],所以
                    dp[i] = Math.max(dp[i-1]+nums[i],nums[i]);
                3.dp数组初始化
                    由于dp[i]表示第i个数结尾的连续子数组的最大和，则dp[0]=nums[0];
                4.确定遍历顺序
                    由于dp[i]是由dp[i-1]递推出来的，可知遍历顺序由前向后
                5.最终结果
                    可知dp数组中存储的最大值就是最终结果。
         */
         int[] dp = new int[nums.length];
         dp[0] = nums[0];
         int max = dp[0];
         for(int i=1;i<nums.length;++i){
             dp[i] = Math.max(dp[i-1]+nums[i],nums[i]);
             max = Math.max(max,dp[i]);
         }
         return max;

    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30

• 方法二

class Solution {
    public int maxSubArray(int[] nums) {
        /*
            思路：
                1.确定dp数组下标及其含义
                    dp[i]表示第i个数结尾的连续子数组的最大和
                    int[] dp = new int[nums.length];
                2.确定递推公式
                    可知dp[i]与dp[i-1]有关，
                    如果dp[i-1]<=0，则dp[i]=nums[i]
                    如果dp[i-1]>0,则dp[i]=dp[i-1]+nums[i],所以
                    dp[i] = Math.max(dp[i-1]+nums[i],nums[i]);
                3.dp数组初始化
                    由于dp[i]表示第i个数结尾的连续子数组的最大和，则dp[0]=nums[0];
                4.确定遍历顺序
                    由于dp[i]是由dp[i-1]递推出来的，可知遍历顺序由前向后
                5.最终结果
                    可知dp数组中存储的最大值就是最终结果。

                优化：
                    由以上思路和代码可知，dp[i]只dp[i-1]有关，因此我们可以用一个常量pre来进行维护，
                    这样就节约了空间
                
         */
         int max = nums[0];
         int pre = max;
         for(int i=1;i<nums.length;++i){
             pre = Math.max(pre+nums[i],nums[i]);
             max = Math.max(max,pre);
         }
         return max;

    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34

70.爬楼梯

假设你正在爬楼梯。需要 n 阶你才能到达楼顶。
每次你可以爬 1 或 2 个台阶。你有多少种不同的方法可以爬到楼顶呢？
注意：给定 n 是一个正整数。

• 方法一：递归(超出时间限制)

/*
	递归重要是分析出递归的核心，不要沉迷于递归的过程
	分析：
	用f(i)表示 表示当 n=i 时，共有多少种走法
	n=1   ->走一步									->f(1) = 1
	n=2   -> （1）一步一步走（2）直接走两步	 			->f(2) = 2 
	n=3   -> （1）先到达f(1),然后从f(1)直接走两步
		  -> （2）先到达f(2),然后从f(2)走一步          ->f(3) = f(1) + f(2)
	n=4	  -> （1）先到达f(2),然后从f(2)直接走两步
		  -> （2）先到达f(3),然后从f(3)走一步          ->f(4) = f(2) + f(3)
	..........
	n=i   -> （1）先到达f(i-2),然后从f(i-2)直接走两步
		  -> （2）先到达f(i-1),然后从f(i-1)走一步          ->f(i) = f(i-2) + f(i-1) 
*/
class Solution{
	public int f(int n){
		//递归的终止条件
		if(n == 1 || n== 2){
			return n;
		}
		return f(n-2) + f(n-1);
	}
}

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24

• 方法2：迭代

/*
	分析：
	用f(i)表示 表示当 n=i 时，共有多少种走法
	用one保存最后走一步，two保存最后走两步
	n=1   ->走一步									->f(1) = 1
	n=2   -> （1）一步一步走（2）直接走两步	 			->f(2) = 2 
	n=3   -> （1）先到达f(1),然后从f(1)直接走两步		
		  -> （2）先到达f(2),然后从f(2)走一步          
		  											->f(3) = two + one
		  											->f(3) = f(1) + f(2)
		  											->two = f(1);one =  f(2)
	n=4	  -> （1）先到达f(2),然后从f(2)直接走两步
		  -> （2）先到达f(3),然后从f(3)走一步          
		  											->f(4) = two + one
		  											->f(4) = f(2) + f(3)
		  											->two = f(2);one =  f(3)
	..........
	n=i   -> （1）先到达f(i-2),然后从f(i-2)直接走两步
		  -> （2）先到达f(i-1),然后从f(i-1)走一步          
		  											->f(i) = two + one
		  											->f(i) = f(i-2) + f(i-1) 
		  											->two = f(i-2);one =  f(i-1)
*/
class Solution{
	public int loop(int n){
		if(n == 1 || n== 2){
			return n;
		}
		int two = 1;//初始化为走到第一节台阶的走法 
		int one = 2;//初始化为走到第二节台阶的走法
		int sum = 0;//保存总的走法
		for(int i=3;i<=n;++i){
			//最后跨两步 + 最后跨一步的走法
			sum = two + one;
			two = one;
			one = sum;
		}
		return sum;
	}
}

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41

• 方法三：动态规划

/*
	用f(i)表示爬到第i级台阶的方案数
	动态规划转移方程：f(i) = f(i-1) + f(i-2) 
	f(i) 只和f(i-1)与f(i-2)有关，所以我们可以用「滚动数组思想」把空间复杂度优化
*/
class Solution {
    public int dp(int n) {
        int p = 0, q = 0, r = 1;
        for (int i = 1; i <= n; ++i) {
            p = q; 
            q = r; 
            r = p + q;
        }
        return r;
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16

118.杨辉三角

给定一个非负整数 numRows，生成「杨辉三角」的前 numRows 行。
在「杨辉三角」中，每个数是它左上方和右上方的数的和。
1 <= numRows <= 30

/*
	分析可知：
		第一列的值都为1
		行号和列号相等时的值为1
		否者arr[i][j] = arr[i-1][j-1] + arr[i-1][j];
*/
class Solution {
    public List<List<Integer>> generate(int numRows) {
        int[][] arr = new int[numRows][numRows];
        List<List<Integer>> res = new ArrayList<List<Integer>>();
        for (int i = 0; i < arr.length; i++) {
            List<Integer> list = new ArrayList<Integer>();
            for (int j = 0; j <= i; j++) {
                if (j == 0){
                    arr[i][j] = 1;
                }else if (i == j){
                    arr[i][j] = 1;
                }else{
                    arr[i][j] = arr[i-1][j-1] + arr[i-1][j];
                }
                list.add(arr[i][j]);
            }
            res.add(list);

        }
        return res;
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28

121.买股票的最佳时机

给定一个数组 prices ，它的第 i 个元素 prices[i] 表示一支给定股票第 i 天的价格。
你只能选择 某一天 买入这只股票，并选择在 未来的某一个不同的日子 卖出该股票。设计一个算法来计算你所能获取的最大利润。
返回你可以从这笔交易中获取的最大利润。如果你不能获取任何利润，返回 0 。
1 <= prices.length <= 105
0 <= prices[i] <= 104

• 方法一

class Solution {
    public int maxProfit(int[] prices) {
        /*
            思路：
                1.确定dp数组及其下标含义
                    dp[i][0]表示第i天不持有股票，所获得最大利润
                    dp[i][1]表示第i天持有股票，所获得最大利润
                    int[][] dp = new int[prices.length][2];
                2.确定递推数组
                    （1）如果第i天不持有股票即dp[i][0],那么可以由两个状态推出来：
                        ①第i-1天就不持有股票，就保持现状，则利润为dp[i-1][0];
                        ②第i-1天持有股票，所得利润就是今天卖出后所得的利润即:
                        dp[i-1][1]+prices[i];
                        则最大利润dp[i][0] = Math.max(dp[i-1][0],dp[i-1][1]+prices[i]);
                    （3）如果第i天持有股票即dp[i][1],那么可以由两个状态推出来：
                        ①第i-1天就持有股票，则保持现状，则利润为dp[i-1][1];
                        ②第i-1天不持有股票，则今天买入，所获得利润为-prices[i];
                        则最大利润dp[i][1] = Math.max(dp[i-1][1],-prices[i]);
                3.dp数组初始化
                    由递推公式 dp[i][0] =Math.max(dp[i-1][0], prices[i] + dp[i-1][1]);
                    和 dp[i][1] = Math.max(dp[i-1][1], -prices[i]);可以看出
                    其基础都是要从dp[0][0]和dp[0][1]推导出来。
                        dp[0][0]表示第0天不持有股票，不持有股票那么现金就是0，所以dp[0][0] = 0;
                        dp[0][1]表示第0天持有股票，此时的持有股票就一定是买入股票了，因为不可能由前
                        一天推出来，所以dp[0][1] = -prices[0];
                4.确定遍历顺序
                    从递推公式可以看出dp[i]都是有dp[i-1]推导出来的，那么一定是从前向后遍历。
                5.最终结果
                    最后要获得最大收益，最后的状态一定是不持有股票，所以最终的结果为
                    dp[prices.length-1][0]
                
         */
         int[][] dp = new int[prices.length][2];
         dp[0][0] = 0;
         dp[0][1] = -prices[0];
         for(int i=1;i<prices.length;++i){
             dp[i][0] = Math.max(dp[i-1][0],dp[i-1][1]+prices[i]);
             dp[i][1] = Math.max(dp[i-1][1],-prices[i]);
         }
         return dp[prices.length-1][0];
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42

• 方法二

/*
	对方法一进行优化
	从递推公式可以看出，dp[i]只是依赖于dp[i - 1]的状态。
		dp[i][0] = Math.max(dp[i-1][0],dp[i-1][1]+prices[i]);
		dp[i][1] = Math.max(dp[i-1][1],-prices[i]);
	那么我们只需要记录 当前天的dp状态和前一天的dp状态就可以了，可以使用滚动数组来节省空间
*/
class Solution {
    public int maxProfit(int[] prices) {
		 int no = 0;
         int yes = -prices[0];
         for(int i=1;i<prices.length;++i){
             no = Math.max(no,yes+prices[i]);
             yes = Math.max(yes,-prices[i]); 
         }
         return no;
    } 
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18

122.买卖股票的最佳时机II

给定一个数组 prices ，其中 prices[i] 是一支给定股票第 i 天的价格。
设计一个算法来计算你所能获取的最大利润。你可以尽可能地完成更多的交易（多次买卖一支股票）。
注意：你不能同时参与多笔交易（你必须在再次购买前出售掉之前的股票）。
1 <= prices.length <= 3 * 104
0 <= prices[i] <= 104

• 方法一

/*
	1.确定dp数组以及下标的含义
		dp[i][0] 表示第i天不持有股票所得最多现金
		dp[i][1] 表示第i天持有股票所得最多现金
		int[][] dp = new int[price.length][2]; 
	2.确定递推公式
		如果第i天不持有股票即dp[i][0]， 也可以由两个状态推出来
			第i-1天就不持有股票，那么就保持现状，所得现金就是昨天不持有股票的所得现金 即：dp[i - 1][0]
			第i天卖出股票，所得现金就是按照今天股票佳价格卖出后所得现金即：prices[i] + dp[i - 1][1]
			dp[i][0]取最大的，dp[i][0] = max(dp[i - 1][0], prices[i] + dp[i - 1][1]);
		如果第i天持有股票即dp[i][1]， 那么可以由两个状态推出来
			第i-1天就持有股票，那么就保持现状，所得现金就是昨天持有股票的所得现金 即：dp[i - 1][1]
			第i天买入股票（说明第i-1天是不持有股票的），所得现金就是买入今天的股票后所得现金与i-1天不持有股票所得现金之和即：dp[i-1][0]-prices[i]
			那么dp[i][0]应该选所得现金最大的，所以dp[i][1] = max(dp[i - 1][0], dp[i-1][0]-prices[i]);
	3.dp数组如何初始化
		由递推公式 dp[i][0] = max(dp[i - 1][0], prices[i] + dp[i - 1][1]);和 dp[i][1] = max(dp[i - 1][0], dp[i-1][0]-prices[i]);可以看出
		其基础都是要从dp[0][0]和dp[0][1]推导出来。
		dp[0][0]表示第0天不持有股票，不持有股票那么现金就是0，所以dp[0][0] = 0;
		dp[0][1]表示第0天持有股票，此时的持有股票就一定是买入股票了，因为不可能有前一天推出来，所以dp[0][1] = -prices[0];
	4.确定遍历顺序
		从递推公式可以看出dp[i]都是有dp[i - 1]推导出来的，那么一定是从前向后遍历。
	5.最终结果
		最后要获得最大收益，最后的状态一定是不持有股票，所以最终的结果为dp[prices.length-1][0]
*/
class Solution {
    public int maxProfit(int[] prices) {
   		int[][] dp = new int[prices.length][2];
   		dp[0][0] = 0;
   		dp[0][1] = -prices[0];
   		for(int i=1;i<prices.length;++i){
			dp[i][0] = Math.max(dp[i-1][0],dp[i-1][1]+prices[i]);
			dp[i][1] = Math.max(dp[i-1][1],dp[i-1][0]-prices[i]);
		}
		return dp[prices.length-1][0];
    } 
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36

• 方法二

/*
	对方法一进行优化
	从递推公式可以看出，dp[i]只是依赖于dp[i - 1]的状态。
		dp[i][0] = Math.max(dp[i-1][0],dp[i-1][1]+prices[i]);
		dp[i][1] = Math.max(dp[i-1][1],dp[i-1][0]-prices[i]);
	那么我们只需要记录 当前天的dp状态和前一天的dp状态就可以了，可以使用滚动数组来节省空间
*/
class Solution {
    public int maxProfit(int[] prices) {
		int notHold = 0;
		int hold = -prices[0];
		for(int i=1;i<prices.length;++i){
			notHold = Math.max(notHold,hold+prices[i]);
			hold = Math.max(hold,notHold-prices[i]);
		} 
		return notHold;
    } 
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18

338.比特位记数

给定一个非负整数 num。对于 0 ≤ i ≤ num 范围中的每个数字 i ，计算其二进制数中的 1 的数目并将它们作为数组返回。

• 方法一：最高有效位

/*
	1.确定dp数组及其下标的含义
		dp[i]表示i的比特数
		int[] dp = new int[num+1];
	2.确定递推公式
		用highBit表示最高有效位
		如果i是2的整数次幂：
			可知i&(i-1)=0,则另highBit=i，更新当前最高效位;
		dp[i] = dp[i-highBit] + 1;
		例如：
			当i=9时
			8 = 2*2*2 = 1000（二进制） ——>最高有效位highBit = 8
			1 = 0001  ——>dp[1] = 1
			9 = 1001  ——>dp[9] = 2
			由上可知 dp[9] = dp[9-8] + 1 = dp[1] + 1
			
	3.初始化
		由递推公式可知，其基础都是有highBit推导出来
		可知0的比特数为0;
		则int highBit=0; 
	4.确定遍历顺序
		从递推公式可以看出dp[i]都是有dp[i - highBit]推导出来的，那么一定是从前向后遍历。
	5.最终的到的数组就是答案
*/
class Solution {
    public int[] countBits(int n) {
    	int[] dp = new int[n+1];
    	int highBit = 0;
    	for(int i=1;i<=n;++i){
			if((i&(i-1)) == 0){
				highBit= i;
			}
			dp[i] = dp[i-highBit] + 1;
		}
		return dp;
    }
}						
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37

• 方法二：最低有效位

/*
	类比方法一：
	递推公式：dp[i] = dp[i/2] + (i%2)  或则 dp[i] = dp[i>>1] + (i&1)
*/
class Solution {
    public int[] countBits(int n) {
    	int[] dp = new int[n+1];
    	for(int i=1;i<=n;++i){
			dp[i] = dp[i>>1] + (i&1);
		}
		return dp;
    }
}	
1
2
3
4
5
6
7
8
9
10
11
12
13

1.1.2 中等题目

62.不同路径

一个机器人位于一个 m x n 网格的左上角 （起始点在下图中标记为 “Start” ）。
机器人每次只能向下或者向右移动一步。机器人试图达到网格的右下角（在下图中标记为 “Finish” ）。
问总共有多少条不同的路径？

• 方法一

/*
	1.确定dp数组的下标及其含义
		dp[i][j]表示从左上角到达(i,j)位置的路径数
		int[][] dp = new int[m][n];
	2.确定递推公式
		由于机器人只能向下或则向右移动，因此要想到达(i,j)的位置，则一定是从(i-1,j)或则(i,j-1)走过来的
		因此 dp[i][j] = dp[i-1][j] + dp[i][j-1];
	3.初始化
		需要注意的是当i=0或j=0时，他们的路径数都是1。
		也就是说dp[i][0] = 1,dp[0][j] = 1;
		很明显dp[0][0] = 1
	4.确定遍历顺序
		由递推公式可以看到dp[i][j]是由dp[i-1][j]和dp[i][j-1]推导出来的，因此是顺序遍历
	5.最终结果
		可知到达最后位置就是数组的最后一个值即dp[m-1][n-1];
		
*/
class Solution {
    public int uniquePaths(int m, int n) {
    	int[][] dp = new int[m][n]; 
    	for(int i=0;i<m;++i){
			dp[i][0] = 1;
		}
		for(int i=1;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];
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34

• 方法二

/*
	对方法一进行优化：
		由于这里dp[i][j]只和dp[i-1][j]与dp[i][j-1]有关，我们可以运用「滚动数组思想」把空间复杂度优化
	1.确定dp数组的下标及其含义
		dp[j]用来缓存当前行
		int[] dp = new int[n];
	2.确定递推公式
		由于机器人只能向下或则向右移动，因此要想到达第i行，则一定是从上一行(j-1)或则当前行(j)走过来的
			则 dp[j] = dp[j-1]+dp[j]
	3.初始化
		由递推公式可知，其基础都是由dp[0]推导来的
		因此dp[0] = 1
	4.确定遍历顺序
		由递推公式可以看到dp[j]是由dp[j-1]和dp[j]推导出来的，因此是顺序遍历
	5.最终结果
		可知到达最后位置就是数组的最后一个值即dp[n-1];
*/
class Solution {
    public int uniquePaths(int m, int n) {
		int[] dp = new int[n];
		dp[0] = 1;
		for(int i=0;i<m;++i){
			for(int j=1;j<n;++j){
				dp[j] = dp[j-1] + dp[j];
			}
		}
		return dp[n-1];
	}
}

/*
	同理
		dp[j]用来缓存当前列
		int[] dp = new int[m];	
		
*/
class Solution {
    public int uniquePaths(int m, int n) {
		int[] dp = new int[m];
		dp[0] = 1;
		for(int i=0;i<n;++i){
			for(int j=1;j<m;++j){
				dp[j] = dp[j-1] + dp[j];
			}
		}
		return dp[m-1];
	}
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48

63.不同路径II

一个机器人位于一个 m x n 网格的左上角 （起始点在下图中标记为“Start” ）。
机器人每次只能向下或者向右移动一步。机器人试图达到网格的右下角（在下图中标记为“Finish”）。
现在考虑网格中有障碍物。那么从左上角到右下角将会有多少条不同的路径？
m = obstacleGrid.length
n = obstacleGrid[i].length
1 <= m, n <= 100
obstacleGrid[i][j] 为 0 或 1

• 动态规划的题目分为两大类，一种是求最优解类，典型问题是背包问题，另一种就是计数类，比如这里的统计方案数的问题，它们都存在一定的递推性质。前者的递推性质还有一个名字，叫做 「最优子结构」 ——即当前问题的最优解取决于子问题的最优解，后者类似，当前问题的方案数取决于子问题的方案数。所以在遇到求方案数的问题时，我们可以往动态规划的方向考虑。
• 方法一

/*
	1.确定dp数组的下标及其含义
		dp[i][j]表示从左上角到达(i,j)位置的路径数
		int[][] dp = new int[m][n];
	2.确定递推公式
		由于机器人只能向下或则向右移动，因此要想到达(i,j)的位置，则一定是从(i-1,j)或则(i,j-1)走过来的
		如果obstacleGrid[i][j] = 1时，即本身有障碍，则dp[i][j] = 0;
		如果obstacleGrid[i][j] = 0时，即本身没有障碍，则 dp[i][j] = dp[i-1][j] + dp[i][j-1];
	3.初始化
		当i=0是，如果这一行有障碍，则障碍之前的路径数都为1，从障碍开始之后的路径数都为0
		同理当j=0时，如果这一列有障碍，则障碍之前的路径数都为1，从障碍开始之后的路径数都为0
	4.确定遍历顺序
		由递推公式可以看到dp[i][j]是由dp[i-1][j]和dp[i][j-1]推导出来的，因此是顺序遍历
	5.最终结果
		可知到达最后位置就是数组的最后一个值即dp[m-1][n-1];
		
*/
class Solution {
    public int uniquePathsWithObstacles(int[][] obstacleGrid) {
        int m = obstacleGrid.length;
        int n = obstacleGrid[0].length;
        int[][] dp = new int[m][n];
        for(int i=0;i<m;++i){
            if(obstacleGrid[i][0] == 0){
                dp[i][0] = 1;
            }else{
                break;
            }
        }
        for(int i=0;i<n;++i){
            if(obstacleGrid[0][i] == 0){
                dp[0][i] = 1;
            }else{
                break;
            }
        }
        for(int i=1;i<m;++i){
            for(int j=1;j<n;++j){
                if(obstacleGrid[i][j] == 1){
                    continue;
                }
                dp[i][j] = dp[i-1][j] + dp[i][j-1];
            }
        }
        return dp[m-1][n-1];
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47

• 方法二

/*
	对方法一进行优化：
		由于这里dp[i][j]只和dp[i-1][j]与dp[i][j-1]有关，我们可以运用「滚动数组思想」把空间复杂度优化
	1.确定dp数组的下标及其含义
		dp[j]用来缓存当前行
		int[] dp = new int[n];
	2.确定递推公式
		由于机器人只能向下或则向右移动，因此要想到达第i行，则一定是从上一行(j-1)或则当前行(j)走过来的
		如果obstacleGrid[i][j] = 1时，即本身有障碍，则dp[j] = 0;
		如果obstacleGrid[i][j] = 0时，即本身没有障碍，
			此时还要考虑j-1>=0,并且obstacleGrid[i][j-1] = 0
			则 dp[j] = dp[j-1]+dp[j]
	3.初始化
		由递推公式可知，其基础都是由dp[0]推导来的
		因此dp[0] = obstacleGrid[0][0] == 0 ? 1 : 0;
	4.确定遍历顺序
		由递推公式可以看到dp[j]是由dp[j-1]和dp[j]推导出来的，因此是顺序遍历
	5.最终结果
		可知到达最后位置就是数组的最后一个值即dp[n-1];
*/
class Solution {
    public int uniquePathsWithObstacles(int[][] obstacleGrid) {
    	int m = obstacleGrid.length;
        int n = obstacleGrid[0].length;
        int[] dp = new int[n];
        dp[0] = obstacleGrid[0][0] == 0 ? 1 : 0;
        for(int i=0;i<m;++i){
			for(int j=0;j<n;++j){
				if(obstacleGrid[i][j] == 1){
					dp[j] = 0;
					continue;
				}
				if(j-1>=0 && obstacleGrid[i][j-1] == 0){
					dp[j] = dp[j-1]+dp[j];
				}
			}
		}
		return dp[n-1];
    }
}

/*
	同理
		dp[j]用来缓存当前列
		int[] dp = new int[m];	
*/
class Solution {
    public int uniquePathsWithObstacles(int[][] obstacleGrid) {
    	int m = obstacleGrid.length;
        int n = obstacleGrid[0].length;
        int[] dp = new int[m];
        dp[0] = obstacleGrid[0][0] == 0 ? 1 : 0;
        for(int i=0;i<n;++i){
			for(int j=0;j<m;++j){
				if(obstacleGrid[j][i] == 1){
					dp[j] = 0;
					continue;
				}
				if(j-1>=0 && obstacleGrid[j-1][i] == 0){
					dp[j] = dp[j-1]+dp[j];
				}
			}
		}
		return dp[m-1];
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66

64.最小路径和

给定一个包含非负整数的 m x n 网格 grid ，请找出一条从左上角到右下角的路径，使得路径上的数字总和为最小。
说明：每次只能向下或者向右移动一步。
m = grid.length
n = grid[i].length
1 <= m, n <= 200
0 <= grid[i][j] <= 100

• 方法一

/*
	1.确定dp数组的下标及其含义
		dp[i][j]表示从左上角到达(i,j)位置的最小路径和
		int[][] dp = new int[m][n];
	2.确定递推公式
		由于只能向下或则向右移动，因此要想到达(i,j)的位置，则一定是从(i-1,j)或则(i,j-1)走过来
		则当i>0,j>0时，dp[i][j] = min(dp[i-1][j],dp[i][j-1]) + grid[i][j];
		当i>0,j=0时，dp[i][0] = dp[i-1][0] + grid[i][0]
		当i=0,j>0时，dp[0][j] = dp[0][j-1] + grid[0][j]
	3.初始化
		由递推公式可知其基础是有dp[0][0]推导而来，因此dp[0][0] = grid[0][0];
	4.确定遍历顺序
		由递推公式可以看到dp[i][j]是由dp[i-1][j]和dp[i][j-1]推导出来的，因此是顺序遍历
	5.最终结果
		可知到达最后位置就是数组的最后一个值即dp[m-1][n-1];
*/
class Solution {
    public int minPathSum(int[][] grid) {
        int[][] dp = new int[grid.length][grid[0].length];
        dp[0][0] = grid[0][0];
        for(int i=1;i<grid.length;++i){
            dp[i][0] = dp[i-1][0] + grid[i][0];
        }
        for(int i=1;i<grid[0].length;++i){
            dp[0][i] = dp[0][i-1] + grid[0][i];
        }
        for(int i = 1;i<grid.length;++i){
            for(int j=1;j<grid[0].length;++j){
                dp[i][j] = Math.min(dp[i-1][j],dp[i][j-1])+grid[i][j];
            }
        }
        return dp[grid.length-1][grid[0].length-1];
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34

• 方法二

/*
	对方法一进行优化：
		由于这里dp[i][j]只和dp[i-1][j]与dp[i][j-1]有关，我们可以运用「滚动数组思想」把空间复杂度优化
	1.确定dp数组的下标及其含义
		dp[j]用来缓存当前行
		int[] dp = new int[n];
	2.确定递推公式
		由于只能向下或则向右移动，因此要想到达第i行，则一定是从上一行(j-1)或则当前行(j)走过来的
			则 dp[j] = Math.min(dp[j],dp[j-1])+grid[i][j]
	3.初始化
		由递推公式可知，其基础都是由dp[0]推导来的
		因此dp[0] = grid[0][0];
		缓存第一行
		dp[i] = dp[i-1] + grid[0][i];
	4.确定遍历顺序
		由递推公式可以看到dp[j]是由dp[j-1]和dp[j]推导出来的，因此是顺序遍历
	5.最终结果
		可知到达最后位置就是数组的最后一个值即dp[n-1];
*/
class Solution {
    public int minPathSum(int[][] grid) {
        int[] dp = new int[grid[0].length];
        dp[0] = grid[0][0];
        for(int i=1;i<grid[0].length;++i){
            dp[i] = dp[i-1] + grid[0][i];
        }
        for(int i = 1;i<grid.length;++i){
            dp[0] = dp[0] + grid[i][0];//对当前行的首位置值进行存储
            for(int j=1;j<grid[0].length;++j){
                dp[j] = Math.min(dp[j],dp[j-1])+grid[i][j];
            }
        }
        return dp[grid[0].length-1];
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35

91.解码方法

一条包含字母 A-Z 的消息通过以下映射进行了 编码 ：

‘A’ -> 1
‘B’ -> 2
…
‘Z’ -> 26

要 解码 已编码的消息，所有数字必须基于上述映射的方法，反向映射回字母（可能有多种方法）。例如，“11106” 可以映射为：
“AAJF” ，将消息分组为 (1 1 10 6)
“KJF” ，将消息分组为 (11 10 6)
注意，消息不能分组为 (1 11 06) ，因为 “06” 不能映射为 “F” ，这是由于 “6” 和 “06” 在映射中并不等价。
给你一个只含数字的 非空 字符串 s ，请计算并返回 解码 方法的 总数 。
题目数据保证答案肯定是一个 32 位 的整数。

1 <= s.length <= 100
s 只包含数字，并且可能包含前导零。

• 方法一

/*
	1.确定dp数组及其下标的含义
		dp[i]表示字符串s的前i个字符解码方法总数
		int[] dp = new int[s.length()+1];
	2.确定递推公式
		由于字母对应的数字为1位数字或则2位数字
			则使用一个字符时候：dp[i] = dp[i-1](当然此时字符串的第i个字符不能为'0')
			使用两个字符时：dp[i] = dp[i-2](因为不能出现0x,所以此时字符串的第i-1个字符不能为'0',并且两个字符拼接成的数字不能大于26，并且i要大于1)
			将上面的两种递推转移方程在对应的条件满足时进行累加
	3.初始化
		有递推公式可以的出其基础都是由dp[0]推出的
			因此 dp[0] = 1;即空字符串可以有1种解码方法，解码出一个空字符串。
	4.确定遍历顺序
		由递推公式可以看出是顺序遍历
	5.最终结果
		dp[s.length()];
*/
class Solution {
    public int numDecodings(String s) {
		int[] dp = new int[s.length()+1];
		dp[0] = 1;
		for(int i=1;i<=s.length();++i){
			if(s.charAt(i-1)!= '0'){
				dp[i] += dp[i-1];
			}
			if(i>1 && s.charAt(i-2) != '0' && ((s.charAt(i-2)-'0')*10 + (s.charAt(i-1)-'0') <= 26)){
				dp[i] += dp[i-2];
			}
		}
		return dp[s.length()];
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32

• 方法二

/*
	对方法一进行优化
	因为dp[i]只和dp[i-1]和dp[i-2]有关，因此可以用三个变量进行状态转移进行空间优化
	用num0,num1,num2分别对应dp[i]、dp[i-1]、dp[i-2]
*/
class Solution {
    public int numDecodings(String s) {
		int num0;
		int num1 = 1;
		int num2 = 0;
		
		for(int i=1;i<=s.length();++i){
			num0 = 0;
			if(s.charAt(i-1)!= '0'){
				num0 += num1;
			}
			if(i>1 && s.charAt(i-2) != '0' && ((s.charAt(i-2)-'0')*10 + (s.charAt(i-1)-'0') <= 26)){
				num0 += num2;
			}
			num2 = num1;
			num1 = num0;
		}
		return num0;
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25

120.三角形最小路径和

给定一个三角形 triangle ，找出自顶向下的最小路径和。
每一步只能移动到下一行中相邻的结点上。相邻的结点 在这里指的是 下标 与 上一层结点下标 相同或者等于 上一层结点下标 + 1 的两个结点。也就是说，如果正位于当前行的下标 i ，那么下一步可以移动到下一行的下标 i 或 i + 1 。
1 <= triangle.length <= 200
triangle[0].length = 1
triangle[i].length = triangle[i - 1].length + 1
-104 <= triangle[i][j] <= 104

• 方法一

/*
	1.确定递推数组及其下标的含义
		dp[i][j]表示从顶点走到（i,j）位置的最小路径和
		int[][] dp = new int[n][n];
	2.确定递推公式
		由于每一步只能移动到下一行「相邻的节点」上，因此要想走到位置(i,j)，上一步就只能在位置(i−1,j−1)或者位置(i−1,j)。			 
		我们在这两个位置中选择一个路径和较小的来进行转移，状态转移方程为
		dp[i][j] = min(dp[i-1][j-1], dp[i-1][j]) + t[i][j]
		t[i][j]表示三角形中（i,j）位置的值
		还要考虑边界情况
		左边边界 dp[i][0] = dp[i-1][0] + t[i][0]
		右边边界 dp[i][i] = dp[i−1][i−1] + t[i][i]

	3.初始化
		dp[0][0] = t[0][0];
	4.遍历顺序
		由递推公式可以看出是顺序遍历
	5.最终结果
		即为 dp[n-1][0]到dp[n-1][n-1]中的最小值，其中n是三角形的行数
		
*/
class Solution {
    public int minimumTotal(List<List<Integer>> triangle) {
        int n=triangle.size();
        int[][] dp = new int[n][n];
        dp[0][0] = triangle.get(0).get(0);
        for(int i=1;i<n;++i){
            dp[i][0] = dp[i-1][0] + triangle.get(i).get(0);
            for(int j=1;j<i;++j){
                dp[i][j] = Math.min(dp[i-1][j-1], dp[i-1][j]) + triangle.get(i).get(j);
            }
            dp[i][i] = dp[i-1][i-1] + triangle.get(i).get(i);
        } 
        int ans = dp[n-1][0];
        for(int i=1;i<n;++i){
            ans = Math.min(ans,dp[n-1][i]);
        } 
        return ans;
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40

• 方法二

/*
	对方法一进行空间优化
	由递推公式可知dp[i][..]只和dp[i-1][..]有关
	因此我们可以只存储i-1的状态和i的状态
	int[][] dp = new int[2][n];
*/
class Solution {
    public int minimumTotal(List<List<Integer>> triangle) {
        int n=triangle.size();
        int[][] dp = new int[2][n];
        dp[0][0] = triangle.get(0).get(0);
        for(int i=1;i<n;++i){
        	int cur = i%2;
        	int pre = 1-cur; 
            dp[cur][0] = dp[pre][0] + triangle.get(i).get(0);
            for(int j=1;j<i;++j){
                dp[cur][j] = Math.min(dp[pre][j-1], dp[pre][j]) + triangle.get(i).get(j);
            }
            dp[cur][i] = dp[pre][i-1] + triangle.get(i).get(i);
        } 
        int ans = dp[(n - 1) % 2][0];
        for(int i=1;i<n;++i){
            ans = Math.min(ans,dp[(n - 1) % 2][i]);
        } 
        return ans;
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27

-方法三

/*

	继续优化
	只记录上一层的状态 ，从后往前更改值
	int[] dp = new int[n]; 缓存当前行
*/
class Solution {
    public int minimumTotal(List<List<Integer>> triangle) {
        int n=triangle.size();
        int[] dp = new int[n];
        dp[0] = triangle.get(0).get(0);
        for(int i=1;i<n;++i){
        	//j=i时只能从左上来
            dp[i] = dp[i-1] + triangle.get(i).get(i);
            for(int j=i-1;j>0;--j){
            	//本行元素来自上左上和顶上最小值
                dp[j] = Math.min(dp[j-1], dp[j]) + triangle.get(i).get(j);
            }
            //本行第一个元素只能从上一行的第一个元素来
            dp[0] = dp[0] + triangle.get(i).get(0);
        } 
        int ans = dp[0];
        for(int i=1;i<n;++i){
            ans = Math.min(ans,dp[i]);
        } 
        return ans;
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28

139.代词拆分

给定一个非空字符串 s 和一个包含非空单词的列表 wordDict，判定 s 是否可以被空格拆分为一个或多个在字典中出现的单词。
说明：
拆分时可以重复使用字典中的单词。
你可以假设字典中没有重复的单词。

/*
	1.确定dp数组及其下标含义
		dp[i]表示表示字符串s前i个字符组成的字符串是否能被空格拆分成若干个字典中出现的单词
		int[] dp = new int[s.length()+1];
	2.确定递推公式
		dp[i] = dp[j] && （(j,i)组成的单词是否在列表中）
	3.初始化
		可以用hashset集合取出列表中的重复元素
		dp[0] = true;
	4.顺序遍历
	5.最终结果
		dp[s.length()]
*/
class Solution {
    public boolean wordBreak(String s, List<String> wordDict) {
        HashSet<String> wordSet = new HashSet<String>(wordDict);
        boolean[] dp = new boolean[s.length()+1];
        dp[0] = true;
        for(int i=1;i<=s.length();++i){
            for(int j=0;j<=i-1;++j){
                if(dp[j] && wordSet.contains(s.substring(j,i))){
                    dp[i] = true;
                    break;
                }
            }
        }
        return dp[s.length()];
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29

198.打家劫舍

你是一个专业的小偷，计划偷窃沿街的房屋。每间房内都藏有一定的现金，影响你偷窃的唯一制约因素就是相邻的房屋装有相互连通的防盗系统，如果两间相邻的房屋在同一晚上被小偷闯入，系统会自动报警。

给定一个代表每个房屋存放金额的非负整数数组，计算你 不触动警报装置的情况下 ，一夜之内能够偷窃到的最高金额。
1 <= nums.length <= 100
0 <= nums[i] <= 400

• 方法一

/*
	1.确定dp数组的下标及其含义
		dp[i] 表示前i间房屋能偷窃到的最高总金额
	2.递推公式
		可知每个房间都有偷或则不偷两种状态
			当不偷第i间房时，则偷窃总金额是前i-1间房的总金额
			当偷第i间房时，则第i-1间房不能偷，因此偷窃总金额为前i-2间房的总金额加上第i间房的金额
		则可知能偷到的最高金额 dp[i] = max(dp[i-1],d[i-2]+nums[i]])
	3.初始化
		考虑边界条件
			只有一件房时
			dp[0] = nums[0];
			有两件房时
			dp[1] = max(nums[0],nums[1]);
	4.确定顺序
		由递推公式可知是顺序遍历
	5.最终结果
		dp[nums.length-1];
*/
class Solution {
    public int rob(int[] nums) {
		if(nums.length == 1){
			return nums[0];
		}
        int[] dp = new int[nums.length];
		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];
	}
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33

• 方法二

/*
	对方法一进行优化
	由递推公式dp[i] = max(dp[i-1],d[i-2]+nums[i]])可知
	dp[i]只与dp[i-1]和dp[i-2]有关，所以可以了用滚动数组的思想对空间进行优化
*/
class Solution {
    public int rob(int[] nums) {
		if(nums.length == 1){
			return nums[0];
		}
		int one = nums[0];
		int two = Math.max(nums[0],nums[1]);
		for(int i=2;i<nums.length;++i){
			int temp = two;
			two = Math.max(two,one+nums[i]);
			one = temp;
		}
		return two;
	}
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20

213.打家劫舍II

你是一个专业的小偷，计划偷窃沿街的房屋，每间房内都藏有一定的现金。这个地方所有的房屋都 围成一圈 ，这意味着第一个房屋和最后一个房屋是紧挨着的。同时，相邻的房屋装有相互连通的防盗系统，如果两间相邻的房屋在同一晚上被小偷闯入，系统会自动报警 。

给定一个代表每个房屋存放金额的非负整数数组，计算你 在不触动警报装置的情况下 ，今晚能够偷窃到的最高金额。
1 <= nums.length <= 100
0 <= nums[i] <= 1000

• 方法一

/*
	此题房子收尾相连，我们要考虑首尾的情况
	则此时我们可偷的范围变成了（0,nums.length-2）或（1，nums.length-1）
	其中每种情况又变成了打家劫舍1中的情况了
*/
class Solution {
    public int rob(int[] nums) {
        int length = nums.length;
        if(length == 1){
            return nums[0];
        }else if(length == 2){
            return Math.max(nums[0],nums[1]);
        }
        return Math.max(robRange(nums,0,length-2),robRange(nums,1,length-1));
        
    }
    public int robRange(int[] nums,int start,int end){
        int[] dp = new int[nums.length-1];
		dp[0] = nums[start];
		dp[1] = Math.max(nums[start],nums[start+1]);
		for(int i=2;i<nums.length-1;++i){
			dp[i] = Math.max(dp[i-1],dp[i-2]+nums[i+start]);
		}
		return dp[nums.length-2];
	}
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26

- 方法二
/*
	对方法一进行优化
*/
class Solution {
    public int rob(int[] nums) {
        int length = nums.length;
        if(length == 1){
            return nums[0];
        }else if(length == 2){
            return Math.max(nums[0],nums[1]);
        }
        return Math.max(robRange(nums,0,length-2),robRange(nums,1,length-1));
        
    }
    public int robRange(int[] nums,int start,int end){
        int one = nums[start];
        int two = Math.max(nums[start],nums[start+1]);
        for(int i = start+2;i<=end;++i){
            int temp = two;
            second = Math.max(one+nums[i],two);
            one = temp;
        }
        return two;
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26

221.最大正方形

在一个由 ‘0’ 和 ‘1’ 组成的二维矩阵内，找到只包含 ‘1’ 的最大正方形，并返回其面积。
m = matrix.length
n = matrix[i].length
1 <= m, n <= 300
matrix[i][j] 为 ‘0’ 或 ‘1’

来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/maximal-square
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

/*
	1.确定dp数组及其下标含义
		dp[i,j]表示以(i,j)为右下角，且只包含1的正方形的边长最大值。
		int[][] dp = new int[m][n];
	2.确定递推公式
		如果该位置的值是 0，则dp(i,j)=0，因为当前位置不可能在由1组成的正方形中；
		如果该位置的值是 1，则dp(i,j) 的值由其上方、左方和左上方的三个相邻位置的dp值决定。具体而言，当前位置的元素值等于三个相邻位置的元素中的最小值加 1
		则 dp[i][j] = min(dp[i-1][j],dp[i],j-1],dp[i-1][j-1]) + 1;
		maxSize = max(maxSize,dp[i][j])
	3.初始化
		考虑边界情况
			如果matrix[i][j] = '1';则在i=0或j=0时dp[i][j]=1;
	4.顺序遍历
	5.最终结果
		maxSide*maxSide	
*/
class Solution {
    public int maximalSquare(char[][] matrix) {
        int m = matrix.length;
        int n = matrix[0].length;
        int[][] dp = new int[m][n];
        int maxSide = 0;
        for(int i=0;i<m;++i){
			for(int j=0;j<n;++j){
				if(matrix[i][j] == '1'){
					if(i==0 || j==0){
						dp[i][j] = 1;
					}else{
						dp[i][j] = Math.min(Math.min(dp[i-1][j],dp[i][j-1]),dp[i-1][j-1]) + 1;
					}
				}
				maxSide = Math.max(maxSide,dp[i][j]);
			}	
		}
        return maxSide*maxSide;
    }
    
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38

279.完全平方数

给定正整数 n，找到若干个完全平方数（比如 1, 4, 9, 16, …）使得它们的和等于 n。你需要让组成和的完全平方数的个数最少。

给你一个整数 n ，返回和为 n 的完全平方数的 最少数量 。

完全平方数 是一个整数，其值等于另一个整数的平方；换句话说，其值等于一个整数自乘的积。例如，1、4、9 和 16 都是完全平方数，而 3 和 11 不是。
1 <= n <= 104

/*
	1.确定dp数组（dp table）以及下标的含义
		**dp[i]：和为i的完全平方数的最少数量为dp[i]**
	2.确定递推公式
		dp[j] 可以由dp[j - i * i]推出， dp[j - i * i] + 1 便可以凑成dp[j]。
		此时我们要选择最小的dp[j]，所以递推公式：dp[j] = min(dp[j - i * i] + 1, dp[j]);
	3.dp数组如何初始化
		dp[0]表示 和为0的完全平方数的最小数量，那么dp[0]一定是0。
		从递归公式dp[j] = min(dp[j - i * i] + 1, dp[j]);中可以看出每次dp[j]都要选最小的，**所以非0下标的dp[i]一定要初始为最大值，这样dp[j]在递推的时候才不会被初始值覆盖**。
		
	4.	确定遍历顺序
		我们知道这是完全背包，
		如果求组合数就是外层for循环遍历物品，内层for遍历背包。
		如果求排列数就是外层for遍历背包，内层for循环遍历物品。
		本题外层for遍历背包，里层for遍历物品，还是外层for遍历物品，内层for遍历背包，都是可以的
*/
class Solution {
    public int numSquares(int n) {
        int[] dp = new int[n+1];
        for(int i=1;i<=n;++i){
            dp[i] = Integer.MAX_VALUE;
        }
        for(int i=0;i<=n;++i){
            for(int j=1;j*j<=i;++j){
                dp[i] = Math.min(dp[i],dp[i-j*j]+1);
            }
        }
        return dp[n];
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30

1.1.3 困难题目

10.正则表达式匹配

给你一个字符串 s 和一个字符规律 p，请你来实现一个支持 ‘.’ 和 ‘*’ 的正则表达式匹配。

‘.’ 匹配任意单个字符
‘*’ 匹配零个或多个前面的那一个元素
所谓匹配，是要涵盖 整个 字符串 s的，而不是部分字符串。

0 <= s.length <= 20
0 <= p.length <= 30
s 可能为空，且只包含从 a-z 的小写字母。
p 可能为空，且只包含从 a-z 的小写字母，以及字符 . 和 *。
保证每次出现字符 * 时，前面都匹配到有效的字符

/*
	1.确定dp数组及其下标的含义
		dp[i][j]表示s的前i个字符和p的前j个字符是否匹配
		boolean[][] dp= new int[m+1][n+1];
	2.确定递推公式
		我们需要考虑三种情况
		（1）p的第j个字符是一个字母
			如果s的第j个字符和p的第j个字符相等，则dp[i][j]=dp[i-1][j-1]
			如果不相等，dp[i][j] = false
		（2）p的第j个字符是一个'.'
			则是一定匹配的，则dp[i][j]=dp[i-1][j-1]
		（3）p的第j个字符是一个'*'
			则p的第j-1个字符加上'*'可以匹配多个字符
				匹配s末尾的一个字符，将该字符扔掉，而该组合还可以继续进行匹配；
				不匹配字符，将该组合扔掉，不再进行匹配。
					则当s的第i个字符和p的第j-1个字符相等时，则dp[i][j] = dp[i-1][j] || dp[i][j-2]
					不相等时,dp[i][j] = dp[i][j-2]
	3.初始化
		空字符串也可以匹配，所以dp[0][0] = true;
	4.确定递推顺序
		由递推公式可以看出是顺序
	5.最终结果
		dp[m][n]
*/
class Solution {
    public boolean isMatch(String s, String p) {
        int m = s.length();
        int n = p.length();
        boolean[][] dp = new boolean[m+1][n+1];
        dp[0][0] = true;
        for(int i=0;i<=m;++i){
            for(int j=1;j<=n;++j){
                if(p.charAt(j-1) != '*'){
                    if(matchs(s,p,i,j)){
                        dp[i][j]=dp[i-1][j-1];
                    }else{
                        dp[i][j] = false;
                    }
                }else{
                    if(matchs(s,p,i,j-1)){
                        dp[i][j] = dp[i-1][j] || dp[i][j-2];
                    }else{
                        dp[i][j] = dp[i][j-2];
                    }
                }
            }
        }
        return dp[m][n];
    }
    //判断s第i个字符和p的第j个字符是否匹配
    private boolean matchs(String s,String p,int i,int j){
        if(i == 0){
            return false;
        }
        if(p.charAt(j-1) == '.'){
            return true;
        }
        return s.charAt(i-1) == p.charAt(j-1);
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60

72.编辑距离

给你两个单词 word1 和 word2，请你计算出将 word1 转换成 word2 所使用的最少操作数 。
你可以对一个单词进行如下三种操作：
插入一个字符
删除一个字符
替换一个字符
0 <= word1.length, word2.length <= 500
word1 和 word2 由小写英文字母组成

/*
	1.确定dp数组下标及其含义
		dp[i][j]表示word1的前i个字母转换成word2的前j个字母所使用的最少操作
		int[] dp = new int[word1.length()+1][word2.length()+1];
	2.确定递推公式
		若当前字母相同则 dp[i][j] = dp[i-1][j-1];
		否则取增删替三个操作的最小值+1
	3.初始化
		dp[i][0] = i;dp[0][j] = j
	4.遍历顺序
		由递推公式可以看出是顺序遍历
	5.最终结果
		dp[word1.length()][word2.length()]
*/
class Solution {
    public int minDistance(String word1, String word2) {
        int m = word1.length();
        int n = word2.length();

        if(m*n == 0){
            return m+n;
        }
        int[][] dp = new int[m+1][n+1];
        for(int i=0;i<m+1;++i){
            dp[i][0] = i;
        }
        for(int i=0;i<n+1;++i){
            dp[0][i] = i;
        }

        for(int i=1;i<m+1;++i){
            for(int j=1;j<n+1;++j){
                if(word1.charAt(i-1) == word2.charAt(j-1)){
                    dp[i][j] = dp[i-1][j-1];
                }else{
                    dp[i][j] = Math.min(Math.min(dp[i-1][j],dp[i][j-1]),dp[i-1][j-1])+1;
                }
                
            }
        }
        return dp[m][n];
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43

85.最大矩形

给定一个仅包含 0 和 1 、大小为 rows x cols 的二维二进制矩阵，找出只包含 1 的最大矩形，并返回其面积
rows = matrix.length
cols =matrix[0].length
0 <= row, cols <= 200
matrix[i][j] 为 ‘0’ 或 ‘1’

/*
	1.确定dp数组及其下标的含义
		dp[i][j]表示到达（i,j）位置时的宽度
		int[][] dp = new int[m][n];
	2.确定递推公式
		当matrix[i][j] == '1'的时候:
			如果j=0，则dp[i][j] = 1;
			否则则是到达(i,j-1)位置时的宽度加1，即dp[i][j] = dp[i][j-1] + 1
		确定高度时我们需要从下往上找，并且所能组能的矩形取决于最小宽度，依次求得每次矩形的面积，保留最大值就是最终结果			
		 
*/
class Solution {
    public int maximalRectangle(char[][] matrix) {
        int m = matrix.length;
        if(m == 0){
            return 0;
        }
        int n = matrix[0].length;
        int[][] dp = new int[m][n];
        for(int i=0;i<m;++i){
            for(int j=0;j<n;++j){
                if(matrix[i][j] == '1'){
                    dp[i][j] = (j==0 ? 0 : dp[i][j-1]) + 1;
                }
            }
        }

        int ret = 0;
        for(int i=0;i<m;++i){
            for(int j=0;j<n;++j){
               if(matrix[i][j] == '0'){
                   continue;
               } 

               int width = dp[i][j];
               int area = width;
               for(int k=i-1;k>=0;--k){
                   width = Math.min(width,dp[k][j]);
                   area = Math.max(area,(i-k+1)*width);
               }
               ret = Math.max(area,ret);
            }
        }
        return ret;
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46

145.不同的子序列

给定一个字符串 s 和一个字符串 t ，计算在 s 的子序列中 t 出现的个数。
字符串的一个 子序列 是指，通过删除一些（也可以不删除）字符且不干扰剩余字符相对位置所组成的新字符串。（例如，“ACE” 是 “ABCDE” 的一个子序列，而 “AEC” 不是）
题目数据保证答案符合 32 位带符号整数范围。
0 <= s.length, t.length <= 1000
s 和 t 由英文字母组成

/*
	1.确定dp数组及其下标的含义
		dp[i][j]表示字符串s的前i个字符组成的字符串的子序列中字符串t的前j个字符组成的字符串出现的个数
		int[][] dp = new int[m+1][n+1];
	2.确定递推公式
		如果s的第i个字符和t的第i个字符相等，我们可以用s的第i个字符进行匹配或则不用第i个字符进行匹配
			因此dp[i][j] = dp[i-1][j-1] + dp[i-1][j];
		如果不相等,不能用s的第i个字符进行匹配
			因此dp[i][j] = dp[i-1][j]
	3.初始化
		从递推公式dp[i][j] = dp[i - 1][j - 1] + dp[i - 1][j]; 和 dp[i][j] = dp[i - 1][j]; 中可以看出dp[i][0] 和dp[0][j]是一定要初始化的。
		dp[i][0] 表示：以第i个字符结尾的s可以随便删除元素，出现空字符串的个数。
			那么dp[i][0]一定都是1，因为也就是把以第i个字符为结尾的s，删除所有元素，出现空字符串的个数就是1。
		再来看dp[0][j]，dp[0][j]：空字符串s可以随便删除元素，出现以第j个字符为结尾的字符串t的个数。
			那么dp[0][j]一定都是0，s如论如何也变成不了t。
		最后就要看一个特殊位置了，即：dp[0][0] 应该是多少。
			dp[0][0]应该是1，空字符串s，可以删除0个元素，变成空字符串t。
	4.遍历顺序
		从递推公式dp[i][j] = dp[i - 1][j - 1] + dp[i - 1][j]; 和 dp[i][j] = dp[i - 1][j]; 
		可以看出dp[i][j]都是根据左上方和正上方推出来的。
		所以遍历的时候一定是从上到下，从左到右，这样保证dp[i][j]可以根据之前计算出来的数值进行计算。
	5.最终结果
		dp[m][n];
*/
class Solution {
    public int numDistinct(String s, String t) {
        int m = s.length();
        int n = t.length();
        int[][] dp = new int[m+1][n+1];
        for(int i=0;i<=m;++i){
			dp[i][0] = 1;
		}
		for(int i=1;i<=m;++i){
			for(int j=1;j<=n;++j){
				if(s.charAt(i-1) == t.charAt(j-1)){
					dp[i][j] = dp[i-1][j-1] + dp[i-1][j];
				}else{
					dp[i][j] = dp[i-1][j];
				}
			}
		}
		return dp[m][n];
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44

123.买卖股票的最佳时机III

给定一个数组，它的第 i 个元素是一支给定的股票在第 i 天的价格。
设计一个算法来计算你所能获取的最大利润。你最多可以完成 两笔 交易。
注意：你不能同时参与多笔交易（你必须在再次购买前出售掉之前的股票）。
1 <= prices.length <= 105
0 <= prices[i] <= 105

• 方法一

/*
	1.确定dp数组以及下标的含义
		一天一共就有五个状态， 
		没有操作
		第一次买入
		第一次卖出
		第二次买入
		第二次卖出
		dp[i][j]中 i表示第i天，j为 [0 - 4] 五个状态，dp[i][j]表示第i天状态j所剩最大现金。
		int[][] dp = new int[m][5];

	2.确定递推公式
		第i天没有操作，则和前一天没有操作状态一样
			dp[i][0] = dp[i-1][0]
		需要注意：dp[i][1]，**表示的是第i天，买入股票的状态，并不是说一定要第i天买入股票。
		达到dp[i][1]状态，有两个具体操作：
			操作一：第i天买入股票了，那么dp[i][1] = dp[i-1][0] - prices[i]
			操作二：第i天没有操作，而是沿用前一天买入的状态，即：dp[i][1] = dp[i - 1][1]
			要获取最大利润，所以 dp[i][1] = max(dp[i-1][0] - prices[i], dp[i - 1][1]);
			
		同理dp[i][2]也有两个操作：
			操作一：第i天卖出股票了，那么dp[i][2] = dp[i - 1][1] + prices[i]
			操作二：第i天没有操作，沿用前一天卖出股票的状态，即：dp[i][2] = dp[i - 1][2]
			所以dp[i][2] = max(dp[i - 1][1] + prices[i], dp[i - 1][2])
			
		同理可推出剩下状态部分：
			dp[i][3] = max(dp[i - 1][3], dp[i - 1][2] - prices[i]);
		 	dp[i][4] = max(dp[i - 1][4], dp[i - 1][3] + prices[i]);

	3.dp数组如何初始化
		第0天没有操作，这个最容易想到，就是0，即：dp[0][0] = 0;
		第0天做第一次买入的操作，dp[0][1] = -prices[0];
		第0天做第一次卖出的操作，这个初始值应该是多少呢？
			首先卖出的操作一定是收获利润，整个股票买卖最差情况也就是没有盈利即全程无操作现金为0，
		从递推公式中可以看出每次是取最大值，那么既然是收获利润如果比0还小了就没有必要收获这个利润了。
			所以dp[0][2] = 0;
		第0天第二次买入操作，初始值应该是多少呢？
			不用管第几次，现在手头上没有现金，只要买入，现金就做相应的减少
			所以第二次买入操作，初始化为：dp[0][3] = -prices[0];
		同理第二次卖出初始化dp[0][4] = 0;
	
	4.确定遍历顺序
		从递归公式其实已经可以看出，一定是从前向后遍历，因为dp[i]，依靠dp[i - 1]的数值。
	5.最终结果
		dp[m-1][4]
*/
class Solution {
    public int maxProfit(int[] prices) {
        int m = prices.length;
        int[][] dp = new int[m][5];
        dp[0][0] = 0;
        dp[0][1] = -prices[0];
        dp[0][2] = 0;
        dp[0][3] = -prices[0];
        dp[0][4] = 0;
        for(int i=1;i<m;++i){
            dp[i][0] = dp[i-1][0];
            dp[i][1] = Math.max(dp[i-1][1], dp[i-1][0] - prices[i]);
            dp[i][2] = Math.max(dp[i-1][2], dp[i-1][1] + prices[i]);
            dp[i][3] = Math.max(dp[i-1][3], dp[i-1][2] - prices[i]);
            dp[i][4] = Math.max(dp[i-1][4], dp[i-1][3] + prices[i]);
        }
        return dp[m-1][4];
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65

• 方法二

/*
	对方法一进行优化
		由递推数组可以看出，dp[i][..]只与dp[i-1][..]有关，利用滚动数组进行优化
		int dp[] = new int[5];
*/
class Solution {
    public int maxProfit(int[] prices) {
        int m = prices.length;
        int[] dp = new int[5];
        dp[1] = -prices[0];
        dp[3] = -prices[0];
        for(int i=1;i<m;++i){
            dp[1] = Math.max(dp[1], dp[0] - prices[i]);
            dp[2] = Math.max(dp[2], dp[1] + prices[i]);
            dp[3] = Math.max(dp[3], dp[2] - prices[i]);
            dp[4] = Math.max(dp[4], dp[3] + prices[i]);
        }
        return dp[4];
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20

• 方法三

/*
	还可以再进行优化到常量空间
*/
class Solution {
    public int maxProfit(int[] prices) {
        int m = prices.length;
 		int buyFirst = -prices[0];
 		int sellFirst = 0;
        int buySecond = -prices[0];
        int sellSecond = 0;
        for(int i=1;i<prices.length;++i){
            buyFirst = Math.max(buyFirst,-prices[i]);
            sellFirst = Math.max(sellFirst, buyFirst + prices[i]);
            buySecond  = Math.max(buySecond , sellFirst - prices[i]);
            sellSecond = Math.max(sellSecond, buySecond + prices[i]);
        }
        return sellSecond;
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19

188.买卖股票的最佳时机IV

给定一个整数数组 prices ，它的第 i 个元素 prices[i] 是一支给定的股票在第 i 天的价格。
设计一个算法来计算你所能获取的最大利润。你最多可以完成 k 笔交易。
注意：你不能同时参与多笔交易（你必须在再次购买前出售掉之前的股票）。
0 <= k <= 100
0 <= prices.length <= 1000
0 <= prices[i] <= 1000

• 方法一

/*
	对III的推广
	1.确定dp数组及其下标的含义
		dp[i][j] ：表示第i天的状态为j，所剩下的最大现金是dp[i][j]
		j的状态表示为：
			0 表示不操作
			1 第一次买入
			2 第一次卖出
			3 第二次买入
			4 第二次卖出
			.....
		可以看出，除了0以外，偶数就是卖出，奇数就是买入。
		题目要求是至多有K笔交易，那么j的范围就定义为 2 * k + 1 就可以了。
		int[][] dp = new int[m][2 * k + 1];
	2.确定递推公式
		达到dp[i][1]状态，有两个具体操作：
			操作一：第i天买入股票了，那么dp[i][1] = dp[i - 1][0] - prices[i]
			操作二：第i天没有操作，而是沿用前一天买入的状态，即：dp[i][1] = dp[i - 1][1]
			选最大的，所以 dp[i][1] = max(dp[i - 1][0] - prices[i], dp[i - 1][0]);
		同理dp[i][2]也有两个操作：
			操作一：第i天卖出股票了，那么dp[i][2] = dp[i - 1][1] + prices[i]
			操作二：第i天没有操作，沿用前一天卖出股票的状态，即：dp[i][2] = dp[i - 1][2]
			所以dp[i][2] = max(dp[i - 1][i] + prices[i], dp[i][2])
		同理......
			dp[i][j] = Math.max(dp[i-1][j], dp[i-1][j-1] - prices[i]); //奇数情况
    		dp[i][j+1] = Math.max(dp[i-1][j+1], dp[i-1][j] + prices[i]);//偶数情况
    3.初始化
    	第0天没有操作，这个最容易想到，就是0，即：dp[0][0] = 0;
		第0天做第一次买入的操作，dp[0][1] = -prices[0];
		第0天做第一次卖出的操作，这个初始值应该是多少呢？
			首先卖出的操作一定是收获利润，整个股票买卖最差情况也就是没有盈利即全程无操作现金为0，
		从递推公式中可以看出每次是取最大值，那么既然是收获利润如果比0还小了就没有必要收获这个利润了。
			所以dp[0][2] = 0;
		第0天第二次买入操作，初始值应该是多少呢？
			不用管第几次，现在手头上没有现金，只要买入，现金就做相应的减少
			所以第二次买入操作，初始化为：dp[0][3] = -prices[0];
		同理第二次卖出初始化dp[0][4] = 0;
		....
		可以推出当j为奇数时初始为-prices[0];偶数时为0
	4.确定遍历顺序
		从递归公式其实已经可以看出，一定是从前向后遍历，因为dp[i]，依靠dp[i - 1]的数值。
	5.最终结果
		最后一次卖出，一定是利润最大的，dp[m-1][2 * k]就是最后求解。
	*/
class Solution {
    public int maxProfit(int k, int[] prices) {
    	//本题的中数组长度可以为0，所以要考虑为0的情况
        if(prices.length == 0){
            return 0;
        }
        int m = prices.length;
        int[][] dp = new int[m][2*k+1];
        for(int j=1;j<2*k;j+=2){
			dp[0][j] = -prices[0];
		}
        for(int i=1;i<m;++i){
            for(int j=1;j<2*k;j+=2){
				dp[i][j] = Math.max(dp[i-1][j], dp[i-1][j-1] - prices[i]);
    			dp[i][j+1] = Math.max(dp[i-1][j+1], dp[i-1][j] + prices[i]);
			}
        }
        return dp[m-1][2*k];
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64

• 方法二

/*
	对方法一优化
*/
class Solution {
    public int maxProfit(int k, int[] prices) {
    	//本题的中数组长度可以为0，所以要考虑为0的情况
        if(prices.length == 0){
            return 0;
        }
        int m = prices.length;
        int[] dp = new int[2*k+1];
        for(int j=1;j<2*k;j+=2){
			dp[j] = -prices[0];
		}
        for(int i=1;i<m;++i){
            for(int j=1;j<2*k;j+=2){
				dp[j] = Math.max(dp[j], dp[j-1] - prices[i]);
    			dp[j+1] = Math.max(dp[j+1], dp[j] + prices[i]);
			}
        }
        return dp[2*k];
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23

1.2 递归

1.2.1 简单题目

21.合并两个有序链表

将两个升序链表合并为一个新的 升序 链表并返回。新链表是通过拼接给定的两个链表的所有节点组成的。
两个链表的节点数目范围是 [0, 50]
-100 <= Node.val <= 100
l1 和 l2 均按 非递减顺序 排列

/*
	1.确定递归函数的参数和返回值：确定哪些参数是递归的过程中需要处理的，那么就在递归函数里加上这个参数， 并且还要明确每次递归的返回值是什么进而确定递归函数的返回类型。

	2.确定终止条件：写完了递归算法,  运行的时候，经常会遇到栈溢出的错误，就是没写终止条件或者终止条件写的不对，操作系统也是用一个栈的结构来保存每一层递归的信息，如果递归没有终止，操作系统的内存栈必然就会溢出。

	3.确定单层递归的逻辑：确定每一层递归需要处理的信息。在这里也就会重复调用自己来实现递归的过程。
*/
/**
 * Definition for singly-linked list.
 * public class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode() {}
 *     ListNode(int val) { this.val = val; }
 *     ListNode(int val, ListNode next) { this.val = val; this.next = next; }
 * }
 */
class Solution {
    public ListNode mergeTwoLists(ListNode l1, ListNode l2) {
        if(l1 == null){//递归终止掉件
            return l2;
        }else if(l2 == null){//递归终止条件
            return l1;
        }else if(l1.val<=l2.val){//如果l1的值小于l2的值，则l1为头节点
            //l1指向剩余节点融合后的头结点
            l1.next = mergeTwoLists(l1.next,l2);
            return l1;
        }else {//反之则返回l2
            l2.next = mergeTwoLists(l1,l2.next);
            return l2; 
        }
    }   
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33

• 迭代方法

/**
 * Definition for singly-linked list.
 * public class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode() {}
 *     ListNode(int val) { this.val = val; }
 *     ListNode(int val, ListNode next) { this.val = val; this.next = next; }
 * }
 */
class Solution {
    public ListNode mergeTwoLists(ListNode l1, ListNode l2) {
        /*
            思路：
                1.创建新链表前置节点
                2.循环遍历两个链表，逐个比较，将较小的节点添加到新的链表
                3.遍历结束则两个链表至少有一个是完全遍历的，则将另一个链表的剩余部分添加到新的链表
                4.最后前置节点的下个节点就是新链表的头节点
        */
        ListNode preHead = new ListNode(-1);
        ListNode cur = preHead;
        while(l1 != null && l2 != null){
            if(l1.val<=l2.val){
                cur.next = l1;
                l1 = l1.next;
            }else{
                cur.next = l2;
                l2 = l2.next;
            }
            cur = cur.next;
        }
        cur.next = l1 == null ? l2 : l1;
        return preHead.next;
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35

203.移除链表元素

给你一个链表的头节点 head 和一个整数 val ，请你删除链表中所有满足 Node.val == val 的节点，并返回 新的头节点 。
列表中的节点数目在范围 [0, 104] 内
1 <= Node.val <= 50
0 <= val <= 50

/**
 * Definition for singly-linked list.
 * public class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode() {}
 *     ListNode(int val) { this.val = val; }
 *     ListNode(int val, ListNode next) { this.val = val; this.next = next; }
 * }
 */
class Solution {
    public ListNode removeElements(ListNode head, int val) {
        if(head == null){//递归终止条件
            return head;
        }
        //先删除头节点后值与val相等的元素
        head.next = removeElements(head.next,val);//调用自身
        //最后判断头节点的值是否与val相等，不相等则返回头节点，相等，则返回头节点指向的下个节点
        return head.val == val ? head.next : head;
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21

• 迭代方法

/**
 * Definition for singly-linked list.
 * public class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode() {}
 *     ListNode(int val) { this.val = val; }
 *     ListNode(int val, ListNode next) { this.val = val; this.next = next; }
 * }
 */
class Solution {
    public ListNode removeElements(ListNode head, int val) {
       /*
            思路：
                1.创建一个前置头节点
                2.循环遍历链表，如果节点值和val相等，进行删除，否则继续遍历
                3.返回新链表的头节点
        */
        ListNode preHead = new ListNode(-1);
        preHead.next = head;
        ListNode cur = preHead;
        while(cur.next != null){
            if(cur.next.val == val){
                cur.next = cur.next.next;
            }else{
                cur = cur.next;
            }
        }
        return preHead.next;
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31

206.反转链表

给你单链表的头节点 head ，请你反转链表，并返回反转后的链表。
链表中节点的数目范围是 [0, 5000]
-5000 <= Node.val <= 5000

/*
	
*/

/**
 * Definition for singly-linked list.
 * public class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode() {}
 *     ListNode(int val) { this.val = val; }
 *     ListNode(int val, ListNode next) { this.val = val; this.next = next; }
 * }
 */
class Solution {
    public ListNode reverseList(ListNode head) {
        if(head == null || head.next == null){//递归终止条件
            return head;
        }
        ListNode newNode = reverseList(head.next);//调用自身，对head节点后的结点进行反转
        //从head.next开始后面的链表已经反转，要进行反转则head.next的下个节点就是它反转前的上一个节点
        //则head.next.next = head;
        /*
			比如 1->2->3->4->5->∅
			则反转后应该是 ∅<-1<-2<-3<-4<-5
			假如此时我们已经对3后面的进行了反转（即从3.next开始）即 1->2->3<-4<-5
			3.next指向的是4，则要进行反转，4的下个节点就要指向3，则就是3.next.next = 3;
		*/
        head.next.next = head;
        //最后一个节点的下个节点要为空
        head.next = null;
        return newNode;
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34

• 迭代方法

/**
 * Definition for singly-linked list.
 * public class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode() {}
 *     ListNode(int val) { this.val = val; }
 *     ListNode(int val, ListNode next) { this.val = val; this.next = next; }
 * }
 */
class Solution {
    public ListNode reverseList(ListNode head) {
        /*
            思路：
                1->2->3->4->5->∅
                ∅<-1<-2<-3<-4<-5
        */
        ListNode pre = null;
        ListNode cur = head;
        while(cur != null){
            ListNode next = cur.next; 
            cur.next = pre;
            pre = cur;
            cur = next;
        }
        return pre;
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28

1.2.2 中等题目

24.两两交换链表中节点

给定一个链表，两两交换其中相邻的节点，并返回交换后的链表。
你不能只是单纯的改变节点内部的值，而是需要实际的进行节点交换。
链表中节点的数目在范围 [0, 100] 内
0 <= Node.val <= 100

/*
	终止条件：本题终止条件很明显，当递归到链表为空或者链表只剩一个元素的时候，终止。
	单次的过程：因为递归是重复做一样的事情，所以从宏观上考虑，只用考虑某一步是怎么完成的。
	返回值：返回给上一层递归的值应该是已经交换完成后的子链表。
	
*/
/**
 * Definition for singly-linked list.
 * public class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode() {}
 *     ListNode(int val) { this.val = val; }
 *     ListNode(int val, ListNode next) { this.val = val; this.next = next; }
 * }
 */
class Solution {
    public ListNode swapPairs(ListNode head) {
        if(head == null || head.next == null){//递归的终止条件
            return head;
        }
        /*
			可以想象只有2个结点的情况，了解一个过程就了解全部过程了
		*/
        ListNode newHead = head.next;
        head.next = swapPairs(newHead.next);//新链表的
        newHead.next = head;
        return newHead;
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30

50. Pow(x, n)

实现 pow(x, n) ，即计算 x 的 n 次幂函数（即，x^n）。
-100.0 < x < 100.0
-231 <= n <= 231-1
-104 <= x^n <= 104

class Solution {
    public double myPow(double x, int n) {
        return n>=0 ? pow(x,n) :  1/pow(x,-n);
    }
    private double pow(double x,int n){
        if(n == 0){//递归终止条件
            return 1.0;
        }
        double y = pow(x,n/2);//调用自身
        return n%2 == 0 ? y*y : y*y*x;//讨论n为奇数还是偶数
    }
}
1
2
3
4
5
6
7
8
9
10
11
12

1.3 深度优先搜索

1.3.1 简单题目

94.二叉树的中序遍历

给定一个二叉树的根节点 root ，返回它的 中序 遍历
树中节点数目在范围 [0, 100] 内
-100 <= Node.val <= 100。

/*
	中序遍历就是先左子节点，再父节点，再右子节点
*/

/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode() {}
 *     TreeNode(int val) { this.val = val; }
 *     TreeNode(int val, TreeNode left, TreeNode right) {
 *         this.val = val;
 *         this.left = left;
 *         this.right = right;
 *     }
 * }
 */
class Solution {
    public List<Integer> inorderTraversal(TreeNode root) {
        List<Integer> list = new ArrayList<Integer>();
        inorder(root,list);
        return list;
    }
    private void inorder(TreeNode root,List<Integer> list){
        if(root == null){
            return;
        }
        inorder(root.left,list);
        list.add(root.val);
        inorder(root.right,list);
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34

100.相同的树

给你两棵二叉树的根节点 p 和 q ，编写一个函数来检验这两棵树是否相同。
如果两个树在结构上相同，并且节点具有相同的值，则认为它们是相同的
两棵树上的节点数目都在范围 [0, 100] 内
-104 <= Node.val <= 104

/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode() {}
 *     TreeNode(int val) { this.val = val; }
 *     TreeNode(int val, TreeNode left, TreeNode right) {
 *         this.val = val;
 *         this.left = left;
 *         this.right = right;
 *     }
 * }
 */
class Solution {
    public boolean isSameTree(TreeNode p, TreeNode q) {
        if(p == null && q==null){
            return true;
        }else if(p == null || q == null){
            return false;
        }else if(p.val != q.val){
            return false;
        }else{
            return isSameTree(p.left,q.left) && isSameTree(p.right,q.right);//递归判断左子树和右子树
        }
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28

101.对称二叉树

给定一个二叉树，检查它是否是镜像对称的

/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode() {}
 *     TreeNode(int val) { this.val = val; }
 *     TreeNode(int val, TreeNode left, TreeNode right) {
 *         this.val = val;
 *         this.left = left;
 *         this.right = right;
 *     }
 * }
 */
class Solution {
    public boolean isSymmetric(TreeNode root) {
        return checkTreeNode(root,root);
    }
    private boolean checkTreeNode(TreeNode node1,TreeNode node2){
        if(node1 == null && node2 == null){
            return true;
        }else if(node1 == null || node2 == null){
            return false;
        }
        return node1.val == node2.val && checkTreeNode(node1.left,node2.right) && checkTreeNode(node1.right,node2.left);
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28

104.二叉树的最大深度

给定一个二叉树，找出其最大深度。
二叉树的深度为根节点到最远叶子节点的最长路径上的节点数。
说明: 叶子节点是指没有子节点的节点。

/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode() {}
 *     TreeNode(int val) { this.val = val; }
 *     TreeNode(int val, TreeNode left, TreeNode right) {
 *         this.val = val;
 *         this.left = left;
 *         this.right = right;
 *     }
 * }
 */
class Solution {
    public int maxDepth(TreeNode root) {
        if(root==null){
            return 0;
        }
        int left = maxDepth(root.left);
        int right = maxDepth(root.right);
        return Math.max(left,right)+1;
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25

110.平衡二叉树

给定一个二叉树，判断它是否是高度平衡的二叉树。
本题中，一棵高度平衡二叉树定义为：
一个二叉树每个节点 的左右两个子树的高度差的绝对值不超过 1 。
树中的节点数在范围 [0, 5000] 内
-104 <= Node.val <= 104

• 方法一：自顶向下

/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode() {}
 *     TreeNode(int val) { this.val = val; }
 *     TreeNode(int val, TreeNode left, TreeNode right) {
 *         this.val = val;
 *         this.left = left;
 *         this.right = right;
 *     }
 * }
 */
class Solution {
    public boolean isBalanced(TreeNode root) {
    	  /* 
            求出每个节点的高度
            判断每个节点的左右两个子树的高度差的绝对值是否超过1
            递归时还要考虑左子树和右子树是否为平衡二叉树
        */
        if(root == null){
            return true;
        }
        return Math.abs(height(root.left)-height(root.right))<=1  && isBalanced(root.left) && isBalanced(root.right); 
    }
    //求每个结点的高度
    private int height(TreeNode root){
        if(root == null){
            return 0;
        }else{
            return Math.max(height(root.left),height(root.right))+1;
        }
        
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37

• 方法二：自底向上

/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode() {}
 *     TreeNode(int val) { this.val = val; }
 *     TreeNode(int val, TreeNode left, TreeNode right) {
 *         this.val = val;
 *         this.left = left;
 *         this.right = right;
 *     }
 * }
 */
class Solution {
    public boolean isBalanced(TreeNode root) {
        return height(root) != -1;
    }
    private int height(TreeNode root){
        if(root == null){
            return 0;
        }

        //类似于后序遍历
        int leftHeight =  height(root.left);
        int rightHeight = height(root.right);
        if(leftHeight == -1 || rightHeight == -1 || Math.abs(leftHeight-rightHeight)>1){
            return -1;
        }else{
            return Math.max(leftHeight,rightHeight)+1;
        }

    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35

111.二叉树的最小深度

给定一个二叉树，找出其最小深度。
最小深度是从根节点到最近叶子节点的最短路径上的节点数量。
说明：叶子节点是指没有子节点的节点。
树中节点数的范围在 [0, 105] 内
-1000 <= Node.val <= 1000

/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode() {}
 *     TreeNode(int val) { this.val = val; }
 *     TreeNode(int val, TreeNode left, TreeNode right) {
 *         this.val = val;
 *         this.left = left;
 *         this.right = right;
 *     }
 * }
 */
class Solution {
    public int minDepth(TreeNode root) {
        if(root == null){
            return 0;
        }
        if(root.left ==  null && root.right  == null){
            return 1;
        }
        int min = Integer.MAX_VALUE;
        if(root.left != null){
            min = Math.min(min,minDepth(root.left));
        }
        if(root.right != null){
            min = Math.min(min,minDepth(root.right));
        }
        return min+1;
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33

112.路径总和

给你二叉树的根节点 root 和一个表示目标和的整数 targetSum ，判断该树中是否存在 根节点到叶子节点 的路径，这条路径上所有节点值相加等于目标和 targetSum 。
叶子节点 是指没有子节点的节点。
树中节点的数目在范围 [0, 5000] 内
-1000 <= Node.val <= 1000
-1000 <= targetSum <= 1000

/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode() {}
 *     TreeNode(int val) { this.val = val; }
 *     TreeNode(int val, TreeNode left, TreeNode right) {
 *         this.val = val;
 *         this.left = left;
 *         this.right = right;
 *     }
 * }
 */
class Solution {
    public boolean hasPathSum(TreeNode root, int targetSum) {
        if(root == null){
            return false;
        }
        if(root.left == null && root.right == null){
            return root.val == targetSum;
        }
        return hasPathSum(root.left,targetSum - root.val) || hasPathSum(root.right,targetSum-root.val);
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26

144.二叉树的前序遍历

给你二叉树的根节点 root ，返回它节点值的 前序 遍历。
树中节点数目在范围 [0, 100] 内
-100 <= Node.val <= 100

/*
	前序遍历：父节点 -> 左子节点 -> 右子节点
*/
/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode() {}
 *     TreeNode(int val) { this.val = val; }
 *     TreeNode(int val, TreeNode left, TreeNode right) {
 *         this.val = val;
 *         this.left = left;
 *         this.right = right;
 *     }
 * }
 */
class Solution {
    public List<Integer> preorderTraversal(TreeNode root) {
        List<Integer> list = new ArrayList<Integer>();
        preOrder(root,list);
        return list;
    }
    private void preOrder(TreeNode root,List<Integer> list){
        if(root == null){
            return;
        }
        list.add(root.val);
        preOrder(root.left,list);
        preOrder(root.right,list);
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33

145.二叉树的后序遍历

给定一个二叉树，返回它的 后序 遍历。

/*
	后序遍历：左子节点 -> 右子节点 -> 父子节点
*/
/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode() {}
 *     TreeNode(int val) { this.val = val; }
 *     TreeNode(int val, TreeNode left, TreeNode right) {
 *         this.val = val;
 *         this.left = left;
 *         this.right = right;
 *     }
 * }
 */
class Solution {
    public List<Integer> postorderTraversal(TreeNode root) {
        List<Integer> list = new ArrayList<Integer>();
        postOrder(root,list);
        return list; 
    }
    private void postOrder(TreeNode root,List<Integer> list){
        if(root == null){
            return;
        }
        postOrder(root.left,list);
        postOrder(root.right,list);
        list.add(root.val);
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33

226.翻转二叉树

/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode() {}
 *     TreeNode(int val) { this.val = val; }
 *     TreeNode(int val, TreeNode left, TreeNode right) {
 *         this.val = val;
 *         this.left = left;
 *         this.right = right;
 *     }
 * }
 */
class Solution {
    public TreeNode invertTree(TreeNode root) {
        if(root == null){
            return null;
        }
        TreeNode left = invertTree(root.left);
        TreeNode right= invertTree(root.right);
        root.left = right;
        root.right = left;
        return root;
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27

404.左叶子之和

/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode() {}
 *     TreeNode(int val) { this.val = val; }
 *     TreeNode(int val, TreeNode left, TreeNode right) {
 *         this.val = val;
 *         this.left = left;
 *         this.right = right;
 *     }
 * }
 */
class Solution {
    //后续遍历
    public int sumOfLeftLeaves(TreeNode root) {
        if(root == null){
            return 0;
        }
        int leftValue = sumOfLeftLeaves(root.left);
        int rightValue = sumOfLeftLeaves(root.right);
        int midValue = 0;
        if(root.left != null && root.left.left == null && root.left.right == null){
            midValue = root.left.val;
        }
        return midValue + leftValue + rightValue;
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30

617.合并二叉树

给定两个二叉树，想象当你将它们中的一个覆盖到另一个上时，两个二叉树的一些节点便会重叠。

你需要将他们合并为一个新的二叉树。合并的规则是如果两个节点重叠，那么将他们的值相加作为节点合并后的新值，否则不为 NULL 的节点将直接作为新二叉树的节点。

/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode() {}
 *     TreeNode(int val) { this.val = val; }
 *     TreeNode(int val, TreeNode left, TreeNode right) {
 *         this.val = val;
 *         this.left = left;
 *         this.right = right;
 *     }
 * }
 */
class Solution {
    //前序遍历
    public TreeNode mergeTrees(TreeNode root1, TreeNode root2) {
        if(root1 == null){
            return root2;
        }
        if(root2 == null){
            return root1;
        }
        TreeNode root = new TreeNode(root1.val + root2.val);
        root.left = mergeTrees(root1.left,root2.left);
        root.right = mergeTrees(root1.right,root2.right);
        return root;
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30

1.3.2 中等题目

98.验证二叉搜索树

给定一个二叉树，判断其是否是一个有效的二叉搜索树。

假设一个二叉搜索树具有如下特征：

节点的左子树只包含小于当前节点的数。
节点的右子树只包含大于当前节点的数。
所有左子树和右子树自身必须也是二叉搜索树。

/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode() {}
 *     TreeNode(int val) { this.val = val; }
 *     TreeNode(int val, TreeNode left, TreeNode right) {
 *         this.val = val;
 *         this.left = left;
 *         this.right = right;
 *     }
 * }
 */
class Solution {
    //中序遍历(因为中序遍历出来的结果是顺序的，若遍历完成则是有效的二叉搜索树，否则不是)
    private long min = Long.MIN_VALUE;
    public boolean isValidBST(TreeNode root) {
        if(root == null){
            return true;
        }
        if(!isValidBST(root.left)){
            return false; 
        }
        if(root.val<=min){
            return false;
        }
        min = root.val;
        return isValidBST(root.right);
    }

}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33

99.恢复搜索二叉树

给你二叉搜索树的根节点 root ，该树中的两个节点被错误地交换。请在不改变其结构的情况下，恢复这棵树。

/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode() {}
 *     TreeNode(int val) { this.val = val; }
 *     TreeNode(int val, TreeNode left, TreeNode right) {
 *         this.val = val;
 *         this.left = left;
 *         this.right = right;
 *     }
 * }
 */
class Solution {
    /*
    中序遍历
    	中序遍历输出的结果是顺序的，如果发现不是顺序的，则说明右节点被错误的交换，
    	记录错误的结点，最后对值进行交换
    */
    private TreeNode  node1,node2,preNode;
    public void recoverTree(TreeNode root) {
        inorder(root);
        int temp = node1.val;
        node1.val = node2.val;
        node2.val = temp;
    }
    private void inorder(TreeNode root){
        if(root == null){
            return;
        }
        inorder(root.left);
        if(preNode != null && preNode.val > root.val){
            if(node1 == null){
                node1 = preNode;//记录第一个错误结点
            }
            node2 = root;//记录第二个错误结点
        }
        preNode = root;
        inorder(root.right);
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43

113.路径总和

给你二叉树的根节点 root 和一个整数目标和 targetSum ，找出所有 从根节点到叶子节点 路径总和等于给定目标和的路径。

叶子节点 是指没有子节点的节点。
树中节点总数在范围 [0, 5000] 内
-1000 <= Node.val <= 1000
-1000 <= targetSum <= 1000

/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode() {}
 *     TreeNode(int val) { this.val = val; }
 *     TreeNode(int val, TreeNode left, TreeNode right) {
 *         this.val = val;
 *         this.left = left;
 *         this.right = right;
 *     }
 * }
 */
class Solution {
    private List<List<Integer>> ans = new ArrayList<List<Integer>>();  
    public List<List<Integer>> pathSum(TreeNode root, int targetSum) {
        List<Integer> list = new ArrayList<Integer>();
        preOrder(root,targetSum,list);
        return ans;
    }
    //前序遍历（递归+回溯）
    private void preOrder(TreeNode root,int targetSum,List<Integer> list){
        if(root == null){      
            return;
        }
        list.add(root.val);
        if(root.val == targetSum && root.left == null && root.right == null){
            ans.add(new ArrayList<Integer>(list));
        }
        preOrder(root.left,targetSum-root.val,list);
        preOrder(root.right,targetSum-root.val,list);
        list.remove(list.size()-1);//回溯
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36

114.二叉树展开为链表

给你二叉树的根结点 root ，请你将它展开为一个单链表：

展开后的单链表应该同样使用 TreeNode ，其中 right 子指针指向链表中下一个结点，而左子指针始终为 null 。
展开后的单链表应该与二叉树 先序遍历 顺序相同。

树中结点数在范围 [0, 2000] 内
-100 <= Node.val <= 100

/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode() {}
 *     TreeNode(int val) { this.val = val; }
 *     TreeNode(int val, TreeNode left, TreeNode right) {
 *         this.val = val;
 *         this.left = left;
 *         this.right = right;
 *     }
 * }
 */
class Solution {
    //后序遍历
    public void flatten(TreeNode root) {
        if(root == null){
            return;
        }
        //先把左右子树拉直
        flatten(root.left);
        flatten(root.right);

        //先保存右子树
        TreeNode right = root.right;
        //把拉直的左子树，放在右边
        root.right = root.left;
        //把左子树置空
        root.left = null;
        //找到最右节点
        while(root.right != null){
            root = root.right;
        }
        //把拉直的右节点放在最右结点的后面
        root.right = right;
    }

}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40

116.填充每个节点的下一个右侧节点指针

给定一个 完美二叉树 ，其所有叶子节点都在同一层，每个父节点都有两个子节点。二叉树定义如下：

struct Node {
int val;
Node *left;
Node *right;
Node *next;
}
填充它的每个 next 指针，让这个指针指向其下一个右侧节点。如果找不到下一个右侧节点，则将 next 指针设置为 NULL。
初始状态下，所有 next 指针都被设置为 NULL。
树中节点的数量少于 4096
-1000 <= node.val <= 1000

/*
// Definition for a Node.
class Node {
    public int val;
    public Node left;
    public Node right;
    public Node next;

    public Node() {}
    
    public Node(int _val) {
        val = _val;
    }

    public Node(int _val, Node _left, Node _right, Node _next) {
        val = _val;
        left = _left;
        right = _right;
        next = _next;
    }
};
*/

class Solution {
	//前序遍历
    public Node connect(Node root) {
        if(root == null || root.left == null){
            return root; 
        }
        root.left.next = root.right;
        if(root.next != null){
            root.right.next = root.next.left;
        }
        connect(root.left);
        connect(root.right);
        return root;
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38

117.填充每个节点的下一个右侧节点指针 II

给定一个二叉树

struct Node {
int val;
Node *left;
Node *right;
Node *next;
}
填充它的每个 next 指针，让这个指针指向其下一个右侧节点。如果找不到下一个右侧节点，则将 next 指针设置为 NULL。

初始状态下，所有 next 指针都被设置为 NULL。

树中的节点数小于 6000
-100 <= node.val <= 100

/*
// Definition for a Node.
class Node {
    public int val;
    public Node left;
    public Node right;
    public Node next;

    public Node() {}
    
    public Node(int _val) {
        val = _val;
    }

    public Node(int _val, Node _left, Node _right, Node _next) {
        val = _val;
        left = _left;
        right = _right;
        next = _next;
    }
};
*/
/*
	左节点：
		root有左节点和右节点，则左节点的next为右节点
		root右节点为null，则查找父节点的兄弟节点的最左边子元素
	
	右节点：
		root右节点不为null，其next为父节点的兄弟节点的最左边子元素
	要先构建右子树，再构建左子树，因为寻找父节点的兄弟节点是从左到右遍历的，如果右子树next没接上就遍历，会出错
*/
class Solution {
    public Node connect(Node root) {
        if(root == null){
            return root;
        }
        if(root.left != null){
            if(root.right != null){
                root.left.next = root.right;
            }else{
                root.left.next = findChild(root);
            }
        }
        if(root.right != null){
            root.right.next = findChild(root); 
        }
        connect(root.right);
        connect(root.left);
        return root;
    }
    private Node findChild(Node root){
        if(root.next == null){
            return null;
        }
        while(root.next != null){
            if(root.next.left != null){
                return root.next.left;
            }
            if(root.next.right != null){
                return root.next.right;
            }
            root = root.next;
        }
        return null;
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66

129. 求根节点到叶节点数字之和

给你一个二叉树的根节点 root ，树中每个节点都存放有一个 0 到 9 之间的数字。
每条从根节点到叶节点的路径都代表一个数字：

例如，从根节点到叶节点的路径 1 -> 2 -> 3 表示数字 123 。
计算从根节点到叶节点生成的 所有数字之和 。

叶节点 是指没有子节点的节点。

树中节点的数目在范围 [1, 1000] 内
0 <= Node.val <= 9
树的深度不超过 10

/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode() {}
 *     TreeNode(int val) { this.val = val; }
 *     TreeNode(int val, TreeNode left, TreeNode right) {
 *         this.val = val;
 *         this.left = left;
 *         this.right = right;
 *     }
 * }
 */
class Solution {
    int sum = 0;//用来存放最后结果
    public int sumNumbers(TreeNode root) {
        dfs(root,0);
        return sum;
    }
    //前序遍历
    private void dfs(TreeNode root,int preNum){
        if(root == null){
            return;
        }
        if(root.left == null && root.right == null){
            sum += preNum*10 + root.val;
            return;
        }
        dfs(root.left,preNum*10 + root.val);//左
        dfs(root.right,preNum*10 + root.val);//右
    }
}
 
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35

130.被围绕的区域

给你一个 m x n 的矩阵 board ，由若干字符 ‘X’ 和 ‘O’ ，找到所有被 ‘X’ 围绕的区域，并将这些区域里所有的 ‘O’ 用 ‘X’ 填充。
m == board.length
n == board[i].length
1 <= m, n <= 200
board[i][j] 为 ‘X’ 或 ‘O’

class Solution {
    int n,m;
    public void solve(char[][] board) {
       n = board.length;
       m = board[0].length;

       //把边界上的O变为T
       for(int i=0;i<n;++i){
           dfs(board,i,0);
           dfs(board,i,m-1);
       }
       for(int  j=1;j<m-1;++j){
           dfs(board,0,j);
           dfs(board,n-1,j);
        }

        for(int i=0;i<n;++i){
            for(int j=0;j<m;++j){
                if(board[i][j] == 'T'){
                    board[i][j] = 'O';
                }else if(board[i][j] == 'O'){
                    board[i][j] = 'X';
                }
            }
        }
    }

    //把O变为T的方法
    public void dfs(char[][] board,int r,int c){
        if(r<0 || c<0 || r>=n || c>= m || board[r][c] != 'O'){
            return;
        }
        board[r][c] = 'T';
        //上下左右搜索
        dfs(board,r+1,c);
        dfs(board,r-1,c);
        dfs(board,r,c+1);
        dfs(board,r,c-1);
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40

133.克隆图

给你无向 连通 图中一个节点的引用，请你返回该图的 深拷贝（克隆）。

图中的每个节点都包含它的值 val（int） 和其邻居的列表（list[Node]）。

class Node {
public int val;
public List neighbors;
}

class Solution {
    private HashMap<Node, Node> visited = new HashMap <> ();
    public Node cloneGraph(Node node) {
        if (node == null) {
            return node;
        }

        // 如果该节点已经被访问过了，则直接从哈希表中取出对应的克隆节点返回
        if (visited.containsKey(node)) {
            return visited.get(node);
        }

        // 克隆节点，注意到为了深拷贝我们不会克隆它的邻居的列表
        Node cloneNode = new Node(node.val, new ArrayList());
        // 哈希表存储
        visited.put(node, cloneNode);

        // 遍历该节点的邻居并更新克隆节点的邻居列表
        for (Node neighbor: node.neighbors) {
            cloneNode.neighbors.add(cloneGraph(neighbor));
        }
        return cloneNode;
    }
}

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25

199. 二叉树的右视图

给定一个二叉树的 根节点 root，想象自己站在它的右侧，按照从顶部到底部的顺序，返回从右侧所能看到的节点值。
二叉树的节点个数的范围是 [0,100]
-100 <= Node.val <= 100

/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode() {}
 *     TreeNode(int val) { this.val = val; }
 *     TreeNode(int val, TreeNode left, TreeNode right) {
 *         this.val = val;
 *         this.left = left;
 *         this.right = right;
 *     }
 * }
 */
class Solution {
    public List<Integer> rightSideView(TreeNode root) {
        List<Integer> list = new ArrayList<Integer>();
        dfs(root,0,list);
        return list;
    }
    //类比前序遍历，不过顺序是中右左
    private void dfs(TreeNode root,int depth,List<Integer> list){
        if(root == null){
            return;
        }
        if(list.size() == depth){//表明此结点是当前层的最右节点
            list.add(root.val);
        }
        depth++;//下一层
        dfs(root.right,depth,list);
        dfs(root.left,depth,list);
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34

200. 岛屿数量

给你一个由 ‘1’（陆地）和 ‘0’（水）组成的的二维网格，请你计算网格中岛屿的数量。

岛屿总是被水包围，并且每座岛屿只能由水平方向和/或竖直方向上相邻的陆地连接形成。

此外，你可以假设该网格的四条边均被水包围。
m = grid.length
n = grid[i].length
1 <= m, n <= 300
grid[i][j] 的值为 ‘0’ 或 ‘1’

/*
	我们可以将二维网格看成一个无向图，竖直或水平相邻的 11 之间有边相连。

	为了求出岛屿的数量，我们可以扫描整个二维网格。如果一个位置为 1，则以其为起始节点开始进行深度优先搜索。在深度优先搜索的过程中，每个搜索到的 1 都会被重新标记为 0。
	
	最终岛屿的数量就是我们进行深度优先搜索的次数。
*/
class Solution {
    public int numIslands(char[][] grid) {
        if(grid==null || grid.length==0){
            return 0;
        }
        int nr = grid.length;
        int nc = grid[0].length;
        int count = 0;
        for(int i=0;i<nr;++i){
            for(int j=0;j<nc;++j){
                if(grid[i][j] == '1'){
                    ++count;
                    dfs(grid,i,j);
                }
            }
        }
        return count;
    }

    public void dfs(char[][] grid,int r,int c){
        int nr = grid.length;
        int nc = grid[0].length;

        if(r<0 || c<0 || r>=nr || c>=nc || grid[r][c]== '0'){
            return;
        } 

        grid[r][c] = '0';//搜索过标记为0;

        dfs(grid,r+1,c);
        dfs(grid,r-1,c);
        dfs(grid,r,c+1);
        dfs(grid,r,c-1);
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42

230. 二叉搜索树中第K小的元素

给定一个二叉搜索树的根节点 root ，和一个整数 k ，请你设计一个算法查找其中第 k 个最小元素（从 1 开始计数）。
树中的节点数为 n 。
1 <= k <= n <= 104
0 <= Node.val <= 104

/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode() {}
 *     TreeNode(int val) { this.val = val; }
 *     TreeNode(int val, TreeNode left, TreeNode right) {
 *         this.val = val;
 *         this.left = left;
 *         this.right = right;
 *     }
 * }
 */
class Solution {
    List<Integer> list = new ArrayList<Integer>();
    public int kthSmallest(TreeNode root, int k) {
        inorder(root);
        return list.get(k-1);
    }
    //中序遍历输出的结果是顺序的，把结果保存在集合中
    private void inorder(TreeNode root){
        if(root == null){
            return;
        }
        inorder(root.left);
        list.add(root.val);
        inorder(root.right);
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31

236.二叉树的最近公共祖先

给定一个二叉树, 找到该树中两个指定节点的最近公共祖先。

百度百科中最近公共祖先的定义为：“对于有根树 T 的两个节点 p、q，最近公共祖先表示为一个节点 x，满足 x 是 p、q 的祖先且 x 的深度尽可能大（一个节点也可以是它自己的祖先）。”

树中节点数目在范围 [2, 105] 内。
-109 <= Node.val <= 109
所有 Node.val 互不相同 。
p != q
p 和 q 均存在于给定的二叉树中

/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode(int x) { val = x; }
 * }
 */
class Solution {
    private TreeNode ans;//用于存储最后结果
    public Solution() {
        this.ans = null;
    }
    public TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) {
        dfs(root,p,q);
        return ans;
    }
    private boolean dfs(TreeNode node,TreeNode p,TreeNode q){
        if(node == null){
            return false;
        }
        boolean left = dfs(node.left,p,q);
        boolean right = dfs(node.right,p,q);
		/*
			如果这个节点是p，q的公共祖先，
				则要么p，q存在于这个节点的左子节点或则右子节点，
				要么这个节点是p（或q），q（或p）在左子节点或右子节点
		*/
        if((left && right) || (node.val == p.val || node.val == q.val) && (left || right)){
            ans = node;
        }
        return left || right || node.val == p.val || node.val == q.val;
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36

1.3.3 困难题目

124.二叉树中的最大路径和

路径 被定义为一条从树中任意节点出发，沿父节点-子节点连接，达到任意节点的序列。同一个节点在一条路径序列中 至多出现一次 。该路径 至少包含一个 节点，且不一定经过根节点。

路径和 是路径中各节点值的总和。

给你一个二叉树的根节点 root ，返回其 最大路径和 。

/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode() {}
 *     TreeNode(int val) { this.val = val; }
 *     TreeNode(int val, TreeNode left, TreeNode right) {
 *         this.val = val;
 *         this.left = left;
 *         this.right = right;
 *     }
 * }
 */
class Solution {
    int maxSum = Integer.MIN_VALUE;
    public int maxPathSum(TreeNode root) {
        maxGain(root);
        return maxSum;
    }
    //后续遍历
    private int maxGain(TreeNode root){
        if(root == null){
            return 0;
        }
        int leftGain = Math.max(maxGain(root.left),0);//左子节点最大增益
        int rightGain = Math.max(maxGain(root.right),0);//右子节点最大增益
        maxSum = Math.max(maxSum,leftGain+rightGain+root.val);// 节点的最大路径和取决于该节点的值与该节点的左右子节点的最大贡献值
        return Math.max(leftGain,rightGain)+root.val;// 返回节点的最大贡献值
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32

297.二叉树的序列化和反序列化

序列化是将一个数据结构或者对象转换为连续的比特位的操作，进而可以将转换后的数据存储在一个文件或者内存中，同时也可以通过网络传输到另一个计算机环境，采取相反方式重构得到原数据。

请设计一个算法来实现二叉树的序列化与反序列化。这里不限定你的序列 / 反序列化算法执行逻辑，你只需要保证一个二叉树可以被序列化为一个字符串并且将这个字符串反序列化为原始的树结构。

提示: 输入输出格式与 LeetCode 目前使用的方式一致，详情请参阅 LeetCode 序列化二叉树的格式。你并非必须采取这种方式，你也可以采用其他的方法解决这个问题。

树中结点数在范围 [0, 104] 内
-1000 <= Node.val <= 1000

/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode(int x) { val = x; }
 * }
 */
public class Codec {

    // Encodes a tree to a single string.
    public String serialize(TreeNode root) {
        return serializeDfs(root,"");
    }

    // Decodes your encoded data to tree.
    public TreeNode deserialize(String data) {
        String[] dataArray = data.split(",");
        List<String> dataList = new LinkedList<String>(Arrays.asList(dataArray));
        return deserializeDfs(dataList);
    }
	
	//前序遍历，将数字转换为字符串用逗号隔开，值为空的转换为None
    private String serializeDfs(TreeNode root,String s){
        if(root == null){
            s += "None,";
        }else{
            s += s.valueOf(root.val)+",";
            s = serializeDfs(root.left,s);
            s = serializeDfs(root.right,s);
        } 
        return s;
    }
    //前序遍历
    private TreeNode deserializeDfs(List<String> dataList) {
        if(dataList.get(0).equals("None")){
            dataList.remove(0);
            return null;
        }
        TreeNode root = new TreeNode(Integer.parseInt(dataList.get(0)));
        dataList.remove(0);
        root.left = deserializeDfs(dataList);
        root.right = deserializeDfs(dataList);
        return root;
    }
}

// Your Codec object will be instantiated and called as such:
// Codec ser = new Codec();
// Codec deser = new Codec();
// TreeNode ans = deser.deserialize(ser.serialize(root));


1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54

1.4 广度优先搜索

1.2.1 中等题目

102.二叉树的层序遍历

给你一个二叉树，请你返回其按 层序遍历 得到的节点值。 （即逐层地，从左到右访问所有节点）。

/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode() {}
 *     TreeNode(int val) { this.val = val; }
 *     TreeNode(int val, TreeNode left, TreeNode right) {
 *         this.val = val;
 *         this.left = left;
 *         this.right = right;
 *     }
 * }
 */
class Solution {
    List<List<Integer>> ans = new ArrayList<List<Integer>>();
    public List<List<Integer>> levelOrder(TreeNode root) {
        bfs(root,0);
        return ans;
    }
    //前序遍历
    private void bfs(TreeNode root,int level){
        if(root == null){ 
            return;
        }
        //level表示层数，层数和集合的尺寸相等表示在当前层
        if(level == ans.size()){
            ans.add(new ArrayList<Integer>());      
        }
        ans.get(level).add(root.val);//当前层的值添加到集合中
        bfs(root.left,level+1);
        bfs(root.right,level+1);
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35

103.二叉树的锯齿形层序遍历

给定一个二叉树，返回其节点值的锯齿形层序遍历。（即先从左往右，再从右往左进行下一层遍历，以此类推，层与层之间交替进行）。

/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode() {}
 *     TreeNode(int val) { this.val = val; }
 *     TreeNode(int val, TreeNode left, TreeNode right) {
 *         this.val = val;
 *         this.left = left;
 *         this.right = right;
 *     }
 * }
 */
class Solution {
    List<List<Integer>> ans = new ArrayList<List<Integer>>();
    public List<List<Integer>> zigzagLevelOrder(TreeNode root) {
        bfs(root,0);
        return ans;
    }
    //前序遍历
    private void bfs(TreeNode root,int level){
        if(root == null){ 
            return;
        }
        //level表示层数，层数和集合的尺寸相等表示在当前层
        if(level == ans.size()){
            ans.add(new LinkedList<Integer>());      
        }

        //当前层的值添加到集合中
        if((level & 1) == 1 ){
            ans.get(level).add(0,root.val);
        }else{
            ans.get(level).add(root.val);
        }

        bfs(root.left,level+1);
        bfs(root.right,level+1);
    }
}

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43

107. 二叉树的层序遍历 II

给定一个二叉树，返回其节点值自底向上的层序遍历。 （即按从叶子节点所在层到根节点所在的层，逐层从左向右遍历）

/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode() {}
 *     TreeNode(int val) { this.val = val; }
 *     TreeNode(int val, TreeNode left, TreeNode right) {
 *         this.val = val;
 *         this.left = left;
 *         this.right = right;
 *     }
 * }
 */
class Solution {
    List<List<Integer>> ans = new ArrayList<List<Integer>>();
    public List<List<Integer>> levelOrderBottom(TreeNode root) {
        bfs(root,0);
        Collections.reverse(ans);//反转指定列表中元素的顺序。 
        return ans;
    }
    //前序遍历
    private void bfs(TreeNode root,int level){
        if(root == null){ 
            return;
        }
        //level表示层数，层数和集合的尺寸相等表示在当前层
        if(level == ans.size()){
            ans.add(new ArrayList<Integer>());      
        }
        ans.get(level).add(root.val);//当前层的值添加到集合中
        bfs(root.left,level+1);
        bfs(root.right,level+1);
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36

1.5 贪心算法

1.5.1 简单题目

409.最长回文子串

给定一个包含大写字母和小写字母的字符串，找到通过这些字母构造成的最长的回文串。
在构造过程中，请注意区分大小写。比如 “Aa” 不能当做一个回文字符串。
注意:
假设字符串的长度不会超过 1010。

class Solution {
    public int longestPalindrome(String s) {
        /*
            使用一个长度为 128 的数组，存储每个字符出现的次数，因为字符的 ASCII 值的范围为 [0, 128)。
            而由于题目中保证了给定的字符串 s 只包含大小写字母，因此我们也可以使用哈希映射（HashMap）来存储每个字符出现的次数
        */ 
        int[] count = new int[128];
        for(int i=0;i<s.length();++i){
            char c = s.charAt(i);
            count[c]++; 
        } 
        int ans = 0;//保存最后结果
        for(int num : count){
            ans += num/2*2;
            if(num%2 == 1 && ans%2 == 0){//某个字符出现奇数次时，结果加1，只加一次
                ans += 1;
            }
        }
        return ans;
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21

455.分发饼干

假设你是一位很棒的家长，想要给你的孩子们一些小饼干。但是，每个孩子最多只能给一块饼干。

对每个孩子 i，都有一个胃口值 g[i]，这是能让孩子们满足胃口的饼干的最小尺寸；并且每块饼干 j，都有一个尺寸 s[j] 。如果 s[j] >= g[i]，我们可以将这个饼干 j 分配给孩子 i ，这个孩子会得到满足。你的目标是尽可能满足越多数量的孩子，并输出这个最大数值。

class Solution {
    public int findContentChildren(int[] g, int[] s) {
        //排序
        Arrays.sort(g);
        Arrays.sort(s);
        
        int i=0;
        int j=0;
        while(i<g.length && j<s.length){
            if(g[i]<=s[j]){//饼干大于孩子的胃口时，才能喂饱
                i++;
            }
            j++;
        }
        return i;
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17

561.数组拆分I

给定长度为 2n 的整数数组 nums ，你的任务是将这些数分成 n 对, 例如 (a1, b1), (a2, b2), …, (an, bn) ，使得从 1 到 n 的 min(ai, bi) 总和最大。

返回该 最大总和 。

/*
 * 一个朴素（贪心）的理解：
 *
 * 假设排完序的结果为a1<=b1<=a2<=b2<=...<=an<=bn
 * 那么a1应该跟谁一组呢？
 *
 * a1作为全局最小值，无论跟谁一组a1都会被累加进答案，
 * 相反，a1的搭档会被永久排除。
 * 既然如此，莫不如排除一个较小的数，即给a1找一个“最小的搭档”b1。
 *
 * 当a1、b1被处理之后，a2同理分析。
 * 所以，最终选择a1,a2,...,an会得到最好的结果。
 */
 class Solution {
    public int arrayPairSum(int[] nums) {
        Arrays.sort(nums);
        int ans = 0;
        for (int i = 0; i < nums.length; i += 2) {
            ans += nums[i];
        }
        return ans;
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23

605.种花问题

假设有一个很长的花坛，一部分地块种植了花，另一部分却没有。可是，花不能种植在相邻的地块上，它们会争夺水源，两者都会死去。

给你一个整数数组 flowerbed 表示花坛，由若干 0 和 1 组成，其中 0 表示没种植花，1 表示种植了花。另有一个数 n ，能否在不打破种植规则的情况下种入 n 朵花？能则返回 true ，不能则返回 false。
1 <= flowerbed.length <= 2 * 104
flowerbed[i] 为 0 或 1
flowerbed 中不存在相邻的两朵花
0 <= n <= flowerbed.length

class Solution {
    public boolean canPlaceFlowers(int[] flowerbed, int n) {
     	/*
            思路：
                考虑花坛长度为1的情况
                考虑边缘问题
         */
        int num = 0;//用来记录能种花的数量
        if(flowerbed.length == 1 && flowerbed[0]==0){
            num++;
            return num>=n;
        }else if(flowerbed.length == 1 && flowerbed[0]==1){
            return num>=n;
        }
        
        if(flowerbed[0]==0 && flowerbed[1]==0){//考虑左边缘
            flowerbed[0] = 1;
            num++;
        }
        if(flowerbed[flowerbed.length-1]==0 && flowerbed[flowerbed.length-2]==0){//考虑右边缘
            flowerbed[flowerbed.length-1] = 1;
            num++;
        }

        for(int i=2;i<flowerbed.length-2;){
            if(flowerbed[i-1]==0 && flowerbed[i]==0 && flowerbed[i+1]==0){
                flowerbed[i]=1;
                num++;
                i=i+2;
            }else{
                ++i;
            }
        }
        return num>=n;
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36

1.5.2 中等题目

45.跳跃游戏II

给你一个非负整数数组 nums ，你最初位于数组的第一个位置。

数组中的每个元素代表你在该位置可以跳跃的最大长度。

你的目标是使用最少的跳跃次数到达数组的最后一个位置。

假设你总是可以到达数组的最后一个位置

1 <= nums.length <= 104
0 <= nums[i] <= 1000

/*
	贪心算法：每次选择跳的更远的位置
*/
class Solution {
    public int jump(int[] nums) {
        int end = 0;//当前所能覆盖最远距离下标
        int steps= 0;
        int maxPositiom = 0;//用来记录下一步所能覆盖的最大范围的下标
        for(int i=0;i<nums.length-1;i++){
            maxPositiom = Math.max(maxPositiom,i+nums[i]);//找到跳的更远的位置 
            if(i==end){//遇到边界，就更新边界，并且步数加一
                steps++;
                end = maxPositiom;
            }
        }
        return steps;
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18

46.跳跃游戏

给定一个非负整数数组 nums ，你最初位于数组的 第一个下标 。
数组中的每个元素代表你在该位置可以跳跃的最大长度。
判断你是否能够到达最后一个下标。

1 <= nums.length <= 3 * 104
0 <= nums[i] <= 105

class Solution {
    public boolean canJump(int[] nums) {
        int rightMost = 0;//用来表示往右跳的最大距离
        for(int i=0;i<nums.length;++i){
            if(i<=rightMost){
                rightMost = Math.max(rightMost,i+nums[i]);
                if(rightMost>=nums.length-1){
                    return true;
                }
            }
        }    
        return false;
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14

134.加油站

在一条环路上有 N 个加油站，其中第 i 个加油站有汽油 gas[i] 升。

你有一辆油箱容量无限的的汽车，从第 i 个加油站开往第 i+1 个加油站需要消耗汽油 cost[i] 升。你从其中的一个加油站出发，开始时油箱为空。

如果你可以绕环路行驶一周，则返回出发时加油站的编号，否则返回 -1。

说明:

如果题目有解，该答案即为唯一答案。
输入数组均为非空数组，且长度相同。
输入数组中的元素均为非负数。

class Solution {
    public int canCompleteCircuit(int[] gas, int[] cost) {
        int n= gas.length;
        int lack = 0;//缺的油
        int newStart = 0;//记录新的开始点
        int saveGas = 0;//剩的油
        for(int i=0;i<n;++i){
            saveGas += gas[i]-cost[i];
            if(saveGas<0){//说明不能到达下个加油站
                newStart = i+1;
                lack += -saveGas;
                saveGas = 0;//因为开始新的起点，所以剩余的油要清0
            }
        }
        return saveGas >= lack ? newStart : -1;
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17

1.5.3 困难题目

135.分发糖果

老师想给孩子们分发糖果，有 N 个孩子站成了一条直线，老师会根据每个孩子的表现，预先给他们评分。

你需要按照以下要求，帮助老师给这些孩子分发糖果：

每个孩子至少分配到 1 个糖果。
评分更高的孩子必须比他两侧的邻位孩子获得更多的糖果。
那么这样下来，老师至少需要准备多少颗糖果呢？

class Solution {
    public int candy(int[] ratings) {
        //用来保存每个人的糖果数量
        int[] candy = new int[ratings.length];

        //每个人最少有一个糖果
        for(int i=0;i<ratings.length;++i){
            candy[i] = 1;
        }
        //从左往右
        for(int i=1;i<ratings.length;++i){
            if(ratings[i]>ratings[i-1]){
                candy[i] = candy[i-1]+1;
            }
        }
        //从右往左
        for(int i=ratings.length-2;i>=0;--i){
            if(ratings[i]>ratings[i+1]){
                candy[i] = Math.max(candy[i],candy[i+1] +1);
            }
        }
        int count = 0;
        for(int i=0;i<candy.length;++i){
            count += candy[i];
        }
        return count;

    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29

1.6 分治

1.6.1 简单题目

108. 将有序数组转换为二叉搜索树

给你一个整数数组 nums ，其中元素已经按 升序 排列，请你将其转换为一棵 高度平衡 二叉搜索树。

高度平衡 二叉树是一棵满足「每个节点的左右两个子树的高度差的绝对值不超过 1 」的二叉树。

1 <= nums.length <= 104
-104 <= nums[i] <= 104
nums 按 严格递增 顺序排列

/*
	分而治之
*/
/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode() {}
 *     TreeNode(int val) { this.val = val; }
 *     TreeNode(int val, TreeNode left, TreeNode right) {
 *         this.val = val;
 *         this.left = left;
 *         this.right = right;
 *     }
 * }
 */
class Solution {
    public TreeNode sortedArrayToBST(int[] nums) {
        return divide(nums,0,nums.length-1);
    }
    //前序遍历
    private TreeNode divide(int[] nums,int left,int right){
        if(left > right){
            return null;
        }
        int mid = left+(right-left)/2;// 总是选择中间位置左边的数字作为根节点
        TreeNode root = new TreeNode(nums[mid]);
        root.left = divide(nums,left,mid-1);
        root.right = divide(nums,mid+1,right);
        return root;
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34

1.6.2 中等题目

105. 从前序与中序遍历序列构造二叉树

给定一棵树的前序遍历 preorder 与中序遍历 inorder。请构造二叉树并返回其根节点。
1 <= preorder.length <= 3000
inorder.length == preorder.length
-3000 <= preorder[i], inorder[i] <= 3000
preorder 和 inorder 均无重复元素
inorder 均出现在 preorder
preorder 保证为二叉树的前序遍历序列
inorder 保证为二叉树的中序遍历序列

/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode() {}
 *     TreeNode(int val) { this.val = val; }
 *     TreeNode(int val, TreeNode left, TreeNode right) {
 *         this.val = val;
 *         this.left = left;
 *         this.right = right;
 *     }
 * }
 */
class Solution {
    public TreeNode buildTree(int[] preorder, int[] inorder) {
        return divide(preorder,0,preorder.length-1,inorder,0,inorder.length-1);
    }
    private TreeNode divide(int[] preorder,int l1,int r1,int[] inorder,int l2,int r2){
        if(l1>r1 || l2> r2){
            return null;
        }
        
        int mid = l2;
        while(inorder[mid] != preorder[l1]){
            //找到中序遍历中的根节点，则根节点的左边是左子节点，右边是右子节点
            ++mid;
        }
        TreeNode root = new TreeNode(preorder[l1]);
        root.left = divide(preorder,l1+1,l1+mid-l2,inorder,l2,mid-1);
        root.right = divide(preorder,l1+mid-l2+1,r1,inorder,mid+1,r2);
        return root;
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35

106. 从中序与后序遍历序列构造二叉树

根据一棵树的中序遍历与后序遍历构造二叉树。

/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode() {}
 *     TreeNode(int val) { this.val = val; }
 *     TreeNode(int val, TreeNode left, TreeNode right) {
 *         this.val = val;
 *         this.left = left;
 *         this.right = right;
 *     }
 * }
 */
class Solution {
    public TreeNode buildTree(int[] inorder, int[] postorder) {
         return divide(postorder,0,postorder.length-1,inorder,0,inorder.length-1);
    }
    private TreeNode divide(int[] postorder,int l1,int r1,int[] inorder,int l2,int r2){
        if(l1>r1 || l2> r2){
            return null;
        }
        
        int mid = l2;
        while(inorder[mid] != postorder[r1]){
            //找到中序遍历中的根节点，则根节点的左边是左子节点，右边是右子节点
            ++mid;
        }
        TreeNode root = new TreeNode(postorder[r1]);
        root.left = divide(postorder,l1,l1+mid-l2-1,inorder,l2,mid-1);
        root.right = divide(postorder,l1+mid-l2,r1-1,inorder,mid+1,r2);
        return root;
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35

148. 排序链表

给你链表的头结点 head ，请将其按 升序 排列并返回 排序后的链表 。

进阶：

你可以在 O(n log n) 时间复杂度和常数级空间复杂度下，对链表进行排序吗？
链表中节点的数目在范围 [0, 5 * 104] 内
-105 <= Node.val <= 105

/**
 * Definition for singly-linked list.
 * public class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode() {}
 *     ListNode(int val) { this.val = val; }
 *     ListNode(int val, ListNode next) { this.val = val; this.next = next; }
 * }
 */
class Solution {
    public ListNode sortList(ListNode head) {
        return divide(head,null);
    }
    //拆分链表
    private ListNode divide(ListNode head,ListNode tail){
        if(head == null){
            return head;
        }
        if(head.next == tail){
            head.next = null;
            return head;
        }

        ListNode midNode = searchMidNode(head,tail);
        ListNode list1 = divide(head,midNode);
        ListNode list2 = divide(midNode,tail);
        ListNode list = merge(list1,list2);
        return list;
    }
    //寻找链表的中点（快慢指针）
    private ListNode searchMidNode(ListNode head,ListNode tail){
        ListNode slow = head;
        ListNode fast = head;
        while(fast!=tail){
            slow = slow.next;
            fast = fast.next;
            if(fast!=tail){
                fast=fast.next;
            }
        }
        return slow;
    }
    //合并链表
    private ListNode merge(ListNode head1,ListNode head2){
        ListNode dummy = new ListNode(0);
        ListNode cur = dummy;
        ListNode t1 = head1;
        ListNode t2 = head2;
        while(t1!=null && t2!=null){
            if(t1.val <= t2.val){
                cur.next = t1;
                t1 = t1.next;
            }else{
                cur.next = t2;
                t2 =t2.next;
            }
            cur = cur.next;
        }
        cur.next = t1 == null ? t2 : t1;
        return dummy.next;
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63

1.7二分查找

1.7.1 简单题目

35. 搜索插入位置

给定一个排序数组和一个目标值，在数组中找到目标值，并返回其索引。如果目标值不存在于数组中，返回它将会被按顺序插入的位置。
请必须使用时间复杂度为 O(log n) 的算法。
1 <= nums.length <= 104
-104 <= nums[i] <= 104
nums 为无重复元素的升序排列数组
-104 <= target <= 104

class Solution {
    public int searchInsert(int[] nums, int target) {
        if(target < nums[0]){
            return 0;
        }
        if(target > nums[nums.length-1]){
            return nums.length;
        }
        int left = 0;
        int right = nums.length-1; 
        while(left<=right){
            int mid = left+(right-left)/2;//防止内存溢出
            if(target == nums[mid]){
                return mid;
            }else if(target<nums[mid]){
                right = mid-1;
            }else{
                left = mid+1;
            }
        }
        return left;   
    }
}

/*
	代码简化
*/
class Solution {
    public int searchInsert(int[] nums, int target) {
        int left = 0;
        int right = nums.length-1;
        int ans = nums.length;
        while(left<=right){
            int mid = left+(right-left)/2;
            if(target<=nums[mid]){
                ans = mid;
                right = mid-1;
            }else{
                left = mid+1;
            }
        }
        return ans; 
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45

69. x 的平方根

实现 int sqrt(int x) 函数。
计算并返回 x 的平方根，其中 x 是非负整数。
由于返回类型是整数，结果只保留整数的部分，小数部分将被舍去。

class Solution {
    public int mySqrt(int x) {
        int l=0;
        int h=x;
        int ans = -1;
        while(l<=h){
            int mid = l+(r-l)/2;
            if((long)mid*mid <= x){
                ans = mid;
                l= mid+1;
            }else{
                h=mid-1;
            }
        }
        return ans;
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17

278. 第一个错误的版本

你是产品经理，目前正在带领一个团队开发新的产品。不幸的是，你的产品的最新版本没有通过质量检测。由于每个版本都是基于之前的版本开发的，所以错误的版本之后的所有版本都是错的。

假设你有 n 个版本 [1, 2, …, n]，你想找出导致之后所有版本出错的第一个错误的版本。

你可以通过调用 bool isBadVersion(version) 接口来判断版本号 version 是否在单元测试中出错。实现一个函数来查找第一个错误的版本。你应该尽量减少对调用 API 的次数。

1 <= bad <= n <= 231 - 1

/* The isBadVersion API is defined in the parent class VersionControl.
      boolean isBadVersion(int version); */

public class Solution extends VersionControl {
    public int firstBadVersion(int n) {
        int l = 1;
        int r = n;
        while(l<=r){
            int mid = l+(r-l)/2;
            if(isBadVersion(mid)){
                r = mid-1;
            }else{
                l = mid+1;
            }      
        }
        return l;
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18

367. 有效的完全平方数

给定一个 正整数 num ，编写一个函数，如果 num 是一个完全平方数，则返回 true ，否则返回 false 。

进阶：不要 使用任何内置的库函数，如 sqrt 。

1 <= num <= 2^31 - 1

class Solution {
    public boolean isPerfectSquare(int num) {
        if(num < 2){
            return true;
        }
        long l = 2;
        long r = num/2;
        while(l<=r){
            long mid = l+(r-l)/2;
            if(mid*mid == num){
                return true;
            }else if(mid*mid > num){
                r = mid - 1;
            }else{
                l = mid + 1;
            }
        }
        return false;
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20

1.7.2 中等题目

33. 搜索旋转排序数组

整数数组 nums 按升序排列，数组中的值 互不相同 。

在传递给函数之前，nums 在预先未知的某个下标 k（0 <= k < nums.length）上进行了 旋转，使数组变为 [nums[k], nums[k+1], …, nums[n-1], nums[0], nums[1], …, nums[k-1]]（下标 从 0 开始 计数）。例如， [0,1,2,4,5,6,7] 在下标 3 处经旋转后可能变为 [4,5,6,7,0,1,2] 。

给你 旋转后 的数组 nums 和一个整数 target ，如果 nums 中存在这个目标值 target ，则返回它的下标，否则返回 -1 。

1 <= nums.length <= 5000
-10^4 <= nums[i] <= 10 ^4
nums 中的每个值都 独一无二
题目数据保证 nums 在预先未知的某个下标上进行了旋转
-10^4 <= target <= 10 ^4

class Solution {
    public int search(int[] nums, int target) {
        int n = nums.length;
        if(n == 0){
            return -1;
        }
        if(n == 1){
            return nums[0] == target ? 0:-1;
        }
        int l = 0;
        int r = n-1;
        
        while(l<=r){
            int mid = (l+r)/2;
            if(target == nums[mid]){
                return mid;
            }
            if(nums[0]<=nums[mid]){//左边有序
                if(target>=nums[0] && target<nums[mid]){
                    r = mid-1;
                }else{
                    l = mid+1;
                }
            }else{//右边有序
                if(target>nums[mid] && target<=nums[n-1]){
                    l = mid+1;
                }else{
                    r = mid-1;
                }
            }
        }
        return -1;
    }
   
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35

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

给定一个按照升序排列的整数数组 nums，和一个目标值 target。找出给定目标值在数组中的开始位置和结束位置。

如果数组中不存在目标值 target，返回 [-1, -1]。

进阶：

你可以设计并实现时间复杂度为 O(log n) 的算法解决此问题吗？
0 <= nums.length <= 105
-109 <= nums[i] <= 109
nums 是一个非递减数组
-109 <= target <= 109

class Solution {
    public int[] searchRange(int[] nums, int target) {
        if(nums.length == 0){
            return new int[]{-1,-1};
        }
        int firstPosition = findFirstPosition(nums,target);
        if(firstPosition == -1){
            return new int[]{-1,-1};
        }
        int lastPosition = findLastPosition(nums,target);
        return new int[]{firstPosition,lastPosition};
    }
	
	//找第一个点
    public int findFirstPosition(int[] nums,int target){
        if(target < nums[0] || target > nums[nums.length-1]){
            return -1;
        }
        int left=0;
        int ritht = nums.length-1;
        int ans = 0;
        while(left<=ritht){
            int mid = (left+ritht)/2;
            if(target<=nums[mid]){
                ans = mid;
                ritht = mid-1;
            }else{
                left = mid+1;
            }
        }
        return nums[ans] == target ? ans : -1;
    }
	
	//找最后一个点
    public int findLastPosition(int[] nums,int target){
        if(target < nums[0] || target > nums[nums.length-1]){
            return -1;
        }
        int left=0;
        int ritht = nums.length-1;
        int ans = 0;
        while(left<=ritht){
            int mid = (left+ritht+1)/2;
            if(target<nums[mid]){
                ritht = mid-1;
            }else{
                ans = mid;
                left = mid+1;
            }
        }
        return nums[ans] == target ? ans : -1;
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53

74. 搜索二维矩阵

编写一个高效的算法来判断 m x n 矩阵中，是否存在一个目标值。该矩阵具有如下特性：

每行中的整数从左到右按升序排列。
每行的第一个整数大于前一行的最后一个整数。

m == matrix.length
n == matrix[i].length
1 <= m, n <= 100
-104 <= matrix[i][j], target <= 104

class Solution {
    public boolean searchMatrix(int[][] matrix, int target) {
        int m = matrix.length;
        int n = matrix[0].length;
        int left = 0;
        int right = m*n-1;
        while(left<=right){
            int mid = left + (right-left)/2;
            if(target == matrix[mid/n][mid%n]){
                return true;
            }else if(target > matrix[mid/n][mid%n]){
                left = mid+1;
            }else{
                right = mid-1;
            }
        }
        return false;
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19

81. 搜索旋转排序数组 II

已知存在一个按非降序排列的整数数组 nums ，数组中的值不必互不相同。

在传递给函数之前，nums 在预先未知的某个下标 k（0 <= k < nums.length）上进行了 旋转 ，使数组变为 [nums[k], nums[k+1], …, nums[n-1], nums[0], nums[1], …, nums[k-1]]（下标 从 0 开始 计数）。例如， [0,1,2,4,4,4,5,6,6,7] 在下标 5 处经旋转后可能变为 [4,5,6,6,7,0,1,2,4,4] 。

给你 旋转后 的数组 nums 和一个整数 target ，请你编写一个函数来判断给定的目标值是否存在于数组中。如果 nums 中存在这个目标值 target ，则返回 true ，否则返回 false 。

1 <= nums.length <= 5000
-104 <= nums[i] <= 104
题目数据保证 nums 在预先未知的某个下标上进行了旋转
-104 <= target <= 104

class Solution {
    public boolean search(int[] nums, int target) {
        if(nums.length == 1){
            return nums[0] == target;
        }
        int left = 0;
        int right = nums.length-1;

        while(left <= right){
            int mid = left + (right-left)/2;
            if(target == nums[mid]){
                return true;
            }else if(nums[left]< nums[mid]){//左边有序
                if(target>= nums[left] && target < nums[mid]){
                    right = mid-1;
                }else{
                    left = mid+1;
                }
            }else if(nums[mid] < nums[left]){//右边有序
                if(target>nums[mid] && target<=nums[right]){
                    left = mid+1; 
                }else{
                    right = mid-1;
                }
            }else if(nums[mid] == nums[left]){
                ++left;
            }           
        }
        return false;
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31

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

已知一个长度为 n 的数组，预先按照升序排列，经由 1 到 n 次 旋转 后，得到输入数组。例如，原数组 nums = [0,1,2,4,5,6,7] 在变化后可能得到：
若旋转 4 次，则可以得到 [4,5,6,7,0,1,2]
若旋转 7 次，则可以得到 [0,1,2,4,5,6,7]
注意，数组 [a[0], a[1], a[2], …, a[n-1]] 旋转一次 的结果为数组 [a[n-1], a[0], a[1], a[2], …, a[n-2]] 。

给你一个元素值 互不相同 的数组 nums ，它原来是一个升序排列的数组，并按上述情形进行了多次旋转。请你找出并返回数组中的 最小元素 。

n == nums.length
1 <= n <= 5000
-5000 <= nums[i] <= 5000
nums 中的所有整数 互不相同
nums 原来是一个升序排序的数组，并进行了 1 至 n 次旋转

class Solution {
    public int findMin(int[] nums) {
        int l = 0;
        int r = nums.length-1;
        while(l<r){
            int mid = l+(r-l)/2;
            if(nums[mid]<nums[r]){
                r = mid;
            }else {
                l = mid + 1;
            }
        }
        return nums[l];
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15

162. 寻找峰值

峰值元素是指其值大于左右相邻值的元素。
给你一个输入数组 nums，找到峰值元素并返回其索引。数组可能包含多个峰值，在这种情况下，返回 任何一个峰值 所在位置即可。
你可以假设 nums[-1] = nums[n] = -∞ 。
1 <= nums.length <= 1000
-231 <= nums[i] <= 231 - 1
对于所有有效的 i 都有 nums[i] != nums[i + 1]

class Solution {
    public int findPeakElement(int[] nums) {
        int l = 0;
        int r = nums.length-1;
        while(l<r){
            int mid = l+(r-l)/2;
            if(nums[mid]>nums[mid+1]){
                r = mid;
            }else{
                l = mid+1;
            }
        }
        return l;
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15

222. 完全二叉树的节点个数

给你一棵 完全二叉树 的根节点 root ，求出该树的节点个数。

完全二叉树 的定义如下：在完全二叉树中，除了最底层节点可能没填满外，其余每层节点数都达到最大值，并且最下面一层的节点都集中在该层最左边的若干位置。若最底层为第 h 层，则该层包含 1~ 2h 个节点。
树中节点的数目范围是[0, 5 * 104]
0 <= Node.val <= 5 * 104
题目数据保证输入的树是 完全二叉树

/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode() {}
 *     TreeNode(int val) { this.val = val; }
 *     TreeNode(int val, TreeNode left, TreeNode right) {
 *         this.val = val;
 *         this.left = left;
 *         this.right = right;
 *     }
 * }
 */
class Solution {
    /**
        完全二叉树的高度可以直接通过不断地访问左子树就可以获取
        判断左右子树的高度: 
        如果相等说明左子树是满二叉树, 然后进一步判断右子树的节点数(最后一层最后出现的节点必然在右子树中)
        如果不等说明右子树是深度小于左子树的满二叉树, 然后进一步判断左子树的节点数(最后一层最后出现的节点必然在左子树中)
    **/
    public int countNodes(TreeNode root) {
        if(root==null){
            return 0;
        }
        int leftDepth = getDepth(root.left);
        int rightDepth = getDepth(root.right);
        if(leftDepth == rightDepth){
            return (1<<leftDepth) + countNodes(root.right);// 1(根节点) + (1 << ld)-1(左完全左子树节点数) + 右子树节点数量
        }else{
            return (1<<rightDepth) + countNodes(root.left);//1(根节点) + (1 << rd)-1(右完全右子树节点数) + 左子树节点数量
        }
    }
    //计算树的深度
    private int getDepth(TreeNode root){
        int depth = 0;
        while(root != null){
            depth++;
            root = root.left;    
        }
        return depth;
    } 
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44

1.8 快速选择

1.8.1 中等题目

215.数组中的第K个最大元素

给定整数数组 nums 和整数 k，请返回数组中第 k 个最大的元素。

请注意，你需要找的是数组排序后的第 k 个最大的元素，而不是第 k 个不同的元素。
1 <= k <= nums.length <= 104
-104 <= nums[i] <= 104

class Solution {
    public int findKthLargest(int[] nums, int k) {
        quikcSort(nums,0,nums.length-1);
        return nums[nums.length-k];
    }
    //快速排序
    private void quikcSort(int[] nums,int l,int r){
        if(l<r){
            int i = l;
            int j = r;
            int x = nums[l];//挖坑
            while(i<j){
                while(i<j && nums[j]>=x){//从右往左找大于x的值
                    j--;
                }
                if(i<j){
                    nums[i++] = nums[j]; 
                }
                while(i<j && nums[i]<x){//从左往右找小于x的值
                    i++;
                }
                if(i<j){
                    nums[j--] = nums[i];
                }
            }
            nums[i] = x;
            quikcSort(nums,l,i-1);
            quikcSort(nums,i+1,r);
        }
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31

2.数据结构

2.1 哈希表

2.1.1 简单题目

13.罗马数字转整数

罗马数字包含以下七种字符: I， V， X， L，C，D 和 M。

字符          数值
I             1
V             5
X             10
L             50
C             100
D             500
M             1000
1
2
3
4
5
6
7
8

例如， 罗马数字 2 写做 II ，即为两个并列的 1。12 写做 XII ，即为 X + II 。 27 写做 XXVII, 即为 XX + V + II 。

通常情况下，罗马数字中小的数字在大的数字的右边。但也存在特例，例如 4 不写做 IIII，而是 IV。数字 1 在数字 5 的左边，所表示的数等于大数 5 减小数 1 得到的数值 4 。同样地，数字 9 表示为 IX。这个特殊的规则只适用于以下六种情况：

I 可以放在 V (5) 和 X (10) 的左边，来表示 4 和 9。
X 可以放在 L (50) 和 C (100) 的左边，来表示 40 和 90。
C 可以放在 D (500) 和 M (1000) 的左边，来表示 400 和 900。
给定一个罗马数字，将其转换成整数。输入确保在 1 到 3999 的范围内。

1 <= s.length <= 15
s 仅含字符 (‘I’, ‘V’, ‘X’, ‘L’, ‘C’, ‘D’, ‘M’)
题目数据保证 s 是一个有效的罗马数字，且表示整数在范围 [1, 3999] 内
题目所给测试用例皆符合罗马数字书写规则，不会出现跨位等情况。
IL 和 IM 这样的例子并不符合题目要求，49 应该写作 XLIX，999 应该写作 CMXCIX 。
关于罗马数字的详尽书写规则，可以参考 罗马数字 - Mathematics 。

class Solution {
    Map<Character, Integer> symbolValues = new HashMap<Character, Integer>() {{
        put('I', 1);
        put('V', 5);
        put('X', 10);
        put('L', 50);
        put('C', 100);
        put('D', 500);
        put('M', 1000);
    }};

    public int romanToInt(String s) {
        int ans = 0;
        for(int i=0;i<s.length();++i){
            if(i<s.length()-1 && symbolValues.get(s.charAt(i))<symbolValues.get(s.charAt(i+1))){
                ans -= symbolValues.get(s.charAt(i));
            }else{
                ans += symbolValues.get(s.charAt(i));
            }
        }
        return ans;
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23

205.同构字符串

给定两个字符串 s 和 t，判断它们是否是同构的。

如果 s 中的字符可以按某种映射关系替换得到 t ，那么这两个字符串是同构的。

每个出现的字符都应当映射到另一个字符，同时不改变字符的顺序。不同字符不能映射到同一个字符上，相同字符只能映射到同一个字符上，字符可以映射到自己本身。

可以假设 s 和 t 长度相同。

class Solution {
    public boolean isIsomorphic(String s, String t) {
        Map<Character,Character> map1 = new HashMap<Character,Character>();
        Map<Character,Character> map2 = new HashMap<Character,Character>();
        for(int i=0;i<s.length();++i){
            char c1  = s.charAt(i);
            char c2  = t.charAt(i);
            if(map1.containsKey(c1) && map1.get(c1)!=c2 || map2.containsKey(c2) && map2.get(c2)!=c1){
                return false;
            }
            map1.put(c1,c2);
            map2.put(c2,c1);
        }
        return true;
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16

217.存在重复元素

给定一个整数数组，判断是否存在重复元素。

如果存在一值在数组中出现至少两次，函数返回 true 。如果数组中每个元素都不相同，则返回 false 。

class Solution {
    public boolean containsDuplicate(int[] nums) {
        Set<Integer> set = new HashSet<Integer>();
        for (int x : nums) {
            if (!set.add(x)) {
                return true;
            }
        }
        return false;
    }
}

1
2
3
4
5
6
7
8
9
10
11
12

219. 存在重复元素 II

给定一个整数数组和一个整数 k，判断数组中是否存在两个不同的索引 i 和 j，使得 nums [i] = nums [j]，并且 i 和 j 的差的 绝对值 至多为 k。

class Solution {
    public boolean containsNearbyDuplicate(int[] nums, int k) {
        Set<Integer> set = new HashSet<>();
        for (int i = 0; i < nums.length; ++i) {
            if (set.contains(nums[i])) return true;
            set.add(nums[i]);
            if (set.size() > k) {
                set.remove(nums[i - k]);
            }
        }
        return false;
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13

242. 有效的字母异位词

给定两个字符串 s 和 t ，编写一个函数来判断 t 是否是 s 的字母异位词。

注意：若 s 和 t 中每个字符出现的次数都相同，则称 s 和 t 互为字母异位词。
1 <= s.length, t.length <= 5 * 104
s 和 t 仅包含小写字母

class Solution {
    public boolean isAnagram(String s, String t) {
        if (s.length() != t.length()) {
            return false;
        }
        Map<Character, Integer> table = new HashMap<Character, Integer>();
        for (int i = 0; i < s.length(); i++) {
            char ch = s.charAt(i);
            table.put(ch, table.getOrDefault(ch, 0) + 1);
        }
        for (int i = 0; i < t.length(); i++) {
            char ch = t.charAt(i);
            table.put(ch, table.getOrDefault(ch, 0) - 1);
            if (table.get(ch) < 0) {
                return false;
            }
        }
        return true;
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20

2.1.2 中等题目

12. 整数转罗马数字

12. 整数转罗马数字
    罗马数字包含以下七种字符： I， V， X， L，C，D 和 M。

字符 数值
I 1
V 5
X 10
L 50
C 100
D 500
M 1000
例如， 罗马数字 2 写做 II ，即为两个并列的 1。12 写做 XII ，即为 X + II 。 27 写做 XXVII, 即为 XX + V + II 。

通常情况下，罗马数字中小的数字在大的数字的右边。但也存在特例，例如 4 不写做 IIII，而是 IV。数字 1 在数字 5 的左边，所表示的数等于大数 5 减小数 1 得到的数值 4 。同样地，数字 9 表示为 IX。这个特殊的规则只适用于以下六种情况：

I 可以放在 V (5) 和 X (10) 的左边，来表示 4 和 9。
X 可以放在 L (50) 和 C (100) 的左边，来表示 40 和 90。
C 可以放在 D (500) 和 M (1000) 的左边，来表示 400 和 900。
给你一个整数，将其转为罗马数字。
1 <= num <= 3999

class Solution {
    private int[] values= {1000, 900, 500, 400, 100, 90, 50, 40, 10, 9, 5, 4, 1};
    private String[] str = {"M", "CM", "D", "CD", "C", "XC", "L", "XL", "X", "IX", "V", "IV", "I"};
    public String intToRoman(int num) {
        
        StringBuilder sb = new StringBuilder();
        for(int i=0;i<values.length;++i){
            int v = values[i];
            String s = str[i];
            while(num>=v){
                num -= v;
                sb.append(s);
            }
        }
        return sb.toString();
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17

49. 字母异位词分组

给你一个字符串数组，请你将 字母异位词 组合在一起。可以按任意顺序返回结果列表。

字母异位词 是由重新排列源单词的字母得到的一个新单词，所有源单词中的字母都恰好只用一次。

1 <= strs.length <= 104
0 <= strs[i].length <= 100
strs[i] 仅包含小写字母

class Solution {
    public List<List<String>> groupAnagrams(String[] strs) {
         HashMap<String,ArrayList<String>> map=new HashMap<>();
         for(String s : strs){
             char[]  ch = s.toCharArray();//字符串转为字符数组
             Arrays.sort(ch);
             String key = String.valueOf(ch);
             if(!map.containsKey(key)){
                 map.put(key,new ArrayList<>());
             }
             map.get(key).add(s);
         }
         return new ArrayList(map.values());
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15

2.2 栈

2.2.1 简单题目

20. 有效的括号

给定一个只包括 ‘(’，’)’，’{’，’}’，’[’，’]’ 的字符串 s ，判断字符串是否有效。

有效字符串需满足：

左括号必须用相同类型的右括号闭合。
左括号必须以正确的顺序闭合。

1 <= s.length <= 104
s 仅由括号 ‘()[]{}’ 组成

class Solution {
    public boolean isValid(String s) {
        int n = s.length();
        if(n % 2 == 1){
            return false;
        }

        Map<Character,Character> pairs = new HashMap<Character,Character>(){{
            put(')','(');
            put(']','[');
            put('}','{');
        }};

        Deque<Character> stack = new LinkedList<Character>();
        for(int i=0;i<n;++i){
            char c = s.charAt(i);
            if(pairs.containsKey(c)){//说明c是右括号
                //栈为空说明还没有左括号，凑不成一对括号，或则右括号对应的左括号和栈中的值不同，说明也凑不成一对括号
                if(stack.isEmpty() || pairs.get(c) != stack.peek()){
                    return false;
                }
                stack.pop();//凑成一对括号了 从栈中弹出     
            }else{
                stack.push(c);//左括号入栈
            }
        }
        return stack.isEmpty();
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29

155. 最小栈

设计一个支持 push ，pop ，top 操作，并能在常数时间内检索到最小元素的栈。

push(x) —— 将元素 x 推入栈中。
pop() —— 删除栈顶的元素。
top() —— 获取栈顶元素。
getMin() —— 检索栈中的最小元素。
pop、top 和 getMin 操作总是在 非空栈 上调用。

class MinStack {
    Deque<Integer> xStack;
    Deque<Integer> minStack;
    /** initialize your data structure here. */
    public MinStack() {
        xStack = new LinkedList<Integer>();
        minStack = new LinkedList<Integer>();
        minStack.push(Integer.MAX_VALUE);
    }
    
    public void push(int val) {
        xStack.push(val);
        minStack.push(Math.min(minStack.peek(),val));
    }
    
    public void pop() {
        xStack.pop();
        minStack.pop();
    }
    
    public int top() {
        return xStack.peek();
    }
    
    public int getMin() {
        return minStack.peek();
    }
}

/**
 * Your MinStack object will be instantiated and called as such:
 * MinStack obj = new MinStack();
 * obj.push(val);
 * obj.pop();
 * int param_3 = obj.top();
 * int param_4 = obj.getMin();
 */
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37

225. 用队列实现栈

请你仅使用两个队列实现一个后入先出（LIFO）的栈，并支持普通栈的全部四种操作（push、top、pop 和 empty）。

实现 MyStack 类：

void push(int x) 将元素 x 压入栈顶。
int pop() 移除并返回栈顶元素。
int top() 返回栈顶元素。
boolean empty() 如果栈是空的，返回 true ；否则，返回 false 。

注意：

你只能使用队列的基本操作 —— 也就是 push to back、peek/pop from front、size 和 is empty 这些操作。
你所使用的语言也许不支持队列。 你可以使用 list （列表）或者 deque（双端队列）来模拟一个队列 , 只要是标准的队列操作即可。

1 <= x <= 9
最多调用100 次 push、pop、top 和 empty
每次调用 pop 和 top 都保证栈不为空

class MyStack {
    Queue<Integer> queue1;
    Queue<Integer> queue2;

    /** Initialize your data structure here. */
    public MyStack() {
        queue1 = new LinkedList<Integer>();
        queue2 = new LinkedList<Integer>();
    }
    
    /** Push element x onto stack. */
    public void push(int x) {
       queue2.offer(x);
       while(!queue1.isEmpty()){
           queue2.offer(queue1.poll());
       }
       Queue<Integer> temp = queue1;
       queue1 = queue2;
       queue2 = temp;
    }
    
    /** Removes the element on top of the stack and returns that element. */
    public int pop() {
        return queue1.poll();
    }
    
    /** Get the top element. */
    public int top() {
        return queue1.peek();
    }
    
    /** Returns whether the stack is empty. */
    public boolean empty() {
        return queue1.isEmpty();
    }
}


/**
 * Your MyStack object will be instantiated and called as such:
 * MyStack obj = new MyStack();
 * obj.push(x);
 * int param_2 = obj.pop();
 * int param_3 = obj.top();
 * boolean param_4 = obj.empty();
 */
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46

2.2.2 中等题目

71.简化路径

给你一个字符串 path ，表示指向某一文件或目录的 Unix 风格 绝对路径 （以 ‘/’ 开头），请你将其转化为更加简洁的规范路径。

在 Unix 风格的文件系统中，一个点（.）表示当前目录本身；此外，两个点 （…） 表示将目录切换到上一级（指向父目录）；两者都可以是复杂相对路径的组成部分。任意多个连续的斜杠（即，’//’）都被视为单个斜杠 ‘/’ 。 对于此问题，任何其他格式的点（例如，’…’）均被视为文件/目录名称。

请注意，返回的 规范路径 必须遵循下述格式：

始终以斜杠 ‘/’ 开头。
两个目录名之间必须只有一个斜杠 ‘/’ 。
最后一个目录名（如果存在）不能 以 ‘/’ 结尾。
此外，路径仅包含从根目录到目标文件或目录的路径上的目录（即，不含 ‘.’ 或 ‘…’）。
返回简化后得到的 规范路径 。
1 <= path.length <= 3000
path 由英文字母，数字，’.’，’/’ 或 ‘_’ 组成。
path 是一个有效的 Unix 风格绝对路径

class Solution {
    public String simplifyPath(String path) {
        String[] s = path.split("/");
        Stack<String> stack = new Stack<>();
        for(int i=0;i<s.length;++i){
            if(s[i].isEmpty() || ".".equals(s[i])){
                continue;
            }else if("..".equals(s[i])){
                if(!stack.isEmpty()){
                    stack.pop();
                } 
            }else{
                stack.push(s[i]);
            }
        }
        return "/" + String.join("/", stack);
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18

150.逆波兰表达式求值

根据 逆波兰表示法，求表达式的值。

有效的算符包括 +、-、*、/ 。每个运算对象可以是整数，也可以是另一个逆波兰表达式。

说明：

整数除法只保留整数部分。
给定逆波兰表达式总是有效的。换句话说，表达式总会得出有效数值且不存在除数为 0 的情况。

提示：

1 <= tokens.length <= 104
tokens[i] 要么是一个算符（"+"、"-"、"*" 或 “/”），要么是一个在范围 [-200, 200] 内的整数

逆波兰表达式：

逆波兰表达式是一种后缀表达式，所谓后缀就是指算符写在后面。

平常使用的算式则是一种中缀表达式，如 ( 1 + 2 ) * ( 3 + 4 ) 。
该算式的逆波兰表达式写法为 ( ( 1 2 + ) ( 3 4 + ) * ) 。
逆波兰表达式主要有以下两个优点：

去掉括号后表达式无歧义，上式即便写成 1 2 + 3 4 + * 也可以依据次序计算出正确结果。
适合用栈操作运算：遇到数字则入栈；遇到算符则取出栈顶两个数字进行计算，并将结果压入栈中。

class Solution {
    public int evalRPN(String[] tokens) {
        Stack<Integer> stack = new Stack<Integer>();
        for(int i=0;i<tokens.length;++i){
            String s = tokens[i];
            if(isNumber(s)){
                stack.push(Integer.parseInt(s));
            }else{
                int num1 = stack.pop();
                int num2 = stack.pop();
                switch(s){
                    case "+":
                        stack.push(num2 + num1);
                        break;
                    case "-":
                        stack.push(num2 - num1);
                        break;
                    case "*":
                        stack.push(num2 * num1);
                        break;
                    case "/":
                        stack.push(num2 / num1);
                        break;
                }
            }
        }
        return stack.pop();
    }
    public boolean isNumber(String token) {
        return !("+".equals(token) || "-".equals(token) || "*".equals(token) || "/".equals(token));
    }

}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33

2.3 图

2.3.1中等题目

207. 课程表

你这个学期必须选修 numCourses 门课程，记为 0 到 numCourses - 1 。

在选修某些课程之前需要一些先修课程。 先修课程按数组 prerequisites 给出，其中 prerequisites[i] = [ai, bi] ，表示如果要学习课程 ai 则 必须 先学习课程 bi 。

例如，先修课程对 [0, 1] 表示：想要学习课程 0 ，你需要先完成课程 1 。
请你判断是否可能完成所有课程的学习？如果可以，返回 true ；否则，返回 false 。

1 <= numCourses <= 105
0 <= prerequisites.length <= 5000
prerequisites[i].length == 2
0 <= ai, bi < numCourses
prerequisites[i] 中的所有课程对 互不相同

class Solution {
    List<List<Integer>> edges;//存储有向图
    int[] indeg;//当前结点入度

    public boolean canFinish(int numCourses, int[][] prerequisites) {
        //根据边的关系来构造图
        //共创建了与课程个数相同的列表数
        //每个列表代表的就是对应的每个课程
        //每个列表里面存储的值，就是该课程指向的下一个课程
        edges = new ArrayList<List<Integer>>();
        for (int i = 0; i < numCourses; ++i) {
            edges.add(new ArrayList<Integer>());
        }
        //创建入度表
        //数组下标对应的是相应的课程，里面的值是该课程的入度值
        indeg = new int[numCourses];
        for (int[] info : prerequisites) {
            edges.get(info[1]).add(info[0]);
            ++indeg[info[0]];
        }
        
        Queue<Integer> queue = new LinkedList<Integer>();
        for (int i = 0; i < numCourses; ++i) {
            if (indeg[i] == 0) {//入度为0的结点入队
                queue.offer(i);
            }
        }

        int visited = 0;//用来记录访问的个数
        while (!queue.isEmpty()) {
            ++visited;
            int u = queue.poll();//从队列中取出一个入度值为0的点
            for (int v: edges.get(u)) {//获取它下一个结点
                --indeg[v];//该结点入度数减一
                if (indeg[v] == 0) {//入度为0的结点入队
                    queue.offer(v);
                }
            }
        }

        return visited == numCourses;//访问的个数与课程数相等说明全部修完
    }
}

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44

210. 课程表 II

现在你总共有 n 门课需要选，记为 0 到 n-1。

在选修某些课程之前需要一些先修课程。 例如，想要学习课程 0 ，你需要先完成课程 1 ，我们用一个匹配来表示他们: [0,1]

给定课程总量以及它们的先决条件，返回你为了学完所有课程所安排的学习顺序。

可能会有多个正确的顺序，你只要返回一种就可以了。如果不可能完成所有课程，返回一个空数组。

说明:

输入的先决条件是由边缘列表表示的图形，而不是邻接矩阵。详情请参见图的表示法。
你可以假定输入的先决条件中没有重复的边。
提示:

这个问题相当于查找一个循环是否存在于有向图中。如果存在循环，则不存在拓扑排序，因此不可能选取所有课程进行学习。
通过 DFS 进行拓扑排序 - 一个关于Coursera的精彩视频教程（21分钟），介绍拓扑排序的基本概念。
拓扑排序也可以通过 BFS 完成。

class Solution {
    List<List<Integer>> edges;//存储有向图
    int[] indeg;//当前结点入度
    int[] ans;
    int index = 0;
    public int[] findOrder(int numCourses, int[][] prerequisites) {
        //根据边的关系来构造图
        //共创建了与课程个数相同的列表数
        //每个列表代表的就是对应的每个课程
        //每个列表里面存储的值，就是该课程指向的下一个课程
        edges = new ArrayList<List<Integer>>();
        for (int i = 0; i < numCourses; ++i) {
            edges.add(new ArrayList<Integer>());
        }
        //创建入度表
        //数组下标对应的是相应的课程，里面的值是该课程的入度值
        indeg = new int[numCourses];
        for (int[] info : prerequisites) {
            edges.get(info[1]).add(info[0]);
            ++indeg[info[0]];
        }
        
        Queue<Integer> queue = new LinkedList<Integer>();
        for (int i = 0; i < numCourses; ++i) {
            if (indeg[i] == 0) {//入度为0的结点入队
                queue.offer(i);
            }
        }

        ans = new int[numCourses];
        while (!queue.isEmpty()) {
            int u = queue.poll();//从队列中取出一个入度值为0的点
            ans[index++] = u;
            for (int v: edges.get(u)) {//获取它下一个结点
                --indeg[v];//该结点入度数减一
                if (indeg[v] == 0) {//入度为0的结点入队
                    queue.offer(v);
                }
            }
            
        }
        if (index != numCourses) {//说明没有修完
            return new int[0];
        }
        return ans;
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47

3.技巧

3.1 双指针

3.1.1 简单题目

给你一个有序数组 nums ，请你 原地 删除重复出现的元素，使每个元素 只出现一次 ，返回删除后数组的新长度。

不要使用额外的数组空间，你必须在 原地 修改输入数组 并在使用 O(1) 额外空间的条件下完成。
0 <= nums.length <= 3 * 104
-104 <= nums[i] <= 104
nums 已按升序排列

class Solution {
    public int removeDuplicates(int[] nums) {
        if(nums.length == 0){
            return 0;
        }
        int left= 1;
        int right = 1;
        while(right<nums.length){
            if(nums[right]!=nums[right-1]){
                nums[left++]=nums[right];
            }
            right++;
        }
        return left;
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16

27.移除元素

给你一个数组 nums 和一个值 val，你需要 原地 移除所有数值等于 val 的元素，并返回移除后数组的新长度。

不要使用额外的数组空间，你必须仅使用 O(1) 额外空间并 原地 修改输入数组。

元素的顺序可以改变。你不需要考虑数组中超出新长度后面的元素。

0 <= nums.length <= 100
0 <= nums[i] <= 50
0 <= val <= 100

class Solution {
    public int removeElement(int[] nums, int val) {
        if(nums.length == 0){
            return 0;
        }
        if(nums.length == 1){
            return nums[0] == val ? 0 : 1;
        }
        int left= 0;
        int right = nums.length-1;
        while(left<=right){
            if(nums[left] == val){
                if(nums[right] != val){
                    int temp = nums[right];
                    nums[right] = nums[left];
                    nums[left] = temp;
                }else{
                    right--;
                }
            }else{
                left++;
            }
        }
        return left;
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26

88. 合并两个有序数组

给你两个按 非递减顺序 排列的整数数组 nums1 和 nums2，另有两个整数 m 和 n ，分别表示 nums1 和 nums2 中的元素数目。

请你 合并 nums2 到 nums1 中，使合并后的数组同样按 非递减顺序 排列。

注意：最终，合并后数组不应由函数返回，而是存储在数组 nums1 中。为了应对这种情况，nums1 的初始长度为 m + n，其中前 m 个元素表示应合并的元素，后 n 个元素为 0 ，应忽略。nums2 的长度为 n 。
nums1.length == m + n
nums2.length == n
0 <= m, n <= 200
1 <= m + n <= 200
-109 <= nums1[i], nums2[j] <= 109

class Solution {
    public void merge(int[] nums1, int m, int[] nums2, int n) {
         int i = m-1;
         int j = n-1;
         int t = m+n-1;
         int cur; 
         while(i>=0 || j>=0){
             if(i==-1){
                 cur = nums2[j--];
             }else if(j==-1){
                 cur = nums1[i--];
             }else if(nums1[i]<=nums2[j]){
                 cur = nums2[j--];
             }else{
                 cur = nums1[i--];
             }
             nums1[t--] = cur; 
         }
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20

125. 验证回文串

给定一个字符串，验证它是否是回文串，只考虑字母和数字字符，可以忽略字母的大小写。

说明：本题中，我们将空字符串定义为有效的回文串。
1 <= s.length <= 2 * 105
字符串 s 由 ASCII 字符组成

class Solution {
    public boolean isPalindrome(String s) {
        int n = s.length();
        int left = 0;
        int right = n-1;
        while(left<right){
            while(left<right && !Character.isLetterOrDigit(s.charAt(left))){
                left++;
            }
            while(left<right && !Character.isLetterOrDigit(s.charAt(right))){
                right--;
            }
            if(left<right && Character.toLowerCase(s.charAt(left))!=Character.toLowerCase(s.charAt(right))){
                return false;
            }
            left++;
            right--;
        }
        return true;
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21

141. 环形链表

给定一个链表，判断链表中是否有环。

如果链表中有某个节点，可以通过连续跟踪 next 指针再次到达，则链表中存在环。 为了表示给定链表中的环，我们使用整数 pos 来表示链表尾连接到链表中的位置（索引从 0 开始）。 如果 pos 是 -1，则在该链表中没有环。注意：pos 不作为参数进行传递，仅仅是为了标识链表的实际情况。

如果链表中存在环，则返回 true 。 否则，返回 false 。
链表中节点的数目范围是 [0, 104]
-105 <= Node.val <= 105
pos 为 -1 或者链表中的一个 有效索引 。

/**
 * Definition for singly-linked list.
 * class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode(int x) {
 *         val = x;
 *         next = null;
 *     }
 * }
 */
public class Solution {
    public boolean hasCycle(ListNode head) {
        if(head == null || head.next == null){
            return false;
        }
        ListNode slow = head;
        ListNode fast = head.next;
        while(slow != fast){
            if(fast == null || fast.next == null){
                return false;
            }
            slow = slow.next;
            fast = fast.next.next;
        }
        return true;
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28

160.相交链表

给你两个单链表的头节点 headA 和 headB ，请你找出并返回两个单链表相交的起始节点。如果两个链表没有交点，返回 null 。
listA 中节点数目为 m
listB 中节点数目为 n
0 <= m, n <= 3 * 104
1 <= Node.val <= 105
0 <= skipA <= m
0 <= skipB <= n
如果 listA 和 listB 没有交点，intersectVal 为 0
如果 listA 和 listB 有交点，intersectVal == listA[skipA + 1] == listB[skipB + 1]

public class Solution {
    public ListNode getIntersectionNode(ListNode headA, ListNode headB) {
        if (headA == null || headB == null) {
            return null;
        }
        ListNode pA = headA, pB = headB;
        while (pA != pB) {
            pA = pA == null ? headB : pA.next;
            pB = pB == null ? headA : pB.next;
        }
        return pA;
    }
}

1
2
3
4
5
6
7
8
9
10
11
12
13
14

167. 两数之和 II - 输入有序数组

给定一个已按照 升序排列 的整数数组 numbers ，请你从数组中找出两个数满足相加之和等于目标数 target 。

函数应该以长度为 2 的整数数组的形式返回这两个数的下标值。numbers 的下标 从 1 开始计数 ，所以答案数组应当满足 1 <= answer[0] < answer[1] <= numbers.length 。

你可以假设每个输入只对应唯一的答案，而且你不可以重复使用相同的元素。

2 <= numbers.length <= 3 * 104
-1000 <= numbers[i] <= 1000
numbers 按 递增顺序 排列
-1000 <= target <= 1000
仅存在一个有效答案

class Solution {
    public int[] twoSum(int[] numbers, int target) {
        int left = 0;
        int right = numbers.length-1;
        while(left<right){
            int sum = numbers[left]+numbers[right];
            if(sum==target){
                return new int[]{left+1,right+1};
            }else if(sum<target){
                ++left;
            }else{
                --right;
            }
        }
        return new int[]{-1,-1};
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17

202. 快乐数

编写一个算法来判断一个数 n 是不是快乐数。

「快乐数」定义为：

对于一个正整数，每一次将该数替换为它每个位置上的数字的平方和。
然后重复这个过程直到这个数变为 1，也可能是 无限循环 但始终变不到 1。
如果 可以变为 1，那么这个数就是快乐数。
如果 n 是快乐数就返回 true ；不是，则返回 false 。

1 <= n <= 231 - 1

class Solution {
    private int getNext(int n) {
        int totalSum = 0;
        while (n > 0) {
            int d = n % 10;
            n = n / 10;
            totalSum += d * d;
        }
        return totalSum;
    }

    public boolean isHappy(int n) {
        Set<Integer> seen = new HashSet<>();
        while (n != 1 && !seen.contains(n)) {
            seen.add(n);
            n = getNext(n);
        }
        return n == 1;
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20

283.移动零

给定一个数组 nums，编写一个函数将所有 0 移动到数组的末尾，同时保持非零元素的相对顺序。

class Solution {
    public void moveZeroes(int[] nums) {
        int n = nums.length, left = 0, right = 0;
        while (right < n) {
            if (nums[right] != 0) {
                swap(nums, left, right);
                left++;
            }
            right++;
        }
    }

    public void swap(int[] nums, int left, int right) {
        int temp = nums[left];
        nums[left] = nums[right];
        nums[right] = temp;
    }
}

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19

344.反转字符串

编写一个函数，其作用是将输入的字符串反转过来。输入字符串以字符数组 char[] 的形式给出。

不要给另外的数组分配额外的空间，你必须原地修改输入数组、使用 O(1) 的额外空间解决这一问题。

你可以假设数组中的所有字符都是 ASCII 码表中的可打印字符。

class Solution {
    public void reverseString(char[] s) {
        int left = 0;
        int right = s.length-1;
        while(left<right){
            char t = s[left];
            s[left] = s[right];
            s[right] = t;
            left++;
            right--;
        } 
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13

3.1.2 中等题目

11.盛最多水的容器

给你 n 个非负整数 a1，a2，…，an，每个数代表坐标中的一个点 (i, ai) 。在坐标内画 n 条垂直线，垂直线 i 的两个端点分别为 (i, ai) 和 (i, 0) 。找出其中的两条线，使得它们与 x 轴共同构成的容器可以容纳最多的水。

说明：你不能倾斜容器。
n = height.length
2 <= n <= 3 * 104
0 <= height[i] <= 3 * 104

class Solution {
    public int maxArea(int[] height) {
        int l = 0;
        int r = height.length-1;
        int ans = 0;
        while(l<r){
            int area = Math.min(height[l],height[r])*(r-l);
            ans = Math.max(ans,area);
            if(height[l]<height[r]){
                ++l;
            }else{
                --r;
            }
        }
        return ans;
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17

15. 三数之和

给你一个包含 n 个整数的数组 nums，判断 nums 中是否存在三个元素 a，b，c ，使得 a + b + c = 0 ？请你找出所有和为 0 且不重复的三元组。

注意：答案中不可以包含重复的三元组。

0 <= nums.length <= 3000
-105 <= nums[i] <= 105

class Solution {
    public List<List<Integer>> threeSum(int[] nums) {
        int n=nums.length;
        Arrays.sort(nums);
        List<List<Integer>> ans = new ArrayList<List<Integer>>();
        for(int i=0;i<n;++i){
            //需要和上一次枚举的数不同
            if(i>0 && nums[i] == nums[i-1]){
                continue;
            }
            for(int j=i+1;j<n;++j){
                 //需要和上一次枚举的数不同
                if(j>i+1 && nums[j] == nums[j-1]){
                    continue;
                }

                int k = n-1;
                int target=-nums[i];
                while(j<k && nums[j]+nums[k]>target){
                    --k;
                }
                if(j==k){
                    break;
                }

                if(nums[j]+nums[k]==target){
                    List<Integer> list = new ArrayList<>();
                    list.add(nums[i]);
                    list.add(nums[j]);
                    list.add(nums[k]);
                    ans.add(list);
                }
            }
        }
        return ans;
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37

16. 最接近的三数之和

给定一个包括 n 个整数的数组 nums 和 一个目标值 target。找出 nums 中的三个整数，使得它们的和与 target 最接近。返回这三个数的和。假定每组输入只存在唯一答案。
3 <= nums.length <= 10^3
-10^3 <= nums[i] <= 10^3
-10^4 <= target <= 10^4

class Solution {
    public int threeSumClosest(int[] nums, int target) {
        int n=nums.length;
        Arrays.sort(nums);
        int best = 1000000;
        for(int i=0;i<n;++i){
            //需要和上一次枚举的数不同
            if(i>0 && nums[i] == nums[i-1]){
                continue;
            }
            int left = i+1;
            int right = n-1;
            while(left<right){
                int sum = nums[i]+nums[left]+nums[right];
                if(sum == target){
                    return target;
                }
                //更新最接近的值
                if(Math.abs(sum-target)<Math.abs(best-target)){
                    best = sum;
                }
                if(sum > target){
                    int right0 = right-1;
                    //需要和上一次枚举的数不同
                    while(left<right0  && nums[right] == nums[right0]){
                        --right0;
                    }
                    right = right0;
                }else{
                    int left0 = left+1;
                    //需要和上一次枚举的数不同
                    while(left0<right && nums[left] == nums[left0]){
                        ++left0;
                    }
                    left = left0;
                }
            }
            
        }
        return best;
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42

19. 删除链表的倒数第 N 个结点

给你一个链表，删除链表的倒数第 n 个结点，并且返回链表的头结点。

进阶：你能尝试使用一趟扫描实现吗？
链表中结点的数目为 sz
1 <= sz <= 30
0 <= Node.val <= 100
1 <= n <= sz

/**
 * Definition for singly-linked list.
 * public class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode() {}
 *     ListNode(int val) { this.val = val; }
 *     ListNode(int val, ListNode next) { this.val = val; this.next = next; }
 * }
 */
class Solution {
    public ListNode removeNthFromEnd(ListNode head, int n) {
        ListNode dummy = new ListNode(0,head);//新建一个节点指向头结点
        int length = getLength(head);
        ListNode cur = dummy;//用来遍历链表
        for(int i=1;i<length-n+1;++i){
            cur = cur.next;//找到要删除节点的上一个节点
        }
        cur.next = cur.next.next;
        ListNode ans = dummy.next;
        return ans;
    }
    //求链表的长度
    public int getLength(ListNode head){
        int length = 0;
        while(head != null){
            ++length;
            head = head.next;
        } 
        return length;
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32

31. 下一个排列

实现获取 下一个排列 的函数，算法需要将给定数字序列重新排列成字典序中下一个更大的排列（即，组合出下一个更大的整数）。

如果不存在下一个更大的排列，则将数字重新排列成最小的排列（即升序排列）。

必须 原地 修改，只允许使用额外常数空间。

class Solution {
    public void nextPermutation(int[] nums) {
        int i = nums.length - 2;
        //从后往前找到第一个递减的数
        while(i>=0 && nums[i]>=nums[i+1]){
            i--;
        }
        if(i >= 0){
            int j = nums.length - 1;
            //从后往前找到第一个大于nums[i]的数
            while(j>=0 && nums[i]>=nums[j]){
                j--;
            }
            swap(nums,i,j);//将nums[i]和nums[j]交换
        }
        reverse(nums,i+1);//将nums[i]后面的数进行反转
        
    }
    public void swap(int[] nums,int i,int j){
        int temp = nums[i];
        nums[i] = nums[j];
        nums[j] = temp;
    }
    public void reverse(int[] nums,int start){
        int left = start;
        int right = nums.length-1;
        while(left<right){
            swap(nums,left,right);
            left++;
            right--;
        }
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33

61. 旋转链表

给你一个链表的头节点 head ，旋转链表，将链表每个节点向右移动 k 个位置。
链表中节点的数目在范围 [0, 500] 内
-100 <= Node.val <= 100
0 <= k <= 2 * 109

/**
 * Definition for singly-linked list.
 * public class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode() {}
 *     ListNode(int val) { this.val = val; }
 *     ListNode(int val, ListNode next) { this.val = val; this.next = next; }
 * }
 */
class Solution {
    public ListNode rotateRight(ListNode head, int k) {
        if (k == 0 || head == null || head.next == null) {
            return head;
        }
        int n=1;
        ListNode cur = head;
        while(cur.next != null){
            cur = cur.next;//找到原始的尾结点
            ++n;
        }
        int m = n-k%n;
        if(m==n){
            return head;
        }
        cur.next = head;//变为环
        while(m-- >0){
            cur = cur.next;//找到新的尾结点
        }
        ListNode newHead = cur.next;
        cur.next = null;//断开环
        return newHead;
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34

75. 颜色分类

给定一个包含红色、白色和蓝色，一共 n 个元素的数组，原地对它们进行排序，使得相同颜色的元素相邻，并按照红色、白色、蓝色顺序排列。

此题中，我们使用整数 0、 1 和 2 分别表示红色、白色和蓝色。
n == nums.length
1 <= n <= 300
nums[i] 为 0、1 或 2

class Solution {
    public void sortColors(int[] nums) {
        int n = nums.length;
        int ptr = 0;
        for (int i = 0; i < n; ++i) {
            if (nums[i] == 0) {
                swap(nums,i,ptr);
                ++ptr;
            }
        }
        for (int i = ptr; i < n; ++i) {
            if (nums[i] == 1) {
                swap(nums,i,ptr);
                ++ptr;
            }
        }
    }
    public void swap(int[] nums,int i,int j){
        int temp = nums[i];
        nums[i] = nums[j];
        nums[j] = temp;
    }
        
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24

80. 删除有序数组中的重复项 II

给你一个有序数组 nums ，请你 原地 删除重复出现的元素，使每个元素 最多出现两次 ，返回删除后数组的新长度。

不要使用额外的数组空间，你必须在 原地 修改输入数组 并在使用 O(1) 额外空间的条件下完成。
1 <= nums.length <= 3 * 104
-104 <= nums[i] <= 104
nums 已按升序排列

class Solution {
    public int removeDuplicates(int[] nums) {
        if(nums.length <=2){
            return nums.length;
        }

        int slow = 2;
        int fast = 2;
        while(fast<nums.length){
            if(nums[fast] != nums[slow-2]){
                nums[slow] = nums[fast];
                ++slow;
            }
            ++fast;
        }
        return slow;
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18

82. 删除排序链表中的重复元素 II

存在一个按升序排列的链表，给你这个链表的头节点 head ，请你删除链表中所有存在数字重复情况的节点，只保留原始链表中 没有重复出现 的数字。

返回同样按升序排列的结果链表。
链表中节点数目在范围 [0, 300] 内
-100 <= Node.val <= 100
题目数据保证链表已经按升序排列

/**
 * Definition for singly-linked list.
 * public class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode() {}
 *     ListNode(int val) { this.val = val; }
 *     ListNode(int val, ListNode next) { this.val = val; this.next = next; }
 * }
 */
class Solution {
    public ListNode deleteDuplicates(ListNode head) {
        if(head == null || head.next == null){
            return head;
        }
        ListNode dummy = new ListNode(-101,head);
        ListNode cur = dummy;
        while(cur.next!=null && cur.next.next!=null){
            if(cur.next.val == cur.next.next.val){
                int x =  cur.next.val;
                while(cur.next!=null && cur.next.val==x){//直到下一个不相等的值的结点
                    cur.next = cur.next.next;
                }
                
            }else{
                cur = cur.next;
            }
            
        }
        return dummy.next;
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32

86. 分隔链表

给你一个链表的头节点 head 和一个特定值 x ，请你对链表进行分隔，使得所有 小于 x 的节点都出现在 大于或等于 x 的节点之前。

你应当 保留 两个分区中每个节点的初始相对位置。

/**
 * Definition for singly-linked list.
 * public class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode() {}
 *     ListNode(int val) { this.val = val; }
 *     ListNode(int val, ListNode next) { this.val = val; this.next = next; }
 * }
 */
class Solution {
    public ListNode partition(ListNode head, int x) {
        //设置两个临时的头结点
        ListNode less_head = new ListNode(0);//
        ListNode more_head = new ListNode(0);
        //对应“指针”（引用）指向这两个头结点
        ListNode less = less_head;
        ListNode more = more_head;
        while(head != null){
            //如果结点值小于x，则将该节点插入less后
            if(head.val<x){
                less.next = head;
                head = head.next;
                less = less.next;
            }else{//否则，则将该节点插入more后
                more.next = head;
                head = head.next;
                more = more.next;
            }
        }
        //两个链表进行拼接
        less.next = more_head.next;
        //末尾置空
        more.next = null;
        return less_head.next;
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37

142. 环形链表 II

给定一个链表，返回链表开始入环的第一个节点。 如果链表无环，则返回 null。

为了表示给定链表中的环，我们使用整数 pos 来表示链表尾连接到链表中的位置（索引从 0 开始）。 如果 pos 是 -1，则在该链表中没有环。注意，pos 仅仅是用于标识环的情况，并不会作为参数传递到函数中。

说明：不允许修改给定的链表。
链表中节点的数目范围在范围 [0, 104] 内
-105 <= Node.val <= 105
pos 的值为 -1 或者链表中的一个有效索引

/**
 * Definition for singly-linked list.
 * class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode(int x) {
 *         val = x;
 *         next = null;
 *     }
 * }
 */
public class Solution {
    public ListNode detectCycle(ListNode head) {
        if(head == null){
            return null;
        }
        ListNode slow = head;
        ListNode fast = head;
        while(fast != null){
            slow = slow.next;
            if(fast.next != null){
                fast = fast.next.next;
            }else{
                return null;
            }
            if(slow == fast){//快慢指针相遇
                ListNode res = head;
                while(res != slow){
                    res = res.next;
                    slow = slow.next;
                }
                return res;
            }
        }
        return null;
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37

143.重排链表

给定一个单链表 L 的头节点 head ，单链表 L 表示为：

L0 → L1 → … → Ln-1 → Ln
请将其重新排列后变为：

L0 → Ln → L1 → Ln-1 → L2 → Ln-2 → …

不能只是单纯的改变节点内部的值，而是需要实际的进行节点交换。

链表的长度范围为 [1, 5 * 104]
1 <= node.val <= 1000

/**
 * Definition for singly-linked list.
 * public class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode() {}
 *     ListNode(int val) { this.val = val; }
 *     ListNode(int val, ListNode next) { this.val = val; this.next = next; }
 * }
 */
class Solution {
    public void reorderList(ListNode head) {
        if(head == null || head.next == null ||head.next.next==null){
            return;
        }
        ListNode midNode = searchMidNode(head);
        ListNode l2 = midNode.next;
        midNode.next = null;
        ListNode head2 = reverseList(l2);
        mergeList(head,head2);
    }
    //寻找链表的中点（快慢指针）
    private ListNode searchMidNode(ListNode head){
        ListNode slow = head;
        ListNode fast = head;
        while(fast.next!=null && fast.next.next!=null){
            slow = slow.next;
            fast = fast.next.next;
        }
        return slow;
    }
    //反转链表（使用前插法）
    private ListNode reverseList(ListNode head){
        ListNode pre = null;
        ListNode cur = head;
        while(cur!=null){
            ListNode temp = cur.next;
            cur.next = pre;
            pre = cur;
            cur = temp;
        }
        return pre;
    }
    //拼接两个链表
    private void mergeList(ListNode head1,ListNode head2){
        ListNode node1;
        ListNode node2;
        
        while(head1!=null && head2!=null){
            node1 = head1.next;
            node2 = head2.next;

            head1.next = head2;
            head1 = node1;

            head2.next = head1;
            head2 = node2;  
        }
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60

189. 旋转数组

给定一个数组，将数组中的元素向右移动 k 个位置，其中 k 是非负数。
1 <= nums.length <= 2 * 104
-231 <= nums[i] <= 231 - 1
0 <= k <= 105

class Solution {
    public void rotate(int[] nums, int k) {
        k = k%nums.length;
        if(k==0){
            return;
        }
        reverse(nums,0,nums.length-1);
        reverse(nums,0,k-1);
        reverse(nums,k,nums.length-1);
    }
    private void reverse(int[] nums,int l,int r){
        while(l<r){
            int temp = nums[l];
            nums[l] = nums[r];
            nums[r] = temp;
            ++l;
            --r;
        }
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20

287. 寻找重复数

给定一个包含 n + 1 个整数的数组 nums ，其数字都在 1 到 n 之间（包括 1 和 n），可知至少存在一个重复的整数。

假设 nums 只有 一个重复的整数 ，找出 这个重复的数 。

你设计的解决方案必须不修改数组 nums 且只用常量级 O(1) 的额外空间。

class Solution {
    public int findDuplicate(int[] nums) {
        int slow = 0, fast = 0;
        do {
            slow = nums[slow];
            fast = nums[nums[fast]];
        } while (slow != fast);
        slow = 0;
        while (slow != fast) {
            slow = nums[slow];
            fast = nums[fast];
        }
        return slow;
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15

3.2 位运算

3.2.1 简单题目

136. 只出现一次的数字

给定一个非空整数数组，除了某个元素只出现一次以外，其余每个元素均出现两次。找出那个只出现了一次的元素。

class Solution {
    public int singleNumber(int[] nums) {
        int single = 0;
        for(int num : nums){
            single ^= num;//按位异或
        }
        return single;
    }
}
1
2
3
4
5
6
7
8
9

190. 颠倒二进制位

颠倒给定的 32 位无符号整数的二进制位。

提示：

请注意，在某些语言（如 Java）中，没有无符号整数类型。在这种情况下，输入和输出都将被指定为有符号整数类型，并且不应影响您的实现，因为无论整数是有符号的还是无符号的，其内部的二进制表示形式都是相同的。
在 Java 中，编译器使用二进制补码记法来表示有符号整数。因此，在上面的 示例 2 中，输入表示有符号整数 -3，输出表示有符号整数 -1073741825。

输入是一个长度为 32 的二进制字符串

public class Solution {
    public int reverseBits(int n) {
        int rev = 0;
        for (int i = 0; i < 32 && n != 0; ++i) {
            rev |= (n & 1) << (31 - i);
            n >>>= 1;//无符号右移
        }
        return rev;
    }
}
1
2
3
4
5
6
7
8
9
10

191. 位1的个数

编写一个函数，输入是一个无符号整数（以二进制串的形式），返回其二进制表达式中数字位数为 ‘1’ 的个数（也被称为汉明重量）。

提示：

请注意，在某些语言（如 Java）中，没有无符号整数类型。在这种情况下，输入和输出都将被指定为有符号整数类型，并且不应影响您的实现，因为无论整数是有符号的还是无符号的，其内部的二进制表示形式都是相同的。
在 Java 中，编译器使用二进制补码记法来表示有符号整数。因此，在上面的 示例 3 中，输入表示有符号整数 -3。
输入必须是长度为 32 的 二进制串 。

public class Solution {
    public int hammingWeight(int n) {
        int ret = 0;
        for (int i = 0; i < 32; i++) {
            if ((n & (1 << i)) != 0) {
                ret++;
            }
        }
        return ret;
    }
}
//优化
public class Solution {
    public int hammingWeight(int n) {
        int ret = 0;
        while (n != 0) {
            n &= n - 1;
            ret++;
        }
        return ret;
    }
}

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23

231. 2 的幂

给你一个整数 n，请你判断该整数是否是 2 的幂次方。如果是，返回 true ；否则，返回 false 。

如果存在一个整数 x 使得 n == 2x ，则认为 n 是 2 的幂次方。

-2^31 <= n <= 2 ^31 - 1

class Solution {
    public boolean isPowerOfTwo(int n) {
        return n > 0 && (n & (n - 1)) == 0;
    }
}

1
2
3
4
5
6

3.2.2 中等题目

137. 只出现一次的数字 II

给你一个整数数组 nums ，除某个元素仅出现 一次 外，其余每个元素都恰出现 三次 。请你找出并返回那个只出现了一次的元素。

1 <= nums.length <= 3 * 104
-231 <= nums[i] <= 231 - 1
nums 中，除某个元素仅出现 一次 外，其余每个元素都恰出现 三次

class Solution {
    public int singleNumber(int[] nums) {
        int a = 0, b = 0;
        for (int num : nums) {
            b = ~a & (b ^ num);
            a = ~b & (a ^ num);
        }
        return b;
    }
}

1
2
3
4
5
6
7
8
9
10
11

260. 只出现一次的数字 III

给定一个整数数组 nums，其中恰好有两个元素只出现一次，其余所有元素均出现两次。 找出只出现一次的那两个元素。你可以按 任意顺序 返回答案。

进阶：你的算法应该具有线性时间复杂度。你能否仅使用常数空间复杂度来实现？
2 <= nums.length <= 3 * 104
-231 <= nums[i] <= 231 - 1
除两个只出现一次的整数外，nums 中的其他数字都出现两次

class Solution {
    public int[] singleNumber(int[] nums) {
        int ret = 0;
        for (int n : nums) {
            ret ^= n;
        }
        int div = 1;
        while ((div & ret) == 0) {
            div <<= 1;
        }
        int a = 0, b = 0;
        for (int n : nums) {
            if ((div & n) != 0) {
                a ^= n;
            } else {
                b ^= n;
            }
        }
        return new int[]{a, b};
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21