func canFinish(numCourses int, prerequisites [][]int) bool {
m := make(map[int][]int)
res := make([]int, numCourses)
for _, p := range prerequisites {
v, ok := m[p[0]]
if !ok {
m[p[0]] = []int{p[1]}
} else {
m[p[0]] = append(v, p[1])
}
}
for i := 0; i < numCourses; i++ {
if helper(i, res, m) == false {
return false
}
}
return true
}
func helper(idx int, res []int, m map[int][]int) bool {
if res[idx] == 1 {
return true
}
if res[idx] == 2 {
return false
}
v, ok := m[idx]
if !ok {
return true
}
res[idx] = 2
for i := 0; i < len(v); i++ {
if helper(v[i], res, m) == false {
return false
}
}
res[idx] = 1
return true
}
Longest Repeating Character Replacement
func characterReplacement(s string, k int) int {
if len(s) == 0 {
return 0
}
str := []byte(s)
start, end := 0, 0
ret := 0
c := make([]int, 26)
c[str[0]-'A']++
for len(str) > end {
maxc := 0
for i := 0; i < 26; i++ {
if c[i] > maxc {
maxc = c[i]
}
}
if maxc+k > end-start {
end++
if end < len(str) {
c[str[end]-'A']++
}
} else {
c[str[start]-'A']--
start++
}
if maxc+k > ret {
if maxc+k <= len(str) {
ret = maxc + k
} else {
ret = len(str)
}
}
}
return ret
}
Group Anagrams
type sortRunes []rune
func (s sortRunes) Less(i, j int) bool {
return s[i] < s[j]
}
func (s sortRunes) Swap(i, j int) {
s[i], s[j] = s[j], s[i]
}
func (s sortRunes) Len() int {
return len(s)
}
func SortString(s string) string {
r := []rune(s)
sort.Sort(sortRunes(r))
return string(r)
}
func groupAnagrams(strs []string) [][]string {
ret := [][]string{}
dic := make(map[string]int, len(strs))
idx := 0
for _, str := range strs {
tmp := SortString(str)
val, ok := dic[tmp]
if ok == false {
dic[tmp] = idx
ret = append(ret, []string{})
ret[idx] = append(ret[idx], str)
idx++
} else {
ret[val] = append(ret[val], str)
}
}
return ret
}
