lthero

LeetCodeCampsDay29贪心part03 有些题目有多个维度时，可以去去除一个维度（比如406） 而有些题目需要同时考虑左右相邻元素时，可以先从左向右、再从右向左遍历 134. 加油站 https://leetcode.cn/problems/gas-station/ 在一条环路上有 n 个加油站，其中第 i 个加油站有汽油 gas[i] 升。 你有一辆油箱容量无限的的汽车，从第 i 个加油站开往第 i+1 个加油站需要消耗汽油 cost[i] 升。你从其中的一个加油站出发，开始时油箱为空。 给定两个整数数组 gas 和 cost ，如果你可以按顺序绕环路行驶一周，则返回出发时加油站的编号，否则返回 -1 。如果存在解，则 保证 它是 唯一 的。 示例 1: 12345678910输入: gas = [1,2,3,4,5], cost = [3,4,5,1,2]输出: 3解释:从 3 号加油站(索引为 3 处)出发，可获得 4 升汽油。此时油箱有 = 0 + 4 = 4 升汽油开往 4 号加油站，此时油箱有 4 - 1 + 5 = 8 升汽油开往 0 号加油站，此时油箱 ...

LeetCodeCampsDay28贪心part02 覆盖范围的题目 122. 买卖股票的最佳时机 II https://leetcode.cn/problems/best-time-to-buy-and-sell-stock-ii/ 给你一个整数数组 prices ，其中 prices[i] 表示某支股票第 i 天的价格。 在每一天，你可以决定是否购买和/或出售股票。你在任何时候 最多 只能持有 一股 股票。你也可以先购买，然后在 同一天 出售。 返回 你能获得的 最大 利润 。 示例 1： 12345输入：prices = [7,1,5,3,6,4]输出：7解释：在第 2 天（股票价格 = 1）的时候买入，在第 3 天（股票价格 = 5）的时候卖出, 这笔交易所能获得利润 = 5 - 1 = 4。随后，在第 4 天（股票价格 = 3）的时候买入，在第 5 天（股票价格 = 6）的时候卖出, 这笔交易所能获得利润 = 6 - 3 = 3。最大总利润为 4 + 3 = 7 。 示例 2： 1234输入：prices = [1,2,3,4,5]输出：4解释：在第 1 天（股票价格 = ...

LeetCodeCampsDay27贪心part01 贪心算法理论与一些基础题目 什么是贪心 贪心的本质是选择每一阶段的局部最优，从而达到全局最优。 这么说有点抽象，来举一个例子： 例如，有一堆钞票，你可以拿走十张，如果想达到最大的金额，你要怎么拿？ 指定每次拿最大的，最终结果就是拿走最大数额的钱。 每次拿最大的就是局部最优，最后拿走最大数额的钱就是推出全局最优。 再举一个例子如果是 有一堆盒子，你有一个背包体积为n，如何把背包尽可能装满，如果还每次选最大的盒子，就不行了。这时候就需要动态规划。动态规划的问题在下一个系列会详细讲解。 贪心的例题 桌上有面值100，50，20，10，1的各种钞票各2张，如果只能拿5张，如何拿才能拿最多钱； 常识的思路肯定是优先拿最大的，然后次大的，先拿2张100，再2张50，一张20的； 贪心的套路（什么时候用贪心） 有没有什么套路可以一看就看出来是贪心。 说实话贪心算法并没有固定的套路。 所以唯一的难点就是如何通过局部最优，推出整体最优。 那么如何能看出局部最优是否能推出整体最优呢？有没有什么固定策略或者套路呢？ 不好意思，也没有！ 靠自己手动模拟 ...

刚出分，很激动，没想到口语居然帮我提分了； 从4月开始自己准备，没报班，每天坚持做听力和阅读，可惜临考试的两周时间内没怎么刷这两个，写作本来想最后一个月专项冲刺，但事儿太多被耽误 了… 基础：裸考六级426分，平时有看英文影片的习惯，读研后经常阅读英文文献 雅思复习经历 下面按类总结下我的复习雅思经历 单词：断断续续背了一些，但都没坚持下来；（后悔）单词非常重要，听力哪怕听出来但不会写也不行！ 听力：用的papa雅思，刷剑桥真题，从C9刷到C19，至少每个都刷了两遍；平时会看油管asmongold 阅读：也是papa雅思，刷真题，从C9到C18都刷了一遍； 写作：买了本simon的写作书，但咋说呢，记了一些模板但没法灵活应用；主要还是练少了… 口语：刚开始买个了语料库，按里面内容练习了半个多月，但记了忘，不会活用；直到…闲鱼买了口语老师的课，上了一课就知道我口语准备错方向了；之前死记硬背的口语语料不会灵活应用，跟着老师上了几节课，至少把口语回复的逻辑搞清楚了，感谢～口语就是得多说，并且不要背稿子～ 感受与教训 听力和阅读提分还是很快的，因为听力和阅读主要是“输入+处理”，对大家应该不 ...

LeetCodeCampsDay25回溯part04 491是去重复的另一种情况，此时是不能将数组先排序再判断 491. 非递减子序列 https://leetcode.cn/problems/non-decreasing-subsequences/ 给你一个整数数组 nums ，找出并返回所有该数组中不同的递增子序列，递增子序列中 至少有两个元素 。你可以按 任意顺序 返回答案。 数组中可能含有重复元素，如出现两个整数相等，也可以视作递增序列的一种特殊情况。 示例 1： 12输入：nums = [4,6,7,7]输出：[[4,6],[4,6,7],[4,6,7,7],[4,7],[4,7,7],[6,7],[6,7,7],[7,7]] 示例 2： 12输入：nums = [4,4,3,2,1]输出：[[4,4]] 提示： 1 <= nums.length <= 15 -100 <= nums[i] <= 100 回溯思路 本题目和90. 子集II有点像，但不同点是，本题不让排序，就没法使用nums[i] == nums[i - 1]来判断某个数字是否在 ...

