每日一题(一)

发表于 2024-03-12 更新于 2024-10-18 分类于算法刷题阅读次数：本文字数： 3.6k 阅读时长 ≈ 13 分钟

Day1 --- 303. 区域和检索 - 数组不可变
Day2 --- 1793. 好子数组的最大分数
Day3 --- 1969. 数组元素的最小非零乘积
Day4 --- 2671. 频率跟踪器
Day5 --- 2617. 网格图中最少访问的格子数
Day6 --- 2549. 统计桌面上的不同数字
Day7 --- 322. 零钱兑换

Day1 --- 303. 区域和检索-数组不可变

题目

给定一个整数数组nums，处理以下类型的多个查询:
1. 计算索引left和right（包含left和right）之间的nums元素的和，其中left <= right

实现NumArray类：
1. NumArray(int[] nums)使用数组nums初始化对象
2. intsumRange(inti, intj)返回数组nums中索引left和right之间的元素的总和，包含left和right两点（也就是nums[left] + nums[left + 1] + ... + nums[right])

题解

不考虑空间复杂度，可以使用一个数组res保存nums的前缀和，res[i]表示nums[0]到nums[i]的和。
由于res的长度为n+1，res[0]为0，所以sumRange函数返回res[right +1 ] - res[left]即可。

class NumArray {
public:
    vector<int> res;
    NumArray(vector<int>& nums) {
        res.resize(nums.size() + 1, 0);
        for(int i = 0; i < nums.size(); ++i){
            res[i + 1] = res[i] + nums[i];
        }

    }
    
    int sumRange(int left, int right) {
        return res[right + 1] - res[left];
    }
};

Day2 --- 1793. 好子数组的最大分数

题目

给定一个整数数组nums（下标从 0 开始）和一个整数k。一个子数组(i, j)的分数定义为min(nums[i], nums[i+1], ..., nums[j]) * (j - i + 1)。一个好子数组的两个端点下标需要满足 i <= k <= j。

请返回好子数组的最大可能分数 。

题解

双指针

由于要满足k必须在好子数组内，即i <= k <= j，所以可以考虑由k点开始，使用双指针向两边扩张，直到子数组两个边界都大于nums[k]，找到了以nums[k]为最小值的最长子数组；
逐步递减nums[k]，使可能的结果中包含小于nums[k]的每种情况，取可能结果的较大值，循环结束便可得到答案。

class Solution {
public:
    int maximumScore(vector<int>& nums, int k) {
        int l = k, r = k, n = nums.size(), res = nums[k]; 
        for(int i = nums[k]; i > 0; i--){ 
            while(r < n && nums[r] >= i) r++; 
            while(l >= 0 && nums[l] >= i) l--; 
            res = max(res, (r - l - 1) * i); 
            if(l < 0 && r == n) break; 
        }
        return res;
    }
};

以nums = [1,4,3,7,4,5],k = 3为例：
- 初始时，l = r = k = 3，res = 7。
- i从7开始递减，当i=7时，l和r都不动，res更新为(4 - 3 + 1) * 7 = 7。
- 当i=6时，l和r都不动，res保持不变。
- 当i=5时，l和r都不动，res保持不变。
- 当i=4时，l不动，r向右移动到5，res更新为(5 - 3 + 1) * 4 = 12。
- 当i=3时，l向左移动到1，r向右移动到5，res更新为(5 - 1 + 1) * 3 = 15。
- 当i=2， l向左移动到1，r向右移动到5，res为(5 - 1 + 1) * 2 = 10。小于15, 保持不变。
- 当i=1， l向左移动到0，r向右移动到5，res为(5 - 0 + 1) * 1 = 6。小于15, 保持不变。
- 最后，返回res=15。

双指针 + 贪心

和上面一致；
上解逐步递减nums[k],遍历了所有的好子数组，多做了一些运算，这里贪心地更新nums[k]减少计算：
- 当i,j都指向大于nums[k]的时候，我们得到了一个好子数组，计算结果，接着替换nums[k]为左右边界的较大值（这是因为，如果用较小值替换，就无法向较大值的那边扩张，从而遗漏解的可能；换句话说，较小值的解的可能是较大值解的可能的子集）。
- 当子数组扩张到一边的顶点时，nums[k]直接更新为另一边的值，直到i < 0 && j == nums.size()完成遍历，跳出循环；

class Solution {
public:
    int maximumScore(vector<int>& nums, int k) {
        int i = k, j = k, res = nums[k], n = nums.size();
        while(1){
            while(i >= 0 && nums[i] >= nums[k]) i--;
            while(j < n && nums[j] >= nums[k]) j++;
            res = max(res, nums[k] * (j - i - 1));
            if(i < 0 && j == n) break;
            if(i > 0 && j < n) nums[k] = max(nums[i], nums[j]);
            else if(i < 0) nums[k] = nums[j];
            else nums[k] = nums[i];

        }
        return res;
    }
};

