Abacteria的学习小站

分割等和子集 给你一个 只包含正整数 的 非空 数组 nums 。请你判断是否可以将这个数组分割成两个子集，使得两个子集的元素和相等。 输入：nums = [1,5,11,5]输出：true解释：数组可以分割成 [1, 5, 5] 和 [11] 。 方法一：0 - 1背包 算法思路： 背包问题为，有N件物品和一个最多能背重量为W的背包，第i件物品的重量是weight[i]，得到的价值是value[i]，每件物品只能用一次，求解将哪些物品装入背包里物品价值总和最大。 明确以下四点，才能把01背包问题套到本题上来（只能放入一次是01背包，能重复多次放入是完全背包）： 背包的体积为sum / 2 背包要放入的商品（集合里的元素），重量为元素的数值，价值也为元素的数值 背包如果正好装满，说明找到了总和为sum / 2的子集 背包中每一个元素是不可重复放入 确定可以套用，则动态规划五部曲： 确定dp数组以及下标的含义 dp[i][j]代表可装物品为0 - i，背包容量为j的情况下，背包内容量的最大值。 确定递推公式 当能放的下nums[i]的时候，比较放还是不放， ...

哈夫曼树和哈夫曼编码 定义：当用 n 个结点（都做叶子结点且都有各自的权值）试图构建一棵树时，如果构建的这棵树的带权路径长度最小，称这棵树为“最优二叉树”，有时也叫“赫夫曼树”或者“哈夫曼树”，哈夫曼树不唯一。 树的带权路径长度为树中所有叶子结点的带权路径长度之和。通常记作 “WPL” 。下面树的WPL = 7 * 1 + 5 * 2 + 2 * 3 + 4 * 3 构造哈夫曼树：以2，6，8，9，3为例。 选最小的两个数，构建树，排序 重复上述操作，如果有相同的值，谁前谁后无所谓，最后WPL值一样。 哈夫曼编码：二叉树往左边为0，往右边为1，即可得到每个树的编码。

