写点什么

2023-08-18:用 go 写算法。你会得到一个字符串 text, 你应该把它分成 k 个子字符串 (subtext1, subtext2,…, subtextk)。 要求满足: subtexti 是

  • 2023-08-18
    北京
  • 本文字数:4936 字

    阅读完需:约 16 分钟

2023-08-18:用 go 写算法。你会得到一个字符串 text,


你应该把它分成 k 个子字符串 (subtext1, subtext2,…, subtextk)。


要求满足:


subtexti 是 非空 字符串,


所有子字符串的连接等于 text ,


( 即 subtext1 + subtext2 + ... + subtextk == text ),


subtexti == subtextk - i + 1 表示所有 i 的有效值( 即 1 <= i <= k )。


返回 k 可能最大值。


输入:text = "ghiabcdefhelloadamhelloabcdefghi"。


输出:7。


解释:我们可以把字符串拆分成 "(ghi)(abcdef)(hello)(adam)(hello)(abcdef)(ghi)"。


来自小红书、谷歌、Bloomberg、微软、亚马逊、字节跳动、摩根大通、Uber。


来自左程云


答案 2023-08-18:

这两种算法的步骤可以概括如下:

方法 1:longestDecomposition1(text)


1.初始化变量 s 为文本的字节数组,变量 n 为文本长度,变量 lr 分别指向字节数组的开头和末尾,变量 ans 初始化为 0。


2.使用双指针法,当 l 小于等于 r 时进行循环:


  • 初始化变量 size 为 1。

  • 在一个循环内,通过比较子字符串是否相同来确定 size 的值,直到 size 使得剩余的子字符串无法再被分割为相同的子字符串。

  • 如果 size 使得剩余的子字符串可以被分割为相同的子字符串,则将 ans 增加 2。

  • 向右移动 l 和向左移动 r,使其分别指向剩余子字符串的新开头和新结尾。


3.如果 r 恰好等于 l-1,则返回 ans,否则返回 ans + 1


方法 2:longestDecomposition2(text)


1.初始化变量 s 为文本的字节数组,变量 n 为文本长度,通过调用 generateDC3 函数生成 dc3 结构体。


2.初始化变量 rankdc3 结构体中的 Rank 切片,初始化变量 rmq 为通过调用 NewRMQ 函数生成的 RMQ 结构体,变量 lr 分别指向字节数组的开头和末尾,变量 ans 初始化为 0。


3.使用双指针法,当 l 小于等于 r 时进行循环:


  • 初始化变量 size 为 1。

  • 在一个循环内,通过比较子字符串是否相同来确定 size 的值,直到 size 使得剩余的子字符串无法再被分割为相同的子字符串。

  • 如果 size 使得剩余的子字符串可以被分割为相同的子字符串,则将 ans 增加 2。

  • 向右移动 l 和向左移动 r,使其分别指向剩余子字符串的新开头和新结尾。


4.如果 r 恰好等于 l-1,则返回 ans,否则返回 ans + 1

复杂度分析:

最初的算法longestDecomposition1的时间复杂度和空间复杂度如下:


  • 时间复杂度:O(n^2),其中 n 为输入字符串 text 的长度。

  • 空间复杂度:O(n),需要额外的空间来存储中间计算结果。


优化后的算法longestDecomposition2使用了DC3RMQ的数据结构,并进行了分块处理,因此时间复杂度和空间复杂度如下:


  • 时间复杂度:O(n log n),其中 n 为输入字符串 text 的长度。

  • 空间复杂度:O(n),需要额外的空间来存储中间计算结果。


总结:优化后的算法longestDecomposition2虽然时间复杂度更低,但空间复杂度和初次计算的算法longestDecomposition1相同,都为 O(n)。

go 语言完整代码如下:

