【一天一题】力扣刷题日记
本文最后更新于 2024年11月7日 下午
*【一天一题—Day55】1608. 特殊数组的特征值
一、前景提要
还行
二、题目
难度：简单
给你一个非负整数数组 nums 。如果存在一个数 x ，使得 nums 中恰好有 x 个元素 大于或者等于 x ，那么就称 nums 是一个 特殊数组 ，而 x 是该数组的 特征值 。
注意： x 不必 是 nums 的中的元素。
如果数组 nums 是一个 特殊数组 ，请返回它的特征值 x 。否则，返回 -1 。可以证明的是，如果 nums 是特殊数组，那么其特征值 x 是 唯一的 。
示例 1：
输入：nums = [3,5]
输出：2
解释：有 2 个元素（3 和 5）大于或等于 2 。
示例 2：
输入：nums = [0,0]
输出：-1
解释：没有满足题目要求的特殊数组，故而也不存在特征值 x 。
如果 x = 0，应该有 0 个元素 >= x，但实际有 2 个。
如果 x = 1，应该有 1 个元素 >= x，但实际有 0 个。
如果 x = 2，应该有 2 个元素 >= x，但实际有 0 个。
x 不能取更大的值，因为 nums 中只有两个元素。
示例 3：
输入：nums = [0,4,3,0,4]
输出：3
解释：有 3 个元素大于或等于 3 。
示例 4：
输入：nums = [3,6,7,7,0]
输出：-1
提示：
- 1 <= nums.length <= 100
- 0 <= nums[i] <= 1000
三、解答
看了答案才觉得简单……不然实在不好想到
1，非官方解法
1 | |
2，官方解法
*【一天一题—Day54】857. 雇佣 K 名工人的最低成本
一、前景提要
困难，先放着
二、题目
难度：困难
有 n 名工人。 给定两个数组 quality 和 wage ，其中，quality[i] 表示第 i 名工人的工作质量，其最低期望工资为 wage[i] 。
现在我们想雇佣 k 名工人组成一个工资组。在雇佣 一组 k 名工人时，我们必须按照下述规则向他们支付工资：
对工资组中的每名工人，应当按其工作质量与同组其他工人的工作质量的比例来支付工资。
工资组中的每名工人至少应当得到他们的最低期望工资。
给定整数 k ，返回 组成满足上述条件的付费群体所需的最小金额 。在实际答案的 10-5 以内的答案将被接受。。
示例 1：
输入： quality = [10,20,5], wage = [70,50,30], k = 2
输出： 105.00000
解释： 我们向 0 号工人支付 70，向 2 号工人支付 35。
示例 2：
输入： quality = [3,1,10,10,1], wage = [4,8,2,2,7], k = 3
输出： 30.66667
解释： 我们向 0 号工人支付 4，向 2 号和 3 号分别支付 13.33333。
提示：
- n == quality.length == wage.length
- 1 <= k <= n <= 104
- 1 <= quality[i], wage[i] <= 104
三、解答
看了答案才觉得简单……不然实在不好想到
1，非官方解法
1 | |
2，官方解法
*【一天一题—Day53】669. 修剪二叉搜索树
一、前景提要
这上班的日子我是一天都不想呆了！
但是开会员后的金拱门早餐蛮实惠的，相比于宿舍楼下2馒头+1豆浆=7.5来说的话，至少金拱门的7.5有一大块肉
二、题目
难度：中等
给你二叉搜索树的根节点 root ，同时给定最小边界low 和最大边界 high。通过修剪二叉搜索树，使得所有节点的值在[low, high]中。修剪树 不应该 改变保留在树中的元素的相对结构 (即，如果没有被移除，原有的父代子代关系都应当保留)。 可以证明，存在 唯一的答案 。
所以结果应当返回修剪好的二叉搜索树的新的根节点。注意，根节点可能会根据给定的边界发生改变。
示例 1：
输入：root = [1,0,2], low = 1, high = 2
输出：[1,null,2]
示例 2：
输入：root = [3,0,4,null,2,null,null,1], low = 1, high = 3
输出：[3,2,null,1]
提示：
- 树中节点数在范围 [1, 104] 内
- 0 <= Node.val <= 104
- 树中每个节点的值都是 唯一 的
- 题目数据保证输入是一棵有效的二叉搜索树
- 0 <= low <= high <= 104
三、解答
看了答案才觉得简单……不然实在不好想到
1，非官方解法
1 | |
2，官方解法
*【一天一题—Day52】1598. 文件夹操作日志搜集器
一、前景提要
这上班的日子我是一天都不想呆了！
但是开会员后的金拱门早餐蛮实惠的，相比于宿舍楼下2馒头+1豆浆=7.5来说的话，至少金拱门的7.5有一大块肉
二、题目
难度：中等
每当用户执行变更文件夹操作时，LeetCode 文件系统都会保存一条日志记录。
下面给出对变更操作的说明：
"../" ：移动到当前文件夹的父文件夹。如果已经在主文件夹下，则 继续停留在当前文件夹 。
"./" ：继续停留在当前文件夹。
"x/" ：移动到名为 x 的子文件夹中。题目数据 保证总是存在文件夹 x 。
给你一个字符串列表 logs ，其中 logs[i] 是用户在 ith 步执行的操作。
文件系统启动时位于主文件夹，然后执行 logs 中的操作。
执行完所有变更文件夹操作后，请你找出 返回主文件夹所需的最小步数 。
示例 1：
输入：logs = ["d1/","d2/","../","d21/","./"]
输出：2
解释：执行 "../" 操作变更文件夹 2 次，即可回到主文件夹
示例 2：
输入：logs = ["d1/","d2/","./","d3/","../","d31/"]
输出：3
示例 3：
输入：logs = ["d1/","../","../","../"]
输出：0
提示：
- 1 <= logs.length <= 103
- 2 <= logs[i].length <= 10
- logs[i] 包含小写英文字母，数字，’.’ 和 ‘/‘
- logs[i] 符合语句中描述的格式
- 文件夹名称由小写英文字母和数字组成
三、解答
看了答案才觉得简单……不然实在不好想到
1，非官方解法
1 | |
2，官方解法
*【一天一题—Day51】667. 优美的排列 II
一、前景提要
阿巴阿巴阿巴阿巴，上课好折磨，在尝试恢复上学期期末的项目，重新部署到新的服务器上
二、题目
难度：中等
给你两个整数 n 和 k ，请你构造一个答案列表 answer ，该列表应当包含从 1 到 n 的 n 个不同正整数，并同时满足下述条件：
假设该列表是 answer = [a1, a2, a3, ... , an] ，那么列表 [|a1 - a2|, |a2 - a3|, |a3 - a4|, ... , |an-1 - an|] 中应该有且仅有 k 个不同整数。
返回列表 answer 。如果存在多种答案，只需返回其中 任意一种 。
示例 1：
输入：n = 3, k = 1
输出：[1, 2, 3]
解释：[1, 2, 3] 包含 3 个范围在 1-3 的不同整数，并且 [1, 1] 中有且仅有 1 个不同整数：1
示例 2：
输入：n = 3, k = 2
输出：[1, 3, 2]
解释：[1, 3, 2] 包含 3 个范围在 1-3 的不同整数，并且 [2, 1] 中有且仅有 2 个不同整数：1 和 2
提示：
- 1 <= k < n <= 104
三、解答
- @Kwbdlhisq
初看没思路，随便找个大点的用例一下就能找到规律。 [1, 1+k, 2, 1+k-1, 3, 1+k-2, 4…..k+2, k+3…n]
1，非官方解法
1 | |
2，官方解法
*【一天一题—Day50】1592. 重新排列单词间的空格
一、前景提要
虚假的简单题
二、题目
难度：简单
给你一个字符串 text ，该字符串由若干被空格包围的单词组成。每个单词由一个或者多个小写英文字母组成，并且两个单词之间至少存在一个空格。题目测试用例保证 text 至少包含一个单词 。
请你重新排列空格，使每对相邻单词之间的空格数目都 相等 ，并尽可能 最大化 该数目。如果不能重新平均分配所有空格，请 将多余的空格放置在字符串末尾 ，这也意味着返回的字符串应当与原 text 字符串的长度相等。
返回 重新排列空格后的字符串 。
示例 1：
输入：text = " this is a sentence "
输出："this is a sentence"
解释：总共有 9 个空格和 4 个单词。可以将 9 个空格平均分配到相邻单词之间，相邻单词间空格数为：9 / (4-1) = 3 个。
示例 2：
输入：text = " practice makes perfect"
输出："practice makes perfect "
解释：总共有 7 个空格和 3 个单词。7 / (3-1) = 3 个空格加上 1 个多余的空格。多余的空格需要放在字符串的末尾。
示例 3：
输入：text = "hello world"
输出："hello world"
示例 4：
输入：text = " walks udp package into bar a"
输出："walks udp package into bar a "
示例 5：
输入：text = "a"
输出："a"
提示：
- 1 <= text.length <= 100
- text 由小写英文字母和 ‘ ‘ 组成
- text 中至少包含一个单词
三、解答
暂略
1，非官方解法
1 | |
2，官方解法
*【一天一题—Day49】828. 统计子串中的唯一字符
一、前景提要
困难题，暂时pass，回头再看，之前的困难题大多会看一下思路，力争弄懂，但是现在时间不是很充裕，在教室违反人体力学的高椅子低桌子上课，整得我腰酸背痛，实在难顶
二、题目
难度：困难
我们定义了一个函数 countUniqueChars(s) 来统计字符串 s 中的唯一字符，并返回唯一字符的个数。
例如：s = "LEETCODE" ，则其中 "L", "T","C","O","D" 都是唯一字符，因为它们只出现一次，所以 countUniqueChars(s) = 5 。
本题将会给你一个字符串 s ，我们需要返回 countUniqueChars(t) 的总和，其中 t 是 s 的子字符串。输入用例保证返回值为 32 位整数。
注意，某些子字符串可能是重复的，但你统计时也必须算上这些重复的子字符串（也就是说，你必须统计 s 的所有子字符串中的唯一字符）。
示例 1：
输入: s = "ABC"
输出: 10
解释: 所有可能的子串为："A","B","C","AB","BC" 和 "ABC"。
其中，每一个子串都由独特字符构成。
所以其长度总和为：1 + 1 + 1 + 2 + 2 + 3 = 10
示例 2：
输入: s = "ABA"
输出: 8
解释: 除了 countUniqueChars("ABA") = 1 之外，其余与示例 1 相同。
示例 3：
输入：s = "LEETCODE"
输出：92
提示：
- 1 <= s.length <= 10^5
- s 只包含大写英文字符
三、解答
暂略
1，非官方解法
1 | |
2，官方解法
【一天一题—Day48】652. 寻找重复的子树
一、前景提要
好累，写了没保存，全没了
二、题目
难度：简单
给你一棵二叉树的根节点 root ，返回所有 重复的子树 。
对于同一类的重复子树，你只需要返回其中任意 一棵 的根结点即可。
如果两棵树具有 相同的结构 和 相同的结点值 ，则认为二者是 重复 的。
示例 1：
输入：root = [1,2,3,4,null,2,4,null,null,4]
输出：[[2,4],[4]]
示例 2：
输入：root = [2,1,1]
输出：[[1]]
示例 3：
输入：root = [2,2,2,3,null,3,null]
输出：[[2,3],[3]]
提示：
- 树中的结点数在 [1, 5000] 范围内。
- -200 <= Node.val <= 200
三、解答
暴力循环，forforforfor
1，非官方解法
1 | |
2，官方解法
【一天一题—Day47】1582. 二进制矩阵中的特殊位置
一、前景提要
今天休息一天，明早5点过去练科二全程
二、题目
难度：简单
给你一个大小为 rows x cols 的矩阵 mat，其中 mat[i][j] 是 0 或 1，请返回 矩阵 mat 中特殊位置的数目 。
特殊位置 定义：如果 mat[i][j] == 1 并且第 i 行和第 j 列中的所有其他元素均为 0（行和列的下标均 从 0 开始 ），则位置 (i, j) 被称为特殊位置。
示例 1：
输入：mat = [[1,0,0],
[0,0,1],
[1,0,0]]
输出：1
解释：(1,2) 是一个特殊位置，因为 mat[1][2] == 1 且所处的行和列上所有其他元素都是 0
示例 2：
输入：mat = [[1,0,0],
[0,1,0],
[0,0,1]]
输出：3
解释：(0,0), (1,1) 和 (2,2) 都是特殊位置
示例 3：
输入：mat = [[0,0,0,1],
[1,0,0,0],
[0,1,1,0],
[0,0,0,0]]
输出：2
示例 4：
输入：mat = [[0,0,0,0,0],
[1,0,0,0,0],
[0,1,0,0,0],
[0,0,1,0,0],
[0,0,0,1,1]]
输出：3
提示：
- rows == mat.length
- cols == mat[i].length
- 1 <= rows, cols <= 100
- mat[i][j] 是 0 或 1
三、解答
暴力循环，forforforfor
1，非官方解法
1 | |
2，官方解法
【一天一题—Day46】646. 最长数对链
一、前景提要
练车好累，腰酸背痛各种，脚还流血了，回来还感冒了，倒车入库也练腻了……
二、题目
难度：中等
给出 n 个数对。 在每一个数对中，第一个数字总是比第二个数字小。
现在，我们定义一种跟随关系，当且仅当 b < c 时，数对(c, d) 才可以跟在 (a, b) 后面。我们用这种形式来构造一个数对链。
给定一个数对集合，找出能够形成的最长数对链的长度。你不需要用到所有的数对，你可以以任何顺序选择其中的一些数对来构造。
示例：
输入：[[1,2], [2,3], [3,4]]
输出：2
解释：最长的数对链是 [1,2] -> [3,4]
提示：
- 给出数对的个数在 [1, 1000] 范围内。
三、解答
1，非官方解法
1 | |
2，官方解法
【一天一题—Day45】687. 最长同值路径
一、前景提要
二、题目
难度：中等
给定一个二叉树的 root ，返回 最长的路径的长度 ，这个路径中的 每个节点具有相同值 。 这条路径可以经过也可以不经过根节点。
两个节点之间的路径长度 由它们之间的边数表示。
示例 1:
输入：root = [5,4,5,1,1,5]
输出：2
示例 2:
输入：root = [1,4,5,4,4,5]
输出：2
提示:
- 树的节点数的范围是 [0, 104]
- -1000 <= Node.val <= 1000
- 树的深度将不超过 1000
三、解答
递归
1，非官方解法
1 | |
2，官方解法
【一天一题—Day44】1475. 商品折扣后的最终价格
一、前景提要
二、题目
难度：简单
给你一个数组 prices ，其中 prices[i] 是商店里第 i 件商品的价格。
商店里正在进行促销活动，如果你要买第 i 件商品，那么你可以得到与 prices[j] 相等的折扣，其中 j 是满足 j > i 且 prices[j] <= prices[i] 的 最小下标 ，如果没有满足条件的 j ，你将没有任何折扣。
请你返回一个数组，数组中第 i 个元素是折扣后你购买商品 i 最终需要支付的价格。
示例 1：
输入：prices = [8,4,6,2,3]
输出：[4,2,4,2,3]
解释：
商品 0 的价格为 price[0]=8 ，你将得到 prices[1]=4 的折扣，所以最终价格为 8 - 4 = 4 。
商品 1 的价格为 price[1]=4 ，你将得到 prices[3]=2 的折扣，所以最终价格为 4 - 2 = 2 。
商品 2 的价格为 price[2]=6 ，你将得到 prices[3]=2 的折扣，所以最终价格为 6 - 2 = 4 。
商品 3 和 4 都没有折扣。
示例 2：
输入：prices = [1,2,3,4,5]
输出：[1,2,3,4,5]
解释：在这个例子中，所有商品都没有折扣。
示例 3：
输入：prices = [10,1,1,6]
输出：[9,0,1,6]
提示：
- 1 <= prices.length <= 500
- 1 <= prices[i] <= 10^3
三、解答
没啥好说的
1，非官方解法
1 | |
2，官方解法
【一天一题—Day43】998. 最大二叉树 II
一、前景提要
回宿舍整理也有点累的
二、题目
难度：中等
最大树 定义：一棵树，并满足：其中每个节点的值都大于其子树中的任何其他值。
给你最大树的根节点 root 和一个整数 val 。
就像 [之前的问题](https://leetcode.cn/problems/maximum-binary-tree/) 那样，给定的树是利用 Construct(a) 例程从列表 a（root = Construct(a)）递归地构建的：
如果 a 为空，返回 null 。
否则，令 a[i] 作为 a 的最大元素。创建一个值为 a[i] 的根节点 root 。
root 的左子树将被构建为 Construct([a[0], a[1], ..., a[i - 1]]) 。
root 的右子树将被构建为 Construct([a[i + 1], a[i + 2], ..., a[a.length - 1]]) 。
返回 root 。
请注意，题目没有直接给出 a ，只是给出一个根节点 root = Construct(a) 。
假设 b 是 a 的副本，并在末尾附加值 val。题目数据保证 b 中的值互不相同。
返回 Construct(b) 。
示例 1：
输入：root = [4,1,3,null,null,2], val = 5
输出：[5,4,null,1,3,null,null,2]
解释：a = [1,4,2,3], b = [1,4,2,3,5]
示例 2：
输入：root = [5,2,4,null,1], val = 3
输出：[5,2,4,null,1,null,3]
解释：a = [2,1,5,4], b = [2,1,5,4,3]
示例 3：
输入：root = [5,2,3,null,1], val = 4
输出：[5,2,4,null,1,3]
解释：a = [2,1,5,3], b = [2,1,5,3,4]
提示：
- 树中节点数目在范围 [1, 100] 内
- 1 <= Node.val <= 100
- 树中的所有值 互不相同
- 1 <= val <= 100
三、解答
1，非官方解法
1 | |
2，官方解法
*【一天一题—Day42】946. 验证栈序列
一、前景提要
最后一个暑假结束咧！
二、题目
难度：中等
给定 pushed 和 popped 两个序列，每个序列中的 值都不重复，只有当它们可能是在最初空栈上进行的推入 push 和弹出 pop 操作序列的结果时，返回 true；否则，返回 false 。
示例 1：
输入：pushed = [1,2,3,4,5], popped = [4,5,3,2,1]
输出：true
解释：我们可以按以下顺序执行：
push(1), push(2), push(3), push(4), pop() -> 4,
push(5), pop() -> 5, pop() -> 3, pop() -> 2, pop() -> 1
示例 2：
输入：pushed = [1,2,3,4,5], popped = [4,3,5,1,2]
输出：false
解释：1 不能在 2 之前弹出。
提示：
- 1 <= pushed.length <= 1000
- 0 <= pushed[i] <= 1000
- pushed 的所有元素 互不相同
- popped.length == pushed.length
- popped 是 pushed 的一个排列
三、解答
1，非官方解法
1 | |
2，官方解法
【一天一题—Day41】793. 阶乘函数后 K 个零
一、前景提要
困难题，直接开摆
二、题目
难度：困难
f(x) 是 x! 末尾是 0 的数量。回想一下 x! = 1 * 2 * 3 * ... * x，且 0! = 1 。
例如， f(3) = 0 ，因为 3! = 6 的末尾没有 0 ；而 f(11) = 2 ，因为 11!= 39916800 末端有 2 个 0 。
给定 k，找出返回能满足 f(x) = k 的非负整数 x 的数量。
示例 1：
输入：k = 0
输出：5
解释：0!, 1!, 2!, 3!, 和 4! 均符合 k = 0 的条件。
示例 2：
输入：k = 5
输出：0
解释：没有匹配到这样的 x!，符合 k = 5 的条件。
示例 3:
输入: k = 3
输出: 5
提示:
- 0 <= k <= 109
三、解答
1，非官方解法
1 | |
2，官方解法
【一天一题—Day40】1470. 重新排列数组
一、前景提要
学一下逻辑左移（把计组的知识点带进来）
二、题目
难度：简单
给你一个数组 nums ，数组中有 2n 个元素，按 [x1,x2,...,xn,y1,y2,...,yn] 的格式排列。
请你将数组按 [x1,y1,x2,y2,...,xn,yn] 格式重新排列，返回重排后的数组。
示例 1：
输入：nums = [2,5,1,3,4,7], n = 3
输出：[2,3,5,4,1,7]
解释：由于 x1=2, x2=5, x3=1, y1=3, y2=4, y3=7 ，所以答案为 [2,3,5,4,1,7]
示例 2：
输入：nums = [1,2,3,4,4,3,2,1], n = 4
输出：[1,4,2,3,3,2,4,1]
示例 3：
输入：nums = [1,1,2,2], n = 2
输出：[1,2,1,2]
提示：
- 1 <= n <= 500
- nums.length == 2n
- 1 <= nums[i] <= 10^3
三、解答
1，非官方解法
1 | |
2，官方解法
【一天一题—Day39】1470. 重新排列数组
一、前景提要
学一下逻辑左移（把计组的知识点带进来）
二、题目
难度：简单
给你一个数组 nums ，数组中有 2n 个元素，按 [x1,x2,...,xn,y1,y2,...,yn] 的格式排列。
请你将数组按 [x1,y1,x2,y2,...,xn,yn] 格式重新排列，返回重排后的数组。
示例 1：
输入：nums = [2,5,1,3,4,7], n = 3
输出：[2,3,5,4,1,7]
解释：由于 x1=2, x2=5, x3=1, y1=3, y2=4, y3=7 ，所以答案为 [2,3,5,4,1,7]
示例 2：
输入：nums = [1,2,3,4,4,3,2,1], n = 4
输出：[1,4,2,3,3,2,4,1]
示例 3：
输入：nums = [1,1,2,2], n = 2
输出：[1,2,1,2]
提示：
- 1 <= n <= 500
- nums.length == 2n
- 1 <= nums[i] <= 10^3
三、解答
1，非官方解法
1 | |
2，官方解法
【一天一题—Day38】662. 二叉树最大宽度
一、前景提要
没啥好说的
二、题目
难度：中等
给你一棵二叉树的根节点 root ，返回树的 最大宽度 。
树的 最大宽度 是所有层中最大的 宽度 。
每一层的 宽度 被定义为该层最左和最右的非空节点（即，两个端点）之间的长度。将这个二叉树视作与满二叉树结构相同，两端点间会出现一些延伸到这一层的 null 节点，这些 null 节点也计入长度。
题目数据保证答案将会在 32 位 带符号整数范围内。
示例 1：
输入：root = [1,3,2,5,3,null,9]
输出：4
解释：最大宽度出现在树的第 3 层，宽度为 4 (5,3,null,9) 。
示例 2：
输入：root = [1,3,2,5,null,null,9,6,null,7]
输出：7
解释：最大宽度出现在树的第 4 层，宽度为 7 (6,null,null,null,null,null,7) 。
示例 3：
输入：root = [1,3,2,5]
输出：2
解释：最大宽度出现在树的第 2 层，宽度为 2 (3,2) 。
提示：
- 树中节点的数目范围是 [1, 3000]
- -100 <= Node.val <= 100
三、解答
1，非官方解法
1 | |
2，官方解法
【一天一题—Day37】1464. 数组中两元素的最大乘积
一、前景提要
没啥好说的
二、题目
难度：简单
给你一个整数数组 nums，请你选择数组的两个不同下标 i 和 j，使 (nums[i]-1)*(nums[j]-1) 取得最大值。
请你计算并返回该式的最大值。
示例 1：
输入：nums = [3,4,5,2]
输出：12
解释：如果选择下标 i=1 和 j=2（下标从 0 开始），则可以获得最大值，(nums[1]-1)*(nums[2]-1) = (4-1)*(5-1) = 3*4 = 12 。
示例 2：
输入：nums = [1,5,4,5]
输出：16
解释：选择下标 i=1 和 j=3（下标从 0 开始），则可以获得最大值 (5-1)*(5-1) = 16 。
示例 3：
输入：nums = [3,7]
输出：12
提示：
- 2 <= nums.length <= 500
- 1 <= nums[i] <= 10^3
三、解答
1，非官方解法
排序数组然后把倒一倒二加起来就行
1 | |
2，官方解法
【一天一题—Day36】658. 找到 K 个最接近的元素
一、前景提要
还行
二、题目
难度：中等
给定一个 排序好 的数组 arr ，两个整数 k 和 x ，从数组中找到最靠近 x（两数之差最小）的 k 个数。返回的结果必须要是按升序排好的。
整数 a 比整数 b 更接近 x 需要满足：
|a - x| < |b - x| 或者
|a - x| == |b - x| 且 a < b
示例 1：
输入：arr = [1,2,3,4,5], k = 4, x = 3
输出：[1,2,3,4]
示例 2：
输入：arr = [1,2,3,4,5], k = 4, x = -1
输出：[1,2,3,4]
提示：
- 1 <= k <= arr.length
- 1 <= arr.length <= 104
- arr 按 升序 排列
- -104 <= arr[i], x <= 104
三、解答
1，非官方解法
用双指针判断与x距离的远近，好使但是不高效
1 | |
2，官方解法
【一天一题—Day35】1460. 通过翻转子数组使两个数组相等
一、前景提要
昨天困难题，懂得都懂
二、题目
难度：简单
给你两个长度相同的整数数组 target 和 arr 。每一步中，你可以选择 arr 的任意 非空子数组 并将它翻转。你可以执行此过程任意次。
如果你能让 arr 变得与 target 相同，返回 True；否则，返回 False 。
示例 1：
输入：target = [1,2,3,4], arr = [2,4,1,3]
输出：true
解释：你可以按照如下步骤使 arr 变成 target：
1- 翻转子数组 [2,4,1] ，arr 变成 [1,4,2,3]
2- 翻转子数组 [4,2] ，arr 变成 [1,2,4,3]
3- 翻转子数组 [4,3] ，arr 变成 [1,2,3,4]
上述方法并不是唯一的，还存在多种将 arr 变成 target 的方法。
示例 2：
输入：target = [7], arr = [7]
输出：true
解释：arr 不需要做任何翻转已经与 target 相等。
示例 3：
输入：target = [3,7,9], arr = [3,7,11]
输出：false
解释：arr 没有数字 9 ，所以无论如何也无法变成 target 。
提示：
- target.length == arr.length
- 1 <= target.length <= 1000
- 1 <= target[i] <= 1000
- 1 <= arr[i] <= 1000
三、解答
1，非官方解法
换个思路，不用顺着题目去旋转，直接用索引来判断即可
1 | |
2，官方解法
*【一天一题—Day33】655. 输出二叉树
一、前景提要
之前还记得<<的作用，现在就忘了
二、题目
难度：中等
给你一棵二叉树的根节点 root ，请你构造一个下标从 0 开始、大小为 m x n 的字符串矩阵 res ，用以表示树的 格式化布局 。构造此格式化布局矩阵需要遵循以下规则：
- 树的 高度 为 height ，矩阵的行数 m 应该等于 height + 1 。
- 矩阵的列数 n 应该等于 2height+1 - 1 。
- 根节点 需要放置在 顶行 的 正中间 ，对应位置为 res[0][(n-1)/2] 。
- 对于放置在矩阵中的每个节点，设对应位置为 res[r][c] ，将其左子节点放置在 res[r+1][c-2height-r-1] ，右子节点放置在 res[r+1][c+2height-r-1] 。
- 继续这一过程，直到树中的所有节点都妥善放置。
- 任意空单元格都应该包含空字符串 "" 。
返回构造得到的矩阵 res 。
示例 1：
输入：root = [1,2]
输出：
[["","1",""],
["2","",""]]
示例 2：
输入：root = [1,2,3,null,4]
输出：
[["","","","1","","",""],
["","2","","","","3",""],
["","","4","","","",""]]
提示：
- 树中节点数在范围 [1, 210] 内
- -99 <= Node.val <= 99
- 树的深度在范围 [1, 10] 内
三、解答
1，非官方解法
1 | |
2，官方解法
【一天一题—Day32】1455. 检查单词是否为句中其他单词的前缀
一、前景提要
简单
二、题目
1455.检查单词是否为句中其他单词的前缀
难度：简单
给你一个字符串 sentence 作为句子并指定检索词为 searchWord ，其中句子由若干用 单个空格 分隔的单词组成。请你检查检索词 searchWord 是否为句子 sentence 中任意单词的前缀。
如果 searchWord 是某一个单词的前缀，则返回句子 sentence 中该单词所对应的下标（下标从 1 开始）。如果 searchWord 是多个单词的前缀，则返回匹配的第一个单词的下标（最小下标）。如果 searchWord 不是任何单词的前缀，则返回 -1 。
字符串 s 的 前缀 是 s 的任何前导连续子字符串。
示例 1：
输入：sentence = "i love eating burger", searchWord = "burg"
输出：4
解释："burg" 是 "burger" 的前缀，而 "burger" 是句子中第 4 个单词。
示例 2：
输入：sentence = "this problem is an easy problem", searchWord = "pro"
输出：2
解释："pro" 是 "problem" 的前缀，而 "problem" 是句子中第 2 个也是第 6 个单词，但是应该返回最小下标 2 。
示例 3：
输入：sentence = "i am tired", searchWord = "you"
输出：-1
解释："you" 不是句子中任何单词的前缀。
提示：
- 1 <= sentence.length <= 100
- 1 <= searchWord.length <= 10
- sentence 由小写英文字母和空格组成。
- searchWord 由小写英文字母组成。
三、解答
1，非官方解法
1 | |
2，官方解法
【一天一题—Day31】654. 最大二叉树
一、前景提要
递归
二、题目
难度：中等
给定一个不重复的整数数组 nums 。 最大二叉树 可以用下面的算法从 nums 递归地构建:
创建一个根节点，其值为 nums 中的最大值。
递归地在最大值 左边 的 子数组前缀上 构建左子树。
递归地在最大值 右边 的 子数组后缀上 构建右子树。
返回 nums 构建的 最大二叉树 。
示例 1：
输入：nums = [3,2,1,6,0,5]
输出：[6,3,5,null,2,0,null,null,1]
解释：递归调用如下所示：
- [3,2,1,6,0,5] 中的最大值是 6 ，左边部分是 [3,2,1] ，右边部分是 [0,5] 。
- [3,2,1] 中的最大值是 3 ，左边部分是 [] ，右边部分是 [2,1] 。
- 空数组，无子节点。
- [2,1] 中的最大值是 2 ，左边部分是 [] ，右边部分是 [1] 。
- 空数组，无子节点。
- 只有一个元素，所以子节点是一个值为 1 的节点。
- [0,5] 中的最大值是 5 ，左边部分是 [0] ，右边部分是 [] 。
- 只有一个元素，所以子节点是一个值为 0 的节点。
- 空数组，无子节点。
示例 2：
输入：nums = [3,2,1]
输出：[3,null,2,null,1]
提示：
- 1 <= nums.length <= 1000
- 0 <= nums[i] <= 1000
- nums 中的所有整数 互不相同
三、解答
1，非官方解法
1 | |
2，官方解法
【一天一题—Day30】1450. 在既定时间做作业的学生人数
一、前景提要
简单题没啥好说的
二、题目
难度：简单
给你两个整数数组 startTime（开始时间）和 endTime（结束时间），并指定一个整数 queryTime 作为查询时间。
已知，第 i 名学生在 startTime[i] 时开始写作业并于 endTime[i] 时完成作业。
请返回在查询时间 queryTime 时正在做作业的学生人数。形式上，返回能够使 queryTime 处于区间 [startTime[i], endTime[i]]（含）的学生人数。
示例 1：
输入：startTime = [1,2,3], endTime = [3,2,7], queryTime = 4
输出：1
解释：一共有 3 名学生。
第一名学生在时间 1 开始写作业，并于时间 3 完成作业，在时间 4 没有处于做作业的状态。
第二名学生在时间 2 开始写作业，并于时间 2 完成作业，在时间 4 没有处于做作业的状态。
第三名学生在时间 3 开始写作业，预计于时间 7 完成作业，这是是唯一一名在时间 4 时正在做作业的学生。
示例 2：
输入：startTime = [4], endTime = [4], queryTime = 4
输出：1
解释：在查询时间只有一名学生在做作业。
示例 3：
输入：startTime = [4], endTime = [4], queryTime = 5
输出：0
示例 4：
输入：startTime = [1,1,1,1], endTime = [1,3,2,4], queryTime = 7
输出：0
示例 5：
输入：startTime = [9,8,7,6,5,4,3,2,1], endTime = [10,10,10,10,10,10,10,10,10], queryTime = 5
输出：5
提示：
- startTime.length == endTime.length
- 1 <= startTime.length <= 100
- 1 <= startTime[i] <= endTime[i] <= 1000
- 1 <= queryTime <= 1000
三、解答
1，非官方解法
1 | |
2，官方解法
多个差分数组的解法
官方解法
*【一天一题—Day29】1224. 最大相等频率
一、前景提要
二、题目
难度：困难
给你一个正整数数组 nums，请你帮忙从该数组中找出能满足下面要求的 最长 前缀，并返回该前缀的长度：
从前缀中 恰好删除一个 元素后，剩下每个数字的出现次数都相同。
如果删除这个元素后没有剩余元素存在，仍可认为每个数字都具有相同的出现次数（也就是 0 次）。
示例 1：
输入：nums = [2,2,1,1,5,3,3,5]
输出：7
解释：对于长度为 7 的子数组 [2,2,1,1,5,3,3]，如果我们从中删去 nums[4] = 5，就可以得到 [2,2,1,1,3,3]，里面每个数字都出现了两次。
示例 2：
输入：nums = [1,1,1,2,2,2,3,3,3,4,4,4,5]
输出：13
提示：
- 2 <= nums.length <= 105
- 1 <= nums[i] <= 105
三、解答
1，非官方解法
1 | |
2，官方解法
哈希表
官方解法
【一天一题—Day28】1302. 层数最深叶子节点的和
一、前景提要
看到二叉树就得思考一下递归
二、题目
难度：中等
给你一棵二叉树的根节点 root ，请你返回 层数最深的叶子节点的和 。
示例：
示例 2：
输入：root = [6,7,8,2,7,1,3,9,null,1,4,null,null,null,5]
输出：19
提示：
- 树中节点数目在范围 [1, 104] 之间。
- 1 <= Node.val <= 100
三、解答
1，非官方解法
dfs，最开始我只写了简单的dfs但是有问题，题目说的最深层的我以为每个子树最深加起来就行，后来才发现是最深层的和，不是最深层的不算
1 | |
2，官方解法
【一天一题—Day27】1656. 设计有序流
一、前景提要
今天题目……翻译的背大锅
二、题目
难度：中等
有 n 个 (id, value) 对，其中 id 是 1 到 n 之间的一个整数，value 是一个字符串。不存在 id 相同的两个 (id, value) 对。
设计一个流，以 任意 顺序获取 n 个 (id, value) 对，并在多次调用时 按 id 递增的顺序 返回一些值。
实现 OrderedStream 类：
- OrderedStream(int n) 构造一个能接收 n 个值的流，并将当前指针 ptr 设为 1 。
- String[] insert(int id, String value) 向流中存储新的 (id, value) 对。存储后：
-- 如果流存储有 id = ptr 的 (id, value) 对，则找出从 id = ptr 开始的 最长 id 连续递增序列 ，并 按顺序 返回与这些 id 关联的值的列表。然后，将 ptr 更新为最后那个 id + 1 。
-- 否则，返回一个空列表。
示例：
输入
["OrderedStream", "insert", "insert", "insert", "insert", "insert"]
[[5], [3, "ccccc"], [1, "aaaaa"], [2, "bbbbb"], [5, "eeeee"], [4, "ddddd"]]
输出
[null, [], ["aaaaa"], ["bbbbb", "ccccc"], [], ["ddddd", "eeeee"]]
解释
OrderedStream os= new OrderedStream(5);
os.insert(3, "ccccc"); // 插入 (3, "ccccc")，返回 []
os.insert(1, "aaaaa"); // 插入 (1, "aaaaa")，返回 ["aaaaa"]
os.insert(2, "bbbbb"); // 插入 (2, "bbbbb")，返回 ["bbbbb", "ccccc"]
os.insert(5, "eeeee"); // 插入 (5, "eeeee")，返回 []
os.insert(4, "ddddd"); // 插入 (4, "ddddd")，返回 ["ddddd", "eeeee"]
提示：
- 1 <= n <= 1000
- 1 <= id <= n
- value.length == 5
- value 仅由小写字母组成
- 每次调用 insert 都会使用一个唯一的 id
- 恰好调用 n 次 insert
三、解答
1，非官方解法
题目不容易懂，结合代码就很好懂了
1 | |
2，官方解法
*【一天一题—Day26】641. 设计循环双端队列
一、前景提要
还行
二、题目
难度：中等
设计实现双端队列。
实现 MyCircularDeque 类:
- MyCircularDeque(int k) ：构造函数,双端队列最大为 k 。
- boolean insertFront()：将一个元素添加到双端队列头部。 如果操作成功返回 true ，否则返回 false 。
- boolean insertLast() ：将一个元素添加到双端队列尾部。如果操作成功返回 true ，否则返回 false 。
- boolean deleteFront() ：从双端队列头部删除一个元素。 如果操作成功返回 true ，否则返回 false 。
- boolean deleteLast() ：从双端队列尾部删除一个元素。如果操作成功返回 true ，否则返回 false 。
- int getFront() )：从双端队列头部获得一个元素。如果双端队列为空，返回 -1 。
- int getRear() ：获得双端队列的最后一个元素。 如果双端队列为空，返回 -1 。
- boolean isEmpty() ：若双端队列为空，则返回 true ，否则返回 false 。
- boolean isFull() ：若双端队列满了，则返回 true ，否则返回 false 。
示例 1：
输入
["MyCircularDeque", "insertLast", "insertLast", "insertFront", "insertFront", "getRear", "isFull", "deleteLast", "insertFront", "getFront"]
[[3], [1], [2], [3], [4], [], [], [], [4], []]
输出
[null, true, true, true, false, 2, true, true, true, 4]
解释
MyCircularDeque circularDeque = new MycircularDeque(3); // 设置容量大小为3
circularDeque.insertLast(1); // 返回 true
circularDeque.insertLast(2); // 返回 true
circularDeque.insertFront(3); // 返回 true
circularDeque.insertFront(4); // 已经满了，返回 false
circularDeque.getRear(); // 返回 2
circularDeque.isFull(); // 返回 true
circularDeque.deleteLast(); // 返回 true
circularDeque.insertFront(4); // 返回 true
circularDeque.getFront(); // 返回 4
提示：
- 1 <= k <= 1000
- 0 <= value <= 1000
- insertFront, insertLast, deleteFront, deleteLast, getFront, getRear, isEmpty, isFull 调用次数不大于 2000 次
三、解答
1，非官方解法
有个可以整活的就是用双端队列实现双端队列哈哈哈
1 | |
2，官方解法
可以看一下的
官方解法
【一天一题—Day25】1422. 分割字符串的最大得分
一、前景提要
今天题目……翻译的背大锅
二、题目
难度：简单
给你一个由若干 0 和 1 组成的字符串 s ，请你计算并返回将该字符串分割成两个 非空 子字符串（即 左 子字符串和 右 子字符串）所能获得的最大得分。
「分割字符串的得分」为 左 子字符串中 0 的数量加上 右 子字符串中 1 的数量。
示例1：
输入：s = "011101"
输出：5
解释：
将字符串 s 划分为两个非空子字符串的可行方案有：
左子字符串 = "0" 且 右子字符串 = "11101"，得分 = 1 + 4 = 5
左子字符串 = "01" 且 右子字符串 = "1101"，得分 = 1 + 3 = 4
左子字符串 = "011" 且 右子字符串 = "101"，得分 = 1 + 2 = 3
左子字符串 = "0111" 且 右子字符串 = "01"，得分 = 1 + 1 = 2
左子字符串 = "01110" 且 右子字符串 = "1"，得分 = 2 + 1 = 3
示例2：
输入：s = "00111"
输出：5
解释：当 左子字符串 = "00" 且 右子字符串 = "111" 时，我们得到最大得分 = 2 + 3 = 5
示例 3：
输入：s = "1111"
输出：3
提示：
- 2 <= s.length <= 500
- 字符串 s 仅由字符 ‘0’ 和 ‘1’ 组成。
三、解答
1，非官方解法
执行用时：1880 ms, 在所有 Java 提交中击败了5.74%的用户
内存消耗：41.8 MB, 在所有 Java 提交中击败了5.07%的用户
笑熄了
1 | |
2，官方解法
【一天一题—Day24】1282. 用户分组
一、前景提要
今天题目……翻译的背大锅
二、题目
难度：中等
有 n 个人被分成数量未知的组。每个人都被标记为一个从 0 到 n - 1 的唯一ID 。
给定一个整数数组 groupSizes ，其中 groupSizes[i] 是第 i 个人所在的组的大小。例如，如果 groupSizes[1] = 3 ，则第 1 个人必须位于大小为 3 的组中。
返回一个组列表，使每个人 i 都在一个大小为 groupSizes[i] 的组中。
每个人应该 恰好只 出现在 一个组 中，并且每个人必须在一个组中。如果有多个答案，返回其中 任何 一个。可以 保证 给定输入 至少有一个 有效的解。
示例1：
输入：groupSizes = [3,3,3,3,3,1,3]
输出：[[5],[0,1,2],[3,4,6]]
解释：
第一组是 [5]，大小为 1，groupSizes[5] = 1。
第二组是 [0,1,2]，大小为 3，groupSizes[0] = groupSizes[1] = groupSizes[2] = 3。
第三组是 [3,4,6]，大小为 3，groupSizes[3] = groupSizes[4] = groupSizes[6] = 3。
其他可能的解决方案有 [[2,1,6],[5],[0,4,3]] 和 [[5],[0,6,2],[4,3,1]]。
示例2：
输入：groupSizes = [2,1,3,3,3,2]
输出：[[1],[0,5],[2,3,4]]
提示：
- groupSizes.length == n
- 1 <= n <= 500
- 1 <= groupSizes[i] <= n
三、解答
1，非官方解法
参考
这应该是最容易理解的思路了
1 | |
2，官方解法
看不太懂，懒得看
官方解法
【一天一题—Day23】1417. 重新格式化字符串
一、前景提要
略
二、题目
难度：简单
给你一个混合了数字和字母的字符串 s，其中的字母均为小写英文字母。
请你将该字符串重新格式化，使得任意两个相邻字符的类型都不同。也就是说，字母后面应该跟着数字，而数字后面应该跟着字母。
请你返回 重新格式化后 的字符串；如果无法按要求重新格式化，则返回一个 空字符串 。
示例1：
输入：s = "a0b1c2"
输出："0a1b2c"
解释："0a1b2c" 中任意两个相邻字符的类型都不同。 "a0b1c2", "0a1b2c", "0c2a1b" 也是满足题目要求的答案。
示例2：
输入：s = "leetcode"
输出：""
解释："leetcode" 中只有字母，所以无法满足重新格式化的条件。
示例 3：
输入：s = "1229857369"
输出：""
解释："1229857369" 中只有数字，所以无法满足重新格式化的条件。
示例 4：
输入：s = "covid2019"
输出："c2o0v1i9d"
示例 5：
输入：s = "ab123"
输出："1a2b3"
提示：
- 1 <= s.length <= 500
- s 仅由小写英文字母和/或数字组成。
三、解答
1，非官方解法
先把字符串进行排序，排序后数字在前字母在后，用双指针和StringBuffer进行组合，如果字符串长度是奇数，判断字符串中间位置的是数字还是字母，如果是数字说明数字多，该位置的字符得插到末尾，反之是头
1 | |
2，官方解法
【一天一题—Day22】640. 求解方程
一、前景提要
略
二、题目
难度：中等
求解一个给定的方程，将x以字符串 "x=#value" 的形式返回。该方程仅包含 '+' ， '-' 操作，变量 x 和其对应系数。
如果方程没有解，请返回 "No solution" 。如果方程有无限解，则返回 “Infinite solutions” 。
题目保证，如果方程中只有一个解，则 'x' 的值是一个整数。
示例1：
输入：nums = [-3,2,-3,4,2]
输出：5
解释：如果你选择 startValue = 4，在第三次累加时，和小于 1 。
累加求和
startValue = 4 | startValue = 5 | nums
(4 -3 ) = 1 | (5 -3 ) = 2 | -3
(1 +2 ) = 3 | (2 +2 ) = 4 | 2
(3 -3 ) = 0 | (4 -3 ) = 1 | -3
(0 +4 ) = 4 | (1 +4 ) = 5 | 4
(4 +2 ) = 6 | (5 +2 ) = 7 | 2
示例2：
输入：nums = [1,2]
输出：1
解释：最小的 startValue 需要是正数。
示例 3：
输入：nums = [1,-2,-3]
输出：5
提示：
- 1 <= nums.length <= 100
- -100 <= nums[i] <= 100
三、解答
1，非官方解法
buhui
2，官方解法
1 | |
【一天一题—Day21】1413. 逐步求和得到正数的最小值
一、前景提要
略
二、题目
难度：ez
给你一个整数数组 nums 。你可以选定任意的 正数 startValue 作为初始值。
你需要从左到右遍历 nums 数组，并将 startValue 依次累加上 nums 数组中的值。
请你在确保累加和始终大于等于 1 的前提下，选出一个最小的 正数 作为 startValue 。
示例1：
输入：nums = [-3,2,-3,4,2]
输出：5
解释：如果你选择 startValue = 4，在第三次累加时，和小于 1 。
累加求和
startValue = 4 | startValue = 5 | nums
(4 -3 ) = 1 | (5 -3 ) = 2 | -3
(1 +2 ) = 3 | (2 +2 ) = 4 | 2
(3 -3 ) = 0 | (4 -3 ) = 1 | -3
(0 +4 ) = 4 | (1 +4 ) = 5 | 4
(4 +2 ) = 6 | (5 +2 ) = 7 | 2
示例2：
输入：nums = [1,2]
输出：1
解释：最小的 startValue 需要是正数。
示例 3：
输入：nums = [1,-2,-3]
输出：5
提示：
- 1 <= nums.length <= 100
- -100 <= nums[i] <= 100
三、解答
1，非官方解法
1 | |
2，官方解法
*【一天一题—Day20】761. 特殊的二进制序列
一、前景提要
略
二、题目
难度：hard
特殊的二进制序列是具有以下两个性质的二进制序列：
- 0 的数量与 1 的数量相等。
- 二进制序列的每一个前缀码中 1 的数量要大于等于 0 的数量。
-
给定一个特殊的二进制序列 S，以字符串形式表示。定义一个操作 为首先选择 S 的两个连续且非空的特殊的子串，然后将它们交换。（两个子串为连续的当且仅当第一个子串的最后一个字符恰好为第二个子串的第一个字符的前一个字符。)
在任意次数的操作之后，交换后的字符串按照字典序排列的最大的结果是什么？
示例1：
输入：words = ["mass","as","hero","superhero"]
输出：["as","hero"]
解释："as" 是 "mass" 的子字符串，"hero" 是 "superhero" 的子字符串。
["hero","as"] 也是有效的答案。
示例2：
输入: S = "11011000"
输出: "11100100"
解释:
将子串 "10" （在S[1]出现） 和 "1100" （在S[3]出现）进行交换。
这是在进行若干次操作后按字典序排列最大的结果。
说明：
- S 的长度不超过 50。
- S 保证为一个满足上述定义的特殊 的二进制序列。
三、解答
1，非官方解法
- 1
- 2
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22class Solution {
public String makeLargestSpecial(String s) {
int count=0,pre=0,n=s.length();
if(n==0){return "";}
List<String> list=new ArrayList<>();
for(int i=0;i<n;i++){
char c=s.charAt(i);
if(c=='1'){count++;}
else{
count--;
if(count==0){
list.add("1"+makeLargestSpecial(s.substring(pre+1,i))+"0");
pre=i+1;
}
}
}
Collections.sort(list);
String ans="";
for(int i=list.size()-1;i>=0;i--){ans+=list.get(i);}
return ans;
}
}
2，官方解法
*【一天一题—Day19】636. 函数的独占时间
一、前景提要
嗯哼
二、题目
难度：mid
有一个 单线程 CPU 正在运行一个含有 n 道函数的程序。每道函数都有一个位于 0 和 n-1 之间的唯一标识符。
函数调用 存储在一个 调用栈 上 ：当一个函数调用开始时，它的标识符将会推入栈中。而当一个函数调用结束时，它的标识符将会从栈中弹出。标识符位于栈顶的函数是 当前正在执行的函数 。每当一个函数开始或者结束时，将会记录一条日志，包括函数标识符、是开始还是结束、以及相应的时间戳。
给你一个由日志组成的列表 logs ，其中 logs[i] 表示第 i 条日志消息，该消息是一个按 "{function_id}:{"start" | "end"}:{timestamp}" 进行格式化的字符串。例如，"0:start:3" 意味着标识符为 0 的函数调用在时间戳 3 的 起始开始执行 ；而 "1:end:2" 意味着标识符为 1 的函数调用在时间戳 2 的 末尾结束执行。注意，函数可以 调用多次，可能存在递归调用 。
函数的 独占时间 定义是在这个函数在程序所有函数调用中执行时间的总和，调用其他函数花费的时间不算该函数的独占时间。例如，如果一个函数被调用两次，一次调用执行 2 单位时间，另一次调用执行 1 单位时间，那么该函数的 独占时间 为 2 + 1 = 3 。
以数组形式返回每个函数的 独占时间 ，其中第 i 个下标对应的值表示标识符 i 的函数的独占时间。
示例1：
输入：n = 2, logs = ["0:start:0","1:start:2","1:end:5","0:end:6"]
输出：[3,4]
解释：
函数 0 在时间戳 0 的起始开始执行，执行 2 个单位时间，于时间戳 1 的末尾结束执行。
函数 1 在时间戳 2 的起始开始执行，执行 4 个单位时间，于时间戳 5 的末尾结束执行。
函数 0 在时间戳 6 的开始恢复执行，执行 1 个单位时间。
所以函数 0 总共执行 2 + 1 = 3 个单位时间，函数 1 总共执行 4 个单位时间。
示例2：
输入：n = 1, logs = ["0:start:0","0:start:2","0:end:5","0:start:6","0:end:6","0:end:7"]
输出：[8]
解释：
函数 0 在时间戳 0 的起始开始执行，执行 2 个单位时间，并递归调用它自身。
函数 0（递归调用）在时间戳 2 的起始开始执行，执行 4 个单位时间。
函数 0（初始调用）恢复执行，并立刻再次调用它自身。
函数 0（第二次递归调用）在时间戳 6 的起始开始执行，执行 1 个单位时间。
函数 0（初始调用）在时间戳 7 的起始恢复执行，执行 1 个单位时间。
所以函数 0 总共执行 2 + 4 + 1 + 1 = 8 个单位时间。
示例3：
输入：n = 2, logs = ["0:start:0","0:start:2","0:end:5","1:start:6","1:end:6","0:end:7"]
输出：[7,1]
解释：
函数 0 在时间戳 0 的起始开始执行，执行 2 个单位时间，并递归调用它自身。
函数 0（递归调用）在时间戳 2 的起始开始执行，执行 4 个单位时间。
函数 0（初始调用）恢复执行，并立刻调用函数 1 。
函数 1在时间戳 6 的起始开始执行，执行 1 个单位时间，于时间戳 6 的末尾结束执行。
函数 0（初始调用）在时间戳 7 的起始恢复执行，执行 1 个单位时间，于时间戳 7 的末尾结束执行。
所以函数 0 总共执行 2 + 4 + 1 = 7 个单位时间，函数 1 总共执行 1 个单位时间。
示例4：
输入：n = 2, logs = ["0:start:0","0:start:2","0:end:5","1:start:7","1:end:7","0:end:8"]
输出：[8,1]
示例 5：
输入：n = 1, logs = ["0:start:0","0:end:0"]
输出：[1]
提示：
- 1 <= n <= 100
- 1 <= logs.length <= 500
- 0 <= function_id < n
- 0 <= timestamp <= 109
- 两个开始事件不会在同一时间戳发生
- 两个结束事件不会在同一时间戳发生
- 每道函数都有一个对应 “start” 日志的 “end” 日志
三、解答
1，非官方解法
1 | |
2，官方解法
【一天一题—Day18】1408. 数组中的字符串匹配
一、前景提要
爽
二、题目
难度：ez
给你一个字符串数组 words ，数组中的每个字符串都可以看作是一个单词。请你按 任意 顺序返回 words 中是其他单词的子字符串的所有单词。
如果你可以删除 words[j] 最左侧和/或最右侧的若干字符得到 word[i] ，那么字符串 words[i] 就是 words[j] 的一个子字符串。
示例1：
输入：words = ["mass","as","hero","superhero"]
输出：["as","hero"]
解释："as" 是 "mass" 的子字符串，"hero" 是 "superhero" 的子字符串。
["hero","as"] 也是有效的答案。
示例2：
输入：words = ["leetcode","et","code"]
输出：["et","code"]
解释："et" 和 "code" 都是 "leetcode" 的子字符串。
示例3：
输入：words = ["blue","green","bu"]
输出：[]
提示：
- 1 <= words.length <= 100
- 1 <= words[i].length <= 30
- words[i] 仅包含小写英文字母。
- 题目数据 保证 每个 words[i] 都是独一无二的。
三、解答
1，非官方解法
1 | |
2，官方解法
【一天一题—Day17】623. 在二叉树中增加一行
一、前景提要
爽
二、题目
难度：mid
给定一个二叉树的根 root 和两个整数 val 和 depth ，在给定的深度 depth 处添加一个值为 val 的节点行。
注意，根节点 root 位于深度 1 。
加法规则如下:
- 给定整数 depth，对于深度为 depth - 1 的每个非空树节点 cur ，创建两个值为 val 的树节点作为 cur 的左子树根和右子树根。
- cur 原来的左子树应该是新的左子树根的左子树。
- cur 原来的右子树应该是新的右子树根的右子树。
- 如果 depth == 1 意味着 depth - 1 根本没有深度，那么创建一个树节点，值 val 作为整个原始树的新根，而原始树就是新根的左子树。
示例1：
输入: root = [4,2,6,3,1,5], val = 1, depth = 2
输出: [4,1,1,2,null,null,6,3,1,5]
示例2：
输入: root = [4,2,null,3,1], val = 1, depth = 3
输出: [4,2,null,1,1,3,null,null,1]
提示：
- 节点数在 [1, 104] 范围内
- 树的深度在 [1, 104]范围内
- -100 <= Node.val <= 100
- -105 <= val <= 105
- 1 <= depth <= the depth of tree + 1
三、解答
1，非官方解法
DFS，递归往下层搜索，但是优雅版
1 | |
2，官方解法
DFS
官方解法
【一天一题—Day16】1403. 非递增顺序的最小子序列
一、前景提要
真解气。我永远相信PLA。
二、题目
难度：ez
给你一个数组 nums，请你从中抽取一个子序列，满足该子序列的元素之和 严格 大于未包含在该子序列中的各元素之和。
如果存在多个解决方案，只需返回 长度最小 的子序列。如果仍然有多个解决方案，则返回 元素之和最大 的子序列。
与子数组不同的地方在于，「数组的子序列」不强调元素在原数组中的连续性，也就是说，它可以通过从数组中分离一些（也可能不分离）元素得到。
注意，题目数据保证满足所有约束条件的解决方案是 唯一 的。同时，返回的答案应当按 非递增顺序 排列。
示例1：
输入：nums = [4,3,10,9,8]
输出：[10,9]
解释：子序列 [10,9] 和 [10,8] 是最小的、满足元素之和大于其他各元素之和的子序列。但是 [10,9] 的元素之和最大。
示例2：
输入：nums = [4,4,7,6,7]
输出：[7,7,6]
解释：子序列 [7,7] 的和为 14 ，不严格大于剩下的其他元素之和（14 = 4 + 4 + 6）。因此，[7,6,7] 是满足题意的最小子序列。注意，元素按非递增顺序返回。
示例3：
输入：nums = [6]
输出：[6]
提示：
- 1 <= nums.length <= 500
- 1 <= nums[i] <= 100
三、解答
1，非官方解法
1 | |
2，官方解法
贪心
官方解法
【一天一题—Day15】899. 有序队列
一、前景提要
java多线程何时我才能认真学完啊！……
二、题目
难度：困难
给定一个字符串 s 和一个整数 k 。你可以从 s 的前 k 个字母中选择一个，并把它加到字符串的末尾。
返回 在应用上述步骤的任意数量的移动后，字典上最小的字符串 。
示例1：
输入：s = "cba", k = 1
输出："acb"
解释：
在第一步中，我们将第一个字符（“c”）移动到最后，获得字符串 “bac”。
在第二步中，我们将第一个字符（“b”）移动到最后，获得最终结果 “acb”。
示例2：
输入：s = "baaca", k = 3
输出："aaabc"
解释：
在第一步中，我们将第一个字符（“b”）移动到最后，获得字符串 “aacab”。
在第二步中，我们将第三个字符（“c”）移动到最后，获得最终结果 “aaabc”。
提示：
- 1 <= k <= S.length <= 1000
- s 只由小写字母组成。
三、解答
1，非官方解法
巧妙的轮转思维（转盘）
Python/Java/TypeScript/Go 脑筋急转弯
结合图片，很好理解，思路难，代码简单
1 | |
2，官方解法
【一天一题—Day14】622. 设计循环队列
一、前景提要
java多线程何时我才能认真学完啊！……
二、题目
难度：中等
设计你的循环队列实现。 循环队列是一种线性数据结构，其操作表现基于 FIFO（先进先出）原则并且队尾被连接在队首之后以形成一个循环。它也被称为“环形缓冲器”。
循环队列的一个好处是我们可以利用这个队列之前用过的空间。在一个普通队列里，一旦一个队列满了，我们就不能插入下一个元素，即使在队列前面仍有空间。但是使用循环队列，我们能使用这些空间去存储新的值。
你的实现应该支持如下操作：
MyCircularQueue(k): 构造器，设置队列长度为 k 。
Front: 从队首获取元素。如果队列为空，返回 -1 。
Rear: 获取队尾元素。如果队列为空，返回 -1 。
enQueue(value): 向循环队列插入一个元素。如果成功插入则返回真。
deQueue(): 从循环队列中删除一个元素。如果成功删除则返回真。
isEmpty(): 检查循环队列是否为空。
isFull(): 检查循环队列是否已满。
示例1：
MyCircularQueue circularQueue = new MyCircularQueue(3); // 设置长度为 3
circularQueue.enQueue(1); // 返回 true
circularQueue.enQueue(2); // 返回 true
circularQueue.enQueue(3); // 返回 true
circularQueue.enQueue(4); // 返回 false，队列已满
circularQueue.Rear(); // 返回 3
circularQueue.isFull(); // 返回 true
circularQueue.deQueue(); // 返回 true
circularQueue.enQueue(4); // 返回 true
circularQueue.Rear(); // 返回 4
提示：
- 所有的值都在 0 至 1000 的范围内；
- 操作数将在 1 至 1000 的范围内；
- 请不要使用内置的队列库。
三、解答
1，非官方解法
很简单……感觉没什么好说的……高难度或者更优雅的看看其他人的写法吧……
1 | |
2，官方解法
【一天一题—Day13】1374. 生成每种字符都是奇数个的字符串
一、前景提要
略，我在思考要不要把一天一题合并成一篇然后保持更新算了呢？……
不然太多了，其他内容都被挡了，要不然就是学别人做个推荐阅读……或者换个主题，搞个有分区模块的那种……整个专门的算法专栏；再要不然就另外部署一个，只放算法博客，然后整个传送门！
还有，本菜鸡军迷祝人民解放军建军节快乐！
二、题目
难度：ez
给你一个整数 n，请你返回一个含 n 个字符的字符串，其中每种字符在该字符串中都恰好出现 奇数次 。
返回的字符串必须只含小写英文字母。如果存在多个满足题目要求的字符串，则返回其中任意一个即可。
示例1：
输入：n = 4
输出："pppz"
解释："pppz" 是一个满足题目要求的字符串，因为 'p' 出现 3 次，且 'z' 出现 1 次。当然，还有很多其他字符串也满足题目要求，比如："ohhh" 和 "love"。
示例2：
输入：n = 2
输出："xy"
解释："xy" 是一个满足题目要求的字符串，因为 'x' 和 'y' 各出现 1 次。当然，还有很多其他字符串也满足题目要求，比如："ag" 和 "ur"。
示例3：
输入：n = 7
输出："holasss"
提示：
- 1 <= n <= 500
三、解答
1，非官方解法
1 | |
2，官方解法
【一天一题—Day12】1161. 最大层内元素和
一、前景提要
yesterday……hard……🤐
二、题目
难度：中等
给你一个二叉树的根节点 root。设根节点位于二叉树的第 1 层，而根节点的子节点位于第 2 层，依此类推。
请返回层内元素之和 最大 的那几层（可能只有一层）的层号，并返回其中 最小 的那个。
示例1：
输入：root = [1,7,0,7,-8,null,null]
输出：2
解释：
第 1 层各元素之和为 1，
第 2 层各元素之和为 7 + 0 = 7，
第 3 层各元素之和为 7 + -8 = -1，
所以我们返回第 2 层的层号，它的层内元素之和最大。
示例2：
输入：root = [989,null,10250,98693,-89388,null,null,null,-32127]
输出：2
提示：
- 树中的节点数在 [1, 104]范围内
- -105 <= Node.val <= 105
三、解答
1，非官方解法
BFS，一层一层遍历
1 | |
2，官方解法
官方解法
BFS和DFS
【一天一题—Day10】593. 有效的正方形
一、前景提要
略
二、题目
难度：中等
给定2D空间中四个点的坐标 p1, p2, p3 和 p4，如果这四个点构成一个正方形，则返回 true 。
点的坐标 pi 表示为 [xi, yi] 。输入 不是 按任何顺序给出的。
一个 有效的正方形 有四条等边和四个等角(90度角)。
示例1：
输入: p1 = [0,0], p2 = [1,1], p3 = [1,0], p4 = [0,1]
输出: True
示例2：
输入：p1 = [0,0], p2 = [1,1], p3 = [1,0], p4 = [0,12]
输出：false
示例3：
输入：p1 = [1,0], p2 = [-1,0], p3 = [0,1], p4 = [0,-1]
输出：true
提示：
- p1.length == p2.length == p3.length == p4.length == 2
- -104 <= xi, yi <= 104
三、解答
1，非官方解法
比较投机取巧……用的是正方形的性质……
1 | |
2，官方解法
但是官方解法也没多牛
【一天一题—Day9】1331. 数组序号转换
一、前景提要
略
二、题目
难度：简单
给你一个整数数组 arr ，请你将数组中的每个元素替换为它们排序后的序号。
序号代表了一个元素有多大。序号编号的规则如下：
示例1：
输入：arr = [40,10,20,30]
输出：[4,1,2,3]
解释：40 是最大的元素。 10 是最小的元素。 20 是第二小的数字。 30 是第三小的数字。
示例2：
输入：arr = [100,100,100]
输出：[1,1,1]
解释：所有元素有相同的序号。
示例3：
输入：arr = [37,12,28,9,100,56,80,5,12]
输出：[5,3,4,2,8,6,7,1,3]
提示：
- 0 <= arr.length <= 105
- -109 <= arr[i] <= 109
三、解答
1，非官方解法
1 | |
2，官方解法
【一天一题—Day6】919. 完全二叉树插入器
一、前景提要
略
二、题目
难度：中等
完全二叉树 是每一层（除最后一层外）都是完全填充（即，节点数达到最大）的，并且所有的节点都尽可能地集中在左侧。
设计一种算法，将一个新节点插入到一个完整的二叉树中，并在插入后保持其完整。
实现 CBTInserter 类:
CBTInserter(TreeNode root) 使用头节点为 root 的给定树初始化该数据结构；
CBTInserter.insert(int v) 向树中插入一个值为 Node.val == val的新节点 TreeNode。使树保持完全二叉树的状态，并返回插入节点 TreeNode 的父节点的值；
CBTInserter.get_root() 将返回树的头节点。
示例1：
输入
["CBTInserter", "insert", "insert", "get_root"]
[[[1, 2]], [3], [4], []]
输出
[null, 1, 2, [1, 2, 3, 4]]
解释
CBTInserter cBTInserter = new CBTInserter([1, 2]);
cBTInserter.insert(3); // 返回 1
cBTInserter.insert(4); // 返回 2
cBTInserter.get_root(); // 返回 [1, 2, 3, 4]
提示：
- 树中节点数量范围为 [1, 1000]
- 0 <= Node.val <= 5000
- root 是完全二叉树
- 0 <= val <= 5000
- 每个测试用例最多调用 insert 和 get_root 操作 104 次
来源：力扣（LeetCode）
链接：https://leetcode.cn/problems/complete-binary-tree-inserter
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。
三、解答
1，非官方解法
1 | |
2，官方解法
【一天一题—Day5】1184. 公交站间的距离
一、前景提要
略
二、题目
难度：简单
环形公交路线上有 n 个站，按次序从 0 到 n - 1 进行编号。我们已知每一对相邻公交站之间的距离，distance[i] 表示编号为 i 的车站和编号为 (i + 1) % n 的车站之间的距离。
环线上的公交车都可以按顺时针和逆时针的方向行驶。
返回乘客从出发点 start 到目的地 destination 之间的最短距离。
示例1：
输入：distance = [1,2,3,4], start = 0, destination = 1
输出：1
解释：公交站 0 和 1 之间的距离是 1 或 9，最小值是 1。
示例2：
输入：distance = [1,2,3,4], start = 0, destination = 2
输出：3
解释：公交站 0 和 2 之间的距离是 3 或 7，最小值是 3。
示例3：
输入：distance = [1,2,3,4], start = 0, destination = 3
输出：4
解释：公交站 0 和 3 之间的距离是 6 或 4，最小值是 4。
提示：
- 1 <= n <= 10^4
- distance.length == n
- 0 <= start, destination < n
- 0 <= distance[i] <= 10^4
三、解答
1，非官方解法
1 | |
2，官方解法
【一天一题—Day4】剑指 Offer II 115. 重建序列
一、前景提要
昨天的是困难题就先略过了吧……去学游泳，笑死，第一次下水差点呛死……
二、题目
剑指 Offer II 115. 重建序列
难度：中等
给定一个长度为 n 的整数数组 nums ，其中 nums 是范围为 [1，n] 的整数的排列。
还提供了一个 2D 整数数组 sequences ，其中 sequences[i] 是 nums 的子序列。
检查 nums 是否是唯一的最短 超序列 。
最短 超序列 是 长度最短 的序列，并且所有序列 sequences[i] 都是它的子序列。
对于给定的数组 sequences ，可能存在多个有效的 超序列 。
- 例如，对于 sequences = [[1,2],[1,3]] ，有两个最短的 超序列 ，[1,2,3] 和 [1,3,2] 。
- 而对于 sequences = [[1,2],[1,3],[1,2,3]] ，唯一可能的最短 超序列 是 [1,2,3] 。
[1,2,3,4] 是可能的超序列，但不是最短的。
如果 nums 是序列的唯一最短 超序列 ，则返回 true ，否则返回 false 。
子序列 是一个可以通过从另一个序列中删除一些元素或不删除任何元素，而不改变其余元素的顺序的序列。
示例1：
输入：nums = [1,2,3], sequences = [[1,2],[1,3]]
输出：false
解释：有两种可能的超序列：[1,2,3]和[1,3,2]。
序列 [1,2] 是[1,2,3]和[1,3,2]的子序列。
序列 [1,3] 是[1,2,3]和[1,3,2]的子序列。
因为 nums 不是唯一最短的超序列，所以返回false。
示例2：
输入：nums = [1,2,3], sequences = [[1,2]]
输出：false
解释：最短可能的超序列为 [1,2]。
序列 [1,2] 是它的子序列：[1,2]。
因为 nums 不是最短的超序列，所以返回false。
示例3：
输入：nums = [1,2,3], sequences = [[1,2],[1,3],[2,3]]
输出：true
解释：最短可能的超序列为[1,2,3]。
序列 [1,2] 是它的一个子序列：[1,2,3]。
序列 [1,3] 是它的一个子序列：[1,2,3]。
序列 [2,3] 是它的一个子序列：[1,2,3]。
因为 nums 是唯一最短的超序列，所以返回true。
提示：
- n == nums.length
- 1 <= n <= 104
- nums 是 [1, n] 范围内所有整数的排列
- 1 <= sequences.length <= 104
- 1 <= sequences[i].length <= 104
- 1 <= sum(sequences[i].length) <= 105
- 1 <= sequences[i][j] <= n
- sequences 的所有数组都是 唯一 的
- sequences[i] 是 nums 的一个子序列
三、解答
简单题我重拳出击！……？
题目我就读了好久，看半天才理解题意
而且因为我状态全无，二维数组的列数行数一直在混淆，边界处理一直在写，一直在犯低级错误
即使最后写好了，因为是暴力解法也没有太大参考意义，即使是这样都花费了我数个小时，我真是服了，状态真的太差了……
1，非官方解法
官方题解是拓扑排序，具体看下个，我用的别人的想法
1 | |
2，官方解法
【一天一题—Day2】814. 二叉树剪枝
一、前景提要
今天在装修我的GitHub主页……嗯……也是很费时的一件事……
而且组好了双屏，向着tech otaku迈进一大步！
效果图：
日后补上装修过程
重复补齐一下前景提要：
距离我尽量维持一天一题已经过去了一个月，整个6月份都在忙期末作业、期末复习和期末实训，放暑假后一直在打电动，在装修博客，导致我一天一题是鸽了又鸽，状态全无。
这让本就是菜鸡的我，又彻底变回纯飞舞，还是连题目都读不太懂的那种。
所以我决心恢复往日的状态。
二、题目
难度：中等
给你二叉树的根结点 root ，此外树的每个结点的值要么是 0 ，要么是 1 。
返回移除了所有不包含 1 的子树的原二叉树。
节点 node 的子树为 node 本身加上所有 node 的后代。
示例1：
输入：root = [1,null,0,0,1]
输出：[1,null,0,null,1]
解释：
只有红色节点满足条件“所有不包含 1 的子树”。 右图为返回的答案。
示例2：
输入：root = [1,0,1,0,0,0,1]
输出：[1,null,1,null,1]
示例3：
输入：root = [1,1,0,1,1,0,1,0]
输出：[1,1,0,1,1,null,1]
提示：
- 树中节点的数目在范围 [1, 200] 内
- Node.val 为 0 或 1
三、解答
看到二叉树，第一反应就是想想能不能用回溯算法
题目的要求：如果有一个二叉树，他的子树里没有1，删掉这个二叉树
思路：一个点去往下找下一个点看看符不符合条件再往上返回，回溯（递归）算法的基操
1，回溯算法
1 | |
2，官方解法
之前做过剪枝的变种题，原题做起来还行
看看官方题解
一样，那没事了。
【一天一题—Day1】1260. 二维网格迁移
一、前景提要
距离我尽量维持一天一题已经过去了一个月，整个6月份都在忙期末作业、期末复习和期末实训，放暑假后一直在打电动，在装修博客，导致我一天一题是鸽了又鸽，状态全无。
这让本就是菜鸡的我，又彻底变回纯飞舞，还是连题目都读不太懂的那种。
所以我决心恢复往日的状态。
二、题目
难度：简单
给你一个 m 行 n 列的二维网格 grid 和一个整数 k。你需要将 grid 迁移 k 次。
每次「迁移」操作将会引发下述活动：
位于 grid[i][j] 的元素将会移动到 grid[i][j + 1]。
位于 grid[i][n - 1] 的元素将会移动到 grid[i + 1][0]。
位于 grid[m - 1][n - 1] 的元素将会移动到 grid[0][0]。
请你返回 k 次迁移操作后最终得到的 二维网格。
示例1：
输入：grid = [[1,2,3],[4,5,6],[7,8,9]], k = 1
输出：[[9,1,2],[3,4,5],[6,7,8]]
示例2：
输入：grid = [[3,8,1,9],[19,7,2,5],[4,6,11,10],[12,0,21,13]], k = 4
输出：[[12,0,21,13],[3,8,1,9],[19,7,2,5],[4,6,11,10]]
示例3：
输入：grid = [[1,2,3],[4,5,6],[7,8,9]], k = 9
输出：[[1,2,3],[4,5,6],[7,8,9]]
提示：
- m == grid.length
- n == grid[i].length
- 1 <= m <= 50
- 1 <= n <= 50
- -1000 <= grid[i][j] <= 1000
- 0 <= k <= 100
三、解答
简单题我重拳出击！……？
题目我就读了好久，看半天才理解题意
而且因为我状态全无，二维数组的列数行数一直在混淆，边界处理一直在写，一直在犯低级错误
即使最后写好了，因为是暴力解法也没有太大参考意义，即使是这样都花费了我数个小时，我真是服了，状态真的太差了……
1，暴力解法
1 | |
2，官方解法
还是看看远处的官方题解吧家人们
拍扁
转换成一维数组，迁移操作前每个元素的下标为：index = i * n + j
然后循环右移
k次迁移后下标变成：index1 = (index + k) % (m * n)
最后是还原
一维数组再变回二维，行号就是⌊index1 / n⌋，列号是index1 % n
⌊x⌋：地板函数，或取整函数，表示小于 x 的最大整数；⌈x⌉：天花板函数，表示大于 x 的最小整数。
我好像完全理解了……？😤后天再来做做看。
【一天一题】力扣刷题日记
https://moechun.fun/2022/08/11/【一天一题】力扣刷题日记/