2022年02月LeetCode每日一题

20220216 1719. 重构一棵树的方案数 困难

func checkWays(pairs [][]int) int {
    adj := map[int]map[int]bool{}
    for _, p := range pairs {
        x, y := p[0], p[1]
        if adj[x] == nil {
            adj[x] = map[int]bool{}
        }
        adj[x][y] = true
        if adj[y] == nil {
            adj[y] = map[int]bool{}
        }
        adj[y][x] = true
    }

    // 检测是否存在根节点
    root := -1
    for node, neighbours := range adj {
        if len(neighbours) == len(adj)-1 {
            root = node
            break
        }
    }
    if root == -1 {
        return 0
    }

    ans := 1
    for node, neighbours := range adj {
        if node == root {
            continue
        }

        currDegree := len(neighbours)
        parent := -1
        parentDegree := math.MaxInt32
        // 根据 degree 的大小找到 node 的父节点 parent
        for neighbour := range neighbours {
            if len(adj[neighbour]) < parentDegree && len(adj[neighbour]) >= currDegree {
                parent = neighbour
                parentDegree = len(adj[neighbour])
            }
        }
        if parent == -1 {
            return 0
        }
        // 检测 neighbours 是否为 adj[parent] 的子集
        for neighbour := range neighbours {
            if neighbour != parent && !adj[parent][neighbour] {
                return 0
            }
        }

        if parentDegree == currDegree {
            ans = 2
        }
    }
    return ans
}

20220217 688. 骑士在棋盘上的概率 中等

var dirs = []struct{ i, j int }{{-2, -1}, {-2, 1}, {2, -1}, {2, 1}, {-1, -2}, {-1, 2}, {1, -2}, {1, 2}}

func knightProbability(n, k, row, column int) float64 {
    dp := make([][][]float64, k+1)
    for step := range dp {
        dp[step] = make([][]float64, n)
        for i := 0; i < n; i++ {
            dp[step][i] = make([]float64, n)
            for j := 0; j < n; j++ {
                if step == 0 {
                    dp[step][i][j] = 1
                } else {
                    for _, d := range dirs {
                        if x, y := i+d.i, j+d.j; 0 <= x && x < n && 0 <= y && y < n {
                            dp[step][i][j] += dp[step-1][x][y] / 8
                        }
                    }
                }
            }
        }
    }
    return dp[k][row][column]
}

20220218 1791. 找出星型图的中心节点 简单

// 方法一：
func findCenter(edges [][]int) int {
    n := len(edges) + 1
    degrees := make([]int, n+1)
    for _, e := range edges {
        degrees[e[0]]++
        degrees[e[1]]++
    }
    for i, d := range degrees {
        if d == n-1 {
            return i
        }
    }
    return -1
}

// 方法二：
func findCenter(edges [][]int) int {
    if edges[0][0] == edges[1][0] || edges[0][0] == edges[1][1] {
        return edges[0][0]
    }
    return edges[0][1]
}

20220219 969. 煎饼排序 中等

func pancakeSort(arr []int) (ans []int) {
    for n := len(arr); n > 1; n-- {
        idx := 0
        for i, v := range arr[:n] {
            if v > arr[idx] { // 找最大值
                idx = i
            }
        }
        if idx == n - 1 {
            continue
        }
        // 1次翻转
        for i, m := 0, idx; i < (m+1)/2; i++ {
            arr[i], arr[m-i] = arr[m-i], arr[i]
        }
        // 2次翻转
        for i := 0; i < n/2; i++ {
            arr[i], arr[n-1-i] = arr[n-1-i], arr[i]
        }
        ans = append(ans, idx+1, n)
    }
    return ans
}

20220220 717. 1比特与2比特字符 简单

// 方法一：正序
func isOneBitCharacter(bits []int) bool {
    i, n := 0, len(bits)
    for i < n - 1 {
        i += bits[i] + 1
    }
    return i == n - 1
}
// 方法二：倒序
func isOneBitCharacter(bits []int) bool {
    n := len(bits)
    i := n - 2
    for i >= 0 && bits[i] == 1 {
        i--
    }
    return (n-i)%2 == 0
}

20220221 838. 推多米诺 中等

func pushDominoes(dominoes string) string {
    s := []byte(dominoes)
    i, n, left := 0, len(s), byte('L')
    for i < n {
        j := i
        for j < n && s[j] == '.' { // 找到一段连续的没有被推动的骨牌
            j++
        }
        right := byte('R')
        if j < n {
            right = s[j]
        }
        if left == right { // 方向相同，那么这些竖立骨牌也会倒向同一方向
            for i < j {
                s[i] = right
                i++
            }
        } else if left == 'R' && right == 'L' { // 方向相对，那么就从两侧向中间倒
            k := j - 1
            for i < k {
                s[i] = 'R'
                s[k] = 'L'
                i++
                k--
            }
        }
        left = right
        i = j + 1
    }
    return string(s)
}

20220222 1994. 好子集的数目 困难

var primes = []int{2, 3, 5, 7, 11, 13, 17, 19, 23, 29}

func numberOfGoodSubsets(nums []int) (ans int) {
    const mod int = 1e9 + 7
    freq := [31]int{}
    for _, num := range nums {
        freq[num]++
    }

    f := make([]int, 1<<len(primes))
    f[0] = 1
    for i := 0; i < freq[1]; i++ {
        f[0] = f[0] * 2 % mod
    }
next:
    for i := 2; i < 31; i++ {
        if freq[i] == 0 {
            continue
        }

        // 检查 i 的每个质因数是否均不超过 1 个
        subset := 0
        for j, prime := range primes {
            if i%(prime*prime) == 0 {
                continue next
            }
            if i%prime == 0 {
                subset |= 1 << j
            }
        }

        // 动态规划
        for mask := 1 << len(primes); mask > 0; mask-- {
            if mask&subset == subset {
                f[mask] = (f[mask] + f[mask^subset]*freq[i]) % mod
            }
        }
    }

    for _, v := range f[1:] {
        ans = (ans + v) % mod
    }
    return
}

20220223 917. 仅仅反转字母 简单

func reverseOnlyLetters(s string) string {
    sb := []byte(s)
    l, r := 0, len(sb) - 1
    for l < r {
        for l < r && !unicode.IsLetter(rune(s[l]))  {
            l++
        }
        for l < r && !unicode.IsLetter(rune(s[r]))  {
            r--
        }
        sb[l], sb[r] = sb[r], sb[l]
        l++
        r--
    }
    return string(sb)
}

20220224 1706. 球会落何处 中等

func findBall(grid [][]int) []int {
    n := len(grid[0])
    ans := make([]int, n)
    for j := range ans {
        col := j // 球的初始列
        for _, row := range grid {
            dir := row[col]
            col += dir // 移动球
            if col < 0 || col == n || row[col] != dir { // 到达侧边或 V 形
                col = -1
                break
            }
        }
        ans[j] = col // col >= 0 为成功到达底部
    }
    return ans
}

20220227 553. 最优除法

func optimalDivision(nums []int) string {
    n := len(nums)
    if n == 1 {
        return strconv.Itoa(nums[0])
    }
    if n == 2 {
        return fmt.Sprintf("%d/%d", nums[0], nums[1])
    }
    ans := &strings.Builder{}
    ans.WriteString(fmt.Sprintf("%d/(%d", nums[0], nums[1]))
    for _, num := range nums[2:] {
        ans.WriteByte('/')
        ans.WriteString(strconv.Itoa(num))
    }
    ans.WriteByte(')')
    return ans.String()
}