On the shoulders of giants.

biweekly-contest-30

转变日期格式

给你一个字符串 date ,它的格式为 Day Month Year ,其中:

  • Day 是集合 {"1st", "2nd", "3rd", "4th", ..., "30th", "31st"} 中的一个元素。
  • Month 是集合 {"Jan", "Feb", "Mar", "Apr", "May", "Jun", "Jul", "Aug", "Sep", "Oct", "Nov", "Dec"} 中的一个元素。
  • Year 的范围在 ​[1900, 2100] 之间。

请你将字符串转变为 YYYY-MM-DD 的格式,其中:

  • YYYY 表示 4 位的年份。
  • MM 表示 2 位的月份。
  • DD 表示 2 位的天数。

示例 1:

输入:date = "20th Oct 2052"
输出:"2052-10-20"

示例 2:

输入:date = "6th Jun 1933"
输出:"1933-06-06"

示例 3:

输入:date = "26th May 1960"
输出:"1960-05-26"

提示:

  • 给定日期保证是合法的,所以不需要处理异常输入。
题解

直接模拟。

时间复杂度:\(O(n)\)

class Solution {
public:
    string get_month_value(string month) {
        if(month == "Jan") return "01";
        if(month == "Feb") return "02";
        if(month == "Mar") return "03";
        if(month == "Apr") return "04";
        if(month == "May") return "05";
        if(month == "Jun") return "06";
        if(month == "Jul") return "07";
        if(month == "Aug") return "08";
        if(month == "Sep") return "09";
        if(month == "Oct") return "10";
        if(month == "Nov") return "11";
        if(month == "Dec") return "12";
        return "";
    }
    string reformatDate(string date) {
        string result = "";
        int p = 0, n = date.length();
        result = date.substr(n - 4, 4);
        while(date[p] != ' ') p++;
        result += "-" + get_month_value(date.substr(p + 1, 3)) + "-";
        if('0' <= date[1] && date[1] <= '9') {
            result += date.substr(0, 2);
        } else {
            result += "0" + string(1, date[0]);
        }
        return result;
    }
};

子数组和排序后的区间和

给你一个数组 nums ,它包含 n 个正整数。你需要计算所有非空连续子数组的和,并将它们按升序排序,得到一个新的包含 n * (n + 1) / 2 个数字的数组。

请你返回在新数组中下标为left 到 right (下标从 1 开始)的所有数字和(包括左右端点)。由于答案可能很大,请你将它对 10^9 + 7 取模后返回。

示例 1:

输入:nums = [1,2,3,4], n = 4, left = 1, right = 5
输出:13 
解释:所有的子数组和为 1, 3, 6, 10, 2, 5, 9, 3, 7, 4 。将它们升序排序后,我们得到新的数组 [1, 2, 3, 3, 4, 5, 6, 7, 9, 10] 。下标从 le = 1 到 ri = 5 的和为 1 + 2 + 3 + 3 + 4 = 13 。

示例 2:

输入:nums = [1,2,3,4], n = 4, left = 3, right = 4
输出:6
解释:给定数组与示例 1 一样,所以新数组为 [1, 2, 3, 3, 4, 5, 6, 7, 9, 10] 。下标从 le = 3 到 ri = 4 的和为 3 + 3 = 6 。

示例 3:

输入:nums = [1,2,3,4], n = 4, left = 1, right = 10
输出:50

提示:

  • 1 <= nums.length <= 10^3
  • nums.length == n
  • 1 <= nums[i] <= 100
  • 1 <= left <= right <= n * (n + 1) / 2
题解

构造新数组然后排序后,遍历区间。

时间复杂度:\(O(n^2\log {n^2})\)

const int MOD = 1E9 + 7;
class Solution {
public:
    int rangeSum(vector<int>& nums, int n, int left, int right) {
        vector<int> val(n * (n + 1) / 2);
        for(int i = 0, x = 0; i < n; i++) {
            for(int j = i; j < n; j++) {
                if(i == j) val[x++] = nums[j];
                else val[x++] = val[x - 1] + nums[j];
            }
        }
        sort(val.begin(), val.end());
        int result = 0;
        for(int i = left; i <= right; i++) {
            result = (result + val[i - 1]) % MOD;
        }
        return result;
    }
};