只出现一次的数字III 给你一个整数数组 nums，其中恰好有两个元素只出现一次，其余所有元素均出现两次。 找出只出现一次的那两个元素。你可以按 任意顺序 返回答案。 你必须设计并实现线性时间复杂度的算法且仅使用常量额外空间来解决此问题。 输入：nums = [1,2,1,3,2,5]输出：[3,5]解释：[5,3] 也是有效的答案。 方法：位运算 算法思路： 异或运算^，相同的两个数之间异或为0。将数组每一个数进行异或，得到两个只出现一次元素的异或值diff。 n & (-n)，可得n的位级表示中最低的那一位1。计算diff = diff * - diff，得到diff的最低一位1，即两个只出现一次的元素在该位上不同。 通过diff & num是否等于0将数组中的元素分类两类，分开异或，即可得到两个只出现一次的元素。 代码实现： class Solution { public int[] singleNumber(int[] nums) { int diff = 0; for(int num: nums)& ...

线程的六种状态 线程池的核心参数 线程池可以看做是线程的集合。在没有任务时线程处于空闲状态，当请求到来：线程池给这个请求分配一个空闲的线程，任务完成后回到线程池中等待下次任务执行(而不是销毁)。这样就实现了线程的重用。如果请求到来时，核心线程被占用，任务便会进入workQueue中等待。若workQueue也满，则会创建救急线程来执行，执行完任务后，救急线程不会保留在线程池中，有一定的生存时间，取决于keepAliveTime与unit。若还有时间，会从workQueue中依次加载任务。 corePoolSize核心线程数目：最多保留的线程数。 maximumPoolSize最大线程数目：核心线程+救急线程。 keepAliveTime生存时间：针对救急线程。 unit时间单位：针对救急线程。 workQueue ：阻塞队列。 threadFactory线程工厂：可以为线程创建时起个好名字。 handler拒绝策略：当核心线程、救急线程、阻塞队列都满是，submit一个任务，则会触发拒绝策略。 默认为AbortPolicy，会抛出异常。 CallerRunsPolicy，由 ...

组合总和 给你一个无重复元素的整数数组candidates和一个目标整数target，找出candidates中可以使数字和为目标数target的所有不同组合 ，并以列表形式返回。你可以按任意顺序返回这些组合。 candidates中的同一个数字可以无限制重复被选取。如果至少一个数字的被选数量不同，则两种组合是不同的。 对于给定的输入，保证和为 target 的不同组合数少于150个。 输入：candidates = [2,3,6,7], target = 7输出：[[2,2,3],[7]]解释：2 和 3 可以形成一组候选，2 + 2 + 3 = 7 。注意 2 可以使用多次。7 也是一个候选， 7 = 7 。仅有这两种组合。 方法一：回溯 算法思路： 本题和77.组合 (opens new window)，216.组合总和III (opens new window)和区别是：本题没有数量要求，可以无限重复，但是有总和的限制，所以间接的也是有个数的限制。 确定递归函数的返回值以及参数 除了题中输入candidates和target外，还需要定义sum来记录path中的总和。 ...

组合总和II 给定一个候选人编号的集合 candidates 和一个目标数 target ，找出 candidates 中所有可以使数字和为 target 的组合。 candidates 中的每个数字在每个组合中只能使用 一次 。 **注意：**解集不能包含重复的组合。 输入: candidates = [10,1,2,7,6,1,5], target = 8,输出:[[1,1,6],[1,2,5],[1,7],[2,6]] 方法：回溯 算法思路： 与39.组合总和不同的是，本题candidates的元素是有重复的，每个数字在每个组合中只能使用一次。所以，我们需要对同一树层上使用过的元素去重，同一树枝上的不需要去重。 确定递归函数参数 除39.组合总和设置的参数外，还需加一个boolean型数组used，用来记录同一树层上的元素是否使用过。 确定递归终止条件 当sum大于等于target时终止递归，当sum等于target时，将path添加到result中。剪枝优化可参考39.组合总和，先将candidates数组排序，当sum + candidates[i] > ...

分割回文串 给你一个字符串 s，请你将 s 分割成一些子串，使每个子串都是 回文串 。返回 s 所有可能的分割方案。 回文串 是正着读和反着读都一样的字符串。 输入：s = "aab"输出：[["a","a","b"],["aa","b"]] 方法：回溯 算法思路： 切割问题类似于组合问题，例如对于字符串abcdef： 组合问题：选取一个a之后，在bcdef中再去选取第二个，选取b之后在cdef中在选组第三个……。 切割问题：切割一个a之后，在bcdef中再去切割第二段，切割b之后在cdef中在切割第三段……。 确定递归函数参数 除了输入的字符串s外，还需设置startIndex记录切割过的位置，不能重复切割。 确定终止条件 当切割线到字符串最后面，即startIndex == s.size()时，终止递归。 if(startIndex == s.length()){ result.add(new ArrayList& ...

电话号码的字母组合 给定一个仅包含数字2~9的字符串，返回所有它能表示的字母组合。答案可以按任意顺序返回。 给出数字到字母的映射如下（与电话按键相同）。注意1不对应任何字母。 输入：digits = "23"输出：["ad","ae","af","bd","be","bf","cd","ce","cf"] 方法：回溯 算法思路： 确定递归函数的返回值以及参数 除了题中输入的digits,还需要定义参数index来记录遍历到digits的第几个数字了，以及需要创建一个数组numString用来记录每个数字对应的字母。 String[] numString = new String[]{"", "", "abc", "def", "ghi", "jkl", ...

组合III 找出所有相加之和为n的k个数的组合，且满足下列条件： 只使用数字1到9 每个数字最多使用一次 返回所有可能的有效组合的列表 。该列表不能包含相同的组合两次，组合可以以任何顺序返回。 输入: k = 3, n = 9输出: [[1,2,6], [1,3,5], [2,3,4]]解释:1 + 2 + 6 = 91 + 3 + 5 = 92 + 3 + 4 = 9没有其他符合的组合了。 方法一：回溯 算法思路： 确定递归函数的返回值以及参数 除了n与k，我们还需要设置变量sum记录path中元素的和，startIndex记录循环搜索的起始位置 确定终止条件 当path大小达到k时终止递归，若此时path中的元素和为sum等于n，则在result中添加path if(path.size() == k){ if(sum == n){ result.add(new ArrayList<>(path)); } return;} 单层搜索的过程 和77.组合一样，都是从startIndex开始遍 ...

组合 LeetCode 77.组合 给定两个整数 n 和 k，返回范围 [1, n] 中所有可能的 k 个数的组合。 你可以按任何顺序返回答案。 输入：n = 4, k = 2输出：[ [2,4], [3,4], [2,3], [1,2], [1,3], [1,4],] 方法一：回溯 算法思路： 确定递归函数的返回值以及参数 除了n与k，我们还需要设置变量startIndex，用来记录本层递归中，集合从哪里开始遍历。如，在取完1后，下一层递归就要在[2, 3, 4]中取数。 回溯函数的终止条件 当到达叶子节点时停止递归，即path数组的大小达到k。此时，用二维数组result将path保存起来，终止本层递归。 if(path.size() == k){ result.add(new ArrayList<>(path)); return;} 单层搜索的过程 for循环用来横向遍历，递归的过程是纵向遍历。for循环每次从startIndex开始遍历，然后用path保存取到的节点。 for(int i = startIndex ...