LeetCodeCampsDay24回溯part03 再次使用了去重复的技巧，其中78,90两题目像是77.组合的变体，都是每次向path添加一个元素的类型； 而93 复原ip以及131. 分割回文串都是每次向path添加多个元素的类型 93. 复原 IP 地址 https://leetcode.cn/problems/restore-ip-addresses/ 有效 IP 地址 正好由四个整数（每个整数位于 0 到 255 之间组成，且不能含有前导 0），整数之间用 '.' 分隔。 例如："0.1.2.201" 和 "192.168.1.1" 是 有效 IP 地址，但是 "0.011.255.245"、"192.168.1.312" 和 "192.168@1.1" 是 无效 IP 地址。 给定一个只包含数字的字符串 s ，用以表示一个 IP 地址，返回所有可能的有效 IP 地址，这些地址可以通过在 s 中插入 '.' 来形成。你 不能 重新排序或删除 s 中的任何数字。你可以按 ...

LeetCodeCampsDay23回溯part02 40.组合总和2使用了去重复的技巧，而131分割回文串是每次向path添加多个元素的类型 39.和40都是每次向path添加一个元素的类型； 39. 组合总和 https://leetcode.cn/problems/combination-sum/ 给你一个 无重复元素 的整数数组 candidates 和一个目标整数 target ，找出 candidates 中可以使数字和为目标数 target 的 所有 不同组合 ，并以列表形式返回。你可以按 任意顺序 返回这些组合。 candidates 中的 同一个 数字可以 无限制重复被选取 。如果至少一个数字的被选数量不同，则两种组合是不同的。 对于给定的输入，保证和为 target 的不同组合数少于 150 个。 示例 1： 123456输入：candidates = [2,3,6,7], target = 7输出：[[2,2,3],[7]]解释：2 和 3 可以形成一组候选，2 + 2 + 3 = 7 。注意 2 可以使用多次。7 也是一个候选， 7 = 7 。仅有这两种组合 ...

LeetCodeCampsDay22回溯part01 包含回溯基础内容，虽然和递归还有点儿像的哦 理论基础 什么是回溯法 回溯法也可以叫做回溯搜索法，它是一种搜索的方式。 在二叉树系列中，我们已经不止一次，提到了回溯，例如二叉树：以为使用了递归，其实还隐藏着回溯 (opens new window)。 回溯是递归的副产品，只要有递归就会有回溯。 所以以下讲解中，回溯函数也就是递归函数，指的都是一个函数 在递归中必有回溯，只是之前都没有用到回溯的操作 回溯法的效率 回溯法的性能如何呢，这里要和大家说清楚了，虽然回溯法很难，很不好理解，但是回溯法并不是什么高效的算法。 因为回溯的本质是穷举，穷举所有可能，然后选出我们想要的答案，如果想让回溯法高效一些，可以加一些剪枝的操作，但也改不了回溯法就是穷举的本质。 那么既然回溯法并不高效为什么还要用它呢？ 因为没得选，一些问题能暴力搜出来就不错了，撑死了再剪枝一下，还没有更高效的解法。 此时大家应该好奇了，都什么问题，这么牛逼，只能暴力搜索 如何理解回溯法 回溯法解决的问题都可以抽象为树形结构，是的，我指的是所有回溯法的问题都可以抽象为树形结 ...

LeetCodeCampsDay21二叉树part08 平衡二叉树的构造；修剪二叉树（难度甚至比删除二叉树的节点要简单一些） 669. 修剪二叉搜索树 https://leetcode.cn/problems/trim-a-binary-search-tree/ 给你二叉搜索树的根节点 root ，同时给定最小边界low 和最大边界 high。通过修剪二叉搜索树，使得所有节点的值在[low, high]中。修剪树 不应该 改变保留在树中的元素的相对结构 (即，如果没有被移除，原有的父代子代关系都应当保留)。 可以证明，存在 唯一的答案 。 所以结果应当返回修剪好的二叉搜索树的新的根节点。注意，根节点可能会根据给定的边界发生改变。 示例 1： 12输入：root = [1,0,2], low = 1, high = 2输出：[1,null,2] 示例 2： 12输入：root = [3,0,4,null,2,null,null,1], low = 1, high = 3输出：[3,2,null,1] 提示： 树中节点数在范围 [1, 104] 内 0 <= Node.va ...

LeetCodeCampsDay20二叉树part07 235. 二叉搜索树的最近公共祖先 https://leetcode.cn/problems/lowest-common-ancestor-of-a-binary-search-tree/ 给定一个二叉搜索树, 找到该树中两个指定节点的最近公共祖先。 百度百科中最近公共祖先的定义为：“对于有根树 T 的两个结点 p、q，最近公共祖先表示为一个结点 x，满足 x 是 p、q 的祖先且 x 的深度尽可能大（一个节点也可以是它自己的祖先）。” 例如，给定如下二叉搜索树: root = [6,2,8,0,4,7,9,null,null,3,5] 示例 1: 123输入: root = [6,2,8,0,4,7,9,null,null,3,5], p = 2, q = 8输出: 6 解释: 节点 2 和节点 8 的最近公共祖先是 6。 示例 2: 123输入: root = [6,2,8,0,4,7,9,null,null,3,5], p = 2, q = 4输出: 2解释: 节点 2 和节点 4 的最近公共祖先是 2, 因为根据定义最 ...