2021年6月刷题日志
6.19
MS 实习了四天，放假回来刷题啦！
题目
1239. 串联字符串的最大长度
难度中等
给定一个字符串数组
arr，字符串s是将arr某一子序列字符串连接所得的字符串，如果s中的每一个字符都只出现过一次，那么它就是一个可行解。请返回所有可行解
s中最长长度。示例 1：
输入：arr = ["un","iq","ue"] 输出：4 解释：所有可能的串联组合是 "","un","iq","ue","uniq" 和 "ique"，最大长度为 4。示例 2：
输入：arr = ["cha","r","act","ers"] 输出：6 解释：可能的解答有 "chaers" 和 "acters"。示例 3：
输入：arr = ["abcdefghijklmnopqrstuvwxyz"] 输出：26提示：
1 <= arr.length <= 161 <= arr[i].length <= 26arr[i]中只含有小写英文字母
思路
深搜 + 剪枝
代码
class Solution {
int maxL;
public int maxLength(List<String> arr) {
int total = 0;
for (String str : arr) {
total += str.length();
}
dfs(0, "", arr, total);
return this.maxL;
}
public void dfs(int idx, String cur, List<String> arr, int total) {
if (cur.length() + total <= maxL || !isLegal(cur))
return;
if (idx == arr.size()) {
this.maxL = Math.max(cur.length(), this.maxL);
return;
}
total -= arr.get(idx).length();
dfs(idx + 1, cur + arr.get(idx), arr, total);
dfs(idx + 1, cur, arr, total);
}
public boolean isLegal(String s) {
if (s.length() > 26)
return false;
int[] cnt = new int[26];
for (int i = 0; i < s.length(); i++) {
int idx = s.charAt(i) - 'a';
cnt[idx]++;
if (cnt[idx] >= 2)
return false;
}
return true;
}
}
6.14
端午节简单题！🐉！
题目
374. 猜数字大小
难度简单
猜数字游戏的规则如下：
- 每轮游戏，我都会从 1 到 n 随机选择一个数字。 请你猜选出的是哪个数字。
- 如果你猜错了，我会告诉你，你猜测的数字比我选出的数字是大了还是小了。
你可以通过调用一个预先定义好的接口
int guess(int num)来获取猜测结果，返回值一共有 3 种可能的情况（-1，1或0）：
- -1：我选出的数字比你猜的数字小
pick < num- 1：我选出的数字比你猜的数字大
pick > num- 0：我选出的数字和你猜的数字一样。恭喜！你猜对了！
pick == num返回我选出的数字。
示例 1：
输入：n = 10, pick = 6 输出：6
思路
又是二分模板题，和昨天的区别有两点：
- 昨天的是找边界，今天的是找点
- 昨天的点有两种值，今天的点可能有三种值。
代码
/**
* Forward declaration of guess API.
* @param num your guess
* @return -1 if num is lower than the guess number
* 1 if num is higher than the guess number
* otherwise return 0
* int guess(int num);
*/
public class Solution extends GuessGame {
public int guessNumber(int n) {
int left = 0, right = n;
while (left < right) {
int mid = left + (right - left) / 2;
if (guess(mid) == 1) {
left = mid + 1;
} else if (guess(mid) == -1) {
right = mid - 1;
} else {
return mid;
}
}
return left;
}
}
6.13
昨天因为一些个人原因刷了题没写题解。
题目
278. 第一个错误的版本
难度简单
你是产品经理，目前正在带领一个团队开发新的产品。不幸的是，你的产品的最新版本没有通过质量检测。由于每个版本都是基于之前的版本开发的，所以错误的版本之后的所有版本都是错的。
假设你有
n个版本[1, 2, ..., n]，你想找出导致之后所有版本出错的第一个错误的版本。你可以通过调用
bool isBadVersion(version)接口来判断版本号version是否在单元测试中出错。实现一个函数来查找第一个错误的版本。你应该尽量减少对调用 API 的次数。示例:
给定 n = 5，并且 version = 4 是第一个错误的版本。 调用 isBadVersion(3) -> false 调用 isBadVersion(5) -> true 调用 isBadVersion(4) -> true 所以，4 是第一个错误的版本。
思路
要从一个[f, f, f, t, t] 找到第一个 f 的位置，还是比较好看出来是二分的。
tip: 在计算
mid的时候要记得使用left + (right - left) / 2，而不是(left + right)/2，因为后一种会溢出。
代码
/* The isBadVersion API is defined in the parent class VersionControl.
boolean isBadVersion(int version); */
public class Solution extends VersionControl {
public int firstBadVersion(int n) {
int left = 0, right = n - 1;
while (left <= right) {
int mid = left + (right - left) / 2;
if (isBadVersion(mid)) {
right = mid - 1;
} else {
left = mid + 1;
}
}
return left;
}
}
6.11
题目
279. 完全平方数
难度中等
给定正整数 n，找到若干个完全平方数（比如
1, 4, 9, 16, ...）使得它们的和等于 n。你需要让组成和的完全平方数的个数最少。给你一个整数
n，返回和为n的完全平方数的 最少数量 。完全平方数 是一个整数，其值等于另一个整数的平方；换句话说，其值等于一个整数自乘的积。例如，
1、4、9和16都是完全平方数，而3和11不是。示例 1：
输入：n = 12 输出：3 解释：12 = 4 + 4 + 4示例 2：
输入：n = 13 输出：2 解释：13 = 4 + 9
思路
动，都可以动
代码
class Solution {
public int numSquares(int n) {
int[] dp = new int[n + 1];
// dp[i] 表示用小于等于 largest 的自然数的平方数组成 i 所需要的最少个数
Arrays.fill(dp, 0x3f3f3f);
dp[0] = 0;
for (int i = 1; i <= n; i++) {
for (int j = 1; j * j <= i; j++) {
dp[i] = Math.min(dp[i], dp[i - j * j] + 1);
}
}
return dp[n];
}
}
6.10
完全背包问题简单版 ⭕
昨天蓝桥杯出成绩了，国二 👶
题目
518. 零钱兑换 II
难度中等
给定不同面额的硬币和一个总金额。写出函数来计算可以凑成总金额的硬币组合数。假设每一种面额的硬币有无限个。
示例 1:
输入: amount = 5, coins = [1, 2, 5] 输出: 4 解释: 有四种方式可以凑成总金额: 5=5 5=2+2+1 5=2+1+1+1 5=1+1+1+1+1
思路
起初我想的方法是用 dp[i][j] 去表示 用前 j 种硬币，凑出 i 元的方案数。
要计算这个，必定需要令 i = 0...amount 一层循环，j = 1...coins.length 一层循环。
但是需要计算出 dp[i][j] 的值，还需要去计算不用第 j 个硬币的凑出 i - 用过的硬币的价值 的方案数，也就是说需要再套一层循环 k = 0...j-1，因此我写出来的代码长这个样子。
class Solution {
public int change(int amount, int[] coins) {
int n = coins.length;
int[][] dp = new int[amount + 1][n + 1];
// dp[i][j] 表示凑出 i 元的可能方案，且只能用前 j 种硬币。
for (int j = 0; j <= n; j++) {
dp[0][j] = 1;
}
for (int i = 0; i <= amount; i++) {
for (int j = 1; j <= n; j++) {
for (int k = 0; k < j; k++) {
int coin = coins[k];
if (i >= coin) {
dp[i][j] += dp[i - coin][k + 1];
}
}
}
}
return dp[amount][n];
}
}
一提交发现击败 5% 😰 于是我去题解区寻找了优化方案，想办法优化掉最内存的循环。
答案肯定是可以的，其实要确定 dp[i][j] 并不需要逐个遍历用过的硬币面值去找，假设只需要通过 dp[i][j - 1] 和 dp[i - coin(当前的面值)][j] 就可以算出来。可以理解为两种情况：
- 不用当前的硬币，只用前
j - 1种硬币凑出来i元。 - 用当前的硬币
coin，并且前j - 1种硬币凑出i - coin元。
class Solution {
public int change(int amount, int[] coins) {
int n = coins.length;
int[][] dp = new int[amount + 1][n + 1];
// dp[i][j] 表示凑出 i 元的可能方案，且只能用前 j 种硬币。
for (int j = 0; j <= n; j++) {
dp[0][j] = 1;
}
for (int i = 0; i <= amount; i++) {
for (int j = 1; j <= n; j++) {
int coin = coins[j - 1];
if (coin <= i) {
dp[i][j] = dp[i - coin][j] + dp[i][j - 1];
} else {
dp[i][j] = dp[i][j - 1];
}
}
}
return dp[amount][n];
}
}
一提交发现击败 10% 💢 见鬼了，继续优化 ！
二维的动态规划耗时长，无非优化成一维的嘛！那就把原来的 dp[i][j] 的 j 给优化掉，直接遍历硬币数组。
class Solution {
public int change(int amount, int[] coins) {
int n = coins.length;
int[] dp = new int[amount + 1];
// dp[i] 表示凑出 i 元的可能方案
dp[0] = 1;
for (int coin: coins) {
for (int i = coin; i <= amount; i++) {
dp[i] += dp[i - coin];
}
}
return dp[amount];
}
}
由于我们求的是组合数，所以在外层遍历硬币，内层遍历金额。反过来会变成排列。
舒服了
6.9
背包问题困难版 ❌
题目
879. 盈利计划
难度困难
集团里有
n名员工，他们可以完成各种各样的工作创造利润。第
i种工作会产生profit[i]的利润，它要求group[i]名成员共同参与。如果成员参与了其中一项工作，就不能参与另一项工作。工作的任何至少产生
minProfit利润的子集称为 盈利计划 。并且工作的成员总数最多为n。有多少种计划可以选择？因为答案很大，所以 返回结果模
10^9 + 7的值。示例 1：
输入：n = 5, minProfit = 3, group = [2,2], profit = [2,3] 输出：2 解释：至少产生 3 的利润，该集团可以完成工作 0 和工作 1 ，或仅完成工作 1 。 总的来说，有两种计划。
思路
虽然看出来是用动规，但是却没看出来是三维的数组（因为有两种限制，工作和人数）
开辟一个三维数组记录状态，dp[i][j][k] 表示的是前 i 项工作，派 j 个人，获得利润大于等于 k 的可能计划数。
进行一个三重的遍历，每次根据人数去更新计划数。
代码
class Solution {
public int profitableSchemes(int n, int minProfit, int[] group, int[] profit) {
int cnt = 0, MOD = (int)1e9 + 7;
int len = group.length;
// dp[i][j][k] 表示前 i 项工作，派 j 个人，获得的利润大于等于 k 的计划数
int[][][] dp = new int[len + 1][n + 1][minProfit + 1];
dp[0][0][0] = 1;
for (int i = 1; i <= len; i++) {
int members = group[i - 1], money = profit[i - 1];
for (int j = 0; j <= n; j++) {
for (int k = 0; k <= minProfit; k++) {
if (j < members) {
dp[i][j][k] = dp[i - 1][j][k] % MOD;
} else {
dp[i][j][k] = (dp[i - 1][j][k] + dp[i - 1][j - members][Math.max(0, k - money)]) % MOD;
}
}
}
}
int sum = 0;
for (int j = 0; j <= n; j++) {
sum = (sum + dp[len][j][minProfit]) % MOD;
}
return sum;
}
}
6.8
又是背包问题 🤦♂️ 人傻了
题目
1049. 最后一块石头的重量 II
难度中等
有一堆石头，用整数数组
stones表示。其中stones[i]表示第i块石头的重量。每一回合，从中选出任意两块石头，然后将它们一起粉碎。假设石头的重量分别为
x和y，且x <= y。那么粉碎的可能结果如下：
- 如果
x == y，那么两块石头都会被完全粉碎；- 如果
x != y，那么重量为x的石头将会完全粉碎，而重量为y的石头新重量为y-x。最后，最多只会剩下一块 石头。返回此石头 最小的可能重量 。如果没有石头剩下，就返回
0。示例 1：
输入：stones = [2,7,4,1,8,1] 输出：1 解释： 组合 2 和 4，得到 2，所以数组转化为 [2,7,1,8,1]， 组合 7 和 8，得到 1，所以数组转化为 [2,1,1,1]， 组合 2 和 1，得到 1，所以数组转化为 [1,1,1]， 组合 1 和 1，得到 0，所以数组转化为 [1]，这就是最优值。
思路
可以看作是需要把一堆石头分成两堆，一堆用来加，一堆用来减。
我们的目标就是让其中一堆的质量尽可能靠近总质量的一半。
利用动态规划，令 dp[i][j] 表示前 i 块石头能否粉碎成重量等于 j 的石头。
代码
class Solution {
public int lastStoneWeightII(int[] stones) {
int n = stones.length;
int sum = 0;
for (int stone: stones) {
sum += stone;
}
int m = sum / 2;
// dp[i][j] 表示前 i 块石头能否粉碎成重量等于 j 的石头
boolean[][] dp = new boolean[n + 1][m + 1];
dp[0][0] = true;
for (int i = 1; i <= n; i++) {
int stone = stones[i - 1];
for (int j = 0; j <= m; j++) {
dp[i][j] = dp[i - 1][j];
if (j >= stone) {
dp[i][j] |= dp[i - 1][j - stone];
}
}
}
for (int j = m; j >= 0; j--) {
if (dp[n][j]) {
return sum - 2 * j;
}
}
return 0;
}
}
6.7
软测期末考试 + 选修课交论文 + 疫苗 + 理发结束，下午三点多终于有空刷题了。
今天高考作文出来了，之前看了木鱼的11p觉醒年代讲解，感觉光引用台词就能写完作文，「觉醒年代」YYDS！
题目
494. 目标和
难度中等
给你一个整数数组
nums和一个整数target。向数组中的每个整数前添加
'+'或'-'，然后串联起所有整数，可以构造一个 表达式 ：
- 例如，
nums = [2, 1]，可以在2之前添加'+'，在1之前添加'-'，然后串联起来得到表达式"+2-1"。返回可以通过上述方法构造的、运算结果等于
target的不同 表达式 的数目。示例 1：
输入：nums = [1,1,1,1,1], target = 3 输出：5 解释：一共有 5 种方法让最终目标和为 3 。 -1 + 1 + 1 + 1 + 1 = 3 +1 - 1 + 1 + 1 + 1 = 3 +1 + 1 - 1 + 1 + 1 = 3 +1 + 1 + 1 - 1 + 1 = 3 +1 + 1 + 1 + 1 - 1 = 3
思路
表面中等题，实际简单题。
哈希表迭代即可求出可能和的种类和个数。
权当学习一下 Java 语法。
代码
class Solution {
public int findTargetSumWays(int[] nums, int target) {
var m = new HashMap<Integer, Integer>();
m.put(0, 1);
for (int num : nums) {
var nxt = new HashMap<Integer, Integer>();
for (int key : m.keySet()) {
int plus = nxt.containsKey(key + num) ? nxt.get(key + num) : 0;
nxt.put(key + num, plus + m.get(key));
int minus = nxt.containsKey(key - num) ? nxt.get(key - num) : 0;
nxt.put(key - num, minus + m.get(key));
}
m = nxt;
}
return m.containsKey(target)? m.get(target): 0;
}
}
6.6
题目
474. 一和零
难度中等
给你一个二进制字符串数组
strs和两个整数m和n。请你找出并返回
strs的最大子集的大小，该子集中 最多 有m个0和n个1。如果
x的所有元素也是y的元素，集合x是集合y的 子集 。示例 1：
输入：strs = ["10", "0001", "111001", "1", "0"], m = 5, n = 3 输出：4 解释：最多有 5 个 0 和 3 个 1 的最大子集是 {"10","0001","1","0"} ，因此答案是 4 。 其他满足题意但较小的子集包括 {"0001","1"} 和 {"10","1","0"} 。{"111001"} 不满足题意，因为它含 4 个 1 ，大于 n 的值 3 。示例 2：
输入：strs = ["10", "0", "1"], m = 1, n = 1 输出：2 解释：最大的子集是 {"0", "1"} ，所以答案是 2 。
思路
又是动态规划，做不出来真苦恼 😕
背包问题的变形。
代码
class Solution {
public int findMaxForm(String[] strs, int m, int n) {
// 空间优化版本
int[][] dp = new int[m + 1][n + 1];
for (String str: strs) {
int zero = 0, one = 0;
for (char c: str.toCharArray()) {
if (c == '0') zero++;
else one++;
}
for (int i = m; i >= zero; i--) {
for (int j = n; j >= one; j--) {
dp[i][j] = Math.max(dp[i][j], dp[i-zero][j-one] + 1);
}
}
}
return dp[m][n];
}
}
6.5
上午蓝桥杯国赛，一言难尽，真就写的都是嗯解。
题目
203. 移除链表元素
难度简单
给你一个链表的头节点
head和一个整数val，请你删除链表中所有满足Node.val == val的节点，并返回 新的头节点 。示例 1：
输入：head = [1,2,6,3,4,5,6], val = 6 输出：[1,2,3,4,5]示例 2：
输入：head = [], val = 1 输出：[]
思路
小技巧，在头节点前新建一个伪结点，便于需要删除头节点的情况。
然后就是很普通的遍历和删结点，因为是链表，所以只要让指针跳过需要删的结点即可，不需要真的删。
代码
为了迎接接下来的夏令营，我又要开始用 Java 刷题了 😪
class Solution {
public ListNode removeElements(ListNode head, int val) {
ListNode dummy = new ListNode(0, head);
ListNode node = head;
ListNode pre = dummy;
while (node != null) {
if (node.val == val) {
pre.next = node.next;
} else {
pre = node;
}
node = node.next;
}
return dummy.next;
}
}
6.4
题目
160. 相交链表
难度简单
给你两个单链表的头节点
headA和headB，请你找出并返回两个单链表相交的起始节点。如果两个链表没有交点，返回null。图示两个链表在节点
c1开始相交**：**
题目数据 保证 整个链式结构中不存在环。
注意，函数返回结果后，链表必须 保持其原始结构 。
示例 1：
输入：intersectVal = 8, listA = [4,1,8,4,5], listB = [5,0,1,8,4,5], skipA = 2, skipB = 3 输出：Intersected at '8' 解释：相交节点的值为 8 （注意，如果两个链表相交则不能为 0）。 从各自的表头开始算起，链表 A 为 [4,1,8,4,5]，链表 B 为 [5,0,1,8,4,5]。 在 A 中，相交节点前有 2 个节点；在 B 中，相交节点前有 3 个节点。
思路
- 先遍历一遍 A 链表，用哈希表记录遍历过的结点值。再遍历一遍 B 链表，同时查找当前结点是否在 A 链表中出现过。
- 第一次先遍历 A 和 B 链表，确认两者长度，第二次，让长的那个链表先前进若干步，保证两者能最终同时到尾结点。一边前进，一边确认是否当前结点相同。
- 交叉遍历，官方题解 YYDS，感觉有种殊途同归的含义。
代码
# 解法2
class Solution:
def getIntersectionNode(self, headA: ListNode, headB: ListNode) -> ListNode:
nodeA, nodeB = headA, headB
lenA = lenB = 0
while nodeA:
nodeA = nodeA.next
lenA += 1
while nodeB:
nodeB = nodeB.next
lenB += 1
if lenA > lenB:
# 确保 A 短 B 长
headA, headB = headB, headA
lenA, lenB = lenB, lenA
nodeA, nodeB = headA, headB
for i in range(lenB - lenA):
nodeB = nodeB.next
while nodeA and nodeB and nodeA != nodeB:
nodeA = nodeA.next
nodeB = nodeB.next
return nodeA if nodeA == nodeB else None
# 解法3
class Solution:
def getIntersectionNode(self, headA: ListNode, headB: ListNode) -> ListNode:
nodeA, nodeB = headA, headB
while nodeA != nodeB:
nodeA = nodeA.next if nodeA else headB
nodeB = nodeB.next if nodeB else headA
return nodeA
6.3
题目
525. 连续数组
难度中等
给定一个二进制数组
nums, 找到含有相同数量的0和1的最长连续子数组，并返回该子数组的长度。示例 1:
输入: nums = [0,1] 输出: 2 说明: [0, 1] 是具有相同数量0和1的最长连续子数组。示例 2:
输入: nums = [0,1,0] 输出: 2 说明: [0, 1] (或 [1, 0]) 是具有相同数量0和1的最长连续子数组。
思路
和昨天的题目类似，都是利用前缀和的思路快速求得某段子数组中 0 的个数和 1 的个数。
利用哈希表记录前面出现过的子数组的 0 和 1 的出现次数之差。
代码
class Solution:
def findMaxLength(self, nums: List[int]) -> int:
dic = dict() # cnt0 - cnt1 -> idx
dic[0] = -1
res = 0
cnts = [0, 0] # 记录0,1的个数
for idx, num in enumerate(nums):
cnts[num] += 1
diff = cnts[0] - cnts[1]
if diff not in dic:
dic[diff] = idx
if diff:
res = max(res, idx - dic[diff])
else:
res = idx + 1
return res
6.2
周六就要去蓝桥杯国赛了，紧张
题目
523. 连续的子数组和
难度中等
给你一个整数数组
nums和一个整数k，编写一个函数来判断该数组是否含有同时满足下述条件的连续子数组：
- 子数组大小 至少为 2 ，且
- 子数组元素总和为
k的倍数。如果存在，返回
true；否则，返回false。如果存在一个整数
n，令整数x符合x = n * k，则称x是k的一个倍数。示例 1：
输入：nums = [23,2,4,6,7], k = 6 输出：true 解释：[2,4] 是一个大小为 2 的子数组，并且和为 6 。示例 2：
输入：nums = [23,2,6,4,7], k = 6 输出：true 解释：[23, 2, 6, 4, 7] 是大小为 5 的子数组，并且和为 42 。 42 是 6 的倍数，因为 42 = 7 * 6 且 7 是一个整数。
思路
-
为了快速计算
nums数组中某段区间和，需要用到前缀和的思想。 -
假设子数组
nums[left: right]和为k的倍数，只需要保证nums[0: left]和nums[0: right]➗k的余数都相同就行了。 -
以上两个操作，可以在一次遍历中使用哈希表完成。
根据官方题解和其他人提交的代码不断优化。
代码
class Solution:
def checkSubarraySum(self, nums: List[int], k: int) -> bool:
visited = dict() # sum -> idx
visited[0] = -1
cur = 0
for idx, num in enumerate(nums):
cur = (cur + num) % k
if cur not in visited:
visited[cur] = idx
if idx - visited[cur] >= 2:
return True
return False