- VisualStudio2022插件的安装及使用-编程手把手系列文章
- pprof-在现网场景怎么用
- C#实现的下拉多选框,下拉多选树,多级节点
- 【学习笔记】基础数据结构:猫树
给你一个字符串 s 、一个字符串 t 。返回 s 中涵盖 t 所有字符的最小子串。如果 s 中不存在涵盖 t 所有字符的子串,则返回空字符串 "" 。 注意: 对于 t 中重复字符,我们寻找的子字符串中该字符数量必须不少于 t 中该字符数量。 如果 s 中存在这样的子串,我们保证它是唯一的答案.
示例 1: 输入:s = "ADOBECODEBANC", t = "ABC" 输出:"BANC" 解释:最小覆盖子串 "BANC" 包含来自字符串 t 的 'A'、'B' 和 'C'.
题目分析: 看到这类最长最短子串等,则首选滑动窗口方法。按照滑动窗口的方法,重点应该是确定满足要求时窗口的状态: 这里是包含字符串t的所有元素就可以,不要求有序,那么使用哈希表来记录就是很好的办法,同时要求最短,即后续要优化,因为可能T的元素会在s中常重复出现,那么哈希表的值设置为频率就能很好达到——》元素出现,并且频率一次就是最短的状态。因为是字符,所以哈希表设计为 var targetFreq :=map[byte]int。 那么targetFreq的长度就代表了目标字符串的元素种类.
func minWindow(s string, t string) string {
if len(s)==0 || len(t)==0{return ""}
left,right,matchCount:=0,0,0
//记录最短序列的开始位置,结合最短长度即可得到最短序列
start:=0
//记录最短长度
minLength := len(s)+1
//记录目标序列的元素的种类和个数。这样无论元素是否有重复,只要这两个要求都满足就可以
targetFreq := make(map[byte]int)
for i := 0; i < len(t); i++ {
targetFreq[t[i]]++
}
//用于记录当前窗口中的元素种类数量情况
windowFreq := make(map[byte]int)
for right<len(s){
charRight := s[right]
right++
//只统计目标序列中的元素即可。
if _,exists:=targetFreq[charRight];exists{
windowFreq[charRight]++
//如果某个元素的数量已经满足了目标序列的数量要求,那么完成的元素数量++
if windowFreq[charRight] == targetFreq[charRight] {
matchCount++
}
}
//所有元素数量已经符合要求,现在看能否缩小序列
for matchCount == len(targetFreq){
if right-left <minLength{
minLength = right-left
start = left
}
charLeft:= s[left]
left++
// 尝试缩小边界
if _,exists:=targetFreq[charLeft];exists{
if windowFreq[charLeft] == targetFreq[charLeft]{
matchCount--
}
windowFreq[charLeft]--
}
}
}
if minLength == len(s)+1{return ""}
return s[start:start+minLength]
}
最后此篇关于76.最小覆盖子串Golang实现的文章就讲到这里了,如果你想了解更多关于76.最小覆盖子串Golang实现的内容请搜索CFSDN的文章或继续浏览相关文章,希望大家以后支持我的博客! 。
我正在尝试创建一个程序,其中字符串的前三个字符重复给定次数,如下所示: foo('Chocolate', 3) # => 'ChoChoCho' foo('Abc', 3) # => 'AbcAbcA
我有以下字符串: std::string str = "Mode:AAA:val:101:id:A1"; 我想分离一个位于 "val:" 和 ":id" 之间的子字符串,这是我的方法: std::st
DNA 字符串可以是任意长度,包含 5 个字母(A、T、G、C、N)的任意组合。 压缩包含 5 个字母(A、T、G、C、N)的 DNA 字母串的有效方法是什么?不是考虑每个字母表 3 位,我们可以使用
是否有一种使用 levenstein 距离将一个特定字符串与第二个较长字符串中的任何区域进行匹配的好方法? 例子: str1='aaaaa' str2='bbbbbbaabaabbbb' if str
使用 OAuth 并使用以下函数使用我们称为“foo”(实际上是 OAuth token )的字符串加密 key public function encrypt( $text ) { // a
我是一名优秀的程序员,十分优秀!