题目的通过率越来越低，题目越来越长，题意不好理解，边界问题，优化问题叠加，导致解题时间大大增加，对我的目标--快速复习一遍技术数据结构和算法阻碍很大啊！已经写了一百多道题了，是时候针对性的做一些题目了。目前打算从以下方面针对性的做一些题目：
数据结构：
- 位操作
- 数组
- 链表
-
二叉树
算法： - 暴力法
- 贪心法
- 动态规划
- 背包问题
- 装箱问题
优先对链表，二叉树，动态规划这几个问题强化练习一下
题目
Given a string s and a non-empty string p, find all the start indices of p's anagrams in s.
Strings consists of lowercase English letters only and the length of both strings s and p will not be larger than 20,100.
The order of output does not matter.
Example 1:
Input:
s: "cbaebabacd"
p: "abc"
Output:
[0, 6]
Explanation:
The substring with start index = 0 is "cba", which is an anagram of "abc".
The substring with start index = 6 is "bac", which is an anagram of "abc".
Example 2:
Input:
s: "abab"
p: "ab"
Output:
[0, 1, 2]
Explanation:
The substring with start index = 0 is "ab", which is an anagram of "ab".
The substring with start index = 1 is "ba", which is an anagram of "ab".
The substring with start index = 2 is "ab", which is an anagram of "ab".
解题思路
从s中找到所有p的anagrams的起始位置
解法1
比较粗暴的解法就是遍历s，从s中截取和p等长的子串s1，然后比较s1和p是否为anagrams。
截取s1
需要遍历s，每次截取和p等长的子串s1，时间复杂度O((n-p+1)p) = O(np)
判断anagrams
比较s1和p是否为anagrams就是比较各字符出现的次数是否相等，将s1各字符出现的次数放入map中，然后遍历p，如果p中字符在map中没有出现过，说明不是anagrams；如果出现过，则将map中改字符的值减1，最终判断map中各值是否都为0，如果有不为0的，说明不是anagrams，否则为anagrams。时间复杂度为O(p + p) = O(p)。
总的时间复杂度为O(n*p2)
这样的解法会导致超时
解法2
考虑到s1中有p-2个数是重叠的，可以在s1向后移的时候，增加后一个字符出现的次数，减少前一个字符出现的次数
并且将p中的字符也放入pMap中，遇到sMap中出现的字符直接判断字符出现的个数，如果次数不等则不是anagrams，相等则将sMap中的对应值置为0.遍历后如果所有sMap中的值都为0，则为anagrams，否则不是anagrams。时间复杂度为O(1)
总的时间复杂度为O(n)
代码
findAnagrams.go
package _438_Find_All_Anagrams_in_a_String
import "fmt"
func FindAnagrams(s string, p string) []int {
lenP := len(p)
var ret []int
lenS := len(s)
if lenS < lenP {
return []int{}
}
var charMap map[byte]int
charMap = make(map[byte]int)
for i := 0; i < lenP; i++ {
charMap[p[i]]++
}
var sMap map[byte]int
sMap = make(map[byte]int)
for i := 0; i < lenP; i++ {
sMap[s[i]]++
}
for i := 0; i < lenS - lenP + 1; i++ {
fmt.Printf("%+v\n", s[i:i+lenP])
isAnagrams := true
var tmpMap map[byte]int
tmpMap = make(map[byte]int)
for k, v := range charMap {
tmpMap[k] = v
}
if i > 0 {
sMap[s[i+lenP-1]]++
sMap[s[i-1]]--
}
for k, v := range sMap {
if 0 == v {
continue
}
_, ok := tmpMap[k]
if !ok {
isAnagrams = false
break
}
tmpMap[k] -= v
}
if isAnagrams {
for _, v := range tmpMap {
if v > 0 {
isAnagrams = false
break
}
}
}
if isAnagrams {
ret = append(ret, i)
}
}
return ret
}
测试
findAnagrams_test.go
package _438_Find_All_Anagrams_in_a_String
import "testing"
func equalSlice(s, p []int) bool {
len1 := len(s)
len2 := len(p)
if len1 != len2 {
return false
}
for i := 0; i < len1; i++ {
if s[i] != p[i] {
return false
}
}
return true
}
func TestFindAnagrams(t *testing.T) {
var tests = []struct{
s string
p string
ret []int
} {
{"cbaebabacd", "abc", []int{0,6}},
{"baa", "aa", []int{1}},
}
for _, v := range tests {
ret := FindAnagrams(v.s, v.p)
if equalSlice(ret, v.ret) {
t.Logf("pass")
} else {
t.Errorf("fail, want %+v, get %+v", v.ret, ret)
}
}
}
