169.多数元素

✒解题思路：

  1. 哈希
  2. 排序法，次数大于n/2的元素必定出现在排序后nums[n/2]的位置上
  3. Boyer-Moore投票算法，将众数记为+1，其他数记为-1，设置计数器count和candidate，当count=0时，令candidate = num。当candidate==num时，count+1，否则count-1
1
2
3
4
5
6
7
8
9
10
11
12
13
class Solution {
	private int majorityElement(int[] nums){
		int count = 0;
		int candidate = 0;
		for (int num:nums){
			if(count==0){
				candidate = num;
			}
			count = count + (candidate==num?1:-1);
		}
		return candidate;
	}
}

70.爬楼梯

✒解题思路：

  1. DP打表
  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
27
28
29
30
//法一
class Solution {
	public int climbStairs(int n) {
		if (n == 1) {
			return 1;
		}
		int[] dp = new int[n + 1];
		dp[1] = 1;
		dp[2] = 2;
		for (int i = 3; i <= n; i++) {
			dp[i] = dp[i - 1] + dp[i - 2];
		}
		return dp[n];
	}
}
//法二
class Solution {
	public int climbStairs(int n) {
		if (n == 1) {
			return 1;
		}
		int first = 1;
		int second = 2;
		for (int i = 3; i <= n; i++) {
			second = first + second;
			first = second - first;
		}
		return second;
	}
}

198.打家劫舍

✒解题思路：

  1. DP打表
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
class Solution {
	public int rob(int[] nums) {
        if (nums.length == 0) {
			return 0;
		}
		if (nums.length == 1) {
			return nums[0];
		}
		if (nums.length == 2) {
			return Math.max(nums[0], nums[1]);
		}
		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(nums[i] + dp[i - 2], dp[i - 1]);
		}
		return dp[dp.length - 1];
	}
}

746.使用最小花费爬楼梯

✒解题思路：

  1. 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
//1
class Solution {
	public int minCostClimbingStairs(int[] cost) {
		int first = 0;
		int second = 0;
		int cur = 0;
		for (int i = 0; i < cost.length; i++) {
			cur = cost[i] + Math.min(first, second);
			first = second;
			second = cur;
		}
		return Math.min(first, second);
	}
}
//2
class Solution {
	public int minCostClimbingStairs(int[] cost) {
		if (cost.length == 0) {
			return 0;
		}
		if (cost.length == 1) {
			return cost[0];
		}
		int[] dp = new int[cost.length + 1];
		dp[0] = cost[0];
		dp[1] = cost[1];
		for (int i = 2; i < cost.length; i++) {
			dp[i] = cost[i] + Math.min(dp[i - 1], dp[i - 2]);
		}
		dp[cost.length] = Math.min(dp[cost.length - 1], dp[cost.length - 2]);
		return dp[cost.length];
	}
}

104.二叉树的最大深度

✒解题思路：

  1. 二叉树的深度遍历
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode(int x) { val = x; }
 * }
 */
class Solution {
	public int maxDepth(TreeNode root) {
		if (root == null) {
			return 0;
		}
		int left_height = maxDepth(root.left);
		int right_height = maxDepth(root.right);
		return Math.max(left_height, right_height) + 1;
	}
}

101.对称二叉树

✒解题思路：

  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
/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode(int x) { val = x; }
 * }
 */
class Solution {
	public boolean isSymmetric(TreeNode root) {
		if (root == null) {
			return true;
		}
		return isMirror(root.left, root.right);
	}

	public boolean isMirror(TreeNode left, TreeNode right) {
		if (left == null && right == null) {
			return true;
		}
		if (left == null || right == null) {
			return false;
		}

		return (left.val == right.val) && isMirror(left.left, right.right) && isMirror(left.right, right.left);
	}
}

100.相同的树

✒解题思路：

  1. 官方：它们的两个根结点具有相同的值,且每个树的右子树都与另一个树的树的右子树相同，每个树的左子树都与另一个树的树的左子树相同
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode(int x) { val = x; }
 * }
 */
class Solution {
	public boolean isSameTree(TreeNode p, TreeNode q) {
		if (p == null && q == null) {
			return true;
		}
		if (p == null || q == null) {
			return false;
		}
		return (p.val == q.val) && isSameTree(p.left, q.left) && isSameTree(p.right, q.right);
	}
}

111.二叉树的最小深度

✒解题思路：

  1. 当root==null，返回0
  2. 当root.left==null&&root.right==null,返回1
  3. 当root.left==null||root.right==null,返回不为空的子树高度
  4. 当子树都不为空，返回较小深度
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode(int x) { val = x; }
 * }
 */
class Solution {
	public int minDepth(TreeNode root) {
		if (root == null) {
			return 0;
		}
		if (root.left == null && root.right == null) {
			return 1;
		}
		int left_height = minDepth(root.left);
		int right_height = minDepth(root.right);
		return (root.left == null || root.right == null) ? left_height + right_height + 1 : Math.min(left_height, right_height) + 1;
	}
}