Day3 --- 1969. 数组元素的最小非零乘积

题目

给你一个正整数p。你有一个下标从1开始的数组nums，这个数组包含范围[1,2p-1]内所有整数的二进制形式（两端都包含）。你可以进行以下操作任意次：

从nums中选择两个元素x和y。
选择x中的一位与y对应位置的位交换。对应位置指的是两个整数相同位置的二进制位。
比方说，如果x = 1101且y = 0011，交换右边数起第2位后，我们得到x = 1111和y = 0001。

请你算出进行以上操作任意次以后，nums能得到的最小非零乘积。将乘积对1e9 + 7取余后返回。注意：答案应为取余之前的最小值。

题解

数组中一共有 $ 2^p - 1 $ 个数，其每位上是1的个数总和为 $ 2^{(p - 1)}$ ，每位上是0的个数总和为 $ 2^{(p - 1)} - 1 $ ，这是因为数组中不包含0:

例如，p=3时，二进制数组为[001, 010, 011, 100, 101, 110, 111]
- 右起第一位上1的个数为4：001, 011, 101, 111，第一位上0的个数为3：010, 100, 110
- 右起第二位上1的个数为4：010, 011, 110, 111，第二位上0的个数为3：001, 100, 101
- 右起第三位上1的个数为4：100, 101, 110, 111，第三位上0的个数为3：001, 010, 011
如果想求得最小非零乘积，可以凑尽可能多的1, 这些数除了右起第一位为1其余位均为0，一共得到 $ 2^{(p - 1)} - 1 $ 个1。
剩下右起第一位的 $ 2^{(p - 1)} - 1 $ 个0,与其余位的1祖成了 $ 2^{(p - 1)} - 1 $ 个 $2^p - 2$ ，所以最小非零乘积为 ${(2^p - 1) * (2^p - 2)^{(2^{(p - 1)} - 1)}}$
下面的问题就是如何计算 ${(2^p - 1) * (2^p - 2)^{(2^{(p - 1)} - 1)}}$

可以发现 $ {(2^{(p - 1)} - 1)}$ 是等比数列，1, 2, 4, 8, ... 2^n的前p - 2项和。

${(2^p - 1) * (2^p - 2)^{(2^{(p - 1)} - 1)}}$
= ${(2^p - 1) * (2^p - 2) ^{1 + 2 + 4 + 8 + ... + 2^{p - 2}}}$
= ${(2^p - 1) * (2^p - 2) * (2^p - 2) ^ {2} * (2^p - 2) ^ {4} * ... * (2^p - 2) ^ {2^{(p - 2)}} }$

class Solution {
public:
    int minNonZeroProduct(int p)
    {
        int mod = 1e9 + 7;
        long long res = ((1LL << p) - 1) % mod;   // 2^p - 1 % mod
        long long x = (res - 1) % mod;            // 2^p - 2 % mod
        for(int i = 0; i < p - 1; ++i){           //循环求(2^p - 2)^(2^(p - 1) - 1)
            res = (res * x) % mod;
            x = (x * x) % mod;
        }
        return res;
    }
};

快速幂求解

题目50. Pow(x, n) 的扩展

记 $ 2^p - 1 $ 为a， $ 2^{(p - 1)} - 1 $ 为pow，使用快速幂求解。

递归快速幂

class Solution {
public:
    int minNonZeroProduct(int p)
    {
        long long mod = 1e9 + 7;
        long long a = (1LL << p) - 1;
        long long pow = (1LL << (p - 1)) - 1;
        return a % mod * quickPow((a - 1)% mod, pow , mod) % mod;

    }
private:
    long long quickPow(long long x, long long n, long long mod)
    {
        if(! n) return 1;
        else if(n % 2) return (quickPow(x, n - 1, mod) * x) % mod;
        else{
            long long res = quickPow(x, n / 2, mod) % mod;
            return (res * res) % mod;
        }
    }
};

非递归快速幂

class Solution {
public:
    int minNonZeroProduct(int p)
    {
        long long mod = 1e9 + 7;
        long long a = (1LL << p) - 1; // 2^p - 1
        long long pow = (1LL << (p - 1)) - 1; // 2^(p - 1) - 1
        return a % mod * quickPow((a - 1)% mod, pow , mod) % mod;

    }
private:
    long long quickPow(long long x, long long n, long long mod) {
        long long res = 1;
        while (n) {
            if (n & 1) {
            res = (res * x) % mod; 
            }
            x = (x * x) % mod; 
            n >>= 1;
        }
        return res;
    }
};

