LeetCode第161场周赛复盘

2019/11/03 LeetCode

欢迎来到LeetCode第161场周赛。这是我第一次参加LeetCode的周赛,比赛时间是1小时30分钟,题目数量是4题。个人觉得题目难度不大,在最后几分钟里我将所有题目都做完了。下面是对本次比赛的复盘。

5247.交换字符使得字符串相同

有两个长度相同的字符串s1s2,且它们其中只含有字符"x""y",你需要通过「交换字符」的方式使这两个字符串相同。

每次「交换字符」的时候,你都可以在两个字符串中各选一个字符进行交换。

交换只能发生在两个不同的字符串之间,绝对不能发生在同一个字符串内部。也就是说,我们可以交换s1[i]s2[j],但不能交换s1[i]s1[j]

最后,请你返回使s2s1相同的最小交换次数,如果没有方法能够使得这两个字符串相同,则返回-1

输入输出

input: s1 = "xx", s2 = "yy"
output: 1

input: s1 = "xy", s2 = "yx"
output: 2

input: s1 = "xx", s2 = "xy"
output: -1

input: s1 = "xxyyxyxyxx", s2 = "xyyxyxxxyx"
output: 4

约束

  • 1 <= s1.length, s2.length <= 1000
  • s1, s2只包含’x’或’y’

思路

我在观察样例1和样例2的时候发现,这两种情况是最小的规约条件,也就是所有问题都可以转变为能够寻找多少对“xx|yy”与“xy|yx”的组合。前者需要1次交换,后者需要2次交换。

例如样例4,将两个字符串相同位去掉剩下s1=”xyxyyx”, s2=”yxyxxy”,按位排序可以将其转化为s1=”xxxyyy”, s2=”yyyxxx”,存在两对“xx|yy”与一对“xy|yx”的组合,即结果为1+1+2=4。

解答

class Solution {
public:
    int minimumSwap(string s1, string s2) {
        int a = 0, b = 0;
        int res = 0;
        for(int i=0; i<s1.size(); i++){
            if(s1[i] == 'x' && s2[i] == 'y')
                a++;
            if(s1[i] == 'y' && s2[i] == 'x')
                b++;
        }
        res += a/2 + b/2;
        a %= 2;
        b %= 2;
        if(a+b == 1)
            return -1;
        res += a+b;
        return res;
    }
};

5248.统计优美子数组

给你一个整数数组nums和一个整数k

如果某个子数组中恰好有k个奇数数字,我们就认为这个子数组是「优美子数组」。

请返回这个数组中「优美子数组」的数目。

输入输出

input: nums = [1,1,2,1,1], k = 3
output: 2

input: nums = [2,4,6], k = 1
output: 0

input: nums = [2,2,2,1,2,2,1,2,2,2], k = 2
output: 16

约束

  • 1 <= nums.length <= 50000
  • 1 <= nums[i] <= 10^5
  • 1 <= k <= nums.length

思路

用数组tmp保存下nums中奇数的下标,随后挑出第i与第i+k-1个下标,以这两个下标作为左区间和右区间,此时nums的子数组[tmp[i], tmp[i+k-1]]刚好存在k个奇数。

以tmp[i]为下标往左边搜索nums,直到遇到边界或者是第一个奇数,假设左边有a个偶数。同样道理以tmp[i+k-1]为下标往右边搜索nums,假设右边有b个偶数。那么对于这个区间,总共有1+a+b+a*b种子数组满足题意。

以样例4为例子。数组tmp保存下[3,6],表示这些下标对应的位置是奇数。其中nums的子数组[1,2,2,1]刚好存在k=2个奇数。随后开始拓展,该子数组的左边有3个偶数,右边有3个偶数,所以结果是1+3+3+3*3=16种。

解答

class Solution {
public:
    int numberOfSubarrays(vector<int>& nums, int k) {
        vector<int> tmp;
        for(int i=0; i<nums.size(); i++){
            if(nums[i] % 2 == 1){
                tmp.push_back(i);
            }
        }
        if(tmp.size() < k)
            return 0;
        int res = 0;
        for(int i=0; i<tmp.size()-k+1; i++){
            int start = tmp[i];
            int end = tmp[i+k-1];
            
            int t1 = start - 1;
            while(t1 >= 0 && nums[t1] % 2 == 0){
                t1--;
            }
            t1++;
            
            int t2 = end + 1;
            while(t2 < nums.size() && nums[t2] % 2 == 0){
                t2++;
            }
            t2--;
            
            cout << t1 << " " << t2 << endl;
            res += (1 + (start - t1) + (t2 - end) + (start - t1)*(t2 - end));
        }
        return res;
    }
};

5248.移除无效的括号

