周赛347

2710. 移除字符串中的尾随零

示例代码：

func removeTrailingZeros(num string) string {
    b := []byte(num)
    i := len(b)
    for ; i > 0 && num[i] == '0'; i-- {
    }
    return string(b[:i+1])
    
    // return strings.TrimRight(num, "0") // 库函数写法
}

2711. 对角线上不同值的数量差

暴力前后缀分解

解题思路

枚举每个位置，往左上和右下遍历，用哈希表统计不同元素个数

示例代码

func differenceOfDistinctValues(grid [][]int) [][]int {
    m, n := len(grid), len(grid[0])
    ans := make([][]int, m)
    
    for i := range ans {
        ans[i] = make([]int, n)
        for j := range ans[i] {
            // 左上
            set := map[int]struct{}{}
            for x, y := i-1, j-1; x >= 0 && y >= 0; {
                set[grid[x][y]] = struct{}{}
                x--
                y--
            }
            sz := len(set)
            
            // 右下
            set = map[int]struct{}{}
            for x, y := i+1, j+1; x < m && y < n; {
                set[grid[x][y]] = struct{}{}
                x++
                y++
            }
            ans[i][j] = abs(sz, len(set))
        }
    }
    return ans
}

func abs(a, b int) int {
    if a < b {
        return b - a
    }
    return a - b
}

解题思路

从第一行和第一列的每个位置出发，向右下遍历，这一条线为s，s范围为[1, m+n-1]，m为行数，n为列数。从最后一行和最后一列出发去遍历，第一列从上到下。

横纵坐标分别为i,j，根据每一条线纵坐标的范围，minJ := max(0, n-s)，maxJ := min(n-1, n-s+m-1)，因为在一条只显示，所以i-j的值是固定的，为s-n，i := s + j - n，有了横纵坐标，就可以一次遍历求出所有的结果

具体讲解见: https://www.bilibili.com/video/BV1fo4y1T7MQ?t=630.2

示例代码

func differenceOfDistinctValues(grid [][]int) [][]int {
    m, n := len(grid), len(grid[0])
    ans := make([][]int, m)
    for i := range ans {
        ans[i] = make([]int, n)
    }
    for s := 1; s < m+n; s++ {
        minJ := max(0, n-s)
        maxJ := min(n-1, n-s+m-1)
        
        // topLeft
        set := map[int]struct{}{}
        for j := minJ; j < maxJ; j++ {
            i := s + j - n
            set[grid[i][j]] = struct{}{}
            ans[i+1][j+1] = len(set) // 左上个数
        }
        
        // bottomRight
        set = map[int]struct{}{}
        for j := maxJ; j > minJ; j-- {
            i := s + j - n
            set[grid[i][j]] = struct{}{}
            ans[i-1][j-1] = abs(ans[i-1][j-1], len(set)) // ans[i-1][j-1]为左上个数, len(set)为右下个数,这里直接求解了
        }
    }
    return ans
}

2712. 使所有字符相等的最小成本

解题思路

没有一对相邻的0-1队都需要翻转一次，因为翻转一次只能修复一个，对后续的没有影响，比如，010101，翻转第一次后为110101，还需要翻转4次，所以遇到相邻不相同就翻转即可，每次翻转时选择短的那半段

示例代码

func minimumCost(s string) int64 {
    n := len(s)
    var sum int64
    for i := 1; i < n; i++ {
        if s[i] != s[i-1] {
            sum += min(i, n-i)
        }
    }
    return sum
}

2713. 矩阵中严格递增的单元格数

解题思路

定义dp数组，dp[i][j]的值表示能够到达这个格子需要访问的格子(与题目表叔相反，但因为求得是最大数量，所以答案是一致的，以示例1举例，dp[0][0]和dp[1][1]表示从dp[0][1]出发可以的个数，值与dp[0][1]出发的访问个数一致，这里注意，出发只能选择一条路)，max(dp[i][j])就是答案。

又因为需要严格大于，所以我们可以将格子排序，然后去计算。当我们计算i行时，因为第i行较小的已经计算完毕，只需要再计算较大的就可以了，所以对于第i来说，就是求第i的最大值，定义rowMax来维护每一行的最大值，列同理。

所以有dp[i][j] = max(rowMax[i], colMax[j])+1

注意，对于相同元素，要先把相同元素求完之后再更新到行最大或者列最大中，因为行列式分别计算的，直接更新会导致行列数据错乱

示例代码

func maxIncreasingCells(mat [][]int) int {
    type pair struct {
        x, y int
    }
    g := make(map[int][]pair)
    for i, row := range mat {
        for j, x := range row {
            g[x] = append(g[x], pair{i, j})
        }
    }
    
    keys := make([]int, 0)
    for k := range g {
        keys = append(keys, k)
    }
    sort.Ints(keys)
    
    rowMax := make([]int, len(mat))
    colMax := make([]int, len(mat[0]))
    var ans int
    for _, x := range keys {
        pos := g[x]
        mx := make([]int, len(pos))
        for i, p := range pos {
            mx[i] = max(rowMax[p.x], colMax[p.y]) + 1 // 先把最大值算出来，再更新 rowMax 和 colMax
            ans = max(ans, mx[i])
        }
        for i, p := range pos {
            rowMax[p.x] = max(rowMax[p.x], mx[i]) // 更新第 p.x 行的最大值
            colMax[p.y] = max(colMax[p.y], mx[i]) // 更新第 p.y 列的最大值
        }
    }
    return ans
}