贪心（Greedy Algorithm）

贪心44.通配符匹配45.跳跃游戏 II55.跳跃游戏122.买卖股票的最佳时机II134.加油站135.分发糖果179.最大数277.搜寻名人280.摆动排序★316.去除重复字母321.拼接最大数330.按要求补齐数组334.递增的三元子序列358.K距离间隔重排字符串376.摆动序列397.整数替换[402.移掉 K 位数字](https://leetcode-/problems/remove-k-digits/)406.根据身高重建队列409.最长回文串410.分割数组的最大值420.强密码检验器[435. 无重叠区间](/problems/non-overlapping-intervals/)452.用最少数量的箭引爆气球455.分发饼干484. 寻找排列502. IPO517.超级洗衣机527. 单词缩写555. 分割连接字符串561. 数组拆分 I581. 最短无序连续子数组605.种花问题611. 有效三角形的个数621. 任务调度器624. 数组列表中的最大距离625. 最小因式分解630. 课程表 III632. 最小区间[646. 最长数对链](/problems/maximum-length-of-pair-chain/)649. Dota2 参议院659. 分割数组为连续子序列670. 最大交换678. 有效的括号字符串680. 验证回文字符串 Ⅱ714. 买卖股票的最佳时机含手续费738.单调递增的数字757. 设置交集大小至少为2763. 划分字母区间765. 情侣牵手767. 重构字符串768. 最多能完成排序的块 II769. 最多能完成排序的块781.森林中的兔子807. 保持城市天际线826. 安排工作以达到最大收益846.一手顺子857. 雇佣 K 名工人的最低成本★860.柠檬水找零861. 翻转矩阵后的得分870. 优势洗牌871.最低加油次数881.救生艇910. 最小差值 II921. 使括号有效的最少添加936. 戳印序列942. 增减字符串匹配945. 使数组唯一的最小增量948. 令牌放置954. 二倍数对数组955. 删列造序 II969. 煎饼排序976. 三角形的最大周长984.不含AAA或BBB的字符串991. 坏了的计算器1005. K 次取反后最大化的数组和1007. 行相等的最少多米诺旋转1011. 在 D 天内送达包裹的能力1013. 将数组分成和相等的三个部分1024. 视频拼接1029. 两地调度1053. 交换一次的先前排列1054. 距离相等的条形码1055. 形成字符串的最短路径1057. 校园自行车分配1058. 最小化舍入误差以满足目标1081. 不同字符的最小子序列1090. 受标签影响的最大值1121. 将数组分成几个递增序列1130. 叶值的最小代价生成树1144. 递减元素使数组呈锯齿状1147. 段式回文1167. 连接棒材的最低费用1183. 矩阵中 1 的最大数量1196. 最多可以买到的苹果数量1199. 建造街区的最短时间1217.玩筹码1221. 分割平衡字符串1247. 交换字符使得字符串相同1253. 重构 2 行二进制矩阵1262. 可被三整除的最大和1296. 划分数组为连续数字的集合1323. 6 和 9 组成的最大数字1326. 灌溉花园的最少水龙头数目1328. 破坏回文串1330. 翻转子数组得到最大的数组值1338. 数组大小减半1353. 最多可以参加的会议数目1363. 形成三的最大倍数1382. 将二叉搜索树变平衡1383. 最大的团队表现值1386. 安排电影院座位1388. 3n 块披萨1400. 构造 K 个回文字符串1402. 做菜顺序1403. 非递增顺序的最小子序列1405. 最长快乐字符串1414. 和为 K 的最少斐波那契数字数目1432. 改变一个整数能得到的最大差值1433. 检查一个字符串是否可以打破另一个字符串1465. 切割后面积最大的蛋糕1481. 不同整数的最少数目1488. 避免洪水泛滥1505. 最多 K 次交换相邻数位后得到的最小整数1509. 三次操作后最大值与最小值的最小差1520. 最多的不重叠子字符串1526. 形成目标数组的子数组最少增加次数1529. 最少的后缀翻转次数1536. 排布二进制网格的最少交换次数1537. 最大得分1541. 平衡括号字符串的最少插入次数1546. 和为目标值且不重叠的非空子数组的最大数目1558. 得到目标数组的最少函数调用次数1561. 你可以获得的最大硬币数目1564. 把箱子放进仓库里 I1567. 乘积为正数的最长子数组长度1578. 使绳子变成彩色的最短时间1580. 把箱子放进仓库里 II1585. 检查字符串是否可以通过排序子字符串得到另一个字符串1589. 所有排列中的最大和1605. 给定行和列的和求可行矩阵1606. 找到处理最多请求的服务器1616. 分割两个字符串得到回文串1632. 矩阵转换后的秩1642. 可以到达的最远建筑1647. 字符频次唯一的最小删除次数1648. 销售价值减少的颜色球1663. 具有给定数值的最小字符串1665. 完成所有任务的最少初始能量1671. 得到山形数组的最少删除次数1673. 找出最具竞争力的子序列1675. 数组的最小偏移量1686. 石子游戏 VI1689. 十-二进制数的最少数目1702. 修改后的最大二进制字符串1703. 得到连续 K 个 1 的最少相邻交换次数1705. 吃苹果的最大数目1708. 长度为 K 的最大子数组1710. 卡车上的最大单元数1713. 得到子序列的最少操作次数1717. 删除子字符串的最大得分1727. 重新排列后的最大子矩阵1733. 需要教语言的最少人数1739. 放置盒子1753. 移除石子的最大得分1754. 构造字典序最大的合并字符串1764. 通过连接另一个数组的子数组得到一个数组1775. 通过最少操作次数使数组的和相等1785. 构成特定和需要添加的最少元素1788. 最大化花园的美观度1792. 最大平均通过率1794. 统计距离最小的子串对个数1798. 你能构造出连续值的最大数目1802. 有界数组中指定下标处的最大值1824. 最少侧跳次数1827. 最少操作使数组递增1833. 雪糕的最大数量1846. 减小和重新排列数组后的最大元素1850. 邻位交换的最小次数1855. 下标对中的最大距离1864. 构成交替字符串需要的最小交换次数1874. 两个数组的最小乘积和1877. 数组中最大数对和的最小值1881. 插入后的最大值1888. 使二进制字符串字符交替的最少反转次数1899. 合并若干三元组以形成目标三元组1903. 字符串中的最大奇数1921. 消灭怪物的最大数量1927. 求和游戏1936. 新增的最少台阶数1946. 子字符串突变后可能得到的最大整数1953. 你可以工作的最大周数1963. 使字符串平衡的最小交换次数1968. 构造元素不等于两相邻元素平均值的数组1969. 数组元素的最小非零乘积1974. 使用特殊打字机键入单词的最少时间1975. 最大方阵和1996.游戏中弱角色的数量. 从双倍数组中还原原数组. 重复 K 次的最长子序列. 每段建筑物的平均高度2027. 转换字符串的最少操作次数2029. 石子游戏 IX2030. 含特定字母的最小子序列2038. 如果相邻两个颜色均相同则删除当前颜色2071. 你可以安排的最多任务数目2078. 两栋颜色不同且距离最远的房子2086. 从房屋收集雨水需要的最少水桶数2087. 网格图中机器人回家的最小代价2091. 从数组中移除最大值和最小值2098. 长度为 K 的最大偶数和子序列2116. 判断一个括号字符串是否有效2126. 摧毁小行星2131. 连接两字母单词得到的最长回文串2132. 用邮票贴满网格图2136.全部开花的最早一天2139.得到目标值的最少行动次数2141.同时运行N台电脑的最长时间2144.打折购买糖果的最小开销2160.拆分数位后四位数字的最小和2170.使数组变成交替数组的最少操作数2178.拆分成最多数目的正偶数之和2182.构造限制重复的字符串2193.得到回文串的最少操作次数[2195.向数组中追加 K 个整数](https://leetcode-/problems/append-k-integers-with-minimal-sum/)[2202.K 次操作后最大化顶端元素](https://leetcode-/problems/maximize-the-topmost-element-after-k-moves/)2207.字符串中最多数目的子字符串2216.美化数组的最少删除数

贪心

贪心算法（又称贪婪算法 Greedy algorithm）是指，在对问题求解时，总是做出在当前看来是最好的选择。也就是说，不从整体最优上加以考虑，他所做出的仅是在某种意义上的局部最优解。贪心算法不是对所有问题都能得到整体最优解，但对范围相当广泛的许多问题他能产生整体最优解或者是整体最优解的近似解，所以贪心算法不要回溯。

44.通配符匹配

45.跳跃游戏 II

55.跳跃游戏

122.买卖股票的最佳时机II

134.加油站

class Solution:def canCompleteCircuit(self, gas: List[int], cost: List[int]) -> int:# 如果总油量 < 总消耗，则不达。# 从 start 出发，当前油量 cur 从 0 计起，如果 cur < 0，说明无法到达下一站，需要从下一站重新开始。# total 计总剩余油量 n = len(cost)cur = total = start = 0for i in range(n): cur += gas[i] - cost[i] if cur < 0:start = i + 1total += curcur = 0total += cur # 一圈下来总剩余return start if total >= 0 else -1

class Solution {public int canCompleteCircuit(int[] gas, int[] cost) {int total = 0, cur = 0, start = 0;for (int i = 0; i < gas.length; i++){cur += gas[i] - cost[i];if (cur < 0){total += cur;start = i + 1;cur = 0;}}return total + cur < 0 ? -1 : start;}}

135.分发糖果

class Solution:def candy(self, ratings: List[int]) -> int:n = len(ratings)left = [1] * nfor i in range(1, n):if ratings[i] > ratings[i - 1]: left[i] = left[i - 1] + 1right, ans = 1, left[-1]for i in range(n - 2, -1, -1):if ratings[i] > ratings[i + 1]: right += 1else: right = 1ans += max(left[i], right) return ansclass Solution:def candy(self, ratings: List[int]) -> int:n, ans, inc, dec, pre = len(ratings), 1, 1, 0, 1for i in range(1, n):if ratings[i] >= ratings[i - 1]:dec = 0pre = 1 if ratings[i] == ratings[i - 1] else pre + 1ans += preinc = preelse:dec += 2 if inc - dec == 1 else 1ans += decpre = 1 return ans

class Solution {public int candy(int[] ratings) {int n = ratings.length, ans = 1, inc = 1, dec = 0, pre = 1;for(int i = 1; i < n; i++){if (ratings[i] < ratings[i-1]){dec += inc - dec == 1 ? 2 : 1;ans += dec;pre = 1;} else {dec = 0;pre = ratings[i] == ratings[i-1] ? 1 : pre + 1; ans += pre;inc = pre;}}return ans;}}

179.最大数

class Solution:def largestNumber(self, nums: List[int]) -> str:n = len(nums)s = map(str, nums) # s = sorted(map(str, nums), reverse=True)# for i in range(n - 1):#for j in range(i + 1, n):# if s[i] + s[j] < s[j] + s[i]:# s[i], s[j] = s[j], s[i]## lambda# s = sorted(s, key=cmp_to_key(lambda x, y: 1 if x+y < y+x else -1))## 自定义函数 from functools import cmp_to_key def cmp(a, b):if a + b < b + a: return 1else: return -1s = sorted(s, key=cmp_to_key(cmp))return ''.join(s) if s[0] != '0' else '0'

class Solution {public String largestNumber(int[] nums) {int n = nums.length;String s[] = new String[n];for(int i = 0; i < n; i++) s[i] = String.valueOf(nums[i]); // compareTo() 方法比较的时候是按照 ASCII 码逐位比较的// 通过比较 (a + b) 和 (b + a) 的大小，就可以判断出 a, b 两个字符串谁应该在前面// 所以 [3, 30, 34] 排序后变为 [34, 3, 30]// [233，23333] 排序后变为 [23333，233]Arrays.sort(s, (a, b) -> {return (b + a).compareTo(a + b);});// 排序后的第一个元素是 0，后面的元素肯定等于 0return s[0].equals("0") ? "0" : String.join("", s);}}

277.搜寻名人

Leetcode

class Solution:def findCelebrity(self, n: int) -> int:# 筛选候选人 candidatec = 0for i in range(1, n):if knows(c, i): # c 不是,否则 i 不是c = i# 检查候选人for i in range(n):if i != c and (not knows(i, c) or knows(c, i)):return -1return c# for a in range(n):#for b in range(n):# if a != b and knows(a, b) or not knows(b, a): break#else:# return a# return -1

public class Solution extends Relation {public int findCelebrity(int n) {int c = 0; // 筛选候选人 candidatefor (int i = 1; i < n; i++){if (knows(c, i)) c = i; // c 不是,否则 i 不是} for (int i = 0; i < n; i++){// 检查候选人if (i != c && (!knows(i, c) || knows(c, i))) return -1;}return c;}}

280.摆动排序

★316.去除重复字母

剩余单一字母，确定位置后，它前面的字母不再改变。每添加一个字母循环判断是否小于前一个字母，如果小于并且前一字符还有剩余，也就是后面还有，则删除前一字符。

class Solution:def removeDuplicateLetters(self, s: str) -> str:q, d, v = [], defaultdict(int), set()for c in s: d[c] += 1for c in s:if c not in v: # c not in q:while q and q[-1] > c and d[q[-1]]:# 前一个字符后面还有并且比较大，删除。v.remove(q.pop())q.append(c)v.add(c)d[c] -= 1return ''.join(q)

class Solution {public String removeDuplicateLetters(String s) {int[] cnt = new int[26];boolean[] vis = new boolean[26];char[] t = s.toCharArray();StringBuilder sb = new StringBuilder(); // 模拟栈for (char c : t) cnt[c-'a']++;for (char c : t) {// if (sb.indexOf(String.valueOf(c)) == -1){if (!vis[c-'a']){int i = sb.length() - 1;while (i >= 0 && sb.charAt(i) > c && cnt[sb.charAt(i)-'a'] > 0){vis[sb.charAt(i)-'a'] = false;sb.deleteCharAt(i--);}sb.append(c);vis[c-'a'] = true;}cnt[c-'a']--;}return sb.toString();}}

321.拼接最大数

330.按要求补齐数组

334.递增的三元子序列

可以使用贪心的方法将空间复杂度降到 O(1)。从左到右遍历数组 nums，遍历过程中维护两个变量 first 和 second，分别表示递增的三元子序列中的第一个数和第二个数，任何时候都有 first < second。

贪心思想是：为了找到递增的三元子序列，first 和 second 应该尽可能地小，此时找到递增的三元子序列的可能性更大。

如果遍历过程中遇到小于 first 的元素，则会用该元素更新 first，虽然更新后的 first 出现在 second 的后面，但是在 second 的前面一定存在一个元素 first’ 小于 second，因此当遇到 num > second 时，(first’,second,num) 即为递增的三元子序列。

class Solution:def increasingTriplet(self, nums: List[int]) -> bool:first, second = nums[0], inf # +∞# [2,1,5,0,4,6] first = 2, 1, 0 second = +∞ 5, 当 first = 0 时，0 在 second 后边，但 前边有一个 1 或 2for x in nums:if x > second: return True # first 始终小于 second 只要找到 x > second, 就找到一个解。 if x > first: second = x # 比 first 大，更新 secondelse: first = x# 更新 first return False

class Solution {public boolean increasingTriplet(int[] nums) {int first = nums[0], second = Integer.MAX_VALUE;for (int n : nums){if (n > second) return true;if (n > first) second = n;else first = n;}return false;}}

358.K距离间隔重排字符串

376.摆动序列

397.整数替换

class Solution:def integerReplacement(self, n: int) -> int:# ans = 0# while n != 1:# if n % 2 == 0:# ans += 1# n //= 2# elif n % 4 == 1:# ans += 2# n //= 2# else:# if n == 3:# ans += 2# n = 1# else:# ans += 2# n = n // 2 + 1# return ans# @lru_cache(None)def x(n):if n <= 3: return n - 1if n & 1 == 0: return 1 + x(n >> 1)# if n & 4 == 1:#return 3 + x((n - 1) >> 2)return 3 + x((n + 1) >> 2)return x(n)# count = 0# while n != 1: # if n & 1: # n += -1 if (n & 2) == 0 or n == 3 else 1# else: n >>= 1# count += 1# return count

402.移掉 K 位数字

class Solution(object):def removeKdigits(self, num, k):stack, remain = [], len(num) - kfor digit in num:while k and stack and stack[-1] > digit:stack.pop()k -= 1stack.append(digit) return ''.join(stack[:remain]).lstrip('0') or '0'

class Solution {public String removeKdigits(String num, int k) {int n = num.length(), r = n - k, m = 0;if(k >= n) return "0"; // 全部删除直接返回 "0" StringBuilder stack = new StringBuilder(); // 模拟栈for(char c : num.toCharArray()){while (m > 0 && k > 0 && stack.charAt(m - 1) > c){stack.deleteCharAt(m - 1); m--; k--; }stack.append(c); m++; // 记录 stack.length()} String res = stack.toString().substring(0, r);int i = 0; for (;i < res.length(); i++)if(res.charAt(i) != '0') break;return i == res.length() ? "0" : res.substring(i);}}

406.根据身高重建队列

409.最长回文串

410.分割数组的最大值

420.强密码检验器

435. 无重叠区间

class Solution:def eraseOverlapIntervals(self, intervals: List[List[int]]) -> int:intervals.sort(key=lambda x:x[1])ans = len(intervals)last = -inffor a, b in intervals:if a >= last:ans -= 1last = breturn ans

452.用最少数量的箭引爆气球

class Solution:def findMinArrowShots(self, points: List[List[int]]) -> int:points.sort()n = len(points)mn = points[0][1]ans = 1 for i, (a, b) in enumerate(points):if mn >= a:mn = min(mn, b)else:ans += 1mn = breturn ans

class Solution {public int findMinArrowShots(int[][] points) {// 贪心法, 按照右端点排序, 每次从最小的右端点射出一支箭. Arrays.sort(points, (a, b) -> pare(a[1], b[1]));int ans = 1, axis = points[0][1]; for(int[] p : points) {if(axis < p[0]) {ans++;axis = p[1];}} return ans;}}

455.分发饼干

class Solution:def findContentChildren(self, g: List[int], s: List[int]) -> int:g.sort()s.sort()ans, i, j = 0, 0, 0while i < len(g) and j < len(s):if s[j] >= g[i]:i += 1j += 1ans += 1else: j += 1 return ans

class Solution {public int findContentChildren(int[] g, int[] s) {Arrays.sort(g);Arrays.sort(s);int i = 0, j = 0, ans = 0;while (i < s.length && j < g.length){if (s[i] >= g[j]){i++;j++;ans++;} else i++; }return ans;}}

484. 寻找排列

502. IPO

517.超级洗衣机

class Solution:def findMinMoves(self, machines: List[int]) -> int: res = s = 0 ave, rem = divmod(sum(machines), len(machines))if rem: return -1# 找前 i 个总需求的次数和单个需要移除次数的最大值for v in machines:d = v - aves += dres = max(res, d, abs(s)) return res

class Solution {public int findMinMoves(int[] machines) {int sum = 0, max = 0, d = 0, n = machines.length, ans = -1, pre = 0;for (int x : machines) sum += x;if (sum % n != 0) return -1;int ave = sum / n;for (int x : machines){d = x - ave;pre += d;ans = Math.max(ans, Math.max(Math.abs(pre), d));}return ans;}}

527. 单词缩写

555. 分割连接字符串

561. 数组拆分 I

581. 最短无序连续子数组

605.种花问题

class Solution:def canPlaceFlowers(self, flowerbed: List[int], n: int) -> bool:m, prev = len(flowerbed), -2# 分四种情况 0 … 0, 1 0 …, 0 … 1, 1 0 … 1for i in range(m):if flowerbed[i]:n -= (i - prev - 2) // 2prev = i if prev < 0: # 第一种n -= (m + 1) // 2else: n -= (m - prev - 1) // 2 return n <= 0

class Solution {public boolean canPlaceFlowers(int[] flowerbed, int n) {int m = flowerbed.length, prev = -2;for (int i = 0; i < m; i++){if (flowerbed[i] == 1){n -= (i - prev - 2) / 2;prev = i;}}if (prev < 0) n -= (m + 1) / 2;else n -= (m - prev - 1) / 2;return n <= 0;}}

611. 有效三角形的个数

621. 任务调度器

624. 数组列表中的最大距离

625. 最小因式分解

630. 课程表 III

632. 最小区间

646. 最长数对链

同 435. 无重叠区间

class Solution:def findLongestChain(self, pairs: List[List[int]]) -> int:# 贪心 b 尽可能的小，按 b 排序pairs.sort(key=lambda x:x[1])last = -infans = 0for a, b in pairs:if a > last:ans += 1last = breturn ans# 动规n = len(pairs) pairs.sort()dp = [1] * nfor i in range(n):for j in range(i - 1, -1, -1):if pairs[i][0] > pairs[j][1]: dp[i] = max(dp[i], dp[j] + 1)return dp[-1]

649. Dota2 参议院

659. 分割数组为连续子序列

670. 最大交换

678. 有效的括号字符串

680. 验证回文字符串 Ⅱ

714. 买卖股票的最佳时机含手续费

738.单调递增的数字

class Solution:def monotoneIncreasingDigits(self, n: int) -> int: if n == 0: return 0arr = list(map(int, str(n)))m = len(arr)for i in range(m - 1):if arr[i] > arr[i + 1]:while i > 0 and arr[i] == arr[i - 1]: i -= 1arr[i] -= 1for j in range(i + 1, m): arr[j] = 9breakreturn int(''.join(map(str, arr)))# ones = 111111111# res = 0# for _ in range(9):#while res + ones > n:# ones //= 10#res += ones# return res

class Solution {public int monotoneIncreasingDigits(int n) {char[] s = String.valueOf(n).toCharArray();int i = 1;while (i < s.length && s[i - 1] <= s[i]) i += 1; if (i < s.length) {while (i > 0 && s[i - 1] > s[i]) s[--i]--;Arrays.fill(s, ++i, s.length, '9');}return Integer.parseInt(new String(s));}}

757. 设置交集大小至少为2

763. 划分字母区间

765. 情侣牵手

767. 重构字符串

768. 最多能完成排序的块 II

769. 最多能完成排序的块

781.森林中的兔子

class Solution:def numRabbits(self, answers: List[int]) -> int:n, ans = len(answers), 0cnt = Counter(answers)for k, v in cnt.items():ans += (v + k) // (k + 1) * (k + 1)#ans += ceil(v/(k+1)) * (k + 1)return ans

class Solution {public int numRabbits(int[] answers) {int ans = 0;Map<Integer, Integer> map = new HashMap<>();for (int x : answers) map.put(x, map.getOrDefault(x, 0) + 1); for (Map.Entry<Integer, Integer> entry : map.entrySet()) {int k = entry.getKey(), v = entry.getValue();ans += (k + v) / (k + 1) * (k + 1);} return ans;}}

807. 保持城市天际线

826. 安排工作以达到最大收益

846.一手顺子

class Solution:def isNStraightHand(self, hand: List[int], groupSize: int) -> bool:if len(hand) % groupSize: return Falsehand.sort()cnt = Counter(hand)for h in hand:if cnt[h] == 0: continuefor num in range(h, h + groupSize):if cnt[num] == 0: return Falsecnt[num] -= 1return True

class Solution {public boolean isNStraightHand(int[] hand, int groupSize) {if (hand.length % groupSize != 0) return false;Arrays.sort(hand);Map<Integer, Integer> map = new HashMap<Integer, Integer>();for (int h: hand){map.put(h, map.getOrDefault(h, 0) + 1);}for (int h: hand){// if (!map.containsKey(h)) continue;// for (int j = h; j < h + groupSize; j++){//if (!map.containsKey(j)) return false;//map.put(j, map.get(j) - 1);//if (map.get(j) == 0) map.remove(j);// }if (map.get(h) == 0) continue;for (int j = h; j < h + groupSize; j++){if (map.get(j) == null || map.get(j) == 0) return false;map.put(j, map.get(j) - 1);}}return true;}}

857. 雇佣 K 名工人的最低成本

★860.柠檬水找零

知识点：boolean, int[], For-Each, if else, switch case break

class Solution:def lemonadeChange(self, bills: List[int]) -> bool:five, ten = 0, 0for i in bills:if i == 5: five += 1elif i == 10:ten += 1five -= 1elif i == 20:if ten > 0: # 先找 10 元的ten -= 1; five -= 1else: five -= 3if five < 0: return Falsereturn True

class Solution {public boolean lemonadeChange(int[] bills) {int five = 0, ten = 0;for (int i : bills){if (i == 5) five += 1;else if (i == 10){ten++; five--; } else if (i == 20){if (ten > 0){// 先找 10 元的ten--;five--;} else five -= 3;}if (five < 0) return false;// switch(i){//case 5:// five++;// break;//case 10:// ten++;// five--;// break;//case 20:// if(ten > 0){// ten--;// five--;// }// else five -= 3;//default :// }// if(five < 0) return false;}return true;}}

861. 翻转矩阵后的得分

870. 优势洗牌

871.最低加油次数

class Solution:def minRefuelStops(self, target: int, startFuel: int, stations: List[List[int]]) -> int:pq = [] stations.append((target, inf))ans = pre = 0# 边走边把加油站一带上，可笑吧！for dis, oil in stations:startFuel += pre - diswhile pq and startFuel < 0: # 说明前面需要加油，当然是按最多的先加。startFuel += -heapq.heappop(pq)ans += 1if startFuel < 0: return -1heapq.heappush(pq, -oil)pre = disreturn ans

class Solution {public int minRefuelStops(int target, int startFuel, int[][] stations) {Queue<Integer> pq = new PriorityQueue<>(Collections.reverseOrder());int i = 0, res = 0, n = stations.length;for (; startFuel < target; res++) {while (i < n && stations[i][0] <= startFuel)pq.offer(stations[i++][1]);if (pq.isEmpty()) return -1;startFuel += pq.poll();}return res;}}

881.救生艇

class Solution:def numRescueBoats(self, people: List[int], limit: int) -> int:n = len(people)people.sort()i, j = 0, n - 1while i < j: if people[i] + people[j] <= limit:i += 1 # 二人同舟j -= 1 # 单独或二人 return n - i

class Solution {public int numRescueBoats(int[] people, int limit) {int n = people.length;Arrays.sort(people);int i = 0, j = n - 1;while (i < j){if (people[i] + people[j] <= limit) i++;j--;}return n - i;}}

910. 最小差值 II

921. 使括号有效的最少添加

936. 戳印序列

942. 增减字符串匹配

945. 使数组唯一的最小增量

948. 令牌放置

954. 二倍数对数组

955. 删列造序 II

969. 煎饼排序

976. 三角形的最大周长

984.不含AAA或BBB的字符串

class Solution:def strWithout3a3b(self, a: int, b: int) -> str:ans = list()k = 0while a or b:if k > 1 and ans[-1] == ans[-2]:writeA = ans[-1] == 'b'else: writeA = a >= bk += 1if writeA:a -= 1; c = 'a'else:b -= 1; c = 'b'ans.append(c)return "".join(ans)

class Solution {public String strWithout3a3b(int a, int b) {StringBuilder sb = new StringBuilder();int k = -1;boolean flag = false;while (a > 0 || b > 0){if (k > 0 && sb.charAt(k) == sb.charAt(k - 1)){flag = sb.charAt(k) == 'b';} else flag = a >= b;if (flag) {sb.append('a'); a--;} else {sb.append('b');b--;} k++;}return sb.toString();}}

991. 坏了的计算器

1005. K 次取反后最大化的数组和

1007. 行相等的最少多米诺旋转

1011. 在 D 天内送达包裹的能力

1013. 将数组分成和相等的三个部分

1024. 视频拼接

1029. 两地调度

1053. 交换一次的先前排列

1054. 距离相等的条形码

1055. 形成字符串的最短路径

1057. 校园自行车分配

1058. 最小化舍入误差以满足目标

1081. 不同字符的最小子序列

1090. 受标签影响的最大值

1121. 将数组分成几个递增序列

1130. 叶值的最小代价生成树

1144. 递减元素使数组呈锯齿状

1147. 段式回文

1167. 连接棒材的最低费用

1183. 矩阵中 1 的最大数量

1196. 最多可以买到的苹果数量

1199. 建造街区的最短时间

1217.玩筹码

第 i 个芯片的位置是 position[i]，注意不是筹码数。

知识点：for, %, Math.min(), ++

class Solution:def minCostToMoveChips(self, position: List[int]) -> int: # odd = even = 0# for k in position:#if k % 2: odd += 1#else: even += 1# return min(even, odd)# d = [0, 0]# for i in position: d[i%2] += 1# return min(d)return min(x := sum(i & 1 for i in position), len(position) - x)

class Solution {public int minCostToMoveChips(int[] position) {int a = 0, b = 0;// for (int i: position){//if (i % 2 == 0) a++;//else b++;// }// return Math.min(a, b);int x = 0;for (int i : position) {if (i % 2 == 0) x++;}return Math.min(x, position.length - x);// int[] res = {0, 0};// for (int i : position) res[i & 1]++;// return Math.min(res[0], res[1]);}}

1221. 分割平衡字符串

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

1253. 重构 2 行二进制矩阵

1262. 可被三整除的最大和

1296. 划分数组为连续数字的集合

1323. 6 和 9 组成的最大数字

1326. 灌溉花园的最少水龙头数目

1328. 破坏回文串

1330. 翻转子数组得到最大的数组值

1338. 数组大小减半

1353. 最多可以参加的会议数目

1363. 形成三的最大倍数

1382. 将二叉搜索树变平衡

1383. 最大的团队表现值

1386. 安排电影院座位

1388. 3n 块披萨

1400. 构造 K 个回文字符串

1402. 做菜顺序

1403. 非递增顺序的最小子序列

1405. 最长快乐字符串

1414. 和为 K 的最少斐波那契数字数目

1432. 改变一个整数能得到的最大差值

1433. 检查一个字符串是否可以打破另一个字符串

1465. 切割后面积最大的蛋糕

1481. 不同整数的最少数目

1488. 避免洪水泛滥

1505. 最多 K 次交换相邻数位后得到的最小整数

1509. 三次操作后最大值与最小值的最小差

1520. 最多的不重叠子字符串

1526. 形成目标数组的子数组最少增加次数

1529. 最少的后缀翻转次数

1536. 排布二进制网格的最少交换次数

1537. 最大得分

1541. 平衡括号字符串的最少插入次数

1546. 和为目标值且不重叠的非空子数组的最大数目

1558. 得到目标数组的最少函数调用次数

1561. 你可以获得的最大硬币数目

1564. 把箱子放进仓库里 I

1567. 乘积为正数的最长子数组长度

1578. 使绳子变成彩色的最短时间

1580. 把箱子放进仓库里 II

1585. 检查字符串是否可以通过排序子字符串得到另一个字符串

1589. 所有排列中的最大和

1605. 给定行和列的和求可行矩阵

1606. 找到处理最多请求的服务器

1616. 分割两个字符串得到回文串

1632. 矩阵转换后的秩

1642. 可以到达的最远建筑

1647. 字符频次唯一的最小删除次数

1648. 销售价值减少的颜色球

1663. 具有给定数值的最小字符串

1665. 完成所有任务的最少初始能量

1671. 得到山形数组的最少删除次数

1673. 找出最具竞争力的子序列

1675. 数组的最小偏移量

1686. 石子游戏 VI

1689. 十-二进制数的最少数目

1702. 修改后的最大二进制字符串

1703. 得到连续 K 个 1 的最少相邻交换次数

1705. 吃苹果的最大数目

1708. 长度为 K 的最大子数组

1710. 卡车上的最大单元数

1713. 得到子序列的最少操作次数

1717. 删除子字符串的最大得分

1727. 重新排列后的最大子矩阵

1733. 需要教语言的最少人数

1739. 放置盒子

1753. 移除石子的最大得分

1754. 构造字典序最大的合并字符串

1764. 通过连接另一个数组的子数组得到一个数组

1775. 通过最少操作次数使数组的和相等

1785. 构成特定和需要添加的最少元素

1788. 最大化花园的美观度

1792. 最大平均通过率

1794. 统计距离最小的子串对个数

1798. 你能构造出连续值的最大数目

1802. 有界数组中指定下标处的最大值

1824. 最少侧跳次数

1827. 最少操作使数组递增

1833. 雪糕的最大数量

1846. 减小和重新排列数组后的最大元素

1850. 邻位交换的最小次数

1855. 下标对中的最大距离

1864. 构成交替字符串需要的最小交换次数

1874. 两个数组的最小乘积和

1877. 数组中最大数对和的最小值

1881. 插入后的最大值

1888. 使二进制字符串字符交替的最少反转次数

1899. 合并若干三元组以形成目标三元组

1903. 字符串中的最大奇数

1921. 消灭怪物的最大数量

1927. 求和游戏

1936. 新增的最少台阶数

1946. 子字符串突变后可能得到的最大整数

1953. 你可以工作的最大周数

1963. 使字符串平衡的最小交换次数

1968. 构造元素不等于两相邻元素平均值的数组

1969. 数组元素的最小非零乘积

1974. 使用特殊打字机键入单词的最少时间

1975. 最大方阵和

1996.游戏中弱角色的数量

记录遍历过的最大的防御力(maxdef)的角色 A，如果当前的角色 B 的防御力小于 maxdef，那么 B 的攻击力一定也小于 A 的攻击力。

class Solution:def numberOfWeakCharacters(self, properties: List[List[int]]) -> int:res = 0properties.sort(key=lambda x: (-x[0], x[1]))maxdef = 0for _, d in properties:if maxdef > d: res += 1else: maxdef = dreturn res

class Solution {public int numberOfWeakCharacters(int[][] properties) {int maxdef = 0, res = 0;Arrays.sort(properties, (o1, o2) -> o1[0] == o2[0] ? o1[1] - o2[1] : o2[0] - o1[0]);for (int[] role : properties){if (maxdef > role[1]) res ++;else maxdef = role[1];}return res;}}

. 从双倍数组中还原原数组

. 重复 K 次的最长子序列

. 每段建筑物的平均高度

2027. 转换字符串的最少操作次数

2029. 石子游戏 IX

2030. 含特定字母的最小子序列

2038. 如果相邻两个颜色均相同则删除当前颜色

2071. 你可以安排的最多任务数目

2078. 两栋颜色不同且距离最远的房子

2086. 从房屋收集雨水需要的最少水桶数

2087. 网格图中机器人回家的最小代价

2091. 从数组中移除最大值和最小值

2098. 长度为 K 的最大偶数和子序列

2116. 判断一个括号字符串是否有效

2126. 摧毁小行星

2131. 连接两字母单词得到的最长回文串

2132. 用邮票贴满网格图

2136.全部开花的最早一天

2139.得到目标值的最少行动次数

class Solution:def minMoves(self, target: int, maxDoubles: int) -> int:res = 0while target > 1:if maxDoubles == 0 : res += target - 1break if target % 2 == 1: target -= 1else:target = target // 2maxDoubles -= 1res += 1return res

class Solution {public int minMoves(int target, int maxDoubles) {int res = 0;while (target > 1){if (maxDoubles == 0){res += target -1;break;}if (target % 2 == 1) target--;else {target /= 2;maxDoubles--; }res++;}return res;}}

2141.同时运行N台电脑的最长时间

class Solution:def maxRunTime(self, n: int, batteries: List[int]) -> int:batteries = sorted(batteries, reverse=True)s = sum(batteries)for t in batteries :if t > s // n :n -= 1s -= telse :return s // n

2144.打折购买糖果的最小开销

class Solution:def minimumCost(self, cost: List[int]) -> int:# 逆序cost.sort(reverse = True)s = sum(cost)for i in range(2, len(cost), 3):s -= cost[i]# 正序 # cost.sort()# n, s = len(cost), 0# for i in range(n - 1, -1, -1):#if (n - i) % 3 != 0: s += cost[i]return s# return sum(x for i, x in enumerate(sorted(cost, reverse = True)) if i % 3 != 2)

class Solution {public int minimumCost(int[] cost) {Arrays.sort(cost);int n = cost.length, res = 0; // 逆序遍历，n - i - 1 为逆序的索引，逆序取两个隔一个。for (int i = n - 1; i >= 0; i--){if ((n - i) % 3 != 0) res += cost[i];}return res;}}

2160.拆分数位后四位数字的最小和

class Solution:def minimumSum(self, num: int) -> int:d = []while num:d.append(num % 10)num //= 10d.sort()return 10 * (d[0] + d[1]) + d[2] + d[3]

class Solution {public int minimumSum(int num) {int[] nums = new int[4];for (int i = 0; i < 4; i++){nums[i] = num % 10;num /= 10;}Arrays.sort(nums);return 10 * (nums[0] + nums[1]) + nums[2] + nums[3];}}

2170.使数组变成交替数组的最少操作数

class Solution:def minimumOperations(self, nums: List[int]) -> int: n = len(nums)if n == 1: return 0a, b = Counter(nums[::2]), Counter(nums[1::2])a = sorted(a.items(), key = lambda x: -x[1]) b = sorted(b.items(), key = lambda x: -x[1])if a[0][0] != b[0][0]: # 两个数组中，出现次数最多的元素不同。return n - a[0][1] - b[0][1] # 最多的不变，其它的都需要变。# 保留第一个最多的元素，第二个次多的元素 cost0 = n - a[0][1] - (0 if len(b) == 1 else b[1][1]) cost1 = n - b[0][1] - (0 if len(a) == 1 else a[1][1]) return min(cost0, cost1)

class Solution {public int minimumOperations(int[] nums) {int N = 100010, n = nums.length, a = 0, b = 0, c = 0, d = 0;int[] x = new int[N], y = new int[N];boolean even = true;for (int i : nums) {if (even) {x[i]++;if (x[i] > x[a]) {b = a; a = i;} else if (i != a && x[i] > x[b]) b = i;} else {y[i]++;if (y[i] > y[c]) {d = c; c = i;} else if (i != c && y[i] > y[d]) d = i;}even = !even;}if (a != c) return n - x[a] - y[c];else return n - Math.max(x[a] + y[d], x[b] + y[c]);}}

2178.拆分成最多数目的正偶数之和

class Solution:def maximumEvenSplit(self, finalSum: int) -> List[int]:if finalSum % 2: return []# k * k + k - finalSum <= 0 求 k 的根 k = int((-1 + sqrt(1 + 4 * finalSum)) / 2) res = list(range(2, 2*k+1, 2))res[-1] += finalSum - (k + 1) * k # 前 k 个偶数的和return res

class Solution {public List<Long> maximumEvenSplit(long finalSum) {List<Long> res = new ArrayList<>();if (finalSum % 2 == 1) return res;long x = 0;while (x < finalSum){x += 2;finalSum -= x;res.add(x);}res.set(res.size() - 1, res.get(res.size() - 1) + finalSum);return res;}}

2182.构造限制重复的字符串

class Solution:def repeatLimitedString(self, s: str, repeatLimit: int) -> str:d = defaultdict(int)for c in s: d[c] += 1q, ans = sorted(d.keys()), [] while q:c = q.pop() # 先处理最大的字符k, r = divmod(d[c], repeatLimit)for i in range(k):ans.append(c * repeatLimit) # 当 q 为空时，可直接返回答案；或最后且 r 为 0 时，不再添加分割字符。if not q or i == k-1 and r == 0: breakch = q[-1]ans.append(ch) # 添加分割字符 d[ch] -= 1# 需要维护字符个数if d[ch] == 0: q.pop()else: ans.append(c * r)return ''.join(ans)

class Solution {public String repeatLimitedString(String s, int repeatLimit) {int[] chs = new int[26];StringBuilder sb = new StringBuilder();for (char c : s.toCharArray()) chs[c - 'a']++;for (int i = 25; i >= 0; i--){int k = repeatLimit;while (chs[i]-- > 0 && k-- > 0){sb.append((char)(i + 97));if (k == 0 && chs[i] > 0){// k 用完字符还有剩余找分割字符for (int j = i - 1; j >= 0; j--){if (chs[j] > 0){chs[j]--;sb.append((char)(j + 97)); // 添加分割字符k = repeatLimit; break;}}}}}//return String.valueOf(sb);return sb.toString();}}class Solution {public String repeatLimitedString(String s, int repeatLimit) {int[] chs = new int[26];StringBuilder sb = new StringBuilder();for (char c : s.toCharArray()) chs[c - 'a']++;sigh:for (int i = 25; i >= 0; i--){if (chs[i] == 0) continue;String t = String.valueOf((char)(i + 97));int d = chs[i] / repeatLimit, r = chs[i] % repeatLimit;flag: // 1、处理整数部分for (int k = 0; k < d; k++){sb.append(t.repeat(repeatLimit));if (k == d - 1 && r == 0) continue sigh; // t 用完后不再添加分割符for (int j = i - 1; j >= 0; j--){if (chs[j] > 0){chs[j]--;sb.append((char)(j + 97)); // 添加分割字符continue flag;}}return sb.toString(); // 其它字母用完后直接返回答案} sb.append(t.repeat(r)); // 2、处理余数部分}return String.valueOf(sb); }}

2193.得到回文串的最少操作次数

从尾部开始，从左向右查找，如果只有一个删除，如果有两个都删除，更新答案和字符串长度 k。

class Solution:def minMovesToMakePalindrome(self, s: str) -> int:k, res = len(s), 0 while k > 2:idx = s.index(s[-1]) # 从右边开始if idx == k - 1: # 只有一个res += k // 2 # 移到中间s = s[:-1] # 删除k -= 1else:s = s[:idx] + s[idx + 1:-1] # 将两个字符删除res += idx # 向前交换到当前串的第一个的次数k -= 2return res

贪心，从左向右遍历，固定左侧字符，然后找到右侧对应字符并删除。

class Solution {public int minMovesToMakePalindrome(String s) {StringBuilder sb = new StringBuilder(s); int n = s.length(), half = n / 2, right = n - 1, res = 0;for (int i = 0; i < half; i++) {// 遍历左半部int j = sb.lastIndexOf(sb.charAt(i)+"");if (i == j) res += half - i; // 单个字符移到中间else {res += right - j;sb.deleteCharAt​(j);right--;}}return res; }}

2195.向数组中追加 K 个整数

class Solution:def minimalKSum(self, nums: List[int], k: int) -> int: # nums.sort() # t = pre = 0# for i in nums: # 去重，统计个数，求和 #if i > k: break#if i != pre: # k += 1 # t += i# pre = i# return (1 + k) * k // 2 - t # nums = sorted(set(nums)) # 去重 # for i in range(len(nums), 0, -1): # 逆序找#if k + i > nums[i - 1]: # return (1 + k + i) * (k + i) // 2 - sum(nums[:i])# return (k + 1) * k // 2 # if k < nums[0]: nums = sorted(set(nums)) # 排序去重后可用二分法i, j = 0, len(nums)while i < j:mid = (i + j) // 2if nums[mid] < k + mid + 1: i = mid + 1else: j = midmex = i + kreturn (mex + 1) * mex // 2 - sum(nums[:i])

class Solution {public long minimalKSum(int[] nums, int k) {Arrays.sort(nums);long t = 0L;int pre = 0;for (int i : nums){// 去重，统计个数，求和 if (i > k) break;if (i != pre){k++;t += i;pre = i;}}return (long)(k + 1) * k / 2 - t;}}

2202.K 次操作后最大化顶端元素

class Solution:def maximumTop(self, nums: List[int], k: int) -> int: if k == 0: return nums[0]n = len(nums)if n == 1: return -1 if k % 2 else nums[0]if k >= n: return max(nums[:k-1]) # nums 的第 k 个数即：nums[k-1] 永远不会出现在栈顶if k < n: return max(max(nums[:k-1], default=0), nums[k])

class Solution {public int maximumTop(int[] nums, int k) {int n = nums.length;if (k == 0) return nums[0];if (n == 1) return k % 2 == 0 ? nums[0] : -1;// if (k == 1) return nums[1];int max = 0;for (int i = 0; i < n && i < k - 1; i++)max = Math.max(max, nums[i]); // nums 的第 k 个数永远不会出现在栈顶if (k < n) max = Math.max(max, nums[k]); // 跳过索引 k - 1return max;}}

2207.字符串中最多数目的子字符串

class Solution:def maximumSubsequenceCount(self, text: str, pattern: str) -> int:a, b = patternx = y = ans = 0# for c in text: # 正序、逆序影响 a, b 的判断顺序。#if c == b: # 正序遇到 b，累加 a 的个数 x，后自增。 # ans += x # y += 1#if c == a: x += 1for c in reversed(text): if c == a:ans += y # ★ 当 a == b 时，先累加和、后自增。x += 1if c == b: y += 1 # x 为最大值，尾加 b，否则首加 a，共增加最大值个数。return max(x, y) + ans

class Solution {public long maximumSubsequenceCount(String text, String pattern) {char a = pattern.charAt(0), b = pattern.charAt(1); long count = 0;int x = 0, y = 0;for(char c : text.toCharArray()) {if(c == b) {// 先 b 后 acount += x; // 先累加后自增y++;} if(c == a) x++;} return count + Math.max(x, y);}}

2216.美化数组的最少删除数

class Solution:def minDeletion(self, nums: List[int]) -> int:res, pre, flag = 0, 0, True # flag = res % 2for i, x in enumerate(nums):if flag or x != pre: pre = xres += 1flag = not flagreturn len(nums) - res + res % 2

class Solution {public int minDeletion(int[] nums) {int res = 0, pre = nums[0]; // res 是留下的个数 boolean flag = true; // 用标记快 1 msfor (int x : nums){// res 为奇数时 pre 的下标是偶数同时需要 pre != x，为偶数时不限。// if ((res % 2 == 1 && x != pre) || res % 2 == 0){// if (res % 2 == 0 || pre != x) {// 也可以理解为只要偶数次，或当前不等于前一个即可。if (flag || pre != x) {res++;flag = !flag;pre = x;}}return nums.length - res + res % 2; // 剩余奇数个需要多删一个}}

LCP 15. 游乐园的迷宫

LCP 30. 魔塔游戏

LCP 32. 批量处理任务

LCP 33. 蓄水

LCP 37. 最小矩形面积

LCP 40. 心算挑战

LCS 01. 下载插件

LCS 02. 完成一半题目