January

1-18 统计元音字母序列的数目

🧩 线性dp

func countVowelPermutation(n int) (ans int) {
    const mod = 1e9 + 7
    f := []int{1, 1, 1, 1, 1}
    for n > 1 {
        f = []int{
            (f[1] + f[2] + f[4]) % mod,
            (f[0] + f[2]) % mod,
            (f[1] + f[3]) % mod,
            f[2],
            (f[2] + f[3]) % mod,
        }
        n--
    }
    for _, num := range f {
        ans = (ans + num) % mod
    }
    return
}

1-08 格雷编码

func grayCode(n int) []int {
    ans := make([]int, 1, 1<<n);
    for i := 1; i <= n; i++ {
        for j := len(ans)-1; j >= 0; j-- {
            ans = append(ans, ans[j]|1<<(i-1))
        }
    }
    return ans
}

🧩 二进制数转格雷码

func grayCode(n int) []int {
    ans := make([]int, 1<<n)
    for i := range ans {
        ans[i] = i>>1 ^ i
    }
    return ans
}

1-03 一周中的第几天

🧩 蔡勒公式

// w:星期
// c:世纪(公元后世纪取值为已经过的世纪数,即year / 100;公元前世纪则为所在世纪的编号,如公元前253年,是公元前3世纪,c就等于-3)
// y:年(y = year MOD 100 + year < 0 ? 100 : 0)
// m:月(3 <= m <= 14,在蔡勒公式中,某年的1、2月要看作上一年的13、14月来计算)
// d:日。
func dayOfTheWeek(day, month, year int) string {
    week := []string{"Sunday", "Monday", "Tuesday", "Wednesday", "Thursday", "Friday", "Saturday"}
    m, y := month, year
    if month < 3 {
        m += 12
        y -= 1
    }
    // 蔡勒公式
    c := y / 100
    y %= 100
    D := c/4 - 2*c + y + y/4 + 13*(m+1)/5 + day - 1 + 210 // 加上30*7防止出现负数
    return week[D%7]
}

1-02 消除游戏

🧩 等差数列

func lastRemaining(n int) int {
    a, k, cnt, step := 1, 0, n, 1
    for cnt > 1 {
        if k%2 == 0 { // 正向
            a += step
        } else { // 反向
            if cnt%2 == 1 {
                a += step
            }
        }
        k++
        cnt >>= 1
        step <<= 1
    }
    return a
}

—— 2021 ——

December

12-28 连接词

🧩 trie树

type trie struct {
    sub   [26]*trie
    isEnd bool
}

func (root *trie) insert(word string) {
    cur := root
    for _, ch := range word {
        if cur.sub[ch-'a'] == nil {
            cur.sub[ch-'a'] = &trie{}
        }
        cur = cur.sub[ch-'a']
    }
    cur.isEnd = true
}

func (root *trie) dfs(word string) bool {
    if word == "" {
        return true
    }
    cur := root
    for i, ch := range word {
        cur = cur.sub[ch-'a']
        if cur == nil {
            return false
        }
        if cur.isEnd && root.dfs(word[i+1:]) {
            return true
        }
    }
    return false
}

func findAllConcatenatedWordsInADict(words []string) (ans []string) {
    sort.Slice(words, func(i, j int) bool {
        return len(words[i]) < len(words[j])
    })
    root := &trie{}
    for _, w := range words {
        if len(w) == 0 {
            continue
        }
        if root.dfs(w) {
            ans = append(ans, w)
        } else {
            root.insert(w)
        }
    }
    return
}

12-27 适龄的朋友

🧩 双指针

func numFriendRequests(ages []int) (ans int) {
    sort.Ints(ages)
    l, r := 0, 0
    for _,a := range ages {
        if a < 15 {
            continue
        }
        for ages[l] * 2 <= a + 14 {
            l++
        }
        for r < len(ages) - 1 && ages[r + 1] <= a {
            r++
        }
        ans += r - l;
    }
    return
}

🧩 前缀和

func numFriendRequests(ages []int) (ans int) {
    const n = 121
    cnt := make([]int, n)
    for _, a := range ages {
        cnt[a] ++
    }
    pre := make([]int, n)
    for i := 1; i < n; i++ {
        pre[i] = pre[i - 1] + cnt[i];
    }

    for i := 15; i < n; i++ {
        if cnt[i] > 0 {
            ans += cnt[i] * (pre[i] - pre[i / 2 + 7] - 1)
        }
    }
    return ans
}

12-24 吃苹果的最大数目

🧩 贪心+堆

func eatenApples(apples []int, days []int) (ans int) {
    h := hp{}
    i := 0
    for ; i < len(apples); i++ {
        for len(h) > 0 && h[0].end <= i {
            heap.Pop(&h)
        }
        if apples[i] > 0 {
            heap.Push(&h, pair{i + days[i], apples[i]})
        }
        if len(h) > 0 {
            h[0].left--
            if h[0].left == 0 {
                heap.Pop(&h)
            }
            ans++
        }
    }

    for len(h) > 0 {
        for len(h) > 0 && h[0].end <= i {
            heap.Pop(&h)
        }
        if len(h) == 0 {
            break
        }
        p := heap.Pop(&h).(pair)
        num := min(p.end-i+1, p.left)
        ans += num
        i += num
    }
    return
}

type pair struct{ end, left int }
type hp []pair

func (h hp) Len() int            { return len(h) }
func (h hp) Less(i, j int) bool  { return h[i].end < h[j].end }
func (h hp) Swap(i, j int)       { h[i], h[j] = h[j], h[i] }
func (h *hp) Push(v interface{}) { *h = append(*h, v.(pair)) }
func (h *hp) Pop() interface{}   { a := *h; v := a[len(a)-1]; *h = a[:len(a)-1]; return v }

12-08 三个无重叠子数组的最大和🔫

🧩 滑动窗口

func maxSumOfThreeSubarrays(nums []int, k int) (ans []int) {
    var sum1, maxSum1, maxSum1Idx int
    var sum2, maxSum2, maxSum12Idx1, maxSum12Inx2 int
    var sum3, maxSum3 int

    for i := 2 * k; i < len(nums); i++ {
        sum1 += nums[i-2*k]
        sum2 += nums[i-k]
        sum3 += nums[i]
        if i >= 3*k-1 {
            if maxSum1 < sum1 {
                maxSum1 = sum1
                maxSum1Idx = i - 3*k + 1
            }
            if maxSum2 < maxSum1+sum2 {
                maxSum2 = maxSum1 + sum2
                maxSum12Idx1 = maxSum1Idx
                maxSum12Inx2 = i - 2*k + 1
            }
            if maxSum3 < maxSum2+sum3 {
                maxSum3 = maxSum2 + sum3
                ans = []int{maxSum12Idx1, maxSum12Inx2, i - k + 1}
            }
            sum1 -= nums[i-3*k+1]
            sum2 -= nums[i-2*k+1]
            sum3 -= nums[i-k+1]
        }
    }
    return
}

12-05 超级次方

🧩 快速幂

const mod = 1337

func superPow(a int, b []int) (ans int) {
    ans = 1
    for i := len(b) - 1; i >= 0; i -- {
        ans = ans * pow(a, b[i]) % mod;
        a = pow(a, 10);
    }
    return
}

func pow(x, n int) (ans int) {
    ans = 1
    for n > 0 {
        if n & 1 == 1 {
            ans = ans * x % mod
        }
        x = x * x % mod
        n >>= 1
    }
    return
}

Try and fail, but don't fail to try.