每日一题(7)

2024-06-24

题目: 503. 下一个更大元素 II

题解和思路

从右往左遍历，利用栈放入可能是更大元素的「候选项」，由于栈的特性，栈顶元素永远会是距离左侧元素最近的下一个更大元素。

当左边元素大于栈顶时，此栈顶无效，需要移除。

对于当前元素，栈顶为下一个更大的元素，为空时记录 $-1$。

因为是循环数组，将数组 copy 一份到数组尾部即可，实现时可以复制，将下标扩大两倍，然后下标取模 $n$ 即可拿到对应元素。

func nextGreaterElements(nums []int) []int {  
    ans := make([]int, len(nums))  
    var stack []int  
    n := len(nums)  
      
    for i := 2*n - 1; i > 0; i-- {  
        x := nums[i%n]  
          
        for len(stack) > 0 && stack[len(stack)-1] <= x {  
            // 左侧树更大,栈顶无效,移除  
            stack = stack[:len(stack)-1]  
        }  
        if len(stack) == 0 { // 右侧没有更大的  
            ans[i%n] = -1  
        } else {  
            ans[i%n] = stack[len(stack)-1]  
        }  
        stack = append(stack, x)  
    }  
    return ans  
}

2024-06-25

题目: 2732. 找到矩阵中的好子集

题解和思路

题解和代码：严格证明+三种计算方法

2024-06-26

题目: 2741. 特别的排列

题解和思路

使用记忆化搜索，枚举 $nums$，依次选择整数进行搜索。

定义 $dfs(s,i)$ 表示已经选择的集合 $s$ 和上一个选下标为 $i$ 的数时，可以构造出多少个特别的排列。

枚举当前要全的数的下标 $j$，接下来要解决的问题是，再已经选的集合为 $S\cup \{j\}$，上一个选的数的下标是 $j$ 时，可以构造出多个特别排列。方案累加可得：

$$dfs(S,i)=\sum_{j \notin S} dfs(s \cup j, j)$$

其中 $j$ 满足 $nums[j] \mod nums[i] = 0$ 或 $nums[i] \mod nums[j] = 0$

递归边界 ：$dfs(U,i) = 1$，表示找到一个特别排列，全集 $U = \{0,1,2,...,n-1\}$

递归入口：$dfs(s \cup \{i\}, i)$

枚举特别排列的第一个数的下标 i，累加所有 $dfs(s \cup \{i\}, i)$，即为答案。

定义 $memo$ 数据记录是否已经搜索过，对于集合 $S$ ，里面的顺序不重要

func specialPerm(nums []int) int {  
    n := len(nums)  
    memo := make([][]int, 1<<n-1)  
    for i := range memo {  
        memo[i] = make([]int, n)  
        for j := range memo[i] {  
            memo[i][j] = -1 // -1 表示没有计算过  
        }  
    }  
      
    var dfs func(int, int) int  
    dfs = func(s int, i int) int {  
        if s == 1<<n {  
            return 1 // 找到一个特别排列  
        }  
          
        if memo[s][i] != -1 {  
            return memo[s][i]  
        }  
          
        res := 0  
        for j, x := range nums {  
            if s>>j&1 == 0 && (nums[i]%x == 0 || x%nums[i] == 0) {  
                res += dfs(s|1<<j, j)  
            }  
        }  
          
        memo[s][i] = res  
        return res  
    }  
      
    ans := 0  
    for i := range nums {  
        ans += dfs(1<<i, i)  
    }  
    return ans % 1e9  
}

2024-06-27

题目: 2734. 执行子串操作后的字典序最小字符串

题解和思路

找到第一个大于 a 的字符，继续向右遍历，直到字符串末尾或者遇到了 a，这个区间内的所有字符减一就找到了答案。因为字符 a 减一会变成 z，这样就不是减小而是增大。

特殊的，如果字符串全是 a，题目要求必须操作一次，把最后一个 a 变成 z 即可。

