LeetCode周赛-149

超、凢脫俗 2021-11-01 05:22 326阅读 0赞

> LeetCode Weekly Test 149 做题整理
> 
> *2019年8月11日*

# 1 一年中的第几天\[⭐\] #

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

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

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzI2ODIyMDI5_size_16_color_FFFFFF_t_70][]

这是一道简单题，考察闰年平年的判断即可。

class Solution:
        def ordinalOfDate(self, date: str) -> int:
            ans = 0
            year, month, day = [int(item) for item in date.split('-')]
            month_list = [31, 28, 31, 30, 31, 30, 31, 31, 30, 31, 30, 31]
            if (year % 100 != 0 and year % 4 == 0) or year % 400 == 0:
                month_list[1] += 1
            for i in range(month - 1):
                ans += month_list[i]
    
            return ans + day

# 2 掷骰子的N种方法\[⭐⭐⭐\] #

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

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

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

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzI2ODIyMDI5_size_16_color_FFFFFF_t_70 1][]

这是一道动态规划题目，最好的方法是定义一个d+1行target+1列的矩阵逐行计算求解即可，因此时间复杂度为O(d\*target)，我在写这道题的时候想的是用备忘录的方法，然而用备忘录的方法会出问题（就不把我的错误思路放上来了）。

初始化的时候：dp\[0\]\[0\]=1，表示我们用0个筛子得到面数为0的情况只有一种，是这么说的。然后将其他位置全部初始化为0.

递推关系式：dp\[i\]\[j\] = (dp\[i\]\[j\]+dp\[i-1\]\[j-k\]) MOD 1e9+7，其中1≤k≤f。

const int MOD = 1e9+7;
    class Solution {
    public:
        int dp[35][1005];
        int numRollsToTarget(int d, int f, int target) {
            memset(dp, 0, sizeof(dp));
            dp[0][0] = 1;
            for(int i = 1; i <= d; i++) {
                for(int j = 1; j <= target; j++) {
                    for(int k = 1; k <= f; k++) {
                        if(j - k >= 0) {
                            dp[i][j] = (dp[i][j] + dp[i - 1][j - k]) % MOD;
                        }
                    }
                }
            }
        return dp[d][target];
        }
    };

# 3 单字符重复子串的最大长度\[⭐⭐⭐⭐\] #

如果字符串中的所有字符都相同，那么这个字符串是单字符重复的字符串。

给你一个字符串 `text`，你只能交换其中两个字符一次或者什么都不做，然后得到一些单字符重复的子串。返回其中最长的子串的长度。

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzI2ODIyMDI5_size_16_color_FFFFFF_t_70 2][]

作为一个编程菜鸟，我感觉这道题真的很难！在做题的时候没有什么好的思路，向大神学习了之后总结出来的。 这道题使用**快慢指针**就可以解决。

class Solution {
    public:
        int maxRepOpt1(string text) {
            map<char, int> cnt;
            for(char c : text){
                cnt[c]++;
            }
            
            int len = text.size();
            int ans = 0;
            for(auto item : cnt) {
                char chr = item.first;
                int ncnt = 0;
                int l = 0, r = 0;
                while(r < len) {
                    if(text[r] != chr)
                        ncnt++;
                    if(ncnt > 1) {
                        while(l <= r && text[l] == chr) l++;
                        l++;
                        ncnt--;
                    }
                    if(!ncnt || r - l + 1 <= item.second)
                        ans = max(ans, r - l + 1);
                    else
                        ans = max(ans, r - l);
                    r++;
                }
            }
            return ans;
        }
    };

# 4 子数组中占绝大多数的元素\[⭐⭐⭐⭐⭐\] #

实现一个 `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`。

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzI2ODIyMDI5_size_16_color_FFFFFF_t_70 3][]

（我觉得比赛之后，他们偷偷把题目要求改了。我用别人已经通过的答案也过不了全部测试！）

class MajorityChecker {
    public:
        
        vector<int> a;
        
        MajorityChecker(vector<int>& a) {
            int n = a.size();
            this->a = a;
        }
        
        int query(int x, int y, int v) {
            int cnt = 0, cur = -1;
            for (int i = x; i <= y; ++ i)
            {
                if (cnt == 0)
                {
                    cnt = 1;
                    cur = a[i];
                }
                else if (a[i] != cur)
                {
                    cnt --;
                }
                else
                {
                    cnt ++;
                }
            }
            int num = 0;
            for (int i = x; i <= y; ++ i)
                num += a[i] == cur;
            if (num >= v) return cur;
            return -1;
        }
    };

[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzI2ODIyMDI5_size_16_color_FFFFFF_t_70]: /images/20211101/75856e390e2d4f53b94a5b0a1b2afd72.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzI2ODIyMDI5_size_16_color_FFFFFF_t_70 1]: /images/20211101/ef651f41153847069decfa84b7acefc3.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzI2ODIyMDI5_size_16_color_FFFFFF_t_70 2]: /images/20211101/3369f77a25f449f3b650e14e3c1565ee.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzI2ODIyMDI5_size_16_color_FFFFFF_t_70 3]: /images/20211101/9d7f671d5d604717bfd1f32536a3271f.png