2024-05-04:用go语言,给定一个起始索引为0的字符串s和一个整数k

2024-05-04:用go语言,给定一个起始索引为0的字符串s和一个整数k。

要进行分割操作,直到字符串s为空:

选择s的最长前缀,该前缀最多包含k个不同字符;

删除该前缀,递增分割计数。如果有剩余字符,它们保持原来的顺序。

在操作之前,可以修改字符串s中的一个字符为另一个小写英文字母。

在最佳情况下修改至多一次字符后,返回操作结束时得到的最大分割数量。

输入:s = “accca”, k = 2。

输出:3。

答案2024-05-04:

chatgpt

题目来自leetcode3003。

大体步骤如下:

1.创建一个递归函数dfs,用于计算分割得到的最大数量。

2.函数中,首先检查是否到达字符串末尾,若是则返回 1(表示完成一个分割)。

3.使用memo记录中间结果,加快计算速度。

4.对于当前处理的字符s[i],如果不将其作为新的分割点,继续处理下一个字符。

5.如果将s[i]作为新的分割点,并且新的字符数量不超过k,则继续向后处理。

6.如果未修改过字符,则尝试修改s[i]为其他26个小写字母,然后继续考虑分割带来的最大数量。

7.在每一步中,根据是否修改过字符,记录当前的最大分割数量。

8.最终返回得到的最大分割数量。

总的时间复杂度为 $O(n \cdot 2^{26})$,其中$n$为字符串长度,$2^{26}$表示尝试修改字符的可能性数目。

总的额外空间复杂度为$O(n \cdot 2^{26})$,主要由memo中间结果记录所占用的空间引起。

Go完整代码如下:

package main

import (
    "fmt"
    "math/bits"
)

func max(x, y int) int {
    if x > y {
        return x
    }
    return y
}

func maxPartitionsAfterOperations(s string, k int) int {
    n := len(s)
    type args struct {
        i, mask int
        changed bool
    }
    memo := map[args]int{}
    var dfs func(int, int, bool) int
    dfs = func(i, mask int, changed bool) (res int) {
        if i == n {
            return 1
        }

        a := args{i, mask, changed}
        if v, ok := memo[a]; ok { // 之前计算过
            return v
        }

        // 不改 s[i]
        bit := 1 << (s[i] - 'a')
        newMask := mask | bit
        if bits.OnesCount(uint(newMask)) > k {
            // 分割出一个子串,这个子串的最后一个字母在 i-1
            // s[i] 作为下一段的第一个字母,也就是 bit 作为下一段的 mask 的初始值
            res = dfs(i+1, bit, changed) + 1
        } else { // 不分割
            res = dfs(i+1, newMask, changed)
        }

        if !changed {
            // 枚举把 s[i] 改成 a,b,c,...,z
            for j := 0; j < 26; j++ {
                newMask := mask | 1<<j
                if bits.OnesCount(uint(newMask)) > k {
                    // 分割出一个子串,这个子串的最后一个字母在 i-1
                    // j 作为下一段的第一个字母,也就是 1<<j 作为下一段的 mask 的初始值
                    res = max(res, dfs(i+1, 1<<j, true)+1)
                } else { // 不分割
                    res = max(res, dfs(i+1, newMask, true))
                }
            }
        }

        memo[a] = res // 记忆化
        return res
    }
    return dfs(0, 0, false)
}

func main() {
    s := "accca"
    k := 2
    result := maxPartitionsAfterOperations(s, k)
    fmt.Println(result)
}

在这里插入图片描述

Python完整代码如下:

# -*-coding:utf-8-*-

def max_partitions_after_operations(s, k):
    n = len(s)
    memo = {}

    def dfs(i, mask, changed):
        if i == n:
            return 1

        a = (i, mask, changed)
        if a in memo:
            return memo[a]

        res = 0
        bit = 1 << (ord(s[i]) - ord('a'))
        new_mask = mask | bit

        if bin(new_mask).count('1') > k:
            res = dfs(i + 1, bit, changed) + 1
        else:
            res = dfs(i + 1, new_mask, changed)

        if not changed:
            for j in range(26):
                new_mask = mask | 1 << j
                if bin(new_mask).count('1') > k:
                    res = max(res, dfs(i + 1, 1 << j, True) + 1)
                else:
                    res = max(res, dfs(i + 1, new_mask, True))

        memo[a] = res
        return res

    return dfs(0, 0, False)

s = "accca"
k = 2
result = max_partitions_after_operations(s, k)
print(result)

在这里插入图片描述

本作品采用《CC 协议》,转载必须注明作者和本文链接
微信公众号:福大大架构师每日一题。最新面试题,涉及golang,rust,mysql,redis,云原生,算法,分布式,网络,操作系统。
讨论数量: 0
(= ̄ω ̄=)··· 暂无内容!

讨论应以学习和精进为目的。请勿发布不友善或者负能量的内容,与人为善,比聪明更重要!
未填写
文章
477
粉丝
23
喜欢
37
收藏
22
排名:454
访问:2.0 万
私信
所有博文
社区赞助商