Leetcode第253场周赛解题分享 第二题 java堆没学呢
5838.检查字符串是否为数组前缀
https://leetcode-cn.com/problems/check-if-string-is-a-prefix-of-array/
难度：简单
题目
给你一个字符串 s 和一个字符串数组 words ，请你判断 s 是否为 words 的 前缀字符串 。
字符串 s 要成为 words 的 前缀字符串 ，需要满足：s 可以由 words 中的前 k（k 为 正数 ）个字符串按顺序相连得到，且 k 不超过 words.length 。
如果 s 是 words 的 前缀字符串 ，返回 true ；否则，返回 false 。
提示：
- 1 <= words.length <= 100
- 1 <= words[i].length <= 20
- 1 <= s.length <= 1000
- words[i] 和 s 仅由小写英文字母组成
示例
示例 1：
输入：s = "iloveleetcode", words = ["i","love","leetcode","apples"]
输出：true
解释：
s 可以由 "i"、"love" 和 "leetcode" 相连得到。
示例 2：
输入：s = "iloveleetcode", words = ["apples","i","love","leetcode"]
输出：false
解释：
数组的前缀相连无法得到 s 。
分析
初始看错题目以为只要数组中的元素能构造出S即可，结果走了一边双端队列，自信提交错误。
结果发现想多了，只需要按照word顺序与s比较即可...是一道简单的字符串检索题目。
这里注意下，当拼接的长度已经比s的长度大，还不能构造s时，就无需再继续操作了，直接返回False节省时间
解题
class Solution:
def isPrefixString(self, s, words):
ret,lg = "",len(s)
for i in words:
ret += i
if ret == s:
return True
elif len(ret) > lg:
return False
return False
class Solution {
public boolean isPrefixString(String s, String[] words) {
String comp = "";
int lg = s.length();
for (String i : words) {
comp += i;
if (comp.equals(s)) {
return true;
} else if (comp.length() > lg) {
return false;
}
}
return false;
}
}
5839.移除石子使总数最小
https://leetcode-cn.com/problems/remove-stones-to-minimize-the-total/
难度：中等
题目
给你一个整数数组 piles ，数组 下标从 0 开始 ，其中 piles[i] 表示第 i 堆石子中的石子数量。另给你一个整数 k ，请你执行下述操作 恰好 k 次：
选出任一石子堆 piles[i] ，并从中 移除 floor(piles[i] / 2) 颗石子。
注意：你可以对 同一堆 石子多次执行此操作。
返回执行 k 次操作后，剩下石子的 最小 总数。
floor(x) 为 小于 或 等于 x 的 最大 整数。（即，对 x 向下取整）。
提示：
- 1 <= piles.length <= 105
- 1 <= piles[i] <= 104
- 1 <= k <= 105
示例
示例 1：
输入：piles = [5,4,9], k = 2
输出：12
解释：可能的执行情景如下：
- 对第 2 堆石子执行移除操作，石子分布情况变成 [5,4,5] 。
- 对第 0 堆石子执行移除操作，石子分布情况变成 [3,4,5] 。
剩下石子的总数为 12 。
示例 2：
输入：piles = [4,3,6,7], k = 3
输出：12
解释：可能的执行情景如下：
- 对第 2 堆石子执行移除操作，石子分布情况变成 [4,3,3,7] 。
- 对第 3 堆石子执行移除操作，石子分布情况变成 [4,3,3,4] 。
- 对第 0 堆石子执行移除操作，石子分布情况变成 [2,3,3,4] 。
剩下石子的总数为 12 。
分析
这是一道基础的堆排序问题.
但由于python没有大根堆，需要将其转化为小根堆后再进行计算即可。
类似题目：
解题
import heapq
class Solution():
def minStoneSum(self, piles, k):
piles = [-i for i in piles]
heapq.heapify(piles)
while k:
p = heapq.heappop(piles)
heapq.heappush(piles, p + (-p // 2))
k -= 1
return -sum(piles)
5840.使字符串平衡的最小交换次数
难度：中等
题目
给你一个字符串 s ，下标从 0 开始 ，且长度为偶数 n 。字符串 恰好 由 n / 2 个开括号 '[' 和 n / 2 个闭括号 ']' 组成。
只有能满足下述所有条件的字符串才能称为 平衡字符串 ：
- 字符串是一个空字符串，或者
- 字符串可以记作 AB ，其中 A 和 B 都是 平衡字符串 ，或者
- 字符串可以写成 [C] ，其中 C 是一个 平衡字符串 。
你可以交换 任意 两个下标所对应的括号 任意 次数。
返回使 s 变成 平衡字符串 所需要的 最小 交换次数。
提示：
- n == s.length
- 2 <= n <= 10^6
- n 为偶数
- s[i] 为'[' 或 ']'
- 开括号 '[' 的数目为 n / 2 ，闭括号 ']' 的数目也是 n / 2
示例
示例 1：
输入：s = "][]["
输出：1
解释：交换下标 0 和下标 3 对应的括号，可以使字符串变成平衡字符串。
最终字符串变成 "[[]]" 。
示例 2：
输入：s = "]]][[["
输出：2
解释：执行下述操作可以使字符串变成平衡字符串：
- 交换下标 0 和下标 4 对应的括号，s = "[]][[]" 。
- 交换下标 1 和下标 5 对应的括号，s = "[[][]]" 。
最终字符串变成 "[[][]]" 。
示例 3：
输入：s = "[]"
输出：0
解释：这个字符串已经是平衡字符串。
分析
我们需要了解一个关键点，什么时候需要调整顺序：
- 当循环s[i]点时，所有右括号的数量大于左括号时，才需要调整。
知道了这点就可以轻松解题了！
- 循环字符串s
- 记录左括号l和有括号r的大小
- 当s[i]为左括号，l无脑+1
- 当s[i]为右括号，需要判断当前r是否大于等于l，
- 如果r > l: l+1,同时ret+1
- 否则r+1
- 最终返回ret
解题
class Solution:
def minSwaps(self, s):
ret = 0
l = r = 0
for i in s:
if i == '[':
l += 1
else:
if l <= r:
l += 1
ret += 1
else:
r += 1
return ret
class Solution {
public int minSwaps(String s) {
int l = 0;
int r = 0;
int ret = 0;
for (int i = 0; i < s.length(); i++) {
if (s.charAt(i) == '[') {
l++;
} else {
if (l <= r) {
l++;
ret++;
} else {
r++;
}
}
}
return ret;
}
}
欢迎关注我的公众号: 清风Python，带你每日学习Python算法刷题的同时，了解更多python小知识。
我的个人博客：https://qingfengpython.cn
