208、实现 Trie (前缀树)
思路代码时空复杂度备注 198、打家劫舍
思路代码时空复杂度备注 213、打家劫舍 II
思路代码时空复杂度备注 337、打家劫舍 III
思路代码时空复杂度备注 112、路径总和
思路代码时空复杂度备注 69、x 的平方根
思路代码时空复杂度备注 64、最小路径和
思路代码时空复杂度备注 208、实现 Trie (前缀树)
208、实现 Trie (前缀树)
Trie 树又叫字典树、前缀树、单词查找树，是一种二叉树衍生出来的高级数据结构，主要应用场景是处理字符串前缀相关的操作。
其每个节点包含以下字段：
指向子节点的指针数组children。对于本题而言，数组长度为 226，即小写英文字母的数量。此时children[0] 对应小写字母 a，children[1] 对应小写字母 b，…，children[25] 对应小写字母 z。布尔字段isEnd，表示该节点是否为字符串的结尾。
插入字符串
我们从字典树的根开始，插入字符串。对于当前字符对应的子节点，有两种情况：
子节点存在。沿着指针移动到子节点，继续处理下一个字符。子节点不存在。创建一个新的子节点，记录在children 数组的对应位置上，然后沿着指针移动到子节点，继续搜索下一个字符。
重复以上步骤，直到处理字符串的最后一个字符，然后将当前节点标记为字符串的结尾。
查找前缀
我们从字典树的根开始，查找前缀。对于当前字符对应的子节点，有两种情况：子节点存在。沿着指针移动到子节点，继续搜索下一个字符。子节点不存在。说明字典树中不包含该前缀，返回空指针。
重复以上步骤，直到返回空指针或搜索完前缀的最后一个字符。
若搜索到了前缀的末尾，就说明字典树中存在该前缀。此外，若前缀末尾对应节点的isEnd 为真，则说明字典树中存在该字符串。 代码
class Trie { private Trie[] children; private boolean isEnd; public Trie() { children = new Trie[26]; isEnd = false; } public void insert(String word) { Trie node = this; for (int i = 0; i < word.length(); i++) { char ch = word.charAt(i); int index = ch - 'a'; if (node.children[index] == null) { node.children[index] = new Trie(); } node = node.children[index]; } node.isEnd = true; } public boolean search(String word) { Trie node = searchPrefix(word); return node != null && node.isEnd; } public boolean startsWith(String prefix) { return searchPrefix(prefix) != null; } private Trie searchPrefix(String prefix) { Trie node = this; for (int i = 0; i < prefix.length(); i++) { char ch = prefix.charAt(i); int index = ch - 'a'; if (node.children[index] == null) { return null; } node = node.children[index]; } return node; }}
时空复杂度 备注 198、打家劫舍 198、打家劫舍
动态规划。
自顶向下状态： 当前房子索引。
选择： 抢or不抢。抢就不能再选相邻房间，要从下下个房间开始选择；不抢就放弃当前，从下一个房子开始选择。
base case： 走过了最后一间房。
优化重复子问题： 使用备忘录记录抢过的房间。自底向上
状态： 当前房子索引。
选择： 抢or不抢。抢就不能再选相邻房间，要从下下个房间开始选择；不抢就放弃当前，从下一个房子开始选择。
base case： 从结果往回推，走过了第一间房结束。
优化重复子问题： 只维护走一步、走两步的最大值 代码 自顶向下
class Solution { // 备忘录 private int[] memo; // 主函数 public int rob(int[] nums) { // 初始化备忘录 memo = new int[nums.length]; Arrays.fill(memo, -1); // 强盗从第 0 间房子开始抢劫 return dp(nums, 0); } // 返回 dp[start..] 能抢到的最大值 private int dp(int[] nums, int start) { if (start >= nums.length) { return 0; } // 避免重复计算 if (memo[start] != -1) return memo[start]; int res = Math.max(dp(nums, start + 1), nums[start] + dp(nums, start + 2)); // 记入备忘录 memo[start] = res; return res; }}
自底向上class Solution { public int rob(int[] nums) { int n = nums.length; // 记录 dp[i+1] 和 dp[i+2] int dp_i_1 = 0, dp_i_2 = 0; // 记录 dp[i] int dp_i = 0; for (int i = n - 1; i >= 0; i--) { dp_i = Math.max(dp_i_1, nums[i] + dp_i_2); dp_i_2 = dp_i_1; dp_i_1 = dp_i; } return dp_i; }}
时空复杂度 1.时间复杂度
O(n)
2.空间复杂度
方法一：O(n) 备忘录需要空间 。
方法二：O(1)
213、打家劫舍 II
首尾房间不能同时被抢，那么只可能有三种不同情况：要么都不被抢；要么第一间房子被抢最后一间不抢；要么最后一间房子被抢第一间不抢。事实上，只要比较情况二和情况三就行了，因为这两种情况对于房子的选择余地比情况一大呀，房子里的钱数都是非负数，能选择的房子多，最优决策结果肯定不会小。
代码class Solution{public int rob(int[] nums) { int n = nums.length; if (n == 1) return nums[0]; return Math.max(robRange(nums, 0, n - 2), robRange(nums, 1, n - 1));}// 仅计算闭区间 [start,end] 的最优结果int robRange(int[] nums, int start, int end) { int n = nums.length; int dp_i_1 = 0, dp_i_2 = 0; int dp_i = 0; for (int i = end; i >= start; i--) { dp_i = Math.max(dp_i_1, nums[i] + dp_i_2); dp_i_2 = dp_i_1; dp_i_1 = dp_i; } return dp_i;}}
时空复杂度 1.时间复杂度
O(n)，其中 n 是数组长度。需要对数组遍历两次，计算可以偷窃到的最高总金额。
2.空间复杂度
O(1)
337、打家劫舍 III
动态规划。
选择：
返回一个大小为 2 的数组 arr
arr[0] 表示不抢 root 的话，得到的最大钱数
arr[1] 表示抢 root 的话，得到的最大钱数
分别递归左右子树得到结果。
class Solution { public int rob(TreeNode root) { int[] res = dp(root); return Math.max(res[0], res[1]); } public int[] dp(TreeNode root) { if (root == null) return new int[]{0, 0}; int[] left = dp(root.left); int[] right = dp(root.right); // 抢，下家就不能抢了 int rob = root.val + left[0] + right[0]; // 不抢，下家可抢可不抢，取决于收益大小 int not_rob = Math.max(left[0],left[1]) + Math.max(right[0],right[1]); return new int[]{not_rob, rob}; }}
时空复杂度 1.时间复杂度
O(N)
2.空间复杂度
空间复杂度只有递归函数堆栈所需的空间 O(N)
112、路径总和
递归：输入一个根节点，返回该根节点到叶子节点是否存在一条和为 targetSum 的路径。每次向下走一个节点，将targetSum减去之前节点的val，直到到达根节点。
代码class Solution { public boolean hasPathSum(TreeNode root, int targetSum) { if(root==null) return false; if(root.left==null && root.right ==null) { return targetSum == root.val; } return hasPathSum(root.left,targetSum-root.val) || hasPathSum(root.right,targetSum-root.val); }}
时空复杂度 1.时间复杂度
O(N)，其中 N 是树的节点数。对每个节点访问一次。
2.空间复杂度
O(H)，其中 H是树的高度。空间复杂度主要取决于递归时栈空间的开销，最坏情况下，树呈现链状，空间复杂度为O(N)。平均情况下树的高度与节点数的对数正相关，空间复杂度为O(logN)。
69、x 的平方根
二分查找，由于 xx平方根的整数部分ans 是满足 k^2 ≤x 的最大k值，因此我们可以对 k进行二分查找，从而得到答案。
代码class Solution { public int mySqrt(int x) { int l = 0, r = x, ans = -1; while (l <= r) { int mid = l + (r - l)/2; if ((long) mid * mid <= x) { ans = mid; l = mid + 1; } else { r = mid - 1; } } return ans; }}
时空复杂度 1.时间复杂度
O(logx)，即为二分查找需要的次数。
2.空间复杂度
O(1)
64、最小路径和
动态规划：在二维矩阵中求最优化问题（最大值或者最小值），肯定需要递归（不断选择不同路径） + 备忘录（解决重叠子问题，防止重复访问）。
代码class Solution { int[][] memo; public int minPathSum(int[][] grid) { int m = grid.length; int n = grid[0].length; // 构造备忘录，初始值全部设为 -1,后续的值更新为到达当前下标的最小路径和 memo = new int[m][n]; for(int[] row:memo){ Arrays.fill(row,-1); } //从右下角往回反推，到右下角的最小路径和 = min（到上边位置的最小路径和，到左边位置的最小路径和）+ 右下角的值。 return dp(grid,m-1,n-1); } //grid数组，当前所在下标 public int dp(int[][] grid,int x,int y) { //base case if(x==0&&y==0) return grid[0][0]; //越界处理:如果索引出界，返回一个很大的值，保证在取 min 的时候不会被取到 if(x<0||y<0) return Integer.MAX_VALUE; // 避免重复计算 if (memo[x][y] != -1) { return memo[x][y]; } // 将计算结果记入备忘录 memo[x][y] = Math.min( dp(grid, x - 1, y), dp(grid, x, y - 1) ) + grid[x][y]; return memo[x][y]; }}
时空复杂度 1.时间复杂度
O(MN)
2.空间复杂度
O(MN)
1）构造备忘录，并初始化默认值
2）递归过程中，先查询备忘录，有直接返回，没有则将结果记录到备忘录。