学无止境

# 题目描述 # 思路与题解 这题我承认我没有解出来，还是看了官方题解后才有思路的 🤣 怎么说呢，这道题如果你能转过弯，把它映射到我们前几道题所做的打家劫舍上，那这个题就很简单啦，关键就在于如何把这个题转换为打家劫舍～ 再看一遍题干， 你必须删除所有等于 nums[i] - 1 和 nums[i] + 1 的元素 ，意思不就是如果我们要获取 nums [i] 房屋的财产，那就不能获取 nums [i] 相邻两间房屋的财产了，所以我们的思路就是要把相同点数 i 累加起来，作为 nums [i]...

# 题目描述 # 思路与题解 比上一题多加了一些条件，但动态规划的思想不变，都是先求解子问题（小问题），然后逐步求解出一个复杂的问题（大问题）~ 上一题我们可以知道在当前 i 处能走到的最大距离，所以稍微一思考，只要后面走的距离在这最大距离之内，步数都不变；只有能走的最大距离不能满足 i 了，才把步数加一，同时更新 i 处能走到的最大距离，是不是很 easy~ class Solution {public: int jump(vector<int>& nums) { int n = nums.size(); if...

# 题目描述 # 思路与题解 经过前面几道题的熏陶，这类题感觉已经挺熟练了，动态规划就是先求解子问题，比如说一个长数组，我们先不要看那么多元素，可以就从有一个元素开始往后遍历求解，最后就可以求出一个复杂问题的答案了～～ 但是这题应该还有好多其他解法，比如说深度优先搜索应该也算一种，一直往前冲，冲不动了就回退，然后再往前冲～～ class Solution {public: bool canJump(vector<int>& nums) { int n = nums.size(); int limit = 0;...

# 题目描述 # 思路与题解 这道题看起来不难，不就在上一道题的基础上添加了首尾房间相邻的限制吗，但我尝试解了三次都失败了，太丢人了...

# 题目描述 # 思路与题解 和前面题的思路蛮像的，关键在于比大小，因为题目有不能偷盗相邻的两个房间的限制，所以比大小的关键就是 max(dp[i-1], dp[i-2] + nums[i]) ，dp [i] 就表示新增了第 i 个房间后的最大收益，所以如果我第 i 个房间不偷，我能得到的最大收益就是 dp [i-1]；如果我第 i 个房间偷了，那我 i-1 房间就不能偷了，所以我能得的最大收益就是 dp [i-2] + nums [i]，是不是很 easy~~ 当然啦，再稍微思考一下，可以用滚动数组把空间复杂度优化为 O (1) class Solution...

# 题目描述 # 思路与题解 这个题目描述的比较绕，如果有纸和笔的话，在纸上画一画会好很多，比如我胡乱画的如下 看了官方题解，思路才比较清晰了 上述代码的时间复杂度和空间复杂度都是 O (n)。但也可以用滚动数组的方式将空间复杂度优化到 O (1) class Solution {public: int minCostClimbingStairs(vector<int>& cost) { int n = cost.size(); int res[n+1]; res[0] = res[1] = 0; res[2]...

# 题目描述 # 思路与题解 n 阶，可以看成是 n-2 阶爬 2 阶后到达，也可以看成是 n-1 阶爬 1 阶后到达，所以就是 n-2 阶的爬取数 + n-1 阶的爬取数，翻译过来就是斐波那契数，easy~ class Solution {public: int climbStairs(int n) { //n 阶，可以看成是 n-2 阶爬 2 阶后到达 // 也可以看成是 n-1 阶爬 1 阶后到达 // 所以就是 n-2 阶的爬取数 + n-1 阶的爬取数 // 翻译过来就是斐波那契数，easy if (n < 4) return...

# 题目描述 # 思路与题解 和昨天的斐波那契数思路一样，用滚动数组的思想，关键点在于设置 p、q、t、r 的初值，我们知道，r = p + q + t，第一个要计算的值是 Fn (3)，T_3 = 0 + 1 + 1，这是滚动之后的，所以 p、q、t、r 的初值应该是 0、0、1、1，这样滚动过后才能变成 0、1、1，就能算出 Fn (3) = r = 0 + 1 + 1。Easy~ class Solution {public: int tribonacci(int n) { if (n < 2) return n; if (n ==...

# 题目描述 # 思路与题解 第一想到的应该就是递归，用递归尝试后爆溢栈了，于是便想到用一个数组记录下来已算出的斐波那契数。我犯的一个低级错误就是把 if (n == 1 || n == 0) return n; 刚开始没有放到 fib 函数里，导致系统输入 0 时，直接 n - 1 = -1，数组越界报错了 🤣 长时间不思考果然脑袋就变笨了 看了官方题解后又有了收获，用滚动数组的思想，就可以将递归函数转换为 for 循环，用自下而上的方法去求解子问题，秒的很 class Solution {public: int data[31]; bool flag[31];...

# 文章来源 The Economist: June 11th - 17th 2022 # 标题 The Capitol-riot hearings: High time for prime time 国会暴动听证会：黄金时间的到来 Why America’s probe into the attempted coup last year is needed, before it’s too late 为什么美国需要对去年的未遂政变进行调查，否则就太晚了 #...