目录方法一：双指针法 方法二：动态规划方法三：单调栈42.接雨水-力扣（LeetCode） 黑色的是柱子，蓝色的是雨水，我们先来观察一下雨水的分布情况:雨水落在凹槽之间，在一个凹槽的左右都会有两个柱子，两个柱子高度可能相同也可能不同，柱子的高低决定了凹槽的雨水的高度，雨水的高度等于两个柱子较低的高度。方法一：双指针法时间复杂度：O（N^2）;空间复杂度：O(1)；缺点：会超时;思想：统计各个所在位置的左边最高高度和右边最高位置（第一个和最后一个柱子所在位置不用统计，他们不可能会接收雨水），然后算出各个位置雨水面积（两边的最高高度的较小值-当前位置的柱子的面积），最后将各个位置的面积相加得到总面

代码随想录算法训练营第1天|LeetCode707.二分查找、LeetCode27.移除元素1、数组理论基础定义：数组是存放在连续内存空间上的相同类型数据的集合。获取：下标索引的方式。从0开始。删除/增添：需要移动其他元素的地址。不能删除，只能覆盖。vectorVSarray：vector是容器，底层实现是arrayJava中没有指针，且不对程序员暴露元素地址。2、LeetCode707.二分查找题目链接：https://leetcode.cn/problems/binary-search/文章讲解：https://programmercarl.com/0704.%E4%BA%8C%E5%88

279.完全平方数给你一个整数n，返回和为n的完全平方数的最少数量。完全平方数是一个整数，其值等于另一个整数的平方；换句话说，其值等于一个整数自乘的积。例如，1、4、9和16都是完全平方数，而3和11不是。示例1：输入：n=12输出：3解释：12=4+4+4示例2：输入：n=13输出：2解释：13=4+9提示：11n104这道题采用动态规划进行求解，不能用贪心去做，否则结果是错误的，反例就是示例1，如果用贪心，12=9+1+1+1，需要4个数。另外一种方法是利用了一个数学定理(四平方和定理)，见https://leetcode.cn/problems/perfect-squares/solut

46.携带研究材料（第六期模拟笔试）题目描述小明是一位科学家，他需要参加一场重要的国际科学大会，以展示自己的最新研究成果。他需要带一些研究材料，但是他的行李箱空间有限。这些研究材料包括实验设备、文献资料和实验样本等等，它们各自占据不同的空间，并且具有不同的价值。小明的行李空间为N，问小明应该如何抉择，才能携带最大价值的研究材料，每种研究材料只能选择一次，并且只有选与不选两种选择，不能进行切割。输入描述第一行包含两个正整数，第一个整数M代表研究材料的种类，第二个正整数N，代表小明的行李空间。第二行包含M个正整数，代表每种研究材料的所占空间。第三行包含M个正整数，代表每种研究材料的价值。输出描述输

我有一个管理大型软件项目的用户首选项的类。项目中可能需要从持久存储中设置或检索用户首选项的任何类都将调用此类的静态方法。这种集中管理允许以编程方式完全删除首选项-如果每个首选项都在接近其使用代码的地方处理，散布在整个项目中，这是不可能的。我在这个过程中遇到了中心化设计的另一个含义。该软件有一个公共(public)API。该API可以在jar中自行提供。该API中的类可能引用pref管理类。因此，pref管理器必须放在APIjar中。每个首选项都可能有一个默认值。在软件启动时，可能会计算该默认值。该算法取决于偏好，因此倾向于驻留在使用代码附近。因此，如果pref管理器需要提供默认值，它会

层序遍历理论讲解LeetCode226.翻转二叉树文章讲解：代码随想录(programmercarl.com)视频讲解：听说一位巨佬面Google被拒了，因为没写出翻转二叉树|LeetCode：226.翻转二叉树_哔哩哔哩_bilibili思路关键在于遍历顺序，只要把每一个节点的左右孩子翻转一下，就可以达到整体翻转的效果。这道题目使用前序遍历和后序遍历都可以。代码如下： ​​​​​​LeetCode101.对称二叉树文章讲解：代码随想录(programmercarl.com)视频讲解：同时操作两个二叉树|LeetCode：101.对称二叉树_哔哩哔哩_bilibili思路本题遍历只能是“后序遍

17.电话号码的字母组合题目给定一个仅包含数字2-9的字符串，返回所有它能表示的字母组合。答案可以按任意顺序返回。给出数字到字母的映射如下（与电话按键相同）。注意1不对应任何字母。  题目链接 .-力扣（LeetCode）文字和画图分析这道题明显是需要互相匹配，如字符串“23”,对应“abc”和“def”。这个时候我们就想到跟循环有关，但是我们很难控制出for循环的个数，所以最好的办法就是采用递归参数我们需要：digits（含2-9的字符串），di（表示层数)，tmp（每一层对应的字符串），t(接收每一次递归结束时的字符串)注意事项：tmp不要传引用,便于递归结束时可以对应到上一层的字符串t需

动态规划（DynamicProgramming,DP）是解决复杂问题的一个强大工具，它将问题分解成更小的子问题，并使用这些子问题的解决方案来构建整体问题的解决方案。在深入探讨最短编辑距离问题之前，让我们先理解什么是动态规划，以及如何通过动态规划的视角来看待这个问题。原题链接：72.编辑距离-力扣（LeetCode）动态规划分析动态规划的核心动态规划通常用于求解最优化问题。其核心思想包括两个主要部分：最优子结构：问题的最优解包含其子问题的最优解。这意味着我们可以通过合并子问题的最优解来构造整个问题的最优解。重叠子问题：在解决问题的过程中，问题被分解成若干个子问题，其中很多子问题是重复的。最短编辑

预备工作安装虚拟机工具VMware或者VirtualBox。新建虚拟机，内存16GB及以上，硬盘100GB及以上。安装Ubuntu，推荐使用20.04版本。用户名不能包含中文。启动并进入Ubuntu虚拟机，以下步骤将在Ubuntu虚拟机中进行操作。一、将Shell环境修改为bashsudodpkg-reconfiguredash选择“No”。二、替换Ubuntu软件源在“https://mirrors.ustc.edu.cn/repogen/”下载对应版本最新的源。在下载好的文件（sources.list）所在的位置开启一个终端窗口，执行下列命令。备份原始文件：sudocp/etc/apt/s

算法沉淀——动态规划之其它背包问题与卡特兰数二维费用的背包问题01.一和零02.盈利计划似包非包组合总和Ⅳ卡特兰数不同的二叉搜索树二维费用的背包问题01.一和零题目链接：https://leetcode.cn/problems/ones-and-zeroes/给你一个二进制字符串数组strs和两个整数m和n。请你找出并返回strs的最大子集的长度，该子集中最多有m个0和n个1。如果x的所有元素也是y的元素，集合x是集合y的子集。示例1：输入：strs=["10","0001","111001","1","0"],m=5,n=3输出：4解释：最多有5个0和3个1的最大子集是{"10","0001