1154. 一年中的第几天

给你一个按 YYYY-MM-DD 格式表示日期的字符串 date，请你计算并返回该日期是当年的第几天。

通常情况下，我们认为 1 月 1 日是每年的第 1 天，1 月 2 日是每年的第 2 天，依此类推。每个月的天数与现行公元纪年法（格里高利历）一致。
示例 1：

  1. 输入：date = "2019-01-09"
  2. 输出：9

示例 2：

输入：date = "2019-02-10"
输出：41

示例 3：

输入：date = "2003-03-01"
输出：60

示例 4：

输入：date = "2004-03-01"
输出：61

提示：

  • date.length == 10
  • date[4] == date[7] == '-'，其他的 date[i] 都是数字。
  • date 表示的范围从 1900 年 1 月 1 日至 2019 年 12 月 31 日。

思路：

  1. 判断好是否为闰年就完了，不需要注意别的事情

代码：

class Solution {
public:
    int ordinalOfDate(string date) {
        int year = stoi(date.substr(0, 4));
        int month = stoi(date.substr(5, 2));
        int day = stoi(date.substr(8, 2));
        int res = 0;
        vector<int> months{ 31, 28, 31, 30, 31, 30, 31, 31, 30, 31, 30, 31 };
        if (month <= 2)
            return accumulate(months.begin(), months.begin() + month - 1, day);
        else
        {
            if (year % 4 == 0)
            {
                if (year % 100 != 0)
                    res = 1;
                else if (year % 400 == 0)
                    res = 1;
            }
            res += accumulate(months.begin(), months.begin() + month - 1, day);
            return res;
        }
    }
};

1155. 掷骰子的N种方法

这里有 d 个一样的骰子，每个骰子上都有 f 个面，分别标号为 1, 2, ..., f。

我们约定：掷骰子的得到总点数为各骰子面朝上的数字的总和。

如果需要掷出的总点数为 target，请你计算出有多少种不同的组合情况（所有的组合情况总共有 f^d 种），模 10^9 + 7 后返回。

示例 1：

输入：d = 1, f = 6, target = 3
输出：1

示例 2：

输入：d = 2, f = 6, target = 7
输出：6

示例 3：

输入：d = 2, f = 5, target = 10
输出：1

示例 4：

输入：d = 1, f = 2, target = 3
输出：0

示例 5：

输入：d = 30, f = 30, target = 500
输出：222616187

提示：

  • 1 <= d, f <= 30
  • 1 <= target <= 1000

思路：

  1. 首先判断target是否符合条件，判断target和d * f之间的关系
  2. 不能使用暴力法，暴力法的时间复杂度为O(n!)
  3. 使用动态规划，转移方程如下
    $$
    dp(d, target) = \sum_{i=1}^{f} dp(d - 1, target - i)
    $$
    其中，d为骰子的个数，target就是题中给的target，f是骰子的面数。可以这么理解，要求d个骰子之和为target，可以分解为f种情况：第d个骰子的值为[1, 2, ..., f]，第1到第d-1个骰子的值之和为[target - 1, target - 2, ..., target - f]，然后d个骰子之和为target的情况数等于上述情况之和。

  4. 如果实在不理解的话，可以画个表格。其中纵轴是d = [1, 2, ...]，横轴是target = [1, 2, ...]。这里假定d=3，f=6 | | 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | 10 | 11 | 12 | 13 | 14 | 15 | 16 | 17 | | | —- | —- | —- | —- | —- | —- | —- | —- | —- | —- | —- | —- | —- | —- | —- | —- | —- | —- | —- | —- | | 1 | 0 | 1 | 1 | 1 | 1 | 1 | 1 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | | 2 | 0 | 0 | 1 | 2 | 3 | 4 | 5 | 6 | 5 | 4 | 3 | 2 | 1 | 0 | 0 | 0 | 0 | 0 | 0 | | 3 | 0 | 0 | 0 | 1 | 3 | 6 | 10 | 15 | 21 | 25 | 27 | 27 | 25 | 21 | 15 | 10 | 6 | 3 | 1 |

  5. trick: 题目说结果要mod 1e9+7，一开始我只在最终结果上做了mod操作，但是后来发现可以在计算表格的时候就mod，结果是一样的

