3137. K 周期字符串需要的最少操作次数[go语言中map学习]

简介: 【5月更文挑战第2天】go语言中map

给你一个长度为 n 的字符串 word 和一个整数 k ,其中 k 是 n 的因数。

在一次操作中,你可以选择任意两个下标 i 和 j,其中 0 <= i, j < n ,且这两个下标都可以被 k 整除,然后用从 j 开始的长度为 k 的子串替换从 i 开始的长度为 k 的子串。也就是说,将子串 word[i..i + k - 1] 替换为子串 word[j..j + k - 1] 。

返回使 word 成为 K 周期字符串 所需的 最少 操作次数。

如果存在某个长度为 k 的字符串 s,使得 word 可以表示为任意次数连接 s ,则称字符串 word 是 K 周期字符串 。例如,如果 word == "ababab",那么 word 就是 s = "ab" 时的 2 周期字符串 。

示例 1:

输入:word = "leetcodeleet", k = 4

输出:1

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

示例 2:

输入:word = "leetcoleet", k = 2

输出:3

解释:可以执行以下操作获得一个 2 周期字符串。

i j word
0 2 etetcoleet
4 0 etetetleet
6 0 etetetetet

提示:

1 <= n == word.length <= 105
1 <= k <= word.length
k 能整除 word.length 。
word 仅由小写英文字母组成。


其实这个题挺好理解,就是将长度k的的子段(没有交集)提取出来,使得他们都相同,如何使操作步骤最小化,那肯定是按照子段重复次数最多的一种来复刻,结果最小。
那么问题就转化成如何找出重复次数最多的,两次遍历找肯定超时,所以用到工具map。

这里只简单的说下怎么用,原理和底层如何,需要的再去深究。
变量名称 := make(map[数据类型]键值类型)
变量名称 := make(map[数据类型]键值类型,长度)
m:=make(map[string]int)
遍历map
for k,v :=range m{
fmt.Println(k,v)
k是键,v是值
}
也可以值调用值
for v:=range m{
fmt.Println(v)
}
也可以进行排序
sort.Strings(m) //按照字符串遍历

