3597. Partition String#
阅读理解题目,按照描述的步骤做就行了
Index | Segment After Adding | Seen Segments | Current Segment Seen Before? | New Segment | Updated Seen Segments |
---|---|---|---|---|---|
0 | “a” | [] | No | "" | [“a”] |
1 | “b” | [“a”] | No | "" | [“a”, “b”] |
2 | “b” | [“a”, “b”] | Yes | “b” | [“a”, “b”] |
3 | “bc” | [“a”, “b”] | No | "" | [“a”, “b”, “bc”] |
4 | “c” | [“a”, “b”, “bc”] | No | "" | [“a”, “b”, “bc”, “c”] |
5 | “c” | [“a”, “b”, “bc”, “c”] | Yes | “c” | [“a”, “b”, “bc”, “c”] |
6 | “cc” | [“a”, “b”, “bc”, “c”] | No | "" | [“a”, “b”, “bc”, “c”, “cc”] |
7 | “d” | [“a”, “b”, “bc”, “c”, “cc”] | No | "" | [“a”, “b”, “bc”, “c”, “cc”, “d”] |
func partitionString(s string) []string {
segments := make([]string, 0)
seen := make(map[string]bool)
start := 0
for i := 1; i <= len(s); i++ {
segment := s[start:i]
if !seen[segment] {
seen[segment] = true
segments = append(segments, segment)
start = i
}
}
return segments
}
这里的 seen
可以使用 HashMap 也可以使用 Trie 来做
3598. Longest Common Prefix Between Adjacent Strings After Removals#
题目#
3598. Longest Common Prefix Between Adjacent Strings After Removals
给你一个字符串数组 words
,对于范围 [0, words.length - 1]
内的每个下标 i
,执行以下步骤:
- 从
words
数组中移除下标i
处的元素。 - 计算修改后的数组中所有 相邻对 之间的 最长公共前缀 的长度。
返回一个数组 answer
,其中 answer[i]
是移除下标 i
后,相邻对之间最长公共前缀的长度。
如果 不存在相邻对,或者 不存在公共前缀,则 answer[i]
应为 0
。
注:字符串的前缀是从字符串的开头开始延伸到任意位置的子字符串。
例子1
Input: words = ["jump","run","run","jump","run"]
Output: [3,0,0,3,3]
解释
移除下标 0:
words
变为["run", "run", "jump", "run"]
最长的相邻对是["run", "run"]
,其公共前缀为"run"
(长度为 3)移除下标 1:
words
变为["jump", "run", "jump", "run"]
没有相邻对有公共前缀(长度为 0)移除下标 2:
words
变为["jump", "run", "jump", "run"]
没有相邻对有公共前缀(长度为 0)移除下标 3:
words
变为["jump", "run", "run", "run"]
最长的相邻对是["run", "run"]
,其公共前缀为"run"
(长度为 3)移除下标 4:
words
变为["jump", "run", "run", "jump"]
最长的相邻对是["run", "run"]
,其公共前缀为"run"
(长度为 3)
思路#
第一点是需要注意在移除元素 i
后,words[i-1]
和 words[i+1]
会变成新的相邻对。 比如 原始:["fcc", "cdfda", "fcec"]
移除下标 1 后变成 ["fcc", "fcec"]
我们应该比较 fcc
和 fcec
第二个点就是这个题直接暴力求解会超时的
其实我们可以将数组分为三个部分来求解
首先计算每一对
i
和i+1
的 LCP。存入数组
lcpPairs[i] = LCP(words[i], words[i+1])
每次移除一个下标
i
,只需在:lcpPairs[0..i-2]
lcp(words[i-1], words[i+1])
(如果i-1
和i+1
都存在)lcpPairs[i+1..n-2]
中找最大值。
通过这样的预处理可以大大减少重复计算量
package main
import (
"fmt"
)
func lcp(a, b string) int {
minLen := len(a)
if len(b) < minLen {
minLen = len(b)
}
for i := 0; i < minLen; i++ {
if a[i] != b[i] {
return i
}
}
return minLen
}
func longestCommonPrefix(words []string) []int {
n := len(words)
ret := make([]int, n)
if n <= 1 {
return ret
}
// Step 1: 预处理所有相邻对的 LCP
lcpPairs := make([]int, n-1)
for i := 0; i < n-1; i++ {
lcpPairs[i] = lcp(words[i], words[i+1])
}
// Step 2: 构建左区间最大值 & 右区间最大值数组
leftPartMax := make([]int, n-1)
rightPartMax := make([]int, n-1)
leftPartMax[0] = lcpPairs[0]
for i := 1; i < n-1; i++ {
if lcpPairs[i] > leftPartMax[i-1] {
leftPartMax[i] = lcpPairs[i]
} else {
leftPartMax[i] = leftPartMax[i-1]
}
}
rightPartMax[n-2] = lcpPairs[n-2]
for i := n - 3; i >= 0; i-- {
if lcpPairs[i] > rightPartMax[i+1] {
rightPartMax[i] = lcpPairs[i]
} else {
rightPartMax[i] = rightPartMax[i+1]
}
}
// Step 3: 遍历每个被删除的 i
for i := 0; i < n; i++ {
maxLcp := 0
// 处理好 i 的所有 case
if i > 1 {
maxLcp = leftPartMax[i-2]
}
if i+1 < n-1 {
if rightPartMax[i+1] > maxLcp {
maxLcp = rightPartMax[i+1]
}
}
// 中间连接 i-1 和 i+1
if i > 0 && i < n-1 {
join := lcp(words[i-1], words[i+1])
if join > maxLcp {
maxLcp = join
}
}
ret[i] = maxLcp
}
return ret
}
func main() {
fmt.Println(longestCommonPrefix([]string{"jump", "run", "run", "jump", "run"})) // [3 0 0 3 3]
fmt.Println(longestCommonPrefix([]string{"dog", "racer", "car"})) // [0 0 0]
fmt.Println(longestCommonPrefix([]string{"f", "cfe", "feab", "fcc", "cdfda", "fcec", "afae", "cdeb", "dc", "bffd", "edabe"})) // [1,1,0,0,2,1,1,1,1,1,1]
}
3599. Partition Array to Minimize XOR#
题目#
3599. Partition Array to Minimize XOR
给你一个整数数组 nums
和一个整数 k
。你的任务是将 nums
分成 k
个非空的 子数组 。对每个子数组,计算其所有元素的按位 XOR 值。返回这 k
个子数组中 最大 XOR 的 最小值 。
子数组 是数组中连续的 非空 元素序列。
例子1
Input: nums = [1,2,3]
, k = 2
Output: 1
解释:
最优划分是 [1]
和 [2, 3]
。
- 第一个子数组的 XOR 是
1
。 - 第二个子数组的 XOR 是
2 XOR 3 = 1
。
子数组中最大的 XOR 是 1,是最小可能值。
思路#
动态规划题目,不过首先我们需要知道 XOR 的一些性质
a ^ a = 0
a ^ 0 = a
所以可以得出
a ^ a ^ b = b
我们首先构建一下前缀 XOR 结果的数组
prefix := make([]int, n+1)
for i := 0; i < n; i++ {
prefix[i+1] = prefix[i] ^ nums[i]
}
prefix[i]
存储的是nums[0] ^ nums[1] ^ ... ^ nums[i-1]
的 XOR 结果
对于连续子数组
nums[a...b]
的结果就是prefix[a] ^ prefix[b+1]
。 因为prefix[a] = nums[0] ^ nums[1] ^ .. ^ nums[a-1]
prefix[b+1] = nums[0] ^ nums[1] ^ .. ^ nums[a-1] ^ nums[a] ^ ... ^ nums[b]
这两个 XOR 之后可以进行消元,得到
nums[a] ^ nums[a+1] ^ ... ^ nums[b]
同样运用这个思路的题目是 1310. XOR Queries of a Subarray
然后我们建立动态规划方程
dp := make([][]int, n+1)
for i := range dp {
dp[i] = make([]int, k+1)
for j := range dp[i] {
dp[i][j] = math.MaxInt32
}
}
dp[0][0] = 0
dp[i][j]
表示将 nums
的前 i
个元素 (nums[0...i-1]
) 划分为 j
个连续子数组时,所有这些子数组 XOR 和中的最大值的最小值
for i := 1; i <= n; i++ {
for j := 1; j <= k && j <= i; j++ {
for p := j - 1; p < i; p++ {
x := prefix[i] ^ prefix[p]
dp[i][j] = min(dp[i][j], max(dp[p][j-1], x))
}
}
}
- 外层循环
i
: 遍历数组元素的数量,从1
到n
。i
代表当前考虑的是前i
个元素 (nums[0...i-1]
)。 - 中间循环
j
: 遍历划分的子数组数量,从1
到k
。同时j
不能超过i
(因为每个子数组非空)。 - 内层循环
p
: 遍历可能的划分点。p
表示第j
个子数组的起始位置。具体来说,nums[p...i-1]
是第j
个子数组。那么前j-1
个子数组必定使用了nums[0...p-1]
这些元素。因此,dp[p][j-1]
存储的就是前j-1
个子数组的解。p
的范围:p
最小为j-1
:因为前j-1
个子数组至少需要j-1
个元素,这意味着p-1
至少是j-2
,所以p
至少是j-1
。p
最大为i-1
:因为第j
个子数组至少要包含nums[i-1]
这个元素,所以p
必须小于i
。
- XOR 计算
x
:x = prefix[i] ^ prefix[p]
计算的是子数组nums[p...i-1]
的异或和。 max(dp[p][j-1], x)
: 对于一个特定的划分点p
,这表示当前这种划分方式(前j-1
个子数组的最大 XOR 是dp[p][j-1]
,第j
个子数组的 XOR 是x
)的总的最大 XOR 值。min(...)
更新dp[i][j]
: 我们要找到所有可能的p
中,使得max(dp[p][j-1], x)
最小的那个值,因为这是dp[i][j]
的定义。
完整代码如下
func minXor(nums []int, k int) int {
n := len(nums)
prefix := make([]int, n+1)
for i := 0; i < n; i++ {
prefix[i+1] = prefix[i] ^ nums[i]
}
const inf = math.MaxInt32
dp := make([][]int, n+1)
for i := range dp {
dp[i] = make([]int, k+1)
for j := range dp[i] {
dp[i][j] = inf
}
}
dp[0][0] = 0
for i := 1; i <= n; i++ {
for j := 1; j <= k && j <= i; j++ {
for p := j - 1; p < i; p++ {
x := prefix[i] ^ prefix[p]
dp[i][j] = min(dp[i][j], max(dp[p][j-1], x))
}
}
}
return dp[n][k]
}
P.S. 1310. XOR Queries of a Subarray 的解法
func xorQueries(arr []int, queries [][]int) []int {
n := len(arr)
prefix := make([]int, n+1)
for i := 0; i < n; i++ {
prefix[i+1] = prefix[i] ^ arr[i]
}
ret := make([]int, len(queries))
for i, query := range queries {
start:= query[0]
end := query[1]
ret[i] = prefix[start] ^ prefix[end+1]
}
return ret
}
3600. Maximize Spanning Tree Stability with Upgrades#
题目#
3600. Maximize Spanning Tree Stability with Upgrades
思路#
好像是要用并查集,留个位置以后再补
https://cp-algorithms.com/data_structures/disjoint_set_union.html