2019-09-29

Course Schedule

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
}