func smallestString(s string) string {  
    b := []byte(s)  
    for i, c := range s {  
        if c != 'a' {  
            for ; i < len(b) && b[i] != 'a'; i++ {  
                b[i]--  
            }  
            return string(b)  
        }  
    }  
    b[len(b)-1] = 'z'  
    return string(b)  
}

2024-06-28

题目: 2742. 给墙壁刷油漆

题解和思路

用「选或不选」来思考，是否付费刷墙。

考虑第 $n-1$ 堵墙是否付费刷：

• 付费刷，问题变成：刷前 $n-2$ 堵墙，在「付费时间之和为 $time[n-1]$ ，免费时间之和为 $0$ 」状态下最小开销
• 不付费，问题变成：刷前 $n-2$ 堵墙，在「付费时间之和为 $0$，免费时间之后为 $1$ 」状态下的最小开销

定义 $dfs(i,j,k)$ 表示刷前 $i$ 堵墙，在「付费时间和为 $j$，免费时间和为 $k$ 」状态下的最少开销。

递归达到终点时，如果 $j\geq k$ 说明这个方案是合法的，否则不合法。

因为最终比较的是 $j$ 和 $k$ 的「相对大小」，不妨定义 $j$ 为「付费时间之后」减去「免费时间之和」，这样递归到终点时，如果 $j \geq 0$，说明这种方案是合法的，否则不合法。

分类讨论：

• 选择付费刷第 $i$ 堵墙：$dfs(i,j) = dfs(i-1, j+time[i])+cost[i]$
• 选择免费刷第 $i$ 堵墙：$dfs(i,j) = dfs(i-1, j-1)$

两种情况取最小：$dfs(i,j)=min(dfs(i-1, j+time[i])+cost[i], dfs(i-1,j-1))$

递归边界：如果 $j>i$，那么剩余的墙都可以免费刷，即 $dfs(i,j)=0$，否则 $dfs(−1,j)=∞$。

递归入口：$dfs(n−1,0)$，即答案

func paintWalls(cost []int, time []int) int {  
    n := len(cost)  
    memo := make([][]int, n)  
    for i := range memo {  
        memo[i] = make([]int, n*2)  
        for j := range memo[i] {  
            memo[i][j] = -1 // 没有计算过  
        }  
    }  
      
    var dfs func(int, int) int  
    dfs = func(i int, j int) int {  
        if j > i { // 剩余的墙可以免费刷  
            return 0  
        }  
        if i < 0 { // 表示j<i<0,不符合题目要求  
            return math.MaxInt / 2  
        }  
          
        if memo[i][j+n] == -1 { // 加上n 防止出现负数  
            memo[i][j+n] = min(dfs(i-1, j+time[i])+cost[i], dfs(i-1, j-1))  
        }  
          
        return memo[i][j+n]  
    }  
      
    return dfs(n-1, 0)  
}

2024-06-29

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

题解和思路

倒序去掉末尾 0 即可

func removeTrailingZeros(num string) string {  
    b := []byte(num)  
    for i := len(b) - 1; i >= 0; i-- {  
        if b[i] != '0' {  
            return string(b[:i+1])  
        }  
    }  
    return num  
}

2024-06-30

题目: 494. 目标和

题解和思路

使用背包解法，$nums$ 的和为 $sum$，其中正数和为 $p$ ，负数和为（带负号的元素） $q$，那么 $p+q=sum$

又因题意，$p-q=target$，所以有：

