leetcode 100
链表
反转链表
单链表的头节点 head
,请反转链表,返回反转后的链表。
1 | var reverseList = function (head) { |
链表固定区间反转链表
- 遍历到第
m-1
个节点:这个节点是反转开始节点的前一个节点。 - 反转第
m
到n
个节点:我们需要通过迭代反转这部分链表的节点。 - 重新连接链表:将反转后的子链表正确连接到链表的前半部分和后半部分。
1 | function reverseBetween(head, m, n) { |
- **创建虚拟节点
dummy
**:- 虚拟节点
dummy
是为了方便处理链表头节点的情况,避免单独处理头节点逻辑。 dummy.next = head
,因此虚拟节点的next
指向链表的头节点。
- 虚拟节点
- 找到第
m-1
个节点:- 使用
for
循环遍历链表,直到找到第m-1
个节点,并用prev
指向它。prev.next
就是第m
个节点,准备开始反转。
- 使用
- 反转第
m
到第n
个节点:- 使用
for
循环,依次反转这段区间的节点。核心逻辑是逐步将第m
到第n
个节点进行插入操作。 curr
始终指向正在处理的节点,nextTemp
保存下一个节点。通过调整指针来实现反转。
- 使用
- 重新连接:
- 在反转过程中,我们逐步将反转后的节点插入到链表中,维护正确的链表顺序。
- 返回结果:
- 最后返回
dummy.next
,即新链表的头节点。
- 最后返回
时间复杂度和空间复杂度:
- 时间复杂度:O(n),我们需要遍历一次链表来找到位置
m
,并在第m
到第n
个节点之间反转。 - 空间复杂度:O(1),因为我们只用了常数空间来进行操作。
判断链表有环
判断给定的链表中是否有环。如果有环则返回true,否则返回false。
1 | function hasCycle(head) { |
如果链表中存在环,
fast
和slow
最终会在环中某一点相遇。如果链表没有环,fast
会在到达链表末尾时变为null
。终止条件:
- 如果
fast
或fast.next
为null
,则链表中没有环,返回false
。 - 如果
slow
和fast
相遇,则表明链表中存在环,返回true
。
- 如果
时间和空间复杂度:
- 时间复杂度:O(n),因为快慢指针最多遍历链表一次。
- 空间复杂度:O(1),只使用了常量级别的额外空间。
链表相加
反转链表
- 反转链表:首先将两个链表反转,以便从最低位开始相加。
- 相加过程:保持你目前的逐位相加逻辑。
- 再次反转结果链表:将相加后的结果链表反转回来,以保持数字的正确顺序。
1 | // 反转链表函数 |
解释:
反转链表:我们首先使用
reverseList
函数反转两个输入链表,使得最低位的数字在链表头部,便于逐位相加。相加过程:保持原有的加法逻辑,逐位相加两个链表节点值,同时处理进位。如果一个链表较长,未匹配的位数会和 0 相加。
处理进位:每次相加时计算是否有进位,并将进位保留到下一轮相加。
反转结果链表:相加结束后,再次反转结果链表,使得返回的链表恢复为从高位到低位的顺序。
示例:
假设输入链表为:
head1: 1 -> 2 -> 3
(表示123
)head2: 4 -> 5 -> 6
(表示456
)
反转链表:
head1
反转为:3 -> 2 -> 1
head2
反转为:6 -> 5 -> 4
逐位相加:
3 + 6 = 9
2 + 5 = 7
1 + 4 = 5
结果链表为:
9 -> 7 -> 5
再次反转结果链表,得到最终结果:
5 -> 7 -> 9
,表示579
。
- 时间复杂度:O(n),其中 n 是链表中较长的那个链表的长度。反转和相加的操作都是线性时间。
- 空间复杂度:O(1),除了结果链表外,算法只使用了常数级别的额外空间。
栈
确实,反转链表虽然有效,但你希望寻找更简单的解法。可以使用栈的方式来解决这个问题。利用栈的“后进先出”特性,可以方便地从链表的尾部开始进行加法,而无需反转链表。
使用栈的解法:
我们可以将两个链表的所有节点值分别压入两个栈中。这样,栈顶就是链表的尾节点。然后,我们逐步弹出栈中的元素进行相加,同时处理进位,最后生成结果链表。
解法步骤:
- 使用两个栈
stack1
和stack2
,将两个链表的所有节点值分别压入栈中。 - 逐步从栈中弹出节点值进行相加,同时处理进位。
- 最后将结果链表按正确的顺序连接。
实现代码:
1 | // 定义链表节点类 |
解法思路:
- 利用栈:我们将两个链表的节点值依次压入两个栈中,这样可以从链表的尾部开始相加,而无需反转链表。
- 逐位相加:通过逐步弹出栈中的元素,进行相加操作,同时处理进位。
- 结果链表构建:每次生成新节点,将其插入到结果链表的前面,从而保持最终链表的顺序。
优点:
- 无需反转链表,代码更直观、简洁。
- 保证从尾部开始相加的正确顺序。
- 时间复杂度为 O(n),空间复杂度为 O(n),其中
n
是较长的链表的长度。
示例:
假设输入链表为:
head1: 1 -> 2 -> 3
(表示123
)head2: 4 -> 5 -> 6
(表示456
)
将链表节点值压入栈中:
stack1: [1, 2, 3]
stack2: [4, 5, 6]
逐位相加:
- 3 + 6 = 9
- 2 + 5 = 7
- 1 + 4 = 5
生成结果链表:
5 -> 7 -> 9
,表示579
。
总结:
这种方法避免了链表的反转,使用栈的方式使得加法过程变得简单明了。如果你希望简化实现,这个解法更加直接并且易于理解。
合并两个有序链表
将两个升序链表合并为一个新的 升序 链表并返回。新链表是通过拼接给定的两个链表的所有节点组成的。
1 | // 合并两个升序链表 |
合并 k 个链表
合并 K
个升序链表的问题可以通过不同的策略来解决。这里有几种常见的方法:
方法 1: 两两合并
- 逐对合并:每次合并两个链表,直到只剩一个链表。
- 时间复杂度:O(K * N * logK),其中
N
是每个链表的平均长度,K
是链表的数量。最坏情况下,合并每对链表需要 O(N) 时间,总共有 K-1 次合并操作。
1 | function mergeTwoLists(l1, l2) { |
递归合并链表
代码解释
mergeTwoLists
函数:- 合并两个已排序的链表。
- 使用递归的方式比较两个链表的头节点,并将较小的节点连接到合并结果上。
- 递归处理两个链表的其余部分。
mergeKLists
函数:- 使用分治法(Divide and Conquer)将链表数组分为两半,递归合并每一半的链表。
- 调用
mergeTwoLists
来合并两个部分,直到所有链表被合并为一个。
优点
- 这种方法相对简洁,没有使用额外的优先队列数据结构。
- 递归和分治法使代码简洁易懂。
时间复杂度
- 时间复杂度为 O(NlogK)O(N \log K)O(NlogK),其中 NNN 是所有链表节点的总数,KKK 是链表的数量。
1 | /** |
方法 2: 使用最小堆(优先队列)
- 最小堆:将每个链表的头节点插入最小堆,然后每次从堆中取出最小节点,并将该节点的下一个节点插入堆中。
- 时间复杂度:O(N * logK),其中
N
是所有链表节点的总数,K
是链表的数量。
1 | class MinHeap { |
方法 3: 分治法
- 递归分治:将链表数组分为两半,递归合并每半部分,最后合并这两半。
- 时间复杂度:O(N * logK),其中
N
是所有链表节点的总数,K
是链表的数量。与最小堆相似,分治法也具有 O(N * logK) 的复杂度,但实现上可能稍复杂。
1 | var mergeKLists = function(lists) { |
选择哪种方法取决于具体的应用场景和性能需求。两两合并实现简单,但效率可能较低;最小堆适用于需要高效合并的场景;分治法则在处理较大的链表集合时表现良好。
对于合并 K
个升序链表,最推荐的方法是使用最小堆(优先队列)。原因如下:
优势:
- 时间复杂度较低:最小堆的时间复杂度是 O(N * logK),其中
N
是所有链表节点的总数,K
是链表的数量。相比于两两合并的方法,最小堆在处理大规模数据时表现更优。 - 代码结构简洁:最小堆方法的代码通常较为简洁,易于理解和实现。尤其是处理链表节点时,通过最小堆自动保证了节点的升序。
- 适用于大规模数据:最小堆在处理大量链表时能够更有效地管理内存和计算复杂度,相较于递归方法和两两合并方法更具优势。
相交链表–两个链表相交的节点
两个单链表的头节点 headA
和 headB
,请你找出并返回两个单链表相交的起始节点。如果两个链表不存在相交节点,返回 null
。
解题思想:双指针
初始化两个指针 p1
和 p2
,分别指向链表 A 和链表 B 的头节点。
遍历链表,当指针 p1
到达链表 A 的末端时,将其指向链表 B 的头节点;当指针 p2
到达链表 B 的末端时,将其指向链表 A 的头节点。
当两个指针相遇时,返回相遇的节点;如果两个指针都为 null
,则返回 null
。
1 | var getIntersectionNode = function(headA, headB) { |
k个一组翻转链表
链表的头节点 head
,每 k
个节点一组进行翻转,返回修改后的链表。k
是一个正整数,它的值小于或等于链表的长度。如果节点总数不是 k
的整数倍,那么请将最后剩余的节点保持原有顺序。不能只是单纯的改变节点内部的值,而是需要实际进行节点交换。
- 分组反转:
- 通过遍历链表,将链表分成若干长度为
k
的小段。 - 对每一小段进行反转操作。
- 反转后的小段重新链接到整体链表上。
- 通过遍历链表,将链表分成若干长度为
- 辅助哑节点:
- 引入一个哑节点(dummy node),它的
next
指向链表的头节点。这使得在处理头节点的反转时可以避免特殊处理,简化了代码的逻辑。
- 引入一个哑节点(dummy node),它的
- 双指针技巧:
- 使用两个指针
pre
和end
来标记需要反转的小段的起始和结束位置。 pre
用于标记当前小段的前一个节点。end
用于遍历到当前小段的结束节点。
- 使用两个指针
- 反转操作:
- 通过辅助函数
reverse
实现对从节点a
到节点b
之间的部分链表的反转。 - 反转后,将这部分链表重新连接到原链表上。
- 通过辅助函数
- 链表遍历和反转:
- 遍历链表,每次找到
k
个节点,进行反转操作。 - 如果剩余节点不足
k
个,则保持其原有顺序。
- 遍历链表,每次找到
下面是这个思路的实现:
1 | var reverseKGroup = function(head, k) { |
这个算法的时间复杂度是 O(n),其中 n 是链表的长度。因为需要遍历每个节点一次。
- 分组:
- 使用
for
循环将end
指针向前移动k
次,找到每个需要反转的小段。如果end
到达链表末尾且不足k
个节点,则跳出循环,不再进行反转。
- 使用
- 反转:
- 使用辅助函数
reverse
反转找到的小段链表。 - 断开当前小段与链表的连接,反转后重新连接到主链表上。
- 使用辅助函数
- 调整指针:
- 将
pre
和end
指针调整到新的位置,准备处理下一个小段。
- 将
这种方法通过局部反转来实现整体链表的反转,确保了每个小段的反转操作独立且高效,并且代码简洁易读。
链表中倒数最后k个结点
输入一个长度为 n 的链表,返回该链表中倒数第k个节点。如果该链表长度小于k,请返回一个长度为 0 的链表。
- 使用两个指针
fast
和slow
,两者都从链表的头节点开始。 - 先让
fast
指针向前移动k
步。 - 然后同时移动
fast
和slow
,直到fast
到达链表的末尾。 - 当
fast
到达末尾时,slow
指针所指向的节点就是倒数第K个节点。
1 | function FindKthToTail(pHead, k) { |
- 首先检查链表头节点是否为空,如果是的话,直接返回
null
。 - 然后我们让
fast
指针向前移动k
步。如果在移动过程中fast
变成了null
,说明k
大于链表长度,直接返回null
。 - 接下来同时移动
fast
和slow
,直到fast
到达链表的末尾。此时,slow
就指向了倒数第K个节点。 - 最后返回
slow
指针指向的节点。
这个算法的时间复杂度是 O(n),空间复杂度是 O(1),其中 n
是链表的长度。
删除链表的倒数第N个节点
给你一个链表,删除链表的倒数第 n
个结点,并且返回链表的头结点。
1 | var removeNthFromEnd = function (head, n) { |
双指针法:
- 时间复杂度:
O(L)
,其中L
是链表的长度。 - 空间复杂度:
O(1)
。 - 只需遍历一次链表。
两两交换链表的节点
给你一个链表,两两交换其中相邻的节点,并返回交换后链表的头节点。你必须在不修改节点内部的值的情况下完成本题(即,只能进行节点交换)。
解法1:迭代
使用迭代实现,通过迭代地遍历链表,并在每次迭代中交换当前节点和下一个节点的位置来达到相邻节点交换的目的。具体步骤如下:
- 首先,检查链表是否为空或者只有一个节点,如果是,则直接返回原链表。
- 创建一个哨兵节点
dummy
,将它的next
指向头节点head
。这样做是为了简化处理头节点的情况。 - 使用一个指针
current
指向哨兵节点,初始化时也指向头节点。 - 在循环中,每次处理两个相邻节点:
- 将
first
指向当前节点的下一个节点。 - 将
second
指向当前节点的下两个节点(即first
的下一个节点)。 - 交换
first
和second
节点的位置。 - 更新指针
current
,使其指向交换后的第一个节点,即first
。
- 将
- 当链表中剩余的节点不足两个时,停止循环。
- 返回哨兵节点的
next
,即新的头节点。
这个方法的关键点在于使用迭代遍历链表,并在每次迭代中交换相邻的两个节点的位置。
1 | var swapPairs = function (head) { |
解法二–递归
一种更简单的递归解法可以用于交换链表中的每两个相邻节点。递归方法直接对每对节点进行处理,而不需要显式地使用哨兵节点。下面是递归实现的方法:
1 | var swapPairs = function(head) { |
随机链表的复制
给你一个长度为 n
的链表,每个节点包含一个额外增加的随机指针 random
,该指针可以指向链表中的任何节点或空节点。
构造这个链表的 深拷贝。 深拷贝应该正好由 n
个 全新 节点组成,其中每个新节点的值都设为其对应的原节点的值。新节点的 next
指针和 random
指针也都应指向复制链表中的新节点,并使原链表和复制链表中的这些指针能够表示相同的链表状态。复制链表中的指针都不应指向原链表中的节点 。
例如,如果原链表中有 X
和 Y
两个节点,其中 X.random --> Y
。那么在复制链表中对应的两个节点 x
和 y
,同样有 x.random --> y
。
返回复制链表的头节点。
用一个由 n
个节点组成的链表来表示输入/输出中的链表。每个节点用一个 [val, random_index]
表示:
val
:一个表示Node.val
的整数。random_index
:随机指针指向的节点索引(范围从0
到n-1
);如果不指向任何节点,则为null
。
你的代码 只 接受原链表的头节点 head
作为传入参数。
这道题的解题思想是使用两次遍历原链表来创建新链表。在第一次遍历中,我们创建了新节点,并使用 Map 数据结构将原节点和新节点进行了映射。在第二次遍历中,我们设置了新节点的 next
和 random
指针,根据原节点的指针找到对应的新节点,并将其指针设置到新节点上。最后,我们返回新链表的头节点。
1 | var copyRandomList = function (head) { |
时间复杂度:O(N),因为我们需要遍历原链表两次,并且在每次遍历中,对每个节点进行常数时间的操作。
LRU缓存
请你设计并实现一个满足 LRU (最近最少使用) 缓存 约束的数据结构。
实现 LRUCache
类:
LRUCache(int capacity)
以 正整数 作为容量capacity
初始化 LRU 缓存int get(int key)
如果关键字key
存在于缓存中,则返回关键字的值,否则返回-1
。void put(int key, int value)
如果关键字key
已经存在,则变更其数据值value
;如果不存在,则向缓存中插入该组key-value
。如果插入操作导致关键字数量超过capacity
,则应该 逐出 最久未使用的关键字。
函数 get
和 put
必须以 O(1)
的平均时间复杂度运行。
这个题目是实现一个LRU(Least Recently Used)缓存。LRU缓存是一种缓存策略,最近使用的数据会被保留,而最久未使用的数据会被淘汰。我们需要实现两个操作:
get(key)
和put(key, value)
。
get(key)
:如果缓存中存在这个键,则返回对应的值,否则返回-1。put(key, value)
:如果缓存中存在这个键,更新其值;如果不存在,插入这个键值对。如果缓存达到容量限制,移除最久未使用的键值对。
为了实现这个功能,可以使用JavaScript的Map
对象。Map
对象按插入顺序保存键值对,因此可以用于实现LRU缓存。
以下是具体的实现步骤和代码:
创建LRUCache类:
- 初始化时,创建一个
Map
对象来存储缓存数据。 - 保存缓存的容量限制。
- 初始化时,创建一个
实现
get
方法:- 如果键存在,将其移到
Map
的末尾以表示最近使用。 - 返回对应的值,如果键不存在返回-1。
- 如果键存在,将其移到
实现
put
方法:- 如果键存在,先删除旧的键值对。
- 将新的键值对插入
Map
的末尾。 - 如果缓存超过容量限制,移除
Map
的第一个键值对(最久未使用的)。
code:
1 | /** |
逐行解释代码
var LRUCache = function(capacity) { ... };
- 构造函数,用于初始化LRU缓存。
this.capacity = capacity;
保存缓存容量。this.cache = new Map();
创建一个Map
对象来存储缓存数据。
LRUCache.prototype.get = function(key) { ... };
if (!this.cache.has(key)) { return -1; }
:如果Map
中没有这个键,返回-1。const value = this.cache.get(key);
:获取键对应的值。this.cache.delete(key);
:删除旧的键值对。this.cache.set(key, value);
:重新插入这个键值对,以表示最近使用。return value;
:返回值。
LRUCache.prototype.put = function(key, value) { ... };
if (this.cache.has(key)) { this.cache.delete(key); }
:如果键存在,删除旧的键值对。else if (this.cache.size >= this.capacity) { ... }
:如果缓存已满,删除最久未使用的键值对。const oldestKey = this.cache.keys().next().value;
:获取Map
中第一个键(最久未使用的键)。this.cache.delete(oldestKey);
:删除最久未使用的键值对。this.cache.set(key, value);
:插入新的键值对。
时间复杂度分析
get
操作:由于Map
对象的delete
和set
操作的时间复杂度都是O(1),所以get
操作的时间复杂度为O(1)。put
操作:同样由于Map
对象的delete
和set
操作的时间复杂度都是O(1),所以put
操作的时间复杂度为O(1)。
因此,LRU缓存的整体时间复杂度是O(1)。
双指针
移动0
给定一个数组 nums
,编写一个函数将所有 0
移动到数组的末尾,同时保持非零元素的相对顺序。必须在不复制数组的情况下原地对数组进行操作。
这个问题的目标是将数组中的所有零元素移动到数组的末尾,同时保持非零元素的相对顺序不变。下面是完整的解决方案:
- 使用两个指针:
slow
和fast
。slow
指针用来记录下一个非零元素要放置的位置,而fast
指针用于遍历数组。 - 当
fast
指针找到非零元素时,将该元素与slow
指针位置的元素交换,并将slow
指针向前移动。 - 当所有非零元素移动完毕后,剩下的元素全部填充为 0。
1 | var moveZeroes = function(nums) { |
- 第一个
for
循环遍历数组中的每个元素,当遇到非零元素时,将该元素移动到slow
指针所指的位置,并将slow
指针前移。 - 当所有非零元素都处理完毕后,第二个
for
循环将数组剩下的部分填充为零。
这个方案的时间复杂度是 O(n),并且是原地修改数组的。
盛最多水的容器
给定一个长度为 n
的整数数组 height
。有 n
条垂线,第 i
条线的两个端点是 (i, 0)
和 (i, height[i])
。找出其中的两条线,使得它们与 x
轴共同构成的容器可以容纳最多的水。返回容器可以储存的最大水量。
说明:你不能倾斜容器。
你正在编写一个解决「盛最多水的容器」问题的函数。这个问题要求找到两个垂直线,使它们与 x 轴共同构成的容器能容纳最多的水。你已经设置了变量 left
和 right
来表示容器的左右边界,并且还开始了 maxArea
的初始化工作。
- 使用两个指针,
left
和right
,分别指向数组的左右两端。 - 计算当前
left
和right
所能形成的容器面积,然后更新最大面积maxArea
。 - 移动指针:为了找到可能更大的容积,总是移动高度较小的那个指针。这样确保有可能获得更大的面积,因为移动较高的指针只会减少宽度,无法增大容积。
1 | var maxArea = function(height) { |
- **
left
和right
**:这两个指针分别指向数组的两端,逐步向中间靠拢。 - **
Math.min(height[left], height[right])
**:计算当前容器的高度,取决于较矮的那根柱子。 - **
right - left
**:计算当前容器的宽度。 - **
maxArea = Math.max(maxArea, currentArea)
**:不断更新最大容器的面积。 - 移动指针:每次比较
left
和right
指向的高度,移动较矮的那一个以期找到更大的容积。
- 时间复杂度:O(n),因为我们只遍历数组一次。
- 空间复杂度:O(1),只使用了常数空间。
三数之和
给你一个整数数组 nums
,判断是否存在三元组 [nums[i], nums[j], nums[k]]
满足 i != j
、i != k
且 j != k
,同时还满足 nums[i] + nums[j] + nums[k] == 0
。请你返回所有和为 0
且不重复的三元组。
注意:答案中不可以包含重复的三元组。
方法1–解题思路
排序:
- 首先将数组排序。这一步是为了方便使用双指针查找和跳过重复元素。
遍历数组:
- 使用一个循环遍历数组,每次选择一个元素作为三元组的第一个元素。
- 跳过重复的元素,以避免结果中出现重复的三元组。
双指针查找:
- 对于每个选定的第一个元素,使用两个指针分别指向该元素之后的两个位置。
- 移动两个指针以查找满足和为零的三元组。
- 如果和为零,将该三元组加入结果数组,并移动两个指针,同时跳过重复的元素。
- 如果和小于零,左指针右移以增加和。
- 如果和大于零,右指针左移以减小和。
代码实现
1 | var threeSum = function (nums) { |
关键点
- 排序:确保数组有序以方便跳过重复元素和使用双指针。
- 双指针查找:有效地缩小查找范围,避免重复结果。
- 跳过重复元素:避免结果中出现重复的三元组。
复杂度分析
时间复杂度:
- 排序的时间复杂度为 (O(nlog n))。
- 遍历数组和双指针查找的时间复杂度为 (O(n^2))。具体来说,对于每个元素,双指针需要遍历剩余的元素。
- 总的时间复杂度为 (O(nlog n) + O(n^2)),即 (O(n^2))。
空间复杂度:
- 由于排序算法需要一些额外的空间,空间复杂度为 (O(n))。
- 结果数组的空间复杂度取决于结果的数量,但不超过 (O(n^2))。
- 总的空间复杂度为 (O(n))(不包括结果数组所需的空间)。
方法2–解题思路
将三数之和的问题转换为两数之和的问题确实可以使解决方案更为直观和简单。具体步骤如下:
- 排序数组:和之前的方法一样,首先对数组进行排序。
- 遍历数组:将每个元素作为三元组中的第一个元素。
- 两数之和:对于每个固定的第一个元素,将问题转化为寻找两个数之和为目标值的问题。
- 使用哈希表查找:在寻找两数之和时,可以使用哈希表来记录已经遍历过的元素,从而高效地查找满足条件的两数。
实现步骤
- 排序:对数组进行排序。
- 遍历:遍历数组,固定一个元素作为三元组的第一个元素。
- 查找两数之和:使用哈希表查找剩余元素中是否存在满足条件的两个数。
代码实现
1 | var threeSum = function(nums) { |
复杂度分析
时间复杂度:
- 排序的时间复杂度为 (O(n \log n))。
- 遍历数组并查找两数之和的时间复杂度为 (O(n^2))。
- 总的时间复杂度为 (O(n \log n) + O(n^2)),即 (O(n^2))。
空间复杂度:
- 额外使用的哈希表空间复杂度为 (O(n))。
- 总的空间复杂度为 (O(n))。
关键点
- 排序:确保数组有序以方便跳过重复元素。
- 两数之和:将三数之和的问题转换为两数之和的问题。
- 哈希表:使用哈希表高效地查找满足条件的两个数。
总结
将三数之和的问题转化为两数之和的问题,通过使用哈希表,可以简化查找过程,并且有效地跳过重复元素,从而避免结果中出现重复的三元组。
删除链表的峰值
峰值节点的定义通常是指某个节点的值大于它前后的节点的值。在单链表中,由于只能单向遍历,不能直接访问前一个节点。因此,需要在遍历时记录前一个节点以便比较。
1 | function deletePeaks(head) { |
**虚拟头节点 (
dummy
)**:- 使用虚拟头节点来处理删除头节点(如果头节点是峰值)的特殊情况。
dummy.next
最终指向的是链表的新的头节点。
三指针遍历:
- 使用
prev
、cur
和next
三个指针来遍历链表:prev
:指向当前节点的前一个节点。cur
:指向当前节点。next
:指向当前节点的下一个节点。
- 通过比较
cur
和prev
、next
的值来判断cur
是否为峰值节点。
- 使用
删除峰值节点:
- 如果当前节点
cur
的值大于前一个节点prev
和下一个节点next
的值,则当前节点cur
被视为峰值节点,跳过它(即将prev.next = next
)。 - 如果当前节点不是峰值节点,则指针正常向前推进。
- 如果当前节点
返回新的链表头:
- 返回
dummy.next
,即链表的新的头节点。
- 返回
假设链表是 [1 -> 3 -> 2 -> 4 -> 1]
,删除峰值节点(值为 3 和 4)后的链表:
1 | let head = new ListNode(1); |
复杂度
- 时间复杂度:O(n),其中 n 是链表的节点数。我们只遍历链表一次。
- 空间复杂度:O(1),因为我们只使用了常数级别的额外空间。
这个方法通过三指针的方式,删除链表中的所有峰值节点。如果你对峰值的定义或具体场景有不同的需求,欢迎进一步说明,我可以帮助调整解决方案。
判断子序列
给定字符串 s 和 t ,判断 s 是否为 t 的子序列。字符串的一个子序列是原始字符串删除一些(也可以不删除)字符而不改变剩余字符相对位置形成的新字符串。(例如,"ace"
是"abcde"
的一个子序列,而"aec"
不是)。
这个问题要求判断字符串 s
是否为字符串 t
的子序列。子序列的定义是:从 t
中删除一些字符(或不删除),而剩下的字符顺序和 s
相同。你需要保持字符的相对顺序不变。
我们可以通过使用双指针来解决这个问题。双指针法的基本思想是同时遍历字符串 s
和 t
,检查 t
中的字符是否能依次匹配 s
的每一个字符。
- 初始化两个指针
i
和j
,分别指向字符串s
和t
的开头。 - 每次比较
s[i]
和t[j]
:- 如果它们相等,移动指针
i
和j
,即匹配到了一个字符。 - 如果它们不相等,移动
t
的指针j
,继续寻找下一个可能的匹配字符。
- 如果它们相等,移动指针
- 最后,如果
s
的所有字符都能在t
中按顺序找到(即i == s.length
),那么s
是t
的子序列。
1 | var isSubsequence = function(s, t) { |
对于
s = "abc"
和t = "ahbgdc"
:s[0] = 'a'
与t[0] = 'a'
匹配,i
和j
同时向前移动。s[1] = 'b'
与t[2] = 'b'
匹配,i
和j
同时向前移动。s[2] = 'c'
与t[4] = 'c'
匹配,i
和j
同时向前移动。- 最终
i
到达了s.length
,所以s
是t
的子序列。
对于
s = "axc"
和t = "ahbgdc"
:s[0] = 'a'
与t[0] = 'a'
匹配,i
和j
同时向前移动。s[1] = 'x'
无法匹配t
中的任何字符,遍历完t
后i != s.length
,所以s
不是t
的子序列。
时间复杂度:
- 时间复杂度:O(n),其中 n 是字符串
t
的长度。因为我们最多只会遍历字符串t
一次。 - 空间复杂度:O(1),只需要常数的额外空间来存储指针。
二分查找
搜索插入位置
给定一个排序数组和一个目标值,在数组中找到目标值,并返回其索引。如果目标值不存在于数组中,返回它将会被按顺序插入的位置。请必须使用时间复杂度为 O(log n)
的算法。
1 | var searchInsert = function (nums, target) { |
在二分查找的过程中,left
最终的位置实际上就是目标值应插入的位置。让我们详细解释一下为什么会这样:
解释为什么返回 left
初始化:
left
指针初始化为数组的开始,即0
。right
指针初始化为数组的末尾,即nums.length - 1
。
二分查找过程:
- 每次循环中,我们计算中间索引
mid
。 - 如果
nums[mid] == target
,直接返回mid
。 - 如果
nums[mid] < target
,说明目标值在mid
右边,所以我们将left
更新为mid + 1
。 - 如果
nums[mid] > target
,说明目标值在mid
左边,所以我们将right
更新为mid - 1
。
- 每次循环中,我们计算中间索引
终止条件:
- 循环在
left
超过right
时终止。 - 终止时,
left
指向的就是目标值应该插入的位置。这是因为:- 在
left
更新为mid + 1
时,意味着left
指针已经移动到所有小于目标值的元素之后。 - 在
right
更新为mid - 1
时,意味着right
指针已经移动到所有大于目标值的元素之前。 - 最终,
left
指向的就是目标值应该插入的位置,不会影响数组的排序。
- 在
- 循环在
假设数组为 [1, 3, 5, 6]
,目标值为 2
。
- 初始化:
left = 0
,right = 3
- 第一次循环:
mid = 1
(索引)nums[mid] = 3
- 因为
3 > 2
,所以更新right = mid - 1 = 0
- 第二次循环:
mid = 0
nums[mid] = 1
- 因为
1 < 2
,所以更新left = mid + 1 = 1
- 循环终止条件:
left = 1
,right = 0
- 退出循环,返回
left = 1
结果是目标值 2
应该插入到索引 1
位置,保证数组有序。
这个实现确保了在 left
超过 right
后,left
就是目标值应该插入的位置,保证数组依旧有序。
查找数组的峰值
给定一个长度为n的数组nums,找到峰值并返回其索引。数组可能包含多个峰值,在这种情况下,返回任何一个所在位置即可。
要在数组中找到一个峰值元素(比邻近元素大的元素)的位置,并返回它的索引。可以使用二分查找来实现这一点,时间复杂度为 O(log n)。
1 | function findPeakElement(nums) { |
- 边界检查:如果数组长度为 1,直接返回 0。
- 二分查找:
- 计算
mid
的位置,将数组分为两部分。 - 如果
nums[mid] > nums[mid + 1]
,说明峰值在左侧(包括mid
),因此将right
移动到mid
。 - 否则,峰值在右侧,将
left
移动到mid + 1
。
- 计算
- 结束条件:当
left == right
时,left
指向的元素就是峰值,返回它的索引。
搜索二维矩阵
给你一个满足下述两条属性的 m x n
整数矩阵:
- 每行中的整数从左到右按非严格递增顺序排列。
- 每行的第一个整数大于前一行的最后一个整数。
给你一个整数 target
,如果 target
在矩阵中,返回 true
;否则,返回 false
。
要在满足以下条件的 m x n
整数矩阵中搜索目标值 target
:
- 每行中的整数从左到右按非严格递增顺序排列。
- 每行的第一个整数大于前一行的最后一个整数。
可以使用二分查找算法,这样可以在 O(log(mn)) 的时间复杂度内完成搜索。因为矩阵的每一行和每一列都是有序的,可以将其视为一个扁平化的有序数组,然后在这个数组中进行二分查找。
解题思路
将二维矩阵视为一维数组:
- 假设矩阵有
m
行n
列,可以将其视为一个长度为m * n
的一维数组。 - 对于矩阵中的任何元素
matrix[i][j]
,可以映射到一维数组中的索引i * n + j
。
- 假设矩阵有
进行二分查找:
- 使用两个指针
left
和right
来表示一维数组的搜索范围,初始时left = 0
,right = m * n - 1
。 - 计算中间索引
mid
,然后将其映射回二维矩阵中的位置,即matrix[mid // n][mid % n]
。 - 比较
matrix[mid // n][mid % n]
和target
:- 如果相等,则返回
true
。 - 如果小于
target
,则移动左指针left = mid + 1
。 - 如果大于
target
,则移动右指针right = mid - 1
。
- 如果相等,则返回
- 使用两个指针
返回结果:
- 如果在搜索范围内没有找到
target
,返回false
。
- 如果在搜索范围内没有找到
代码实现
1 | var searchMatrix = function(matrix, target) { |
时间复杂度分析
- 时间复杂度:O(log(mn)),其中
m
是矩阵的行数,n
是矩阵的列数。因为使用的是二分查找,算法的时间复杂度是对元素总数的对数。 - 空间复杂度:O(1),因为我们只使用了常数级别的额外空间。
这个方法利用了矩阵的有序性质,通过二分查找高效地搜索目标值。
方法二
使用右上角值的特性
1 | var searchMatrix = function(matrix, target) { |
解释和逻辑调整
初始化:
row
初始化为0
,即从矩阵的第一行开始查找。col
初始化为n - 1
,即从矩阵的最后一列开始查找。
迭代查找:
- 在每一次迭代中,检查当前位置
matrix[row][col]
:- 如果
matrix[row][col] === target
,直接返回true
。 - 如果
matrix[row][col] > target
,说明目标值在当前列的左侧,所以将col
减小。 - 如果
matrix[row][col] < target
,说明目标值在当前行的下方,所以将row
增加。
- 如果
- 在每一次迭代中,检查当前位置
终止条件:
- 循环在
row >= m
或col < 0
时终止,表示查找超出了矩阵的边界,此时返回false
。
- 循环在
这种方法利用了矩阵的有序性质,在时间复杂度为 O(m + n) 的情况下完成了目标值的搜索。
1 | var searchMatrix = function(matrix, target) { |
在排序数组中查找元素的第一个和最后一个位置
给你一个按照非递减顺序排列的整数数组 nums
,和一个目标值 target
。请你找出给定目标值在数组中的开始位置和结束位置。如果数组中不存在目标值 target
,返回 [-1, -1]
。必须设计并实现时间复杂度为 O(log n)
的算法解决此问题。
解题思路
- 使用两次二分查找:
- 第一次查找左边界:找到第一个大于等于目标值的位置。
- 第二次查找右边界:找到最后一个等于目标值的位置。
- 实现细节:
- 初始化
left
和right
指针分别指向数组的起始和末尾。 - 在第一次二分查找中,如果
nums[mid] >= target
,则向左移动right
,否则向右移动left
。 - 在第二次二分查找中,如果
nums[mid] <= target
,则向右移动left
,否则向左移动right
。
- 初始化
- 返回结果:
- 如果找到目标值的左边界和右边界,返回它们的索引。
- 如果没有找到目标值,返回
[-1, -1]
表示未找到。
1 | var searchRange = function(nums, target) { |
这种方法的时间复杂度为 O(log n),其中 n
是数组 nums
的长度。这是因为每个二分查找都是对数组的对数级别的搜索,因此整体的时间复杂度是合理的。
数组中的逆序对
在数组中的两个数字,如果前面一个数字大于后面的数字,则这两个数字组成一个逆序对。输入一个数组,求出这个数组中的逆序对的总数P。并将P对1000000007取模的结果输出。 即输出P mod 1000000007
数据范围: 对于 50%50% 的数据, size≤104siz**e≤104,对于 100%100% 的数据, size≤105siz**e≤105,数组中所有数字的值满足 0≤val≤1090≤val≤109
要求:空间复杂度 O(n)O(n),时间复杂度 O(nlogn)O(nlogn)
使用改进的归并排序方法。逆序对的定义是当 nums[i] > nums[j]
且 i < j
时,称为一个逆序对。在归并排序的“合并”步骤中,我们可以高效地计算这些逆序对。
1 | function InversePairs(nums) { |
解释
归并排序与逆序对统计:
- 我们使用改进的归并排序,在“合并”两个有序子数组时统计逆序对。
- 当左半部分的一个元素大于右半部分的一个元素时,可以得出从左边当前元素到中间所有的元素都和右边这个元素形成逆序对。
逆序对统计逻辑:
- 如果
arr[i] > arr[j]
,则mid - i + 1
个元素都满足逆序条件,因为[i, mid]
区间内的所有元素都比arr[j]
大。
- 如果
取模运算:
- 最后返回结果时,对 (10^9 + 7) 取模,以避免结果过大。
这种方法的时间复杂度为 (O(n \log n)),适合大规模输入的情况。
搜索旋转排序数组
整数数组 nums
按升序排列,数组中的值 互不相同 。
在传递给函数之前,nums
在预先未知的某个下标 k
(0 <= k < nums.length
)上进行了 旋转,使数组变为 [nums[k], nums[k+1], ..., nums[n-1], nums[0], nums[1], ..., nums[k-1]]
(下标 从 0 开始 计数)。例如, [0,1,2,4,5,6,7]
在下标 3
处经旋转后可能变为 [4,5,6,7,0,1,2]
。
给你 旋转后 的数组 nums
和一个整数 target
,如果 nums
中存在这个目标值 target
,则返回它的下标,否则返回 -1
。
要求:时间复杂度为 O(log n)
这是一个经典的二分查找问题,要求在旋转排序数组中查找目标值,并且要求时间复杂度为 (O(\log n))。要实现这一点,可以利用二分查找的变种算法。在旋转数组中,每次二分查找都会有一个有序的半区间,利用这个有序区间判断目标值是否在其中,从而决定如何移动左右指针。
解决思路
初始化:
- 使用两个指针
left
和right
分别指向数组的起始和末尾。
- 使用两个指针
二分查找:
- 计算中间索引
mid
。 - 判断
nums[mid]
是否等于target
,如果是,返回mid
。 - 判断左半部分是否有序:
- 如果
nums[left] <= nums[mid]
,表示左半部分有序:- 如果
target
在nums[left]
和nums[mid]
之间,移动right
指针到mid - 1
。 - 否则,移动
left
指针到mid + 1
。
- 如果
- 如果
- 如果左半部分无序,则右半部分一定有序:
- 如果
target
在nums[mid]
和nums[right]
之间,移动left
指针到mid + 1
。 - 否则,移动
right
指针到mid - 1
。
- 如果
- 计算中间索引
返回结果:
- 如果找不到目标值,返回
-1
。
- 如果找不到目标值,返回
代码实现
1 | var search = function (nums, target) { |
解释
- 初始化:设定
left
为数组的起始位置,right
为数组的末尾位置。 - 二分查找循环:
- 计算中间索引
mid
。 - 如果
nums[mid]
等于目标值,直接返回mid
。 - 判断
nums[left]
是否小于等于nums[mid]
来确定左半部分是否有序。 - 如果左半部分有序,判断目标值是否在左半部分范围内,如果在,则移动
right
指针;否则,移动left
指针。 - 如果左半部分无序,则右半部分一定有序,判断目标值是否在右半部分范围内,如果在,则移动
left
指针;否则,移动right
指针。
- 计算中间索引
- 返回结果:如果找不到目标值,返回
-1
。
这种方法能够在 (O(log n)) 时间复杂度内完成搜索,满足题目的要求。
寻找旋转数组的最小值
已知一个长度为 n
的数组,预先按照升序排列,经由 1
到 n
次 旋转 后,得到输入数组。例如,原数组 nums = [0,1,2,4,5,6,7]
在变化后可能得到:
- 若旋转
4
次,则可以得到[4,5,6,7,0,1,2]
- 若旋转
7
次,则可以得到[0,1,2,4,5,6,7]
注意,数组 [a[0], a[1], a[2], ..., a[n-1]]
旋转一次 的结果为数组 [a[n-1], a[0], a[1], a[2], ..., a[n-2]]
。
给你一个元素值 互不相同 的数组 nums
,它原来是一个升序排列的数组,并按上述情形进行了多次旋转。请你找出并返回数组中的 最小元素 。
要求:时间复杂度为 O(log n)
方法1:sort排序
1 | var findMin = function (nums) { |
方法2:二分查找
当 nums[mid] == nums[right]
时,不能确定最小值在哪一半,所以我们可以通过将右边界缩小一位来跳过重复的元素。
初始化指针:
- 使用两个指针
left
和right
分别指向数组的起始和末尾。
- 使用两个指针
二分查找:
- 计算中间索引
mid
。 - 如果中间元素
nums[mid]
大于右端元素nums[right]
,说明最小值在右半部分,因此移动left
指针到mid + 1
。 - 否则,说明最小值在左半部分或者就是
mid
,因此移动right
指针到mid
。
- 计算中间索引
返回结果:
- 循环结束时,
left
和right
会指向最小值所在的位置,返回nums[left]
或nums[right]
。
- 循环结束时,
1 | function minNumberInRotateArray(nums) { |
处理重复元素:当 nums[mid] == nums[right]
时,无法判断最小值的位置,因此我们将 right
减 1 来继续查找。
例如数组
[1, 0, 1, 1, 1]
,中间的1
与右端1
相等时,右边可能包含最小值,也可能不包含,但为了保证正确性,我们只需将right
减小一位。时间复杂度:(O(log n))
- 每次循环将搜索区间缩小一半,因此时间复杂度为 (O(log n))。
空间复杂度:(O(1))
- 只使用了常量空间来存储指针和中间变量,没有使用额外的数组或数据结构。
这种方法通过不断缩小搜索范围,确保在 (O(\log n)) 时间复杂度内找到最小元素。
寻找两个正序数组的中位数
给定两个大小分别为 m
和 n
的正序(从小到大)数组 nums1
和 nums2
。请你找出并返回这两个正序数组的 中位数 。
算法的时间复杂度应该为 O(log (m+n))
。
1 | var findMedianSortedArrays = function(nums1, nums2) { |
好的,让我们修改您的代码,以实现 ( O(\log(m+n)) ) 的时间复杂度,使用二分查找的方法直接在数组 nums1
和 nums2
中寻找中位数的位置。
1 | var findMedianSortedArrays = function(nums1, nums2) { |
解释:
初始化和二分查找设置:
- 首先确保
nums1
是较小的数组(或大小相等)。这样可以简化二分查找的处理。 - 计算合并后数组的总长度
totalLength
和中位数位置的halfLength
。
- 首先确保
二分查找:
- 在较小数组
nums1
上使用二分查找,找到一个索引i
,满足以下条件:- 在
nums1
的i
左侧和nums2
的j
左侧的元素均小于或等于右侧的元素。
- 在
- 根据当前的划分情况调整
i
的值,使得划分更接近理想情况。
- 在较小数组
划分条件:
- 根据当前的
i
和j
计算nums1
和nums2
的左右两侧元素,并检查是否满足划分条件。 - 如果条件满足,则根据总长度是偶数还是奇数来计算中位数。
- 根据当前的
边界处理:
- 确保在处理
nums1
和nums2
边界情况时的正确性,例如i
或j
达到数组边界时的处理。
- 确保在处理
这种方法保证了在 ( O(\log(\min(m, n))) ) 的时间复杂度内找到中位数,符合题目要求。
栈
最小栈
设计一个支持 push
,pop
,top
操作,并能在常数时间内检索到最小元素的栈。实现 MinStack
类:
MinStack()
初始化堆栈对象。void push(int val)
将元素val推入堆栈。void pop()
删除堆栈顶部的元素。int top()
获取堆栈顶部的元素。int getMin()
获取堆栈中的最小元素。
你的实现使用了两个栈:x_stack
用于存储所有元素,min_stack
用于存储当前的最小元素,这样可以在常数时间内获取最小值。你的实现是正确的并且高效,以下是对代码的详细解释和分析:
代码实现和解释
1 | var MinStack = function() { |
**构造函数 (
MinStack
)**:- 初始化两个栈:
x_stack
存储所有元素,min_stack
存储当前的最小值。 min_stack
初始化为[Infinity]
,这样确保在第一次push
操作时可以正确比较并更新最小值。
- 初始化两个栈:
push
方法:- 将元素
x
推入x_stack
。 - 将
x
与min_stack
当前的栈顶元素进行比较,取较小值推入min_stack
,这样min_stack
的栈顶始终保持最小值。
- 将元素
pop
方法:- 同时弹出
x_stack
和min_stack
的栈顶元素,确保min_stack
的栈顶始终与x_stack
保持同步。
- 同时弹出
top
方法:- 返回
x_stack
的栈顶元素。
- 返回
getMin
方法:- 返回
min_stack
的栈顶元素,即当前的最小值。
- 返回
时间复杂度:
push
:O(1)pop
:O(1)top
:O(1)getMin
:O(1)
空间复杂度:
- 每次
push
操作都会向min_stack
添加一个元素,因此空间复杂度为 O(n),其中 n 是堆栈中的元素数量。
- 每次
这个实现确保了所有操作的时间复杂度为常数时间,同时通过辅助栈 min_stack
维持当前的最小值,使得 getMin
操作能够快速返回最小值。
字符串解码
给定一个经过编码的字符串,返回它解码后的字符串。编码规则为: k[encoded_string]
,表示其中方括号内部的 encoded_string
正好重复 k
次。注意 k
保证为正整数。你可以认为输入字符串总是有效的;输入字符串中没有额外的空格,且输入的方括号总是符合格式要求的。此外,你可以认为原始数据不包含数字,所有的数字只表示重复的次数 k
,例如不会出现像 3a
或 2[4]
的输入。
使用栈来辅助解码:遍历输入字符串,使用两个栈来分别存储数字(重复次数)和字符串。
遍历解码过程:
- 当遇到数字时,解析完整的数字并入栈。
- 当遇到
[
时,将当前解码的字符串入栈,并重置当前字符串。 - 当遇到
]
时,开始出栈,直到遇到[
,这时将重复次数和当前字符串出栈,根据重复次数构造新的字符串并入栈。
构造最终解码后的字符串:最终栈中只会有一个字符串,即解码后的结果。
1 | var decodeString = function(s) { |
解释和示例
对于字符串
3[a]2[bc]
:- 遇到数字
3
,入栈; - 遇到
[
,当前数字和当前字符串入栈,重置当前数字和字符串; - 遇到
]
,出栈,根据出栈的数字重复当前字符串,结果为"aaabcbc"
。
- 遇到数字
对于字符串
3[a2[c]]
:- 遇到数字
3
,入栈; - 遇到
[
,当前数字和当前字符串入栈,重置当前数字和字符串; - 遇到
]
,出栈,根据出栈的数字重复当前字符串,结果为"accaccacc"
。
- 遇到数字
这种方法通过栈的结构,有效地处理了嵌套的解码规则,保证了字符串的正确解码。
每日温度
给定一个整数数组 temperatures
,表示每天的温度,返回一个数组 answer
,其中 answer[i]
是指对于第 i
天,下一个更高温度出现在几天后。如果气温在这之后都不会升高,请在该位置用 0
来代替。
这个问题可以使用单调栈(Monotonic Stack)来解决,以便有效地找到每一天后面第一个更高温度出现的天数。下面是具体的实现方法:
- 使用单调栈:维护一个单调递减的栈,栈中存储的是温度数组的索引。
- 遍历温度数组:从左到右遍历每一天的温度。
- 如果当前温度大于栈顶索引处的温度,说明找到了栈顶索引对应的下一个更高温度的位置,计算天数差值并更新结果数组。
- 如果当前温度小于等于栈顶索引处的温度,将当前索引入栈,继续下一天的遍历。
这种方法的时间复杂度是 O(n),因为每个元素最多进栈和出栈各一次。
下面是具体的 JavaScript 实现:
1 | var dailyTemperatures = function(temperatures) { |
解释
- 初始化:创建一个与温度数组相同长度的结果数组
result
,并创建一个空的栈stack
。 - 遍历温度数组:对于每一天的温度,如果当前温度大于栈顶索引处的温度,说明找到了下一个更高温度的位置,计算天数差值并更新
result
数组;否则将当前索引入栈。 - 返回结果:最终得到的
result
数组即为每一天后面第一个更高温度出现的天数,如果没有更高温度则为 0。
这种方法利用了单调栈的特性,能够在 O(n) 的时间复杂度内解决问题,是一种高效的解决方案。
有效的括号
给定一个只包括 '('
,')'
,'{'
,'}'
,'['
,']'
的字符串 s
,判断字符串是否有效。有效字符串需满足:
- 左括号必须用相同类型的右括号闭合。
- 左括号必须以正确的顺序闭合。
- 每个右括号都有一个对应的相同类型的左括号。
解题思想
要判断一个字符串中的括号是否有效,我们可以使用栈(stack)数据结构来帮助我们进行匹配。具体思路如下:
- 遍历字符串中的每个字符。
- 如果遇到左括号(’(‘,’{‘,’[‘),将其压入栈中。
- 如果遇到右括号(’)’,’}’,’]’),检查栈顶元素是否是对应的左括号。如果是,将栈顶元素弹出;否则,字符串无效。
- 遍历结束后,如果栈为空,则字符串有效;否则,无效。
以下是完整的代码和逐行解释:
1 | var isValid = function (s) { |
逐行解释
- 函数声明和初始化
1 | var isValid = function(s) { |
const stack = [];
:创建一个空栈用于存储左括号。const matchingBracket = { ... };
:定义括号的对应关系。
- 遍历字符串
1 | for (const char of s) { |
for (const char of s) { ... }
:遍历字符串中的每个字符。if (char === '(' || char === '{' || char === '[') { stack.push(char); }
:如果是左括号,将其压入栈中。else if (char === ')' || char === '}' || char === ']') { ... }
:如果是右括号,检查栈顶元素是否是对应的左括号。if (stack.length === 0 || stack[stack.length - 1] !== matchingBracket[char]) { return false; }
:如果不匹配,返回false
。stack.pop();
:弹出栈顶元素。
- 检查栈是否为空
1 | return stack.length === 0; |
return stack.length === 0;
:如果栈为空,返回true
,否则返回false
。
时间复杂度分析
- 时间复杂度:O(n),其中 n 是字符串的长度。我们只遍历字符串一次,每个字符的操作(压栈和弹栈)都是 O(1) 的时间复杂度。
- 空间复杂度:O(n),在最坏情况下(所有字符都是左括号时),栈的大小可以达到字符串长度。
柱状图中最大的矩形
给定 n 个非负整数,用来表示柱状图中各个柱子的高度。每个柱子彼此相邻,且宽度为 1 。求在该柱状图中,能够勾勒出来的矩形的最大面积。
这个问题可以用单调栈来解决。通过一次遍历就可以找到每一个柱子作为矩形高度时的最大矩形面积,最终求出最大值。以下是具体实现的 Python 代码:
1 | function largestRectangleArea(heights) { |
解释
初始化和扩展高度数组:
- 为了方便处理边界情况,我们在高度数组的两端各添加一个高度为0的柱子。这保证了我们在处理到数组的边界时,能够正确地计算所有可能的矩形面积。
使用栈来存储柱子的索引:
- 栈中存储的是柱子的索引,而不是高度。
- 当遍历到的当前柱子的高度小于栈顶柱子的高度时,表示可以计算以栈顶柱子高度为基础的最大矩形面积。
计算矩形面积:
- 当当前柱子的高度小于栈顶柱子的高度时,不断从栈中弹出柱子的索引,并计算以弹出柱子高度为矩形高度的最大面积。
- 宽度的计算方法是当前柱子的索引减去新栈顶柱子索引再减1。
更新最大面积:
- 每次计算出的矩形面积都会与当前最大面积比较,并更新最大面积。
这样通过一次遍历,就能找到每一个柱子作为矩形高度时的最大矩形面积,最终求出整个柱状图中的最大矩形面积。
通过输入 heights = [2, 1, 5, 6, 2, 3]
来详细解释代码的执行过程。
执行过程:
初始化:
heights = [0, 2, 1, 5, 6, 2, 3, 0]
stack = []
maxArea = 0
遍历高度数组:
第1步(i = 0):
- 当前高度
heights[0] = 0
- 栈为空,直接入栈:
stack = [0]
第2步(i = 1):
- 当前高度
heights[1] = 2
- 栈顶高度
heights[stack[stack.length - 1]] = heights[0] = 0
- 当前高度大于栈顶高度,直接入栈:
stack = [0, 1]
第3步(i = 2):
- 当前高度
heights[2] = 1
- 栈顶高度
heights[stack[stack.length - 1]] = heights[1] = 2
- 当前高度小于栈顶高度,开始弹栈:
- 弹出栈顶索引1,高度h = 2,宽度w = 2 - 0 - 1 = 1,面积 = 2 * 1 = 2,更新maxArea = 2
- 栈:
stack = [0]
- 当前高度
heights[2] = 1
大于栈顶高度,直接入栈:stack = [0, 2]
第4步(i = 3):
- 当前高度
heights[3] = 5
- 栈顶高度
heights[stack[stack.length - 1]] = heights[2] = 1
- 当前高度大于栈顶高度,直接入栈:
stack = [0, 2, 3]
第5步(i = 4):
- 当前高度
heights[4] = 6
- 栈顶高度
heights[stack[stack.length - 1]] = heights[3] = 5
- 当前高度大于栈顶高度,直接入栈:
stack = [0, 2, 3, 4]
第6步(i = 5):
- 当前高度
heights[5] = 2
- 栈顶高度
heights[stack[stack.length - 1]] = heights[4] = 6
- 当前高度小于栈顶高度,开始弹栈:
- 弹出栈顶索引4,高度h = 6,宽度w = 5 - 3 - 1 = 1,面积 = 6 * 1 = 6,更新maxArea = 6
- 弹出栈顶索引3,高度h = 5,宽度w = 5 - 2 - 1 = 2,面积 = 5 * 2 = 10,更新maxArea = 10
- 栈:
stack = [0, 2]
- 当前高度
heights[5] = 2
大于栈顶高度,直接入栈:stack = [0, 2, 5]
第7步(i = 6):
- 当前高度
heights[6] = 3
- 栈顶高度
heights[stack[stack.length - 1]] = heights[5] = 2
- 当前高度大于栈顶高度,直接入栈:
stack = [0, 2, 5, 6]
第8步(i = 7):
- 当前高度
heights[7] = 0
- 栈顶高度
heights[stack[stack.length - 1]] = heights[6] = 3
- 当前高度小于栈顶高度,开始弹栈:
- 弹出栈顶索引6,高度h = 3,宽度w = 7 - 5 - 1 = 1,面积 = 3 * 1 = 3,maxArea = 10
- 弹出栈顶索引5,高度h = 2,宽度w = 7 - 2 - 1 = 4,面积 = 2 * 4 = 8,maxArea = 10
- 弹出栈顶索引2,高度h = 1,宽度w = 7 - 0 - 1 = 6,面积 = 1 * 6 = 6,maxArea = 10
- 栈:
stack = [0]
- 当前高度
heights[7] = 0
大于栈顶高度,直接入栈:stack = [0, 7]
- 当前高度
结果
遍历结束后,最大矩形面积 maxArea
为 10。
只出现一次的数字
你提供的代码用于查找数组 nums
中唯一一个不重复的数字,但有一些问题需要修正。排序和遍历方法时间复杂度较高,break
也不需要使用。此外,代码中没有处理边界条件和正确返回值。
下面是修正和优化后的代码,其中我使用了异或运算来解决问题。异或运算时间复杂度为 O(n)
,空间复杂度为 O(1)
,这是查找单个不重复元素的一种高效方法:
修正后的代码:
1 | var singleNumber = function (nums) { |
解释
异或运算:
- 异或运算 (
^
) 的性质:a ^ a = 0
:任何数和自身异或结果为 0。a ^ 0 = a
:任何数和 0 异或结果为自身。- 异或运算具有交换律和结合律:
a ^ b ^ a = b
。
- 异或运算 (
算法步骤:
- 初始化
result
为 0。 - 遍历数组
nums
,对每个数字进行异或操作。 - 最终,
result
即为唯一一个不重复的数字。
- 初始化
时间和空间复杂度
- 时间复杂度:
O(n)
,其中n
是数组nums
的长度。我们只需遍历数组一次。 - 空间复杂度:
O(1)
,只使用了一个额外的变量result
。
这种方法相比于排序和遍历的方法更为高效,特别适用于查找数组中唯一不重复的数字。
方法2
1 | var singleNumber = function (nums) { |
当然,除了使用异或运算外,还有其他方法可以解决这个问题,例如使用哈希表或者计数的方法。这些方法的时间复杂度也是 O(n)
,但它们的空间复杂度为 O(n)
。下面是两个不同的解法:
方法一:使用哈希表
我们可以使用一个哈希表来记录每个数字出现的次数。最后遍历哈希表,找到只出现一次的数字。
1 | /** |
方法二:使用集合
我们可以利用集合来存储每个数字。如果一个数字已经存在于集合中,我们将其删除。如果不存在,我们将其添加到集合中。最后,集合中剩下的唯一元素就是只出现一次的数字。
1 | /** |
方法三:数学方法(2∗sum(集合)−sum(数组))
这是一个基于数学的方法。集合中所有元素的和乘以2减去数组中所有元素的和,结果就是只出现一次的数字。
1 | /** |
总结
哈希表方法:
- 时间复杂度:
O(n)
- 空间复杂度:
O(n)
- 时间复杂度:
集合方法:
- 时间复杂度:
O(n)
- 空间复杂度:
O(n)
- 时间复杂度:
数学方法:
- 时间复杂度:
O(n)
- 空间复杂度:
O(n)
- 时间复杂度:
上述三种方法中,哈希表和集合方法都需要额外的 O(n)
空间,而异或方法则只需要 O(1)
的空间。根据具体需求选择适合的方法。
多数元素
给定一个大小为 n
的数组 nums
,返回其中的多数元素。多数元素是指在数组中出现次数 大于 ⌊ n/2 ⌋
的元素。你可以假设数组是非空的,并且给定的数组总是存在多数元素。
你提供的代码用于寻找数组 nums
中的多数元素,即出现次数超过 n/2
的元素。代码思路是通过哈希表记录每个元素的出现次数,然后再找出出现次数超过一半的元素。这个方法是可行的,但可以进行一些优化和修正。
修正后的代码
1 | /** |
逐行分析
初始化哈希表:
1
let map = new Map();
初始化一个空的
Map
来存储每个元素的出现次数。遍历数组并记录出现次数:
1
2
3for (let num of nums) {
map.set(num, (map.get(num) || 0) + 1);
}遍历
nums
数组,对于每个元素num
,在map
中记录其出现次数。如果num
已经存在于map
中,则获取其当前的次数并加 1;如果不存在,则初始化为 1。遍历哈希表找出多数元素:
1
2
3
4
5for (let [key, value] of map.entries()) {
if (value > Math.floor(nums.length / 2)) {
return key;
}
}遍历
map
中的所有键值对,检查每个值是否大于nums.length / 2
,如果是,则返回对应的键。
优化方法:Boyer-Moore 投票算法
除了使用哈希表的方法,我们还可以使用 Boyer-Moore 投票算法,这种算法时间复杂度为 O(n)
,空间复杂度为 O(1)
。这个算法的核心思想是通过计数来找到多数元素。
1 | var majorityElement = function (nums) { |
Boyer-Moore 投票算法逐行分析
初始化候选者和计数器:
1
2let candidate = null;
let count = 0;初始化候选者为
null
,计数器为0
。遍历数组:
1
2
3
4
5
6for (let num of nums) {
if (count === 0) {
candidate = num;
}
count += (num === candidate) ? 1 : -1;
}遍历
nums
数组,如果计数器为0
,则将当前元素num
设置为候选者。然后,如果当前元素等于候选者,计数器加 1,否则计数器减 1。返回候选者:
1
return candidate;
最后返回候选者,即为多数元素。
Boyer-Moore 投票算法的优势
- 时间复杂度:
O(n)
,只需遍历数组一次。 - 空间复杂度:
O(1)
,只使用了常数级别的额外空间。
表达式求值
堆
数组中的第K个最大元素
给定整数数组 nums
和整数 k
,请返回数组中第 **k**
个最大的元素。需要找的是数组排序后的第 k
个最大的元素,而不是第 k
个不同的元素。必须设计并实现时间复杂度为 O(n)
的算法解决此问题。
方法1:排序
最直接的方法是先对数组进行排序,然后取第 k
个最大的元素。
1 | var findKthLargest = function (nums, k) { |
复杂度分析:
- 时间复杂度:O(nlogn)
- 空间复杂度:O(1)
方法 2:使用最小堆
使用最小堆可以在时间复杂度上进行优化。维持一个大小为 k
的最小堆,堆顶元素就是第 k
大的元素。
1 | var findKthLargest = function(nums, k) { |
复杂度分析:
- 时间复杂度:O(N log k),其中 N 是数组的长度。对每个元素插入和删除操作的时间复杂度是 O(log k)。
- 空间复杂度:O(k),堆的大小为 k。
方法 3:快速选择(Quickselect)
快速选择算法是快速排序的一部分,可以在平均情况下在线性时间内找到第 k
个最大的元素。
1 | var findKthLargest = function(nums, k) { |
复杂度分析:
- 时间复杂度:O(N) 在平均情况下,快速选择的时间复杂度是 O(N)。
- 空间复杂度:O(1) 快速选择是原地排序,没有使用额外的空间。
方法 4:基于快速排序的分治法
与快速选择类似,可以使用快速排序的分治思想,找到第 k
大的元素。
1 | var findKthLargest = function(nums, k) { |
复杂度分析:
- 时间复杂度:O(N log N) 在最坏情况下,分治法的时间复杂度是 O(N log N)。
- 空间复杂度:O(log N) 由于递归调用栈的空间开销。
方法 5:使用内置方法
如果可以使用JavaScript的内置方法,也可以用以下代码:
1 | var findKthLargest = function(nums, k) { |
复杂度分析:
- 时间复杂度:O(N log N) 排序的时间复杂度是 O(N log N)。
- 空间复杂度:O(1) 使用原地排序,不需要额外空间。
每种方法都有其适用的场景。使用排序方法简单直接,但在处理大数据时,快速选择和最小堆的方法更为高效。
前K个高频元素
给定一个整数数组 nums
和一个整数 k
,请返回其中出现频率前 k
高的元素。可以按 任意顺序 返回答案。
要解决这个问题,可以分为以下步骤:
- 统计每个元素的频率:使用哈希表(Map)来记录每个元素出现的次数。
- 使用最小堆(小顶堆)来找出前 k 高频率的元素:在堆中保持当前频率最高的 k 个元素。
步骤 1:统计每个元素的频率
使用哈希表 freqMap
来记录每个元素出现的频率。
步骤 2:使用最小堆来维护前 k 高频率的元素
- 遍历哈希表:将元素和其频率加入最小堆中。
- 维护堆的大小:当堆的大小超过 k 时,删除堆顶元素(频率最小的元素)。
- 输出结果:堆中剩下的元素即为频率前 k 高的元素。
code:
1 | var topKFrequent = function(nums, k) { |
复杂度分析:
- 时间复杂度:O(N log k),其中 N 是数组
nums
的长度。建立哈希表的时间复杂度是 O(N),向最小堆中插入元素和删除堆顶元素的平均时间复杂度是 O(log k),总体复杂度是 O(N log k)。 - 空间复杂度:O(N),用于存储哈希表和最小堆的元素。
这种方法利用了哈希表和最小堆的特性,通过维护堆来找出前 k 高频率的元素,非常高效。
解法2:
1 | var topKFrequent = function(nums, k) { |
这段代码利用小顶堆的特性,通过优先队列的方式高效地解决了「前 k 高频元素」的问题。它将复杂度控制在 O(N log k),适用于处理大量数据的情况,并且通过自定义的 PriorityQueue
类来实现堆操作,使代码结构清晰且具有可重用性。
解法3:
1 | let topKFrequent = function (nums, k) { |
- 对
arr
数组进行排序,排序依据是map.get(b) - map.get(a)
,即按照数字在map
中的频率降序排列。 - 使用
slice(0, k)
方法取排序后的前k
个元素作为结果返回。
这段代码通过
Map
对象统计频率,利用Set
对象进行去重,然后对数组进行排序来实现找出前k
个高频元素的功能。它的复杂度主要由排序操作决定,在最坏情况下为O(n log n)
,其中n
是nums
数组的长度。
数据流的中位数
中位数是有序整数列表中的中间值。如果列表的大小是偶数,则没有中间值,中位数是两个中间值的平均值。
- 例如
arr = [2,3,4]
的中位数是3
。 - 例如
arr = [2,3]
的中位数是(2 + 3) / 2 = 2.5
。
实现 MedianFinder 类:
MedianFinder()
初始化MedianFinder
对象。void addNum(int num)
将数据流中的整数num
添加到数据结构中。double findMedian()
返回到目前为止所有元素的中位数。与实际答案相差10-5
以内的答案将被接受。
解法1:排序(会超时)
每次添加一个数字后,对所有数字进行排序,然后根据排序结果找到中位数。
时间复杂度:
O(n log n)
,每次插入数字后进行排序。空间复杂度:
O(n)
,需要存储所有数字。
1 | class MedianFinder { |
解法2:双堆法
- 使用一个大顶堆来存储数据流中较小的一半数据,堆顶存储较小那部分数据中的最大值。
- 使用一个小顶堆来存储数据流中较大的一半数据,堆顶存储较大那部分数据中的最小值。
如果数据流中的数据个数是偶数,则大顶堆和小顶堆中的元素数相同,取两个堆顶的平均值作为中位数。如果数据流中的数据个数是奇数,则将大顶堆中的堆顶元素作为中位数(大顶堆比小顶堆多存一个元素)。
1 | // 大顶堆存储较小的一半元素,小顶堆存储较大的一半元素 |
- 时间复杂度
- 插入数据时需要将新元素插入堆,并调整堆,堆排序的复杂度为 O(log n)。
- 获取中位数的操作是常数时间 O(1)。
- 空间复杂度:O(n),使用了两个堆来存储数据流中的元素。
解法3:双指针
解题思路:
- 使用两个指针分别指向排序后数组的中间位置。
- 添加数字时,通过双指针维护数组的中间位置。
复杂度分析:
- 时间复杂度:
O(n)
(维护指针的位置)。 - 空间复杂度:
O(n)
。
1 | var MedianFinder = function () { |
二叉树
二叉树是一种每个节点最多有两个子节点的树形数据结构。通常,这两个子节点称为左子节点和右子节点。
一个二叉树由一组节点组成:
- 每个节点包含一个值(数据)。
- 每个节点最多有两个子节点(左子节点和右子节点)。
- 每个节点可以连接到一个父节点(除了根节点)。
二叉树的基本术语
- 根节点(Root):二叉树的顶端节点。每棵二叉树都有唯一的根节点。
- 叶子节点(Leaf Node):没有子节点的节点,即它的左右子节点都为
null
。 - 内部节点(Internal Node):有至少一个子节点的节点。
- 节点的深度(Depth):从根节点到该节点所经过的边的数量。
- 树的高度(Height):从根节点到叶子节点的最长路径的边数(也可以理解为树的最大深度)。
- 子树(Subtree):每个节点以及它的所有后代节点可以看作是一棵子树。
二叉树的类型
二叉树有许多不同的变种,以下是几种常见的类型:
满二叉树(Full Binary Tree):每个节点要么有 0 个子节点(叶子节点),要么有 2 个子节点。
完全二叉树(Complete Binary Tree):树的每一层(除了最后一层)都被完全填满,最后一层的所有节点都尽可能向左排列。
平衡二叉树(Balanced Binary Tree):树的任意节点的左子树和右子树的高度差不超过 1。这种结构保证了搜索、插入和删除操作的效率。
二叉搜索树(Binary Search Tree, BST):一种特殊的二叉树结构,满足以下性质:
- 对于每个节点,左子树的所有节点值都小于该节点的值。
- 对于每个节点,右子树的所有节点值都大于该节点的值。
完全二叉树(Perfect Binary Tree):所有内部节点都有两个子节点,且所有叶子节点位于同一层。
二叉树的常见操作
(1)遍历:
遍历是指按照一定的顺序访问二叉树中的每一个节点。常见的二叉树遍历方法有以下几种:
前序遍历(Pre-order Traversal):首先访问根节点,然后递归遍历左子树,最后递归遍历右子树。顺序为:根 -> 左 -> 右。
中序遍历(In-order Traversal):首先递归遍历左子树,然后访问根节点,最后递归遍历右子树。顺序为:左 -> 根 -> 右。对于二叉搜索树(BST),中序遍历可以得到递增的有序序列。
后序遍历(Post-order Traversal):首先递归遍历左子树,然后递归遍历右子树,最后访问根节点。顺序为:左 -> 右 -> 根。
层次遍历(Level-order Traversal):也称为广度优先遍历(BFS),按照层次从上到下、从左到右依次访问节点。
(2)插入和删除:
插入:向二叉树中插入新节点时,需要按照二叉树的性质找到合适的位置,通常插入在叶子节点上。
删除:删除节点是较复杂的操作,特别是在二叉搜索树中。删除节点有三种情况:
- 节点是叶子节点,直接删除。
- 节点有一个子节点,用子节点替换该节点。
- 节点有两个子节点,用其右子树中的最小节点或左子树中的最大节点替换该节点。
(3)查找:
- 对于一般的二叉树,查找某个值通常需要遍历整个树。
- 对于二叉搜索树(BST),可以利用其有序性进行高效的查找,查找操作的时间复杂度为 O(log n)。
二叉树的实际应用
二叉搜索树(BST):广泛用于实现高效的搜索、插入、删除操作,如数据库的索引和优先队列等。
堆(Heap):是一种特殊的完全二叉树,用于实现优先队列,最大堆用于实现最大值优先,最小堆用于实现最小值优先。
表达式树:用于表示算术表达式的二叉树,操作符位于内部节点,操作数位于叶子节点。
哈夫曼树:用于构建哈夫曼编码,广泛用于数据压缩算法。
二叉树的优点与缺点
优点:
- 有序性:对于二叉搜索树,具有天然的有序性,便于快速查找、插入和删除。
- 递归结构:二叉树的递归性质使得许多算法设计可以更加简洁清晰。
- 灵活性:二叉树可以用于表示许多不同的应用场景,例如表达式、优先队列等。
缺点:
- 平衡问题:普通的二叉树在插入和删除节点后可能会变得不平衡,导致最坏情况下的时间复杂度变为 O(n)。
- 空间浪费:二叉树节点中需要存储两个指针(左右子树),在节点数量很大时会带来额外的空间开销。
code
下面是一个二叉树的简单定义和遍历的实现示例(JavaScript):
1 | // 定义二叉树节点 |
总结
- 二叉树是一种基础的数据结构,每个节点最多有两个子节点。二叉树的灵活性和递归结构使其成为许多算法的基础。
- 二叉搜索树(BST) 是一种常用的二叉树,支持高效的查找、插入和删除操作。
- 遍历是二叉树的基本操作,包括前序、中序、后序和层次遍历。
- 二叉树在计算机科学中有广泛的应用,如搜索算法、优先队列、表达式树等。
前序遍历
1 | function preorderTraversal(root) { |
中序遍历
1 | function inorderTraversal(root) { |
后序遍历
1 | function postorderTraversal(root) { |
二叉树的最大深度
1 | function maxDepth(root) { |
二叉树的层次遍历
给你二叉树的根节点 root
,返回其节点值的 层序遍历 。 (即逐层地,从左到右访问所有节点)。
层次遍历(广度优先遍历)的核心思想是逐层处理节点,即先处理根节点,再处理第一层的所有节点,接着处理第二层的所有节点,以此类推。为了实现这种遍历方式,通常使用队列来帮助记录当前层和下一层的节点。
- 初始化:
- 如果根节点为空,直接返回空数组。
- 使用队列(FIFO,先进先出)数据结构来辅助层次遍历。将根节点加入队列。
- 初始化一个结果数组
res
,用于存储每一层的节点值。
- 循环处理每一层:
- 当队列不为空时,继续循环。
- 记录当前队列的长度
size
,即当前层的节点数量。 - 初始化一个数组
cur
,用于存储当前层的节点值。
- 处理当前层的每个节点:
- 使用
for
循环遍历当前层的每个节点(循环次数为size
)。 - 从队列中取出一个节点,将其值加入
cur
数组。 - 如果该节点有左子节点,则将左子节点加入队列。
- 如果该节点有右子节点,则将右子节点加入队列。
- 使用
- 保存当前层的结果:
- 将当前层的节点值数组
cur
加入结果数组res
。
- 将当前层的节点值数组
- 返回结果:
- 当所有节点都处理完毕后,
while
循环结束,返回结果数组res
。
- 当所有节点都处理完毕后,
1 | var levelOrder = function (root) { |
对于层次遍历(广度优先遍历)二叉树,时间复杂度的分析如下:
- 每个节点在
queue
中最多进队列和出队列各一次,因此每个节点被处理的次数是常数级的。 - 假设二叉树有
n
个节点,则总的处理时间为O(n)
。
算法的时间复杂度是 O(n)
,其中 n
是二叉树中的节点总数。
将有序的数组转换成二叉搜索树
给定一个整数数组 nums
,其中元素已经按 升序 排列,请你将其转换为一棵平衡二叉搜索树。
将一个已排序的整数数组转换为平衡二叉搜索树(BST)的问题可以通过递归的方式解决。核心思想是找到数组的中间元素作为根节点,然后将数组的左半部分作为左子树,右半部分作为右子树,递归地进行下去。
1 | var sortedArrayToBST = function(nums) { |
- 时间复杂度:
O(n)
,其中n
是数组的长度。每个元素在递归过程中只访问一次。 - 空间复杂度:
O(log n)
,递归调用的最大深度是树的高度,对于平衡二叉树高度为log n
。
这种方法通过递归和分治的思想,将一个排序数组转换为一棵平衡的二叉搜索树,从而实现了高效的构建过程。
二叉搜索树与双向链表
输入一棵二叉搜索树,将该二叉搜索树转成一个排序的双向链表。
要求:空间复杂度O(1)(即在原树上操作),时间复杂度 O(n)
您正在实现将二叉搜索树转换为双向链表的函数 Convert
。以下是完整的代码实现,使用中序遍历的方法来将二叉搜索树转换成一个有序的双向链表:
1 | function Convert(pRootOfTree) { |
- 定义变量:
head
作为双向链表的头节点,prev
记录遍历时的前一个节点。 - 中序遍历构建链表:通过中序遍历函数
inOrder
,按照左 -> 根 -> 右的顺序访问节点。 - 连接节点:
- 如果
head
为null
,说明是访问的第一个节点,将其设为链表头节点。 - 否则,连接
prev
和当前节点:prev.right
指向当前节点,current.left
指向prev
。
- 如果
- 返回结果:返回链表的头节点
head
。
这段代码会将二叉搜索树转换为一个有序的双向链表。
判断完全二叉树
给定一个二叉树,确定他是否是一个完全二叉树。
- 使用层序遍历(广度优先搜索,BFS)从根节点开始,逐层访问节点。
- 遇到空节点后,所有后续节点都必须是空节点。如果遇到非空节点,说明这不是一棵完全二叉树。
- 如果在遍历过程中,发现一个节点缺少子节点但后续节点还存在子节点,说明不是完全二叉树。
1 | function isCompleteTree(root) { |
- 初始化:
- 使用队列
queue
进行层序遍历,从根节点开始。 flag
用来标记是否遇到空节点。
- 使用队列
- 层序遍历:
- 从队列中取出一个节点,如果该节点为空,设置
flag
为true
。 - 如果
flag
已经被设置为true
,但后续还遇到非空节点,则说明这不是完全二叉树,直接返回false
。
- 从队列中取出一个节点,如果该节点为空,设置
- 结束条件:
- 遍历完所有节点后,如果没有违反完全二叉树的性质,返回
true
。
- 遍历完所有节点后,如果没有违反完全二叉树的性质,返回
判断平衡二叉树
输入一棵节点数为 n 二叉树,判断该二叉树是否是平衡二叉树。只需要考虑其平衡性,不需要考虑其是不是排序二叉树。
平衡二叉树(Balanced Binary Tree),具有以下性质:它是一棵空树或它的左右两个子树的高度差的绝对值不超过1,并且左右两个子树都是一棵平衡二叉树。
判断一个二叉树是否是平衡二叉树(Balanced Binary Tree),通常是指该二叉树中的每一个节点的左右子树的高度差不超过 1。也就是说,对于每一个节点,其左右子树的高度之差的绝对值不能超过 1,且它的左右子树也都是平衡二叉树。
1 | // 定义二叉树的节点结构 |
前序和中序遍历构造二叉树
给定两个整数数组 preorder
和 inorder
,其中 preorder
是二叉树的先序遍历, inorder
是同一棵树的中序遍历,请构造二叉树并返回其根节点。
从前序遍历和中序遍历的序列构造一棵二叉树,可以通过递归的方式实现。前序遍历的第一个元素总是根节点,而中序遍历中根节点的位置可以将树分为左子树和右子树。我们可以利用这一点,递归地构造二叉树。下面是实现代码,并带有详细的逐行解释。
要从前序遍历和中序遍历的序列构造一棵二叉树,我们可以利用前序遍历的特点,即前序遍历的第一个元素总是当前子树的根节点。而中序遍历可以将树分为左子树和右子树。通过递归地构建子树,我们可以重建整个二叉树。具体步骤如下:
- 找到根节点:前序遍历的第一个元素是当前子树的根节点。
- 划分左右子树:在中序遍历中找到根节点的位置,根节点左边的部分是左子树,右边的部分是右子树。
- 递归构建子树:根据划分结果,递归地构建左子树和右子树。
1 | var buildTree = function (preorder, inorder) { |
- 时间复杂度:
O(n^2)
,其中n
是树中节点的数量。在最坏情况下,每次查找中序遍历的根节点位置都需要O(n)
的时间。 - 空间复杂度:
O(n)
,用于存储构建的二叉树以及递归调用栈的空间。递归的深度最大为树的高度,对于平衡树是O(log n)
,最坏情况下(如链状树)是O(n)
。
合并二叉树
已知两颗二叉树,将它们合并成一颗二叉树。合并规则是:都存在的结点,就将结点值加起来,否则空的位置就由另一个树的结点来代替。
将两棵二叉树合并为一棵二叉树的过程需要遍历两棵树并将它们对应位置的节点值相加。如果某个位置只有一棵树有节点,直接使用该节点。
可以通过递归实现这一过程。递归函数将两个树节点作为参数,如果两个节点都存在,创建一个新的节点,其值为两个节点值之和,然后递归合并它们的左右子树。如果只有一个节点存在,返回该节点。
1 | function mergeTrees(t1, t2) { |
基本情况:
- 如果
t1
为空,返回t2
。 - 如果
t2
为空,返回t1
。
- 如果
合并当前节点:
- 创建一个新的
TreeNode
,其值为t1.val + t2.val
。
- 创建一个新的
递归合并子树:
- 合并左子树:
mergedNode.left = mergeTrees(t1.left, t2.left)
。 - 合并右子树:
mergedNode.right = mergeTrees(t1.right, t2.right)
。
- 合并左子树:
返回合并后的树:
- 返回新的
mergedNode
。
- 返回新的
- 时间复杂度:O(n),其中
n
是两棵树中节点数较多的那棵树的节点数。每个节点都会被访问一次。 - 空间复杂度:O(h),其中
h
是两棵树中较高的那棵树的高度。递归调用栈的深度等于树的高度。
前序和中序的序列构造一棵二叉树并给出右侧视图
请根据二叉树的前序遍历,中序遍历恢复二叉树,并打印出二叉树的右视图
如输入[1,2,4,5,3],[4,2,5,1,3]时,通过前序遍历的结果[1,2,4,5,3]和中序遍历的结果[4,2,5,1,3]可重建出以下二叉树:[1,3,5]
1 | function solve(preOrder, inOrder) { |
- 构建二叉树:
- 利用前序遍历数组
preOrder
确定根节点。 - 利用中序遍历数组
inOrder
确定根节点的位置,从而划分左子树和右子树的节点。 - 递归地构建左子树和右子树。
- 利用前序遍历数组
- 获取二叉树右视图:
- 使用广度优先搜索(BFS)遍历二叉树。
- 在每一层中,记录最后一个访问的节点,即为该层的右视图节点。
- 将这些节点值依次加入结果数组中。
时间复杂度分析
- 构建二叉树:
buildTree
函数中,preOrder
和inOrder
数组的切片操作每次都需要O(n)
时间,其中n
是当前数组的长度。- 在最坏情况下,构建树的每个节点都需要
O(n)
次切片操作,因此构建树的总时间复杂度为O(n^2)
。
- 获取右视图:
right
函数中,使用 BFS 遍历树,每个节点访问一次,因此时间复杂度为O(n)
。
综合起来,构建树的时间复杂度为 O(n^2)
,获取右视图的时间复杂度为 O(n)
。因此,总的时间复杂度为 O(n^2)
。
验证二叉搜索树
给你一个二叉树的根节点 root
,判断其是否是一个有效的二叉搜索树。
有效 二叉搜索树定义如下:
节点的左子树只包含小于当前节点的数。
节点的右子树只包含 大于 当前节点的数。
所有左子树和右子树自身必须也是二叉搜索树。
1 | var isValidBST = function (root) { |
二叉树的最近公共祖先
给定一棵二叉树(保证非空)以及这棵树上的两个节点对应的val值 o1 和 o2,请找到 o1 和 o2 的最近公共祖先节点。数据范围:树上节点数满足 1≤𝑛≤105 1≤n≤105 , 节点值val满足区间 [0,n)
要求:时间复杂度 𝑂(𝑛)O(n)
[!CAUTION]
本题保证二叉树中每个节点的val值均不相同。
1 | function lowestCommonAncestor(root, o1, o2) { |
- 递归终止条件:
- 如果当前节点是
null
,说明没有找到o1
或o2
,返回null
。 - 如果当前节点的值等于
o1
或o2
,返回当前节点,因为这个节点可能是最近公共祖先或是o1
或o2
本身。
- 如果当前节点是
- 递归查找左右子树:
- 对当前节点的左右子树进行递归查找,分别保存左子树和右子树的结果。
- 公共祖先判断:
- 如果左右子树都不为
null
,说明o1
和o2
分别位于当前节点的左右子树中,因此当前节点是最近公共祖先。 - 如果只有左子树或右子树不为
null
,则说明o1
和o2
都在该子树中,返回该子树的结果。
- 如果左右子树都不为
二叉搜索树的最近公共祖先
给定一个二叉搜索树, 找到该树中两个指定节点的最近公共祖先。
- 对于该题的最近的公共祖先定义:对于有根树T的两个节点p、q,最近公共祖先LCA(T,p,q)表示一个节点x,满足x是p和q的祖先且x的深度尽可能大。在这里,一个节点也可以是它自己的祖先。
- 二叉搜索树是若它的左子树不空,则左子树上所有节点的值均小于它的根节点的值; 若它的右子树不空,则右子树上所有节点的值均大于它的根节点的值
- 所有节点的值都是唯一的。
- p、q 为不同节点且均存在于给定的二叉搜索树中。
1 | function lowestCommonAncestor(root, p, q) { |
- 如果
root.val
大于max
,则说明p
和q
都在当前节点的左子树中,继续向左子树查找。 - 如果
root.val
小于min
,则说明p
和q
都在当前节点的右子树中,继续向右子树查找。 - 否则,
root
正好是p
和q
的最近公共祖先,直接返回root.val
。
二叉搜索树中第K小的元素
给定一个二叉搜索树的根节点 root
,和一个整数 k
,请你设计一个算法查找其中第 k
个最小元素(从 1 开始计数)。
解题思想是利用二叉搜索树(BST)的性质和中序遍历来找到第 k
小的元素。BST 的一个重要性质是中序遍历其节点会得到一个有序的递增序列。通过中序遍历,我们可以一次性访问 BST 中的所有节点,并且能够按照递增的顺序进行计数,因此第 k
小的元素就是中序遍历过程中第 k
个访问的节点。
方法一:中序遍历
1 | var kthSmallest = function(root, k) { |
方法二–优化方案
如果只需要找到第 k
小的元素,不需要完整的中序遍历结果数组,可以在遍历过程中直接计数并在找到第 k
小元素时立即返回,避免额外的空间开销。
1 | var kthSmallest = function(root, k) { |
- **
count
**:用于记录当前遍历到的节点是第几个节点。 - **
result
**:用于保存第k
小的节点值,一旦找到k
小的节点值,就可以停止递归。 - 中序遍历的过程:在中序遍历过程中,逐个计数,当计数等于
k
时,直接保存当前节点值并停止遍历。
时间复杂度:仍然是 O(n),最坏情况下需要遍历所有节点才能找到第
k
小的节点。空间复杂度:O(h),其中
h
是树的高度,递归栈的空间复杂度等于树的高度,最坏情况下是 O(n)。
二叉搜索树的最小绝对差
给你一个二叉搜索树的根节点 root
,返回 树中任意两不同节点值之间的最小差值 。差值是一个正数,其数值等于两值之差的绝对值。
- 中序遍历二叉搜索树:通过递归或迭代的方式对树进行中序遍历,得到一个按顺序排列的数组
res
。 - 计算最小差值:遍历数组
res
,计算相邻两个值的差值,找到最小的差值。
1 | var getMinimumDifference = function(root) { |
- 时间复杂度:O(n),其中 n 是二叉树的节点个数。我们需要遍历整个树来获得所有节点值。
- 空间复杂度:O(n),因为我们需要一个数组来保存所有节点值。
序列化二叉树
请实现两个函数,分别用来序列化和反序列化二叉树,不对序列化之后的字符串进行约束,但要求能够根据序列化之后的字符串重新构造出一棵与原二叉树相同的树。
二叉树的序列化(Serialize)是指:把一棵二叉树按照某种遍历方式的结果以某种格式保存为字符串,从而使得内存中建立起来的二叉树可以持久保存。序列化可以基于先序、中序、后序、层序的二叉树等遍历方式来进行修改,序列化的结果是一个字符串,序列化时通过 某种符号表示空节点(#)。
二叉树的反序列化(Deserialize)是指:根据某种遍历顺序得到的序列化字符串结果str,重构二叉树。
- 序列化(Serialize):
- 使用广度优先搜索(BFS)来遍历二叉树,将每个节点的值按层序加入到字符串中。
- 对于空节点,用特殊符号(如
"#"
)来表示。 - 结果是一个字符串表示的二叉树。
- 反序列化(Deserialize):
- 根据序列化的字符串重新构建二叉树,使用层序遍历的方式,从根节点开始构造树。
- 使用队列来保持当前正在处理的节点,依次为每个节点构建左右子树。
1 | // 序列化二叉树 |
- **
Serialize(pRoot)
**:- 使用一个队列(
queue
)来进行层序遍历。 - 每当处理一个节点时,将它的值保存到
result
数组中,并将它的左、右子节点加入队列。 - 如果遇到空节点,则保存特殊符号
"#"
。 - 最终将
result
数组转换为字符串并返回。
- 使用一个队列(
- **
Deserialize(s)
**:- 将序列化后的字符串分割为一个数组
values
,然后用队列帮助重建树。 - 首先创建根节点,将其加入队列。
- 依次从数组中读取值,为当前节点的左、右子节点赋值。
- 如果遇到
"#"
,表示该节点为空。
- 将序列化后的字符串分割为一个数组
- 时间复杂度:O(n),其中
n
是二叉树中的节点数。无论是序列化还是反序列化,我们都需要遍历每个节点一次。 - 空间复杂度:O(n),需要使用队列和存储结果的数组,空间复杂度与节点数成正比。
二叉树的右侧视图
给定一个二叉树的 根节点 root
,想象自己站在它的右侧,按照从顶部到底部的顺序,返回从右侧所能看到的节点值。
该算法的目的是获取二叉树的右视图,即从右侧看二叉树时能看到的所有节点。解题的核心思想是使用广度优先搜索(BFS),逐层遍历二叉树,并记录每一层的最后一个节点。
- 广度优先搜索(BFS):
- BFS 是一种逐层遍历树或图的算法。对于树的层次遍历,BFS 非常适用,因为它能够按层次逐层访问节点。
- 使用队列来实现 BFS,因为队列是先进先出(FIFO)的数据结构,适合按顺序处理节点。
- 逐层遍历并记录最后一个节点:
- 在每一层的遍历中,记录该层的最后一个节点。这个节点就是从右侧视角能看到的节点。
- 使用一个变量
lastNode
来保存每层最后一个节点。 - 遍历完每一层后,将
lastNode
的值添加到结果数组res
中。
- 节点入队和出队:
- 从队列中取出当前层的所有节点,并将它们的左子节点和右子节点依次加入队列,确保下一层的节点能够被处理。
步骤
- 输入检查:
- 如果根节点为空,直接返回空数组,因为没有节点可以被看到。
- 初始化队列和结果数组:
- 队列初始包含根节点,用于开始层次遍历。
- 结果数组用于保存每层的最右侧节点值。
- 广度优先搜索:
- 使用
while
循环进行 BFS,只要队列不为空,就继续处理节点。
- 使用
- 逐层处理:
for
循环遍历当前层的所有节点,使用levelSize
记录当前层的节点数。- 每次从队列中取出一个节点,并将其左子节点和右子节点加入队列。
lastNode
保存当前层的最后一个节点。
- 保存结果:
- 每层处理完后,将
lastNode
的值添加到结果数组中。
- 每层处理完后,将
- 返回结果:
- 最终返回结果数组,其中包含从右侧视角能看到的所有节点值。
1 | var rightSideView = function(root) { |
时间复杂度:
O(N)
,其中N
是树中的节点总数。每个节点被访问一次,因此时间复杂度为O(N)
。空间复杂度:
O(D)
,其中D
是树的最大深度。在最坏情况下,队列中可能包含一层的所有节点,因此空间复杂度为O(D)
。
二叉树的镜像
操作给定的二叉树,将其变换为源二叉树的镜像。
要求: 空间复杂度 𝑂(𝑛)O(n) 。本题也有原地操作,即空间复杂度 𝑂(1)O(1) 的解法,时间复杂度 𝑂(𝑛)O(n)
方法1–递归
1 | function Mirror(pRoot) { |
- 时间复杂度:O(n),其中
n
是二叉树中的节点数。每个节点都需要被访问一次,因此时间复杂度为 O(n)。 - 空间复杂度:O(h),其中
h
是树的高度。递归调用栈的深度等于树的高度,最坏情况下为 O(n)(完全不平衡的树),最佳情况下为 O(log n)(完全平衡的树)。
方法2–迭代实现(使用栈)
1 | function mirror(root) { |
递归实现:
- 基本情况:如果节点为空,返回
null
。 - 交换左右子树:将当前节点的左子树和右子树进行交换。
- 递归处理左右子树:对左右子树分别进行递归处理。
- 基本情况:如果节点为空,返回
迭代实现:
- 使用栈来保存需要处理的节点。
- 每次从栈中弹出一个节点,交换其左右子树,然后将左右子节点推入栈中,继续处理。
- 时间复杂度:O(n),其中
n
是二叉树中的节点数。每个节点都需要访问一次,因此时间复杂度为 O(n)。 - 空间复杂度:O(n),因为使用了栈来存储节点。最坏情况下,栈中可能需要保存所有节点,因此空间复杂度为 O(n)。
二叉树的直径
给你一棵二叉树的根节点,返回该树的 直径 。
二叉树的 直径 是指树中任意两个节点之间最长路径的 长度 。这条路径可能经过也可能不经过根节点 root
。
两节点之间路径的 长度 由它们之间边数表示。
这道题的解题思想是通过深度优先搜索 (DFS) 来计算二叉树的直径。二叉树的直径定义为任意两个节点路径中最远距离的节点数目。我们通过递归的方式计算每个节点的左右子树的深度,并更新当前的最大直径。
代码实现:
1 | var diameterOfBinaryTree = function (root) { |
解题思路
- **深度优先搜索 (DFS)**:使用 DFS 递归计算每个节点的深度。
- 最大直径更新:在递归过程中,计算左右子树的深度之和,并不断更新最大直径。
- 递归返回深度:每个节点的深度为其左右子树深度的最大值加一。
时间复杂度
- 时间复杂度:每个节点都遍历一次,所以时间复杂度是 (O(N)),其中 (N) 是二叉树的节点数。
- 空间复杂度:由于递归调用栈的深度为树的高度,最坏情况下,空间复杂度为 (O(N))(当树退化为链表时)。
通过这种方法,我们能够有效地计算出二叉树的直径,并且代码具有较高的效率和可读性。
二叉树转为链表
给你二叉树的根结点 root
,请你将它展开为一个单链表:
- 展开后的单链表应该同样使用
TreeNode
,其中right
子指针指向链表中下一个结点,而左子指针始终为null
。 - 展开后的单链表应该与二叉树 先序遍历 顺序相同。
解题思路
- 后序遍历二叉树:
- 采用后序遍历(右 -> 左 -> 根)的方式遍历二叉树,这样可以确保在修改当前节点之前,右子树和左子树已经被处理。
- 后序遍历的原因是我们要从下到上,从右到左地处理节点,这样可以确保每个节点的右指针正确指向下一个节点。
- 修改节点指针:
- 将当前节点的右指针指向上一个处理过的节点。
- 将当前节点的左指针设为
null
,因为在链表中不需要左指针。 - 更新
pre
为当前节点,以便下一个节点能够正确地指向它。
1 | var flatten = function (root) { |
时间复杂度
- 时间复杂度:
O(n)
,其中n
是二叉树的节点数。每个节点被访问一次,且每个节点的指针修改操作都是常数时间操作。 - 空间复杂度:
O(h)
,其中h
是二叉树的高度。空间复杂度主要取决于递归调用栈的深度。对于平衡二叉树,空间复杂度为O(log n)
;对于退化为链表的二叉树,空间复杂度为O(n)
。
总结
这段代码通过后序遍历(先右子树,再左子树,最后根节点)处理二叉树中的每个节点,并将二叉树原地转换为链表形式。每次遍历到一个节点时,将其右指针指向上一个访问过的节点,左指针设为 null
,然后更新 pre
为当前节点。最终,二叉树被转换为一个按先序遍历顺序的链表。
二叉树的路径总和
给定一个二叉树的根节点 root
,和一个整数 targetSum
,求该二叉树里节点值之和等于 targetSum
的 路径 的数目。
路径 不需要从根节点开始,也不需要在叶子节点结束,但是路径方向必须是向下的(只能从父节点到子节点)。
解题思想
我们需要找到二叉树中所有路径的和为给定的 targetSum
的路径条数。为了实现这一目标,我们需要在树中每个节点进行深度优先搜索(DFS),并从每个节点开始,检查所有可能的路径是否满足条件。这样做可以确保我们不会遗漏任何可能的路径。
1 | var pathSum = function (root, targetSum) { |
时间复杂度
- 对于每个节点,需要调用
depth
函数来计算从该节点开始的所有路径和。depth
函数在最坏情况下会访问树中的每个节点,因此其时间复杂度为O(N)
,其中N
是节点总数。 dfs
函数需要遍历整棵树中的每个节点,因此其时间复杂度也为O(N)
。
总的时间复杂度为 O(N^2)
,因为对于树中的每个节点,我们都执行了一次 depth
函数的完整遍历。
空间复杂度
空间复杂度主要由递归调用栈的深度决定。在最坏情况下(即树为单链表时),递归深度为 N
,因此空间复杂度为 O(N)
。
总结:该算法通过遍历每个节点并从每个节点开始检查所有可能路径,最终找到所有和为 targetSum
的路径条数,其时间复杂度为 O(N^2)
,空间复杂度为 O(N)
。
解法二–前缀和
解题思想
该算法使用深度优先搜索(DFS)遍历整棵树,并使用一个哈希表 prefixSum
来记录从根节点到当前节点的路径和的出现次数。通过计算当前路径和与目标路径和的差值,可以快速判断是否存在从某个节点到当前节点的路径和等于 targetSum
。这使得算法在一次遍历过程中即可计算出所有符合条件的路径条数。
1 | var pathSum = function (root, targetSum) { |
时间复杂度
- 单次遍历整棵树,时间复杂度为
O(N)
,其中N
是节点总数。
空间复杂度
- 主要由哈希表的大小和递归调用栈的深度决定。最坏情况下,空间复杂度为
O(N)
。
二叉树的最近路径
给定一个二叉树, 找到该树中两个指定节点的最近公共祖先。
百度百科中最近公共祖先的定义为:“对于有根树 T 的两个节点 p、q,最近公共祖先表示为一个节点 x,满足 x 是 p、q 的祖先且 x 的深度尽可能大(一个节点也可以是它自己的祖先)。”
1 | var lowestCommonAncestor = function(root, p, q) { |
时间复杂度分析
时间复杂度主要取决于对二叉树的遍历,因为需要在树中搜索节点 p
和 q
,并找到它们的最近公共祖先。
- 最坏情况下,我们需要遍历整棵二叉树,因为
p
和q
可能分别位于树的最深层,此时时间复杂度为O(n)
,其中n
是二叉树中节点的个数。
空间复杂度分析
空间复杂度包括递归调用的栈空间以及递归函数本身使用的空间。
- 递归深度:在最坏情况下,递归调用的深度可以达到树的高度。对于平衡二叉树,递归深度为
O(log n)
;对于最坏情况下的不平衡二叉树,递归深度为O(n)
。 - 额外空间:除了递归调用的栈空间外,递归函数本身使用的额外空间很小,是常数级别的空间,因此空间复杂度主要取决于递归调用的栈空间。
综合考虑,改进后的代码在时间复杂度上是 O(n)
,在空间复杂度上是 O(log n)
到 O(n)
,具体取决于树的形状(平衡还是不平衡)。
二叉树最大的路径和
二叉树中的 路径 被定义为一条节点序列,序列中每对相邻节点之间都存在一条边。同一个节点在一条路径序列中 至多出现一次 。该路径 至少包含一个 节点,且不一定经过根节点。
路径和 是路径中各节点值的总和。
给你一个二叉树的根节点 root
,返回其 最大路径和 。
1 | var maxPathSum = function (root) { |
在分析这段代码的时间复杂度时,我们可以考虑以下几个方面:
时间复杂度分析
递归函数的调用次数:
- 对于每个节点,递归函数
maxPathSumRecursive
都会被调用一次。因此,时间复杂度与节点的数量成正比,即为O(n)
,其中n
是二叉树中节点的个数。
- 对于每个节点,递归函数
每次递归的时间复杂度:
- 在每次调用
maxPathSumRecursive
时,我们执行了常数时间的计算操作(比如比较、加法、取最大值等)。因此,每个递归调用的时间复杂度可以视为O(1)
。
- 在每次调用
总体时间复杂度:
- 综合以上两点,整个算法的时间复杂度为
O(n)
,其中n
是二叉树中节点的个数。这是因为我们对每个节点都进行了一定数量的常数时间操作,总共进行了n
次这样的操作。
- 综合以上两点,整个算法的时间复杂度为
空间复杂度分析
递归调用的空间复杂度:
- 在递归调用的过程中,会使用系统栈来存储递归调用的信息,因此空间复杂度取决于递归调用的深度。
- 在最坏情况下,二叉树是一个链式结构(类似链表),递归深度可以达到
O(n)
,此时空间复杂度为O(n)
。 - 在平衡二叉树的情况下,递归深度为
O(log n)
,因此空间复杂度为O(log n)
。
额外的空间:
- 除了递归调用的栈空间外,算法本身并没有使用额外的辅助空间,因此额外空间复杂度为
O(1)
。
- 除了递归调用的栈空间外,算法本身并没有使用额外的辅助空间,因此额外空间复杂度为
综合考虑,该算法的时间复杂度为 O(n)
,空间复杂度取决于递归调用的深度,最坏情况下为 O(n)
,平均情况下为 O(log n)
(对于平衡二叉树)。
二叉搜索树与双向链表
输入一棵二叉搜索树,将该二叉搜索树转换成一个排序的双向链表。
将二叉搜索树转换成排序的双向链表的过程可以通过中序遍历来实现。在遍历过程中,将每个节点的左右子指针重新调整为双向链表的前后指针。
- 定义辅助函数:用来进行中序遍历,并在遍历过程中调整节点指针。
- 维护双向链表指针:在遍历过程中,维护一个前驱节点指针
prev
,用于调整当前节点的前驱指针。 - 连接双向链表:遍历结束后,返回双向链表的头节点。
1 | function Convert(pRootOfTree) { |
- **定义辅助函数
inOrder
**:进行中序遍历并调整节点指针。 - 维护双向链表指针:
prev
:用于记录当前节点的前驱节点。head
:用于记录双向链表的头节点。
- 调整节点指针:
- 如果
prev
为null
,说明当前节点是双向链表的头节点。 - 否则,调整当前节点与前驱节点的指针,使其形成双向链表。
- 如果
- 返回结果:遍历结束后,返回双向链表的头节点
head
。
注意
- 二叉树为空时返回
null
。 - 确保在中序遍历过程中正确调整节点指针,使其形成双向链表。
回溯
回溯算法是一种基于递归的算法设计技术,用于解决一些组合问题。其核心思想是逐步构建一个解,然后在发现该解不满足条件时,返回到上一步,尝试另一种可能性。这个过程不断重复,直到找到所有可能的解或确定没有解。
回溯算法的基本步骤
- 选择:选择一个可能的选择进行尝试。
- 约束:检查当前选择是否满足问题的约束条件。
- 终止条件:判断当前选择是否为一个完整的解。
- 回溯:如果当前选择不满足条件或不是一个完整的解,回溯到上一步,尝试其他选择。
回溯算法的伪代码
以下是回溯算法的一般伪代码结构:
1 | function backtrack(solution): |
回溯算法的应用
回溯算法在许多经典的计算问题中都有应用,包括但不限于以下几个方面:
- N皇后问题:在N×N的棋盘上放置N个皇后,使得它们不能互相攻击。
- 图的着色问题:为图中的每个节点分配一种颜色,确保相邻节点颜色不同。
- 数独:填充数独的解。
- 旅行商问题:找到一条经过所有城市并且总距离最短的路径。
回溯算法的优缺点
优点:
- 简单易理解,适用于小规模问题。
- 可以用于生成所有可能的解,保证找到所有可能的解。
缺点:
- 对于大规模问题,回溯算法的时间复杂度可能非常高,因为其本质上是穷举所有可能的解。
- 需要大量的递归调用,可能导致较高的空间复杂度。
示例
以经典的N皇后问题为例,来说明回溯算法的应用。N皇后问题要求在N×N的棋盘上放置N个皇后,使得它们互相不能攻击。回溯算法的步骤如下:
- 从第一个皇后开始,尝试将其放置在第一行的一个位置。
- 递归地尝试将下一个皇后放置在下一行的某个位置,同时检查是否与之前放置的皇后冲突。
- 如果发现冲突,回溯到上一步,尝试其他位置。
- 重复上述步骤,直到所有皇后都成功放置或者确定无解。
通过回溯算法,可以系统地探索所有可能的解决方案,并找到满足条件的所有解。
全排列
给定一个不含重复数字的数组 nums
,返回其 所有可能的全排列 。可以 按任意顺序 返回答案。
解题思想
回溯算法基本思路:
- 回溯算法是一种通过尝试所有可能的候选解来解决问题的方法。它适用于求解组合优化问题,其中每一个解都是通过递归构建的。
- 在本问题中,我们要求生成数组
nums
的所有排列,即不同元素的所有可能顺序组合。
具体实现步骤:
- 使用一个递归函数
backtrack
来构建排列。 - 使用一个
path
数组来存储当前的排列路径。 - 使用一个
used
数组来标记每个元素是否已经被使用过。 - 当
path
的长度等于nums
的长度时,将path
加入结果集合res
。 - 对于每个位置
i
,如果nums[i]
没有被使用过,则将其加入path
,标记为已使用,然后递归调用backtrack
。 - 递归完成后,回溯:将
path
的最后一个元素移除,将其对应的used
标记为未使用,以便尝试下一个可能的排列。
- 使用一个递归函数
返回结果:
- 最终,函数返回
res
,即包含所有排列的数组。
- 最终,函数返回
1 | var permute = function (nums) { |
时间复杂度分析
时间复杂度:假设数组
nums
的长度为n
,生成所有排列的数量为n!
(即阶乘)。因此,生成所有排列的时间复杂度为O(n!)
。- 每个排列的构建涉及
n
次选择,每次选择中有n
个选项,因此总共有n!
种排列。 - 在每个排列的构建过程中,需要对
path
的操作(push 和 pop),这些操作的时间复杂度可以视为常数时间,因为path
最多包含n
个元素。
- 每个排列的构建涉及
空间复杂度:主要是递归调用和存储结果集所需的空间。
- 递归调用的最大深度为
n
,因此空间复杂度为O(n)
。 - 结果集
res
最多包含n!
个排列,每个排列的长度为n
,因此结果集的空间复杂度为O(n * n!)
。
- 递归调用的最大深度为
总结
回溯算法是一种递归枚举所有可能性的有效方法,尤其适用于组合优化问题。在本问题中,通过回溯算法可以生成数组的所有排列。虽然时间复杂度是 O(n!)
,这在大规模问题上可能会导致性能问题,但在实践中,回溯算法在处理小规模问题时表现良好,并且能够准确地找到所有解。
全排列||
给定一个可包含重复数字的序列 nums
,按任意顺序 返回所有不重复的全排列。
这个问题的解题思想是利用回溯算法生成包含重复元素的全排列,并通过一些条件判断和技巧来确保生成的排列是唯一的。
解题思想:
排序数组:
- 首先对输入的数组
nums
进行排序,这样相同的元素会相邻排列。排序后的数组有助于在回溯过程中判断重复元素和跳过已经处理过的情况。
- 首先对输入的数组
回溯算法:
- 使用回溯算法来探索所有可能的排列。回溯算法是一种深度优先搜索(DFS)的应用,通过递归实现。
- 主要思路是从左到右依次选择未使用过的元素,加入当前排列
cur
中,然后递归处理剩余的元素。如果当前cur
的长度等于nums
的长度,则说明找到了一个完整的排列,将其加入结果数组res
中。 - 在递归调用之后,需要撤销选择,即将当前加入的元素从
cur
中移除,并将其标记为未使用,以便进行下一次选择。
处理重复情况:
- 使用
used
数组来标记每个位置的元素是否已经被选择过。 - 在循环中,如果当前元素已经被使用 (
used[i] === true
),则跳过该元素。 - 对于排序后的数组,在判断重复元素时,如果当前元素与上一个元素相同,并且上一个元素未被使用过 (
!used[i - 1]
),则跳过当前元素,以确保不会生成重复的排列。
- 使用
递归终止条件:
- 当
cur
的长度等于nums
的长度时,将当前排列加入res
中,并返回,结束当前递归路径。
- 当
1 | var permuteUnique = function(nums) { |
复杂度分析
- 时间复杂度:假设数组
nums
的长度为n
,在最坏情况下,所有排列都是唯一且符合条件的。回溯算法的时间复杂度为O(n * n!)
,其中n!
是所有可能的排列数,每个排列的生成和处理都需要O(n)
的时间复杂度。 - 空间复杂度:主要消耗在递归调用栈和存储结果的空间。使用了
used
数组和cur
数组来记录状态和当前排列,以及最终的res
数组来存储所有符合条件的排列。因此,空间复杂度为O(n)
。
总体来说,这种解法利用回溯算法和一些额外的判断条件,能够高效地生成包含重复元素的所有唯一排列,并且确保每个排列只出现一次。
下一个排列
整数数组的一个 排列 就是将其所有成员以序列或线性顺序排列。
- 例如,
arr = [1,2,3]
,以下这些都可以视作arr
的排列:[1,2,3]
、[1,3,2]
、[3,1,2]
、[2,3,1]
。
整数数组的 下一个排列 是指其整数的下一个字典序更大的排列。更正式地,如果数组的所有排列根据其字典顺序从小到大排列在一个容器中,那么数组的 下一个排列 就是在这个有序容器中排在它后面的那个排列。如果不存在下一个更大的排列,那么这个数组必须重排为字典序最小的排列(即,其元素按升序排列)。
- 例如,
arr = [1,2,3]
的下一个排列是[1,3,2]
。 - 类似地,
arr = [2,3,1]
的下一个排列是[3,1,2]
。 - 而
arr = [3,2,1]
的下一个排列是[1,2,3]
,因为[3,2,1]
不存在一个字典序更大的排列。
给你一个整数数组 nums
,找出 nums
的下一个排列。必须** 原地 **修改,只允许使用额外常数空间。
解题思路:
**从右向左找到第一个降序的位置
i
**:- 从数组的倒数第二个元素开始向前查找,找到第一个位置
i
满足nums[i] < nums[i+1]
。这是因为如果该位置满足这个条件,可以使得我们修改这个位置以获得字典序更大的排列。
- 从数组的倒数第二个元素开始向前查找,找到第一个位置
**找到大于
nums[i]
的最小元素位置j
**:- 在位置
i+1
到数组末尾之间,找到最小的元素nums[j]
,满足nums[j] > nums[i]
。这样做是为了确保新的排列尽可能小地增加。
- 在位置
**交换元素
nums[i]
和nums[j]
**:- 将位置
i
的元素和位置j
的元素进行交换。
- 将位置
翻转从位置
i+1
到末尾的元素:- 最后,翻转从位置
i+1
到数组末尾的所有元素。这一步确保得到的是下一个字典序更大的排列,并且是最小的增加量。
- 最后,翻转从位置
特殊情况处理:
- 如果整个数组已经是降序排列(即没有找到位置
i
满足nums[i] < nums[i+1]
),则直接翻转整个数组,得到最小的字典序排列。
- 如果整个数组已经是降序排列(即没有找到位置
code:
1 | var nextPermutation = function (nums) { |
这段代码通过以上的步骤实现了寻找数组 nums
的下一个排列,并且在原地进行修改,符合题目要求的要求。
复杂度分析:
时间复杂度:整个算法的时间复杂度为
O(n)
,其中n
是数组nums
的长度。这是因为我们需要遍历数组两次(一次找位置i
,一次找位置j
),并进行一次翻转操作。空间复杂度:算法使用了常数额外空间
O(1)
,除了存储输入数组外,没有使用额外空间。
示例解释:
假设输入数组 nums = [1, 2, 3]
:
**找到位置
i
**:从右向左遍历,找到nums[1] < nums[2]
,因此i = 1
。**找到位置
j
**:在位置i+1
到数组末尾中,找到nums[2] = 3
大于nums[1] = 2
,因此j = 2
。交换元素:交换
nums[i]
和nums[j]
,得到数组[1, 3, 2]
。翻转操作:翻转从位置
i+1
到末尾的元素,得到最终结果[1, 3, 2]
,这是数组[1, 2, 3]
的下一个排列。
子集
给你一个整数数组 nums
,数组中的元素 互不相同 。返回该数组所有可能的子集(幂集)。解集 不能 包含重复的子集。你可以按 任意顺序 返回解集。
解题思想
这段代码使用了回溯算法来生成给定数组 nums
的所有子集。回溯算法是一种递归的深度优先搜索方法,它通过不断地做选择和撤销选择来探索所有可能的解空间。
**回溯函数
backtrack
**:backtrack
函数接收两个参数:start
表示当前处理的起始位置,subset
表示当前构建的子集。- 在每次递归调用开始时,将当前子集
subset
的拷贝加入结果集res
中,这样做是为了避免后续对subset
的修改影响到已经加入结果集的内容。 - 然后,从
start
开始循环遍历数组nums
,将nums[i]
加入到subset
中,然后递归调用backtrack(i + 1, subset)
来处理下一个位置的元素。 - 在递归返回后,通过
subset.pop()
进行回溯,即移除最后加入的元素,以便尝试下一个可能的选择。
结束条件:
- 当
backtrack
函数开始时,如果start
等于nums.length
,表示当前位置已经超过数组长度,不再进行递归调用,直接返回。
- 当
初始调用:
- 初始时调用
backtrack(0, [])
,从数组的第一个位置开始生成子集,初始子集为空数组[]
。
- 初始时调用
1 | /** |
时间复杂度
- 时间复杂度:O(2^n)
- 回溯算法的时间复杂度主要取决于生成所有子集的数量。对于每个元素,可以选择加入或不加入子集,因此共有 2^n 种可能的子集组合。
- 每个子集的生成过程中,都涉及将当前子集的拷贝加入结果集
res
,这个操作的复杂度是 O(n),其中 n 是subset
的长度。 - 所以总体来说,时间复杂度是 O(2^n * n)。
空间复杂度
- 空间复杂度:O(n * 2^n)
- 空间复杂度主要取决于递归调用栈的深度,最坏情况下可以达到 O(n)。
- 另外,存储结果集的空间复杂度为 O(n * 2^n),因为有 2^n 个子集,每个子集的平均长度为 O(n)。
总结
通过回溯算法,这段代码能够有效地生成一个数组的所有子集。每次递归调用都尝试将当前位置的元素加入子集,并递归处理下一个位置,直到遍历完整个数组。通过合理的回溯和递归操作,确保了每个可能的组合都被考虑到,同时避免了重复计算,从而达到了生成所有子集的目的。
字母大小全排列
给定一个字符串 s
,通过将字符串 s
中的每个字母转变大小写,可以获得一个新的字符串。返回 所有可能得到的字符串集合 。以 任意顺序 返回输出。
要解决这个问题,我们可以使用回溯算法来生成所有可能的字符串集合,其中每个字符可以转换为其大小写形式。
解法一——回溯
解题思路
回溯算法基本思路:
- 我们从字符串的第一个字符开始,依次考虑每个字符的大小写转换。
- 对于每个字符,可以选择保持其原始大小写,或者转换为相应的另一种大小写形式。
- 使用递归来生成所有可能的组合,直到处理完字符串的所有字符。
具体实现步骤:
- 定义一个递归函数
backtrack
,它接收两个参数:当前处理的字符索引index
和当前形成的字符串current
。 - 在每个字符位置上,分两种情况递归处理:
- 将当前字符转换为其大写形式或小写形式,并继续向下递归。
- 如果已经到达字符串的末尾(
index === s.length
),则将形成的字符串加入结果集合。
- 使用一个数组
res
来存储所有可能的字符串。
- 定义一个递归函数
返回结果:
- 最终,将生成的所有字符串存储在数组
res
中返回。
- 最终,将生成的所有字符串存储在数组
实现代码
1 | var letterCasePermutation = function(s) { |
代码说明
**回溯函数
backtrack
**:backtrack
函数根据当前处理的字符索引index
和形成的当前字符串current
进行递归处理。- 当
index
等于s.length
时,表示已经处理完所有字符,将current
加入结果集res
中。 - 对于每个字符,首先将其原样加入
current
中,然后判断是否为字母,如果是则添加其对应的大写形式。
字符处理:
- 使用正则表达式
/[a-zA-Z]/.test(char)
来检测当前字符是否为字母。 - 如果是字母,则添加其大写形式到
current
中(避免添加两次相同的形式)。
- 使用正则表达式
初始调用:
- 初始调用
backtrack(0, '')
从字符串的第一个字符开始递归处理,初始的current
为空字符串。
- 初始调用
时间复杂度
时间复杂度:O(2^n)
- 回溯算法的时间复杂度主要取决于生成的字符串数量,对于每个字符,可以选择两种形式(原始形式和大写形式)。
空间复杂度:
- 空间复杂度主要由递归调用栈的深度决定,最坏情况下可以达到 O(n),其中 n 是字符串
s
的长度。 - 另外,存储结果的空间复杂度为 O(2^n),因为最多会生成 2^n 个字符串。
- 空间复杂度主要由递归调用栈的深度决定,最坏情况下可以达到 O(n),其中 n 是字符串
这种方法通过递归和回溯的方式,有效地生成了所有可能的字符串形式,以达到题目要求的所有可能得到的字符串集合。
解法二——迭代
除了使用回溯算法外,还可以考虑使用迭代的方法来生成所有可能的字符串集合。这种方法可以通过遍历输入字符串,并根据每个字符的类型(字母或数字)动态更新结果集合。让我展示一种基于迭代的解决方案。
迭代解决方案
迭代解决方案的基本思路是使用一个数组来存储每一步生成的结果,并根据输入字符串中的每个字符更新这个数组。
初始定义:
- 创建一个初始的数组
result
,将空字符串""
加入作为初始的结果。
- 创建一个初始的数组
迭代过程:
- 遍历输入字符串
s
中的每个字符。 - 对于每个字符,如果是字母,则遍历当前
result
数组中的每个字符串,生成一个新的字符串,包括原始字符和其大写形式,并将生成的新字符串加入一个临时数组nextResult
。 - 如果是数字,则直接将当前
result
数组中的每个字符串加上这个数字字符,加入到nextResult
中。
- 遍历输入字符串
更新结果集:
- 将
nextResult
数组的内容更新回result
,以便下一次迭代继续使用。
- 将
返回结果:
- 最终
result
中存储的即为所有可能得到的字符串集合。
- 最终
实现代码
1 | /** |
代码说明
初始定义:
- 创建一个初始的
result
数组,其中包含一个空字符串""
,作为初始的结果。
- 创建一个初始的
迭代过程:
- 遍历输入字符串
s
中的每个字符char
。 - 如果
char
是字母(使用正则表达式/[a-zA-Z]/.test(char)
进行判断),则遍历当前result
数组中的每个字符串str
,生成两个新的字符串:str + char.toLowerCase()
:将char
转换为小写加入新的字符串。str + char.toUpperCase()
:将char
转换为大写加入新的字符串。
- 如果
char
是数字,则直接遍历result
数组中的每个字符串str
,将char
加入到str
后面形成新的字符串。
- 遍历输入字符串
更新结果集:
- 将生成的新字符串数组
nextResult
赋值给result
,以便下一次迭代使用。
- 将生成的新字符串数组
返回结果:
- 最终返回
result
,其中包含了所有可能的字符串集合。
- 最终返回
时间复杂度
时间复杂度:O(2^n)
- 对于每个字符,可能生成两个新字符串(大小写形式),因此最终的字符串数量为 2^n。
- 每次循环需要遍历
result
数组中的字符串,因此总体时间复杂度是 O(2^n * n),其中 n 是输入字符串s
的长度。
空间复杂度:O(2^n * n)
- 空间复杂度主要取决于存储结果的数组
result
,以及每个字符串的长度为 n。
- 空间复杂度主要取决于存储结果的数组
这种迭代方法避免了递归调用带来的额外内存消耗,同时通过动态更新结果集来生成所有可能的字符串集合,是另一种有效的解决方案。
在处理字符串大小写转换生成所有可能字符串集合的问题中,回溯算法和迭代算法各有其优缺点,简单性可以从几个角度来评估:
方法比较
理解和实现:
- 回溯算法:
- 回溯算法通常涉及递归和回溯的概念,需要理解递归调用和回溯过程中的状态管理。
- 实现时需要考虑如何维护当前路径、处理选择列表以及正确的回溯操作。
- 迭代算法:
- 迭代算法更加直观,可以通过循环和条件语句来动态更新结果集。
- 每一步都是直接在当前状态下进行计算,相对来说更易于理解和实现。
- 回溯算法:
代码复杂度:
- 回溯算法:
- 需要设计和管理递归函数,考虑递归调用带来的栈空间消耗。
- 可能需要额外的数据结构来存储中间状态,如路径的深拷贝。
- 迭代算法:
- 使用基本的循环和数组操作,代码结构相对直观和简单。
- 不涉及递归调用,可以减少栈空间的使用,适用于大数据集的情况。
- 回溯算法:
性能和空间消耗:
- 回溯算法:
- 可能存在大量的递归调用,如果不适当地进行状态管理和剪枝,会消耗较多的栈空间。
- 需要考虑额外的空间复杂度用于存储结果集和中间状态。
- 迭代算法:
- 在每一步迭代中动态更新结果集,可能会更有效地利用内存。
- 不会遇到栈溢出的问题,适合处理大规模数据集。
- 回溯算法:
结论
从简单性的角度来看,迭代算法通常更容易理解和实现。它直接在当前状态下处理,避免了递归调用可能带来的复杂性和额外的内存消耗。在大多数情况下,迭代算法对于处理字符串大小写转换生成所有可能字符串集合的问题更加直观和高效。
因此,如果您更注重简单性和直观性,并且不需要额外的递归调用管理,推荐使用迭代算法。如果您熟悉回溯算法或者问题需要经典的深度优先搜索(DFS)策略,那么回溯算法也是一个有效的选择,尤其适用于需要深度探索所有可能性的场景。
电话号码的字母组合
给定一个仅包含数字 2-9
的字符串,返回所有它能表示的字母组合。答案可以按 任意顺序 返回。给出数字到字母的映射如下(与电话按键相同)。注意 1 不对应任何字母。
要解决这个问题,我们可以使用回溯算法。给定一个仅包含数字 2-9 的字符串,每个数字对应多个字母,我们需要生成所有可能的字母组合。
数字到字母的映射
首先,需要一个映射表,将数字映射到对应的字母:
1 | 2 -> "abc" |
解题思路
我们使用回溯算法来生成所有可能的组合:
- 初始化映射表:使用一个数组
mapping
来存储数字到字母的映射关系。 - 定义回溯函数:这个函数将逐步构建可能的字母组合。
- 处理递归终止条件:当组合长度等于输入字符串长度时,将当前组合加入结果集。
- 遍历当前数字对应的所有字母:将每个字母加入当前组合,然后递归处理下一个数字。
- 回溯:在递归返回后,移除当前字母,以便尝试下一个可能的字母。
代码实现
以下是具体的代码实现:
1 | var letterCombinations = function(digits) { |
复杂度分析
- 时间复杂度:O(3^N * 4^M),其中 N 是输入中对应 3 个字母的数字个数,M 是对应 4 个字母的数字个数。因为每个数字对应的字母数不同,组合的总数是 3^N * 4^M。
- 空间复杂度:O(N),这里 N 是输入字符串的长度。递归调用的深度最多为 N,存储当前路径的数组
cur
也是 O(N)。
这种方法简洁且高效,利用回溯法可以生成所有可能的组合。
组合总和
给你一个 无重复元素 的整数数组 candidates
和一个目标整数 target
,找出 candidates
中可以使数字和为目标数 target
的 所有 不同组合 ,并以列表形式返回。你可以按 任意顺序 返回这些组合。
candidates
中的 同一个 数字可以 无限制重复被选取 。如果至少一个数字的被选数量不同,则两种组合是不同的。
对于给定的输入,保证和为 target
的不同组合数少于 150
个。
理解解题思路并逐行解释代码,然后进行复杂度分析是非常重要的。我们将继续使用回溯算法来解决允许重复选择元素的组合求和问题。
解题思路
回溯算法基本思路:
- 回溯算法是一种通过深度优先搜索(DFS)寻找所有解的算法。
- 在本题中,我们需要找出数组
candidates
中所有允许重复选择的组合,使得这些组合的元素之和等于给定的target
。
递归函数设计:
- 设计一个递归函数
backtrack
,该函数会根据当前的选择路径进行搜索,并更新当前的组合cur
和剩余目标值remain
。
- 设计一个递归函数
回溯过程:
- 与前面的题目相比,不同之处在于每次递归调用时,可以从当前位置开始选择元素,并允许重复选择当前位置的元素。
- 当当前组合
cur
的和等于target
时,将当前组合加入结果集res
中。 - 如果当前组合的和已经超过
target
,则进行回溯操作,尝试其他可能的组合。
代码实现
1 | var combinationSum = function(candidates, target) { |
代码解释和改进
**回溯函数
backtrack
**:- 参数
start
:表示从candidates
数组的哪个位置开始选择元素。 - 参数
remain
:表示当前剩余的目标值。 - 如果
remain === 0
,将当前组合cur
加入结果集res
中。 - 遍历
candidates
数组,从start
开始选择元素:- 如果当前元素大于
remain
,跳过当前循环(剪枝操作)。 - 将当前元素加入
cur
中,递归调用backtrack
继续向下搜索。 - 回溯(撤销选择),尝试下一个可能的选择。
- 如果当前元素大于
- 参数
调用回溯函数:
backtrack(0, target)
:从candidates
数组的第一个位置开始,初始目标值为target
。
复杂度分析
- 时间复杂度:假设
candidates
数组的长度为n
,目标值为target
。在最坏情况下,每个元素都可能被选取多次,因此时间复杂度为O((target / min(candidates))^n)
,即指数级别的复杂度。 - 空间复杂度:递归调用的深度最多为
target / min(candidates)
,加上存储结果的空间,空间复杂度也为O((target / min(candidates))^n)
。
示例
假设 candidates = [2, 3, 6, 7]
,target = 7
。
调用 combinationSum(candidates, target)
后,返回结果应为 [[2, 2, 3], [7]]
,表示所有可能的组合为 [2, 2, 3]
和 [7]
。
这种方法能够有效地找出所有允许重复选择元素的组合,利用回溯算法遍历所有可能性,是经典的组合求和问题的解决方法之一。
括号生成
数字 n
代表生成括号的对数,请你设计一个函数,用于能够生成所有可能的并且 有效的 括号组合。
解题思想
- 回溯法:
- 回溯法是一种通过递归来尝试所有可能的组合的算法。在这个问题中,我们使用回溯法来生成所有可能的括号组合。
- 有效性条件:
- 在构建组合的过程中,我们需要确保每一步构建出来的部分组合都是有效的。
- 有效的括号组合需要满足:
- 左括号
(
的数量不超过右括号)
的数量。 - 在任何时候,添加的右括号
)
数量不能超过左括号(
的数量。
- 左括号
1 | var generateParenthesis = function(n) { |
空间复杂度主要取决于递归调用时使用的栈空间,以及存储结果的空间。下面来详细分析空间复杂度:
时间复杂度分析:
对于生成有效括号组合的问题,时间复杂度分析主要考虑两方面:
生成所有可能的括号组合:
- 每个括号组合长度为
2n
,每个位置上可以是左括号(
或右括号)
,因此所有可能的括号组合总数是2^(2n)
。
- 每个括号组合长度为
有效括号组合的数量:
- 有效的括号组合数量是第
n
个卡塔兰数C(n)
,其近似值为4^n / (n * sqrt(n))
。虽然生成所有可能的括号组合需要O(2^(2n))
的时间,但实际上有效的括号组合数量少得多,大约是O(4^n / sqrt(n))
。
- 有效的括号组合数量是第
生成和验证有效括号组合的时间:
- 在最坏情况下,生成每个有效组合的时间复杂度是
O(n)
,因为需要在递归过程中构建和检查每个组合的有效性。
- 在最坏情况下,生成每个有效组合的时间复杂度是
综合来看,总时间复杂度主要受到有效括号组合数量的影响,因此总时间复杂度约为 O(4^n / sqrt(n))
。
空间复杂度分析:
空间复杂度主要考虑两方面:
递归调用栈的空间:
- 在递归过程中,调用栈的最大深度为
2n
,即左括号和右括号各n
个。因此,递归调用栈的空间复杂度为O(n)
。
- 在递归过程中,调用栈的最大深度为
存储结果的空间:
result
数组用于存储所有有效的括号组合。有效括号组合的数量是O(4^n / sqrt(n))
,每个组合的长度为2n
。- 因此,结果数组的空间复杂度为
O(n * 4^n / sqrt(n))
,简化为O(4^n / sqrt(n))
。
综合来看,总空间复杂度约为 O(4^n / sqrt(n))
。
结论:
- 时间复杂度:
O(4^n / sqrt(n))
- 空间复杂度:
O(4^n / sqrt(n))
这种复杂度表示该算法在生成有效括号组合时是相对高效的,但随着 n
的增大,组合数量呈指数级增长,计算和存储的资源需求也会显著增加。
单词搜索
单词必须按照字母顺序,通过相邻的单元格内的字母构成,其中“相邻”单元格是那些水平相邻或垂直相邻的单元格。同一个单元格内的字母不允许被重复使用。
这个问题可以用深度优先搜索(DFS)结合回溯法来解决。需要在一个二维网格中搜索是否存在一个单词,其中单词的字母必须按照字母顺序通过相邻的单元格(水平或垂直相邻)构成,并且同一个单元格内的字母不能重复使用。
解题思想:
遍历网格:
- 对网格中的每个单元格进行遍历,尝试从该单元格开始匹配单词。
**深度优先搜索 (DFS)**:
- 定义一个DFS函数,用于从当前单元格出发,尝试匹配单词的每个字母。
- 如果当前单元格的字母与单词中对应位置的字母匹配,则继续搜索相邻的四个方向(上、下、左、右)。
- 使用回溯法,即在搜索完一个方向后,需要撤销当前单元格的选择,以便尝试其他方向。
边界条件和剪枝:
- 边界条件包括检查索引是否越界,当前单元格是否已经被访问,以及当前单元格的字母是否与单词对应位置的字母匹配。
- 剪枝操作可以减少不必要的搜索,例如一旦发现某个方向无法匹配,则立即返回。
code:
1 | var exist = function (board, word) { |
复杂度分析:
时间复杂度:
- 最坏情况下,需要遍历整个网格的每个单元格,进行一次DFS。DFS的深度最大为单词的长度
L
。每次DFS有四个方向,因此时间复杂度为O(N * M * 4^L)
,其中N
和M
分别为网格的行数和列数,L
为单词的长度。
- 最坏情况下,需要遍历整个网格的每个单元格,进行一次DFS。DFS的深度最大为单词的长度
空间复杂度:
- 主要空间消耗在于递归调用栈。最坏情况下递归栈的深度为单词的长度
L
,因此空间复杂度为O(L)
。
- 主要空间消耗在于递归调用栈。最坏情况下递归栈的深度为单词的长度
这个解法通过遍历每个单元格,并使用DFS进行深度优先搜索和回溯,确保可以找到所有可能的路径并验证其有效性。通过剪枝操作,避免了不必要的计算,从而提高了算法的效率。
分割回文串
给你一个字符串 s
,请你将 s
分割成一些子串,使每个子串都是回文串。返回 s
所有可能的分割方案。
解题思想
该问题的目标是找到所有可能的回文子串分割。我们可以使用回溯法来解决这个问题。
步骤:
- 遍历字符串的每一个可能的起点和终点,检查该子串是否为回文。
- 如果是回文,则将该子串加入当前路径,并继续检查剩下的部分。
- 如果遍历到字符串的末尾,则将当前路径加入结果数组。
- 回溯到上一步,继续检查其他可能的子串。
代码实现
1 | var partition = function(s) { |
复杂度分析
时间复杂度
- 生成所有子串:
- 生成所有子串的复杂度是 O(2n)O(2^n)O(2n),因为每个字符在回文分割中有两种选择:作为单独的字符或者与其他字符组成回文。
- 检查回文性:
- 对于每一个子串,需要 O(n)O(n)O(n) 的时间来检查它是否是回文。因此,在最坏情况下,回文检查的复杂度是 O(n⋅2n)O(n \cdot 2^n)O(n⋅2n)。
- 组合的生成:
- 每个可能的分割都会产生一个路径,路径的生成和记录也是 O(n⋅2n)O(n \cdot 2^n)O(n⋅2n)。
综合考虑,时间复杂度为 O(n⋅2n)O(n \cdot 2^n)O(n⋅2n)。
空间复杂度
- 递归调用栈:
- 最深的递归深度为 O(n)O(n)O(n),因为每次递归调用都会消耗栈空间。
- 存储路径:
- 存储所有可能的路径和中间结果需要 O(n⋅2n)O(n \cdot 2^n)O(n⋅2n) 的空间。
综合考虑,空间复杂度为 O(n⋅2n)O(n \cdot 2^n)O(n⋅2n)。
总结
通过回溯法可以有效地找到所有可能的回文子串分割。尽管时间和空间复杂度较高,但该方法对于大多数实际输入是可行的。
N皇后
按照国际象棋的规则,皇后可以攻击与之处在同一行或同一列或同一斜线上的棋子。n 皇后问题 研究的是如何将 n
个皇后放置在 n×n
的棋盘上,并且使皇后彼此之间不能相互攻击。给你一个整数 n
,返回所有不同的 n 皇后问题 的解决方案。每一种解法包含一个不同的 n 皇后问题 的棋子放置方案,该方案中 'Q'
和 '.'
分别代表了皇后和空位。
解决N皇后问题可以使用回溯法来找到所有可能的解决方案。我们需要确保每个皇后放置的位置不受其他皇后的攻击,即任何两个皇后不在同一行、同一列或同一对角线上。
code:
1 | var solveNQueens = function (n) { |
代码解释
初始化:
res
是存储所有解决方案的数组。board
是当前棋盘状态,用二维数组表示,其中.
表示空位,Q
表示皇后。
isValid
函数:- 检查在
(row, col)
位置放置皇后是否有效。 - 通过检查当前列、左上对角线和右上对角线是否有皇后来判断。
- 检查在
backtrack
函数:- 递归地尝试在每一行放置皇后。
- 如果当前行
row
等于n
,说明所有皇后都已经成功放置,将当前棋盘状态加入结果数组。 - 否则,遍历当前行的每一列,尝试放置皇后,并递归处理下一行。
**主函数
solveNQueens
**:- 初始化棋盘和结果数组。
- 调用
backtrack
函数从第0行开始递归地尝试放置皇后。 - 返回结果数组
res
。
复杂度分析
时间复杂度
最坏情况下,我们需要检查所有可能的皇后放置组合。对于每一个位置,我们最多有 (n) 个选择,因此时间复杂度为 (O(n!))。
空间复杂度
主要由递归调用栈和存储结果的空间决定。在最坏情况下,递归的深度为 (n),每层递归最多存储一个棋盘状态,因此空间复杂度为 (O(n^2))。
哈希
两数之和
给定一个整数数组 nums
和一个整数目标值 target
,请你在该数组中找出 和为目标值 target
的那 两个 整数,并返回它们的数组下标。
你可以假设每种输入只会对应一个答案,不能使用两次相同的元素,可以按任意顺序返回答案。
1 | var twoSum = function (nums, target) { |
- 返回空数组:如果遍历完数组后没有找到符合条件的两个数字,函数会返回一个空数组
[]
。这样可以避免没有返回值的情况发生。 - 时间复杂度:遍历整个数组一次,查找和存储在
Map
中的操作是常数时间,因此整体时间复杂度为 **O(n)**,其中n
是数组的长度。
字母异位词分组
给你一个字符串数组,请你将 字母异位词 组合在一起。可以按任意顺序返回结果列表。字母异位词 是由重新排列源单词的所有字母得到的一个新单词。
1 | var groupAnagrams = function(strs) { |
- Map(映射):使用
Map
来存储每一组异位词,键是经过排序的字符串,值是该组异位词组成的数组。 - 字符串排序:对于每个字符串
str
,将其拆分为字符数组,按字母顺序排序,再重新合并为字符串。排序后的字符串作为键,因为异位词的排序结果是相同的。 - 将异位词放入对应组:检查
Map
中是否已有这个排序后的字符串作为键。如果有,就把当前字符串加入到这个键对应的数组中;如果没有,就为这个键创建一个新的数组。 - 返回结果:最终返回
Map
中所有值的集合,也就是所有分组好的异位词。
缺失的第一个正数
给定一个无重复元素的整数数组nums,请你找出其中没有出现的最小的正整数
进阶: 空间复杂度 𝑂(1)O(1),时间复杂度 𝑂(𝑛)O(n)
1 | function minNumberDisappeared(nums) { |
最长连续序列
给定一个未排序的整数数组 nums ,找出数字连续的最长序列(不要求序列元素在原数组中连续)的长度,设计并实现时间复杂度为 O(n) 的算法解决此问题。
1 | var longestConsecutive = function (nums) { |
- 起点判断:
if (!curNum.has(num - 1))
用来判断num
是否是某个连续序列的起点。如果num-1
不存在于Set
中,那么num
就是连续序列的第一个数字。 - 扩展序列:一旦找到了序列的起点,就通过
while (curNum.has(cur + 1))
循环向后检查,看看下一个数字是否存在。如果存在,继续延长这个序列的长度。 - 更新最大长度:对于每一个连续序列,我们用
Math.max
更新最大长度maxLength
。
盛最多水的容器
给定一个长度为 n 的整数数组 height 。有 n 条垂线,第 i 条线的两个端点是 (i, 0) 和 (i, height[i]) 。找出其中的两条线,使得它们与 x 轴共同构成的容器可以容纳最多的水。返回容器可以储存的最大水量。
说明:你不能倾斜容器。
1 | var maxArea = function (height) { |
接雨水
1 | /** |
无重复字符的最长子串
给定一个字符串 s ,请你找出其中不含有重复字符的 最长
子串
的长度。
1 | var lengthOfLongestSubstring = function (s) { |
最长无重复子数组
1 | function maxLength(arr) { |
最大子数组和
给你一个整数数组 nums
,请你找出一个具有最大和的连续子数组(子数组最少包含一个元素),返回其最大和。
子数组:是数组中的一个连续部分。
1 | /** |
和为K的子数组
一个整数数组 nums
和一个整数 k
,请你统计并返回 该数组中和为 k
的子数组的个数 。子数组是数组中元素的连续非空序列。
解题方法:前缀和+哈希表
1 | var subarraySum = function (nums, k) { |
详细步骤
初始化:
- 创建一个哈希表
mp
来存储每个前缀和的出现次数。 - 初始化前缀和
pre
为0,并将其在哈希表中的出现次数设置为1(处理从数组开始到当前位置的子数组和为k
的情况)。
- 创建一个哈希表
遍历数组:
- 对于每个元素
i
,更新前缀和pre
。 - 检查
pre - k
是否存在于哈希表中。如果存在,说明有子数组和为k
,将出现次数加到count
上。 - 更新哈希表中
pre
的出现次数。
- 对于每个元素
返回结果:
- 返回符合条件的子数组数量
count
。
- 返回符合条件的子数组数量
时间复杂度
- 时间复杂度: O(n),其中
n
是数组的长度。由于遍历一次数组和哈希表的操作(插入和查找)都是 O(1) 的。 - 空间复杂度: O(n),因为哈希表的大小与数组的长度有关,最坏情况下需要存储所有前缀和。
除自身以外数组的乘积
一个整数数组 nums
,返回 数组 answer
,其中 answer[i]
等于 nums
中除 nums[i]
之外其余各元素的乘积 。
题目数据 保证 数组
nums
之中任意元素的全部前缀元素和后缀的乘积都在 32 位 整数范围内。请 不要使用除法,且在O(*n*)
时间复杂度内完成此题。
遍历两次,逻辑清晰
通过两次遍历数组,算法将左侧乘积和右侧乘积分别累积到结果数组中,逻辑简单且直观。以下是两次遍历的具体步骤:
- 第一次遍历:计算左侧乘积
- 初始化
left
为 1,遍历数组时,将left
的值存入res[i]
中,并更新left
为当前元素与其乘积。
- 初始化
- 第二次遍历:计算右侧乘积并计算最终结果
- 初始化
right
为 1,从右向左遍历数组时,将right
与res[i]
相乘并存回res[i]
,然后更新right
为当前元素与其乘积。
- 初始化
1 | /** |
合并区间
以数组 intervals
表示若干个区间的集合,其中单个区间为 intervals[i] = [starti, endi]
。请你合并所有重叠的区间,并返回 一个不重叠的区间数组,该数组需恰好覆盖输入中的所有区间 。
示例 1:
1 | 输入:intervals = [[1,3],[2,6],[8,10],[15,18]] |
示例 2:
1 | 输入:intervals = [[1,4],[4,5]] |
找到字符串中所有字母异位词
思想:基于滑动窗口和哈希表
滑动窗口:使用两个指针
left
和right
维护一个窗口,初始时窗口大小为目标字符串p
的长度。通过移动指针来扩展或缩小窗口,以在源字符串s
中寻找符合条件的子串。哈希表:创建一个哈希表
pMap
,用于记录目标字符串p
中每个字符的出现次数。然后,通过在遍历源字符串s
的过程中更新这个哈希表,并根据哈希表的信息来判断窗口内的子串是否符合条件。
算法的具体步骤如下:
- 首先,构建目标字符串
p
的哈希表,记录其中每个字符的出现次数。 - 然后,使用两个指针
left
和right
维护一个窗口,在源字符串s
上进行遍历。 - 在遍历过程中,每次移动右指针
right
,将右指针位置的字符加入窗口中,并更新哈希表。 - 同时,检查哈希表中记录的字符出现次数,如果在窗口内出现的字符数与目标字符串中相应字符的数目匹配,则计数器
count
减一。 - 当
count
减为 0 时,表示窗口内的字符与目标字符串中的字符匹配,此时记录窗口的起始位置。 - 继续移动左指针
left
,缩小窗口,直到窗口大小与目标字符串长度相等。 - 在移动左指针的过程中,同样需要更新哈希表,并根据哈希表中记录的字符出现次数,更新计数器
count
。 - 最后,返回所有符合条件的子串的起始位置。
通过滑动窗口和哈希表的方法,可以高效地在源字符串 s
中找到所有与目标字符串 p
是字母异位词的子串的起始索引。
1 | var findAnagrams = function (s, p) { |
滑动窗口最大值
1 | /** |
最小的K个数
解题思路
排序法:
- 先对数组进行排序,然后选择前 k 个数。
堆(优先队列)法:
- 维护一个大小为 k 的最大堆,遍历数组,将每个元素插入堆中。如果堆的大小超过 k,则移除堆顶元素。最后堆中的元素即为最小的 k 个数。
解法一–排序
1 | function GetLeastNumbers_Solution(input, k) { |
改进:直接使用 slice
方法来获取最小的 k 个数,而不需要显式地创建和填充新数组。
1 | function GetLeastNumbers_Solution(input, k) { |
解法二–堆(优先队列)法
当 k 较小且数组较大时,使用堆的性能会更好。下面是一个使用 JavaScript 中的最小堆实现的方法:
基于堆的代码
1 | class MaxHeap { |
时间复杂度
- 排序法:时间复杂度为 O(nlogn)O(n \log n)O(nlogn),其中 nnn 是数组的长度。
- 堆法:时间复杂度为 O(nlogk)O(n \log k)O(nlogk),其中 nnn 是数组的长度,kkk 是要返回的最小元素的数量。对于较大的数组和较小的 k,这种方法更高效。
寻找第K大的数
有一个整数数组,请你根据快速排序的思路,找出数组中第 k 大的数。
给定一个整数数组 a ,同时给定它的大小n和要找的 k ,请返回第 k 大的数(包括重复的元素,不用去重),保证答案存在。
要求:时间复杂度 𝑂(𝑛𝑙𝑜𝑔𝑛),空间复杂度 𝑂(1)
数据范围:0≤𝑛≤10000≤n≤1000, 1≤𝐾≤𝑛1≤K≤n,数组中每个元素满足 0≤𝑣𝑎𝑙≤100000000≤val≤10000000
1 | function findKth(a, n, K) { |
优化解法–快速选择
快速选择是一个更高效的解法,它的平均时间复杂度是 O(n)。
1 | function findKth(a, n, K) { |
选择合适的方法
- 对于小规模数据,可以直接使用排序法。
- 对于大规模数据,快速选择法更高效。
最小覆盖字串
描述:给定一个字符串 s
、一个字符串 t
。返回 s
中涵盖 t
所有字符的最小子串。如果 s
中不存在涵盖 t
所有字符的子串,则返回空字符串 ""
。
注意:
- 对于
t
中重复字符,我们寻找的子字符串中该字符数量必须不少于t
中该字符数量。 - 如果
s
中存在这样的子串,我们保证它是唯一的答案。
示例 1:
1 | 输入:s = "ADOBECODEBANC", t = "ABC" |
示例 2:
1 | 输入:s = "a", t = "a" |
示例 3:
1 | 输入: s = "a", t = "aa" |
代码
1 | var minWindow = function (s, t) { |
第二种方法
1 | var minWindow = function(s, t) { |
LRU缓存
设计LRU(最近最少使用)缓存结构,该结构在构造时确定大小,假设大小为 capacity ,操作次数是 n ,并有如下功能:
- Solution(int capacity) 以正整数作为容量 capacity 初始化 LRU 缓存
- get(key):如果关键字 key 存在于缓存中,则返回key对应的value值,否则返回 -1 。
- set(key, value):将记录(key, value)插入该结构,如果关键字 key 已经存在,则变更其数据值 value,如果不存在,则向缓存中插入该组 key-value ,如果key-value的数量超过capacity,弹出最久未使用的key-value
1 | class ListNode { |
二倍数对数组
给定一个长度为偶数的整数数组 arr
,只有对 arr
进行重组后可以满足 “对于每个 0 <= i < len(arr) / 2
,都有 arr[2 * i + 1] = 2 * arr[2 * i]
” 时,返回 true
;否则,返回 false
。
解题思路
这道题的核心在于如何将数组进行重组,使得重组后的数组满足特定条件:对于每个 0 <= i < len(arr) / 2
,都有 arr[2 * i + 1] = 2 * arr[2 * i]
。这个条件实际上要求数组的一半元素是另一半元素的两倍。
为了实现这一点,我们可以采用以下步骤:
- 排序:将数组进行排序,以便我们能轻松地找到符合条件的元素对。
- 计数:使用一个计数器来记录数组中每个元素的出现次数。
- 匹配:从最小的元素开始,尝试匹配每个元素和它的两倍。如果能够找到这样的配对,则继续,否则返回
false
。
具体步骤
- 将数组进行排序。
- 遍历排序后的数组,使用一个哈希表来记录每个元素的出现次数。
- 对于每个元素,如果当前元素已经被匹配过(计数为零),则跳过。否则,检查它的两倍是否存在且计数大于零。如果存在,则将两个元素的计数都减一。
- 如果所有元素都能找到匹配,则返回
true
;否则,返回false
。
代码实现
1 | var canReorderDoubled = function(arr) { |
复杂度分析
- 时间复杂度:$O(n \log n)$,主要由排序步骤决定。
- 空间复杂度:$O(n)$,哈希表存储每个元素的计数。
总结
通过排序和计数相结合的方法,我们能够有效地判断数组是否能重组成满足条件的形式。这种方法确保了我们能在合理的时间和空间复杂度内解决问题。
动态规划
爬楼梯
假设你正在爬楼梯。需要 n
阶你才能到达楼顶。
每次你可以爬 1
或 2
个台阶。你有多少种不同的方法可以爬到楼顶呢?
1 | var climbStairs = function (n) { |
解法2–动态规划
利用动态规划的思想
1 | var climbStairs = function(n) { |
杨辉三角
给定一个非负整数 numRows
,生成「杨辉三角」的前 numRows
行。
在「杨辉三角」中,每个数是它左上方和右上方的数的和。
1 | var generate = function (numRows) { |
杨辉三角 ||
给定一个非负索引 rowIndex
,返回「杨辉三角」的第 rowIndex
行。
在「杨辉三角」中,每个数是它左上方和右上方的数的和。
- 我们定义了一个函数
getRow
,它接受一个整数rowIndex
作为参数,并返回杨辉三角的第rowIndex
行。 - 我们初始化了一个数组
dp
,它的长度为rowIndex + 1
,并且所有的元素都被初始化为1
。我们使用这个数组来存储当前行的值。 - 我们开始一个外部循环,从
1
开始一直到rowIndex
结束。这个循环用来生成每一行的值。 - 在内部循环中,我们从当前行的倒数第二个位置开始向前遍历,直到第一个位置。这是因为在杨辉三角中,除了第一个和最后一个位置的元素为
1
,其他位置的元素是由上一行的两个相邻元素相加而得到的。 - 在内部循环中,我们更新当前行的值。对于当前行的第
j
个元素,它的值等于上一行的第j - 1
个元素和第j
个元素之和。这就是杨辉三角的定义。 - 内部循环结束后,当前行的所有元素已经更新完毕。
- 最后,我们返回生成的第
rowIndex
行的数组dp
。
通过这段代码,我们可以生成杨辉三角的第 rowIndex
行。它的时间复杂度为 O(n^2),其中 n 是 rowIndex
的值。
1 | var getRow = function (rowIndex) { |
打家劫舍
你是一个专业的小偷,计划偷窃沿街的房屋。每间房内都藏有一定的现金,影响你偷窃的唯一制约因素就是相邻的房屋装有相互连通的防盗系统,如果两间相邻的房屋在同一晚上被小偷闯入,系统会自动报警。
给定一个代表每个房屋存放金额的非负整数数组,计算你 不触动警报装置的情况下 ,一夜之内能够偷窃到的最高金额。
1 | var rob = function (nums) { |
矩阵置零
给定一个 *m* x *n*
的矩阵,如果一个元素为 0 ,则将其所在行和列的所有元素都设为 0 。请使用 原地 算法。
1 | var setZeroes = function(matrix) { |
螺旋矩阵
给你一个 m
行 n
列的矩阵 matrix
,按照 顺时针螺旋顺序 ,返回矩阵中的所有元素。
1 | var spiralOrder = function(matrix) { |
旋转图像
一个 n × n 的二维矩阵 matrix
表示一个图像。将图像顺时针旋转 90 度。必须在原地旋转图像,需要直接修改输入的二维矩阵。不能使用另一个矩阵来旋转图像。
解题思想
转置矩阵:
- 定义:矩阵的转置是将矩阵的行和列互换的操作。
- 步骤:
- 遍历矩阵的每个元素(仅遍历上三角区域,以避免重复交换),将元素
matrix[i][j]
和matrix[j][i]
互换。 - 这样可以把矩阵的行变成列,实现了对角线(从左上角到右下角)的镜像对称。
- 遍历矩阵的每个元素(仅遍历上三角区域,以避免重复交换),将元素
反转每一行:
- 定义:反转每一行意味着将行中的元素顺序反转。
- 步骤:
- 对转置后的每一行执行反转操作,这样可以完成顺时针旋转 90 度的目标。
- 反转每一行将原来的列顺序变为行顺序,从而实现了旋转。
1 | var rotate = function (matrix) { |
总结
- 转置矩阵:交换矩阵的行和列,使得矩阵沿对角线对称。
- 反转每一行:将转置后的每一行反转,使得矩阵变成顺时针旋转 90 度的状态。
这种方法的时间复杂度是 ( O(n^2) ),空间复杂度是 ( O(1) )(原地操作)。这是因为我们只使用了原始矩阵,并且操作只涉及到元素的交换和行的反转。
搜索二维矩阵 ||
编写一个高效的算法来搜索 *m* x *n*
矩阵 matrix
中的一个目标值 target
。该矩阵具有以下特性:
- 每行的元素从左到右升序排列。
- 每列的元素从上到下升序排列。
这道题的解题思想是利用矩阵的排序性质进行高效搜索。具体来说,每行的元素从左到右升序排列,每列的元素从上到下升序排列。这些性质允许我们从矩阵的某个角落开始,通过逐步排除不可能的区域来缩小搜索范围。我们可以选择从矩阵的右上角(或者左下角)开始搜索,因为这样我们可以根据当前元素和目标值的比较结果决定移动的方向,从而高效地进行搜索。
具体步骤
选择起始点:从矩阵的右上角开始搜索。右上角的元素是当前行中的最大值,同时也是当前列中的最小值。
比较目标值与当前元素
:
- 如果当前元素等于目标值,返回
true
。 - 如果当前元素小于目标值,说明目标值可能在当前行的下方,因此向下移动一行。
- 如果当前元素大于目标值,说明目标值可能在当前列的左侧,因此向左移动一列。
- 如果当前元素等于目标值,返回
更新搜索范围:根据比较结果,更新行或列的索引,继续搜索,直到找到目标值或搜索范围超出矩阵的边界。
返回结果:如果在搜索过程中找到目标值,返回
true
;如果搜索完成后仍未找到目标值,返回false
。
1 | var searchMatrix = function (matrix, target) { |
复杂度分析
- 时间复杂度:$O(m + n)$,其中 $m$ 是矩阵的行数,$n$ 是矩阵的列数。在最坏的情况下,我们可能会从右上角走到左下角,遍历矩阵中的所有行和列。
- 空间复杂度:$O(1)$,只使用了常数级别的额外空间。
总结
这种方法充分利用了矩阵的排序性质,从右上角开始搜索,通过比较当前元素和目标值来决定移动方向,逐步排除不可能的区域,从而高效地找到目标值。
分割等和子集
给你一个 只包含正整数 的 非空 数组 nums
。请你判断是否可以将这个数组分割成两个子集,使得两个子集的元素和相等。
code:
1 | function canPartition(nums) { |
解释:
- 计算总和:首先,使用
reduce
方法计算数组nums
的总和totalSum
。 - 检查总和是否为奇数:如果
totalSum
是奇数,则不能将数组分割成两个和相等的子集,直接返回false
。 - 初始化动态规划数组:创建一个布尔数组
dp
,长度为target + 1
,并初始化为false
。dp[0]
设为true
,表示和为 0 的子集是存在的(空集)。 - 动态规划状态转移:遍历数组
nums
中的每个元素num
,从大到小更新dp
数组。对于每个num
,如果dp[j - num]
为true
,则设置dp[j]
为true
。 - 返回结果:最终返回
dp[target]
,表示是否存在和为target
的子集。
最长有效括号
给你一个只包含 '('
和 ')'
的字符串,找出最长有效(格式正确且连续)括号子串的长度。
要找出只包含 ‘(‘ 和 ‘)’ 的字符串中最长有效括号子串的长度,可以使用动态规划或栈的方法。这里先介绍使用栈的方法。
方法一:使用栈
栈可以用来追踪括号的位置,并帮助我们确定有效括号子串的长度。
步骤:
- 初始化一个栈,栈底放一个初始值
-1
(表示未匹配的右括号的索引)。 - 遍历字符串:
- 如果遇到左括号
'('
,将它的索引压入栈中。 - 如果遇到右括号
')'
:- 先弹出栈顶元素,表示匹配了一个左括号。
- 如果栈为空,将当前索引压入栈中(表示新的未匹配的右括号的索引)。
- 如果栈不为空,计算当前右括号的索引与栈顶元素的索引的差值,这个差值就是当前有效括号子串的长度,并更新最大长度。
- 如果遇到左括号
code:
1 | function longestValidParentheses(s) { |
方法二:动态规划
动态规划方法需要用一个数组 dp
来记录以每个字符为结尾的最长有效括号子串的长度。
步骤:
- 初始化一个
dp
数组,所有元素初始化为 0。 - 遍历字符串:
- 如果当前字符是右括号
')'
并且前一个字符是左括号'('
,则更新dp
数组。 - 如果当前字符是右括号
')'
并且前一个字符是右括号')'
,则检查是否能形成一个更长的有效括号子串,并更新dp
数组。
- 如果当前字符是右括号
- 最后,返回
dp
数组中的最大值。
code:
1 | function longestValidParentheses(s) { |
这两种方法都可以有效地找到最长有效括号子串的长度,可以根据具体需求选择适合的方法。
多维动态规划
不同路径
一个机器人位于一个 m x n
网格的左上角 (起始点在下图中标记为 “Start” )。机器人每次只能向下或者向右移动一步。机器人试图达到网格的右下角(在下图中标记为 “Finish” )。问总共有多少条不同的路径?
这个问题可以用动态规划来解决。机器人从左上角走到右下角,每次只能向下或向右移动一步,问总共有多少种不同的路径。
动态规划解法
我们可以定义一个二维数组 dp
,其中 dp[i][j]
表示从起始点 (0, 0)
到达网格 (i, j)
的不同路径数目。
初始化:
- 起始点
(0, 0)
到达自身的路径数目为1
,因此dp[0][0] = 1
。
状态转移:
对于每个位置 (i, j)
,可以从上方 (i-1, j)
或左侧 (i, j-1)
到达:
- 如果当前位置在第一行
i == 0
,只能从左侧到达,即dp[0][j] = dp[0][j-1]
。 - 如果当前位置在第一列
j == 0
,只能从上方到达,即dp[i][0] = dp[i-1][0]
。 - 否则,路径数目为上方和左侧的路径数目之和,即
dp[i][j] = dp[i-1][j] + dp[i][j-1]
。
最终结果:
目标是求解 dp[m-1][n-1]
,即到达右下角的不同路径数目。
实现代码:
1 | function uniquePaths(m, n) { |
解释
- 我们首先初始化一个
dp
数组,大小为m x n
,所有元素初始化为0
。 - 起始点
(0, 0)
的路径数目为1
。 - 使用双重循环遍历整个网格,更新
dp[i][j]
的值,根据上方和左侧的路径数目更新当前位置的路径数目。 - 最后返回
dp[m-1][n-1]
,即到达右下角的路径数目。
这样的动态规划解法时间复杂度为 O(m * n)
,空间复杂度为 O(m * n)
,适用于给定的网格大小。
最小路径和
给定一个包含非负整数的 *m* x *n*
网格 grid
,请找出一条从左上角到右下角的路径,使得路径上的数字总和为最小。
说明:每次只能向下或者向右移动一步。
解题思想
动态规划(Dynamic Programming):
- 动态规划是一种将复杂问题分解成更小的子问题,并存储每个子问题的结果以避免重复计算的方法。
- 在这个问题中,我们需要找到从左上角到右下角的路径,使得路径上的数字总和最小。
定义状态:
- 用二维数组
dp
存储到达每个格子(i, j)
的最小路径和,其中dp[i][j]
表示到达(i, j)
的最小路径和。
- 用二维数组
状态转移方程:
- 对于起点
(0, 0)
,dp[0][0] = grid[0][0]
。 - 对于第一行的任意格子
(0, j)
,只能从左侧到达,dp[0][j] = dp[0][j - 1] + grid[0][j]
。 - 对于第一列的任意格子
(i, 0)
,只能从上方到达,dp[i][0] = dp[i - 1][0] + grid[i][0]
。 - 对于其他格子
(i, j)
,可以从上方或左侧到达,dp[i][j] = Math.min(dp[i - 1][j], dp[i][j - 1]) + grid[i][j]
。
- 对于起点
初始条件和边界条件:
- 初始条件是起点的值:
dp[0][0] = grid[0][0]
。 - 边界条件是第一行和第一列的处理。
- 初始条件是起点的值:
计算顺序:
- 从左上角开始,逐行逐列计算,依次填充
dp
数组。
- 从左上角开始,逐行逐列计算,依次填充
返回结果:
- 最终结果是
dp[m - 1][n - 1]
,即到达右下角的最小路径和。
- 最终结果是
1 | var minPathSum = function (grid) { |
时间和空间复杂度分析
时间复杂度:
- 遍历整个
m x n
的网格,每个格子都进行常数时间的计算。 - 总的时间复杂度为
O(m * n)
。
- 遍历整个
空间复杂度:
- 使用了一个大小为
m x n
的二维数组dp
来存储中间结果。 - 总的空间复杂度为
O(m * n)
。
- 使用了一个大小为
最长回文子串
给你一个字符串 s
,找到 s
中最长的 回文子串。
题目描述
给定一个字符串 s
,找到 s
中最长的回文子串。你可以假设 s
的最大长度为 1000。
解题思想
这里我们使用动态规划的方法来解决这个问题。我们定义一个二维数组 dp
,其中 dp[i][j]
表示字符串 s
从第 i
个字符到第 j
个字符(即 s[i:j+1]
)是否是回文串。
动态规划的状态转移方程:
- 如果
s[i] == s[j]
并且j - i <= 2
(即两个字符相同且之间的字符数小于等于1,例如”aa”或”aba”),则dp[i][j] = true
。 - 如果
s[i] == s[j]
并且dp[i + 1][j - 1] == true
,则dp[i][j] = true
。 - 其他情况下,
dp[i][j] = false
。
我们需要遍历所有的子串,找出最长的回文子串。
复杂度分析:
- 时间复杂度:O(n^2)
- 空间复杂度:O(n^2)
code:
1 | var longestPalindrome = function (s) { |
代码解释
初始化:
dp
数组表示s[i:j+1]
是否为回文。maxLength
保存当前最长回文子串的长度。start
保存当前最长回文子串的起始位置。
单字符回文初始化:
- 所有单个字符都是回文,初始化
dp[i][i] = true
。
- 所有单个字符都是回文,初始化
状态转移:
- 双重循环遍历所有子串。
- 如果
s[start] == s[end]
并且end - start <= 2
或dp[start + 1][end - 1]
为真,则更新dp[start][end]
。 - 如果当前子串为回文且长度超过
maxLength
,更新maxLength
和start
。
返回结果:
- 从
start
开始,长度为maxLength
的子串就是最长回文子串。
- 从
这种方法时间复杂度和空间复杂度都是 O(n^2),在可接受范围内,可以在大多数情况下有效解决问题。
最长公共子序列
给定两个字符串 text1
和 text2
,返回这两个字符串的最长 公共子序列 的长度。如果不存在 公共子序列 ,返回 0
。一个字符串的 子序列 是指这样一个新的字符串:它是由原字符串在不改变字符的相对顺序的情况下删除某些字符(也可以不删除任何字符)后组成的新字符串。
例如,
"ace"
是"abcde"
的子序列,但"aec"
不是"abcde"
的子序列。
两个字符串的 公共子序列 是这两个字符串所共同拥有的子序列。
当使用JavaScript解决最长公共子序列(LCS)的问题时,可以采用类似动态规划的方法来实现。以下是具体的解题思路、代码实现以及复杂度分析:
解题思路
动态规划方法:
定义状态:我们定义
dp[i][j]
表示text1
的前i
个字符和text2
的前j
个字符的最长公共子序列的长度。状态转移方程:
- 如果
text1[i-1] === text2[j-1]
,则dp[i][j] = dp[i-1][j-1] + 1
。即当前字符相同时,最长公共子序列长度加一。 - 否则,
dp[i][j] = Math.max(dp[i-1][j], dp[i][j-1])
。当前字符不同时,取前一个状态的最大值。
- 如果
边界条件:初始化
dp
数组,确保空字符串的情况下最长公共子序列长度为 0。求解目标:
dp[m][n]
即为text1
和text2
的最长公共子序列的长度,其中m
和n
分别是text1
和text2
的长度。
code:
1 | var longestCommonSubsequence = function (text1, text2) { |
逐行代码分析
function longestCommonSubsequence(text1, text2) {
:定义函数longestCommonSubsequence
,接收两个字符串text1
和text2
。const m = text1.length;
和const n = text2.length;
:获取text1
和text2
的长度。const dp = Array.from(Array(m + 1), () => Array(n + 1).fill(0));
:创建一个二维数组dp
,其大小为(m+1) x (n+1)
,并初始化为 0。for (let i = 1; i <= m; i++) {
和for (let j = 1; j <= n; j++) {
:双重循环遍历text1
和text2
的所有字符。if (text1[i - 1] === text2[j - 1]) {
:判断当前字符是否相等。dp[i][j] = dp[i - 1][j - 1] + 1;
:如果相等,则更新dp[i][j]
为左上角元素加一,即最长公共子序列长度加一。dp[i][j] = Math.max(dp[i - 1][j], dp[i][j - 1]);
:如果不相等,则取左边或上边的较大值,保证dp[i][j]
为当前的最长公共子序列长度。return dp[m][n];
:返回dp
数组的最后一个元素,即text1
和text2
的最长公共子序列的长度。
时间复杂度和空间复杂度分析
时间复杂度:双重循环遍历了
text1
和text2
,因此时间复杂度为O(m * n)
,其中m
和n
分别是text1
和text2
的长度。空间复杂度:使用了
(m+1) x (n+1)
大小的二维数组dp
,因此空间复杂度为O(m * n)
。
这种动态规划方法在JavaScript中同样有效地解决了求解两个字符串最长公共子序列长度的问题,具有较高的时间和空间效率。
编辑距离
给你两个单词 word1
和 word2
, 请返回将 word1
转换成 word2
所使用的最少操作数 。
你可以对一个单词进行如下三种操作:
- 插入一个字符
- 删除一个字符
- 替换一个字符
要解决将 word1
转换为 word2
的最少操作数问题,我们可以使用动态规划的方法。这种方法通常适用于解决字符串之间的编辑距离问题,可以进行插入、删除和替换操作。
解题思路
定义状态:
- 定义
dp[i][j]
表示将word1
的前i
个字符转换为word2
的前j
个字符所需的最少操作数。
- 定义
状态转移方程:
- 如果
word1[i-1] === word2[j-1]
,即当前字符相同,则dp[i][j] = dp[i-1][j-1]
,不需要额外操作。 - 否则,需要考虑三种操作情况:
- 插入:
dp[i][j] = dp[i][j-1] + 1
,即在word1
的前i
个字符后插入一个字符,使得与word2
的前j
个字符相同。 - 删除:
dp[i][j] = dp[i-1][j] + 1
,即删除word1
的第i
个字符,使得剩余的前i-1
个字符与word2
的前j
个字符相同。 - 替换:
dp[i][j] = dp[i-1][j-1] + 1
,即将word1
的第i
个字符替换为word2
的第j
个字符。
- 插入:
- 如果
初始化:
dp[0][0] = 0
,表示两个空字符串之间的编辑距离为 0。dp[i][0] = i
,表示将word1
的前i
个字符转换为空字符串所需的操作数。dp[0][j] = j
,表示将空字符串转换为word2
的前j
个字符所需的操作数。
求解目标:
- 最终结果存储在
dp[m][n]
中,其中m
和n
分别为word1
和word2
的长度。
- 最终结果存储在
1 | var minDistance = function(word1, word2) { |
- 在
minDistance
函数中,我们首先计算出word1
和word2
的长度m
和n
。 - 创建二维数组
dp
,并初始化边界条件,处理空字符串的情况。 - 使用双重循环填充
dp
数组,根据字符是否相同决定采取插入、删除或替换操作,更新dp[i][j]
的值。 - 最后返回
dp[m][n]
,即将word1
转换为word2
所需的最小操作数。
这种方法保证了在 O(m * n)
的时间复杂度内完成计算,其中 m
和 n
分别是 word1
和 word2
的长度。
贪心算法
买卖股票的最佳时机
给定一个数组 prices
,它的第 i
个元素 prices[i]
表示一支给定股票第 i
天的价格。
你只能选择 某一天 买入这只股票,并选择在 未来的某一个不同的日子 卖出该股票。设计一个算法来计算你所能获取的最大利润。返回你可以从这笔交易中获取的最大利润。如果你不能获取任何利润,返回 0
。
- 寻找最低价格:遍历价格数组,保持一个变量记录到当前为止的最低价格。
- 计算利润:在遍历时,计算如果在当前价格卖出股票,能获得的利润,并更新最大利润。
1 | var maxProfit = function(prices) { |
- 时间复杂度:O(n),其中
n
是数组prices
的长度。我们只需要遍历一次价格数组。 - 空间复杂度:O(1),只用了常数空间来存储最低价格和最大利润。
时间复杂度和空间复杂度
- 时间复杂度:O(n)
- 这里 n 是数组
prices
的长度。因为我们只需遍历数组一次,所以时间复杂度是线性的,即 O(n)。
- 这里 n 是数组
- 空间复杂度:O(1)
- 只使用了两个额外的变量
profit
和money
,所以空间复杂度是常数级别的,即 O(1)。
- 只使用了两个额外的变量
跳跃游戏
给你一个非负整数数组 nums
,你最初位于数组的 第一个下标 。数组中的每个元素代表你在该位置可以跳跃的最大长度。判断你是否能够到达最后一个下标,如果可以,返回 true
;否则,返回 false
。
这个问题可以使用贪心算法来解决。贪心算法的思想是在每一步都尽量跳得更远,从而在遍历数组的过程中不断更新最远可以到达的位置。具体来说,我们维护一个变量 maxReach
,表示当前可以到达的最远位置。如果在遍历过程中某一个位置超出了 maxReach
,那么说明无法到达最后一个下标,否则最终 maxReach
可以覆盖或超过最后一个下标。
解题思路
- 初始化
maxReach
为 0,表示最远可以到达的位置。 - 遍历数组中的每一个位置
i
:- 如果当前位置
i
超出了maxReach
,返回false
。 - 更新
maxReach
为i + nums[i]
和maxReach
中的较大值。
- 如果当前位置
- 遍历结束后,如果
maxReach
大于或等于最后一个下标,返回true
,否则返回false
。
1 | var canJump = function(nums) { |
复杂度分析
时间复杂度:O(n)
- 需要遍历数组一次,其中 n 是数组
nums
的长度。
- 需要遍历数组一次,其中 n 是数组
空间复杂度:O(1)
- 只使用了一个额外变量
maxReach
,所以空间复杂度是常数级别的,即 O(1)。
- 只使用了一个额外变量
跳跃游戏||
给定一个长度为 n
的 0 索引整数数组 nums
。初始位置为 nums[0]
。
每个元素 nums[i]
表示从索引 i
向前跳转的最大长度。换句话说,如果你在 nums[i]
处,你可以跳转到任意 nums[i + j]
处:
0 <= j <= nums[i]
i + j < n
返回到达 nums[n - 1]
的最小跳跃次数。生成的测试用例可以到达 nums[n - 1]
。
可以使用贪心算法来解决这个问题,通过维护一个范围内可以到达的最远位置,以及在当前范围内跳跃的次数来解决。
- 维护三个变量:
jumps
表示总跳跃次数。currentEnd
表示当前跳跃可以到达的最远位置。farthest
表示从当前跳跃到达的所有位置中可以到达的最远位置。
- 遍历数组中的每一个位置
i
:- 更新
farthest
为max(farthest, i + nums[i])
。 - 如果当前位置
i
达到了currentEnd
,则更新jumps
并将currentEnd
更新为farthest
。
- 更新
- 返回
jumps
。
1 | var jump = function(nums) { |
- 时间复杂度:O(n)
- 只需遍历数组一次,其中 n 是数组
nums
的长度。
- 只需遍历数组一次,其中 n 是数组
- 空间复杂度:O(1)
- 只使用了常数个额外变量。
对于 nums = [2, 3, 1, 1, 4]
:
- 初始化
jumps = 0
,currentEnd = 0
,farthest = 0
。 - 遍历数组:
i = 0
:farthest = max(0, 0 + 2) = 2
,currentEnd = 0
,更新jumps = 1
,currentEnd = 2
。i = 1
:farthest = max(2, 1 + 3) = 4
,currentEnd = 2
。i = 2
:farthest = max(4, 2 + 1) = 4
,currentEnd = 2
,更新jumps = 2
,currentEnd = 4
。
- 返回
jumps = 2
。
划分字母区间
给你一个字符串 s
。我们要把这个字符串划分为尽可能多的片段,同一字母最多出现在一个片段中。注意,划分结果需要满足:将所有划分结果按顺序连接,得到的字符串仍然是 s
。返回一个表示每个字符串片段的长度的列表。
要将字符串 s
划分为尽可能多的片段,同一字母最多出现在一个片段中,可以使用贪心算法和哈希表来解决这个问题。具体步骤如下:
解题思路
- 记录每个字符的最后出现位置:使用一个哈希表记录字符串
s
中每个字符最后一次出现的下标。 - 遍历字符串并划分片段:使用两个指针
start
和end
,其中start
表示当前片段的开始位置,end
表示当前片段中字符的最远出现位置。- 遍历字符串
s
,更新end
为当前字符的最后出现位置。 - 当遍历到的位置
i
等于end
时,说明当前片段可以结束,记录片段长度并更新start
为下一个位置。
- 遍历字符串
代码实现
1 | var partitionLabels = function(s) { |
复杂度分析
时间复杂度:O(n)
- 其中 n 是字符串
s
的长度。需要遍历字符串两次,一次记录最后出现的位置,一次进行划分。
- 其中 n 是字符串
空间复杂度:O(1)
- 哈希表的空间复杂度是 O(1),因为字符集大小是固定的(假设只有小写字母)。
示例解释
对于 s = "ababcbacadefegdehijhklij"
:
记录每个字符最后出现的位置:
1
{a: 8, b: 5, c: 7, d: 14, e: 15, f: 11, g: 13, h: 19, i: 22, j: 23, k: 20, l: 21}
遍历字符串并划分片段:
i = 0
到8
,最后一个字符是a
,所以第一个片段是"ababcbaca"
,长度是9
。i = 9
到15
,最后一个字符是e
,所以第二个片段是"defegde"
,长度是7
。i = 16
到23
,最后一个字符是j
,所以第三个片段是"hijhklij"
,长度是8
。
最终结果是 [9, 7, 8]
。
零钱兑换
给你一个整数数组 coins
,表示不同面额的硬币;以及一个整数 amount
,表示总金额。计算并返回可以凑成总金额所需的 最少的硬币个数 。如果没有任何一种硬币组合能组成总金额,返回 -1
。你可以认为每种硬币的数量是无限的。
解题思想
该问题可以使用动态规划来解决。动态规划的基本思想是通过保存子问题的解来加速求解过程,从而避免重复计算,通常适用于具有重叠子问题和最优子结构性质的问题。
具体步骤如下:
定义状态:使用
dp[i]
表示凑成金额i
所需的最少硬币数。状态转移方程:对于每个金额
i
,遍历所有硬币面额coin
,如果可以用当前硬币coin
凑成金额i
,则更新dp[i]
:1
dp[i] = Math.min(dp[i], dp[i - coin] + 1);
其中
dp[i - coin] + 1
表示使用当前硬币coin
后的硬币数量,dp[i]
则是取当前的最小值。初始化:初始化
dp[0] = 0
,表示凑成金额0
不需要任何硬币。遍历计算:从金额
1
到amount
,依次计算每个金额的最少硬币数,直到计算出dp[amount]
。结果返回:如果
dp[amount]
的值为初始值(例如amount + 1
),则表示无法凑成金额amount
,返回-1
;否则返回dp[amount]
。
复杂度分析
- 时间复杂度:O(amount * n),其中
amount
是目标金额,n
是硬币的种类数。内外两层循环的时间复杂度均为O(amount * n)
。 - 空间复杂度:O(amount),使用了大小为
amount + 1
的dp
数组来存储每个金额的最少硬币数。
1 | var coinChange = function (coins, amount) { |
输入:coins = [1, 2, 5], amount = 11
:展示了输入的硬币面额数组和目标金额。输出:3
:展示了函数coinChange
返回的最少硬币个数。对于coins = [1, 2, 5]
和amount = 11
,可以用5 + 5 + 1
三个硬币凑成11
,所以返回3
。
单词拆分
给你一个字符串 s
和一个字符串列表 wordDict
作为字典。如果可以利用字典中出现的一个或多个单词拼接出 s
则返回 true
。
注意:不要求字典中出现的单词全部都使用,并且字典中的单词可以重复使用。
你可以使用动态规划来解决这个问题。下面是基于动态规划的解法:
解题思路
定义状态:
- 定义一个布尔数组
dp
,其中dp[i]
表示字符串s
的前i
个字符能否被字典wordDict
中的单词拼接而成。
- 定义一个布尔数组
状态转移:
- 对于每个位置
i
,检查所有以j
结尾的子串(其中0 <= j < i
),如果dp[j]
为true
,且子串s[j:i]
出现在wordDict
中,则dp[i]
也设为true
。
- 对于每个位置
初始化:
dp[0]
初始化为true
,表示空串可以被拼接出。
计算结果:
- 最终返回
dp[n]
,其中n
是字符串s
的长度。如果dp[n]
为true
,则说明可以用字典中的单词拼接出整个字符串s
。
- 最终返回
复杂度分析
- 时间复杂度:O(n^2),其中
n
是字符串s
的长度。外层循环遍历字符串s
的每个字符,内层循环遍历每个可能的前缀子串。 - 空间复杂度:O(n),需要额外的空间存储
dp
数组。
code:
1 | var wordBreak = function(s, wordDict) { |
示例解释
- 给定字符串
s = "leetcode"
和字典wordDict = ["leet", "code"]
。 - 我们可以将字符串拆分成 “leet code”,其中 “leet” 和 “code” 分别出现在
wordDict
中。 - 因此,返回
true
表示可以利用字典中的单词拼接出字符串s
。
这种方法利用动态规划的思想,通过逐步构建 dp
数组来判断是否能够用字典中的单词拼接出目标字符串。
最长递增子序列
给你一个整数数组 nums
,找到其中最长严格递增子序列的长度。子序列 是由数组派生而来的序列,删除(或不删除)数组中的元素而不改变其余元素的顺序。例如,[3,6,2,7]
是数组 [0,3,1,6,2,2,7]
的子序列。
找到最长严格递增子序列的长度可以使用动态规划(DP)的方法。动态规划的基本思想是通过记录每个位置的最长递增子序列长度来逐步构建最终的结果。
解题思路
定义状态:
- 使用一个数组
dp
,其中dp[i]
表示以nums[i]
结尾的最长严格递增子序列的长度。
- 使用一个数组
状态转移:
- 对于每个位置
i
,遍历i
之前的所有位置j
,如果nums[i] > nums[j]
,则更新dp[i]
:dp[i] = Math.max(dp[i], dp[j] + 1)
- 对于每个位置
初始化:
dp
数组的每个位置初始化为1
,因为每个元素都可以单独成为一个子序列。
结果计算:
- 最终结果是
dp
数组中的最大值,即dp
数组中所有值的最大值。
- 最终结果是
复杂度分析
- 时间复杂度:O(n^2),其中
n
是数组nums
的长度。两层循环分别遍历数组中的每个元素。 - 空间复杂度:O(n),需要额外的空间存储
dp
数组。
code:
1 | var lengthOfLIS = function (nums) { |
示例解释
- 给定数组
nums = [10, 9, 2, 5, 3, 7, 101, 18]
。 - 最长严格递增子序列为
[2, 3, 7, 101]
,其长度为4
。
通过动态规划的方法,我们可以有效地找到最长严格递增子序列的长度。每次更新 dp
数组时,我们记录以每个元素结尾的最长递增子序列的长度,最终取最大值作为结果。
乘积最大子数组
给你一个整数数组 nums
,请你找出数组中乘积最大的非空连续子数组(该子数组中至少包含一个数字),并返回该子数组所对应的乘积。测试用例的答案是一个 32-位 整数。
要找到数组中乘积最大的非空连续子数组,我们可以使用动态规划的思想。具体来说,我们需要在遍历数组时,记录到当前元素为止的最大乘积和最小乘积,因为负数的乘积可能会使最小值变成最大值。
解题思路
定义状态:
- 使用
maxProduct
记录到当前元素为止的最大乘积。 - 使用
minProduct
记录到当前元素为止的最小乘积(因为负数乘积可能会导致最小值变成最大值)。 - 使用
result
记录最终的最大乘积。
- 使用
状态转移:
- 对于每个元素
nums[i]
,更新maxProduct
和minProduct
:1
2
3tempMax = maxProduct;
maxProduct = Math.max(nums[i], maxProduct * nums[i], minProduct * nums[i]);
minProduct = Math.min(nums[i], tempMax * nums[i], minProduct * nums[i]); - 更新
result
:1
result = Math.max(result, maxProduct);
- 对于每个元素
初始化:
maxProduct
、minProduct
和result
均初始化为数组的第一个元素nums[0]
。
结果计算:
- 最终返回
result
。
- 最终返回
复杂度分析
- 时间复杂度:O(n),其中
n
是数组nums
的长度。只需一次遍历。 - 空间复杂度:O(1),只使用了常数级别的额外空间。
代码实现
下面是使用动态规划实现的 JavaScript 代码:
1 | var maxProduct = function(nums) { |
示例解释
- 给定数组
nums = [2, 3, -2, 4]
。 - 乘积最大的非空连续子数组为
[2, 3]
,其乘积为6
。
通过动态规划的方法,我们可以有效地找到乘积最大的非空连续子数组。每次更新 maxProduct
和 minProduct
时,考虑当前元素、当前元素与之前 maxProduct
的乘积、当前元素与之前 minProduct
的乘积,然后更新结果。最终结果即为乘积最大的子数组的乘积。
图论
相关的算法:
1. 深度优先搜索(DFS)
题目:给定一个无向图,写一个算法输出图中所有连通分量。
提示:可以使用深度优先搜索(DFS)来找到所有连通分量。
2. 广度优先搜索(BFS)
题目:给定一个无向图和一个起始节点,写一个算法输出从起始节点到所有其他节点的最短路径。
提示:可以使用广度优先搜索(BFS)来找到从起始节点到所有其他节点的最短路径。
3. 最短路径算法
题目:给定一个带权有向图和一个起始节点,写一个算法输出从起始节点到所有其他节点的最短路径。
提示:可以使用Dijkstra算法来解决这个问题。
4. 最小生成树
题目:给定一个带权无向图,写一个算法输出图的最小生成树。
提示:可以使用Kruskal或Prim算法来找到最小生成树。
5. 拓扑排序
题目:给定一个有向无环图(DAG),写一个算法输出图的拓扑排序。
提示:可以使用Kahn算法或深度优先搜索(DFS)来找到拓扑排序。
6. 二分图检测
题目:给定一个无向图,写一个算法判断图是否是二分图。
提示:可以使用染色法(两种颜色)来检测二分图。
7. 欧拉回路与欧拉路径
题目:给定一个无向图,写一个算法判断图中是否存在欧拉回路或欧拉路径,并输出该路径(如果存在)。
提示:可以使用Hierholzer算法来找到欧拉回路或欧拉路径。
8. 强连通分量
题目:给定一个有向图,写一个算法输出图中的所有强连通分量。
提示:可以使用Tarjan算法或Kosaraju算法来找到强连通分量。
9. Bellman-Ford算法
题目:给定一个带权有向图和一个起始节点,写一个算法输出从起始节点到所有其他节点的最短路径,允许存在负权边。
提示:可以使用Bellman-Ford算法来解决这个问题。
10. Floyd-Warshall算法
题目:给定一个带权有向图,写一个算法输出任意两点间的最短路径。
提示:可以使用Floyd-Warshall算法来找到任意两点间的最短路径。
岛屿数量
给你一个由 '1'
(陆地)和 '0'
(水)组成的的二维网格,请你计算网格中岛屿的数量。岛屿总是被水包围,并且每座岛屿只能由水平方向和/或竖直方向上相邻的陆地连接形成。此外,你可以假设该网格的四条边均被水包围。
找出并计算岛屿的数量。对于给定的输入,输出应该是1,因为所有的’1’相连在一起形成一个岛屿。
我们将使用深度优先搜索(DFS)来遍历网格,找到并标记所有相连的’1’,每当我们发现一个新的’1’时,就意味着我们找到了一个新的岛屿。
具体步骤
- 遍历网格:遍历每一个元素,如果遇到’1’,就开始进行DFS遍历。
- DFS遍历:在DFS过程中,将当前’1’变为’0’,并递归遍历其相邻的’1’,直到所有相连的’1’都被标记为’0’。
- 计数岛屿:每次发现一个新的’1’并开始DFS时,计数器加一。
1 | var numIslands = function(grid) { |
解释
- 初始化与边界检查:首先检查网格是否为空或长度为零。如果是,则直接返回0。
- 定义DFS函数:DFS函数用于将当前格子及其相邻的所有’1’标记为’0’。通过递归调用,实现对相邻格子的遍历。
- 主循环:遍历整个网格的每个元素。
- 如果当前元素是’1’,则意味着发现一个新的岛屿,计数器加一。
- 调用DFS函数,从当前’1’开始,将与之相连的所有’1’都标记为’0’,避免重复计数。
- 输出结果:主循环结束后,计数器的值即为岛屿的数量。
腐烂的橘子
在给定的 m x n
网格 grid
中,每个单元格可以有以下三个值之一:
- 值
0
代表空单元格; - 值
1
代表新鲜橘子; - 值
2
代表腐烂的橘子。
每分钟,腐烂的橘子 周围 4 个方向上相邻 的新鲜橘子都会腐烂。返回 直到单元格中没有新鲜橘子为止所必须经过的最小分钟数。如果不可能,返回 -1
。
你的目标是实现一个计算腐烂橘子所需时间的算法,这里是题目的描述以及实现的正确方式。
题目描述
在一个 grid
矩阵中,每个单元格可以有以下三个值之一:
- 0 表示这个单元格是空的。
- 1 表示这个单元格有一个新鲜的橘子。
- 2 表示这个单元格有一个腐烂的橘子。
每分钟,任何与腐烂橘子相邻(4个方向:上、下、左、右)的新鲜橘子都会变成腐烂橘子。
编写一个函数,来计算直到没有新鲜橘子存在所需的最小分钟数。如果无法使所有橘子腐烂,则返回 -1。
解题思路
- 问题理解:
- 给定一个二维网格,其中
1
表示新鲜橘子,2
表示腐烂橘子,0
表示空格。新鲜橘子只能被水平或垂直相邻的腐烂橘子腐烂。求使得所有新鲜橘子腐烂所需的最少分钟数。如果无法使所有新鲜橘子腐烂,则返回-1
。
- 给定一个二维网格,其中
- 解题思路:
- 使用广度优先搜索(BFS)来模拟腐烂橘子的传播过程。首先将所有初始的腐烂橘子加入队列,然后不断从队列中取出腐烂橘子,并将其相邻的新鲜橘子变为腐烂,直到队列为空。
- 使用一个计数器
minutes
来记录经过的时间步长,即腐烂的分钟数。 - 使用一个
fresh
变量来记录当前还未腐烂的新鲜橘子数量,如果 BFS 结束后fresh
不为0
,说明有新鲜橘子无法腐烂,返回-1
;否则返回minutes - 1
,即腐烂橘子传播的总时间。
使用广度优先搜索(BFS)来解决这个问题,具体步骤如下:
- 将所有腐烂橘子的位置加入队列,并记录新鲜橘子的数量。
- 从队列中依次取出腐烂橘子的位置,并将其四个方向相邻的新鲜橘子变为腐烂,并将这些新变腐烂的橘子位置加入队列。
- 每一轮处理表示一分钟过去了。
- 如果处理完所有腐烂橘子后仍然有新鲜橘子未被腐烂,则返回 -1。
code:
1 | var orangesRotting = function(grid) { |
解释
- 初始化:我们首先遍历整个网格,将所有腐烂的橘子位置加入队列,同时记录新鲜橘子的数量。
- BFS遍历:使用队列进行广度优先搜索,每轮遍历将相邻的新鲜橘子变为腐烂,并记录所需的时间(分钟数)。
- 结果计算:如果所有新鲜橘子都变为腐烂,则返回所需时间;否则返回 -1,表示无法使所有橘子腐烂。
这样我们可以有效地计算出使所有橘子腐烂所需的最小时间。
复杂度分析
- 时间复杂度:假设网格大小为
m x n
。- 初始化队列和统计新鲜橘子的时间复杂度为
O(m * n)
。 - BFS 的时间复杂度为
O(m * n)
,因为每个节点(橘子)最多访问一次。 - 总体时间复杂度为
O(m * n)
。
- 初始化队列和统计新鲜橘子的时间复杂度为
- 空间复杂度:使用了队列来存储腐烂橘子的坐标,最坏情况下空间复杂度为
O(m * n)
,用于存储整个网格。
课程表
你这个学期必须选修 numCourses
门课程,记为 0
到 numCourses - 1
。在选修某些课程之前需要一些先修课程。 先修课程按数组 prerequisites
给出,其中 prerequisites[i] = [ai, bi]
,表示如果要学习课程 ai
则 必须 先学习课程 bi
。
- 例如,先修课程对
[0, 1]
表示:想要学习课程0
,你需要先完成课程1
。
请你判断是否可能完成所有课程的学习?如果可以,返回 true
;否则,返回 false
。
解题思想
要解决这个问题,我们可以将其转换为图论中的“检测有向图中是否存在环”的问题。如果课程的先修关系形成了一个有向无环图(DAG),那么我们可以完成所有课程;否则,如果存在环,我们就无法完成所有课程。
我们可以使用拓扑排序来检测有向图中的环。如果图中存在拓扑排序,则说明没有环;否则,存在环。我们可以通过广度优先搜索(BFS)或深度优先搜索(DFS)来实现拓扑排序。
下面是使用 BFS(Kahn’s 算法)实现的代码:
code
1 | var canFinish = function(numCourses, prerequisites) { |
解题思路
构建图:
- 使用邻接表来表示课程的依赖关系。
- 使用入度数组来记录每门课程的先修课程数量。
初始化队列:
- 将所有入度为0的课程加入队列。这些课程没有任何先修课程,可以直接开始学习。
广度优先搜索(BFS):
- 从队列中取出一门课程,将其标记为已完成(增加完成课程的计数)。
- 对该课程的所有后续课程进行处理:将后续课程的入度减1,如果减1后入度为0,则将其加入队列。
检查结果:
- 如果所有课程都被标记为已完成(完成课程的计数等于总课程数),则返回
true
。 - 否则,返回
false
,表示存在循环依赖,无法完成所有课程。
- 如果所有课程都被标记为已完成(完成课程的计数等于总课程数),则返回
复杂度分析
- 时间复杂度:
O(V + E)
,其中V
是课程的数量(顶点数),E
是先修课程的数量(边数)。构建图和执行 BFS 的过程都需要遍历所有顶点和边。 - 空间复杂度:
O(V + E)
,需要存储邻接表和入度数组。
这个方法高效且直观,适用于解决课程表问题。
实现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 类实现,使用 JavaScript 原型方法来定义 insert
、search
和 startsWith
方法。每个方法都有详细的注释来解释其工作原理。
完整代码实现
1 | // 定义 Trie 节点 |
解释和注释
- TrieNode 类:每个 Trie 节点包含一个
children
对象来存储子节点和一个布尔值isEndOfWord
来标记单词结束。 - Trie 类:包含一个
root
属性,它是一个 TrieNode 实例,表示前缀树的根节点。 - insert 方法:从根节点开始,逐个字符插入。如果字符不存在当前节点的
children
中,就创建新节点。插入完成后,标记最后一个节点的isEndOfWord
为true
。 - search 方法:使用
_searchPrefix
辅助函数找到节点,返回节点是否为单词结束。 - startsWith 方法:使用
_searchPrefix
辅助函数检查前缀是否存在。 - _searchPrefix 方法:从根节点开始,逐个字符检查节点是否存在,返回最终节点或
null
。
复杂度分析
时间复杂度:
insert
:O(m),其中 m 是单词的长度。search
和startsWith
:O(m),其中 m 是查询单词或前缀的长度。
空间复杂度:
- 每个节点最多有 26 个子节点(假设只处理小写字母),空间复杂度与插入的单词数量和长度有关。