每日一题(5)

2024-06-10

题目: 881. 救生艇

题解和思路

把所有人的体重排序，使用双指针，同时去取最轻的和最重的人，如果船不能同时装下两个，就先装走最重的人。

func numRescueBoats(people []int, limit int) int {  
    sort.Ints(people)  
    n := len(people)  
    left, right := 0, n-1  
    ans := 0  
    for left <= right {  
        if people[left]+people[right] <= limit {  
            left++  
        }  
        right--  
        ans++  
    }  
    return ans  
}

2024-06-11

题目: 419. 甲板上的战舰

题解和思路

统计战舰的的头即可，满足条件的战舰左上肯定为空，边缘特殊处理一下即可

func countBattleships(board [][]byte) int {  
    ans := 0  
    for i, b := range board {  
        for j, b2 := range b {  
            if b2 == 'X' && (i == 0 || board[i-1][j] == '.') && (j == 0 || board[i][j-1] == '.') {  
                ans++  
            }  
        }  
    }  
    return ans  
}

2024-06-12

题目: 2806. 取整购买后的账户余额

题解和思路

向上取整 $(x+5)/10*10$ 即可

func accountBalanceAfterPurchase(purchaseAmount int) int {  
    return 100 - (purchaseAmount+5)/10*10  
}

2024-06-13

题目: 2813. 子序列最大优雅度

题解和思路

利润从大到小排序, 先选择前 $k$ 个项目,计算最大利润
遍历 $[k+1,n)$ 中的项目, 只有当第 $k+i$ 个项目未选择过，且前面选择的项目没有重复时才能从原来选择的项目中替换以增加利润，因为:

• 如果 k+i 个项目与前面的类别相同,那么他的利润更小,不需要选他
• 如果前面项目为出现重复, 那么类别一增一减 distinct_categories 不会有变化,而后面的利润比前面小, 反而会降低

我们需要保证 $total\_profit$ 尽量大的同时去增加 $categories$ 的数量，以达到目的.

func findMaximumElegance(items [][]int, k int) int64 {  
    sort.Slice(items, func(i, j int) bool {  
        return items[i][0] > items[j][0]  
    })  
      
    ans, totalProfit := 0, 0  
    vis := make(map[int]bool)  
    var repeat []int  
    for _, item := range items[:k] {  
        profit, category := item[0], item[1]  
        totalProfit += profit  
        if !vis[category] {  
            vis[category] = true  
        } else {  
            repeat = append(repeat, profit)  
        }  
    }  
      
    for _, item := range items[k:] {  
        profit, category := item[0], item[1]  
        if len(repeat) > 0 && !vis[category] {  
            vis[category] = true  
            totalProfit = totalProfit - repeat[len(repeat)-1] + profit  
            repeat = repeat[:len(repeat)-1]  
        }  
    }  
    return int64(ans)  
}

2024-06-14

题目: 2786. 访问数组中的位置使分数最大

题解和思路

数组求最值，一眼动态规划。先寻找子问题：

如示例一 $nums=[2,3,6,1,9,2]$，子序列第一个数为 $nums[0]=2$，是一个偶数。接下来的考虑的问题有两种：

• 在区间 $[1,n-1]$ 中选择一个子序列，其第一个数与 $nuns[0]$ 相同为偶数
• 在区间 $[1,n-1]$ 中选择一个子序列，其第一个数与 $nuns[0]$ 相同为奇数

考虑 $nums[1]=3$ 选不选：

• 考虑第一种，即选与 $nums[0]$ 同为偶数，由于不符合要求，不选，问题变成：在区间 $[2,n-1]$ 中选择一个子序列，第一个数必须为偶数。
• 考虑第二种，选奇数，符合要求，一定要选。因为 $nums$ 数组中的元素都为正数，假设不选更优，那么最终子序列的任意奇数前插入 $nums[1]=3$，不会减去 $x$，且增加了得分，互相矛盾，所以必须选。选之后要解决的问题也有两种：
  • 在区间 $[2,n-1]$ 中选择一个子序列，其第一个数与 $nuns[0]$ 相同为奇数
  • 在区间 $[2,n-1]$ 中选择一个子序列，其第一个数与 $nuns[0]$ 相同为偶数

最终问题变成了「在区间 $[i,n-1]$ 中选择一个子序列，其第一个数的奇偶性为 $j$ 使的最大得分」，状态定义为 $dfs(i,j)$。

考虑 $v=nums[i]$ 选或不选：

• 如果 $v \% 2 \neq j$，由于不符合要求，不选，问题变成：在下标 $[i+1,n-1]$ 中选一个子序列，其第一个数的奇偶性为 $j$ 时的最大得分，即 $dfs(i,j) = dfs(i+1,j)$
• 如果 $v\%2 = j$，根据上文讨论，一定要选，根据情况分为两种：
  • 在下标 $[i+1,n-1]$ 中选择一个子序列，其第一个数的奇偶性为 $j$ 时的最大得分，即 $dfs(i,j) = dfs(i+1,j)+v$
  • 在下标 $[i+1, n-1]$ 中选择一个子序列，其第一个数的奇偶性不等于 $j$ 的最大得分，即 $dfs(i,j) = dfs(i+1,j\oplus 1)-x+v$。其中 $j\oplus 1$ 表示 $j$ 奇偶性取反，减去 $x$ 是因为奇偶性不同。
  • 这两种情况取最大值，就得到了 $dfs(i,j)$。即 $dfs(i,j) = max(dfs(i+1,j), dfs(i+1,j\oplus 1)-x)+v$