给你一个由'('')'和小写字母组成的字符串s

你需要从字符串中删除最少数目的'('或者')'(可以删除任意位置的括号),使得剩下的「括号字符串」有效。

请返回任意一个合法字符串。

有效「括号字符串」应当符合以下任意一条要求:

- 空字符串或只包含小写字母的字符串
- 可以被写作 AB(A 连接 B)的字符串,其中 A 和 B 都是有效「括号字符串」
- 可以被写作 (A) 的字符串,其中 A 是一个有效的「括号字符串」

输入输出

input: s = "lee(t(c)o)de)"
output: "lee(t(c)o)de"

input: s = "a)b(c)d"
output: "ab(c)d"

input: s = "))(("
output: ""

input: s = "(a(b(c)d)"
output: "a(b(c)d)"

约束

  • 1 <= s.length <= 10^5
  • s[i] 可能是 ‘(‘、’)’ 或英文小写字母

思路

第一反应是使用栈。遇到左括号的时候入栈,遇到右括号的时候检查栈是否为空,如果为空那么这个右括号无效,否则右括号有效,并弹出栈的一个元素(这个元素是左括号,并且有效)。

因为字符串是从左到右遍历的,所以在遇到右括号的时候,没有办法知道前边的左括号在哪个位置。一个简单的办法是,当遇到右括号是有效的时候,对其做标记,此时栈要弹出一个元素,那么我们需要对字符串向前搜索第一个遇到的左括号(一定会遇到),然后将其做标记。

扫描一遍之后,没有被做标记的左右括号都是无效的,可以删除掉。我在下面的代码中模拟了栈的操作,但是没有使用栈。前几次提交都出现了内存不足的错误,原因是我使用了额外的字符串来储存结果。这个题目的正确做法是对字符串做原址操作,否则会出现内存不足。

解答

class Solution {
public:
    string minRemoveToMakeValid(string s) {
        int su = 0;
        for(int i=0; i<s.size(); i++){
            if(s[i] == '('){
                su++;
            }
            if(s[i] == ')'){
                if(su != 0){
                    int t = i;
                    // 向前搜索第一个左括号
                    while(s[t] != '(')
                        t--;
                    // 做标记
                    s[t] = '#';
                    s[i] = '$';
                    su--;
                }
            }
        }
        int posi = 0;
        while((posi = s.find('(')) != string::npos){
            s.erase(posi, 1);
        }
        while((posi = s.find(')')) != string::npos){
            s.erase(posi, 1);
        }
        for(string::iterator it = s.begin(); it!=s.end(); it++){
            if(*it == '#')
                *it = '(';
            if(*it == '$')
                *it = ')';
        }
        return s;
    }
};

5250.检查好数组

给你一个正整数数组nums,你需要从中任选一些子集,然后将子集中每一个数乘以一个任意整数,并求出他们的和。

假如该和结果为1,那么原数组就是一个「好数组」,则返回True;否则请返回False

输入输出

input: nums = [12,5,7,23]
output: true
// 5*3 + 7*(-2) = 1

input: nums = [29,6,10]
output: true
// 29*1 + 6*(-3) + 10*(-1) = 1

input: nums = [3,6]
output: false

约束

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

思路

先说结论,这道题转换为求解nums数组所有数的最大公约数是否为1,如果为1,则输出true,否则输出false。很简单吧,哈哈。

假设nums = [a1, a2, a3, … , an],那么用数学语言描述就是对于下列等式是否存在整数解:

这种想法完全是灵机一现,假如nums的所有数的最大公约数不为1,假设为k,那么上式化简为:

对于上面这条式子,k不等于1,而括号中的值不管等于多少都不可能使等式结果为1。所以反过来说,当k等于1时,存在整数解满足上式(这个说法不是数学证明,只是猜测)。那么k等于1时是什么意义呢?也就是nums数组中的所有数的最大公约数为1。对于两个数的最大公约数很容易求,用拓展的欧几里得算法。那么对于n个数呢?看下面的解答。

解答

class Solution {
public:
    int gcd(int a, int b){
        return b == 0 ? a : gcd(b, a%b);
    }
    int ngcd(vector<int>& nums, int n){
        if(n == 1)
            return nums[0];
        return gcd(nums[n-1], ngcd(nums, n-1));
    }
    bool isGoodArray(vector<int>& nums) {
        int a = ngcd(nums, nums.size());
        return a == 1;
    }
};

总结

我非常喜欢LeetCode的答题模式,相比于传统的ACM,LeetCode的题目更强调关注算法过程,而不是要关注引入什么头文件、输入输出的格式等等。这次周赛的难度相比于ACM算是比较简单的,下次继续努力。

Search

    Table of Contents