三次操作后最大值与最小值的最小差

给你一个数组 nums ,每次操作你可以选择 nums 中的任意一个元素并将它改成任意值。

请你返回三次操作后, nums 中最大值与最小值的差的最小值。

示例 1:

输入:nums = [5,3,2,4]
输出:0
解释:将数组 [5,3,2,4] 变成 [2,2,2,2].
最大值与最小值的差为 2-2 = 0 。

示例 2:

输入:nums = [1,5,0,10,14]
输出:1
解释:将数组 [1,5,0,10,14] 变成 [1,1,0,1,1] 。
最大值与最小值的差为 1-0 = 1 。

示例 3:

输入:nums = [6,6,0,1,1,4,6]
输出:2

示例 4:

输入:nums = [1,5,6,14,15]
输出:1

提示:

  • 1 <= nums.length <= 10^5
  • -10^9 <= nums[i] <= 10^9
题解

从小到大排序后,枚举删除最左边多少个,最后边多少个。

时间复杂度:\(O(n\log n)\)

class Solution {
public:
    int minDifference(vector<int>& nums) {
        if(nums.size() <= 4) return 0;
        sort(nums.begin(), nums.end());
        int result = 2E9;
        for(int i = 0; i <= 3; i++) {
            int j = 3 - i;
            result = min(result, nums[nums.size() - 1 - j] - nums[i]);
        }
        return result;
    }
};

石子游戏 IV

Alice 和 Bob 两个人轮流玩一个游戏,Alice 先手。

一开始,有 n 个石子堆在一起。每个人轮流操作,正在操作的玩家可以从石子堆里拿走 任意 非零 平方数 个石子。

如果石子堆里没有石子了,则无法操作的玩家输掉游戏。

给你正整数 n ,且已知两个人都采取最优策略。如果 Alice 会赢得比赛,那么返回 True ,否则返回 False 。

示例 1:

输入:n = 1
输出:true
解释:Alice 拿走 1 个石子并赢得胜利,因为 Bob 无法进行任何操作。

示例 2:

输入:n = 2
输出:false
解释:Alice 只能拿走 1 个石子,然后 Bob 拿走最后一个石子并赢得胜利(2 -> 1 -> 0)。

示例 3:

输入:n = 4
输出:true
解释:n 已经是一个平方数,Alice 可以一次全拿掉 4 个石子并赢得胜利(4 -> 0)。

示例 4:

输入:n = 7
输出:false
解释:当 Bob 采取最优策略时,Alice 无法赢得比赛。
如果 Alice 一开始拿走 4 个石子, Bob 会拿走 1 个石子,然后 Alice 只能拿走 1 个石子,Bob 拿走最后一个石子并赢得胜利(7 -> 3 -> 2 -> 1 -> 0)。
如果 Alice 一开始拿走 1 个石子, Bob 会拿走 4 个石子,然后 Alice 只能拿走 1 个石子,Bob 拿走最后一个石子并赢得胜利(7 -> 6 -> 2 -> 1 -> 0)。

示例 5:

输入:n = 17
输出:false
解释:如果 Bob 采取最优策略,Alice 无法赢得胜利。

提示:

  • 1 <= n <= 10^5
题解

确定要必胜态后,从小到大判断是否存在让对手处于必败态。

时间复杂度:\(O(n)\)

class Solution {
public:
    bool winnerSquareGame(int n) {
        vector<int> f(n + 1);
        for(int i = 1; i <= n / i; i++) f[i * i] = 1;
        for(int i = 0; i <= n; i++) {
            if(f[i] == 1) continue;
            for(int j = 1; j <= i / j; j++) {
                if(f[i - j * j] == 0) {
                    f[i] = 1;
                    break;
                }
            }
        }
        return f[n];
    }
};
Share

You may also like...

发表评论

电子邮件地址不会被公开。 必填项已用*标注