Leetcode时间限制
注意:
⏰表示未完成
⭐表示重要
🌟表示超级重要
😄表示我的思路并且通过了
😭表示自己尝试的方法但是通不过
🙆♂表示他人的方法通过了
🙅♂表示他人的方法但没通过
💭表示只写了想法没写代码无论自己或者其他人的.
题号.题目
描述
样例
思想1名称(self
思路
描述
代码
\\语法, 以后搜索\\语法可以学习语法
\\思想, 学习思想
复杂度
- 时间: $$
- 空间: $$
思想2名称*
思路
描述
代码
复杂度
- 时间: $$
- 空间: $$
动态规划
509. 斐波那契数
斐波那契数，通常用 F(n) 表示，形成的序列称为 斐波那契数列 。该数列由 0 和 1 开始，后面的每一项数字都是前面两项数字的和。也就是：
F(0) = 0，F(1) = 1
F(n) = F(n - 1) + F(n - 2)，其中 n > 1
给你 n ，请计算 F(n) 。
动态规划
思路
使用状态转移方程计算.
代码
public int fib(int n) {
return fib1(n);
}
int fib1(int n) {
int []f = new int[n+1];
for(int i =0;i <= n; i++) {
if (i==0) f[i] = 0;
else if(i==1) f[i] = 1;
else{
f[i] = f[i-1]+f[i-2];
}
}
return f[n];
}
复杂度
- 时间: $O(N)$
- 空间: $O(N)$
动态规划+滚动数组
将空间复杂度将为$O(1)$.
递归
思路
根据状态转移方程递归求解
代码
public int fib(int n) {
return fib2(n);
}
int fib2(int n) {
if(n==0) {
return 0;
}else if(n==1) {
return 1;
}else{
return fib2(n-1)+fib2(n-2);
}
}
复杂度
- 时间: $O(N^2)$, 有h层高树, 每层$2^{i-1}$个节点(最后一层2个, 还要分n为奇偶).
- 空间: $O(H)$
递归其实非常的浪费时间, 因为在计算fib(n)时候会计算一遍第二项fib(n-2),但在计算fib2(n-1)的时候, 会再计算一遍第一项fib2(n-1).
graph TD 1((n))---2((n-1)) 1((n))---3((n-2)) 2((n-1))---4((n-2)) 2((n-1))---5((n-3=1)) 3((n-2))---6((n-3=1)) 3((n-2))---7((n-4=0)) 4((n-2))---8((n-3=1)) 4((n-2))---9((n-4=0))
递归的时间复杂度为递归的次数*递归的操作, 节点是为$O(N^2)$, 操作为加一次.
递归算法的空间复杂度=递归深度N*每次递归所要的辅助空间。 对于单线程来说，递归有运行时堆栈，求的是递归最深的那一次压栈所耗费的空间的个数，因为递归最深的那一次所耗费的空间足以容纳它所有递归过程。
递归+记忆化搜索*
思路
减少递归多重复算的那几次, 讲$O(N^2)$优化到$O(N)$.
代码
private int[] assistant_f;
public int fib(int n) {
assistant_f = new int[n+1];
return fib3(n);
}
int fib3(int n) {
if(n==0) {
return assistant_f[n]=0;
}else if(n==1) {
return assistant_f[n]=1;
}else{
return assistant_f[n] = fib3(n-1)+fib3(n-2);
}
}
复杂度
- 时间: $O(N)$
- 空间: $O(N)$
graph TD 1((n))---2((n-1)) 1((n))---3((n-2)) 2((n-1))---3((n-2)) 2((n-1))---8((n-3=1)) 3((n-2))---8((n-3=1)) 3((n-2))---9((n-4=0)) 3((n-2))---8((n-3=1)) 3((n-2))---9((n-4=0))
1137. 第 N 个泰波那契数
泰波那契序列 Tn 定义如下：
T0 = 0, T1 = 1, T2 = 1, 且在 n >= 0 的条件下 Tn+3 = Tn + Tn+1 + Tn+2
给你整数 n，请返回第 n 个泰波那契数 Tn 的值。
递归（self
思路
直接用if-elseif写递归，但是是三叉树，太慢了
代码
if(n==0)return 0;
else if(n==1) return 1;
else if(n==2) retirm 1;
else return tribonacci(n-3)+trbonacci(n-2)+tribonacci(n-1);
动态规划存储后随机访问(self
思路
用私有数组存储计算过的斐波那契数列
代码
class Solution {
private int[] assistanf_f;
public int tribonacci(int n) {
assistanf_f = new int[38];
assistanf_f[0] = 0;
assistanf_f[1] = 1;
assistanf_f[2] = 1;
for(int i = 3; i <= n; i++) {
assistanf_f[i] = assistanf_f[i-3]+assistanf_f[i-2]+assistanf_f[i-1];//思想
}
return assistanf_f[n];
}
}
复杂度
- 时间: $O(N)$
- 空间: $O(N)$
递归(推导二叉递归+滚动数组)
思路
直接用递归的话会超时，给定的通项公式可以进一步推导 T(n+3) = T(n+2) + T(n+1) +T(n+0)， T(n+4) = T(n+3) + T(n+2) + T(n+1)， 两者相减 T(n+4) - T(n+3) = T(n+3) - T(n)， 所以T(n) = 2T(n-1) - T(n+4)(n>=4)
代码
class Solution {
public int tribonacci(int n) {
if (n == 0) {
return 0;
}
if (n <= 2) {
return 1;
}
int p = 0, q = 0, r = 1, s = 1;
for (int i = 3; i <= n; ++i) {
p = q;
q = r;
r = s;
s = p + q + r;
}
return s;
}
}
复杂度
- 时间: $O(N)$
- 空间: $O(1)$
70. 爬楼梯
假设你正在爬楼梯。需要 n 阶你才能到达楼顶。
每次你可以爬 1 或 2 个台阶。你有多少种不同的方法可以爬到楼顶呢？
动态规划+辅助数组(self
思路
重要的是写出动态规划的转移方程, 而第n个阶梯只能由n-1走1步或者n-2走2步上来(n-2走1步再走1步不算, 因为已经算到n-1上面了), 也就是转移方程等于
$$
f(n) = f(n-1)+f(n-2)
$$
代码
class Solution {
private int [] f;
public int climbStairs(int n) {
f = new int[46];
f[1] = 1;
f[2] = 2;
for(int i =3; i <= n; i++) {
f[i]=f[i-1]+f[i-2];
}
return f[n];
}
}
复杂度
- 时间: $O(N)$
- 空间: $O(1)$
动态规划+滚动数组
思路
利用滚动数组节省辅助数组的空间
代码
class Solution {
public int climbStairs(int n) {
if(n == 1) return 1;
else if(n==2)return 2;
int a = 1, b = 1, c = 2;
for(int i =3; i <= n; i++) {
a = b;
b = c;
c = a+b;
}
return c;
}
}
复杂度
- 时间: $O(N)$
- 空间: $O(1)$
746. 使用最小花费爬楼梯
给你一个整数数组 cost ，其中 cost[i] 是从楼梯第 i 个台阶向上爬需要支付的费用。一旦你支付此费用，即可选择向上爬一个或者两个台阶。
你可以选择从下标为 0 或下标为 1 的台阶开始爬楼梯。
请你计算并返回达到楼梯顶部的最低花费。
示例 1：
输入：cost = [10,15,20]
输出：15
解释：你将从下标为 1 的台阶开始。
- 支付 15 ，向上爬两个台阶，到达楼梯顶部。
总花费为 15 。
动态规划找转移方程(self
思路
用一个sum数组记录到达第i个阶梯所需要的最小的总步数,
$$
sum[0] = cost[0] \
sum[1] = cost[1] \
sum[n] = min(sum[n-1],sum[n-2])+const[n]
$$
而最后的结果就是倒数两个阶梯的最小值(因为到达这两个阶梯后可以直接跨1步或者2步到达楼顶,楼顶就是数组的最大长度的那个位置)
代码
class Solution {
private int []sum;
public int minCostClimbingStairs(int[] cost) {
int length = cost.length;
sum = new int[1000];
for(int i = 0; i < length; i++) {
if(i==0) sum[0] = cost[0];
else if(i==1) sum[1] = cost[1];
else sum[i] = Math.min(sum[i-2],sum[i-1])+cost[i];
}
return Math.min(sum[length-2],sum[length-1]);
}
}
复杂度
- 时间: $O(N)$
- 空间: $O(N)$
动态规划另外一个转移方程
思路
官方题解另外一个转移方程, 无所谓啦, 我的也正确.
$$
p[i]=min(dp[i−1]+cost[i−1],dp[i−2]+cost[i−2])
$$
198. 打家劫舍
你是一个专业的小偷，计划偷窃沿街的房屋。每间房内都藏有一定的现金，影响你偷窃的唯一制约因素就是相邻的房屋装有相互连通的防盗系统，如果两间相邻的房屋在同一晚上被小偷闯入，系统会自动报警。
给定一个代表每个房屋存放金额的非负整数数组，计算你 不触动警报装置的情况下 ，一夜之内能够偷窃到的最高金额。
示例 1：
输入：[1,2,3,1]
输出：4
解释：偷窃 1 号房屋 (金额 = 1) ，然后偷窃 3 号房屋 (金额 = 3)。
偷窃到的最高金额 = 1 + 3 = 4 。
递归(self
思路
找递归终止条件和递归方程, 递归终止条件有
- e-s==0时, return nums[e];例如
[1] - e-s==1时, ruturn Math.max(nums[s],nums[e]); 例如
[1,3] - e-s==2时, return Math.max(nums[s]+nums[s+2], nums[s+1]);例如
[1,2,3] - else return Math.max(nums[s]+robHelp(s+2,e,nums), nums[s+1]+robHelp(s+3,e,nums)); 例如
[1,3,2,4]就相当于1与[2,4]和3与[4].
但是这样太费时间了, 样例正确但是太长的样例时间过不了.
代码
class Solution {
public int rob(int[] nums) {
return robHelp(0,nums.length-1,nums);
}
public int robHelp(int s, int e, int [] nums) {
if(e-s==0) return nums[s];
else if(e-s==1) return Math.max(nums[s],nums[e]);
else if(e-s==2) return Math.max(nums[s]+nums[s+2], nums[s+1]);
else return Math.max(nums[s]+robHelp(s+2,e,nums), nums[s+1]+robHelp(s+3,e,nums));
}
}
复杂度
- 时间: 分析不出
动态规划找动态方程*
思路
样例为[0,1,2,3,4,5], 则dp[i]表示到达此屋时能偷到的最大金钱数, 则
$$
dp[i] = max(dp[i-2]+nums[i],dp[i-1])
$$
很好理解, dp[i]就是要么是dp[i-2]再加nums[i],要么是dp[i-1]两个中的最大值(第i个不偷了)
代码
class Solution {
public int rob(int[] nums) {
int [] dp = new int[1001];
for(int i =0; i < nums.length; i++) {
if(i==0) dp[i] = nums[i];
else if(i==1) dp[i] = Math.max(nums[0],nums[1]);
else dp[i] = Math.max(dp[i-2]+nums[i],dp[i-1]);
}
return dp[nums.length-1];
}
}
复杂度
- 时间: $O(N)$
- 空间: $O(N)$
动态规划滑动数组
代码
class Solution {
public int rob(int[] nums) {
if(nums.length==1) return nums[0];
else if(nums.length==2) return Math.max(nums[0], nums[1]);
int a = 0, b = 0, c=0;
for(int i =2; i < nums.length; i++) {
if (i <=2) {
a = nums[0];
b = Math.max(nums[0],nums[1]);
}else{
a = b;
b = c;
}
c = Math.max(a+nums[i], b);
}
return c;
}
}
复杂度
- 时间: $O(N)$
- 空间: $O(1)$
执行用时：0 ms, 在所有 Java 提交中击败了100.00% 的用户
内存消耗：35.9 MB, 在所有 Java 提交中击败了34.18% 的用户(不采用滑动数组的话是5%)
213. 打家劫舍 II
你是一个专业的小偷，计划偷窃沿街的房屋，每间房内都藏有一定的现金。这个地方所有的房屋都 围成一圈 ，这意味着第一个房屋和最后一个房屋是紧挨着的。同时，相邻的房屋装有相互连通的防盗系统，如果两间相邻的房屋在同一晚上被小偷闯入，系统会自动报警 。
给定一个代表每个房屋存放金额的非负整数数组，计算你 在不触动警报装置的情况下 ，今晚能够偷窃到的最高金额。
示例 1：
输入：nums = [2,3,2]
输出：3
解释：你不能先偷窃 1 号房屋（金额 = 2），然后偷窃 3 号房屋（金额 = 2）, 因为他们是相邻的。
动态规划+首尾处理(self
思路
要么不偷第一个,要么不偷最后一个, 要么两个都不偷(肯定比前两者小), 所以只需要比较去除首尾的打家劫舍两个中取最大的即可.
代码
class Solution {
public int rob(int[] nums) {
int[]nums1 = new int[nums.length-1];
int[]nums2 = new int[nums.length-1];
if(nums.length==1) return nums[0];
else if (nums.length==2) return Math.max(nums[0], nums[1]);
System.arraycopy(nums, 0, nums1, 0 ,nums.length-1);//语法
int result1 = robHelp(nums1);
System.arraycopy(nums, 1, nums2, 0, nums.length-1);
int result2 = robHelp(nums2);
return Math.max(result1,result2);
}
public int robHelp(int[] nums) {
int[] dp = new int[nums.length];
for(int i = 0; i < nums.length; i++) {
if (i==0) dp[i] = nums[0];
else if(i==1)dp[i] = Math.max(nums[0], nums[1]);
else dp[i] = Math.max(dp[i-2]+nums[i], dp[i-1]);
}
return dp[nums.length-1];
}
}
复杂度
- 时间: $O(N)$
- 空间: $O(N)$
740. 打家劫舍Ⅳ(删除并获得点数
给你一个整数数组 nums ，你可以对它进行一些操作。
每次操作中，选择任意一个 nums[i] ，删除它并获得 nums[i] 的点数。之后，你必须删除 所有 等于 nums[i] - 1 和 nums[i] + 1 的元素。
开始你拥有 0 个点数。返回你能通过这些操作获得的最大点数。
示例 1：
输入：nums = [3,4,2]
输出：6
解释：
删除 4 获得 4 个点数，因此 3 也被删除。
之后，删除 2 获得 2 个点数。总共获得 6 个点数。
示例 2：
输入：nums = [2,2,3,3,3,4]
输出：9
解释：
删除 3 获得 3 个点数，接着要删除两个 2 和 4 。
之后，再次删除 3 获得 3 个点数，再次删除 3 获得 3 个点数。
总共获得 9 个点数.
提示：
1 <= nums.length <= 2 * 1041 <= nums[i] <= 104
观察数据下标计数(self
思路
通过下标计数记录数字的权重, 相当于money, 然后就转化为打家劫舍了
代码
class Solution {
public int deleteAndEarn(int[] nums) {
int [] money = new int[10001]; //语法, 新申请后默认为0
for(int i = 0; i < nums.length; i++) {
money[nums[i]]+=nums[i];
}
return robHelp(money);
}
public int robHelp(int[] nums) {
int[] dp = new int[nums.length];
for(int i = 0; i < nums.length; i++) {
if (i==0) dp[i] = nums[0];
else if(i==1)dp[i] = Math.max(nums[0], nums[1]);
else dp[i] = Math.max(dp[i-2]+nums[i], dp[i-1]);
}
return dp[nums.length-1];
}
}
复杂度
- 时间: $O(N)$
- 空间: $O(N)$
337. 打家劫舍 III
在上次打劫完一条街道之后和一圈房屋后，小偷又发现了一个新的可行窃的地区。这个地区只有一个入口，我们称之为“根”。 除了“根”之外，每栋房子有且只有一个“父“房子与之相连。一番侦察之后，聪明的小偷意识到“这个地方的所有房屋的排列类似于一棵二叉树”。 如果两个直接相连的房子在同一天晚上被打劫，房屋将自动报警。
计算在不触动警报的情况下，小偷一晚能够盗取的最高金额。
动态规划找(self
思路
动态方程是某个节点的取值为本节点的值加上四个子孙的值与两个孩子的值的最大值, 但是使用递归会超时, 所以需要记忆化, 记忆化的方法是精髓, 可以用哈希表来记忆化.
代码核心
动态方程是某个节点的取值为本节点的值加上四个子孙的值与两个孩子的值的最大值.
class Solution {
public int rob(TreeNode root) {
return robHelp(root);
}
public int robHelp(TreeNode root) {
if(root==null) return 0;
else if(root.left==null&&root.right==null){
return root.val;
}else if(root.left==null&&root.right!=null) {
return Math.max(root.val+robHelp(root.right.left)+robHelp(root.right.right), robHelp(root.right));
}else if(root.left!=null&&root.right==null) {
return Math.max(robHelp(root.left),root.val+robHelp(root.left.left)+robHelp(root.left.right));
}else{
return Math.max(root.val+robHelp(root.left.left)+robHelp(root.left.right)+robHelp(root.right.left)+robHelp(root.right.right), robHelp(root.left)+robHelp(root.right));
}
}
}
因为动态规划递归调用重复计算了很多, 所以需要用一个数据结构持久化, 我刚开始想的是构造一颗相同结构的树, 只不过树的域中多加一个int money的数据域, 然后每次用这个money域而不是递归调用, 但是没构造好, 太麻烦了,经过提示可以用一个哈希表来存储树节点对应的money, 如果有的话就不计算了, 没有的话就再计算, 但是发现代码是一坨屎山.看看得了.
代码
class Solution {
Map<TreeNode, Integer> money;
public int rob(TreeNode root) {
money = new HashMap<TreeNode, Integer>(); //语法, //思想
return robHelp(root);
}
public int robHelp(TreeNode root) {
if(root==null) return 0;
else if(root.left==null&&root.right==null){
money.put(root,root.val);
return money.get(root);
}else if(root.left==null&&root.right!=null) {
int right_left = money.get(root.right.left)==null?robHelp(root.right.left):money.get(root.right.left);
int right_right = money.get(root.right.right)==null?robHelp(root.right.right):money.get(root.right.right);
int root_right = money.get(root.right)==null?robHelp(root.right):money.get(root.right);
money.put(root, Math.max(root.val+right_left+right_right, root_right));
return money.get(root);
}else if(root.left!=null&&root.right==null) {
int left_left = money.get(root.left.left)==null?robHelp(root.left.left):money.get(root.left.left);
int left_right = money.get(root.left.right)==null?robHelp(root.left.right):money.get(root.left.right);
int root_left = money.get(root.left)==null?robHelp(root.left):money.get(root.left);
money.put(root, Math.max(root.val+left_left+left_right, root_left));
return money.get(root);
}else{
int right_left = money.get(root.right.left)==null?robHelp(root.right.left):money.get(root.right.left);
int right_right = money.get(root.right.right)==null?robHelp(root.right.right):money.get(root.right.right);
int root_right = money.get(root.right)==null?robHelp(root.right):money.get(root.right);
int left_left = money.get(root.left.left)==null?robHelp(root.left.left):money.get(root.left.left);
int left_right = money.get(root.left.right)==null?robHelp(root.left.right):money.get(root.left.right);
int root_left = money.get(root.left)==null?robHelp(root.left):money.get(root.left);
money.put(root, Math.max(root.val+left_left+left_right+right_left+right_right, root_left+root_right));
return money.get(root);
}
}
}
复杂度
- 时间: $$
- 空间: $$
动态规划另一个转移方程(待
思路
简化一下这个问题：一棵二叉树，树上的每个点都有对应的权值，每个点有两种状态（选中和不选中），问在不能同时选中有父子关系的点的情况下，能选中的点的最大权值和是多少。
我们可以用 f(o) 表示选择 o节点的情况下，o 节点的子树上被选择的节点的最大权值和；g(o)表示不选择 o 节点的情况下，o 节点的子树上被选择的节点的最大权值和；l 和 r 代表 o的左右孩子。
当 o 被选中时，o的左右孩子都不能被选中，故 ooo 被选中情况下子树上被选中点的最大权值和为 l和 r 不被选中的最大权值和相加，即 $$f(o)=g(l)+g(r)$$
当 o不被选中时，o 的左右孩子可以被选中，也可以不被选中。对于 oo的某个具体的孩子 x，它对 o的贡献是 xxx 被选中和不被选中情况下权值和的较大值。故 $$g(o)=max{f(l),g(l)}+max{f(r),g(r)}$$
代码
class Solution {
Map<TreeNode, Integer> f = new HashMap<TreeNode, Integer>();
Map<TreeNode, Integer> g = new HashMap<TreeNode, Integer>();
public int rob(TreeNode root) {
dfs(root);
return Math.max(f.getOrDefault(root, 0), g.getOrDefault(root, 0));
}
public void dfs(TreeNode node) {
if (node == null) {
return;
}
dfs(node.left);
dfs(node.right);
f.put(node, node.val + g.getOrDefault(node.left, 0) + g.getOrDefault(node.right, 0));
g.put(node, Math.max(f.getOrDefault(node.left, 0), g.getOrDefault(node.left, 0)) + Math.max(f.getOrDefault(node.right, 0), g.getOrDefault(node.right, 0)));
}
}
作者：LeetCode-Solution
链接：https://leetcode-cn.com/problems/house-robber-iii/solution/da-jia-jie-she-iii-by-leetcode-solution/
来源：力扣（LeetCode）
著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。
复杂度
- 时间: $O(N)$
- 空间: $O(N)$
欢迎在评论区中进行批评指正，转载请注明来源，如涉及侵权，请联系作者删除。
