个人中心
gpt4 book ai didi

2024-12-14：K周期字符串需要的最少操作次数。用go语言，给定一个长度为n的字符串word和一个整数k，k是n的因数。每次操作可以选择两个下标i和j，使得i和j都可以被k整除，然后用从j

转载 作者：撒哈拉 更新时间：2024-12-14 20:47:42 56 4
gpt4 key购买 nike

2024-12-14：K 周期字符串需要的最少操作次数。用go语言，给定一个长度为n的字符串 word 和一个整数k，k是n的因数。每次操作可以选择两个下标i和j，使得i和j都可以被k整除，然后用从j开始的长度为k的子串替换从i开始的长度为k的子串。要使得word成为一个K周期字符串，需要进行最少的操作次数.

一个K周期字符串是指存在一个长度为k的字符串s，通过多次连接s可以得到word。比如，如果word == "ababab"，那么当s = "ab"时，word是一个2周期字符串.

现在，请计算使word成为K周期字符串所需的最少操作次数.

1 <= n == word.length <= 100000.

1 <= k <= word.length.

k 能整除 word.length .

word 仅由小写英文字母组成.

输入：word = "leetcodeleet", k = 4.

输出：1.

解释：可以选择 i = 4 和 j = 0 获得一个 4 周期字符串。这次操作后，word 变为 "leetleetleet".

答案2024-12-14:

chatgpt 。

题目来自leetcode3137.

大体步骤如下：

1.初始化变量 n 为字符串 word 的长度，并设定变量 res 初始值为最大整数.

2.创建一个空的计数映射 count，用于存储不同子串的出现次数.

3.遍历字符串 word 中长度为 k 的子串，依次检查每个子串.

4.在循环中，统计每个长度为 k 的子串出现的次数，更新 res 为使得 word 成为 K 周期字符串所需的最少操作次数.

5.返回最少操作次数 res.

总体时间复杂度:

  • 遍历整个字符串 word 需要 O(n/k) 的时间.

  • 在每一步中，计算和更新 res 的时间复杂度为 O(1).

  • 因此，总体时间复杂度为 O(n/k).

总体额外空间复杂度:

  • 需要额外的空间来存储计数映射 count，其大小取决于字符串中包含 unique 子串的数量，最坏情况下可达到 O(n/k).

  • 因此，总体额外空间复杂度为 O(n/k).

Go完整代码如下：

package main

import (
	"fmt"
	"math"
)

func minimumOperationsToMakeKPeriodic(word string, k int) int {
	n, res := len(word), math.MaxInt
	count := map[string]int{}
	for i := 0; i < n; i += k {
		count[word[i:i+k]]++
		res = min(res, n/k-count[word[i:i+k]])
	}
	return res
}

func main() {
	word := "leetcodeleet"
	k := 4
	fmt.Println(minimumOperationsToMakeKPeriodic(word, k))
}

在这里插入图片描述

Rust完整代码如下：

use std::collections::HashMap;

fn min_operations_to_make_k_periodic(word: &str, k: usize) -> i32 {
    let n = word.len();
    let mut res = i32::MAX;
    let mut count: HashMap<&str, i32> = HashMap::new();

    for i in (0..n).step_by(k) {
        let sub_str = &word[i..i+k];
        *count.entry(sub_str).or_insert(0) += 1;
        res = res.min((n / k) as i32 - *count.get(&sub_str).unwrap_or(&0));
    }

    res
}

fn main() {
    let word = "leetcodeleet";
    let k = 4;
    println!("{}", min_operations_to_make_k_periodic(word, k));
}

在这里插入图片描述

最后此篇关于2024-12-14：K周期字符串需要的最少操作次数。用go语言，给定一个长度为n的字符串word和一个整数k，k是n的因数。每次操作可以选择两个下标i和j，使得i和j都可以被k整除，然后用从j的文章就讲到这里了,如果你想了解更多关于2024-12-14：K周期字符串需要的最少操作次数。用go语言，给定一个长度为n的字符串word和一个整数k，k是n的因数。每次操作可以选择两个下标i和j，使得i和j都可以被k整除，然后用从j的内容请搜索CFSDN的文章或继续浏览相关文章，希望大家以后支持我的博客！ 。

56 4 0
文章推荐： Redis应用—2.在列表数据里的应用
文章推荐： ChatGPT生成测试用例的最佳实践（一）
文章推荐： 深度学习入门笔记——神经网络的构建和使用
文章推荐： 【杂谈】后台日志该怎么打印
撒哈拉
个人简介

我是一名优秀的程序员,十分优秀！

滴滴打车优惠券免费领取
滴滴打车优惠券
全站热门文章
Copyright 2021 - 2024 cfsdn All Rights Reserved 蜀ICP备2022000587号
广告合作:1813099741@qq.com 6ren.com