func minimumOperationsToMakeKPeriodic(word string, k int) int {
   
    l:=len(word)
    m:=make(map[string]int)
    for i:=0;i<l;i+=k{
   
        s:=word[i:i+k]
        m[s]++
    }
    sum:=0
    for _,v:=range m{
   
        //fmt.Println(k,v)
        if v>sum{
   
            sum=v
        }
    }

    return l/k-sum
}
目录
相关文章
|
2月前
|
人工智能 自然语言处理 算法
Go语言统计字符串中每个字符出现的次数 — 简易频率分析器
本案例实现一个字符统计程序,支持中文、英文及数字,可统计用户输入文本中各字符的出现次数,并以整洁格式输出。内容涵盖应用场景、知识点讲解、代码实现与拓展练习,适合学习文本分析及Go语言基础编程。
|
2月前
|
存储 人工智能 安全
深入理解 go sync.Map - 基本原理
本文介绍了 Go 语言中 `map` 在并发使用时的常见问题及其解决方案,重点对比了 `sync.Mutex`、`sync.RWMutex` 和 `sync.Map` 的性能差异及适用场景。文章指出,普通 `map` 不支持并发读写,容易引发错误;而 `sync.Map` 通过原子操作和优化设计,在某些场景下能显著提升性能。同时详细讲解了 `sync.Map` 的基本用法及其适合的应用环境,如读多写少或不同 goroutine 操作不同键的场景。
128 1
|
4月前
|
存储 安全 Go
Map的遍历与判断键是否存在-《Go语言实战指南》
本文介绍了 Go 语言中对 `map` 的常见操作,包括遍历所有项和判断键是否存在。通过 `for range` 可以遍历 `map` 的键值对、仅键或仅值(需忽略键)。注意,`map` 遍历顺序是随机的。判断键是否存在时,使用双赋值语法 `value, ok := map[key]`,其中 `ok` 表示键是否存在。直接访问不存在的键会返回类型的零值,可能导致逻辑错误。掌握这些机制可更安全高效地处理键值对数据。
|
5月前
|
Go 索引
【LeetCode 热题100】394:字符串解码(详细解析)(Go语言版)
本文详细解析了 LeetCode 热题 394:字符串解码。题目要求对编码字符串如 `k[encoded_string]` 进行解码,其中 `encoded_string` 需重复 `k` 次。文章提供了两种解法:使用栈模拟和递归 DFS,并附有 Go 语言实现代码。栈解法通过数字栈与字符串栈记录状态,适合迭代;递归解法则利用函数调用处理嵌套结构,代码更简洁。两者时间复杂度均为 O(n),但递归需注意栈深度问题。文章还总结了解题注意事项及适用场景,帮助读者更好地掌握字符串嵌套解析技巧。
139 6
|
6月前
|
存储 机器学习/深度学习 缓存
🚀 力扣热题 394:字符串解码(详细解析)(Go语言版)
文章提供了两种解法:栈结构和递归解法。栈解法通过维护数字栈与字符串栈,依次处理 `[` 和 `]`,构造解码结果;递归解法则利用函数调用逐层解析嵌套结构。两者时间复杂度均为 $O(n)$,空间复杂度也为 $O(n)$。栈解法直观易懂,适合初学者;递归解法优雅简洁,适合处理深度嵌套规则。掌握这两种方法,可灵活应对类似问题,提升解题能力。
185 11
|
7月前
|
存储 缓存 安全
Go 语言中的 Sync.Map 详解:并发安全的 Map 实现
`sync.Map` 是 Go 语言中用于并发安全操作的 Map 实现,适用于读多写少的场景。它通过两个底层 Map(`read` 和 `dirty`)实现读写分离,提供高效的读性能。主要方法包括 `Store`、`Load`、`Delete` 等。在大量写入时性能可能下降,需谨慎选择使用场景。
|
8月前
|
存储 安全 Go
Go语言中的map数据结构是如何实现的?
Go 语言中的 `map` 是基于哈希表实现的键值对数据结构,支持快速查找、插入和删除操作。其原理涉及哈希函数、桶(Bucket)、动态扩容和哈希冲突处理等关键机制,平均时间复杂度为 O(1)。为了确保线程安全,Go 提供了 `sync.Map` 类型,通过分段锁实现并发访问的安全性。示例代码展示了如何使用自定义结构体和切片模拟 `map` 功能,以及如何使用 `sync.Map` 进行线程安全的操作。
226 9
|
9月前
|
Go
go语言for遍历映射(map)
go语言for遍历映射(map)
309 12
|
7月前
|
编译器 Go
揭秘 Go 语言中空结构体的强大用法
Go 语言中的空结构体 `struct{}` 不包含任何字段,不占用内存空间。它在实际编程中有多种典型用法:1) 结合 map 实现集合(set)类型;2) 与 channel 搭配用于信号通知;3) 申请超大容量的 Slice 和 Array 以节省内存;4) 作为接口实现时明确表示不关注值。此外,需要注意的是,空结构体作为字段时可能会因内存对齐原因占用额外空间。建议将空结构体放在外层结构体的第一个字段以优化内存使用。
|
7月前
|
运维 监控 算法
监控局域网其他电脑:Go 语言迪杰斯特拉算法的高效应用
在信息化时代,监控局域网成为网络管理与安全防护的关键需求。本文探讨了迪杰斯特拉(Dijkstra)算法在监控局域网中的应用,通过计算最短路径优化数据传输和故障检测。文中提供了使用Go语言实现的代码例程,展示了如何高效地进行网络监控,确保局域网的稳定运行和数据安全。迪杰斯特拉算法能减少传输延迟和带宽消耗,及时发现并处理网络故障,适用于复杂网络环境下的管理和维护。