家庭成员之间需要用语言表达感情 2022.2.22
极简生活,不乱买东西, 买东西前思考家庭存货 2022.3.8
人生要事
67. 二进制求和
给你两个二进制字符串 a 和 b ,以二进制字符串的形式返回它们的和。
示例 1:
输入:a = “11”, b = “1”
输出:”100”
示例 2:
输入:a = “1010”, b = “1011”
输出:”10101”
提示:
1 <= a.length, b.length <= 104
a 和 b 仅由字符 ‘0’ 或 ‘1’ 组成
字符串如果不是 “0” ,就不含前导零
模拟加法
1 | class Solution { |
66. 加一
给定一个由 整数 组成的 非空 数组所表示的非负整数,在该数的基础上加一。
最高位数字存放在数组的首位, 数组中每个元素只存储单个数字。
你可以假设除了整数 0 之外,这个整数不会以零开头。
示例 1:
输入:digits = [1,2,3]
输出:[1,2,4]
解释:输入数组表示数字 123。
示例 2:
输入:digits = [4,3,2,1]
输出:[4,3,2,2]
解释:输入数组表示数字 4321。
示例 3:
输入:digits = [0]
输出:[1]
方法一 模拟加法
主要是要考虑进位的情况
1 | class Solution { |
方法二 考虑最右边9的个数即可
由于本题情况特殊,只需要+1,所以只需要考虑最右边9的个数即可,然后将倒数第一个非9的数加1,
如果全部为9,则所有数全部设置为0,新增最高位为1。
1 | class Solution { |
58. 最后一个单词的长度
给你一个字符串 s,由若干单词组成,单词前后用一些空格字符隔开。返回字符串中 最后一个 单词的长度。
单词 是指仅由字母组成、不包含任何空格字符的最大子字符串。
示例 1:
输入:s = “Hello World”
输出:5
解释:最后一个单词是“World”,长度为5。
示例 2:
输入:s = “ fly me to the moon “
输出:4
解释:最后一个单词是“moon”,长度为4。
示例 3:
输入:s = “luffy is still joyboy”
输出:6
解释:最后一个单词是长度为6的“joyboy”。
方法一:从左到右顺序遍历
双指针记录单词开头和结尾,单词开头为空字符串后的第一个字符;单词结尾为单词开头往后遍历直到碰到空格为止
1 | class Solution { |
方法二:从后向左遍历
如果最右边为空格,需要跳过
从最右边第一个非空字符开始向左遍历,直到碰到空格或者左边界为止。
1 | class Solution { |
27. 移除元素
给你一个数组 nums 和一个值 val,你需要 原地 移除所有数值等于 val 的元素,并返回移除后数组的新长度。
不要使用额外的数组空间,你必须仅使用 O(1) 额外空间并 原地 修改输入数组。
元素的顺序可以改变。你不需要考虑数组中超出新长度后面的元素。
说明:
为什么返回数值是整数,但输出的答案是数组呢?
请注意,输入数组是以「引用」方式传递的,这意味着在函数里修改输入数组对于调用者是可见的。
你可以想象内部操作如下:
// nums 是以“引用”方式传递的。也就是说,不对实参作任何拷贝
int len = removeElement(nums, val);
// 在函数里修改输入数组对于调用者是可见的。
// 根据你的函数返回的长度, 它会打印出数组中 该长度范围内 的所有元素。
for (int i = 0; i < len; i++) {
print(nums[i]);
}
示例 1:
输入:nums = [3,2,2,3], val = 3
输出:2, nums = [2,2]
解释:函数应该返回新的长度 2, 并且 nums 中的前两个元素均为 2。你不需要考虑数组中超出新长度后面的元素。例如,函数返回的新长度为 2 ,而 nums = [2,2,3,3] 或 nums = [2,2,0,0],也会被视作正确答案。
示例 2:
输入:nums = [0,1,2,2,3,0,4,2], val = 2
输出:5, nums = [0,1,4,0,3]
解释:函数应该返回新的长度 5, 并且 nums 中的前五个元素为 0, 1, 3, 0, 4。注意这五个元素可为任意顺序。你不需要考虑数组中超出新长度后面的元素。
1 | class Solution { |
26. 删除有序数组中的重复项
给你一个 升序排列 的数组 nums ,请你 原地 删除重复出现的元素,使每个元素 只出现一次 ,返回删除后数组的新长度。元素的 相对顺序 应该保持 一致 。
由于在某些语言中不能改变数组的长度,所以必须将结果放在数组nums的第一部分。更规范地说,如果在删除重复项之后有 k 个元素,那么 nums 的前 k 个元素应该保存最终结果。
将最终结果插入 nums 的前 k 个位置后返回 k 。
不要使用额外的空间,你必须在 原地 修改输入数组 并在使用 O(1) 额外空间的条件下完成。
判题标准:
系统会用下面的代码来测试你的题解:
int[] nums = […]; // 输入数组
int[] expectedNums = […]; // 长度正确的期望答案
int k = removeDuplicates(nums); // 调用
assert k == expectedNums.length;
for (int i = 0; i < k; i++) {
assert nums[i] == expectedNums[i];
}
如果所有断言都通过,那么您的题解将被 通过。
示例 1:
输入:nums = [1,1,2]
输出:2, nums = [1,2,_]
解释:函数应该返回新的长度 2 ,并且原数组 nums 的前两个元素被修改为 1, 2 。不需要考虑数组中超出新长度后面的元素。
示例 2:
输入:nums = [0,0,1,1,1,2,2,3,3,4]
输出:5, nums = [0,1,2,3,4]
解释:函数应该返回新的长度 5 , 并且原数组 nums 的前五个元素被修改为 0, 1, 2, 3, 4 。不需要考虑数组中超出新长度后面的元素。
提示:
1 <= nums.length <= 3 * 104
-104 <= nums[i] <= 104
nums 已按 升序 排列
1 | class Solution { |
21. 合并两个有序链表
两个升序链表合并为一个新的 升序 链表并返回。新链表是通过拼接给定的两个链表的所有节点组成的。
示例 1:
输入:l1 = [1,2,4], l2 = [1,3,4]
输出:[1,1,2,3,4,4]
示例 2:
输入:l1 = [], l2 = []
输出:[]
示例 3:
输入:l1 = [], l2 = [0]
输出:[0]
提示:
两个链表的节点数目范围是 [0, 50]
-100 <= Node.val <= 100
l1 和 l2 均按 非递减顺序 排列
1 | struct ListNode { |
13. 罗马数字转整数
罗马数字包含以下七种字符: I, V, X, L,C,D 和 M。
字符 数值
I 1
V 5
X 10
L 50
C 100
D 500
M 1000
例如, 罗马数字 2 写做 II ,即为两个并列的 1 。12 写做 XII ,即为 X + II 。 27 写做 XXVII, 即为 XX + V + II 。
通常情况下,罗马数字中小的数字在大的数字的右边。但也存在特例,例如 4 不写做 IIII,而是 IV。数字 1 在数字 5 的左边,所表示的数等于大数 5 减小数 1 得到的数值 4 。同样地,数字 9 表示为 IX。这个特殊的规则只适用于以下六种情况:
I 可以放在 V (5) 和 X (10) 的左边,来表示 4 和 9。
X 可以放在 L (50) 和 C (100) 的左边,来表示 40 和 90。
C 可以放在 D (500) 和 M (1000) 的左边,来表示 400 和 900。
给定一个罗马数字,将其转换成整数。
示例 1:
输入: s = “III”
输出: 3
示例 2:
输入: s = “IV”
输出: 4
示例 3:
输入: s = “IX”
输出: 9
示例 4:
输入: s = “LVIII”
输出: 58
解释: L = 50, V= 5, III = 3.
示例 5:
输入: s = “MCMXCIV”
输出: 1994
解释: M = 1000, CM = 900, XC = 90, IV = 4.
提示:
1 <= s.length <= 15
s 仅含字符 (‘I’, ‘V’, ‘X’, ‘L’, ‘C’, ‘D’, ‘M’)
题目数据保证 s 是一个有效的罗马数字,且表示整数在范围 [1, 3999] 内
题目所给测试用例皆符合罗马数字书写规则,不会出现跨位等情况。
IL 和 IM 这样的例子并不符合题目要求,49 应该写作 XLIX,999 应该写作 CMXCIX 。
关于罗马数字的详尽书写规则,可以参考 罗马数字 - Mathematics 。
1 | class Solution { |
1796. 字符串中第二大的数字
给你一个混合字符串 s ,请你返回 s 中 第二大 的数字,如果不存在第二大的数字,请你返回 -1 。
混合字符串 由小写英文字母和数字组成。
示例 1:
输入:s = “dfa12321afd”
输出:2
解释:出现在 s 中的数字包括 [1, 2, 3] 。第二大的数字是 2 。
示例 2:
输入:s = “abc1111”
输出:-1
解释:出现在 s 中的数字只包含 [1] 。没有第二大的数字。
提示:
1 <= s.length <= 500
s 只包含小写英文字母和(或)数字。
看似简单,很久不练习,还真不一定能30min内完成。每日练枪!
题解
1 | class Solution { |
86. 分隔链表
给你一个链表的头节点 head 和一个特定值 x ,请你对链表进行分隔,使得所有 小于 x 的节点都出现在 大于或等于 x 的节点之前。
你应当 保留 两个分区中每个节点的初始相对位置。
示例 1:
输入:head = [1,4,3,2,5,2], x = 3
输出:[1,2,2,4,3,5]
示例 2:
输入:head = [2,1], x = 2
输出:[1,2]
最小生成树
描述
一个有 n 户人家的村庄,有 m 条路相互连接着。村里现在要修路,每条路都有一个成本价格,现在请你帮忙计算下,最少需要花费多少钱,就能让这 n 户人家连接起来。
cost为一个二维数组,每个元素是一个长度为3的一维数组 a ,a[0]和a[1]表示村庄a[0]和村庄a[1]有一条路,修这条路的成本价格为 a[2] .
每户之间可能有多条道路连接,但不可能自己与自己相连
进阶: 时间复杂度 O(n+mlogm), 空间复杂度 O(n)
示例1
输入:
3,3,[[1,3,3],[1,2,1],[2,3,1]]
返回值:
2
示例2
输入:
2,1,[[1,2,1]]
返回值:
1
28. 实现 strStr() 字符串匹配
实现 strStr() 函数。
给你两个字符串 haystack 和 needle ,请你在 haystack 字符串中找出 needle 字符串出现的第一个位置(下标从 0 开始)。如果不存在,则返回 -1 。
说明:
当 needle 是空字符串时,我们应当返回什么值呢?这是一个在面试中很好的问题。
对于本题而言,当 needle 是空字符串时我们应当返回 0 。这与 C 语言的 strstr() 以及 Java 的 indexOf() 定义相符。
示例 1:
输入:haystack = “hello”, needle = “ll”
输出:2
示例 2:
输入:haystack = “aaaaa”, needle = “bba”
输出:-1
提示:
1 <= haystack.length, needle.length <= 104
haystack 和 needle 仅由小写英文字符组成
暴力法
1 | class Solution { |
KMP算法(Knuth-Morris-Pratt算法)
TODO
165. 比较版本号
给你两个版本号 version1 和 version2 ,请你比较它们。
版本号由一个或多个修订号组成,各修订号由一个 ‘.’ 连接。每个修订号由 多位数字 组成,可能包含 前导零 。每个版本号至少包含一个字符。修订号从左到右编号,下标从 0 开始,最左边的修订号下标为 0 ,下一个修订号下标为 1 ,以此类推。例如,2.5.33 和 0.1 都是有效的版本号。
比较版本号时,请按从左到右的顺序依次比较它们的修订号。比较修订号时,只需比较 忽略任何前导零后的整数值 。也就是说,修订号 1 和修订号 001 相等 。如果版本号没有指定某个下标处的修订号,则该修订号视为 0 。例如,版本 1.0 小于版本 1.1 ,因为它们下标为 0 的修订号相同,而下标为 1 的修订号分别为 0 和 1 ,0 < 1 。
返回规则如下:
如果 version1 > version2 返回 1,
如果 version1 < version2 返回 -1,
除此之外返回 0。
示例 1:
输入:version1 = “1.01”, version2 = “1.001”
输出:0
解释:忽略前导零,”01” 和 “001” 都表示相同的整数 “1”
示例 2:
输入:version1 = “1.0”, version2 = “1.0.0”
输出:0
解释:version1 没有指定下标为 2 的修订号,即视为 “0”
示例 3:
输入:version1 = “0.1”, version2 = “1.1”
输出:-1
解释:version1 中下标为 0 的修订号是 “0”,version2 中下标为 0 的修订号是 “1” 。0 < 1,所以 version1 < version2
双指针
1 | class Solution { |
分糖果问题(系列)
575. 分糖果
Alice 有 n 枚糖,其中第 i 枚糖的类型为 candyType[i] 。Alice 注意到她的体重正在增长,所以前去拜访了一位医生。
医生建议 Alice 要少摄入糖分,只吃掉她所有糖的 n / 2 即可(n 是一个偶数)。Alice 非常喜欢这些糖,她想要在遵循医生建议的情况下,尽可能吃到最多不同种类的糖。
给你一个长度为 n 的整数数组 candyType ,返回: Alice 在仅吃掉 n / 2 枚糖的情况下,可以吃到糖的 最多 种类数。
示例 1:
输入:candyType = [1,1,2,2,3,3]
输出:3
解释:Alice 只能吃 6 / 2 = 3 枚糖,由于只有 3 种糖,她可以每种吃一枚。
示例 2:
输入:candyType = [1,1,2,3]
输出:2
解释:Alice 只能吃 4 / 2 = 2 枚糖,不管她选择吃的种类是 [1,2]、[1,3] 还是 [2,3],她只能吃到两种不同类的糖。
示例 3:
输入:candyType = [6,6,6,6]
输出:1
解释:Alice 只能吃 4 / 2 = 2 枚糖,尽管她能吃 2 枚,但只能吃到 1 种糖。
提示:
n == candyType.length
2 <= n <= 104
n 是一个偶数
-105 <= candyType[i] <= 105
贪心
能吃的糖果数不大于糖果种类数,也不大于糖果个数的一半。
1 | class Solution { |
135. 分发糖果
n 个孩子站成一排。给你一个整数数组 ratings 表示每个孩子的评分。
你需要按照以下要求,给这些孩子分发糖果:
每个孩子至少分配到 1 个糖果。
相邻两个孩子评分更高的孩子会获得更多的糖果。
请你给每个孩子分发糖果,计算并返回需要准备的 最少糖果数目 。
示例 1:
输入:ratings = [1,0,2]
输出:5
解释:你可以分别给第一个、第二个、第三个孩子分发 2、1、2 颗糖果。
示例 2:
输入:ratings = [1,2,2]
输出:4
解释:你可以分别给第一个、第二个、第三个孩子分发 1、2、1 颗糖果。
第三个孩子只得到 1 颗糖果,这满足题面中的两个条件。
两次遍历
这题和求直方图中水量那题的思路有点类似。
先从左到右遍历,保证得分大的右邻居的糖果数符合要求
再从右向左遍历,保证得分大的左邻居的糖果数符合要求
时间复杂度O(n)
空间复杂度O(n)
1 | class Solution { |
还可以对空间进行一些优化
TODO
1103. 分糖果 II
排排坐,分糖果。
我们买了一些糖果 candies,打算把它们分给排好队的 n = num_people 个小朋友。
给第一个小朋友 1 颗糖果,第二个小朋友 2 颗,依此类推,直到给最后一个小朋友 n 颗糖果。
然后,我们再回到队伍的起点,给第一个小朋友 n + 1 颗糖果,第二个小朋友 n + 2 颗,依此类推,直到给最后一个小朋友 2 * n 颗糖果。
重复上述过程(每次都比上一次多给出一颗糖果,当到达队伍终点后再次从队伍起点开始),直到我们分完所有的糖果。注意,就算我们手中的剩下糖果数不够(不比前一次发出的糖果多),这些糖果也会全部发给当前的小朋友。
返回一个长度为 num_people、元素之和为 candies 的数组,以表示糖果的最终分发情况(即 ans[i] 表示第 i 个小朋友分到的糖果数)。
示例 1:
输入:candies = 7, num_people = 4
输出:[1,2,3,1]
解释:
第一次,ans[0] += 1,数组变为 [1,0,0,0]。
第二次,ans[1] += 2,数组变为 [1,2,0,0]。
第三次,ans[2] += 3,数组变为 [1,2,3,0]。
第四次,ans[3] += 1(因为此时只剩下 1 颗糖果),最终数组变为 [1,2,3,1]。
示例 2:
输入:candies = 10, num_people = 3
输出:[5,2,3]
解释:
第一次,ans[0] += 1,数组变为 [1,0,0]。
第二次,ans[1] += 2,数组变为 [1,2,0]。
第三次,ans[2] += 3,数组变为 [1,2,3]。
第四次,ans[0] += 4,最终数组变为 [5,2,3]。
提示:
1 <= candies <= 10^9
1 <= num_people <= 1000
遍历
1 | class Solution { |
等差数列
TODO
NC125 和为K的连续最大子数组
NC125 和为K的连续最大子数组
给定一个无序数组 arr , 其中元素可正、可负、可0。给定一个整数 k ,求 arr 所有连续子数组中累加和为k的最长连续子数组长度。保证至少存在一个合法的连续子数组。
[1,2,3]的连续子数组有[1,2],[2,3],[1,2,3] ,但是[1,3]不是
要求:空间复杂度 O(n), 时间复杂度 O(n)
示例1
输入:
[1,-2,1,1,1],0
返回值:
3
示例2
输入:
[0,1,2,3],3
返回值:
3
前缀和+哈希表
哈希表记录前缀和第一次出现的位置
1 | class Solution { |
560. 和为K的连续子数组
560. 和为 K 的子数组
给你一个整数数组 nums 和一个整数 k ,请你统计并返回 该数组中和为 k 的子数组的个数 。
示例 1:
输入:nums = [1,1,1], k = 2
输出:2
示例 2:
输入:nums = [1,2,3], k = 3
输出:2
提示:
1 <= nums.length <= 2 * 104
-1000 <= nums[i] <= 1000
-107 <= k <= 107
暴力枚举, 无法通过OJ
1 | class Solution { |
前缀和+哈希表
记录pre[i]为序号为0-i的数组中所有数的和。
对于序号为[i, j]的子树组来说,如果pre[j]-pre[i-1] == k, 则其为一个目标答案。
可以考虑用一个哈希表记录所有前缀和出现的次数,遍历一次即可求得答案。
时间复杂度和空间复杂度均为O(n)
1 | class Solution { |
222. 完全二叉树的节点个数
给你一棵 完全二叉树 的根节点 root ,求出该树的节点个数。
完全二叉树 的定义如下:在完全二叉树中,除了最底层节点可能没填满外,其余每层节点数都达到最大值,并且最下面一层的节点都集中在该层最左边的若干位置。若最底层为第 h 层,则该层包含 1~ 2h 个节点。
示例 1:
输入:root = [1,2,3,4,5,6]
输出:6
示例 2:
输入:root = []
输出:0
示例 3:
输入:root = [1]
输出:1
提示:
树中节点的数目范围是[0, 5 * 104]
0 <= Node.val <= 5 * 104
题目数据保证输入的树是 完全二叉树
进阶:遍历树来统计节点是一种时间复杂度为 O(n) 的简单解决方案。你可以设计一个更快的算法吗?
直接深度优先遍历
1 | /** |
二分查找
若完全二叉树层数为h,根为0层,最后一层也就是第h层的节点数为1至2^h之间,总的节点数为[2^h, 2&(h+1)-1]
可以通过二分法判断。
如果判断最后一层的一个节点是否存在 是核心的问题。可以通过位运算来确定。
整体的时间复杂度为O(log^2n)
1 | /** |
丑数(系列)
263. 丑数
丑数 就是只包含质因数 2、3 和 5 的正整数。
给你一个整数 n ,请你判断 n 是否为 丑数 。如果是,返回 true ;否则,返回 false 。
示例 1:
输入:n = 6
输出:true
解释:6 = 2 × 3
示例 2:
输入:n = 1
输出:true
解释:1 没有质因数,因此它的全部质因数是 {2, 3, 5} 的空集。习惯上将其视作第一个丑数。
示例 3:
输入:n = 14
输出:false
解释:14 不是丑数,因为它包含了另外一个质因数 7 。
分别对n反复除以质因子2,3,5, 如果最后剩余的值为1,则OK
1 | class Solution { |
264. 丑数 II
给你一个整数 n ,请你找出并返回第 n 个 丑数 。
丑数 就是只包含质因数 2、3 和/或 5 的正整数。
示例 1:
输入:n = 10
输出:12
解释:[1, 2, 3, 4, 5, 6, 8, 9, 10, 12] 是由前 10 个丑数组成的序列。
示例 2:
输入:n = 1
输出:1
解释:1 通常被视为丑数。
暴力法
直接按自然数顺序遍历isUgly, 但是时间复杂度O(nlogn)太高,
1 | class Solution { |
小顶堆
每次从堆顶取出最小值,然后乘以三个因子后的数加入堆,为了避免重复,可以使用集合过滤。
时间复杂度也是O(nlogn), 但是确能通过OJ了
1 | class Solution { |
三个数组(或者叫动态规划)
dp[i] = min(dp[i-1]*2, dp[i-1]*3, dp[i-1]*5)
初始时候dp[1] = 1;
后面不断的乘以2,3,5分别可以得到3个数组,就是不知道下一次该选谁,所以有三个指针记录当前走到的位置。
1 | class Solution { |
313. 超级丑数
超级丑数 是一个正整数,并满足其所有质因数都出现在质数数组 primes 中。
给你一个整数 n 和一个整数数组 primes ,返回第 n 个 超级丑数 。
题目数据保证第 n 个 超级丑数 在 32-bit 带符号整数范围内。
示例 1:
输入:n = 12, primes = [2,7,13,19]
输出:32
解释:给定长度为 4 的质数数组 primes = [2,7,13,19],前 12 个超级丑数序列为:[1,2,4,7,8,13,14,16,19,26,28,32] 。
示例 2:
输入:n = 1, primes = [2,3,5]
输出:1
解释:1 不含质因数,因此它的所有质因数都在质数数组 primes = [2,3,5] 中。
提示:
1 <= n <= 105
1 <= primes.length <= 100
2 <= primes[i] <= 1000
题目数据 保证 primes[i] 是一个质数
primes 中的所有值都 互不相同 ,且按 递增顺序 排列
思路和普通丑数的处理方式一样
1 | class Solution { |
1201. 丑数 III
给你四个整数:n 、a 、b 、c ,请你设计一个算法来找出第 n 个丑数。
丑数是可以被 a 或 b 或 c 整除的 正整数 。
示例 1:
输入:n = 3, a = 2, b = 3, c = 5
输出:4
解释:丑数序列为 2, 3, 4, 5, 6, 8, 9, 10… 其中第 3 个是 4。
示例 2:
输入:n = 4, a = 2, b = 3, c = 4
输出:6
解释:丑数序列为 2, 3, 4, 6, 8, 9, 10, 12… 其中第 4 个是 6。
示例 3:
输入:n = 5, a = 2, b = 11, c = 13
输出:10
解释:丑数序列为 2, 4, 6, 8, 10, 11, 12, 13… 其中第 5 个是 10。
示例 4:
输入:n = 1000000000, a = 2, b = 217983653, c = 336916467
输出:1999999984
这题和前面的题,似乎都不太一样,
递推的思路,时间复杂度太高
1 | class Solution { |
二分
TODO
剑指 Offer 50. 第一个只出现一次的字符
在字符串 s 中找出第一个只出现一次的字符。如果没有,返回一个单空格。 s 只包含小写字母。
示例 1:
输入:s = “abaccdeff”
输出:’b’
示例 2:
输入:s = “”
输出:’ ‘
哈希表一次遍历
1 | class Solution { |
使用队列+哈希表
1 | class Solution { |
剑指 Offer 61. 扑克牌中的顺子
从若干副扑克牌中随机抽 5 张牌,判断是不是一个顺子,即这5张牌是不是连续的。2~10为数字本身,A为1,J为11,Q为12,K为13,而大、小王为 0 ,可以看成任意数字。A 不能视为 14。
示例 1:
输入: [1,2,3,4,5]
输出: True
示例 2:
输入: [0,0,1,2,5]
输出: True
限制:
数组长度为 5
数组的数取值为 [0, 13] .
一次遍历+哈希表
1 | class Solution { |
排序+一次遍历
1 | class Solution { |
36. 有效的数独
请你判断一个 9 x 9 的数独是否有效。只需要 根据以下规则 ,验证已经填入的数字是否有效即可。
数字 1-9 在每一行只能出现一次。
数字 1-9 在每一列只能出现一次。
数字 1-9 在每一个以粗实线分隔的 3x3 宫内只能出现一次。(请参考示例图)
注意:
一个有效的数独(部分已被填充)不一定是可解的。
只需要根据以上规则,验证已经填入的数字是否有效即可。
空白格用 ‘.’ 表示。
一趟遍历
分别用二维数组记录每一行和每一列中1-9出现的个数,用三维数组记录每一个小方格中1-9的个数。
1 | class Solution { |
37. 解数独
编写一个程序,通过填充空格来解决数独问题。
数独的解法需 遵循如下规则:
数字 1-9 在每一行只能出现一次。
数字 1-9 在每一列只能出现一次。
数字 1-9 在每一个以粗实线分隔的 3x3 宫内只能出现一次。(请参考示例图)
数独部分空格内已填入了数字,空白格用 ‘.’ 表示。
回溯
先遍历一次board,找到需要填数的位置,然后依次遍历填写,如果填写完成就结束。
1 | class Solution { |
1382. 将二叉搜索树变平衡
给你一棵二叉搜索树,请你返回一棵 平衡后 的二叉搜索树,新生成的树应该与原来的树有着相同的节点值。如果有多种构造方法,请你返回任意一种。
如果一棵二叉搜索树中,每个节点的两棵子树高度差不超过 1 ,我们就称这棵二叉搜索树是 平衡的 。
示例 1:
输入:root = [1,null,2,null,3,null,4,null,null]
输出:[2,1,3,null,null,null,4]
解释:这不是唯一的正确答案,[3,1,4,null,2,null,null] 也是一个可行的构造方案。
示例 2:
输入: root = [2,1,3]
输出: [2,1,3]
中序遍历
可以利用 二叉搜索树中序遍历的结果是有序数组的特点,先得到有序数组,然后在构建平衡二叉搜索树
时间空间复杂度均为O(n)
1 | /** |
插入时旋转
TODO
108. 将有序数组转换为二叉搜索树
给你一个整数数组 nums ,其中元素已经按 升序 排列,请你将其转换为一棵 高度平衡 二叉搜索树。
高度平衡 二叉树是一棵满足「每个节点的左右两个子树的高度差的绝对值不超过 1 」的二叉树。
示例 1:
输入:nums = [-10,-3,0,5,9]
输出:[0,-3,9,-10,null,5]
解释:[0,-10,5,null,-3,null,9] 也将被视为正确答案:
示例 2:
输入:nums = [1,3]
输出:[3,1]
解释:[1,null,3] 和 [3,1] 都是高度平衡二叉搜索树。
升序数组转化为平衡二叉树,可以有很多种;
转化为高度平衡的二叉树,却只有有限的几种,核心在于选择跟节点的方式:
- 总是选择中间数的左边一个数
- 总是选择中间数的右边一个数
- 选择中间数的左或右的一个数
时间复杂度:O(n), 数组中每个数遍历一次即可
空间复杂度:O(logn), 主要是递归调用的深度,高度平衡二叉树,高度为logn
1 | /** |
NC144 懂二进制
描述
世界上有10种人,一种懂二进制,一种不懂。那么你知道两个int32整数m和n的二进制表达,有多少个位(bit)不同么?
示例1
输入:
3,5
返回值:
2
说明:
3的二进制为11,5的二进制为101,总共有2位不同
示例2
输入:
1999,2299
复制
返回值:
7
1 | class Solution { |
1044. 最长重复子串
给你一个字符串 s ,考虑其所有 重复子串 :即 s 的(连续)子串,在 s 中出现 2 次或更多次。这些出现之间可能存在重叠。
返回 任意一个 可能具有最长长度的重复子串。如果 s 不含重复子串,那么答案为 “” 。
示例 1:
输入:s = “banana”
输出:”ana”
示例 2:
输入:s = “abcd”
输出:””
提示:
2 <= s.length <= 3 * 104
s 由小写英文字母组成
99. 恢复二叉搜索树
给你二叉搜索树的根节点 root ,该树中的 恰好 两个节点的值被错误地交换。请在不改变其结构的情况下,恢复这棵树 。
示例 1:
输入:root = [1,3,null,null,2]
输出:[3,1,null,null,2]
解释:3 不能是 1 的左孩子,因为 3 > 1 。交换 1 和 3 使二叉搜索树有效。
示例 2:
输入:root = [3,1,4,null,null,2]
输出:[2,1,4,null,null,3]
解释:2 不能在 3 的右子树中,因为 2 < 3 。交换 2 和 3 使二叉搜索树有效。
提示:
树上节点的数目在范围 [2, 1000] 内
-231 <= Node.val <= 231 - 1
进阶:使用 O(n) 空间复杂度的解法很容易实现。你能想出一个只使用 O(1) 空间的解决方案吗?
中序遍历
- 先中序遍历拿到遍历结果值
- 然后找到异常的2个数。分是否相邻两种情况
- 遍历二叉树修复这两个数
时间复杂度: O(n)
空间复杂度:O(n)
1 | /** |
其实没必要真正返回一个数组存储中序遍历的结果,可以在中序遍历的过程中直接找到异常的数,然后交换。
一次遍历二叉树得到,时间复杂度为O(n)
空间复杂度主要来自于递归调用深度,为二叉树高度,最坏情况下为单链表,O(n)
1 | /** |
Morris 中序遍历
TODO
面试题 16.05. 阶乘尾数
设计一个算法,算出 n 阶乘有多少个尾随零。
示例 1:
输入: 3
输出: 0
解释: 3! = 6, 尾数中没有零。
示例 2:
输入: 5
输出: 1
解释: 5! = 120, 尾数中有 1 个零.
说明: 你算法的时间复杂度应为 O(log n) 。
分析质因子
考虑到因子2和5才有可能贡献尾数0,由于2一定比5多,只需考虑因子5的个数。
比如30,有30,25,20,15,10,5共6个数贡献7个因子5(25贡献了两个5)
一般通用情况下,考虑[1,n]中质因子p的个数。
[1, n]中p的倍数有n1=[n/p]个,即至少能贡献n1个质因子;
[1, n]中p^2的倍数有n2=[n/(p^2)]个,即至少能贡献n2个质因子;
举个例子,比如n=30, p=5, n1=[30/5]=6,也就是一阶5可以有6个贡献,即51,52,53,54,55,56
n2=[30/25]=1, 也就是二阶5有1个贡献,即25*1。
需要说明的是这里25虽然被计算了两次,但是却没有算重复,累积贡献2个5,其中一阶5和二阶5分别贡献了一次5。
由于5^3=125已经大于30了,所以就不用考虑三阶的5了。
推而广之,[1, n]中质因子的个数是
[n/p] + [n/(p^2)] + [n/(p^3)] + …
1 | class Solution { |
剑指 Offer 36. 二叉搜索树与双向链表
输入一棵二叉搜索树,将该二叉搜索树转换成一个排序的循环双向链表。要求不能创建任何新的节点,只能调整树中节点指针的指向。
为了让您更好地理解问题,以下面的二叉搜索树为例:
我们希望将这个二叉搜索树转化为双向循环链表。链表中的每个节点都有一个前驱和后继指针。对于双向循环链表,第一个节点的前驱是最后一个节点,最后一个节点的后继是第一个节点。
下图展示了上面的二叉搜索树转化成的链表。“head” 表示指向链表中有最小元素的节点。
特别地,我们希望可以就地完成转换操作。当转化完成以后,树中节点的左指针需要指向前驱,树中节点的右指针需要指向后继。还需要返回链表中的第一个节点的指针。
中序遍历的思路-递归实现
时间复杂度:二叉树每个节点遍历一次,O(n)
空间复杂度:递归调用深度为树的高度,二叉树高度最差情况下会退化为单链表,为O(n)
1 | /* |
中序遍历 栈的实现
TODO
方阵乘法
描述
给定两个 nn 的矩阵 A 和 B ,求 AB 。
数据范围:1 \le n \le 1001≤n≤100,-100 \le Matrix_{i,j}\le 100−100≤Matrix
i,j
≤100
要求:空间复杂度 O(n^2)O(n
2
) , 时间复杂度 O(n^3 )O(n
3
)
进阶:本题也有空间复杂度 O(n^2)O(n
2
),时间复杂度 O(n^{log7})O(n
log7
)的解法
PS:更优时间复杂度的算法这里并不考察
示例1
输入:
[[1,2],[3,2]],[[3,4],[2,1]]
返回值:
[[7,6],[13,14]]
示例2
输入:
[[1]],[[1]]
返回值:
[[1]]
329. 矩阵中的最长递增路径
给定一个 m x n 整数矩阵 matrix ,找出其中 最长递增路径 的长度。
对于每个单元格,你可以往上,下,左,右四个方向移动。 你 不能 在 对角线 方向上移动或移动到 边界外(即不允许环绕)。
示例 1:
输入:matrix = [[9,9,4],[6,6,8],[2,1,1]]
输出:4
解释:最长递增路径为 [1, 2, 6, 9]。
示例 2:
输入:matrix = [[3,4,5],[3,2,6],[2,2,1]]
输出:4
解释:最长递增路径是 [3, 4, 5, 6]。注意不允许在对角线方向上移动。
示例 3:
输入:matrix = [[1]]
输出:1
深度优先搜索-递归
对于每一个位置,其上下左右四个方向中,比当前位置值大的值与当前值必然组成长度不小于2的段。
求得每个位置的最长递增路径长度后,遍历每个位置的值,即可求得答案。
当然,为了避免重复计算,使用数组记录已经求得的值。所以也叫 记忆化深度优先搜索。
时间复杂度: O(mn),其中m和n为矩阵的长和宽。考虑矩阵为无向图,深度优先遍历的时间复杂度为O(V+E), 其中V、E分别为无向图的顶点和边。在矩阵中,O(V) = O(mn), O(E) = O(4mn) = O(mn)
空间复杂度:O(mn), 空间主要是缓存memo和递归调用的深度,memo为mn, 递归调用深度最坏是把所有矩阵元素连起来,长度不会超过m*n
1 | class Solution { |
动态规划
如果是动态规划,则是先计算值较大节点的路径长度,然后递推
可以考虑使用优先级队列对矩阵中元素进行排序,然后从大到小计算以元素i,j结尾的最大序列的长度:dp[i][j]
记录整个过程中最大的dp[i][j]值即为答案
dp[i][j]表示以元素(i, j)为开始节点的最大路径长度
时间和空间复杂度依然是O(m*n)
1 | class Solution { |
广度优先搜索-队列-拓扑排序
将矩阵看作是一个有向图,计算每个单元格对应的出度,即有多少条边从该节点出发,也就是相邻的四个顶点有几个点比该点大。
边界条件是出度为0的点,若为路径,必为路径结尾。
基于出度的概念,可以使用拓扑排序求解,从所有出度为0的单元格开始广度优先搜索,每一轮都会遍历当前队列中的所有节点,然后更新周围的节点,
并将出度为0的节点加入下一层。这样,分别遍历出度为0,相邻且出度为1,相邻且出度为2…的节点,当遍历结束时,搜索的总层数即为答案。
时间复杂度:O(mn)
空间复杂度:O(mn)
1 | class Solution { |
617. 合并二叉树
给你两棵二叉树: root1 和 root2 。
想象一下,当你将其中一棵覆盖到另一棵之上时,两棵树上的一些节点将会重叠(而另一些不会)。你需要将这两棵树合并成一棵新二叉树。合并的规则是:如果两个节点重叠,那么将这两个节点的值相加作为合并后节点的新值;否则,不为 null 的节点将直接作为新二叉树的节点。
返回合并后的二叉树。
注意: 合并过程必须从两个树的根节点开始。
示例 1:
输入:root1 = [1,3,2,5], root2 = [2,1,3,null,4,null,7]
输出:[3,4,5,5,4,null,7]
示例 2:
输入:root1 = [1], root2 = [1,2]
输出:[2,2]
深度优先搜索-递归
面试时候,需要和面试官确认,是否可以修改原有的两棵树。还有合并后的二叉树是否可以和原树共用空间。
递归真是解决二叉树的问题的一个利器。
时间复杂度:O(min(m, n)), 其中m和n分别是两个二叉树的节点个数, 只有二叉树中均不为空的节点才需要合并,需要合并的节点数不超过二者中节点数较小者的2倍
空间复杂度:O(min(m, n)), 空间复杂度取决于递归调用的层数,二叉树递归的层数不超过二叉树的深度
1 | /** |
广度优先搜索-队列
层序遍历的思路,使用三个队列分别存储原始两个树和新树中需要合并的节点。
不需要合并的节点,直接复用既有的节点。(这一点需要和面试官达成一致)
1 | /** |
面试题 04.10. 检查子树
检查子树。你有两棵非常大的二叉树:T1,有几万个节点;T2,有几万个节点。设计一个算法,判断 T2 是否为 T1 的子树。
如果 T1 有这么一个节点 n,其子树与 T2 一模一样,则 T2 为 T1 的子树,也就是说,从节点 n 处把树砍断,得到的树与 T2 完全相同。
注意:此题相对书上原题略有改动。
示例1:
输入:t1 = [1, 2, 3], t2 = [2]
输出:true
示例2:
输入:t1 = [1, null, 2, 4], t2 = [3, 2]
输出:false
递归
如果一个树是另一个树的子树,则其根节点必然是相等,左右子树也是分别是子树。
如果t2为空,则必然是子树
如果t1为空,但是t2不为空,那必不是子树。
如果t1和t2的值相等,再看其左右子树是不是都相等或存在子树。
如果左子树不为空,看t2是否在左子树中
如果右子树不为空,看t2是否在右子树中
时间复杂度: O(m*n)
空间复杂度:O(m+n), 递归调用深度为二叉树深度, 二叉树深度最坏为节点数
1 | /** |
中序遍历
中序遍历等得到二叉树唯一的串,并且子树的树会紧挨着。
时间复杂度: O(mn), 因为中序二叉树中每个元素均遍历一次为O(m+n),但是find函数却是O(mn)
空间复杂度:O(logm+logn), 递归调用深度为二叉树深度
1 | /** |
剑指 Offer 21. 调整数组顺序使奇数位于偶数前面
输入一个整数数组,实现一个函数来调整该数组中数字的顺序,使得所有奇数在数组的前半部分,所有偶数在数组的后半部分。
示例:
输入:nums = [1,2,3,4]
输出:[1,3,2,4]
注:[3,1,2,4] 也是正确的答案之一。
一趟遍历划分
借用快速排序划分的思想,将数组分为两个部分
1 | class Solution { |
226. 翻转二叉树
给你一棵二叉树的根节点 root ,翻转这棵二叉树,并返回其根节点。
示例 1:
输入:root = [4,2,7,1,3,6,9]
输出:[4,7,2,9,6,3,1]
示例 2:
输入:root = [2,1,3]
输出:[2,3,1]
示例 3:
输入:root = []
输出:[]
递归
1 | /** |
剑指 Offer 46. 把数字翻译成字符串
给定一个数字,我们按照如下规则把它翻译为字符串:0 翻译成 “a” ,1 翻译成 “b”,……,11 翻译成 “l”,……,25 翻译成 “z”。一个数字可能有多个翻译。请编程实现一个函数,用来计算一个数字有多少种不同的翻译方法。
示例 1:
输入: 12258
输出: 5
解释: 12258有5种不同的翻译,分别是”bccfi”, “bwfi”, “bczi”, “mcfi”和”mzi”
提示:
0 <= num < 231
动态规划
记录dp[i]是以第i个数结尾的子数字串所能得到的翻译个数,则最后这个数对整体的贡献可以有两种:
要么单独一个数字成为一个翻译,要么和前一个数字共同成为一个翻译。
当前两个数字的翻译方案需要组成的数字合法。
1 | class Solution { |
用滚动数组优化空间复杂度
1 | class Solution { |
53. 最大子数组和
给你一个整数数组 nums ,请你找出一个具有最大和的连续子数组(子数组最少包含一个元素),返回其最大和。
子数组 是数组中的一个连续部分。
示例 1:
输入:nums = [-2,1,-3,4,-1,2,1,-5,4]
输出:6
解释:连续子数组 [4,-1,2,1] 的和最大,为 6 。
示例 2:
输入:nums = [1]
输出:1
示例 3:
输入:nums = [5,4,-1,7,8]
输出:23
动态规划
记录dp[i] 为以第i个数结尾的 连续子数组的最大和。
那么dp[i]等于dp[i-1]+nums[i]或nums[i]中的较大者,即每次遍历数组,看是否该数是单独贡献,还是可以加到前序子数组中。
最终的结果为dp中的最大值。
时间复杂度:O(n)
空间复杂度:O(1)
1 | class Solution { |
分治
线段树的思路需要专题梳理
TODO 20220504
152. 乘积最大子数组
给你一个整数数组 nums ,请你找出数组中乘积最大的非空连续子数组(该子数组中至少包含一个数字),并返回该子数组所对应的乘积。
测试用例的答案是一个 32-位 整数。
子数组 是数组的连续子序列。
示例 1:
输入: nums = [2,3,-2,4]
输出: 6
解释: 子数组 [2,3] 有最大乘积 6。
示例 2:
输入: nums = [-2,0,-1]
输出: 0
解释: 结果不能为 2, 因为 [-2,-1] 不是子数组。
提示:
1 <= nums.length <= 2 * 104
-10 <= nums[i] <= 10
nums 的任何前缀或后缀的乘积都 保证 是一个 32-位 整数
动态规划
记录dp_max[i]是以第i个数结尾的乘积最大子数组的积,则
dp_max[i] = max(dp_max[i-1]*nums[i], nums[i])
但是这样只能解决数组中所有数全部非负或全部非正的情形。
考虑负负得正的情形,我们新加一个dp_min, 表示最小的积,
则:
dp_max[i] = max(dp_max[i-1]*nums[i], dp_min[i-1]*nums[i], nums[i])
dp_min[i] = min(dp_max[i-1]*nums[i], dp_min[i-1]*nums[i], nums[i])
由于第i个状态只和i-1状态有关,所以可以考虑使用滚动数组的思想节省空间。
最终时间复杂度:O(n)
空间复杂度:O(1)
1 | class Solution { |
208. 实现 Trie (前缀树)
Trie(发音类似 “try”)或者说 前缀树 是一种树形数据结构,用于高效地存储和检索字符串数据集中的键。这一数据结构有相当多的应用情景,例如自动补完和拼写检查。
请你实现 Trie 类:
Trie() 初始化前缀树对象。
void insert(String word) 向前缀树中插入字符串 word 。
boolean search(String word) 如果字符串 word 在前缀树中,返回 true(即,在检索之前已经插入);否则,返回 false 。
boolean startsWith(String prefix) 如果之前已经插入的字符串 word 的前缀之一为 prefix ,返回 true ;否则,返回 false 。
示例:
输入
[“Trie”, “insert”, “search”, “search”, “startsWith”, “insert”, “search”]
[[], [“apple”], [“apple”], [“app”], [“app”], [“app”], [“app”]]
输出
[null, null, true, false, true, null, true]
解释
Trie trie = new Trie();
trie.insert(“apple”);
trie.search(“apple”); // 返回 True
trie.search(“app”); // 返回 False
trie.startsWith(“app”); // 返回 True
trie.insert(“app”);
trie.search(“app”); // 返回 True
提示:
1 <= word.length, prefix.length <= 2000
word 和 prefix 仅由小写英文字母组成
insert、search 和 startsWith 调用次数 总计 不超过 3 * 104 次
26叉树
Trie 前缀树,实际就是多叉树,如果只考虑小写字母那就是26叉树。
定义每个节点有一个子节点数组和一个是否结束标记。
初始化:子节点数组长度定义为26,是否结束标记定义为false
插入:将字符串中的每个字符挨个插入到树中,如果字符已存在,则看下一层,字符不存在则创建一个节点,注意:最后一个字符的节点标记为结束
查找前缀:按字符依次查找,如果返回空则未找到,全部找到为找到
查找字符串:类似查找前缀,但是结束时需要判定结束标记。
1 | class Trie { |
N皇后(系列)
51. N 皇后
n 皇后问题 研究的是如何将 n 个皇后放置在 n×n 的棋盘上,并且使皇后彼此之间不能相互攻击。
给你一个整数 n ,返回所有不同的 n 皇后问题 的解决方案。
每一种解法包含一个不同的 n 皇后问题 的棋子放置方案,该方案中 ‘Q’ 和 ‘.’ 分别代表了皇后和空位。
示例 1:
输入:n = 4
输出:[[“.Q..”,”…Q”,”Q…”,”..Q.”],[“..Q.”,”Q…”,”…Q”,”.Q..”]]
解释:如上图所示,4 皇后问题存在两个不同的解法。
示例 2:
输入:n = 1
输出:[[“Q”]]
提示:
1 <= n <= 9
回溯穷举
逐行尝试选择皇后放置的列,放置之前先检查可以放置在哪一列。当所有行都判断完后,可以将答案放置在答案数组中
一个皇后可以放置的位置,需要满足:
1.同列上方无皇后
2.左右斜对角延伸的上方每一行无皇后
python3代码
2020.07.25 15:37:13年的代码
printN负责打印结果数组
cal8queens通过递归穷举每一行
is_valid判断指定行和列是否OK
1 | class Solution: |
C++的代码
1 | class Solution { |
基于集合的回溯
前一种方法中,check函数的时间复杂度为O(n),导致整体的时间复杂度较高为O(n*n!)
可以使用集合将check的时间复杂度降低到O(1)
通过分析,我们可以发现:
- 左上方斜线上的元素,横纵坐标之差相等
- 右上方斜线上的元素,横纵坐标之和相等
- 纵向方向的元素,纵坐标相等。
所以可以用三个集合存储上述的数,用空间换时间
1 | class Solution { |
基于位运算的回溯
前一种使用集合来记录三个方向是否可以放置皇后,这里用三个数通过位运算来表示,
可以将判断是否能放皇后的空间复杂度从O(N)降低为O(1)
TODO
52. N皇后 II
n 皇后问题 研究的是如何将 n 个皇后放置在 n × n 的棋盘上,并且使皇后彼此之间不能相互攻击。
给你一个整数 n ,返回 n 皇后问题 不同的解决方案的数量。
示例 1:
输入:n = 4
输出:2
解释:如上图所示,4 皇后问题存在两个不同的解法。
示例 2:
输入:n = 1
输出:1
提示:
1 <= n <= 9
基于集合的回溯
思路同上
1 | class Solution { |
295. 数据流的中位数
中位数是有序列表中间的数。如果列表长度是偶数,中位数则是中间两个数的平均值。
例如,
[2,3,4] 的中位数是 3
[2,3] 的中位数是 (2 + 3) / 2 = 2.5
设计一个支持以下两种操作的数据结构:
void addNum(int num) - 从数据流中添加一个整数到数据结构中。
double findMedian() - 返回目前所有元素的中位数。
示例:
addNum(1)
addNum(2)
findMedian() -> 1.5
addNum(3)
findMedian() -> 2
进阶:
如果数据流中所有整数都在 0 到 100 范围内,你将如何优化你的算法?
如果数据流中 99% 的整数都在 0 到 100 范围内,你将如何优化你的算法?
两个堆
时间复杂度主要是优先队列调整的时间O(logn)
空间复杂度O(n)
1 | class MedianFinder { |
有序集合+双指针
时间复杂度同样是O(logn)
1 | class MedianFinder { |
进阶 11
如果数据流中所有整数都在 00 到 100100 范围内,那么我们可以利用计数排序统计每一类数的数量,并使用双指针维护中位数。
进阶 22
如果数据流中 99%99% 的整数都在 00 到 100100 范围内,那么我们依然利用计数排序统计每一类数的数量,并使用双指针维护中位数。对于超出范围的数,我们可以单独进行处理,建立两个数组,分别记录小于 00 的部分的数的数量和大于 100100 的部分的数的数量即可。当小部分时间,中位数不落在区间 [0,100][0,100] 中时,我们在对应的数组中暴力检查即可。
10. 正则表达式匹配&44. 通配符匹配
10. 正则表达式匹配
给你一个字符串 s 和一个字符规律 p,请你来实现一个支持 ‘.’ 和 ‘*’ 的正则表达式匹配。
‘.’ 匹配任意单个字符
‘*’ 匹配零个或多个前面的那一个元素
所谓匹配,是要涵盖 整个 字符串 s的,而不是部分字符串。
示例 1:
输入:s = “aa”, p = “a”
输出:false
解释:”a” 无法匹配 “aa” 整个字符串。
示例 2:
输入:s = “aa”, p = “a*”
输出:true
解释:因为 ‘*’ 代表可以匹配零个或多个前面的那一个元素, 在这里前面的元素就是 ‘a’。因此,字符串 “aa” 可被视为 ‘a’ 重复了一次。
示例 3:
输入:s = “ab”, p = “.“
输出:true
解释:”.“ 表示可匹配零个或多个(’*’)任意字符(’.’)
动态规划
dp[i][j]表示s的前i个字符和p的前j个字符是否匹配。
若p[j-1] != ‘‘, 则看对应字符是否相等;
若p[j-1] == ‘‘, 则需要考虑2种情况:
- p[j-2] == s[i-1], 也就是*前一个字符是否和s对应字符匹配,若匹配则可以匹配1次或多次。其中匹配1次,可以被多次+0次合并。
- p[j-2] != s[i-2], 不匹配,则只能表示匹配0次,消去前一个字符,再比较。
1 | class Solution { |
44. 通配符匹配
给定一个字符串 (s) 和一个字符模式 (p) ,实现一个支持 ‘?’ 和 ‘*’ 的通配符匹配。
‘?’ 可以匹配任何单个字符。
‘*’ 可以匹配任意字符串(包括空字符串)。
两个字符串完全匹配才算匹配成功。
说明:
s 可能为空,且只包含从 a-z 的小写字母。
p 可能为空,且只包含从 a-z 的小写字母,以及字符 ? 和 *。
示例 1:
输入:
s = “aa”
p = “a”
输出: false
解释: “a” 无法匹配 “aa” 整个字符串。
示例 2:
输入:
s = “aa”
p = ““
输出: true
解释: ‘‘ 可以匹配任意字符串。
示例 3:
输入:
s = “cb”
p = “?a”
输出: false
解释: ‘?’ 可以匹配 ‘c’, 但第二个 ‘a’ 无法匹配 ‘b’。
示例 4:
输入:
s = “adceb”
p = “ab”
输出: true
解释: 第一个 ‘‘ 可以匹配空字符串, 第二个 ‘‘ 可以匹配字符串 “dce”.
示例 5:
输入:
s = “acdcb”
p = “a*c?b”
输出: false
动态规划
dp[i][j]表示s的前i个字符和p的前j个字符是否匹配。
1 | class Solution { |
189. 轮转数组
给你一个数组,将数组中的元素向右轮转 k 个位置,其中 k 是非负数。
示例 1:
输入: nums = [1,2,3,4,5,6,7], k = 3
输出: [5,6,7,1,2,3,4]
解释:
向右轮转 1 步: [7,1,2,3,4,5,6]
向右轮转 2 步: [6,7,1,2,3,4,5]
向右轮转 3 步: [5,6,7,1,2,3,4]
示例 2:
输入:nums = [-1,-100,3,99], k = 2
输出:[3,99,-1,-100]
解释:
向右轮转 1 步: [99,-1,-100,3]
向右轮转 2 步: [3,99,-1,-100]
提示:
1 <= nums.length <= 105
-231 <= nums[i] <= 231 - 1
0 <= k <= 105
进阶:
尽可能想出更多的解决方案,至少有 三种 不同的方法可以解决这个问题。
你可以使用空间复杂度为 O(1) 的 原地 算法解决这个问题吗?
三次翻转数组
1 | class Solution { |
使用额外的临时数组
但是空间复杂度为O(n)
1 | class Solution { |
环形数组
不使用额外数组,一个个的将每一个数依次放到最终的位置。需要移动n次
时间复杂度O(n), 空间复杂度O(1)
1 | class Solution { |
还可以通过最大公约数控制循环结束
1 | class Solution { |
1277. 统计全为 1 的正方形子矩阵
给你一个 m * n 的矩阵,矩阵中的元素不是 0 就是 1,请你统计并返回其中完全由 1 组成的 正方形 子矩阵的个数。
示例 1:
输入:matrix =
[
[0,1,1,1],
[1,1,1,1],
[0,1,1,1]
]
输出:15
解释:
边长为 1 的正方形有 10 个。
边长为 2 的正方形有 4 个。
边长为 3 的正方形有 1 个。
正方形的总数 = 10 + 4 + 1 = 15.
示例 2:
输入:matrix =
[
[1,0,1],
[1,1,0],
[1,1,0]
]
输出:7
解释:
边长为 1 的正方形有 6 个。
边长为 2 的正方形有 1 个。
正方形的总数 = 6 + 1 = 7.
动态规划
记录dp[i][j]为以右下角为(i,j)的矩形的最大边长,则dp[i][j]也表示以右下角为(i,j)的矩形的个数
遍历每个dp值,并求和即为所有正方形的个数。
1 | class Solution { |
最大正方形和最大矩形
221. 最大正方形
在一个由 ‘0’ 和 ‘1’ 组成的二维矩阵内,找到只包含 ‘1’ 的最大正方形,并返回其面积。
示例 1:
输入:matrix = [[“1”,”0”,”1”,”0”,”0”],[“1”,”0”,”1”,”1”,”1”],[“1”,”1”,”1”,”1”,”1”],[“1”,”0”,”0”,”1”,”0”]]
输出:4
示例 2:
输入:matrix = [[“0”,”1”],[“1”,”0”]]
输出:1
示例 3:
输入:matrix = [[“0”]]
输出:0
暴力法
时间复杂度O(mnmin(m,n)^2), 时间超限
1 | class Solution { |
动态规划
考虑记录dp[i][j]以(i,j)为右下角且只包含1的正方形的边长大小,则:
- 当i==0或j==0即边界时,dp[i][j] = 1,
- dp[i][j]与左边,上边,左上角三个位置的dp有关
1 | class Solution { |
84. 柱状图中最大的矩形
给定 n 个非负整数,用来表示柱状图中各个柱子的高度。每个柱子彼此相邻,且宽度为 1 。
求在该柱状图中,能够勾勒出来的矩形的最大面积。
示例 1:
输入:heights = [2,1,5,6,2,3]
输出:10
解释:最大的矩形为图中红色区域,面积为 10
示例 2:
输入: heights = [2,4]
输出: 4
暴力法
矩形面积等于 底*高,程序计算的时候,需要固定一个然后遍历另一个。
我们固定高的思路:
对于每一个柱形i,从i向两边遍历,直到严格小于该柱形的边界,则中间部分为底边。
但是无法通过OJ
1 | class Solution { |
单调栈
维持高度值严格单调递增的栈,方便寻找每个柱子的左边界和右边界
1 | class Solution { |
做一些常数项的优化,将寻找右边界合并。
注意初始化right默认值为n,因为有可能部分值最后未出栈,右边界为n
1 | class Solution { |
85. 最大矩形
给定一个仅包含 0 和 1 、大小为 rows x cols 的二维二进制矩阵,找出只包含 1 的最大矩形,并返回其面积。
示例 1:
输入:matrix = [[“1”,”0”,”1”,”0”,”0”],[“1”,”0”,”1”,”1”,”1”],[“1”,”1”,”1”,”1”,”1”],[“1”,”0”,”0”,”1”,”0”]]
输出:6
解释:最大矩形如上图所示。
示例 2:
输入:matrix = []
输出:0
示例 3:
输入:matrix = [[“0”]]
输出:0
示例 4:
输入:matrix = [[“1”]]
输出:1
示例 5:
输入:matrix = [[“0”,”0”]]
输出:0
转化为柱形图
借鉴【柱状图中最大矩形】的思路,将矩形转化为柱状图,然后计算,可得到解。
时间复杂度为O(mnmin(m, n))
1 | class Solution { |
柱状图+单调栈
与上一题类似,寻找左右边界的过程可以使用单调栈优化,空间换时间
时间复杂度O(m*n)
1 | class Solution { |
191. 位1的个数
编写一个函数,输入是一个无符号整数(以二进制串的形式),返回其二进制表达式中数字位数为 ‘1’ 的个数(也被称为汉明重量)。
提示:
请注意,在某些语言(如 Java)中,没有无符号整数类型。在这种情况下,输入和输出都将被指定为有符号整数类型,并且不应影响您的实现,因为无论整数是有符号的还是无符号的,其内部的二进制表示形式都是相同的。
在 Java 中,编译器使用二进制补码记法来表示有符号整数。因此,在上面的 示例 3 中,输入表示有符号整数 -3。
示例 1:
输入:00000000000000000000000000001011
输出:3
解释:输入的二进制串 00000000000000000000000000001011 中,共有三位为 ‘1’。
示例 2:
输入:00000000000000000000000010000000
输出:1
解释:输入的二进制串 00000000000000000000000010000000 中,共有一位为 ‘1’。
示例 3:
输入:11111111111111111111111111111101
输出:31
解释:输入的二进制串 11111111111111111111111111111101 中,共有 31 位为 ‘1’。
位运算顺序判断每一个二进制位
时间复杂度O(K)
1 | class Solution { |
利用n&(n-1)运算的特点
时间复杂度O(logn)
1 | class Solution { |
剑指 Offer 51. 数组中的逆序对
在数组中的两个数字,如果前面一个数字大于后面的数字,则这两个数字组成一个逆序对。输入一个数组,求出这个数组中的逆序对的总数。
示例 1:
输入: [7,5,6,4]
输出: 5
暴力解法
时间复杂度O(n^2), 无法通过OJ
1 | class Solution { |
归并排序
两个有序数组merge的时候, 当将要选右边数组合并到新数组时,被选中的这个数比左半数组中的数都要小,
此时逆序对数增加为左边数组中的长度。
时间复杂度O(nlogn)
空间复杂度O(n)
1 | class Solution { |
临时数组仅申请一次,降低中间申请销毁的时间
1 | class Solution { |
离散化树状数组
TODO
76. 最小覆盖子串
给你一个字符串 s 、一个字符串 t 。返回 s 中涵盖 t 所有字符的最小子串。如果 s 中不存在涵盖 t 所有字符的子串,则返回空字符串 “” 。
注意:
对于 t 中重复字符,我们寻找的子字符串中该字符数量必须不少于 t 中该字符数量。
如果 s 中存在这样的子串,我们保证它是唯一的答案。
示例 1:
输入:s = “ADOBECODEBANC”, t = “ABC”
输出:”BANC”
示例 2:
输入:s = “a”, t = “a”
输出:”a”
示例 3:
输入: s = “a”, t = “aa”
输出: “”
解释: t 中两个字符 ‘a’ 均应包含在 s 的子串中,
因此没有符合条件的子字符串,返回空字符串。
双指针方案
核心问题是判断窗口内的子串是否覆盖了目标串。
1 | class Solution { |
983. 最低票价
在一个火车旅行很受欢迎的国度,你提前一年计划了一些火车旅行。在接下来的一年里,你要旅行的日子将以一个名为 days 的数组给出。每一项是一个从 1 到 365 的整数。
火车票有 三种不同的销售方式 :
一张 为期一天 的通行证售价为 costs[0] 美元;
一张 为期七天 的通行证售价为 costs[1] 美元;
一张 为期三十天 的通行证售价为 costs[2] 美元。
通行证允许数天无限制的旅行。 例如,如果我们在第 2 天获得一张 为期 7 天 的通行证,那么我们可以连着旅行 7 天:第 2 天、第 3 天、第 4 天、第 5 天、第 6 天、第 7 天和第 8 天。
返回 你想要完成在给定的列表 days 中列出的每一天的旅行所需要的最低消费 。
示例 1:
输入:days = [1,4,6,7,8,20], costs = [2,7,15]
输出:11
解释:
例如,这里有一种购买通行证的方法,可以让你完成你的旅行计划:
在第 1 天,你花了 costs[0] = $2 买了一张为期 1 天的通行证,它将在第 1 天生效。
在第 3 天,你花了 costs[1] = $7 买了一张为期 7 天的通行证,它将在第 3, 4, …, 9 天生效。
在第 20 天,你花了 costs[0] = $2 买了一张为期 1 天的通行证,它将在第 20 天生效。
你总共花了 $11,并完成了你计划的每一天旅行。
示例 2:
输入:days = [1,2,3,4,5,6,7,8,9,10,30,31], costs = [2,7,15]
输出:17
解释:
例如,这里有一种购买通行证的方法,可以让你完成你的旅行计划:
在第 1 天,你花了 costs[2] = $15 买了一张为期 30 天的通行证,它将在第 1, 2, …, 30 天生效。
在第 31 天,你花了 costs[0] = $2 买了一张为期 1 天的通行证,它将在第 31 天生效。
你总共花了 $17,并完成了你计划的每一天旅行。
提示:
1 <= days.length <= 365
1 <= days[i] <= 365
days 按顺序严格递增
costs.length == 3
1 <= costs[i] <= 1000
记忆化搜索
需要从第1天开始遍历到第365天,时间复杂度为O(M)
1 | class Solution { |
优化的记忆化搜索
其实没必要从1遍历到365,只需要遍历必须出行的那些天,即days数组的长度
时间复杂度为O(N)
1 | class Solution { |
322. 零钱兑换
给你一个整数数组 coins ,表示不同面额的硬币;以及一个整数 amount ,表示总金额。
计算并返回可以凑成总金额所需的 最少的硬币个数 。如果没有任何一种硬币组合能组成总金额,返回 -1 。
你可以认为每种硬币的数量是无限的。
示例 1:
输入:coins = [1, 2, 5], amount = 11
输出:3
解释:11 = 5 + 5 + 1
示例 2:
输入:coins = [2], amount = 3
输出:-1
示例 3:
输入:coins = [1], amount = 0
输出:0
回溯算法时间复杂度为 O(S^n)会超时,需要更加高效的算法
1 | class Solution { |
动态规划
记录F(S):组成金额 S 所需的最少硬币数量
最后一枚硬币面值为C,则F(S)=F(S−C)+1, C需要遍历并选择最小的F(S-C)
我们一共需要计算 S 个状态的答案,且每个状态 F(S) 由于上面的记忆化的措施只计算了一次,而计算一个状态的答案需要枚举 n 个面额值,所以一共需要 O(Sn) 的时间复杂度。
自底向上计算叫动态规划,自顶向下叫记忆化搜索?
1 | class Solution { |
子集(系列)
78. 子集
给你一个整数数组 nums ,数组中的元素 互不相同 。返回该数组所有可能的子集(幂集)。
解集 不能 包含重复的子集。你可以按 任意顺序 返回解集。
示例 1:
输入:nums = [1,2,3]
输出:[[],[1],[2],[1,2],[3],[1,3],[2,3],[1,2,3]]
示例 2:
输入:nums = [0]
输出:[[],[0]]
回溯法
时间复杂度O(n*2^n), 2^n种状态,每种状态均需遍历一次数组
空间复杂度O(n), 存储临时变量数组path
1 | class Solution { |
位运算
假设有n位数,则每位选或不选用二进制数表示,刚好有2^n种选择。从0到2^n-1.
遍历每种选择,然后分别看这n个数是否该选进去,用按位或运算的方式。
1 | class Solution { |
90. 子集 II
给你一个整数数组 nums ,其中可能包含重复元素,请你返回该数组所有可能的子集(幂集)。
解集 不能 包含重复的子集。返回的解集中,子集可以按 任意顺序 排列。
示例 1:
输入:nums = [1,2,2]
输出:[[],[1],[1,2],[1,2,2],[2],[2,2]]
示例 2:
输入:nums = [0]
输出:[[],[0]]
回溯法
一般需要去重的时候,都需要先排序。
1 | class Solution { |
关于,回溯,有两种写法,都可以,值得专题揣摩
1 | class Solution { |
大数操作
415. 字符串相加
给定两个字符串形式的非负整数 num1 和num2 ,计算它们的和并同样以字符串形式返回。
你不能使用任何內建的用于处理大整数的库(比如 BigInteger), 也不能直接将输入的字符串转换为整数形式。
示例 1:
输入:num1 = “11”, num2 = “123”
输出:”134”
示例 2:
输入:num1 = “456”, num2 = “77”
输出:”533”
示例 3:
输入:num1 = “0”, num2 = “0”
输出:”0”
1 | class Solution { |
43. 字符串相乘
给定两个以字符串形式表示的非负整数 num1 和 num2,返回 num1 和 num2 的乘积,它们的乘积也表示为字符串形式。
注意:不能使用任何内置的 BigInteger 库或直接将输入转换为整数。
示例 1:
输入: num1 = “2”, num2 = “3”
输出: “6”
示例 2:
输入: num1 = “123”, num2 = “456”
输出: “56088”
1 | class Solution { |
还有一种直接计算的方法
乘法的时候,长度为m、n的两个数相乘,结果最大为m+n+1位,两个位为i,j的数乘积所在的位置为i+j+1,进位在i+j
1 | class Solution { |
468. 验证IP地址
给定一个字符串 queryIP。如果是有效的 IPv4 地址,返回 “IPv4” ;如果是有效的 IPv6 地址,返回 “IPv6” ;如果不是上述类型的 IP 地址,返回 “Neither” 。
有效的IPv4地址 是 “x1.x2.x3.x4” 形式的IP地址。 其中 0 <= xi <= 255 且 xi 不能包含 前导零。例如: “192.168.1.1” 、 “192.168.1.0” 为有效IPv4地址, “192.168.01.1” 为无效IPv4地址; “192.168.1.00” 、 “192.168@1.1” 为无效IPv4地址。
一个有效的IPv6地址 是一个格式为“x1:x2:x3:x4:x5:x6:x7:x8” 的IP地址,其中:
1 <= xi.length <= 4
xi 是一个 十六进制字符串 ,可以包含数字、小写英文字母( ‘a’ 到 ‘f’ )和大写英文字母( ‘A’ 到 ‘F’ )。
在 xi 中允许前导零。
例如 “2001:0db8:85a3:0000:0000:8a2e:0370:7334” 和 “2001:db8:85a3:0:0:8A2E:0370:7334” 是有效的 IPv6 地址,而 “2001:0db8:85a3::8A2E:037j:7334” 和 “02001:0db8:85a3:0000:0000:8a2e:0370:7334” 是无效的 IPv6 地址。
示例 1:
输入:queryIP = “172.16.254.1”
输出:”IPv4”
解释:有效的 IPv4 地址,返回 “IPv4”
示例 2:
输入:queryIP = “2001:0db8:85a3:0:0:8A2E:0370:7334”
输出:”IPv6”
解释:有效的 IPv6 地址,返回 “IPv6”
示例 3:
输入:queryIP = “256.256.256.256”
输出:”Neither”
解释:既不是 IPv4 地址,又不是 IPv6 地址
非常好的细节题
IPv4:
1.用.切分后,需要有四部分
2.每个部分不为空、开头不为0、不超过3位数
3.每个部分的每个字符均为数字
4.每个部分的范围在0-255
IPv6:
- 用:切分后,需要有8部分
- 每个部分的长度不为空且不超过4
- 每个部分的每个字符在0-9、a-f、A-F之间
1 | class Solution { |
179. 最大数
给定一组非负整数 nums,重新排列每个数的顺序(每个数不可拆分)使之组成一个最大的整数。
注意:输出结果可能非常大,所以你需要返回一个字符串而不是整数。
示例 1:
输入:nums = [10,2]
输出:”210”
示例 2:
输入:nums = [3,30,34,5,9]
输出:”9534330”
排序后直接拼接
核心在于需要重新定义排序的比较函数。也可以转换为字符串后比较。
1 | class Solution { |
543. 二叉树的直径
给定一棵二叉树,你需要计算它的直径长度。一棵二叉树的直径长度是任意两个结点路径长度中的最大值。这条路径可能穿过也可能不穿过根结点。
示例 :
给定二叉树
1
/ \
2 3
/ \
4 5
返回 3, 它的长度是路径 [4,2,1,3] 或者 [5,2,1,3]。
深度优先搜索
直径就是两个节点路径长度的最大值。
每个路径长度可以拆解为左子树和右子树的深度两部分之和。
1 | /** |
NC99 多叉树的直径
如果换成多叉树,该如何处理呢?
约瑟夫问题-圆圈中最后剩下的数字
0,1,···,n-1这n个数字排成一个圆圈,从数字0开始,每次从这个圆圈里删除第m个数字(删除后从下一个数字开始计数)。求出这个圆圈里剩下的最后一个数字。
例如,0、1、2、3、4这5个数字组成一个圆圈,从数字0开始每次删除第3个数字,则删除的前4个数字依次是2、0、4、1,因此最后剩下的数字是3。
示例 1:
输入: n = 5, m = 3
输出: 3
示例 2:
输入: n = 10, m = 17
输出: 2
这个问题是以弗拉维奥·约瑟夫命名的,他是1世纪的一名犹太历史学家。他在自己的日记中写道,他和他的40个战友被罗马军队包围在洞中。他们讨论是自杀还是被俘,最终决定自杀,并以抽签的方式决定谁杀掉谁。约瑟夫斯和另外一个人是最后两个留下的人。约瑟夫斯说服了那个人,他们将向罗马军队投降,不再自杀。约瑟夫斯把他的存活归因于运气或天意,他不知道是哪一个
真是一个有趣的故事
首先,长度为 n 的序列会先删除第 m % n 个元素,然后剩下一个长度为 n - 1 的序列。
那么,我们可以递归地求解 f(n - 1, m),就可以知道对于剩下的 n - 1 个元素,最终会留下第几个元素,我们设答案为 x = f(n - 1, m)。
由于我们删除了第 m % n 个元素,将序列的长度变为 n - 1。
当我们知道了 f(n - 1, m) 对应的答案 x 之后,我们也就可以知道,长度为 n 的序列最后一个删除的元素,应当是从 m % n 开始数的第 x 个元素。因此有 f(n, m) = (m % n + x) % n = (m + x) % n。
假设初始只有1个人,序号为0,则只能选0。
假设第n-1次选中x,则第n次会选中(x+m)%n
1 | class Solution { |
128. 最长连续序列
给定一个未排序的整数数组 nums ,找出数字连续的最长序列(不要求序列元素在原数组中连续)的长度。
请你设计并实现时间复杂度为 O(n) 的算法解决此问题。
示例 1:
输入:nums = [100,4,200,1,3,2]
输出:4
解释:最长数字连续序列是 [1, 2, 3, 4]。它的长度为 4。
示例 2:
输入:nums = [0,3,7,2,5,8,4,6,0,1]
输出:9
直观想法是分别遍历每个数x,然后看x+1, x+2, …等数是否在数组中,若在则连续序列长度加1。
使用哈希表提高查找效率,同时,若x-1已经做过判断,则x无需再判断。
这样,平均每个元素只会访问一次,时间复杂度O(n)
空间复杂度O(n)
1 | class Solution { |
二叉搜索树的第K大节点
给定一棵二叉搜索树,请找出其中第 k 大的节点的值。
示例 1:
输入: root = [3,1,4,null,2], k = 1
3
/
1 4
2
输出: 4
示例 2:
输入: root = [5,3,6,2,4,null,null,1], k = 3
5
/
3 6
/
2 4
/
1
输出: 4
中序遍历然后取倒数第k个数
1 | /** |
略微优化, 直接一次遍历搞定
1 | /** |
297. 二叉树的序列化与反序列化
序列化是将一个数据结构或者对象转换为连续的比特位的操作,进而可以将转换后的数据存储在一个文件或者内存中,同时也可以通过网络传输到另一个计算机环境,采取相反方式重构得到原数据。
请设计一个算法来实现二叉树的序列化与反序列化。这里不限定你的序列 / 反序列化算法执行逻辑,你只需要保证一个二叉树可以被序列化为一个字符串并且将这个字符串反序列化为原始的树结构。
提示: 输入输出格式与 LeetCode 目前使用的方式一致,详情请参阅 LeetCode 序列化二叉树的格式。你并非必须采取这种方式,你也可以采用其他的方法解决这个问题。
DFS
可以深度优先或广度优先
1 | /** |
方法二:括号表示编码 + 递归下降解码
TODO
887. 鸡蛋掉落
给你 k 枚相同的鸡蛋,并可以使用一栋从第 1 层到第 n 层共有 n 层楼的建筑。
已知存在楼层 f ,满足 0 <= f <= n ,任何从 高于 f 的楼层落下的鸡蛋都会碎,从 f 楼层或比它低的楼层落下的鸡蛋都不会破。
每次操作,你可以取一枚没有碎的鸡蛋并把它从任一楼层 x 扔下(满足 1 <= x <= n)。如果鸡蛋碎了,你就不能再次使用它。如果某枚鸡蛋扔下后没有摔碎,则可以在之后的操作中 重复使用 这枚鸡蛋。
请你计算并返回要确定 f 确切的值 的 最小操作次数 是多少?
示例 1:
输入:k = 1, n = 2
输出:2
解释:
鸡蛋从 1 楼掉落。如果它碎了,肯定能得出 f = 0 。
否则,鸡蛋从 2 楼掉落。如果它碎了,肯定能得出 f = 1 。
如果它没碎,那么肯定能得出 f = 2 。
因此,在最坏的情况下我们需要移动 2 次以确定 f 是多少。
示例 2:
输入:k = 2, n = 6
输出:3
示例 3:
输入:k = 3, n = 14
输出:4
听说是原谷歌经典面试题,
动态规划
考虑特殊情况:
- 有任意个鸡蛋,直接用二分法
- 有1个鸡蛋,只能从低到高一层楼一层楼的遍历
- 有2个鸡蛋,100层楼,可以考虑分10层,这样最大需要19次,也可以考虑让第一个鸡蛋和第二个鸡蛋最大尝试次数之和均匀一点,
- 有k个鸡蛋,n层楼,dp[k, n]。选择任意扔鸡蛋的位置为x,则有两种情况且:
- 鸡蛋碎了,则消耗一个鸡蛋,答案在x层下方的x-1楼层中。t1 = dp[k-1, x-1]
- 鸡蛋没碎,则消耗0个鸡蛋,答案在x层上方剩下的n-x楼层中。t2 = dp[k, n-x]
接下来就是寻找x的位置,然后计算每个x的取值情况下的最小值。
关于x的函数t1和t2, t1单调递增,t2单调递减,二者分段函数的最小值在交点处,考虑离散函数特点,选交点左右两个数。
1 | class Solution { |
方法二:决策单调性
方法三:数学法
二分查找以及多种变形
原始题
给定一个 n 个元素有序的(升序)整型数组 nums 和一个目标值 target ,写一个函数搜索 nums 中的 target,如果目标值存在返回下标,否则返回 -1。
示例 1:
输入: nums = [-1,0,3,5,9,12], target = 9
输出: 4
解释: 9 出现在 nums 中并且下标为 4
示例 2:
输入: nums = [-1,0,3,5,9,12], target = 2
输出: -1
解释: 2 不存在 nums 中因此返回 -1
1 | class Solution { |
1 | class Solution: |
34. 在排序数组中查找元素的第一个和最后一个位置
给定一个按照升序排列的整数数组 nums,和一个目标值 target。找出给定目标值在数组中的开始位置和结束位置。
如果数组中不存在目标值 target,返回 [-1, -1]。
进阶:
你可以设计并实现时间复杂度为 O(log n) 的算法解决此问题吗?
示例 1:
输入:nums = [5,7,7,8,8,10], target = 8
输出:[3,4]
示例 2:
输入:nums = [5,7,7,8,8,10], target = 6
输出:[-1,-1]
示例 3:
输入:nums = [], target = 0
输出:[-1,-1]
1 | class Solution { |
35. 搜索插入位置
给定一个排序数组和一个目标值,在数组中找到目标值,并返回其索引。如果目标值不存在于数组中,返回它将会被按顺序插入的位置。
请必须使用时间复杂度为 O(log n) 的算法。
示例 1:
输入: nums = [1,3,5,6], target = 5
输出: 2
示例 2:
输入: nums = [1,3,5,6], target = 2
输出: 1
示例 3:
输入: nums = [1,3,5,6], target = 7
输出: 4
寻找第一个大于等于目标值的元素
1 | class Solution { |
更清晰的写法
1 | class Solution { |
278. 第一个错误的版本
你是产品经理,目前正在带领一个团队开发新的产品。不幸的是,你的产品的最新版本没有通过质量检测。由于每个版本都是基于之前的版本开发的,所以错误的版本之后的所有版本都是错的。
假设你有 n 个版本 [1, 2, …, n],你想找出导致之后所有版本出错的第一个错误的版本。
你可以通过调用 bool isBadVersion(version) 接口来判断版本号 version 是否在单元测试中出错。实现一个函数来查找第一个错误的版本。你应该尽量减少对调用 API 的次数。
示例 1:
输入:n = 5, bad = 4
输出:4
解释:
调用 isBadVersion(3) -> false
调用 isBadVersion(5) -> true
调用 isBadVersion(4) -> true
所以,4 是第一个错误的版本。
示例 2:
输入:n = 1, bad = 1
输出:1
1 | // The API isBadVersion is defined for you. |
寻找第一个错误的版本
1 | // The API isBadVersion is defined for you. |
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
示例 2:
输入:n = 1, pick = 1
输出:1
示例 3:
输入:n = 2, pick = 1
输出:1
示例 4:
输入:n = 2, pick = 2
输出:2
1 | /** |
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
二分然后双指针
时间复杂度O(logn + k)
1 | class Solution { |
162. 寻找峰值
峰值元素是指其值严格大于左右相邻值的元素。
给你一个整数数组 nums,找到峰值元素并返回其索引。数组可能包含多个峰值,在这种情况下,返回 任何一个峰值 所在位置即可。
你可以假设 nums[-1] = nums[n] = -∞ 。
你必须实现时间复杂度为 O(log n) 的算法来解决此问题。
示例 1:
输入:nums = [1,2,3,1]
输出:2
解释:3 是峰值元素,你的函数应该返回其索引 2。
示例 2:
输入:nums = [1,2,1,3,5,6,4]
输出:1 或 5
解释:你的函数可以返回索引 1,其峰值元素为 2;
或者返回索引 5, 其峰值元素为 6。
1 | class Solution { |
852. 山脉数组的峰顶索引
符合下列属性的数组 arr 称为 山脉数组 :
arr.length >= 3
存在 i(0 < i < arr.length - 1)使得:
arr[0] < arr[1] < … arr[i-1] < arr[i]
arr[i] > arr[i+1] > … > arr[arr.length - 1]
给你由整数组成的山脉数组 arr ,返回任何满足 arr[0] < arr[1] < … arr[i - 1] < arr[i] > arr[i + 1] > … > arr[arr.length - 1] 的下标 i 。
示例 1:
输入:arr = [0,1,0]
输出:1
示例 2:
输入:arr = [0,2,1,0]
输出:1
示例 3:
输入:arr = [0,10,5,2]
输出:1
示例 4:
输入:arr = [3,4,5,1]
输出:2
示例 5:
输入:arr = [24,69,100,99,79,78,67,36,26,19]
输出:2
此题与寻找峰值一题比较相似,但是此题只存在一个解。
上一题的答案可以直接用,并且可以无需考虑边界问题了。
1 | class Solution { |
9. 回文数
给你一个整数 x ,如果 x 是一个回文整数,返回 true ;否则,返回 false 。
回文数是指正序(从左向右)和倒序(从右向左)读都是一样的整数。
例如,121 是回文,而 123 不是。
示例 1:
输入:x = 121
输出:true
示例 2:
输入:x = -121
输出:false
解释:从左向右读, 为 -121 。 从右向左读, 为 121- 。因此它不是一个回文数。
示例 3:
输入:x = 10
输出:false
解释:从右向左读, 为 01 。因此它不是一个回文数。
翻转一半的数
1 | class Solution { |
转换为string后双指针遍历
1 | class Solution { |
14. 最长公共前缀
编写一个函数来查找字符串数组中的最长公共前缀。
如果不存在公共前缀,返回空字符串 “”。
示例 1:
输入:strs = [“flower”,”flow”,”flight”]
输出:”fl”
示例 2:
输入:strs = [“dog”,”racecar”,”car”]
输出:””
解释:输入不存在公共前缀。
每两个字符串合并
1 | class Solution { |
纵向扫描
1 | class Solution { |
32. 最长有效括号
给你一个只包含 ‘(‘和 ‘)’的字符串,找出最长有效(格式正确且连续)括号子串的长度。
示例 1:
输入:s = “(()”
输出:2
解释:最长有效括号子串是 “()”
示例 2:
输入:s = “)()())”
输出:4
解释:最长有效括号子串是 “()()”
示例 3:
输入:s = “”
输出:0
先做一个热身题
20. 有效的括号
给定一个只包括 ‘(‘,’)’,’{‘,’}’,’[‘,’]’ 的字符串 s ,判断字符串是否有效。
有效字符串需满足:
左括号必须用相同类型的右括号闭合。
左括号必须以正确的顺序闭合。
示例 1:
输入:s = “()”
输出:true
示例 2:
输入:s = “()[]{}”
输出:true
示例 3:
输入:s = “(]”
输出:false
示例 4:
输入:s = “([)]”
输出:false
示例 5:
输入:s = “{[]}”
输出:true
使用栈的方法
1 | class Solution: |
C++版本
1 | class Solution { |
最长有效括号
动态规划
记dp[i]为以序号i结尾的最长有效括号的长度。则有以下几种情况:
- 以(结尾的串肯定不合法,直接赋0
- 以)结尾的串,分两种情况:
- 如果s[i-1]为(, 则dp[i] = dp[i-2] + 2
- 如果s[i-1]为), 且dp[i-1]是一个有效的括号段,且这个括号段前一个元素是(, 则dp[i] = dp[i-1] + dp[i-dp[i-1]-2] + 2
时间复杂度和空间复杂度均为O(n)
1 | class Solution { |
栈的方法
保持栈顶元素为当前最后一个没有被匹配的右括号的下标。
若为左括号,则将其序号入栈
若为右括号,则先弹出栈顶元素,然后判断:
- 若栈为空,则将当前i入栈
- 不为空,计算i-s.top()则为以该右括号结尾的最大有效括号的长度
1 | class Solution { |
两趟遍历
不是很好理解,或者说有点巧妙
用两个计数器left和right分别记录左括号和右括号的个数。两次扫描
- 先从左到右扫描,
- 如果left与right相等, 记录差值
- 如果left < right, 计数器清零
- 从右到左扫描,
- 如果left与right相等, 记录差值
- 如果left > right, 计数器清零
1 | class Solution { |
组合(系列)
77. 组合
给定两个整数 n 和 k,返回范围 [1, n] 中所有可能的 k 个数的组合。
你可以按 任何顺序 返回答案。
示例 1:
输入:n = 4, k = 2
输出:
[
[2,4],
[3,4],
[2,3],
[1,2],
[1,3],
[1,4],
]
示例 2:
输入:n = 1, k = 1
输出:[[1]]
回溯算法
1 | class Solution { |
字典序方法
TODO
39. 组合总和
给你一个 无重复元素 的整数数组candidates 和一个目标整数target,找出candidates中可以使数字和为目标数 target 的 所有 不同组合 ,并以列表形式返回。你可以按 任意顺序 返回这些组合。
candidates 中的 同一个 数字可以 无限制重复被选取 。如果至少一个数字的被选数量不同,则两种组合是不同的。
对于给定的输入,保证和为 target 的不同组合数少于 150 个。
示例 1:
输入:candidates = [2,3,6,7], target = 7
输出:[[2,2,3],[7]]
解释:
2 和 3 可以形成一组候选,2 + 2 + 3 = 7 。注意 2 可以使用多次。
7 也是一个候选, 7 = 7 。
仅有这两种组合。
示例 2:
输入: candidates = [2,3,5], target = 8
输出: [[2,2,2,2],[2,3,3],[3,5]]
示例 3:
输入: candidates = [2], target = 1
输出: []
回溯法
1 | class Solution { |
换一种写法,用循环构建多个分支。
1 | class Solution { |
40. 组合总和 II
给定一个候选人编号的集合 candidates 和一个目标数 target ,找出 candidates 中所有可以使数字和为 target 的组合。
candidates 中的每个数字在每个组合中只能使用 一次 。
注意:解集不能包含重复的组合。
示例 1:
输入: candidates = [10,1,2,7,6,1,5], target = 8,
输出:
[
[1,1,6],
[1,2,5],
[1,7],
[2,6]
]
示例 2:
输入: candidates = [2,5,2,1,2], target = 5,
输出:
[
[1,2,2],
[5]
]
回溯
1 | class Solution { |
239. 滑动窗口最大值
给你一个整数数组 nums,有一个大小为k的滑动窗口从数组的最左侧移动到数组的最右侧。你只可以看到在滑动窗口内的 k 个数字。滑动窗口每次只向右移动一位。
返回 滑动窗口中的最大值 。
示例 1:
输入:nums = [1,3,-1,-3,5,3,6,7], k = 3
输出:[3,3,5,5,6,7]
解释:
滑动窗口的位置 最大值
[1 3 -1] -3 5 3 6 7 3
1 [3 -1 -3] 5 3 6 7 3
1 3 [-1 -3 5] 3 6 7 5
1 3 -1 [-3 5 3] 6 7 5
1 3 -1 -3 [5 3 6] 7 6
1 3 -1 -3 5 [3 6 7] 7
示例 2:
输入:nums = [1], k = 1
输出:[1]
优先队列
时间复杂度O(nlogn)
1 | class Solution { |
双端队列构建单调递减队列
1 | class Solution { |
143. 重排链表
给定一个单链表 L 的头节点 head ,单链表 L 表示为:
L0 → L1 → … → Ln - 1 → Ln
请将其重新排列后变为:
L0 → Ln → L1 → Ln - 1 → L2 → Ln - 2 → …
不能只是单纯的改变节点内部的值,而是需要实际的进行节点交换。
示例 1:
输入:head = [1,2,3,4]
输出:[1,4,2,3]
示例 2:
输入:head = [1,2,3,4,5]
输出:[1,5,2,4,3]
链表中点+反转链表+合并链表
1 | /** |
460. LFU 缓存
请你为 最不经常使用(LFU)缓存算法设计并实现数据结构。
实现 LFUCache 类:
LFUCache(int capacity) - 用数据结构的容量 capacity 初始化对象 int get(int key) - 如果键 key 存在于缓存中,则获取键的值,否则返回 -1 。 void put(int key,
int value) - 如果键 key 已存在,则变更其值;如果键不存在,请插入键值对。当缓存达到其容量 capacity
时,则应该在插入新项之前,移除最不经常使用的项。在此问题中,当存在平局(即两个或更多个键具有相同使用频率)时,应该去除 最近最久未使用 的键。 为了确定最不常使用的键,可以为缓存中的每个键维护一个 使用计数器
。使用计数最小的键是最久未使用的键。
当一个键首次插入到缓存中时,它的使用计数器被设置为 1 (由于 put 操作)。对缓存中的键执行 get 或 put 操作,使用计数器的值将会递增。
函数 get 和 put 必须以 O(1) 的平均时间复杂度运行。
示例:
输入:
[“LFUCache”, “put”, “put”, “get”, “put”, “get”, “get”, “put”, “get”, “get”, “get”]
[[2], [1, 1], [2, 2], [1], [3, 3], [2], [3], [4, 4], [1], [3], [4]]
输出:
[null, null, null, 1, null, -1, 3, null, -1, 3, 4]
解释:
// cnt(x) = 键 x 的使用计数
// cache=[] 将显示最后一次使用的顺序(最左边的元素是最近的) LFUCache lfu = new LFUCache(2); lfu.put(1, 1); //
cache=[1,_], cnt(1)=1 lfu.put(2, 2);
// cache=[2,1], cnt(2)=1, cnt(1)=1 lfu.get(1);
// 返回 1
// cache=[1,2], cnt(2)=1, cnt(1)=2 lfu.put(3, 3);
// 去除键 2 ,因为 cnt(2)=1 ,使用计数最小
// cache=[3,1], cnt(3)=1, cnt(1)=2 lfu.get(2);
// 返回 -1(未找到)
lfu.get(3);
// 返回 3
// cache=[3,1], cnt(3)=2, cnt(1)=2 lfu.put(4, 4);
// 去除键 1 ,1 和 3 的 cnt 相同,但 1 最久未使用
// cache=[4,3],
cnt(4)=1, cnt(3)=2 lfu.get(1);
// 返回 -1(未找到) lfu.get(3);
// 返回 3
// cache=[3,4], cnt(4)=1, cnt(3)=3 lfu.get(4);
// 返回 4
// cache=[3,4], cnt(4)=2, cnt(3)=3
提示:
0 <= capacity <= 104 0 <= key <= 105 0 <= value <= 109 最多调用 2 * 105 次 get 和 put 方法
使用哈希表+平衡二叉树
最好使用堆,但是堆支持动态更新非头节点,使用平衡二叉树替代
时间复杂度O(logn)
空间复杂度O(capacity)
1 | struct Node{ |
两个哈希表
一个哈希表frequency_table存储频率和对应频率下的节点,使用双向链表解决冲突,
队头的节点是最近的节点,队尾的节点是较久的节点。
每个节点存储,key,value,freq
一个哈希表key_table存储key和对应缓存在双向链表中的地址。
时间复杂度变为O(1)
1 | struct Node{ |
93. 复原 IP 地址
有效 IP 地址 正好由四个整数(每个整数位于 0 到 255 之间组成,且不能含有前导 0),整数之间用 ‘.’ 分隔。
例如:”0.1.2.201” 和 “192.168.1.1” 是 有效 IP 地址,但是 “0.011.255.245”、”192.168.1.312” 和 “192.168@1.1“ 是 无效 IP 地址。
给定一个只包含数字的字符串 s ,用以表示一个 IP 地址,返回所有可能的有效 IP 地址,这些地址可以通过在 s 中插入 ‘.’ 来形成。你 不能 重新排序或删除 s 中的任何数字。你可以按 任何 顺序返回答案。
示例 1:
输入:s = “25525511135”
输出:[“255.255.11.135”,”255.255.111.35”]
示例 2:
输入:s = “0000”
输出:[“0.0.0.0”]
示例 3:
输入:s = “101023”
输出:[“1.0.10.23”,”1.0.102.3”,”10.1.0.23”,”10.10.2.3”,”101.0.2.3”]
提示:
1 <= s.length <= 20
s 仅由数字组成
回溯算法
1 | class Solution: |
48. 旋转图像
给定一个 n × n 的二维矩阵 matrix 表示一个图像。请你将图像顺时针旋转 90 度。
你必须在 原地 旋转图像,这意味着你需要直接修改输入的二维矩阵。请不要 使用另一个矩阵来旋转图像。
对角翻转+镜像翻转
1 | class Solution: |
直接翻转
每次翻转会引起四个数的改变。
四个数的坐标比较难定。
关键规律:
对于矩阵中第 i 行的第 j 个元素,在旋转后,它出现在倒数第 i 列的第 j 个位置。
对应公式:row, col = col, n-row-1
推导得到四个坐标,实际循环的时候,要先将最后一个数放到第一个数
1 | class Solution: |
22. 括号生成
本文字数: 645 阅读时长 ≈ 1 分钟
数字 n代表生成括号的对数,请你设计一个函数,用于能够生成所有可能的并且 有效的 括号组合。
示例 1:
输入:n = 3
输出:[“((()))”,”(()())”,”(())()”,”()(())”,”()()()”]
示例 2:
输入:n = 1
输出:[“()”]
提示:
1 <= n <= 8
回溯算法
左右括号从 n 开始递减
剩余左括号总数要小于等于右括号
1 | class Solution: |
101. 对称二叉树
给你一个二叉树的根节点 root , 检查它是否轴对称。
示例 1:
输入:root = [1,2,2,3,4,4,3]
输出:true
示例 2:
输入:root = [1,2,2,null,3,null,3]
输出:false
提示:
树中节点数目在范围 [1, 1000] 内 -100 <= Node.val <= 100
进阶:你可以运用递归和迭代两种方法解决这个问题吗?
递归法
1 | # Definition for a binary tree node. |
广度优先遍历-队列
1 | # Definition for a binary tree node. |
328. 奇偶链表
给定单链表的头节点head,将所有索引为奇数的节点和索引为偶数的节点分别组合在一起,然后返回重新排序的列表。
第一个节点的索引被认为是 奇数 , 第二个节点的索引为偶数 ,以此类推。
请注意,偶数组和奇数组内部的相对顺序应该与输入时保持一致。
你必须在O(1)的额外空间复杂度和O(n)的时间复杂度下解决这个问题。
示例 1:
输入: head = [1,2,3,4,5]
输出: [1,3,5,2,4]
示例 2:
输入: head = [2,1,3,5,6,4,7]
输出: [2,3,6,7,1,5,4]
直接一次遍历
将偶数节点放到新链表,结束后链接到旧链表之后
1 | # Definition for singly-linked list. |
41. 缺失的第一个正数
给你一个未排序的整数数组 nums ,请你找出其中没有出现的最小的正整数。
请你实现时间复杂度为 O(n) 并且只使用常数级别额外空间的解决方案。
示例 1:
输入:nums = [1,2,0]
输出:3
示例 2:
输入:nums = [3,4,-1,1]
输出:2
示例 3:
输入:nums = [7,8,9,11,12]
输出:1
提示:
1 <= nums.length <= 5 * 105
-231 <= nums[i] <= 231 - 1
直观的思路:哈希表
但是时间空间复杂度都是O(n),空间复杂度不满足题目的要求
1 | class Solution: |
改造当前数组为哈希表
数组长度为n,则数组中的数,如果存储的是[1,n], 则第一个缺失的数是n+1
否则缺失的数一定在[1,n]中的某一个。
1 | class Solution: |
交换方式
1 | class Solution: |
排序矩阵查找(系列)
240. 搜索二维矩阵 II
给定M×N矩阵,每一行、每一列都按升序排列,请编写代码找出某元素。
看到这题,最简单的就是直接一次遍历所有元素,时间复杂度是O(m*n)。
当然,看到升序,也比较容易想到二分查找,可以按行遍历m次,每次使用二分查找。
但是,还有没有其他更好的办法呢?
倒三角线遍历
观察发现,如果从右上角开始遍历,直到左下角结束,假设当前元素为cur,可以发现:
- 如果cur<target, 由于cur是这一行中最大的数,则可以舍弃这一行,cur下移
- 如果cur>target, 由于cur是这一列中最小的数,则可以舍弃这一列,cur左移
1 | class Solution: |
C++版本
1 | class Solution { |
当然, 从左下角走到右上角也是OK的, 代码如下:
1 | class Solution: |
正三角遍历
将矩阵划分为四块:左上、右上、左下、右下,每次可以排除其中一块
1 | class Solution: |
74. 搜索二维矩阵
编写一个高效的算法来判断m x n矩阵中,是否存在一个目标值。该矩阵具有如下特性:
每行中的整数从左到右按升序排列。
每行的第一个整数大于前一行的最后一个整数。
两次二分查找
可以先按第一列二分查找确定所在的行,然后再对行做一次二分
一次二分
将整个矩形视作一个一维数组,直接一次二分完成
1 | class Solution: |
C++版本
1 | class Solution { |
删除排序链表中的重复元素(系列)
删除重复元素,保留一个
给定一个已排序的链表的头 head , 删除所有重复的元素,使每个元素只出现一次 。返回 已排序的链表 。
1 | # Definition for singly-linked list. |
删除所有重复的元素
给定一个已排序的链表的头 head , 删除原始链表中所有重复数字的节点,只留下不同的数字 。
返回 已排序的链表 。
细节题, 关键点是有可能删除第一个元素,为了方便,一般需要添加一个dummy节点
1 | # Definition for singly-linked list. |
二叉树的合法性判断(系列)
验证二叉搜索树
给你一个二叉树的根节点 root ,判断其是否是一个有效的二叉搜索树。
有效 二叉搜索树定义如下:
节点的左子树只包含 小于 当前节点的数。
节点的右子树只包含 大于 当前节点的数。
所有左子树和右子树自身必须也是二叉搜索树。
直接递归判断
1 | # Definition for a binary tree node. |
中序遍历的思路
中序遍历得到的数组必然是从小到大有序排列的。
递归思路
时间复杂度和空间复杂度均为O(n)
1 | # Definition for a binary tree node. |
非递归思路
1 | # Definition for a binary tree node. |
用C++重写一遍加深记忆,这个时候就体现出Python写代码的方便性了
1 | /** |
二叉树的完全性检验
给定一个二叉树的 root ,确定它是否是一个 完全二叉树 。
在一个 完全二叉树 中,除了最后一个关卡外,所有关卡都是完全被填满的,
并且最后一个关卡中的所有节点都是尽可能靠左的。它可以包含 1 到 2^h 节点之间的最后一级 h 。
层序遍历的思路
如果将完全二叉数用数组存储,那么它的节点序号是顺序的。
如果有n个节点,则最后一个节点的序号应该是n-1
1 | # Definition for a binary tree node. |
寻找两个正序数组的中位数
给定两个大小分别为 m 和 n 的正序(从小到大)数组 nums1 和 nums2。请你找出并返回这两个正序数组的 中位数 。
算法的时间复杂度应该为 O(log (m+n)) 。
示例 1:
1 | 输入:nums1 = [1,3], nums2 = [2] |
示例 2:
1 | 输入:nums1 = [1,2], nums2 = [3,4] |
双指针法直接查找中位数
正常的解法是将两个数组合并,然后得到中位数,但是其实不用存储新数组,可以直接用双指针分别遍历,
分别取两个数组中较小的数,累积遍历(m+n)//2+1次即可。
考虑到奇数和偶数的差异,需要记录两个结果值。这里用left和right记录。
同时,还需要考虑如果有一个数组遍历完的情况
为了注重代码可读性,调整代码如下:
1 | class Solution: |
二分查找法-划分数组
时间复杂度:O(log min(m,n))
空间复杂度:O(1)
1 | class Solution { |
python3重写一次
1 | class Solution: |
二分查找法-查找第k大的数
时间复杂度O(log(m+n))
1 | class Solution: |
56. 合并区间
以数组 intervals 表示若干个区间的集合,其中单个区间为 intervals[i] = [starti, endi] 。请你合并所有重叠的区间,并返回 一个不重叠的区间数组,该数组需恰好覆盖输入中的所有区间 。
示例 1:
输入:intervals = [[1,3],[2,6],[8,10],[15,18]]
输出:[[1,6],[8,10],[15,18]]
解释:区间 [1,3] 和 [2,6] 重叠, 将它们合并为 [1,6].
示例 2:
输入:intervals = [[1,4],[4,5]]
输出:[[1,5]]
解释:区间 [1,4] 和 [4,5] 可被视为重叠区间。
排序后一次遍历
此题咋一看,还挺难,掌握思路后其实还蛮简单
1 | class Solution: |
C语言经典库函数
字符串转换整数 (atoi)
请你来实现一个 myAtoi(string s) 函数,使其能将字符串转换成一个 32 位有符号整数(类似 C/C++ 中的 atoi 函数)。
函数 myAtoi(string s) 的算法如下:
读入字符串并丢弃无用的前导空格
检查下一个字符(假设还未到字符末尾)为正还是负号,读取该字符(如果有)。 确定最终结果是负数还是正数。 如果两者都不存在,则假定结果为正。
读入下一个字符,直到到达下一个非数字字符或到达输入的结尾。字符串的其余部分将被忽略。
将前面步骤读入的这些数字转换为整数(即,”123” -> 123, “0032” -> 32)。如果没有读入数字,则整数为 0 。必要时更改符号(从步骤 2 开始)。
如果整数数超过 32 位有符号整数范围 [−231, 231 − 1] ,需要截断这个整数,使其保持在这个范围内。具体来说,小于 −231 的整数应该被固定为 −231 ,大于 231 − 1 的整数应该被固定为 231 − 1 。
返回整数作为最终结果。
注意:
本题中的空白字符只包括空格字符 ‘ ‘ 。
除前导空格或数字后的其余字符串外,请勿忽略 任何其他字符。
示例 1:
输入:s = “42”
输出:42
解释:加粗的字符串为已经读入的字符,插入符号是当前读取的字符。
第 1 步:”42”(当前没有读入字符,因为没有前导空格)
^
第 2 步:”42”(当前没有读入字符,因为这里不存在 ‘-‘ 或者 ‘+’)
^
第 3 步:”42”(读入 “42”)
^
解析得到整数 42 。
由于 “42” 在范围 [-231, 231 - 1] 内,最终结果为 42 。
示例 2:
输入:s = “ -42”
输出:-42
解释:
第 1 步:” -42”(读入前导空格,但忽视掉)
^
第 2 步:” -42”(读入 ‘-‘ 字符,所以结果应该是负数)
^
第 3 步:” -42”(读入 “42”)
^
解析得到整数 -42 。
由于 “-42” 在范围 [-231, 231 - 1] 内,最终结果为 -42 。
示例 3:
输入:s = “4193 with words”
输出:4193
解释:
第 1 步:”4193 with words”(当前没有读入字符,因为没有前导空格)
^
第 2 步:”4193 with words”(当前没有读入字符,因为这里不存在 ‘-‘ 或者 ‘+’)
^
第 3 步:”4193 with words”(读入 “4193”;由于下一个字符不是一个数字,所以读入停止)
^
解析得到整数 4193 。
由于 “4193” 在范围 [-231, 231 - 1] 内,最终结果为 4193 。
提示:
0 <= s.length <= 200
s 由英文字母(大写和小写)、数字(0-9)、’ ‘、’+’、’-‘ 和 ‘.’ 组成
方法一:一次遍历
注意扣细节。
- 前序空白字符直接过滤
- 空白字符之后只允许至多紧跟一个+或者-
- 符号之后必须是连续数字
- 数字部分简单看就是按数位求和。特别需要注意是否溢出,两种情况可能溢出:乘10的时候和累加当前数字的时候
- 累加当前数字的时候需要区分当前的符号位,因为正数和负数的绝对值相差1
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39class Solution {
public:
int myAtoi(string s) {
cout << INT_MAX << "\t" << INT_MIN;
int ans = 0;
int flag = 1;
int i = 0;
while (s[i] == ' '){
i++;
}
// 前序空白符号后,紧跟着的只能是一个+或-,如果有多个+、-则判定非法,返回0
if (s[i] == '+'){
i++;
}else if (s[i] == '-'){
flag = -1;
i++;
}
// 符号之后的一定要是数字,如果为字符则非法。忽略数字最后的其他字符
while (i < s.size() && s[i] <= '9' && s[i] >= '0' ){
int digit = s[i] - '0';
// cout << i << " " << digit << " ans:" << ans << endl;
if (ans > INT_MAX / 10){
return flag > 0 ? INT_MAX : INT_MIN;
}
if (ans == INT_MAX / 10 && flag > 0 && digit >= INT_MAX % 10){
return INT_MAX;
}
// MAX_MIN -2147483648 MAX_MAX 2147483647, 负数绝对值比正数大,此处应为>=, 否则边界情况,会溢出
if (ans == INT_MAX / 10 && flag < 0 && digit >= flag * (INT_MIN % 10)){
// cout << digit << INT_MIN % 10;
return INT_MIN;
}
ans = 10 * ans + digit;
i += 1;
}
return ans*flag;
}
};
方法二:有限状态机
一种很好的思路,可以将逻辑判断变得比较清晰,不容易出错。
但是实际上,也新增了一些麻烦。
1 | class Automation{ |
7. 整数反转 reverse-integer
给你一个 32 位的有符号整数 x ,返回将 x 中的数字部分反转后的结果。
如果反转后整数超过 32 位的有符号整数的范围 [−231, 231 − 1] ,就返回 0。
假设环境不允许存储 64 位整数(有符号或无符号)。
一次遍历
1 | class Solution { |
先转换为正数
1 | class Solution { |
二维数组的不同路径
62. 不同路径
一个机器人位于一个 m x n 网格的左上角 (起始点在下图中标记为 “Start” )。
机器人每次只能向下或者向右移动一步。机器人试图达到网格的右下角(在下图中标记为 “Finish” )。
问总共有多少条不同的路径?
组合数
总共要走m+n-n步,其中向下m-1步,向右n-1步,一个方向的选择确定后,另一个方向也就固定了。
所以其实是一个组合问题,从m+n-2个数中选择m-1个数
1 | class Solution: |
动态规划
最终走到终点有两种选择,从上到下或者从左到右。
1 | class Solution: |
63. 不同路径 II
一个机器人位于一个 m x n 网格的左上角 (起始点在下图中标记为 “Start” )。
机器人每次只能向下或者向右移动一步。机器人试图达到网格的右下角(在下图中标记为 “Finish”)。
现在考虑网格中有障碍物。那么从左上角到右下角将会有多少条不同的路径?
网格中的障碍物和空位置分别用 1 和 0 来表示。
动态规划
1 | class Solution: |
滚动数组优化
二叉树的路径问题(系列)
112. 路径总和
给你二叉树的根节点 root 和一个表示目标和的整数 targetSum 。判断该树中是否存在 根节点到叶子节点 的路径,这条路径上所有节点值相加等于目标和 targetSum 。如果存在,返回 true ;否则,返回 false 。
叶子节点 是指没有子节点的节点。
深度优先遍历
1 | # Definition for a binary tree node. |
广度优先遍历
1 | # Definition for a binary tree node. |
113. 路径总和 II
给你二叉树的根节点 root 和一个整数目标和 targetSum ,找出所有 从根节点到叶子节点 路径总和等于给定目标和的路径。
叶子节点 是指没有子节点的节点。
深度优先遍历
重点在弹出的动作,方便下次遍历
1 | # Definition for a binary tree node. |
广度优先遍历
在找到和相等的节点时,需要反查到根节点。为此,需要有一个dict记录节点的父节点
理解起来相对更容易一点
1 | # Definition for a binary tree node. |
437. 路径总和 III
给定一个二叉树的根节点 root ,和一个整数 targetSum ,求该二叉树里节点值之和等于 targetSum 的 路径 的数目。
路径 不需要从根节点开始,也不需要在叶子节点结束,但是路径方向必须是向下的(只能从父节点到子节点)。
深度优先遍历
定义rootSum为从root节点开始往下得到的路径和为目标值的路径个数
则原问题等于三个子问题的和:
根节点往下路径和为目标值的个数
左子树的解
右子树的解
1 | # Definition for a binary tree node. |
前缀路径和
【经典方法】
用dict记录从根节点到当前节点的路径(不含当前节点)上每个节点的路径和
1 | # Definition for a binary tree node. |
257. 二叉树的所有路径
给你一个二叉树的根节点 root ,按 任意顺序 ,返回所有从根节点到叶子节点的路径。
叶子节点 是指没有子节点的节点。
深度优先遍历
题目要返回的是字符串形式的路径,表示无语
1 | # Definition for a binary tree node. |
广度优先遍历
1 | # Definition for a binary tree node. |
124. 二叉树中的最大路径和
路径 被定义为一条从树中任意节点出发,沿父节点-子节点连接,达到任意节点的序列。同一个节点在一条路径序列中 至多出现一次 。该路径 至少包含一个 节点,且不一定经过根节点。
路径和 是路径中各节点值的总和。
给你一个二叉树的根节点 root ,返回其 最大路径和 。
递归
1 | # Definition for a binary tree node. |
求根节点到叶节点数字之和
给你一个二叉树的根节点 root ,树中每个节点都存放有一个 0 到 9 之间的数字。
每条从根节点到叶节点的路径都代表一个数字:
例如,从根节点到叶节点的路径 1 -> 2 -> 3 表示数字 123 。
计算从根节点到叶节点生成的 所有数字之和 。
叶节点 是指没有子节点的节点。
深度优先遍历
1 | # Definition for a binary tree node. |
广度优先遍历
1 | # Definition for a binary tree node. |
编辑距离
给你两个单词 word1 和 word2, 请返回将 word1 转换成 word2 所使用的最少操作数 。
你可以对一个单词进行如下三种操作:
插入一个字符
删除一个字符
替换一个字符
示例 1:
输入:word1 = “horse”, word2 = “ros”
输出:3
解释:
horse -> rorse (将 ‘h’ 替换为 ‘r’)
rorse -> rose (删除 ‘r’)
rose -> ros (删除 ‘e’)
示例 2:
输入:word1 = “intention”, word2 = “execution”
输出:5
解释:
intention -> inention (删除 ‘t’)
inention -> enention (将 ‘i’ 替换为 ‘e’)
enention -> exention (将 ‘n’ 替换为 ‘x’)
exention -> exection (将 ‘n’ 替换为 ‘c’)
exection -> execution (插入 ‘u’)
动态规划
对于两个串A和B,编辑动作可以归纳为三类:
- A后添加一个数字
- B后添加一个数字
- A修改一个数字
dp[i][j]表示A的前i个字符和B的前j个字符的编辑距离。
可以拆解为三个子问题:
- dp[i-1][j], A的前i-1个字符和B的前j个字符, 可以通过A后添加一个数字得到目标问题
- dp[i][i-1], 同理,可以在B后添加一个数字得到目标问题
- dp[i-1][j-1], A的前i-1个字符和B的前j-1个字符, 我们可以修改A的第i个字符使之和B的第j个字符一致得到目标问题。
如果二者原本相同,则不需要修改,否则编辑距离+1。
1 | class Solution { |
回文链表
给你一个单链表的头节点 head ,请你判断该链表是否为回文链表。如果是,返回 true ;否则,返回 false 。
示例 1:
输入:head = [1,2,2,1]
输出:true
示例 2:
输入:head = [1,2]
输出:false
提示:
链表中节点数目在范围[1, 10^5] 内
0 <= Node.val <= 9
进阶:你能否用O(n) 时间复杂度和 O(1) 空间复杂度解决此题?
遍历得到数组然后再判断
1 | /** |
翻转链表后半段,然后在比较
空间复杂度可以降低到O(1)
1 | /** |
数字转换为十六进制数
牛客网进制转换
描述
给定一个十进制数 M ,以及需要转换的进制数 N 。将十进制数 M 转化为 N 进制数。
当 N 大于 10 以后, 应在结果中使用大写字母表示大于 10 的一位,如 ‘A’ 表示此位为 10 , ‘B’ 表示此位为 11 。
若 M 为负数,应在结果中保留负号。
1 | # |
力扣转换16进制数
这个一个位运算的题目,需要对原码、反码、补码等知识了解比较清楚
1 | class Solution { |
感觉用C++刷题虽然会慢一点,但是感觉会很清晰,要不后面还是用C++刷题吧
前K个高频单词
给定一个单词列表 words 和一个整数 k ,返回前 k 个出现次数最多的单词。
返回的答案应该按单词出现频率由高到低排序。如果不同的单词有相同出现频率, 按字典顺序 排序。
示例 1:
输入: words = [“i”, “love”, “leetcode”, “i”, “love”, “coding”], k = 2
输出: [“i”, “love”]
解析: “i” 和 “love” 为出现次数最多的两个单词,均为2次。
注意,按字母顺序 “i” 在 “love” 之前。
示例 2:
输入: [“the”, “day”, “is”, “sunny”, “the”, “the”, “the”, “sunny”, “is”, “is”], k = 4
输出: [“the”, “is”, “sunny”, “day”]
解析: “the”, “is”, “sunny” 和 “day” 是出现次数最多的四个单词,
出现次数依次为 4, 3, 2 和 1 次。
注意:
1 <= words.length <= 500
1 <= words[i] <= 10
words[i] 由小写英文字母组成。
k 的取值范围是 [1, 不同 words[i] 的数量]
进阶:尝试以 O(n log k) 时间复杂度和 O(n) 空间复杂度解决。
哈希表+排序
时间复杂度:O(nlogn)
python元组排序,可以一次排序完成
1 | class Solution: |
写法上还可以有点不一样,
1 | class Solution: |
哈希表 + 优先队列
1 | class Solution: |
逆波兰表达式求值&&表达式计算器
1. 逆波兰表达式求值
根据 逆波兰表示法,求表达式的值。
有效的算符包括 +、-、*、/ 。每个运算对象可以是整数,也可以是另一个逆波兰表达式。
注意 两个整数之间的除法只保留整数部分。
可以保证给定的逆波兰表达式总是有效的。换句话说,表达式总会得出有效数值且不存在除数为 0 的情况。
示例 1:
输入:tokens = [“2”,”1”,”+”,”3”,”*”]
输出:9
解释:该算式转化为常见的中缀算术表达式为:((2 + 1) * 3) = 9
示例 2:
输入:tokens = [“4”,”13”,”5”,”/“,”+”]
输出:6
解释:该算式转化为常见的中缀算术表达式为:(4 + (13 / 5)) = 6
示例 3:
输入:tokens = [“10”,”6”,”9”,”3”,”+”,”-11”,”“,”/“,”“,”17”,”+”,”5”,”+”]
输出:22
解释:该算式转化为常见的中缀算术表达式为:
((10 * (6 / ((9 + 3) * -11))) + 17) + 5
= ((10 * (6 / (12 * -11))) + 17) + 5
= ((10 * (6 / -132)) + 17) + 5
= ((10 * 0) + 17) + 5
= (0 + 17) + 5
= 17 + 5
= 22
提示:
1 <= tokens.length <= 104
tokens[i] 是一个算符(”+”、”-“、”*” 或 “/“),或是在范围 [-200, 200] 内的一个整数
逆波兰表达式:
逆波兰表达式是一种后缀表达式,所谓后缀就是指算符写在后面。
平常使用的算式则是一种中缀表达式,如 ( 1 + 2 ) * ( 3 + 4 ) 。
该算式的逆波兰表达式写法为 ( ( 1 2 + ) ( 3 4 + ) * ) 。
逆波兰表达式主要有以下两个优点:
去掉括号后表达式无歧义,上式即便写成 1 2 + 3 4 + * 也可以依据次序计算出正确结果。
适合用栈操作运算:遇到数字则入栈;遇到算符则取出栈顶两个数字进行计算,并将结果压入栈中
栈
题目限制所有的表达式都是合法的,可以使用栈。
将所有的数字全部入栈,碰到符号时,弹出两个栈顶元素,计算结果后入栈。
注意除法只保留整数部分,对于负数的情况需要特殊处理
1 | class Solution: |
2. 表达式计算器的通用套路
能同时解决leetcode 224,227,772
双栈的解法
循环遍历每个元素:
若为空格,跳过
若为左括号,入栈
若为右括号,则计算,直到碰到左括号
若为数字,则入栈
若为符号,则先计算,直到碰到左括号,然后符号入栈
细节需要注意:开头为符号以及括号内开头为符号的情况
1 | class Solution: |
对于+、-、*、/只需要考虑入栈时候的优先级判断即可, 但是代码细节需要做一些微调
1 | class Solution: |
最小路径和
给定一个包含非负整数的 m x n 网格 grid ,请找出一条从左上角到右下角的路径,使得路径上的数字总和为最小。
说明:每次只能向下或者向右移动一步。
动态规划
dp[i][j]表示从左上角到(i,j)位置的最短路径和
对于第一行,i=0, j<n, dp[i][j] = dp[i][j-1]+grid[i][j]
对于第一列,j=0, i<m, dp[i][j] = dp[i-1][j]+grid[i][j]
对于其他行的位置,i<m, j< n,
dp[i][j] = min(dp[i][j-1], dp[i-1][j]) + grid[i][j]
1 | class Solution: |
多数元素
给定一个大小为 n 的数组,找到其中的多数元素。多数元素是指在数组中出现次数 大于 ⌊ n/2 ⌋ 的元素。
你可以假设数组是非空的,并且给定的数组总是存在多数元素。
示例 1:
输入:[3,2,3]
输出:3
示例 2:
输入:[2,2,1,1,1,2,2]
输出:2
哈希表法
1 | class Solution: |
排序法
1 | class Solution: |
摩尔投票法
有点神奇!
如果数字相同就+1,不同就-1
1 | class Solution: |
分治
随机化
平衡二叉树
给定一个二叉树,判断它是否是高度平衡的二叉树。
本题中,一棵高度平衡二叉树定义为:
一个二叉树每个节点 的左右两个子树的高度差的绝对值不超过 1 。
自顶向下递归
递归求高度,然后判断根节点和左右子节点是否都是平衡二叉树
时间复杂度为O(nlogn)
1 | # Definition for a binary tree node. |
计算高度的时候 顺便判断是否是平衡二叉树
-1表示非平衡二叉树,否则为高度
时间复杂度为O(n)
1 | # Definition for a binary tree node. |
链表排序
给你链表的头结点 head ,请将其按 升序 排列并返回 排序后的链表 。
插入排序法
和数组的方式类似,时间复杂度为O(n^2)
对应147. 对链表进行插入排序
1 | # Definition for singly-linked list. |
归并排序
自顶向下递归
时间复杂度O(nlogn)
空间复杂度O(logn)
对链表自顶向下归并排序的过程如下。
找到链表的中点,以中点为分界,将链表拆分成两个子链表。寻找链表的中点可以使用快慢指针的做法,快指针每次移动 2 步,慢指针每次移动 1 步,当快指针到达链表末尾时,慢指针指向的链表节点即为链表的中点。
对两个子链表分别排序。
将两个排序后的子链表合并,得到完整的排序后的链表。可以使用「21. 合并两个有序链表」的做法,将两个有序的子链表进行合并。
上述过程可以通过递归实现。递归的终止条件是链表的节点个数小于或等于 11,即当链表为空或者链表只包含 11 个节点时,不需要对链表进行拆分和排序。
1 | # Definition for singly-linked list. |
自底向上归并
迭代法,写起来细节有点繁琐,留TODO
验证回文串
给定一个字符串,验证它是否是回文串,只考虑字母和数字字符,可以忽略字母的大小写。
说明:本题中,我们将空字符串定义为有效的回文串。
示例 1:
输入: “A man, a plan, a canal: Panama”
输出: true
解释:”amanaplanacanalpanama” 是回文串
示例 2:
输入: “race a car”
输出: false
解释:”raceacar” 不是回文串
一种是先过滤掉非数字和字符串的字符,然后判断
一种是直接判断
1 | class Solution: |
二叉树的最大深度
给定一个二叉树,找出其最大深度。
二叉树的深度为根节点到最远叶子节点的最长路径上的节点数。
说明: 叶子节点是指没有子节点的节点。
示例:
给定二叉树 [3,9,20,null,null,15,7],
3
/
9 20
/
15 7
返回它的最大深度 3 。
层序遍历
也就是广度优先
1 | # Definition for a binary tree node. |
深度优先遍历
1 | # Definition for a binary tree node. |
岛屿数量
给你一个由 ‘1’(陆地)和 ‘0’(水)组成的的二维网格,请你计算网格中岛屿的数量。
岛屿总是被水包围,并且每座岛屿只能由水平方向和/或竖直方向上相邻的陆地连接形成。
此外,你可以假设该网格的四条边均被水包围。
示例 1:
输入:grid = [
[“1”,”1”,”1”,”1”,”0”],
[“1”,”1”,”0”,”1”,”0”],
[“1”,”1”,”0”,”0”,”0”],
[“0”,”0”,”0”,”0”,”0”]
]
输出:1
示例 2:
输入:grid = [
[“1”,”1”,”0”,”0”,”0”],
[“1”,”1”,”0”,”0”,”0”],
[“0”,”0”,”1”,”0”,”0”],
[“0”,”0”,”0”,”1”,”1”]
]
输出:3
深度优先遍历
遍历网格中的每个元素,如果为”1”,则答案ans计数加1,
同时启动深度优先遍历,将上下左右四个方向的连接元素全部标记为非”1”
遍历下一个元素
1 | class Solution: |
广度优先搜索
这个就是最直观的思路,
用一个队列存储已访问的节点,然后出队列的时候,将其上下左右方向”连通”(即值为1)的元素放入队列
1 | class Solution: |
并查集
TODO
二叉树的右视图
给定一个二叉树的 根节点 root,想象自己站在它的右侧,按照从顶部到底部的顺序,返回从右侧所能看到的节点值。
层序遍历的思路
1 | # Definition for a binary tree node. |
还可以用深度优先遍历的思路
接雨水
给定 n 个非负整数表示每个宽度为 1 的柱子的高度图,计算按此排列的柱子,下雨之后能接多少雨水。
输入:height = [0,1,0,2,1,0,1,3,2,1,2,1]
输出:6
解释:上面是由数组 [0,1,0,2,1,0,1,3,2,1,2,1] 表示的高度图,在这种情况下,可以接 6 个单位的雨水(蓝色部分表示雨水)。
动态规划
从左向右记录当前值及其左边所有数的最大值,left_max
从右向左记录right_max
1 | class Solution: |
双指针
left_max和right_max只记录当前值,一次遍历即可
时间复杂度还是O(n)
空间复杂度将为O(1)
1 | class Solution: |
单调栈
TODO
字符串排列(系列)
全排列
输入一个字符串,打印出该字符串中字符的所有排列。
你可以以任意顺序返回这个字符串数组,但里面不能有重复元素。
示例:
输入:s = “abc”
输出:[“abc”,”acb”,”bac”,”bca”,”cab”,”cba”]
回溯
其实就是穷举法
从左往右依次填入字符,为了避免在同一位置填入相同元素需要设置一个标记数组来记录元素访问情况
1 | class Solution: |
47. 全排列 II
给定一个可包含重复数字的序列 nums ,按任意顺序 返回所有不重复的全排列。
示例 1:
输入:nums = [1,1,2]
输出:
[[1,1,2],
[1,2,1],
[2,1,1]]
示例 2:
输入:nums = [1,2,3]
输出:[[1,2,3],[1,3,2],[2,1,3],[2,3,1],[3,1,2],[3,2,1]]
1 | class Solution { |
合并K个升序链表
23. 合并K个升序链表
给你一个链表数组,每个链表都已经按升序排列。
请你将所有链表合并到一个升序链表中,返回合并后的链表。
示例 1:
输入:lists = [[1,4,5],[1,3,4],[2,6]]
输出:[1,1,2,3,4,4,5,6]
解释:链表数组如下:
[
1->4->5,
1->3->4,
2->6
]
将它们合并到一个有序链表中得到。
1->1->2->3->4->4->5->6
示例 2:
输入:lists = []
输出:[]
示例 3:
输入:lists = [[]]
输出:[]
没想到居然是一个困难题
循环使用 2个链表合并的思路处理
时间复杂度:由于除第一个链表外,其他每个链表都要被遍历多次,
等差数列:
第一次合并后,链表长度:2n
第二次合并后,链表长度:3n
第k-1次合并后,链表长度:kn
合计遍历(2+k)n*(k-1)/2=O(k^2*n)
空间复杂度O(1)
1 | # Definition for singly-linked list. |
分治+归并
k个数组,先两两合并,然后逐步归并。
划分深度为logk层,每层每个数都要遍历一次,每层k*n个数
时间复杂度O(logk * kn)
空间复杂度:栈空间logk,
若改为递归,则实际需要kn的额外空间
1 | # Definition for singly-linked list. |
同时比较k个链表中开头的值,并用最小堆优化
时间复杂度:n个节点,k为最小堆的大小,每个节点必进出最小堆一次,堆调整O(logk),整体O(nlogk)
空间复杂度:即为堆的大小,O(logk)
1 | # Definition for singly-linked list. |