Day4 --- 2671. 频率跟踪器

题目

请你设计并实现一个能够对其中的值进行跟踪的数据结构，并支持对频率相关查询进行应答。

实现 FrequencyTracker 类：

FrequencyTracker()：使用一个空数组初始化 FrequencyTracker 对象。
void add(int number)：添加一个 number 到数据结构中。
void deleteOne(int number)：从数据结构中删除一个 number 。数据结构可能不包含 number ，在这种情况下不删除任何内容。
bool hasFrequency(int frequency): 如果数据结构中存在出现 frequency 次的数字，则返回 true，否则返回 false。

题解

使用两个unordered_map，一个map保存number的频率，另一个frequency_map保存频率的个数。
add函数：map中number的频率加一，frequency_map中更新后的map[number]的频率加一。
deleteOne函数：map中number的频率减一，frequency_map中更新后的map[number]的频率减一。
hasFrequency函数：返回frequency_map中frequency的频率是否大于0。

class FrequencyTracker {
public:
    FrequencyTracker() {

    }
    
    void add(int number) {
        --frequency_map[map[number]];
        ++frequency_map[++map[number]];
    }
    
    void deleteOne(int number) {
        if(map.find(number) == map.end() || ! map[number]) return;
        --frequency_map[map[number]];
        ++frequency_map[--map[number]];
    }
    
    bool hasFrequency(int frequency) {
        return frequency_map[frequency];
    }

private:
    unordered_map<int, int> map;
    unordered_map<int, int> frequency_map;
};

Day5 --- 2617. 网格图中最少访问的格子数

题目

给你一个下标从 0 开始的 m x n 整数矩阵 grid 。你一开始的位置在左上角格子(0, 0) 。

当你在格子 (i, j) 的时候，你可以移动到以下格子之一：

满足 j < k <= grid[i][j] + j 的格子 (i, k) （向右移动），或者满足 i < k <= grid[i][j] + i 的格子 (k, j) （向下移动）。请你返回到达 右下角 格子 (m - 1, n - 1) 需要经过的最少移动格子数，如果无法到达右下角格子，请你返回 -1 。

注意：grid 的下标从 0 开始。

题解

本题CV,题解参考此处

//单调栈优化DP
class Solution {
public:
    int minimumVisitedCells(vector<vector<int>> &grid) {
        int m = grid.size(), n = grid[0].size(), mn;
        vector<vector<pair<int, int>>> col_stacks(n); // 每列的单调栈
        vector<pair<int, int>> row_st; // 行单调栈
        for (int i = m - 1; i >= 0; i--) {
            row_st.clear();
            for (int j = n - 1; j >= 0; j--) {
                int g = grid[i][j];
                auto &col_st = col_stacks[j];
                mn = i < m - 1 || j < n - 1 ? INT_MAX : 1;
                if (g) { // 可以向右/向下跳
                    // 在单调栈上二分查找最优转移来源
                    auto it = lower_bound(row_st.begin(), row_st.end(), j + g, [](const auto &a, const int b) {
                        return a.second > b;
                    });
                    if (it < row_st.end()) mn = it->first + 1;
                    it = lower_bound(col_st.begin(), col_st.end(), i + g, [](const auto &a, const int b) {
                        return a.second > b;
                    });
                    if (it < col_st.end()) mn = min(mn, it->first + 1);
                }
                if (mn < INT_MAX) {
                    // 插入单调栈
                    while (!row_st.empty() && mn <= row_st.back().first) {
                        row_st.pop_back();
                    }
                    row_st.emplace_back(mn, j);
                    while (!col_st.empty() && mn <= col_st.back().first) {
                        col_st.pop_back();
                    }
                    col_st.emplace_back(mn, i);
                }
            }
        }
        return mn < INT_MAX ? mn : -1; // 最后一个算出的 mn 就是 f[0][0]
    }
};

Day6 --- 2549. 统计桌面上的不同数字

题目

给你一个正整数 n ，开始时，它放在桌面上。在 10^9 天内，每天都要执行下述步骤：

对于出现在桌面上的每个数字 x ，找出符合 1 <= i <= n 且满足 x % i == 1 的所有数字 i 。
然后，将这些数字放在桌面上。返回在 10^9 天之后，出现在桌面上的不同整数的数目。

注意：

一旦数字放在桌面上，则会一直保留直到结束。 % 表示取余运算。例如，14 % 3 等于 2 。

题解

输入n,那么第二天n - 1一定在桌面上，同理n - 2也在桌面上。
以此类推，直到2;

class Solution {
public:
    int distinctIntegers(int n) {
        return max(1,n - 1);//如果n=1,那么返回1
    }
};

Day7 --- 322. 零钱兑换