代码：

class Solution {
public:
    int numRollsToTarget(int d, int f, int target) {
        if (target > d * f)
            return false;
        vector<vector<long>> dp(d + 1, vector<long>(d * f + 1, 0));
        for (int i = 1; i <= f; i++)
        {
            dp[1][i] = 1;
        }
        for (int i = 2; i <= d; i++)
        {
            for (int j = i; j <= min(target, i*f); j++)
            {
                for (int k = 1; k <= f; k++)
                    if (j - k >= 0)
                        dp[i][j] += (dp[i - 1][j - k]) % 1000000007;
            }
        }
        return dp[d][target] % 1000000007;
    }
};

1157. 子数组中占绝大多数的元素

实现一个 MajorityChecker 的类，它应该具有下述几个 API：

  • MajorityChecker(int[] arr) 会用给定的数组 arr 来构造一个 MajorityChecker 的实例。

    int query(int left, int right, int threshold)


  • 有这么几个参数：

    • 0 <= left <= right < arr.length 表示数组 arr 的子数组的长度。
    • 2 * threshold > right - left + 1，也就是说阀值 threshold 始终比子序列长度的一半还要大。

每次查询 query(...) 会返回在 arr[left], arr[left+1], ..., arr[right] 中至少出现阀值次数 threshold 的元素，如果不存在这样的元素，就返回 -1。

示例：

MajorityChecker majorityChecker = new MajorityChecker([1,1,2,2,1,1]);
majorityChecker.query(0,5,4); // 返回 1
majorityChecker.query(0,3,3); // 返回 -1
majorityChecker.query(2,3,2); // 返回 2

提示：

  • 1 <= arr.length <= 20000
  • 1 <= arr[i] <= 20000
  • 对于每次查询，0 <= left <= right < len(arr)
  • 对于每次查询，2 * threshold > right - left + 1
  • 查询次数最多为 10000

思路：

  1. 首先吐槽这个题目把阈值写成了阀值。。
  2. 求数组中出现次数超过一半的数字，这是一个很经典的算法了，思路大概如下
    • 在数组中每次选择两个不相同的数字，然后删除，这样剩下的数字中，原先次数超过一半的数组现在一定还超过一半。这样反复进行，直到数组中最后剩下的数字全都一样
    • 不需要每次都删除两个不一样的数字，也可以四个，六个，只要保证删除掉的数字中两两一组，每组的两个数字不相同就行
  3. 可以维护两个变量，cnt和curr_num，cnt表示curr_num出现的次数，然后遍历数组。如果当前数字和curr_num相同，则cnt += 1；如果不同，则cnt -= 1。如果cnt == 0的时候，将curr_num的值重新设置为当前的数字。
  4. 实在看不明白，可以看看别人的教程出现次数超过一半的数字
  5. 找到出现次数超过一半的数字之和，再次遍历数组，判断出现次数和threshold的关系，返回相应的值

代码：

class MajorityChecker {

private:
    vector<int> _arr;

public:
    MajorityChecker(vector<int>& arr) {
        _arr = arr;
    }

    int query(int left, int right, int threshold) {
        int cnt = 0;
        int curr = -1;
        for (int i = left; i <= right; i++)
        {
            if (cnt == 0)
            {
                cnt = 1;
                curr = _arr[i];
            }
            else if (_arr[i] == curr)
                cnt++;
            else
                cnt--;
        }
        cnt = 0;
        for (int i = left; i <= right; i++)
            cnt += (_arr[i] == curr) ? 1 : 0;
        return (cnt >= threshold) ? curr : -1;
    }
};