递归边界：当 $i==n$ 时结束，没有元素了，得分为 0

递归入口：$dfs(0,nums[0]\% 2)$，也就是答案

func maxScore(nums []int, x int) int64 {  
    n := len(nums)  
    memo := make([][2]int, n)  
    for i := range memo {  
        memo[i] = [2]int{-1, -1}  
    }  
      
    var dfs func(int, int) int  
    dfs = func(i int, j int) (res int) {  
        if i == n {  
            return  
        }  
        if memo[i][j] != -1 {  
            return memo[i][j]  
        }  
          
        if nums[i]%2 != j {  
            res = dfs(i+1, j)  
        } else {  
            res = max(dfs(i+1, j), dfs(i+1, j^1)-x) + nums[i]  
        }  
        memo[i][j] = res  
        return res  
    }  
      
    return int64(dfs(0, nums[0]%2))  
}

记忆化搜索：

func maxScore2(nums []int, x int) int64 {  
    n := len(nums)  
    dp := make([][2]int, n+1)  
    for i := n - 1; i >= 0; i-- {  
        v := nums[i]  
        r := v % 2  
        dp[i][r^1] = dp[i+1][r^1]  // 奇偶性不同
        dp[i][r] = max(dp[i+1][r], dp[i+1][r^1]-x) + v  
    }  
    return int64(dp[0][nums[0]%2])  
}

2024-06-15

题目: 2779. 数组的最大美丽值

题解和思路

差分数组：

因为是选子序列，且子序列所有的元素都相等，所以元素顺序对答案没有影响，可以先对数组进行排序。

对于 $nums[i]$ 可替换为$nums[i]−k$到 $nums[i]+k$ 内的任一整数，所以实际上是在求 $n$ 个 数组段 的重合范围，可以用差分数组来实现

以 $nums=[4,6,1,2]，k=2$ 为例：

• $nums[0]$ 的取值范围为 $[2,6]$
• $nums[1]$的取值范围为 $[4,8]$
• $nums[2]$ 的取值范围为 $[−1,3]$
• $nums[3]$ 的取值范围为$[4,6]$

转换为差分数组，就变成了在 $[2,6],[4,8],[0,3],[4,6]$ 范围内的数分别 $+1$（因为 $nums[i] $），最后求出差分数组中最大的值即可。

细节上：创建一个长度为 $max(nums)+k+2$ 的差分数组存储值，遍历时更新每个数取值范围的差分数组值。

func maximumBeauty(nums []int, k int) int {  
    n := len(nums)  
    sort.Ints(nums)  
      
    d := make([]int, nums[n-1]+k+2)  
    for _, num := range nums {  
        d[max(0, num-k)] += 1  
        d[num+k+1] -= 1  
    }  
      
    sum := 0  
    ans := 0  
    for i := max(0, nums[0]-k); i < len(d); i++ {  
        sum += d[i]  
        ans = max(ans, sum)  
    }  
    return ans  
}

滑动窗口

差分数组在最极端的情况下会申请长度为 $10^5 \times 2$ 的数组，会造成空间浪费。

按照上述思路，将数组排序后，对于数组中的每个数 $x$，都可以变成区间 $[x-k, x+k]$ 中的数，最终题目要求的「相等元素组成的最长子序列」就变成了从多个区间内选出的最大交集。

因为排序后选出的区间是连续的，队友子数组最左边的 $x$ 和最右边的 $y$ 将满足：

$$x+k\geq y-k$$

即：$y-x\leq 2k$，原问题就变成了「排序后，找出最长连续子数组，数组头结点与尾节点之差不超过 $2k$ 」。

使用滑动窗口，枚举 $nums[right]$ 作为子数组的最后一个数，如果 $nums[right]-nums[left] > k$ 就移动左端点，最终 $right-left+1$ 就是子数组的长度。

func maximumBeauty(nums []int, k int) int {  
    n := len(nums)  
    sort.Ints(nums)  
      
    left, ans := 0, 1  
    for right := 1; right < n; right++ {  
        if nums[right]-nums[left] > k*2 {  
            left++  
        }  
        ans = max(ans, right-left+1)     
    }  
      
    return ans  
}

2024-06-16

题目: 521. 最长特殊序列 Ⅰ

题解和思路

如果 $a = b$，如示例 3 所言，字符串 a 的每个子序列也是字符串 b 的每个子序列。同样，字符串 b 的每个子序列也是字符串 a 的子序列。不存在独有的子序列，返回 $-1$。

如果 $a \neq b$ ，取二者长度最大值即可，因为当 $len(a)>len(b)$ 时，把字符串 $a$ 作为独立子序列，它必不是 $b$ 字符串的子序列，此时答案为 $len(a)$，反之同理

func findLUSlength(a string, b string) int {  
    if a == b {  
        return -1  
    }  
      
    return max(len(a), len(b))  
}