每日一题(一)

发表于 更新于 分类于 阅读次数： 本文字数： 2.9k 阅读时长 ≈ 10 分钟

Day1 --- 518. 零钱兑换 II
Day2 --- 2642. 设计可以求最短路径的图类
Day3 --- 2580. 统计将重叠区间合并成组的方案数
Day4 --- 1997. 访问完所有房间的第一天
Day5 --- 2908. 元素和最小的山形三元组 I
Day6 --- 2952. 需要添加的硬币的最小数量
Day7 --- 331. 验证二叉树的前序序列化

Day1 --- 518. 零钱兑换 II

题目

给你一个整数数组 coins 表示不同面额的硬币，另给一个整数 amount 表示总金额。
请你计算并返回可以凑成总金额的硬币组合数。如果任何硬币组合都无法凑出总金额，返回 0 。
假设每一种面额的硬币有无限个。
题目数据保证结果符合 32 位带符号整数。

题解

这道题是一个典型的完全背包问题，与前一日题目类似。

通过五步曲进行解答：

  1. 确定dp数组以及下标的含义

    dp[i]：表示凑成总金额为 i 的硬币组合数。

  2. 确定递推公式

    对于每个硬币 coin，可以选择拿或者不拿，如果选择拿，那么 dp[i] = dp[i] + dp[i - coin]，如果选择不拿，那么 dp[i] 不变。

  3. 初始化

    dp[0] = 1，表示凑成总金额为 0 的硬币组合数为 1。

  4. 确定遍历顺序

    由于题目要求的是组合数，而不是排列数，所以外层遍历硬币（物品），内层遍历金额（背包）。

  5. 举例推导dp数组

    以 coins = [1, 2, 5], amount = 5 为例，推导 dp 数组：

    dp[i]数组下标 0 1 2 3 4 5
    硬币1加入遍历 1 1 1 1 1 1
    硬币2加入遍历 1 1 2 2 3 3
    硬币5加入遍历 1 1 2 2 3 4 
1
2
3
4
5
6
7
8
9
10
11
12
13
class Solution {
public:
    int change(int amount, vector<int>& coins) {
        vector<int> dp(amount + 1, 0);  // dp[i] 表示凑成总金额为 i 的硬币组合数
        dp[0] = 1;
        for (int coin : coins) {    
            for (int i = coin; i <= amount; ++i) { 
                dp[i] += dp[i - coin];
            }
        }
        return dp[amount];
    }
};

其中，内层循环等价于下面的代码，这里做了简化。

1
2
3
4
5
6
7
8
for (int i = 0; i <= amount; ++i) {
    if (i - coin >= 0) {
        dp[i] += dp[i - coin];// 拿
    }
    else {
        dp[i] += 0;// 不拿
    }
}

Day2 --- 2642. 设计可以求最短路径的图类

题目

给你一个有 n 个节点的 有向带权 图，节点编号为 0 到 n - 1 。图中的初始边用数组 edges 表示，其中 edges[i] = [fromi, toi, edgeCosti] 表示从 fromi 到 toi 有一条代价为 edgeCosti 的边。
请你实现一个 Graph 类：
- Graph(int n, int[][] edges) 初始化图有 n 个节点，并输入初始边。
- addEdge(int[] edge) 向边集中添加一条边，其中 edge = [from, to, edgeCost] 。数据保证添加这条边之前对应的两个节点之间没有有向边。
int shortestPath(int node1, int node2) 返回从节点 node1 到 node2 的路径 最小 代价。如果路径不存在，返回 -1 。一条路径的代价是路径中所有边代价之和。

题解

还未学到图的相关知识，暂时跳过。

Day3 --- 2580. 统计将重叠区间合并成组的方案数

题目

给你一个二维整数数组 ranges ，其中 ranges[i] = [starti, endi] 表示 starti 到 endi 之间（包括二者）的所有整数都包含在第 i 个区间中。

你需要将 ranges 分成 两个 组（可以为空），满足：

每个区间只属于一个组。 两个有 交集 的区间必须在 同一个 组内。 如果两个区间有至少 一个 公共整数，那么这两个区间是 有交集 的。

比方说，区间 [1, 3] 和 [2, 5] 有交集，因为 2 和 3 在两个区间中都被包含。 请你返回将 ranges 划分成两个组的 总方案数 。由于答案可能很大，将它对 1e9 + 7 取余 后返回。

