共计 9287 个字符,预计需要花费 24 分钟才能阅读完成。
本文已收录到 AndroidFamily,技术和职场问题,请关注公众号 [彭旭锐] 发问。
大家好,我是小彭。
上周是 LeetCode 第 333 场周赛,你加入了吗?这场周赛品质很高,但难度标得不对,我真的会谢。算法解题思维须要长时间锤炼,退出咱们一起刷题吧~
小彭的 Android 交换群 02 群曾经建设啦,公众号回复“加群”退出咱们~
2570. 合并两个二维数组 – 求和法(Easy)
题目地址
https://leetcode.cn/problems/…
题目形容
给你两个 二维 整数数组 nums1
和 nums2.
nums1[i] = [idi, vali]
示意编号为idi
的数字对应的值等于vali
。nums2[i] = [idi, vali]
示意编号为idi
的数字对应的值等于vali
。
每个数组都蕴含 互不雷同 的 id,并按 id 以 递增 顺序排列。
请你将两个数组合并为一个按 id 以递增顺序排列的数组,并合乎下述条件:
- 只有在两个数组中至多呈现过一次的 id 能力蕴含在后果数组内。
- 每个 id 在后果数组中 只能呈现一次,并且其对应的值等于两个数组中该 id 所对应的值求和。如果某个数组中不存在该 id,则认为其对应的值等于
0
。
返回后果数组。返回的数组须要按 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()}
}
复杂度剖析:
- 工夫复杂度:$O(n + m)$
- 空间复杂度:$O(1)$
2571. 将整数缩小到零须要的起码操作数(Medium)
题目地址
https://leetcode.cn/problems/…
题目形容
给你一个正整数 n
,你能够执行下述操作 任意 次:
n
加上或减去2
的某个 幂
返回使 n
等于 0
须要执行的 起码 操作数。
如果 x == 2i
且其中 i >= 0
,则数字 x
是 2
的幂。
题解一(贪婪 + 记忆化递归)
这道题在比赛时的标签是 Easy,实际上应该是 Medium,收录到题库后官网也改成 Medium 了。
题目显著是决策模型,首先要想到回溯、贪婪、动静布局等思路。
如果用暴力回溯如何解决呢?显然,在每一轮决策中,咱们能够抉择数字的二进制示意中任意一个“1”,并相应地加上 $2^k$ 或减去 $2^k$,终止条件为剩下最初一个“1”时,必然减去 $2^k$。
事实上,咱们发现在每一轮决策中并不需要枚举所有抉择,只须要从最低位的“1”开始打消,最终总能失去最优解。这是因为最低位受到的束缚最小,低位的加法会影响高位并产生间断的 111,有可能使后果更优,而高位的加减对低位没有影响,不会对后果产生更优解。
所以咱们的算法是:获取以后数字最低位的 $1= 2^k$,尝试加上 $2^k$ 或减去 $2^k$ 并将问题转换为规模更小的数,直到剩下的数正好是 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
}
}
复杂度剖析:
- 工夫复杂度:$O(C)$ 其中 $C$ 是所有测试用例合并的状态数,每个状态的工夫复杂度是 $O(1)$。如果以单个测试用例剖析复杂度,则工夫复杂度是 $O(c)$,$c$ 是 int 的位数。
- 空间复杂度:$O(C)$ 散列表空间。
题解二(贪婪 + 统计 1 的个数)
咱们发现:当执行某个操作后,使得二进制中 1 的个数更少的计划最终总的操作次数肯定更低。
例如:当最低位 1 是间断的多个 111 时,采纳加法能够一次性打消多个“1”,否则减法固定打消单个“1”更优。
- 1011, 1101:加法后 = 1011, 1110,减法后:1011, 1100(减法更优)
-
1011, 1111:加法后 = 1100, 0000,减法后:1011, 1110(加法更优)
因而咱们的算法是:在每一步抉择中间接以试错的形式做贪婪抉择,先比拟操作后后果中二进制中 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
}
}
复杂度剖析:
- 工夫复杂度:$O(mlgm)$ 其中 $m$ 是数字中 1 的个数,单次统计位 1 的操作工夫复杂度是 $O(lgm)$。
- 空间复杂度:$O(1)$ 只应用常数级别空间。
题解三(位运算优化)
思路参考:灵茶山艾府的题解
持续题解二的思路,间断多个 1 的最优解是先加上 lowbit 再减去 lowbit,那么最多须要操作两次,而单个 1 的最优解是间接减去 lowbit,最多只有操作一次。
咱们发现:
// 间断 1 的状况:n = 0011, 1111
3n = 1011, 1101
n xor 3n = 1000, 0010 // 正好失去 2 个 1
// 单个 1 的状况:n = 0100
3n = 1100
n xor 3n = 1000 // 正好失去 1 个 1
因而答案就是 n xor 3n
中 1 的个数。
class Solution {fun minOperations(n: Int): Int {return Integer.bitCount(n xor 3 * n)
}
}
复杂度剖析:
- 工夫复杂度:$O(1)$
- 空间复杂度:$O(1)$
2572. 无平方子集计数(Medium)
题目地址
https://leetcode.cn/problems/…
题目形容
给你一个正整数数组 nums
。
如果数组 nums
的子集中的元素乘积是一个 无平方因子数 ,则认为该子集是一个 无平方 子集。
无平方因子数 是无奈被除 1
之外任何平方数整除的数字。
返回数组 nums
中 无平方 且 非空 的子集数目。因为答案可能很大,返回对 109 + 7
取余的后果。
nums
的 非空子集 是能够由删除 nums
中一些元素(能够不删除,但不能全副删除)失去的一个数组。如果形成两个子集时抉择删除的下标不同,则认为这两个子集不同。
准备常识
- 质数 / 素数:只能被 1 和自身整除的数,例如 3,5,7;
- 合数:除了能被 1 和自身整除外,还能被其余数整除的数。也能够了解为由多个不为 1 的质数相乘组成的数,例如 4 = 2 2,6 = 2 3。
- 1 既不是质数也不是合数。
- 质因数分解:将合数合成为多个质数相乘的模式,其中的质数就是合数的质因子。例如 10 蕴含质因子 2 和 5,12 蕴含质因子 2 和 3。
- 状态压缩:用一个维度(通常是二进制数)示意所有物品存在或不存在的状态。
题解一(状态压缩 + 01 背包)
这道题的标签是 Medium,但实际上是 Hard。
题目的外围是求“乘积是无平方因子数的子集”数目,显然有:
- 1、当子集中存在平方数时,该子集肯定不是解。 例如子集中存在
4
或9
或 25 时,子集的乘积肯定存在平方因子; - 2、当子集中任意两个数存在雷同的质因子时,该子集肯定不是解。 例如子集中存在
6
和2
,这两个数都存在雷同的质因子“2”
,因而它们的乘积肯定存在平方因子。 -
3、咱们察看到本题的输出数据范畴只有 [1, 30],30 以内的质数只有
2, 3, 5, 7, 11, 13, 17, 19, 23, 29
总共 10 个数,所以咱们能够事后对 2 ~ 30 的数字进行质因数分解,并且应用二进制掩码 Mask 记录数字是否蕴含某个质因子。 例如:- 00, 0000, 0011:示意存在质因子 2 和 3
- 11, 1111, 1111:示意存在所有质因子(只是举例,本题不存在)
所以,咱们的算法思路应该是:从数字列表抉择中若干个数,如果所有质因子的呈现次数不超过 1,则能够组成非法的子集, 例如 [3, 5] 中所有质因子最多只呈现 1 次,因而形成一个非法的子集。
“从数字列表抉择中若干个数”, 由此咱们发现原问题能够转换为相熟背包问题 —— 计算背包能够包容的物品组合计划数:
- 物品:每一个数字是一个不可分割的物品,咱们不可能抉择半个数;
- 物品体积:每个物品所蕴含的质因子就是该物品的体积;
- 背包容积:背包容积为 10,即背包最多只能蕴含 10 个质因子;
- 限度条件:背包内的数字的质因子不能反复。
实现问题转换后,依照相熟的背包问题模板解决即可:
- 状态转移方程:
dp[i][j] = dp[i - 1][j] + dp[i - 1][j xor mask]
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()}
复杂度剖析:
- 工夫复杂度:$O(n^{2m})$ 其中 $n$ 是 $nums$ 数组的长度,$m$ 是质数的个数(m ≤ 10)。
- 空间复杂度:$O(2^{2m} + 31)$ $dp$ 数组空间与预处理的二进制掩码数组。
题解二(计数优化)
题解一还有优化空间。
在外层循环中,咱们枚举的是物品维度,如果同一个物品中存在多个时,会存在反复计算。因而,咱们能够预处理物品列表,统计不同物品的呈现次数。举例说明:
- 在物品列表
[3, 3, 5]
中物品[3]
呈现了两次,而这两个物品3
都能够和物品[5]
组成指标子集,总个数 = [3] 呈现次数 * 其余子集个数; - 物品 1 较非凡,在物品列表
[1, 1, 5]
中,物品[1]
能够与物品[5]
组成指标子集,同时任意个数的[1, 1]
也能够[5]
组成指标子集,总个数 = $2^{[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 {
// 元素计数
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()}
}
复杂度剖析:
- 工夫复杂度:$O(n + q^{2m})$ 其中 $n$ 是 $nums$ 数组的长度,$m$ 是质数的个数(m ≤ 10),$q$ 是输出数据范畴内非平方因子数的个数 $(q ≤ 18)$
- 空间复杂度:$O(2^{2m} + 31)$ $dp$ 数组空间与预处理的二进制掩码数组。
2573. 找出对应 LCP 矩阵的字符串(Hard)
题目地址
https://leetcode.cn/problems/…
题目形容
对任一由 n
个小写英文字母组成的字符串 word
,咱们能够定义一个 n x n
的矩阵,并满足:
lcp[i][j]
等于子字符串word[i,...,n-1]
和word[j,...,n-1]
之间的最长公共前缀的长度。
给你一个 n x n
的矩阵 lcp
。返回与 lcp
对应的、按字典序最小的字符串 word
。如果不存在这样的字符串,则返回空字符串。
对于长度雷同的两个字符串 a
和 b
,如果在 a
和 b
不同的第一个地位,字符串 a
的字母在字母表中呈现的程序先于 b
中的对应字母,则认为字符串 a
按字典序比字符串 b
小。例如,"aabd"
在字典上小于 "aaca"
,因为二者不同的第一地位是第三个字母,而 'b'
先于 'c'
呈现。
准备常识
LCP 矩阵的定义是一个字符串中的 [i, 字符串开端]
和 [j, 字符串开端]
两个子串的最长公共前缀的长度。依据定义能够得出根本性质:
- 性质 1:当
LCP[i][j]
等于0
时,位于str[i]
与str[j]
的两个字符肯定不雷同;反之当LCP[i][j]
大有 0 时,位于str[i]
与str[j]
的两个字符肯定雷同。 -
性质 2:LCP 矩阵的定义能够利用动静布局推导(与两个字符串的最长公共前缀相似):
- 当
str[i] == str[j]
时,LCP[i][j] = 0
(无独特前缀) - 当
str[i] == str[j]
时,LCP[i][j] = LCP[i + 1][j + 1] + 1
- 当
题解(贪婪结构 + 动静布局)
贪婪思路:题目要求输入满足 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)
}
}
复杂度剖析:
- 工夫复杂度:$O(n^2)$ 结构与验证都是 $O(n^2)$ 级别。
- 空间复杂度:$O(1)$ 不思考后果字符串,只应用了常数级别变量。