$$\left\{ \begin{array}{ll} p = \frac{sum+target}{2} \\ q = \frac{sum-target}{2} \\ \end{array} \right.$$

• 如果 $target \geq 0$，那么取 $q = \frac{sum-target}{2}$ 作为背包更好
• 如果 $target \lt 0$，那么取 $p=\frac{sum+target}{2}$ 作为背包更好

终上所述，取 $\frac{sum- |target|}{2}$

最终根据背包问题解法，此处取方案数，所以状态转移公式为：$dfs(i, c) = dfs(i - 1, c) + dfs(i - 1, c - nums[i])$

注意：当 $sum-|target|< 0$ 时没有结果，即 $sum < target$；$\frac{sum- |target|}{2}$ 为奇数时也没有解，因为 $p$ 和 $q$ 都为整数

func findTargetSumWays(nums []int, target int) int {  
    sum := 0  
    for _, num := range nums {  
        sum += num  
    }  
    sum -= abs(0, target)  
    // p−q=target p+q=s, 2q=s-target  
    if sum < 0 || sum%2 == 1 {  
        return 0  
    }  
      
    m := sum / 2 // 背包数量  
    n := len(nums)  
    memo := make([][]int, n)  
    for i := range memo {  
        memo[i] = make([]int, m+1)  
        for j := range memo[i] {  
            memo[i][j] = -1  
        }  
    }  
      
    var dfs func(int, int) int  
    dfs = func(i int, c int) int {  
        if i < 0 {  
            if c == 0 {  
                return 1  
            }  
            return 0  
        }  
          
        if memo[i][c] == -1 {  
            if c < nums[i] {  
                memo[i][c] = dfs(i-1, c)  
            } else {  
                memo[i][c] = dfs(i-1, c) + dfs(i-1, c-nums[i])  
            }  
        }  
        return memo[i][c]  
    }  
    return dfs(n-1, m)  
}

翻译为递推，根据回溯，当 $i$ 和 $c$ 都为 $0$ 时，结果为 $1$，翻译成递推后，$dp[0][0]=1$

func findTargetSumWays2(nums []int, target int) int {  
    sum := 0  
    for _, num := range nums {  
        sum += num  
    }  
    sum -= abs(0, target)  
    // p−q=target p+q=s, 2q=s-target  
    if sum < 0 || sum%2 == 1 {  
        return 0  
    }  
      
    m := sum / 2 // 背包数量  
    n := len(nums)  
      
    dp := make([][]int, n+1)  
    for i := range dp {  
        dp[i] = make([]int, m+1)  
    }  
    dp[0][0] = 1  
    for i, num := range nums {  
        for c := 0; c <= m; c++ {  
            if c < num {  
                dp[i+1][c] = dp[i][c]  
            } else {  
                dp[i+1][c] = dp[i][c] + dp[i][c-num]
            }  
        }  
    }  
    return dp[n][m] 
}

因为 $dp$ 数组中的变化永远只与上一个数组有关，所以改为两个数组也可以完成

func findTargetSumWays(nums []int, target int) int {
    sum := 0
    for _, num := range nums {
        sum += num
    }
    sum -= abs(0, target)
    // p−q=target p+q=s, 2q=s-target
    if sum < 0 || sum%2 == 1 {
        return 0
    }
    
    m := sum / 2 // 背包数量
    n := len(nums)
    
    dp := make([][]int, 2)
    for i := range dp {
        dp[i] = make([]int, m+1)
    }
    dp[0][0] = 1
    
    for i, num := range nums {
        for c := 0; c <= m; c++ {
            if c < num {
                dp[(i+1)%2][c] = dp[i%2][c]
            } else {
                dp[(i+1)%2][c] = dp[i%2][c] + dp[i%2][c-num]
            }
        }
    }
    return dp[n%2][m]
}

从后往前遍历，翻译为一个数组

func findTargetSumWays(nums []int, target int) int {  
    sum := 0  
    for _, num := range nums {  
        sum += num  
    }  
    sum -= abs(0, target)  
    if sum < 0 || sum%2 == 1 {  
        return 0  
    }  
      
    m := sum / 2 // 背包数量  
    dp := make([]int, m+1)  
    dp[0] = 1  
    for _, num := range nums {  
        for c := m; c >= num; c-- {  
            dp[c] += dp[c-num]  
        }  
    }  
    return dp[m]  
}