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; } }