题目

给你一个整数数组 coins ，表示不同面额的硬币；以及一个整数 amount ，表示总金额。

计算并返回可以凑成总金额所需的 最少的硬币个数 。如果没有任何一种硬币组合能组成总金额，返回 -1 。

你可以认为每种硬币的数量是无限的。

题解

每种硬币的数量是无限的，是典型的完全背包问题。

下面进行动态规划的分析：

确定dp数组以及下标的含义
- dp[j]：凑成总金额为j所需的最少硬币个数。
确定递推公式
- 对于每个硬币coin，dp[i] = min(dp[i], dp[i - coin] + 1)。
- 凑足总额为j - coins[i]的最少个数为dp[j - coins[i]]，那么只需要加上一个钱币coins[i]即dp[j - coins[i]] + 1就是dp[j]（考虑coins[i]）
- dp[j]要取所有dp[j - coins[i]] + 1中最小的。
- 递推公式：dp[j] = min(dp[j - coins[i]] + 1, dp[j]);
dp数组初始化
- dp[0] = 0，凑成总金额为0所需的最少硬币个数为0。
- 其余的dp初始化为amount + 1，因为硬币的面值最小为1，所以最多需要amount个硬币。
- 如果小于这个数，根据递推公式min(dp[j - coins[i]] + 1, dp[j])，可能会出现错误。
确定遍历顺序

本题求钱币最小个数，那么钱币有顺序和没有顺序都可以，都不影响钱币的最小个数，所以本题并不强调集合是组合还是排列，所以遍历顺序无所谓。
- 如果求组合，外层for循环遍历物品，内层for循环遍历背包；
- 如果求排列，外层for循环遍历背包，内层for循环遍历物品。
- 本题钱币数量可以无限使用，是完全背包，所以遍历的内循环是正序。

举例推导dp数组

以输入coins = [1, 2, 5], amount = 11为例：

dp[n]	min{......}	min{...}	res
`dp[0]`	——	——	0
`dp[1]`	`min(dp[1 - 1] + 1, dp[1])`	`min(dp[0] + 1, dp[1])`	1
`dp[2]`	`min(dp[2 - 2] + 1, dp[2])`	`min(dp[0] + 1, dp[2])`	1
`dp[3]`	`min(dp[3 - 1] + 1, dp[3])`	`min(dp[2] + 1, dp[3])`	2
`dp[4]`	`min(dp[4 - 2] + 1, dp[4])`	`min(dp[2] + 1, dp[4])`	2
`dp[5]`	`min(dp[5 - 5] + 1, dp[5])`	`min(dp[0] + 1, dp[5])`	1
`dp[6]`	`min(dp[6 - 5] + 1, dp[6])`	`min(dp[1] + 1, dp[6])`	2
`dp[7]`	`min(dp[7 - 5] + 1, dp[7])`	`min(dp[2] + 1, dp[7])`	2
`dp[8]`	`min(dp[8 - 5] + 1, dp[8])`	`min(dp[3] + 1, dp[8])`	2
`dp[9]`	`min(dp[9 - 5] + 1, dp[9])`	`min(dp[4] + 1, dp[9])`	3
`dp[10]`	`min(dp[10 - 5] + 1, dp[10])`	`min(dp[5] + 1, dp[10])`	2
`dp[11]`	`min(dp[11 - 5] + 1, dp[11])`	`min(dp[6] + 1, dp[11])`	3

代码如下：

class Solution {
public:
    int coinChange(vector<int>& coins, int amount) {
        vector<int> dp(amount + 1, amount + 1);
        dp[0] = 0;
        for(int i = 1; i <= amount; ++i){//遍历背包
            for(int coin : coins){//遍历物品
                if(i - coin >= 0 && dp[i - coin] !=amount + 1){//可以放入背包
                    dp[i] = min(dp[i], dp[i - coin] + 1);//选择最小的
                }
            }
        }
        return dp[amount] == amount + 1 ? -1 : dp[amount];//如果dp[amount] == amount + 1，说明没有找到合适的硬币组合
    }
};

上面代码先遍历背包，再遍历物品；如果先遍历物品，再遍历背包，也是可以的。

class Solution {
public:
    int coinChange(vector<int>& coins, int amount) {
        vector<int> dp(amount + 1, amount + 1);
        dp[0] = 0;
        for(int coin : coins){//遍历物品
            for(int i = coin; i <= amount; ++i){//遍历背包
                dp[i] = min(dp[i], dp[i - coin] + 1);
            }
        }
        return dp[amount] == amount + 1 ? -1 : dp[amount];
    }
};

时间复杂度：$O(n \times m)$，其中n为硬币的个数，m为总金额。
空间复杂度：$O(m)$，m为总金额。