之和 随想录 随想day7

455.分发饼干 自己的 思路： 先排序，然后每个孩子找到他能满足的胃口饼干，找到了之后，孩子向前，饼干向前 代码： 1 int findContentChildren(vector<int>& g, vector<int>& s) 2 { 3 int result = 0; 4 sort(g.be ......

332.重新安排行程（可跳过） 难点： 1，解决死锁问题，我采用的是 selected，但是不会出现A->B->A这条信息 2，即使出现A-》B-》A，因为是有多条路径，所以无法找到合适的含有全部机场的路径 3，保证顺序 代码： 1 //机票信息 -》 一条遍历所有机场的路径 2 //步骤： 3 / ......

647. 回文子串 516.最长回文子序列 动态规划总结篇 647. 回文子串 dp[i][j]为[i,j]是否为回文串 这里要注意的是我们的遍历顺序，不能是i一遍，j一遍这样，因为会包含后面的信息 所以我们这里选择的是先遍历长度，然后再遍历首字符 class Solution: def count ......

###1. 状态压缩 + 动态规划 顺序不重要，依次枚举数组1的每个数，和数组2进行组合计算 ``` class Solution { public: int minimumXORSum(vector& nums1, vector& nums2) { int n = nums1.size(); if ......

491.递增子序列 此题的难点： 1，前提需要保留原有顺序 2，保证递增 3，保证去重 注意： 去重一定要有set的同时保证有顺序 代码： 1 void findSubsequences_trackBack(vector<int>& nums, int startIndex, vector<int> ......

392.判断子序列 115.不同的子序列 583. 两个字符串的删除操作 72. 编辑距离 编辑距离总结篇 392.判断子序列 和昨天的最长重复子串一样，只要计算两者的重复长度是不是和s一样就行了。但是还是不如双指针的时间复杂度 O(nm) O(nm) class Solution: def isS ......

392.判断子序列 115.不同的子序列 583. 两个字符串的删除操作 72. 编辑距离 编辑距离总结篇 392.判断子序列 和昨天的最长重复子串一样，只要计算两者的重复长度是不是和s一样就行了。但是还是不如双指针的时间复杂度 O(nm) O(nm) class Solution: def isS ......

# 数组 ## 704. 二分查找 给定一个 `n` 个元素有序的（升序）整型数组 `nums` 和一个目标值 `target` ，写一个函数搜索 `nums` 中的 `target`，如果目标值存在返回下标，否则返回 `-1`。 **示例 1:** ``` 输入: nums = [-1,0,3,5 ......

93.复原IP地址 思路： 先考虑合法的情况，然后再依次往path里面加字符，如果它的长度>4但是还没有到最末尾，也就是说他是错的，也就return出去 代码： 1 //根据给定的一组字符串，分出来可能正确的IP 2 //思路：切割，[start, i]，其中长度为0-3， 3 //判断是否满足条件 ......

第九章 动态规划part12 ● 309.最佳买卖股票时机含冷冻期 ● 714.买卖股票的最佳时机含手续费 ● 总结 309.最佳买卖股票时机含冷冻期 本题加了一个冷冻期，状态就多了，有点难度，大家要把各个状态分清，思路才能清晰 视频讲解： https://programmercarl.com/03 ......

第九章 动态规划part15 ● 392.判断子序列 ● 115.不同的子序列 详细布置 392.判断子序列 这道题目算是 编辑距离问题 的入门题目（毕竟这里只是涉及到减法），慢慢的，后面就要来解决真正的 编辑距离问题了 https://programmercarl.com/0392.%E5%88% ......

第九章 动态规划part16 ● 583. 两个字符串的删除操作 ● 72. 编辑距离 ● 编辑距离总结篇 详细布置 583. 两个字符串的删除操作 本题和动态规划：115.不同的子序列 相比，其实就是两个字符串都可以删除了，情况虽说复杂一些，但整体思路是不变的。 72. 编辑距离 最终我们迎来了编 ......

300.最长递增子序列 674. 最长连续递增序列 718. 最长重复子数组 1143.最长公共子序列 1035.不相交的线 53. 最大子序和 动态规划 300.最长递增子序列 dp[i]：以nums[i]为尾的最大上升子序列 如果前面的nums[j]<nums[i] : dp[i] = max( ......

1. 两数之和 给定一个整数数组 nums 和一个整数目标值 target，请你在该数组中找出 和为目标值 target 的那 两个 整数，并返回它们的数组下标。 你可以假设每种输入只会对应一个答案。但是，数组中同一个元素在答案里不能重复出现。 你可以按任意顺序返回答案。 示例 1： 输入：nums ......

问题：给定一个整数数组 nums 和一个整数目标值 target，请你在该数组中找出 和为目标值 target 的那 两个 整数，并返回它们的数组下标。 你可以假设每种输入只会对应一个答案。但是，数组中同一个元素在答案里不能重复出现。 你可以按任意顺序返回答案。 思考： 1.利用暴力法，双指针，一个 ......

根据 $P_i$ 是个排列，那将 $i$ 和 $P_i$ 进行连边之后不难发现图是由许多环构成的。 则若 $i$ 为 `(`，$P_i$ 则肯定为 `)`，$P_j = i$ 的 $j$ 肯定也为 `)`，否则就会出现度数为 $2$ 的情况。 所以发现一个点与相邻两个点的状态是恰好相反的，即确定环上 ......

39. 组合总和 思路： 虽然可以是重复的，但是考虑到组合没有顺序这一说，所以还是要保留startIndex， sum不要再遍历一遍，再相加，应该跟随path，一起相加 代码： 1 void combinationSum_trackBack(vector<int>& candidates, int ......

给定一个列表为nums = [2, 7, 11, 15]，目标值target = 9，找出列表中任意2数之和等于9的元素以及所在位置 思路：双重遍历去一对一的比较判断 1 nums = [2, 7, 11, 15, 1, 8, 2] 2 target = 9 3 list_new = [] 4 de ......

121. 买卖股票的最佳时机 122.买卖股票的最佳时机II 123.买卖股票的最佳时机III 188.买卖股票的最佳时机IV 309.最佳买卖股票时机含冷冻期 714.买卖股票的最佳时机含手续费 总结 121. 买卖股票的最佳时机 全程只能买卖一次 贪心算法 这个算法的写法也非常有意思！左边小右边 ......

给定一个整数数组 nums 和一个整数目标值 target，请你在该数组中找出 和为目标值 target 的那 两个 整数，并返回它们的数组下标。 你可以假设每种输入只会对应一个答案。但是，数组中同一个元素在答案里不能重复出现。 你可以按任意顺序返回答案。 ``` 示例 1： 输入：nums = [ ......

216.组合总和III 思路： 很像上一个组合类型的题目，唯一不同的就是自己写一个sum 代码： 1 void convertBST_cur(TreeNode* root, vector<TreeNode*>& nodes) 2 { 3 if (!root) return ; 4 if (root- ......

198.打家劫舍 213.打家劫舍II 337.打家劫舍III 198.打家劫舍 class Solution: def rob(self, nums: List[int]) -> int: n = len(nums) if n == 0: return 0 dp = [0 for _ in ran ......

回溯——组合 思路： 套了K次的循环，如何对K次循环呢，就需要一个startIndex，用它来控制从哪里开始 代码： 1 void combine_backTrack(int n, int k, int startIndex, vector<int>& path, vector<vector<int ......

完全背包 ● 518. 零钱兑换 II ● 377. 组合总和 Ⅳ ● 70. 爬楼梯 （进阶） ● 322. 零钱兑换 ● 279.完全平方数 ● 139.单词拆分 ● 关于多重背包，你该了解这些！ ● 背包问题总结篇！ 完全背包 有N件物品和一个最多能背重量为W的背包。第i件物品的重量是weig ......

669. 修剪二叉搜索树 思路 递归法： 需要思考清楚，如果当前节点<low，那么就返回递归它的右节点，而不是自己取判断，找出来一个合适的节点，这样的话会越想越乱 代码： 1 TreeNode* trimBST_cursor(TreeNode* root, int low, int high) { ......

235. 二叉搜索树的最近公共祖先 思路： 因为是二叉搜索树，所以公共祖先一定是位于这两个节点区间中的 问题： 为什么第一个是这两个中间的例子，就是公共祖先呢？因为是最先符合要求的， 代码： 1 TreeNode* lowestCommonAncestor(TreeNode* root, TreeN ......

01背包问题，你该了解这些！ 01背包问题，你该了解这些！ 滚动数组 01 背包 有n件物品和一个最多能背重量为w 的背包。第i件物品的重量是weight[i]，得到的价值是value[i] 。每件物品只能用一次，求解将哪些物品装入背包里物品价值总和最大。 二维dp数组01背包 1. 确定dp数组以 ......

530.二叉搜索树的最小绝对差 思路： 根据二叉搜素树的特点，直接中序遍历，就是有序数组，然后两个节点进行比较，就可以 代码： 1 int getMinimumDifference(TreeNode* root) { 2 if(!root) return 0; 3 int result = INT_ ......

# 0 前言 开源之夏落选给我带来的打击实在是太大了，我一下子失去了这个暑假的奋斗目标以及动力，我不知道做什么项目了，我也不知道该往哪个方向发展了 我是悲观的人 这段时间还要军训，身心俱疲 # 1 一些记录 1. [如何参与一个顶级开源项目](https://crossoverjie.top/201 ......

654.最大二叉树 比较简单，直接上代码 1 TreeNode* constructMax_cursor(vector<int>& nums) 2 { 3 if (nums.size() == 0) return NULL; 4 //getMaxNum 5 int index = 0; 6 int ......