62. 不同路径
一个机器人位于一个 m x n 网格的左上角 （起始点在下图中标记为“Start” ）。
机器人每次只能向下或者向右移动一步。机器人试图达到网格的右下角（在下图中标记为“Finish”）。
问总共有多少条不同的路径？
例如，上图是一个7 x 3 的网格。有多少可能的路径？
说明：m 和 n 的值均不超过 100。
示例 1:
输入: m = 3, n = 2 输出: 3 解释: 从左上角开始，总共有 3 条路径可以到达右下角。 1. 向右 -> 向右 -> 向下 2. 向右 -> 向下 -> 向右 3. 向下 -> 向右 -> 向右示例 2:
输入: m = 7, n = 3 输出: 28 class Solution { public int uniquePaths(int m, int n) { int[][] dp = new int[m][n]; for (int i = 0; i < m; i++) { for (int j = 0; j < n; j++) { if (i == 0 || j == 0) dp[i][j] = 1; else { dp[i][j] = dp[i - 1][j] + dp[i][j - 1]; } } } return dp[m - 1][n - 1]; } }64. 最小路径和
给定一个包含非负整数的 m x n 网格，请找出一条从左上角到右下角的路径，使得路径上的数字总和为最小。
说明：每次只能向下或者向右移动一步。
示例:
输入: [ [1,3,1], [1,5,1], [4,2,1] ] 输出: 7 解释: 因为路径 1→3→1→1→1 的总和最小。 class Solution { public int minPathSum(int[][] grid) { int m = grid.length; int n = grid[0].length; int[][] dp = new int[m][n]; for(int i = 0; i < m; i++) { for(int j = 0; j < n; j++) { if(i == 0 && j == 0) { dp[i][j] = grid[i][j]; }else if(i == 0) { dp[i][j] = dp[i][j - 1] + grid[i][j]; }else if(j == 0) { dp[i][j] = dp[i - 1][j] + grid[i][j]; }else { dp[i][j] = Math.min(dp[i][j - 1] + grid[i][j], dp[i - 1][j] + grid[i][j]); } } } return dp[m - 1][n - 1]; } }70. 爬楼梯
假设你正在爬楼梯。需要 n 阶你才能到达楼顶。
每次你可以爬 1 或 2 个台阶。你有多少种不同的方法可以爬到楼顶呢？
注意：给定 n 是一个正整数。
示例 1：
输入： 2 输出： 2 解释： 有两种方法可以爬到楼顶。 1. 1 阶 + 1 阶 2. 2 阶示例 2：
输入： 3 输出： 3 解释： 有三种方法可以爬到楼顶。 1. 1 阶 + 1 阶 + 1 阶 2. 1 阶 + 2 阶 3. 2 阶 + 1 阶假设你正在爬楼梯，需要 n 阶你才能到达楼顶。
每次你可以爬 1 或 2 个台阶，你有多少种不同的方法可以爬到楼顶呢？
方法一：暴力法
算法
在暴力法中，我们将会把所有可能爬的阶数进行组合，也就是 1 和 2 。而在每一步中我们都会继续调用 climbStairsclimbStairs 这个函数模拟爬 11 阶和 22 阶的情形，并返回两个函数的返回值之和。
climbStairs(i,n)=(i + 1, n) + climbStairs(i + 2, n)climbStairs(i,n)=(i+1,n)+climbStairs(i+2,n)
其中 ii 定义了当前阶数，而 nn 定义了目标阶数。
Java public class Solution { public int climbStairs(int n) { climb_Stairs(0, n); } public int climb_Stairs(int i, int n) { if (i > n) { return 0; } if (i == n) { return 1; } return climb_Stairs(i + 1, n) + climb_Stairs(i + 2, n); } }复杂度分析
时间复杂度：O(2^n)O(2n)，树形递归的大小为 2^n2n 。
在 n = 5 时的递归树将是这样的：
空间复杂度：O(n)O(n)，递归树的深度可以达到 nn 。
方法二：记忆化递归
算法
在上一种方法中，我们计算每一步的结果时出现了冗余。另一种思路是，我们可以把每一步的结果存储在 memomemo 数组之中，每当函数再次被调用，我们就直接从 memomemo 数组返回结果。
在 memomemo 数组的帮助下，我们得到了一个修复的递归树，其大小减少到 nn。
Java public class Solution { public int climbStairs(int n) { int memo[] = new int[n + 1]; return climb_Stairs(0, n, memo); } public int climb_Stairs(int i, int n, int memo[]) { if (i > n) { return 0; } if (i == n) { return 1; } if (memo[i] > 0) { return memo[i]; } memo[i] = climb_Stairs(i + 1, n, memo) + climb_Stairs(i + 2, n, memo); return memo[i]; } }复杂度分析
时间复杂度：O(n)O(n)，树形递归的大小可以达到 nn。空间复杂度：O(n)O(n)，递归树的深度可以达到 nn。方法三：动态规划
算法
不难发现，这个问题可以被分解为一些包含最优子结构的子问题，即它的最优解可以从其子问题的最优解来有效地构建，我们可以使用动态规划来解决这一问题。
第 ii 阶可以由以下两种方法得到：
在第 (i-1)(i−1) 阶后向上爬一阶。
在第 (i-2)(i−2) 阶后向上爬 22 阶。
所以到达第 ii 阶的方法总数就是到第 (i-1)(i−1) 阶和第 (i-2)(i−2) 阶的方法数之和。
令 dp[i]dp[i] 表示能到达第 ii 阶的方法总数：
dp[i]=dp[i-1]+dp[i-2]dp[i]=dp[i−1]+dp[i−2]
示例：
1 / 7
Java public 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]; } }
复杂度分析
时间复杂度：O(n)O(n)，单循环到 nn 。
空间复杂度：O(n)O(n)，dpdp 数组用了 nn 的空间。
方法四：斐波那契数
算法
在上述方法中，我们使用 dpdp 数组，其中 dp[i]=dp[i-1]+dp[i-2]dp[i]=dp[i−1]+dp[i−2]。可以很容易通过分析得出 dp[i]dp[i]其实就是第 ii 个斐波那契数。
Fib(n)=Fib(n-1)+Fib(n-2)Fib(n)=Fib(n−1)+Fib(n−2)
现在我们必须找出以 11 和 22 作为第一项和第二项的斐波那契数列中的第 nn 个数，也就是说 Fib(1)=1Fib(1)=1 且 Fib(2)=2Fib(2)=2。
Java public 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++) { int third = first + second; first = second; second = third; } return second; } }复杂度分析
时间复杂度：O(n)O(n)，单循环到 nn，需要计算第 nn 个斐波那契数。
空间复杂度：O(1)O(1)，使用常量级空间。
75. 颜色分类
给定一个包含红色、白色和蓝色，一共 n 个元素的数组，原地对它们进行排序，使得相同颜色的元素相邻，并按照红色、白色、蓝色顺序排列。
此题中，我们使用整数 0、 1 和 2 分别表示红色、白色和蓝色。
注意: 不能使用代码库中的排序函数来解决这道题。
示例:
输入: [2,0,2,1,1,0] 输出: [0,0,1,1,2,2]进阶：
一个直观的解决方案是使用计数排序的两趟扫描算法。 首先，迭代计算出0、1 和 2 元素的个数，然后按照0、1、2的排序，重写当前数组。你能想出一个仅使用常数空间的一趟扫描算法吗？
方法一: 一次遍历
直觉
本问题被称为 荷兰国旗问题 ，最初由 Edsger W. Dijkstra提出。 其主要思想是给每个数字设定一种颜色，并按照荷兰国旗颜色的顺序进行调整。
我们用三个指针（p0, p2 和curr）来分别追踪0的最右边界，2的最左边界和当前考虑的元素。
本解法的思路是沿着数组移动 curr 指针，若nums[curr] = 0，则将其与 nums[p0]互换；若 nums[curr] = 2 ，则与 nums[p2]互换。
算法
初始化0的最右边界：p0 = 0。在整个算法执行过程中 nums[idx < p0] = 0.
初始化2的最左边界 ：p2 = n - 1。在整个算法执行过程中 nums[idx > p2] = 2.
初始化当前考虑的元素序号 ：curr = 0.
While curr <= p2 :
若 nums[curr] = 0 ：交换第 curr个 和 第p0个 元素，并将指针都向右移。
若 nums[curr] = 2 ：交换第 curr个和第 p2个元素，并将 p2指针左移 。
若 nums[curr] = 1 ：将指针curr右移。
class Solution { /* 荷兰三色旗问题解 */ public void sortColors(int[] nums) { // 对于所有 idx < i : nums[idx < i] = 0 // j是当前考虑元素的下标 int p0 = 0, curr = 0; // 对于所有 idx > k : nums[idx > k] = 2 int p2 = nums.length - 1; int tmp; while (curr <= p2) { if (nums[curr] == 0) { // 交换第 p0个和第curr个元素 // i++，j++ tmp = nums[p0]; nums[p0++] = nums[curr]; nums[curr++] = tmp; } else if (nums[curr] == 2) { // 交换第k个和第curr个元素 // p2-- tmp = nums[curr]; nums[curr] = nums[p2]; nums[p2--] = tmp; } else curr++; } } }复杂度分析
时间复杂度 :由于对长度 NN的数组进行了一次遍历，时间复杂度为O(N)O(N) 。
空间复杂度 :由于只使用了常数空间，空间复杂度为O(1)O(1) 。
78. 子集
给定一组不含重复元素的整数数组 nums，返回该数组所有可能的子集（幂集）。
说明：解集不能包含重复的子集。
示例:
输入: nums = [1,2,3] 输出: [ [3], [1], [2], [1,2,3], [1,3], [2,3], [1,2], [] ] class Solution { public List<List<Integer>> subsets(int[] nums) { List<List<Integer>> result = new ArrayList<>(); List<Integer> list = new ArrayList<>(); subsets(nums, 0, list, result); return result; } private void subsets(int[] nums, int index, List<Integer> list, List<List<Integer>> result) { if(index == nums.length) result.add(new ArrayList(list)); else { subsets(nums, index + 1, list, result); list.add(nums[index]); subsets(nums, index + 1, list, result); list.remove(list.size() - 1); } } }79. 单词搜索
给定一个二维网格和一个单词，找出该单词是否存在于网格中。
单词必须按照字母顺序，通过相邻的单元格内的字母构成，其中“相邻”单元格是那些水平相邻或垂直相邻的单元格。同一个单元格内的字母不允许被重复使用。
示例:
board = [ ['A','B','C','E'], ['S','F','C','S'], ['A','D','E','E'] ] 给定 word = "ABCCED", 返回 true. 给定 word = "SEE", 返回 true. 给定 word = "ABCB", 返回 false. public class Solution { public boolean exist(char[][] board, String word) { if(board == null || board.length == 0 || board.length * board[0].length < word.length()) return false; boolean[][] mark = new boolean[board.length][board[0].length]; boolean res = false; // iterate board, find the match starting character to pass to findWord function for(int i=0; i<board.length; i++) { for(int j=0; j<board[0].length; j++) { if(board[i][j] == word.charAt(0)) res = res || findWord(board, word, 0, i, j, mark); if(res) return res; } } return res; } public boolean findWord(char[][] board, String word, int wordIndex, int row, int col, boolean[][] markBoard) { // base case 1: if exceed word's length, meaning it is done and found the word if(wordIndex == word.length()) return true; /* base case 2: if this character is out of bound or * this character is not match to word's character or * hits character has been already visited */ if(row >= board.length || row < 0 || col >= board[0].length || col < 0 || word.charAt(wordIndex) != board[row][col] || markBoard[row][col]) return false; // mark this char as visited markBoard[row][col] = true; // follow top, right, bottom, left order to check character // if any direction future path return true, meaning no need to continue other directions if(findWord(board, word, wordIndex + 1, row - 1, col, markBoard) || // go top findWord(board, word, wordIndex + 1, row, col + 1, markBoard) || // go right findWord(board, word, wordIndex + 1, row + 1, col, markBoard) || // go bottom: findWord(board, word, wordIndex + 1, row, col - 1, markBoard)) // go left: { return true; } markBoard[row][col] = false; // clear the mark of this character // if this this character's all four directions path has failed, return false to last level return false; } }