题解

  • 这道题本质上就是求合并后的区间个数cnt，然后再求组合数。
  • 对于每个区间，可以选择放入第一组或者第二组，所以有2^cnt种方案。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
class Solution {
public:
    int countWays(vector<vector<int>>& ranges) {
        int ans = 1, max_r = -1;
        //按照区间左端点升序排序
        sort(ranges.begin(), ranges.end(), [](auto &a, auto &b){return a[0] < b[0];});
        // ranges::sort(ranges, [](auto &a, auto &b) { return a[0] < b[0]; });
        for(auto &range : ranges){
          //排序后的左端点如果大于max_r，说明这两个区间不重叠，后面的区间不可能再与之重叠
          //更新方案数量，然后更新区间右端点max_r
            if(range[0] > max_r) ans = ans * 2 % 1000000007;
            max_r = max(range[1], max_r);
        }
        return ans;  
    }
};

上面的排序代码中，使用了lambda表达式，可以参考这篇博文。
ranges::sort(ranges, ...)这里使用了C++20的特性，第一个参数是排序对象，第二个参数是比较函数，比较函数的返回值为bool类型，表示是否交换两个元素的位置。

Day4 --- 1997. 访问完所有房间的第一天

题目

你需要访问 n 个房间，房间从 0 到 n - 1 编号。同时，每一天都有一个日期编号，从 0 开始，依天数递增。你每天都会访问一个房间。

最开始的第 0 天，你访问 0 号房间。给你一个长度为 n 且 下标从 0 开始 的数组 nextVisit 。在接下来的几天中，你访问房间的 次序 将根据下面的 规则 决定：

  • 假设某一天，你访问 i 号房间。
  • 如果算上本次访问，访问 i 号房间的次数为 奇数 ，那么 第二天 需要访问 nextVisit[i] 所指定的房间，其中 0 <= nextVisit[i] <= i 。
  • 如果算上本次访问，访问 i 号房间的次数为 偶数 ，那么 第二天 需要访问 (i + 1) mod n 号房间。
    请返回你访问完所有房间的第一天的日期编号。题目数据保证总是存在这样的一天。由于答案可能很大，返回对 10e9 + 7 取余后的结果。

题解

  • 动态规划问题，使用dp数组进行解答。
  • dp[i]表示访问完所有房间的第一天的日期编号。
  • 对于每个房间i，如果访问i号房间的次数为奇数，那么第二天访问nextVisit[i]号房间，否则访问(i + 1) mod n号房间。
  • 由于访问i号房间的次数为奇数，那么访问nextVisit[i]号房间的次数为偶数，所以dp[nextVisit[i]]为dp[i] + 1。
  • 访问(i + 1) mod n号房间的次数为偶数，所以dp[(i + 1) mod n]为dp[i] + 2。
  • 最后返回dp[n - 1]即可。
1
2
3
4
5
6
7
8
9
10
11
class Solution {
public:
    int firstDayBeenInAllRooms(vector<int>& nextVisit) {
        int n = nextVisit.size();
        vector<long> dp(n, 0);
        for (int i = 1; i < n; ++i) {
            dp[i] = ( 2 * dp[i - 1] - dp[nextVisit[i - 1]] + 2 + 1000000007) % 1000000007;
        }
        return dp[n - 1];
    }
};

Day5 --- 2908. 元素和最小的山形三元组 I

题目

给你一个下标从 0 开始的整数数组 nums 。

如果下标三元组 (i, j, k) 满足下述全部条件，则认为它是一个 山形三元组 ：

  • i < j < k
  • nums[i] < nums[j] 且 nums[k] < nums[j] 请你找出 nums 中 元素和最小 的山形三元组，并返回其 元素和 。如果不存在满足条件的三元组，返回 -1 。

题解

  • 前缀数组pre存储nums中k之前的最小值。
  • 后缀数组suf存储nums中k之后的最小值。
  • 同时遍历nums，pre和suf数组，找到满足条件的山形三元组，取最小值即可。
  • 前缀可以使用局部变量代替，减少空间复杂度。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
class Solution {
public: 
    int minimumSum(vector<int>& nums) {
        int n = nums.size();
        vector<int> suf(n, 0);
        suf[n - 1] = nums[n - 1];
        for (int i = n - 2; i >= 0; --i) {
            suf[i] = min(suf[i + 1], nums[i]);
        }
        int res = INT_MAX;
        int pre = nums[0];
        for (int i = 1; i < n - 1; ++i) {
            pre = min(pre, nums[i - 1]);
            if (pre < nums[i] && nums[i] > suf[i + 1]) {
                res = min(res, pre + nums[i] + suf[i + 1]);
            }
        }
        return res == INT_MAX ? -1 : res;
    }
};

