On the shoulders of giants.

weekly-contest-161

交换字符使得字符串相同

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

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

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

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

示例 1:

输入:s1 = "xx", s2 = "yy"
输出:1
解释:
交换 s1[0] 和 s2[1],得到 s1 = "yx",s2 = "yx"。

示例 2:

输入:s1 = "xy", s2 = "yx"
输出:2
解释:
交换 s1[0] 和 s2[0],得到 s1 = "yy",s2 = "xx" 。
交换 s1[0] 和 s2[1],得到 s1 = "xy",s2 = "xy" 。
注意,你不能交换 s1[0] 和 s1[1] 使得 s1 变成 "yx",因为我们只能交换属于两个不同字符串的字符。

示例 3:

输入:s1 = "xx", s2 = "xy"
输出:-1

示例 4:

输入:s1 = "xxyyxyxyxx", s2 = "xyyxyxxxyx"
输出:4

提示:

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

因为两字符串要相同,所有一定有两字符串长度一样且 xy 都是偶数个。

假如只有一个对 s1[i]=’x’,s2[i]=’y’ ,那必定存在一对 s1[j]=’y’,s2[j]=’x’ 它们可以合法操作,且最少两次操作即可。

如果有成对出现的 s1[i]=’x’,s2[i]=’y’ 或是 s1[i]=’y’,s2[i]=’x’ 那么两对最少经过一次操作即可。

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

class Solution {
public:
    int minimumSwap(string s1, string s2) {
        if(s1.length() != s2.length()) return -1;
        
        int sumx = 0, sumy = 0, a = 0, b = 0;
        
        for(int i = 0; i < s1.length(); i++) {
            (s1[i] == 'x') ? sumx++ : sumy++;
            (s2[i] == 'x') ? sumx++ : sumy++;
        }
        
        if(sumx % 2 || sumy % 2) return -1;
        
        for(int i = 0; i < s1.length(); i++) {
            if(s1[i] != s2[i]) {
                (s1[i] == 'x') ? a++ : b++;
            }
        }
        
        return (a + 1) / 2 + (b + 1) / 2;
    }
};

统计「优美子数组」

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

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

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

示例 1:

输入:nums = [1,1,2,1,1], k = 3
输出:2
解释:包含 3 个奇数的子数组是 [1,1,2,1] 和 [1,2,1,1] 。

示例 2:

输入:nums = [2,4,6], k = 1
输出:0
解释:数列中不包含任何奇数,所以不存在优美子数组。

示例 3:

输入:nums = [2,2,2,1,2,2,1,2,2,2], k = 2
输出:16

提示:

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

pos 数组记录 nums[i] % 2 == 1 的位置 i ,用“长度”为 k 的双指针扫描一遍即可(应用乘法计数原理)。

为了操作简单,我们在 pos 最前面加入 0 ,在最后面加入 nums.size() + 1 ,代表原数组最前最后加入一个奇数。

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

class Solution {
public:
    int numberOfSubarrays(vector<int>& nums, int k) {
        vector<int> pos;
        int ret = 0;
        
        pos.push_back(0);
        for(int i = 0; i < nums.size(); i++) {
            if(nums[i] % 2) pos.push_back(i + 1);
        }
        pos.push_back(nums.size() + 1);
        
        if(pos.size() - 2 < k) return 0;
        
        for(int i = 1; i + k < pos.size(); i++) {
            int lef = i, rig = i + k - 1;
            ret += (pos[lef] - pos[lef - 1]) * (pos[rig + 1] - pos[rig]);
        }
        
        return ret;
    }
};

移除无效的括号

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

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

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

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

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

示例 1:

输入:s = "lee(t(c)o)de)"
输出:"lee(t(c)o)de"
解释:"lee(t(co)de)" , "lee(t(c)ode)" 也是一个可行答案。

示例 2:

输入:s = "a)b(c)d"
输出:"ab(c)d"

示例 3:

输入:s = "))(("
输出:""
解释:空字符串也是有效的

示例 4:

输入:s = "(a(b(c)d)"
输出:"a(b(c)d)"

提示:

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

模拟栈的操作,不合法的最后会留在栈内,答案应该不能包含最后栈内的元素。

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

class Solution {
public:
    string minRemoveToMakeValid(string s) {
        vector<int> sta(s.length());
        int top = 0, x = 0;
        string ret = "";
        
        for(int i = 0; i < s.length(); i++) {
            if(s[i] == '(' || s[i] == ')') {
                if(top == 0) sta[top++] = i;
                else {
                    if(s[sta[top - 1]] == '(') {
                        if(s[i] == ')') top--;
                        else sta[top++] = i;
                    }
                    else sta[top++] = i;
                }
            }
        }
        
        for(int i = 0; i < s.length(); i++) {
            if(x < top && sta[x] == i) {
                x++;
                continue;
            }
            ret += s[i];
        }
        
        return ret;
    }
};

检查「好数组」

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

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

示例 1:

输入:nums = [12,5,7,23]
输出:true
解释:挑选数字 5 和 7。
5*3 + 7*(-2) = 1

示例 2:

输入:nums = [29,6,10]
输出:true
解释:挑选数字 29, 6 和 10。
29*1 + 6*(-3) + 10*(-1) = 1

示例 3:

输入:nums = [3,6]
输出:false

提示:

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

裴蜀定理n 个整数数间): 设a_1,a_2,a_3,...,a_nn 个整数, d 是它们的最大公约数,那么存在整数 x_1,x_2,...,x_n  使得 x_1*a_1+x_2*a_2+...+x_n*a_n=d

即求出所有数的 gcd ,如果所有数的 gcd 都不能满足 gcd = 1 ,那么无解,否则存在解。

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

class Solution {
public:
    int gcd(int a, int b) {
        return b ? gcd(b, a % b) : a;
    }
    bool isGoodArray(vector<int>& nums) {
        int d = 0;
        for(auto a : nums) {
            d = gcd(d, a);
        }
        return d == 1;
    }
};
Share

You may also like...

发表评论

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