package main
import ( "fmt" "strings" "time")
func longestDecomposition1(text string) int { if len(text) == 1 { return 1 }
s := []byte(text) n := len(s) l := 0 r := n - 1 ans := 0
for l <= r { size := 1 for 2*size <= r-l+1 { if same1(s, l, r, size) { break } size++ } if 2*size <= r-l+1 { ans += 2 } l += size r -= size }
if r == l-1 { return ans } return ans + 1}
func same1(s []byte, l, r, size int) bool { for i, j := l, r-size+1; j <= r; i, j = i+1, j+1 { if s[i] != s[j] { return false } } return true}
func longestDecomposition2(str string) int { if len(str) == 1 { return 1 } s := []byte(str) n := len(s) dc3 := generateDC3(s, n) rank := dc3.Rank rmq := NewRMQ(dc3.Height) l := 0 r := n - 1 ans := 0 for l <= r { size := 1 for ; 2*size <= r-l+1; size++ { if same2(rank, rmq, l, r, size) { break } } if 2*size <= r-l+1 { ans += 2 } l += size r -= size } if r == l-1 { return ans } return ans + 1}
func same2(rank []int, rmq *RMQ, l, r, size int) bool { start1 := l start2 := r - size + 1 minStart := getMin(rank[start1], rank[start2]) maxStart := getMax(rank[start1], rank[start2]) return rmq.Min(minStart+1, maxStart) >= size}
func getMin(a, b int) int { if a < b { return a } else { return b }}
func getMax(a, b int) int { if a > b { return a } else { return b }}
func generateDC3(s []byte, n int) *DC3 { min0 := 2147483647 max0 := -2147483648 for _, cha := range s { min0 = getMin(min0, int(cha)) max0 = getMax(max0, int(cha)) } arr := make([]int, n) for i := 0; i < n; i++ { arr[i] = int(s[i]) - min0 + 1 } return NewDC3(arr, max0-min0+1)
}
type DC3 struct { Sa []int Rank []int Height []int}
func NewDC3(nums []int, max int) *DC3 { res := &DC3{} res.Sa = res.sa(nums, max) res.Rank = res.rank() res.Height = res.height(nums) return res}func (dc3 *DC3) sa(nums []int, max int) []int { n := len(nums) arr := make([]int, n+3) copy(arr, nums) return dc3.skew(arr, n, max)}
func (dc3 *DC3) skew(nums []int, n int, K int) []int { n0 := (n + 2) / 3 n1 := (n + 1) / 3 n2 := n / 3 n02 := n0 + n2 s12 := make([]int, n02+3) sa12 := make([]int, n02+3)
for i, j := 0, 0; i < n+(n0-n1); i++ { if i%3 != 0 { s12[j] = i j++ } }
dc3.radixPass(nums, s12, sa12, 2, n02, K) dc3.radixPass(nums, sa12, s12, 1, n02, K) dc3.radixPass(nums, s12, sa12, 0, n02, K)
name := 0 c0 := -1 c1 := -1 c2 := -1
for i := 0; i < n02; i++ { if c0 != nums[sa12[i]] || c1 != nums[sa12[i]+1] || c2 != nums[sa12[i]+2] { name++ c0 = nums[sa12[i]] c1 = nums[sa12[i]+1] c2 = nums[sa12[i]+2] }
if sa12[i]%3 == 1 { s12[sa12[i]/3] = name } else { s12[sa12[i]/3+n0] = name } }
if name < n02 { sa12 = dc3.skew(s12, n02, name) for i := 0; i < n02; i++ { s12[sa12[i]] = i + 1 } } else { for i := 0; i < n02; i++ { sa12[s12[i]-1] = i } }
s0 := make([]int, n0) sa0 := make([]int, n0)
for i, j := 0, 0; i < n02; i++ { if sa12[i] < n0 { s0[j] = 3 * sa12[i] j++ } }
dc3.radixPass(nums, s0, sa0, 0, n0, K)
sasa := make([]int, n)
for p, t, k := 0, n0-n1, 0; k < n; k++ { i := 0 if sa12[t] < n0 { i = sa12[t]*3 + 1 } else { i = (sa12[t]-n0)*3 + 2 } j := sa0[p]
rr := false if sa12[t] < n0 { rr = dc3.leq1(nums[i], s12[sa12[t]+n0], nums[j], s12[j/3]) } else { rr = dc3.leq(nums[i], nums[i+1], s12[sa12[t]-n0+1], nums[j], nums[j+1], s12[j/3+n0]) }
if rr { sasa[k] = i t++ if t == n02 { for k++; p < n0; p, k = p+1, k+1 { sasa[k] = sa0[p] } } } else { sasa[k] = j p++ if p == n0 { for k++; t < n02; t, k = t+1, k+1 { if sa12[t] < n0 { sasa[k] = sa12[t]*3 + 1 } else { sasa[k] = (sa12[t]-n0)*3 + 2 } } } } }
return sasa}
func (t *DC3) radixPass(nums []int, input []int, output []int, offset int, n int, k int) { cnt := make([]int, k+1)
for i := 0; i < n; i++ { cnt[nums[input[i]+offset]]++ }
for i, sum := 0, 0; i < len(cnt); i++ { t := cnt[i] cnt[i] = sum sum += t }
for i := 0; i < n; i++ { output[cnt[nums[input[i]+offset]]] = input[i] cnt[nums[input[i]+offset]]++ }}
func (t *DC3) leq1(a1 int, a2 int, b1 int, b2 int) bool { return a1 < b1 || (a1 == b1 && a2 <= b2)}
func (t *DC3) leq(a1 int, a2 int, a3 int, b1 int, b2 int, b3 int) bool { return a1 < b1 || (a1 == b1 && t.leq1(a2, a3, b2, b3))}
func (t *DC3) rank() []int { n := len(t.Sa) ans := make([]int, n)
for i := 0; i < n; i++ { ans[t.Sa[i]] = i }
return ans}
func (t *DC3) height(s []int) []int { n := len(s) ans := make([]int, n)
for i, k := 0, 0; i < n; i++ { if t.Rank[i] != 0 { if k > 0 { k-- } j := t.Sa[t.Rank[i]-1]
for i+k < n && j+k < n && s[i+k] == s[j+k] { k++ }
ans[t.Rank[i]] = k } }
return ans}
type RMQ struct { min0 [][]int}
func NewRMQ(arr []int) *RMQ { res := &RMQ{} n := len(arr) k := power2(n) res.min0 = make([][]int, n+1) for i := 0; i <= n; i++ { res.min0[i] = make([]int, k+1) } for i := 1; i <= n; i++ { res.min0[i][0] = arr[i-1] } for j := 1; (1 << j) <= n; j++ { for i := 1; i+(1<<j)-1 <= n; i++ { res.min0[i][j] = getMin(res.min0[i][j-1], res.min0[i+(1<<(j-1))][j-1]) } } return res}
func (t *RMQ) Min(l, r int) int { l++ r++ k := power2(r - l + 1) return getMin(t.min0[l][k], t.min0[r-(1<<k)+1][k])}
func power2(m int) int { ans := 0 for (1 << ans) <= (m >> 1) { ans++ } return ans}
func generateS(a, b int) string { ans := make([]byte, a+b) for i := 0; i < a; i++ { ans[i] = 'a' } for i, j := a, 0; j < b; i, j = i+1, j+1 { ans[i] = 'b' } return string(ans)}
func generateT(part string, n int) string { builder := strings.Builder{} for i := 0; i < n; i++ { builder.WriteString(part) } return builder.String()}
func main() { fmt.Println("先展示一下DC3的用法") test := "aaabaaa" dc3 := generateDC3([]byte(test), len(test)) fmt.Println("sa[i]表示字典序排名第i的是什么位置开头的后缀串") sa := dc3.Sa for i := 0; i < len(test); i++ { fmt.Printf("%d : %d\n", i, sa[i]) }
fmt.Println("rank[i]表示i位置开头的后缀串的字典序排多少名") rank := dc3.Rank for i := 0; i < len(test); i++ { fmt.Printf("%d : %d\n", i, rank[i]) }
fmt.Println("height[i]表示字典序排名i的后缀串和前一个排名的后缀串,最长公共前缀是多长") height := dc3.Height for i := 0; i < len(test); i++ { fmt.Printf("%d : %d\n", i, height[i]) }
fmt.Println("性能测试开始") var start, end int64 s := generateS(300000, 1) t := generateT(s, 2)
start = time.Now().UnixNano() / int64(time.Millisecond) fmt.Println("方法1的结果 :", longestDecomposition1(t)) end = time.Now().UnixNano() / int64(time.Millisecond) fmt.Println("方法1的运行时间 :", end-start, "毫秒")
start = time.Now().UnixNano() / int64(time.Millisecond) fmt.Println("方法2的结果 :", longestDecomposition2(t)) end = time.Now().UnixNano() / int64(time.Millisecond) fmt.Println("方法2的运行时间 :", end-start, "毫秒")
fmt.Println("性能测试结束")}
复制代码



发布于: 刚刚阅读数: 4
用户头像

公众号:福大大架构师每日一题 2021-02-15 加入

公众号:福大大架构师每日一题

评论

发布
暂无评论
2023-08-18:用go写算法。你会得到一个字符串 text, 你应该把它分成 k 个子字符串 (subtext1, subtext2,…, subtextk)。 要求满足: subtexti 是_福大大架构师每日一题_福大大架构师每日一题_InfoQ写作社区