Day6 --- 2952. 需要添加的硬币的最小数量

题目

给你一个下标从 0 开始的整数数组 coins，表示可用的硬币的面值，以及一个整数 target 。

如果存在某个 coins 的子序列总和为 x，那么整数 x 就是一个 可取得的金额 。

返回需要添加到数组中的 任意面值 硬币的 最小数量 ，使范围 [1, target] 内的每个整数都属于 可取得的金额 。

数组的 子序列 是通过删除原始数组的一些（可能不删除）元素而形成的新的 非空 数组，删除过程不会改变剩余元素的相对位置。

题解

参考链接

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
class Solution {
public:
    int minimumAddedCoins(vector<int>& coins, int target) {
        ranges::sort(coins);
        int res = 0, right = 1, i = 0;
        while(right <= target){
            if(i < coins.size() && coins[i] <= right){
                right += coins[i++];
            }
            else{
                right *= 2;
                res++;
            }
        }
        return res;
    }
};

Day7 --- 331. 验证二叉树的前序序列化

题目

序列化二叉树的一种方法是使用 前序遍历 。当我们遇到一个非空节点时，我们可以记录下这个节点的值。如果它是一个空节点，我们可以使用一个标记值记录，例如#。

给定一串以逗号分隔的序列，验证它是否是正确的二叉树的前序序列化。编写一个在不重构树的条件下的可行算法。

保证 每个以逗号分隔的字符或为一个整数或为一个表示 null 指针的 '#' 。

你可以认为输入格式总是有效的

例如它永远不会包含两个连续的逗号，比如 "1,,3" 。
注意：不允许重建树。

题解

  • 使用栈进行解答。
  • 遍历字符串，如果当前字符为#，表示空节点，如果栈顶也为#，则表示当前空节点和其父节点连续为空节点，需要将它们一起弹出，直到栈顶不是#或者栈为空。在此过程中，如果栈为空，则表示序列不合法，然后将当前空节点压入栈中。
  • 如果当前字符不为#，表示非空节点，将其压入栈中。
  • 遍历结束后，判断栈中是否只有一个元素，且为#。

举例："9,3,4,#,#,1,#,#,2,#,6,#,#"

  • 遍历到9，压入栈中，栈：9
  • 遍历到3，压入栈中，栈：9, 3
  • 遍历到4，压入栈中，栈：9, 3, 4
  • 遍历到#，栈顶为4，压入栈中，栈：9, 3, 4, #
  • 遍历到#，栈顶为#，弹出栈顶及其父节点，栈：9, 3
    • 将当前空节点压入栈中，栈：9, 3, #
  • 遍历到1，压入栈中，栈：9, 3, #, 1
  • 遍历到#，栈顶为1，压入栈中，栈：9, 3, #, 1, #
  • 遍历到#，栈顶为#，弹出栈顶及其父节点，栈：9, 3, #
    • 此时栈顶为#，弹出栈顶及其父节点，栈：9
      • 将当前空节点压入栈中，栈：9, #
  • 遍历到2，压入栈中，栈：9, #, 2
  • 遍历到#，栈顶为2，压入栈中，栈：9, #, 2, #
  • 遍历到6，压入栈中，栈：9, #, 2, #, 6
  • 遍历到#，栈顶为6，压入栈中，栈：9, #, 2, #, 6, #
  • 遍历到#，栈顶为#，弹出栈顶及其父节点，栈：9, #, 2, #
    • 此时栈顶为#，弹出栈顶及其父节点，栈：9, #
      • 此时栈顶为#，弹出栈顶及其父节点，栈：
      • 将当前空节点压入栈中，栈：#
  • 遍历结束，判断栈中是否只有一个元素，且为#，返回true。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
class Solution {
public:
    bool isValidSerialization(string preorder) {
        stack<string> stk;
        stringstream ss(preorder);
        string str;
        while (getline(ss, str, ',')) {
            while (!stk.empty() && stk.top() == "#" && str == "#") {
                stk.pop();
                if (stk.empty()) return false;
                stk.pop();
            }
            stk.push(str);
        }
        return stk.size() == 1 && stk.top() == "#";
    }
};