本文已收录到 AndroidFamily，技术和职场问题，请关注公众号 [彭旭锐] 提问。
大家好，我是小彭。
上周是 LeetCode 第 333 场周赛，你参加了吗？这场周赛质量很高，但难度标得不对，我真的会谢。算法解题思维需要长时间锻炼，加入我们一起刷题吧~
小彭的 Android 交流群 02 群已经建立啦，公众号回复 “加群” 加入我们~
https://leetcode.cn/problems/merge-two-2d-arrays-by-summing-values/
题目描述给你两个 二维 整数数组 nums1 和 nums2.
每个数组都包含 互不相同 的 id ，并按 id 以 递增 顺序排列。
请你将两个数组合并为一个按 id 以递增顺序排列的数组，并符合下述条件：
返回结果数组。返回的数组需要按 id 以递增顺序排列。
题解简单模拟题，使用双指针合并数组即可。
class Solution { fun mergeArrays(nums1: Array<IntArray>, nums2: Array<IntArray>): Array<IntArray> { val n = nums1.size val m = nums2.size val result = LinkedList<IntArray>() var index1 = 0 var index2 = 0 while (index1 < n && index2 < m) { val e1 = nums1[index1] val e2 = nums2[index2] if (e1[0] == e2[0]) { result.add(intArrayOf(e1[0], e1[1] e2[1])) index1 index2 } else if (e1[0] < e2[0]) { result.add(e1) index1 } else { result.add(e2) index2 } } while (index1 < n) { result.add(nums1[index1 ]) } while (index2 < m) { result.add(nums2[index2 ]) } return result.toTypedArray() }}
复杂度分析：
https://leetcode.cn/problems/minimum-operations-to-reduce-an-integer-to-0/
题目描述给你一个正整数 n ，你可以执行下述操作 任意 次：
返回使 n 等于 0 需要执行的 最少 操作数。
如果 x == 2i 且其中 i >= 0 ，则数字 x 是 2 的幂。
题解一（贪心 记忆化递归）这道题在竞赛时的标签是 Easy，实际上应该是 Medium，收录到题库后官方也改成 Medium了。
题目明显是决策模型，首先要想到回溯、贪心、动态规划等思路。
如果用暴力回溯如何解决呢？显然，在每一轮决策中，我们可以选择数字的二进制表示中任意一个 “1”，并相应地加上 2� 或减去 2�，终止条件为剩下最后一个 “1” 时，必然减去 2�。
事实上，我们发现在每一轮决策中并不需要枚举所有选择，只需要从最低位的 “1” 开始消除，最终总能得到最优解。这是因为最低位受到的约束最小，低位的加法会影响高位并产生连续的 111，有可能使结果更优，而高位的加减对低位没有影响，不会对结果产生更优解。
所以我们的算法是：获取当前数字最低位的 1=2�，尝试加上 2� 或减去 2� 并将问题转换为规模更小的数，直到剩下的数正好是 2 的幂结束。递归过程中会存在重复状态，所以需要加上记忆化剪枝。
class Solution { // 备忘录 private val memo = HashMap<Int, Int>() fun minOperations(n: Int): Int { // n 是 2 的幂 if (n and (n - 1) == 0) return 1 if (memo.containsKey(n)) return memo[n]!! // 最低位 1 val lowbit = n and -n val result = 1 Math.min(minOperations(n lowbit), minOperations(n - lowbit)) memo[n] = result return result }}
复杂度分析：
我们发现： 当执行某个操作后，使得二进制中 1 的个数更少的方案最终总的操作次数一定更低。
例如：当最低位 1 是连续的多个 111 时，采用加法可以一次性消除多个 “1”，否则减法固定消除单个 “1” 更优。
因此我们的算法是：在每一步选择中直接以试错的方式做贪心选择，先比较操作后结果中二进制中 1 的个数，再选择更优的操作。
class Solution { fun minOperations(n: Int): Int { var num = n var operateCount = 0 while (num != 0) { // 最低位 1 val lowbit = num and -num // 直接判断 if (Integer.bitCount(num lowbit) <= Integer.bitCount(num - lowbit)) { num = lowbit } else { num -= lowbit } operateCount } return operateCount }}
复杂度分析：
思路参考：灵茶山艾府的题解
继续题解二的思路，连续多个 1 的最优解是先加上 lowbit 再减去 lowbit，那么最多需要操作两次，而单个 1 的最优解是直接减去 lowbit，最多只要操作一次。
我们发现：
// 连续 1 的情况：n = 0011, 11113n = 1011, 1101n xor 3n = 1000, 0010 // 正好得到 2 个 1// 单个 1 的情况：n = 01003n = 1100n xor 3n = 1000 // 正好得到 1 个 1
因此答案就是 n xor 3n 中 1 的个数。
class Solution { fun minOperations(n: Int): Int { return Integer.bitCount(n xor 3 * n) }}
复杂度分析：
https://leetcode.cn/problems/count-the-number-of-square-free-subsets/
题目描述给你一个正整数数组 nums 。
如果数组 nums 的子集中的元素乘积是一个 无平方因子数 ，则认为该子集是一个 无平方 子集。
无平方因子数 是无法被除 1 之外任何平方数整除的数字。
返回数组 nums 中 无平方 且 非空 的子集数目。因为答案可能很大，返回对 109 7 取余的结果。
nums 的 非空子集 是可以由删除 nums 中一些元素（可以不删除，但不能全部删除）得到的一个数组。如果构成两个子集时选择删除的下标不同，则认为这两个子集不同。
预备知识这道题的标签是 Medium，但实际上是 Hard。
题目的核心是求 “乘积是无平方因子数的子集” 数目，显然有：
所以，我们的算法思路应该是： 从数字列表选择中若干个数，如果所有质因子的出现次数不超过 1，则可以组成合法的子集， 例如 [3, 5] 中所有质因子最多只出现 1 次，因此构成一个合法的子集。
“从数字列表选择中若干个数”， 由此我们发现原问题可以转换为熟悉背包问题 —— 计算背包可以容纳的物品组合方案数：
完成问题转换后，按照熟悉的背包问题模板解决即可：
class Solution { companion object { private val MOD = 1000000007 private val primeList = listOf(2, 3, 5, 7, 11, 13, 17, 19, 23, 29) private val masks = IntArray(31).apply { for (i in 2..30) { for ((j, prime) in primeList.withIndex()) { // 过滤平方因子数 if (i % (prime * prime) == 0) { this[i] = -1 break } // 记录质因子 if (i % prime == 0) this[i] = this[i] or (1 shl j) } } } } fun squareFreeSubsets(nums: IntArray): Int { // 背包问题 // 过滤平方因子数（数字 1 的 mask == 0） val numsFiltered = nums.filter { masks[it] >= 0 } // 物品总数 val n = numsFiltered.size // 背包容积 11,1111,1111 val amount = (1 shl 10) - 1 // dp[i][j] 表示选择前 i 个物品且体积为 j 的方案数 val dp = Array(n 1) { IntArray(amount 1) }.apply { // 选择前 i 个物品且体积为 0 的方案为 1 this[0][0] = 1 } // 枚举物品 for (i in 1..n) { // 物品的质因子属性 val mask = masks[numsFiltered[i - 1]] // 枚举体积 for (j in 0..amount) { dp[i][j] = dp[i - 1][j] // j | mask == j => mask 是 j 的子集 if (j or mask == j) dp[i][j] = dp[i - 1][j xor mask] } } // 题目不要求背包装满，所以 dp[n - 1][...] 的方案都包含，最后再去掉空集 return dp[n].sum() - 1 }}
考虑大数越界问题：
fun squareFreeSubsets(nums: IntArray): Int { // 背包问题 // 过滤平方因子数（数字 1 的 mask == 0） val numsFiltered = nums.filter { masks[it] >= 0 } // 物品总数 val n = numsFiltered.size // 背包容积 11,1111,1111 val amount = (1 shl 10) - 1 // dp[i][j] 表示选择前 i 个物品且体积为 j 的方案数 val dp = Array(n 1) { IntArray(amount 1) }.apply { // 选择前 i 个物品且体积为 0 的方案为 1 this[0][0] = 1 } // 枚举物品 for (i in 1..n) { // 物品的质因子属性 val mask = masks[numsFiltered[i - 1]] // 枚举体积 for (j in 0..amount) { dp[i][j] = dp[i - 1][j] // j | mask == j => mask 是 j 的子集 if (j or mask == j) dp[i][j] = (dp[i][j] dp[i - 1][j xor mask]) % MOD } } // 题目不要求背包装满，所以 dp[n - 1][...] 的方案都包含，最后再去掉空集 var sum = 0L for (count in dp[n]) { sum = count } return ((sum - 1 MOD) % MOD).toInt()}
01 背包问题可以取消物品维度降低空间复杂度：
fun squareFreeSubsets(nums: IntArray): Int { // 背包问题 // 物品总数 val n = nums.size // 背包容积 11,1111,1111 val amount = (1 shl 10) - 1 // dp[i][j] 表示选择前 i 个物品且体积为 j 的方案数 val dp = IntArray(amount 1).apply { // 选择前 i 个物品且体积为 0 的方案为 1 this[0] = 1 } // 枚举物品 for (i in 1..n) { // 物品的质因子属性 val mask = masks[nums[i - 1]] // 过滤平方因子数 if (mask < 0) continue // 枚举体积（从大到小遍历） for (j in amount downTo 0) { // j | mask == j => mask 是 j 的子集 if (j or mask == j) dp[j] = (dp[j] dp[j xor mask]) % MOD } } // 题目不要求背包装满，所以 dp[n - 1][...] 的方案都包含，最后再去掉空集 var sum = 0L for (count in dp) { sum = count } return ((sum - 1 MOD) % MOD).toInt()}
复杂度分析：
题解一还有优化空间。
在外层循环中，我们枚举的是物品维度，如果同一个物品中存在多个时，会存在重复计算。因此，我们可以预处理物品列表，统计不同物品的出现次数。举例说明：
class Solution { companion object { private val MOD = 1000000007 private val primeList = listOf(2, 3, 5, 7, 11, 13, 17, 19, 23, 29) private val masks = IntArray(31).apply { for (i in 2..30) { for ((j, prime) in primeList.withIndex()) { // 过滤平方因子数 if (i % (prime * prime) == 0) { this[i] = -1 break } // 记录质因子 if (i % prime == 0) this[i] = this[i] or (1 shl j) } } } } fun squareFreeSubsets(nums: IntArray): Int { // 元素计数 var pow1 = 1L val cnts = IntArray(31).apply { for (element in nums) { if (element == 1) pow1 = pow1 * 2 % MOD else this[element] } } // 物品总数 val n = nums.size // 背包容积 11,1111,1111 val amount = (1 shl 10) - 1 // dp[i][j] 表示选择前 i 个物品且体积为 j 的方案数 val dp = LongArray(amount 1).apply { // 选择前 i 个物品且体积为 0 的方案为 1 this[0] = 1 } // 枚举去重物品 for ((num, cnt) in cnts.withIndex()) { // 物品的质因子属性 val mask = masks[num] // 过滤不存在的物品 if (cnt <= 0) continue // 过滤平方因子数和 1 if (mask <= 0) continue // 枚举体积（从大到小遍历） for (j in amount downTo 0) { // j | mask == j => mask 是 j 的子集 if (j or mask == j) dp[j] = (dp[j] dp[j xor mask] * cnt) % MOD } } // 题目不要求背包装满，所以 dp[n - 1][...] 的方案都包含，最后再去掉空集 var sum = 0L for (count in dp) { sum = (sum count) % MOD } // 1 的任意组合可以与其他子集组合 return ((sum * pow1 - 1 MOD) % MOD).toInt() }}
复杂度分析：
https://leetcode.cn/problems/find-the-string-with-lcp/description/
题目描述对任一由 n 个小写英文字母组成的字符串 word ，我们可以定义一个 n x n 的矩阵，并满足：
给你一个 n x n 的矩阵 lcp 。返回与 lcp 对应的、按字典序最小的字符串 word 。如果不存在这样的字符串，则返回空字符串。
对于长度相同的两个字符串 a 和 b ，如果在 a 和 b 不同的第一个位置，字符串 a 的字母在字母表中出现的顺序先于 b 中的对应字母，则认为字符串 a 按字典序比字符串 b 小。例如，"aabd" 在字典上小于 "aaca" ，因为二者不同的第一位置是第三个字母，而 'b' 先于 'c' 出现。
预备知识LCP 矩阵的定义是一个字符串中的 [i, 字符串末尾] 和 [j, 字符串末尾] 两个子串的最长公共前缀的长度。根据定义可以得出基本性质：
贪心思路： 题目要求输出满足 LCP 矩阵的字典序最小的结果，那么我们应该优先选择数值最小的字母 ‘a’。
可以用反证法证明：假设 “bcbc” 是满足条件且字典序最小的结果，那么我们可以将 ‘b’ 映射为 ‘a’，而 ‘c’ 映射为 ‘b’ 得到 “abab”。由于 LCP 矩阵只考虑公共前缀长度而不考虑字母，所以 “abab” 一定符合同一个 LCP 矩阵定义，与假设矛盾。
因此，我们的算法思路是：从 s[0] 开始填入 ‘a’，并根据 LCP[0][j] > 0 将所有 s[j] 设置为同一个字符 ‘a’，依此类推。从下一个未填入的位置开始填入 ‘b’，并将所有相同的 LCP[i][j] > 0 的位置填入 ‘b’，直到字符串结束或候选字符大于 ‘z’ 结束。
class Solution { fun findTheString(lcp: Array<IntArray>): String { // 目标字符串长度 val n = lcp.size // 1、构造字符串 // 目标字符串 val charArray = CharArray(n) { ' ' } // 候选字符序列 'a' -> 'z' var candidate = 'a' var i = 0 while (i < n) { // 当前位置已经填充 if (charArray[i] != ' ') { i continue } // 候选字符不够 if (candidate > 'z') { return "" } // 填充相同字符的位置，并且使用字典序最小的候选字符 for (j in i until n) { if (lcp[i][j] > 0) charArray[j] = candidate } // 下一个候选字符 candidate = 1 i } return String(charArray) }}
使用贪心算法构造出字符串后，我们还需要检查字符串是否符合 LCP 矩阵的定义。这是因为构造时只考虑 Lcp[i][j] > 0，但至于具体大于 0 的什么数并没有考虑，所以我们还需要验证的过程：
class Solution { fun findTheString(lcp: Array<IntArray>): String { // 目标字符串长度 val n = lcp.size // 1、构造字符串 ... // 2、检查字符串是否符合 LCP（因为构造时只考虑 lcp[i][j] > 0） for (i in n - 1 downTo 0) { for (j in n - 1 downTo 0) { if (charArray[i] == charArray[j]) { if (i == n - 1 || j == n - 1) { if (lcp[i][j] != 1) return "" } else { if (lcp[i][j] != lcp[i 1][j 1] 1) return "" } } else { if (lcp[i][j] != 0) return "" } } } return String(charArray) }}
复杂度分析：
