林重笑

1005.K次取反后最大化的数组和文章：9. K次取反后最大化的数组和 题目：1005. K 次取反后最大化的数组和 【思路】 局部最优推出全局最优 题目蕴含了两次取反： 1.数组里有正数和负数，我们优先对负数进行取反。优先找绝对值最大的负数进行取反。 2.数组里面都是正数，我们优先对最小的正数进行反复取反。消耗取反次数。 步骤： 1.按数组绝对值的大小进行排序 2.对负数进行取反 以上完成第一次贪心的操作 3.k还没用完，（k是奇数）取最小的-1，（k是偶数）不用修改数组，完成第二次贪心，直接求和返回* 我觉得本题的难度在于怎么让数组按绝对值大小进行排序&&求和返回 Java实现 //数组按绝对值从大到小排序 nums = IntStream.of(nums).boxed().sorted((o1,o2) -> Math.abs(o2) - Math.abs(o1)).mapToInt(Integer::intValue).toArray(); IntStream.of(nums) 将整数数组 nums 转换为一个 ...

122.买卖股票的最佳时期II文章：6. 买卖股票的最佳时机II 题目：122. 买卖股票的最佳时机 II 【思路】 买卖股票可以使用贪心思路。 用区间的思维显示收获的利润 -> 我们可以转化为每天收获的利润和。 收集每天收获的正利润。 Java实现 123456789class Solution { public int maxProfit(int[] prices) { int res= 0; for(int i= 1;i < prices.length;i++){ res += Math.max(prices[i]-prices[i-1],0); } return res; }} Go实现 1234567891011121314func maxProfit(prices []int) int { res := 0 for i:=1;i < len(prices);i++{ ...

贪心算法理论基础1. 贪心算法理论基础什么是贪心贪心的本质是选择每一阶段的局部最优解，从而达到全局最优。 贪心的套路（什么时候用贪心）说实话贪心算法并没有固定的套路。 所以唯一的难点就是如何通过局部最优，推出整体最优。 那么如何能看出局部最优是否能推出整体最优呢？有没有什么固定策略或者套路呢？ 不好意思，也没有！ 靠自己手动模拟，如果模拟可行，就可以试一试贪心策略，如果不可行，可能需要动态规划。 有同学问了如何验证可不可以用贪心算法呢？ 最好用的策略就是举反例，如果想不到反例，那么就试一试贪心吧。 贪心一般解题步骤贪心算法一般分四步： 将问题分解为若干个子问题 找出适合的贪心策略 求解每一个子问题的最优解 将局部最优解叠成全局最优解 455.分发饼干文章：2. 分发饼干 题目：455. 分发饼干 【思路】 Java实现 123456789101112131415class Solution { public int findContentChildren(int[] g, int[] s) { Arrays.sort(g); ...

332.重新安排行程文章：19. 重新安排行程 题目：332. 重新安排行程 【思路】 题目存在的几个问题： 1.一个行程中会出现回头，会形成一个圈，处理不好的话。 2.有多种解法，要返回字母序靠前排在前面的 3.使用回溯，终止条件是什么 4.如何遍历一个机场所对应的所有机场 Java实现 1234567891011121314151617181920212223242526272829303132class Solution { private LinkedList<String>res ; private LinkedList<String> path = new LinkedList<>(); public List<String> findItinerary(List<List<String>> tickets) { Collections.sort(tickets,(a,b)->a.get(1).compareTo(b.get(1))); ...

491.递增子序列文章：14. 递增子序列 题目：491. 递增子序列 【思路】 90.子集中我们是通过排序，再加一个标记数组来达到去重的目的。 而本题求自增长子序列，不能对原数组进行排列，排列完的数组不符合题意。 因此我们需要使用新的去重逻辑。 回溯三部曲 递归函数参数 本题求子序列，因此一个元素不能重复使用，需要使用startIndex来调整下一层递归的起始位置 终止条件 本题需要我们遍历整颗树形结构，终止条件那不需要return。 单层逻辑遍历 同一父节点下的同层上使用过的元素就不能再使用了。 去重：在树层上去重（该节点会包含3），在树枝上不去重。 Java实现 12345678910111213141516171819202122class Solution { List<List<Integer>>res = new ArrayList<>(); LinkedList<Integer>path = new LinkedList<>(); public List<Lis ...

93.复原IP地址文章：10. 复原IP地址 题目：93. 复原 IP 地址 【思路】 确定终止条件 IP一共有三个逗点，也就说明树的高度（深度）一共为3，那么当逗点为3时，前三个IP字段为合法字段，我们就需要对最后一个IP字段进行判断是否为合法ip字段，如果合法则说明当前整个路径path为 一个合法IP，添加入结果集即可。 Java实现 1234567891011121314151617181920212223242526272829303132class Solution { List<String> res = new ArrayList<>(); StringBuilder sb = new StringBuilder(); public List<String> restoreIpAddresses(String s) { dps(s,0,0); return res; } public void dps(String s ,int start ...

39.组合总和文章：7. 组合总和 题目：39. 组合总和 【思路】 需要剪枝：先将数组排好序sort.Ints(arr)，如果arr[i] > target的话，说明后面的值就不需要再去回溯了（因为当前值已经比target大了）。不剪枝的话会超过内存限制噢！ Java实现 1234567891011121314151617181920212223class Solution { List<List<Integer>> res = new ArrayList<>(); LinkedList<Integer> path = new LinkedList<>(); public List<List<Integer>> combinationSum(int[] candidates, int target) { Arrays.sort(candidates); backtracking(candidates,target,0); ...

216.组合总和III文章：4. 组合总和III 题目：216. 组合总和 III 【思路】 和77.组合相似的解法。 在写题目的过程中，经常把回溯函数的遍历起始索引写成startIndex，而我们需要写的是i。 startIndex是在同一个集合里面遍历，防止重复遍历 Java实现 1234567891011121314151617181920212223class Solution { List<List<Integer>>res = new ArrayList<>(); LinkedList<Integer> path = new LinkedList<>(); public List<List<Integer>> combinationSum3(int k, int n) { backtracking(k,n,1,0); return res; } public void backtracking(int ...

回溯理论基础回溯法（回溯搜索法），是一种搜索的方式。 只要有递归就会有回溯。 因此，回溯函数也就是递归函数，指的都是一个函数。 回溯的本质是穷举。 回溯法解决的问题 组合问题：N个数里面按一定规则找出k个数的集合。 切割问题：一个字符串按一定规则有几种切割方式。 子集问题：一个N个数的集合里有多少个符合条件的子集。 排列问题：N个数按一定规则全排列，有几种排列方式。 棋盘问题：N皇后，解数独等等 排列？组合？ 组合是不强调元素顺序的，排列是强调元素顺序的。 组合无序，排列有序 如何理解回溯法回溯法解决的问题都可以抽象为树形结构。 因为回溯法解决的都是在集合中递归查找子集，集合的大小就构成了树的宽度，递归的深度都构成了树的深度。 回溯三部曲 回溯函数模板返回值以及参数 名字：backtracking 返回值：一般为void 参数：一般先写逻辑，然后需要什么参数就填什么参数 终止条件 一般来说搜到叶子节点也就找到了满足条件的一条答案，把这个答案存放起来，并结束本层递归。 回溯搜索的遍历过程 回溯法一般是在集合中递归搜索，集合的大小构成了树的宽度，递归的深度构成了树的深度 1 ...

669.修建二叉树文章：31. 修剪二叉搜索树 题目：669. 修剪二叉搜索树 视频：你修剪的方式不对，我来给你纠正一下！| LeetCode：669. 修剪二叉搜索树_哔哩哔哩_bilibili 【常见误区】 不能直接return删除当前节点后的左右子树，有可能左右子树里面也有需要删除的节点。因此我们需要return的是当前函数（递归） Java实现 12345678910111213141516class Solution { public TreeNode trimBST(TreeNode root, int low, int high) { if(root == null)return null; if(root.val < low){ TreeNode right = trimBST(root.right,low,high); return right; } if(root.val > high){ ...