5247. 交换字符使得字符串相同
5247. 交换字符使得字符串相同
用户通过次数583
用户尝试次数721
通过次数597
提交次数1363
题目难度Easy
有两个长度相同的字符串 s1 和 s2，且它们其中 只含有 字符 "x" 和 "y"，你需要通过「交换字符」的方式使这两个字符串相同。
每次「交换字符」的时候，你都可以在两个字符串中各选一个字符进行交换。
交换只能发生在两个不同的字符串之间，绝对不能发生在同一个字符串内部。也就是说，我们可以交换 s1[i] 和 s2[j]，但不能交换 s1[i] 和 s1[j]。
最后，请你返回使 s1 和 s2 相同的最小交换次数，如果没有方法能够使得这两个字符串相同，则返回 -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'。
这个题是个找规律题。
- 记录下x-y和y-x的个数，因为除去相同的x-x，y-y，剩下的都是上图不相等的。
- 任意两个x-y或y-x可以经过一次交换变成相同的
- 所以可以经过取模运算可以得到成对的x-y或y-x的个数，也就是变换的次数
- 成对的计算完，最终可能有三种情况。
- x-y和y-x各剩一个——这种变化次数是2
- 各剩0，这种不需要再交换了
- 其他，都是不能交换成功的
public int minimumSwap(String s1, String s2) {
if (s1.length() != s2.length()) {
return -1;
}
int countXY = 0;
int countYX = 0;
for (int i = 0; i < s1.length(); i++) {
if (s1.charAt(i) == 'x' && s2.charAt(i) == 'y') {
countXY++;
} else if (s1.charAt(i) == 'y' && s2.charAt(i) == 'x') {
countYX++;
}
}
int sum = countYX / 2;
countYX = countYX % 2;
sum += countXY / 2;
countXY = countXY % 2;
if (countXY == 1 && countYX == 1) {
return sum + 2;
} else if (countXY == 0 && countYX == 0) {
return sum;
} else {
return -1;
}
}
5248. 统计「优美子数组」
5248. 统计「优美子数组」
用户通过次数407
用户尝试次数605
通过次数415
提交次数1137
题目难度Medium
给你一个整数数组 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
很简单，将所有的奇数下标存到list里面。然后遍历。
- 对于最左边的index，计算他与上一个index的距离
- 对于最右边的index，计算他与下一个index的距离
- 最终结果就是 += 左边距离 * 右边距离
前面两个注释的代码都超时了，第一个是暴力循环，第二个是两重循环的前缀和。
public int numberOfSubarrays(int[] nums, int k) {
/* int count = 0;
int left = -1;
int sum = 0;
for (int i = 0; i < nums.length; i++) {
if (nums[i] % 2 == 1) {
if (left == -1) {
left = i;
}
count++;
}
if (count == k) {
int l = 1;
int r = 1;
int lefttem = left;
while (lefttem > 0 && nums[--lefttem] % 2 == 0) {
l++;
}
int item = i;
while (item < nums.length - 1 && nums[++item] % 2 == 0) {
r++;
}
sum += l * r;
if (i == nums.length - 1) {
break;
} else {
i = left;
}
left = -1;
count = 0;
}
}
return sum;*/
/* int arr[] = new int[nums.length + 1];
for (int i = 0; i < nums.length; i++) {
if (nums[i] % 2 == 0) {
nums[i] = 0;
} else {
nums[i] = 1;
}
}
arr[0] = 0;
arr[1] = nums[0];
for (int i = 1; i < nums.length + 1; i++) {
arr[i] = arr[i - 1] + nums[i - 1];
}
int sum = 0;
for (int i = 0; i < arr.length; i++) {
for (int j = 0; j < i; j++) {
if (arr[i] - arr[j] == k) {
sum++;
}
}
}
return sum;*/
int sum = 0;
List<Integer> list = new ArrayList<>();
for (int i = 0; i < nums.length; i++) {
if (nums[i] % 2 == 1) {
list.add(i);
}
}
for (int i = k - 1; i < list.size(); i++) {
int l, r;
int leftIndex = i - k + 1;
if (leftIndex > 0) {
l = list.get(leftIndex) - list.get(leftIndex - 1);
} else {
l = list.get(leftIndex) + 1;
}
if (i < list.size() - 1) {
r = list.get(i + 1) - list.get(i);
} else {
r = nums.length - list.get(i);
}
sum += r * l;
}
return sum;
}
5249. 移除无效的括号
5249. 移除无效的括号
用户通过次数419
用户尝试次数500
通过次数425
提交次数839
题目难度Medium
给你一个由 '('、')' 和小写字母组成的字符串 s。
你需要从字符串中删除最少数目的 '(' 或者 ')' （可以删除任意位置的括号)，使得剩下的「括号字符串」有效。
请返回任意一个合法字符串。
有效「括号字符串」应当符合以下 任意一条 要求：
空字符串或只包含小写字母的字符串
可以被写作 AB（A 连接 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] 可能是 '('、')' 或英文小写字母
用栈写。
-
对于(直接入栈
-
对于)如果栈是空不做操作
-
不是空，那么栈顶的(则是有效的括号，对应的当前的)也是有效的
最后遍历就好，
如果是合法的括号就append上、
public String minRemoveToMakeValid(String s) {
Deque<Integer> stack = new LinkedList<>();
boolean[] isValid = new boolean[s.length()];
for (int i = 0; i < s.length(); i++) {
if (s.charAt(i) == '(') {
stack.push(i);
} else if (s.charAt(i) == ')') {
if (!stack.isEmpty()) {
isValid[stack.pop()] = true;
isValid[i] = true;
}
}
}
StringBuilder sb = new StringBuilder();
for (int i = 0; i < s.length(); i++) {
if ((s.charAt(i) == '(' || s.charAt(i) == ')') ) {
if (isValid[i]) {
sb.append(s.charAt(i));
}
} else {
sb.append(s.charAt(i));
}
}
return sb.toString();
}
5250. 检查「好数组」
5250. 检查「好数组」
用户通过次数173
用户尝试次数243
通过次数186
提交次数540
题目难度Hard
给你一个正整数数组 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。如果是那就是true，不是，那就是false。
public boolean isGoodArray(int[] nums) {
int g = nums[0];
for (int num : nums) {
g = Gcd(g, num);
}
return g == 1;
}
int Gcd(int a, int b) {
while (b != 0) {
int r = b;
b = a % b;
a = r;
}
return a;
}
扫一扫
被折叠的 条评论
为什么被折叠?
到【灌水乐园】发言
