想学数据结构与算法的前端同学,照着这份清单刷下去,保证妥妥能掌握,题目的顺序我参考了卡哥,在这里感谢下卡哥带我入门算法。我觉得解算法最好的方式一定画图,只要能把图画出来,基本就解决一半了,我在题解放的动画大部分是在leetcode的题解上录制的,这里也感谢下leetcode各位大神,我觉得看动画是理解算法最好的方式(至少对我来说),因为人类天生更能记住图像而不是文字。我会持续不断更新该文档~
数组
704.二分查找
给定一个
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
提示:
- 你可以假设
nums
中的所有元素是不重复的。n
将在[1, 10000]
之间。nums
的每个元素都将在[-9999, 9999]
之间。
二分查找
- 时间复杂度:$O(logn)$,其中 n 是数组的长度。
- 空间复杂度:$O(1)$。
function search(nums: number[], target: number): number {
let low = 0;
let high = nums.length - 1;
while (low <= high) {
let mid = Math.floor((low + high) / 2);
if (nums[mid] < target) {
low = mid + 1;
}
else if (nums[mid] > target) {
high = mid - 1;
}
else {
return mid
}
}
return -1
};
27.移除元素
给你一个数组 nums 和一个值 val,你需要 原地 移除所有数值等于 val 的元素,并返回移除后数组的新长度。
不要使用额外的数组空间,你必须仅使用 O(1) 额外空间并原地修改输入数组。
元素的顺序可以改变。你不需要考虑数组中超出新长度后面的元素。
示例 1: 给定 nums = [3,2,2,3], val = 3, 函数应该返回新的长度 2, 并且 nums 中的前两个元素均为 2。 你不需要考虑数组中超出新长度后面的元素。
示例 2: 给定 nums = [0,1,2,2,3,0,4,2], val = 2, 函数应该返回新的长度 5, 并且 nums 中的前五个元素为 0, 1, 3, 0, 4。
你不需要考虑数组中超出新长度后面的元素。
双指针
时间复杂度:O(n)
空间复杂度:O(1)
function removeElement(nums: number[], val: number): number {
let slowIndex = 0;
for (let fastIndex = 0; fastIndex < nums.length; fastIndex++) {
if (val !== nums[fastIndex]) {
nums[slowIndex++] = nums[fastIndex];
}
}
return slowIndex;
};
977.有序数组的平方
给你一个按 非递减顺序 排序的整数数组 nums,返回 每个数字的平方 组成的新数组,要求也按 非递减顺序 排序。
示例 1: 输入:nums = [-4,-1,0,3,10] 输出:[0,1,9,16,100] 解释:平方后,数组变为 [16,1,0,9,100],排序后,数组变为 [0,1,9,16,100]
示例 2: 输入:nums = [-7,-3,2,3,11] 输出:[4,9,9,49,121]
双指针
时间复杂度:O(n)
空间复杂度:O(1)
function sortedSquares(nums: number[]): number[] {
let result = Array.of(nums.length);
let k = nums.length - 1;
let left = 0;
let right = nums.length - 1;
while (left <= right) {
if (nums[left] * nums[left] > nums[right] * nums[right]) {
result[k--] = nums[left] * nums[left];
left++;
} else if (nums[left] * nums[left] <= nums[right] * nums[right]) {
result[k--] = nums[right] * nums[right];
right--;
}
}
return result;
};
209.长度最小的子数组
给定一个含有 n 个正整数的数组和一个正整数 s ,找出该数组中满足其和 ≥ s 的长度最小的 连续 子数组,并返回其长度。如果不存在符合条件的子数组,返回 0。
示例:
输入:s = 7, nums = [2,3,1,2,4,3] 输出:2 解释:子数组 [4,3] 是该条件下的长度最小的子数组。
提示:
- 1 <= target <= 10^9
- 1 <= nums.length <= 10^5
- 1 <= nums[i] <= 10^5
滑动窗口
时间复杂度:O(n)
空间复杂度:O(1)
function minSubArrayLen(target: number, nums: number[]): number {
let sum = 0;
let ans = Infinity;
let start = 0;
let end = 0;
while (end < nums.length) {
sum += nums[end];
while (sum >= target) {
ans = Math.min(ans, end - start + 1);
sum -= nums[start++];
}
end++;
}
return ans === Infinity ? 0 : ans;
};
59.螺旋矩阵Ⅱ
给定一个正整数 n,生成一个包含 1 到 n^2 所有元素,且元素按顺时针顺序螺旋排列的正方形矩阵。
示例:
输入: 3 输出: [ [ 1, 2, 3 ], [ 8, 9, 4 ], [ 7, 6, 5 ] ]
模拟法
时间复杂度:$O(n^2)$,其中几是给定的正整数。矩阵的大小是 $n * n$,需要填入矩阵中的每个元素。 空间复杂度:$0(1)$。除了返回的矩阵以外,空间复杂度是常数。
function generateMatrix(n: number): number[][] {
let mat: number[][] = Array.from(new Array(n)).map(() => Array.from(new Array(n)));
let l = 0, r = n - 1, b = n - 1, t = 0;
let num = 1, target = n * n;
while(num <= target) {
for (let i = l; i <= r; i++) mat[t][i] = num++;
t++;
for (let i = t; i <= b; i++) mat[i][r] = num++;
r--;
for (let i = r; i >= l; i--) mat[b][i] = num++;
b--;
for (let i = b; i >= t; i--) mat[i][l] = num++;
l++;
}
return mat;
};
链表
203.移除链表元素
题意:删除链表中等于给定值 val 的所有节点。
示例 1: 输入:head = [1,2,6,3,4,5,6], val = 6 输出:[1,2,3,4,5]
示例 2: 输入:head = [], val = 1 输出:[]
示例 3: 输入:head = [7,7,7,7], val = 7 输出:[]
虚拟头节点
/**
* Definition for singly-linked list.
* class ListNode {
* val: number
* next: ListNode | null
* constructor(val?: number, next?: ListNode | null) {
* this.val = (val===undefined ? 0 : val)
* this.next = (next===undefined ? null : next)
* }
* }
*/
function removeElements(head: ListNode | null, val: number): ListNode | null {
const dummyHead = new ListNode();
dummyHead.next = head;
let temp = dummyHead;
while (temp.next) {
if (temp.next.val === val) {
temp.next = temp.next.next
} else {
temp = temp.next;
}
}
return dummyHead.next;
};
707.设计链表
在链表类中实现这些功能:
- get(index):获取链表中第 index 个节点的值。如果索引无效,则返回-1。
- addAtHead(val):在链表的第一个元素之前添加一个值为 val 的节点。插入后,新节点将成为链表的第一个节点。
- addAtTail(val):将值为 val 的节点追加到链表的最后一个元素。
- addAtIndex(index,val):在链表中的第 index 个节点之前添加值为 val 的节点。如果 index 等于链表的长度,则该节点将附加到链表的末尾。如果 index 大于链表长度,则不会插入节点。如果index小于0,则在头部插入节点。
- deleteAtIndex(index):如果索引 index 有效,则删除链表中的第 index 个节点。
虚拟头节点
时间复杂度:初始化O(1),get消耗O(index),addAtHead消耗O(1),addAtTail消耗O(1),addAtIndex消耗O(index)。
空间复杂度:所有函数单词调用的空间复杂度均为O(1),总体空间复杂度O(n),其中n为addAtHead,addAtTail和addAtIndex的调用次数之和。
class N {
next: N;
val: number;
constructor(val?: number) {
this.val = val;
}
}
class MyLinkedList {
dummyNode: N = new N(0);
size = 0;
constructor() {
}
get(index: number): number {
if (index < 0 || index >= this.size) return -1;
let temp = this.dummyNode;
for (let i = 0; i <= index; i++) {
temp = temp.next;
}
return temp.val;
}
addAtHead(val: number): void {
this.addAtIndex(0, val);
}
addAtTail(val: number): void {
this.addAtIndex(this.size, val);
}
addAtIndex(index: number, val: number): void {
if (index > this.size) return;
index = Math.max(0, index);
this.size++;
let pred = this.dummyNode;
for (let i = 0; i < index; i++) {
pred = pred.next;
}
const n = new N(val);
n.next = pred.next;
pred.next = n;
}
deleteAtIndex(index: number): void {
if (index < 0 || index >= this.size) return;
this.size--;
let pred = this.dummyNode;
for (let i = 0; i < index; i++) {
pred = pred.next;
}
pred.next = pred.next.next;
}
}
/**
* Your MyLinkedList object will be instantiated and called as such:
* var obj = new MyLinkedList()
* var param_1 = obj.get(index)
* obj.addAtHead(val)
* obj.addAtTail(val)
* obj.addAtIndex(index,val)
* obj.deleteAtIndex(index)
*/
206.反转链表
题意:反转一个单链表。
示例: 输入: 1->2->3->4->5->NULL 输出: 5->4->3->2->1->NULL
双指针
时间复杂度:$O(n)$,其中n是链表的长度。需要遍历链表一次。
空间复杂度:$O(1)$。
/**
* Definition for singly-linked list.
* class ListNode {
* val: number
* next: ListNode | null
* constructor(val?: number, next?: ListNode | null) {
* this.val = (val===undefined ? 0 : val)
* this.next = (next===undefined ? null : next)
* }
* }
*/
function reverseList(head: ListNode | null): ListNode | null {
let prev: ListNode = null;
let cur: ListNode = head;
while (cur) {
const temp: ListNode = cur.next;
cur.next = prev;
prev = cur;
cur = temp;
}
return prev;
};
递归
时间复杂度:$O(n)$,其中n是链表的长度。需要对链表的每个节点进行反转操作。 空间复杂度:$O(n)$,其中几是链表的长度。空间复杂度主要取决于递归调用的栈空间,最多为n层。
/**
* Definition for singly-linked list.
* class ListNode {
* val: number
* next: ListNode | null
* constructor(val?: number, next?: ListNode | null) {
* this.val = (val===undefined ? 0 : val)
* this.next = (next===undefined ? null : next)
* }
* }
*/
function reverseList(head: ListNode | null): ListNode | null {
if (!head || !head.next) return head;
const ret = reverseList(head.next);
head.next.next = head;
head.next = null;
return ret;
};
24.两两交换链表中的节点
给定一个链表,两两交换其中相邻的节点,并返回交换后的链表。
你不能只是单纯的改变节点内部的值,而是需要实际的进行节点交换。
输入:head = [1,2,3,4] 输出:[2,1,4,3] 输入:head = [] 输出:[] 输入:head = [1] 输出:[1]
迭代
- 时间复杂度:$O(n)$,其中 n是链表的节点数量。需要对每个节点进行更新指针的操作。
- 空间复杂度:$O(1)$。
/**
* Definition for singly-linked list.
* class ListNode {
* val: number
* next: ListNode | null
* constructor(val?: number, next?: ListNode | null) {
* this.val = (val===undefined ? 0 : val)
* this.next = (next===undefined ? null : next)
* }
* }
*/
function swapPairs(head: ListNode | null): ListNode | null {
if (!head || !head.next) return head;
const dummyNode = new ListNode();
dummyNode.next = head;
let temp = dummyNode;
while (temp.next && temp.next.next) {
let node1 = temp.next;
let node2 = temp.next.next;
temp.next = node2;
node1.next = node2.next;
node2.next = node1;
temp = node1;
}
return dummyNode.next;
};
递归
- 时间复杂度:$O(n)$,其中n是链表的节点数量。需要对每个节点进行更新指针的操作。
- 空间复杂度:$O(n)$,其中n是链表的节点数量。空间复杂度主要取决于递归调用的栈空间。
/**
* Definition for singly-linked list.
* class ListNode {
* val: number
* next: ListNode | null
* constructor(val?: number, next?: ListNode | null) {
* this.val = (val===undefined ? 0 : val)
* this.next = (next===undefined ? null : next)
* }
* }
*/
function swapPairs(head: ListNode | null): ListNode | null {
if (head === null || head.next === null) return head;
const newHead = head.next;
head.next = swapPairs(newHead.next);
newHead.next = head;
return newHead;
};
19.删除链表的倒数第N个结点
给你一个链表,删除链表的倒数第
n
个结点,并且返回链表的头结点。输入:head = [1,2,3,4,5], n = 2 输出:[1,2,3,5] 输入:head = [1], n = 1 输出:[] 输入:head = [1,2], n = 1 输出:[1]
栈
- 时间复杂度:$O(L)$,其中 $L$ 是链表的长度。
- 空间复杂度:$O(L)$,其中 $L$ 是链表的长度。主要为栈的开销。
/**
* Definition for singly-linked list.
* class ListNode {
* val: number
* next: ListNode | null
* constructor(val?: number, next?: ListNode | null) {
* this.val = (val===undefined ? 0 : val)
* this.next = (next===undefined ? null : next)
* }
* }
*/
function removeNthFromEnd(head: ListNode | null, n: number): ListNode | null {
if (!head) return head;
const dummyNode = new ListNode(0);
dummyNode.next = head;
const stack: ListNode[] = [];
let cur = dummyNode;
let prev: ListNode = null;
while (cur.next) {
stack.unshift(cur);
cur = cur.next;
}
while (n > 0) {
n--;
prev = stack.shift();
}
prev.next = prev.next.next;
return dummyNode.next;
};
双指针
- 时间复杂度:$O(L)$,其中 $L$ 是链表的长度。
- 空间复杂度:$O(1)$。
/**
* Definition for singly-linked list.
* class ListNode {
* val: number
* next: ListNode | null
* constructor(val?: number, next?: ListNode | null) {
* this.val = (val===undefined ? 0 : val)
* this.next = (next===undefined ? null : next)
* }
* }
*/
function removeNthFromEnd(head: ListNode | null, n: number): ListNode | null {
if (!head) return head;
const dummyNode = new ListNode(0);
dummyNode.next = head;
let first: ListNode = head;
let second: ListNode = dummyNode;
for (let i = 0; i < n; i++) {
first = first.next;
}
while(first) {
first = first.next;
second = second.next;
}
second.next = second.next.next;
return dummyNode.next;
};
160.链表相交
给你两个单链表的头节点 headA 和 headB ,请你找出并返回两个单链表相交的起始节点。如果两个链表没有交点,返回 null 。
图示两个链表在节点 c1 开始相交:
题目数据 保证 整个链式结构中不存在环。
注意,函数返回结果后,链表必须 保持其原始结构 。
双指针
- 时间复杂度:$O(m+n)$,其中 $m$ 和 $n$ 是分别是链表 $headA$ 和 $headB$ 的长度。两个指针同时遍历两个链表,每个指针遍历两个链表各一次。
- 空间复杂度:$O(1)$。
/**
* Definition for singly-linked list.
* public class ListNode {
* int val;
* ListNode next;
* ListNode(int x) {
* val = x;
* next = null;
* }
* }
*/
public class Solution {
public ListNode getIntersectionNode(ListNode headA, ListNode headB) {
if (headA == null || headB == null) return null;
ListNode pA = headA;
ListNode pB = headB;
while (pA != pB) {
pA = pA == null ? headB : pA.next;
pB = pB == null ? headA : pB.next;
}
return pA;
}
}
142.环形链表Ⅱ
题意: 给定一个链表,返回链表开始入环的第一个节点。 如果链表无环,则返回 null。
为了表示给定链表中的环,使用整数 pos 来表示链表尾连接到链表中的位置(索引从 0 开始)。 如果 pos 是 -1,则在该链表中没有环。
说明:不允许修改给定的链表。
哈希表
思路:遍历链表中的每个节点,并将它记录下来;一旦遇到了此前遍历过的节点,就可以判定链表中存在环。
- 时间复杂度:$O(N)$,其中 $N$ 为链表中节点的数目。我们恰好需要访问链表中的每一个节点。
- 空间复杂度:$O(N)$,其中 $N$ 为链表中节点的数目。我们需要将链表中的每个节点都保存在哈希表当中。
/**
* Definition for singly-linked list.
* class ListNode {
* val: number
* next: ListNode | null
* constructor(val?: number, next?: ListNode | null) {
* this.val = (val===undefined ? 0 : val)
* this.next = (next===undefined ? null : next)
* }
* }
*/
function detectCycle(head: ListNode | null): ListNode | null {
if (!head) return head;
const set = new Set();
let temp = head;
while (temp) {
if (set.has(temp)) {
return temp;
}
set.add(temp);
temp = temp.next;
}
return null;
};
快慢双指针
- 时间复杂度:$O(N)$,其中 $N$ 为链表中节点的数目。在最初判断快慢指针是否相遇时,$slow$ 指针走过的距离不会超过链表的总长度;随后寻找入环点时,走过的距离也不会超过链表的总长度。因此,总的执行时间为 $O(N)+O(N) =O(N)$。
- 空间复杂度:$O(1)$。我们只使用了 $slou,fast$ 两个指针。
/**
* Definition for singly-linked list.
* class ListNode {
* val: number
* next: ListNode | null
* constructor(val?: number, next?: ListNode | null) {
* this.val = (val===undefined ? 0 : val)
* this.next = (next===undefined ? null : next)
* }
* }
*/
function detectCycle(head: ListNode | null): ListNode | null {
if (!head) return null;
let slow = head, fast = head;
while (true) {
if (!fast || !fast.next) return null;
slow = slow.next;
fast = fast.next.next;
if (slow === fast) break;
}
fast = head;
while (slow !== fast) {
slow = slow.next;
fast = fast.next;
}
return fast;
};
哈希表
242.有效的字母异位词
给定两个字符串 s 和 t ,编写一个函数来判断 t 是否是 s 的字母异位词。
**注意:**若
s
和t
中每个字符出现的次数都相同,则称s
和t
互为字母异位词。示例 1: 输入: s = "anagram", t = "nagaram" 输出: true
示例 2: 输入: s = "rat", t = "car" 输出: false
说明: 你可以假设字符串只包含小写字母。
哈希表
时间复杂度:O(n),其中n为s的长度
空间复杂度:O(S),其中S为字符集大小
function isAnagram(s: string, t: string): boolean {
if (s.length !== t.length) return false;
const map = new Map<string, number>();
for (let i = 0; i < s.length; i++) {
map.set(s[i], (map.get(s[i]) || 0) + 1);
}
for (let i = 0; i < t.length; i++) {
map.set(t[i], (map.get(t[i]) || 0) - 1);
if (map.get(t[i]) < 0) return false;
}
return true
};
1002.查找共用字符
给你一个字符串数组 words ,请你找出所有在 words 的每个字符串中都出现的共用字符( 包括重复字符),并以数组形式返回。你可以按 任意顺序 返回答案。
示例 1:
输入:words = ["bella","label","roller"] 输出:["e","l","l"] 示例 2:
输入:words = ["cool","lock","cook"] 输出:["c","o"]
提示:
1 <= words.length <= 100 1 <= words[i].length <= 100 words[i] 由小写英文字母组成
哈希表
- 时间复杂度:$O(n(m+|∑|)$,其中 $n$ 是数组 A 的长度(即字符串的数目),$m$ 是字符串的平均长度,$∑$ 为字符集,在本题中字符集为所有小写字母,$∑$=26。
- 空间复杂度:$O(|∑|)$。
class Solution {
public List<String> commonChars(String[] words) {
List<String> result = new ArrayList<String>();
if (words.length == 0) return result;
int[] hash = new int[26];
for (int i = 0; i < words[0].length(); i++) {
hash[words[0].charAt(i) - 'a']++;
}
for (int i = 1; i < words.length; i++) {
int[] hashOtherStr = new int[26];
for (int j = 0; j < words[i].length(); j++) {
hashOtherStr[words[i].charAt(j) - 'a']++;
}
for (int k = 0; k < 26; k++) {
hash[k] = Math.min(hash[k], hashOtherStr[k]);
}
}
for (int i = 0; i < 26; i++) {
while (hash[i] != 0) {
char c = (char) (i + 'a');
result.add(String.valueOf(c));
hash[i]--;
}
}
return result;
}
}
349.两个数组的交集
给定两个数组
nums1
和nums2
,返回 它们的交集 。输出结果中的每个元素一定是 唯一 的。我们可以 不考虑输出结果的顺序 。示例 1:
输入:nums1 = [1,2,2,1], nums2 = [2,2] 输出:[2]
示例 2:
输入:nums1 = [4,9,5], nums2 = [9,4,9,8,4] 输出:[9,4] 解释:[4,9] 也是可通过的
两个集合
使用两个集合分别存储两个数组中的元素,然后遍历较小的集合,判断其中的每个元素是否在另一个集合中,如果元素也在另一个集合中,则将该元素添加到返回值。
- 时间复杂度:$O(m+n)$,其中 $m$ 和 $n$ 分别是两个数组的长度。使用两个集合分别存储两个数组中的元素需要 $O(m+n)$ 的时间,遍历较小的集合并判断元素是否在另一个集合中需要 $O(min(m,n))$ 的时间,因此总时间复杂度是 $O(m+n)$。
- 空间复杂度:$O(m+n)$,其中 $m$ 和 $n$ 分别是两个数组的长度。空间复杂度主要取决于两个集合。
function intersection(nums1: number[], nums2: number[]): number[] {
let set1 = new Set(nums1);
let set2 = new Set(nums2);
const res = new Set<number>();
if (set1.size > set2.size) {
[set1, set2] = [set2, set1];
}
for (let num of set1) {
if (set2.has(num)) {
res.add(num);
}
}
return [...res];;
};
排序+双指针
思路:数组排序,然后用两个指针分别遍历数组,如果两个指针指向的元素相等就是其中一个交集,否则比较两个指针指向的元素的大小,较小的向前移动。
- 时间复杂度:$O(mlogm+n logn)$,其中m和n分别是两个数组的长度。对两个数组排序的时间复杂度分别是 $O(mlog m)$ 和 $O(nlogn)$,双指针寻找交集元素的时间复杂度是 $O(m+n)$,因此总时间复杂度是 $O(mlog m + nlog n)$。
- 空间复杂度:$O(logm + logn)$,其中 $m$ 和 $n$ 分别是两个数组的长度。空间复杂度主要取决于排序使用的额外空间。
function intersection(nums1: number[], nums2: number[]): number[] {
nums1.sort((x, y) => x - y);
nums2.sort((x, y) => x - y);
let index1 = 0;
let index2 = 0;
const intersection = new Set<number>();
while (index1 < nums1.length && index2 < nums2.length) {
if (nums1[index1] === nums2[index2]) {
intersection.add(nums1[index1]);
index1++;
index2++;
} else if (nums1[index1] > nums2[index2]) {
index2++;
} else {
index1++;
}
}
return [...intersection];
};
202.快乐数
哈希表
思路:通过持续计算数字的平方和并将结果添加到集合中,如果最终得到1(快乐数),则结束;如果产生的数字已经在集合中(表示陷入循环且循环中没有1),则可以确定该数不是快乐数。
- 时间复杂度:$O(log n)$。
- 空间复杂度:$O(log n)$。
function getNext(n: number) {
let totalSum = 0;
while (n > 0) {
let d = n % 10;
n = Math.floor(n / 10);
totalSum += d * d;
}
return totalSum;
}
function isHappy(n: number): boolean {
const set = new Set<Number>();
let sum = n;
while (sum !== 1) {
let newSum = getNext(sum);
if (set.has(newSum)) return false;
set.add(newSum);
sum = newSum;
}
return true;
};
【推荐】快慢指针
思路:通过快慢两个指针(一个一次计算一步,另一个一次计算两步)遍历数字的平方和序列,如果这个序列能够到达1(快乐数),则快指针将首先到达1;如果序列陷入循环且循环中没有1,那么快慢指针最终将相遇,此时可以确定该数不是快乐数。
- 时间复杂度:$O(log n)$。
- 空间复杂度:$O(1)$。
function getNext(n: number) {
let totalSum = 0;
while (n > 0) {
let d = n % 10;
n = Math.floor(n / 10);
totalSum += d * d;
}
return totalSum;
}
function isHappy(n: number): boolean {
let slow = n;
let fast = getNext(n);
while (fast !== 1) {
if (slow === fast) return false;
slow = getNext(slow);
fast = getNext(getNext(fast));
}
return true;
};
1.两数之和
给定一个整数数组 nums 和一个目标值 target,请你在该数组中找出和为目标值的那 两个 整数,并返回他们的数组下标。
你可以假设每种输入只会对应一个答案。但是,数组中同一个元素不能使用两遍。
示例:
给定 nums = [2, 7, 11, 15], target = 9
因为 nums[0] + nums[1] = 2 + 7 = 9
所以返回 [0, 1]
哈希表
- 时间复杂度:$O(N)$,其中 $N$ 是数组中的元素数量。对于每一个元素
x
,我们可以 $O(1)$ 地寻找target - x
。 - 空间复杂度:$O(N)$,其中 $N$ 是数组中的元素数量。主要为哈希表的开销。
function twoSum(nums: number[], target: number): number[] {
const map = new Map<number, number>();
for (let i = 0; i < nums.length; i++) {
const index = map.get(target - nums[i])
if (index !== undefined) {
return [index, i];
}
map.set(nums[i], i);
}
return [];
};
454.四数相加Ⅱ
哈希表
给定四个包含整数的数组列表 A , B , C , D ,计算有多少个元组 (i, j, k, l) ,使得 A[i] + B[j] + C[k] + D[l] = 0。
为了使问题简单化,所有的 A, B, C, D 具有相同的长度 N,且 0 ≤ N ≤ 500 。所有整数的范围在 -2^28 到 2^28 - 1 之间,最终结果不会超过 2^31 - 1 。
例如:
输入:
- A = [ 1, 2]
- B = [-2,-1]
- C = [-1, 2]
- D = [ 0, 2]
输出: 2
解释:
两个元组如下:
- (0, 0, 0, 1) -> A[0] + B[0] + C[0] + D[1] = 1 + (-2) + (-1) + 2 = 0
- (1, 1, 0, 0) -> A[1] + B[1] + C[0] + D[0] = 2 + (-1) + (-1) + 0 = 0
- 先计算列表A和B中所有可能的两数之和,并在一个哈希表中记录每种两数之和出现的次数。对于每一对(A[i], B[j]),将A[i] + B[j]加入到哈希表,并更新哈希表中对应的计数。
- 然后,对于列表C和D中的每一对(C[k], D[l]),计算-(C[k] + D[l]),看它是否在哈希表中。如果在,那么就找到了一种组合,使得A[i] + B[j] + C[k] + D[l]等于0。
- 将哈希表中与-(C[k] + D[l])相对应的值加到结果中,因为这个值表示存在多少种可能的(A[i], B[j])组合,使得A[i] + B[j]的和等于-(C[k] + D[l]),也就是说,存在多少种可能的四元组使得他们的和等于0。
这个方法将原问题从四个列表的四重循环简化为了两个两重循环,大大减少了计算的复杂性。使用哈希表记录两数之和的频率,也提高了查找的效率。这种方法的时间复杂度是$O(n^2)$,空间复杂度也是$O(n^2)$,其中n是列表A, B, C, D的长度。
function fourSumCount(nums1: number[], nums2: number[], nums3: number[], nums4: number[]): number {
const map = new Map<number, number>();
for (let num1 of nums1) {
for (let num2 of nums2) {
const sum = num1 + num2
map.set(sum, map.has(sum) ? map.get(sum) + 1 : 1);
}
}
let ans = 0
for (let num3 of nums3) {
for (let num4 of nums4) {
if (map.get(-num3 - num4) !== undefined) {
ans += map.get(-num3 - num4);
}
}
}
return ans
};
383.赎金信
字符统计
给定一个赎金信 (ransom) 字符串和一个杂志(magazine)字符串,判断第一个字符串 ransom 能不能由第二个字符串 magazines 里面的字符构成。如果可以构成,返回 true ;否则返回 false。
(题目说明:为了不暴露赎金信字迹,要从杂志上搜索各个需要的字母,组成单词来表达意思。杂志字符串中的每个字符只能在赎金信字符串中使用一次。)
注意:
你可以假设两个字符串均只含有小写字母。
canConstruct("a", "b") -> false canConstruct("aa", "ab") -> false canConstruct("aa", "aab") -> true
- 时间复杂度:$O(m+n)$,只需遍历两个字符一次即可。
- 空间复杂度:$O(S)$,$S$ 是字符集,这道题中 $S$ 为全部小写英语字母,因此 $S=26$。
function canConstruct(ransomNote: string, magazine: string): boolean {
if (ransomNote.length > magazine.length) return false;
const arr = Array.from(new Array(26), () => 0);
for (let s of magazine) {
const index = s.charCodeAt(0) - 'a'.charCodeAt(0);
arr[index]++;
}
for (let s of ransomNote) {
const index = s.charCodeAt(0) - 'a'.charCodeAt(0);
if (arr[index] - 1 < 0) {
return false
}
arr[index]--;
}
return true;
};
15.三数之和
给你一个包含 n 个整数的数组 nums,判断 nums 中是否存在三个元素 a,b,c ,使得 a + b + c = 0 ?请你找出所有满足条件且不重复的三元组。
注意: 答案中不可以包含重复的三元组。
示例:
给定数组 nums = [-1, 0, 1, 2, -1, -4],
满足要求的三元组集合为: [ [-1, 0, 1], [-1, -1, 2] ]
示例1
输入:nums = [-1,0,1,2,-1,-4] 输出:[[-1,-1,2],[-1,0,1]] 解释: nums[0] + nums[1] + nums[2] = (-1) + 0 + 1 = 0 。 nums[1] + nums[2] + nums[4] = 0 + 1 + (-1) = 0 。 nums[0] + nums[3] + nums[4] = (-1) + 2 + (-1) = 0 。 不同的三元组是 [-1,0,1] 和 [-1,-1,2] 。 注意,输出的顺序和三元组的顺序并不重要。
示例2
输入:nums = [0,1,1] 输出:[] 解释:唯一可能的三元组和不为 0 。
示例3
输入:nums = [0,0,0] 输出:[[0,0,0]] 解释:唯一可能的三元组和为 0 。
排序+双指针
- 时间复杂度:$O(N^2)$,其中 $N$ 是数组的长度。
- 空间复杂度:$O(log N)$
function threeSum(nums: number[]): number[][] {
if (nums.length < 3) return [];
nums.sort((a, b) => a - b);
const ans: number[][] = [];
for (let i = 0; i < nums.length; i++) {
if (nums[i] > 0) break;;
if (i > 0 && nums[i] === nums[i - 1]) continue;
let L = i + 1;
let R = nums.length - 1;
while (L < R) {
const sum = nums[i] + nums[L] + nums[R];
if (sum < 0) {
L++;
} else if (sum > 0) {
R--;
} else {
while (nums[L] === nums[L + 1]) L++; // 去重
while (nums[R] === nums[R - 1]) R--; // 去重
ans.push([nums[i], nums[L], nums[R]]);
L++;
R--;
}
}
}
return ans;
};
18.四数之和
题意:给定一个包含 n 个整数的数组 nums 和一个目标值 target,判断 nums 中是否存在四个元素 a,b,c 和 d ,使得 a + b + c + d 的值与 target 相等?找出所有满足条件且不重复的四元组。
注意:
答案中不可以包含重复的四元组。
示例: 给定数组 nums = [1, 0, -1, 0, -2, 2],和 target = 0。 满足要求的四元组集合为: [ [-1, 0, 0, 1], [-2, -1, 1, 2], [-2, 0, 0, 2] ]
排序+双指针
- 时间复杂度:$O(n^3)$,其中 $n$ 是数组的长度。排序的时间复杂度是 $O(nlog n)$,枚举四元组的时间复杂度是 $O(n^3)$,因此总时间复杂度为 $O(n^3 + nlog n) = O(n^3)$。
- 空间复杂度:$O(logn)$,其中 $n$ 是数组的长度。空间复杂度主要取决于排序额外使用的空间。此外排序修改了输入数组 $nums$,实际情况中不一定允许,因此也可以看成使用了一个额外的数组存储了数组 $nums$ 的副本并排序,空间复杂度为 $O(n)$。
和三数之和解法一样。
function fourSum(nums: number[], target: number): number[][] {
const quadruplets: number[][] = [];
if (nums.length < 4) {
return quadruplets;
}
nums.sort((x, y) => x - y);
const length = nums.length;
for (let i = 0; i < length - 3; i++) {
if (i > 0 && nums[i] === nums[i - 1]) {
continue;
}
// 最小值大于target,退出循环
if (nums[i] + nums[i + 1] + nums[i + 2] + nums[i + 3] > target) {
break;
}
// 最大值小于target,跳过当前循环
if (nums[i] + nums[length - 3] + nums[length - 2] + nums[length - 1] < target) {
continue;
}
for (let j = i + 1; j < length - 2; j++) {
if (j > i + 1 && nums[j] === nums[j - 1]) {
continue;
}
// 最小值大于target,退出循环
if (nums[i] + nums[j] + nums[j + 1] + nums[j + 2] > target) {
break;
}
// 最大值小于target,跳过当前循环
if (nums[i] + nums[j] + nums[length - 2] + nums[length - 1] < target) {
continue;
}
let left = j + 1, right = length - 1;
while (left < right) {
const sum = nums[i] + nums[j] + nums[left] + nums[right];
if (sum === target) {
quadruplets.push([nums[i], nums[j], nums[left], nums[right]]);
while (left < right && nums[left] === nums[left + 1]) {
left++;
}
left++;
while (left < right && nums[right] === nums[right - 1]) {
right--;
}
right--;
} else if (sum < target) {
left++;
} else {
right--;
}
}
}
}
return quadruplets;
};
字符串
344.反转字符串
编写一个函数,其作用是将输入的字符串反转过来。输入字符串以字符数组 char[] 的形式给出。
不要给另外的数组分配额外的空间,你必须原地修改输入数组、使用 O(1) 的额外空间解决这一问题。
你可以假设数组中的所有字符都是 ASCII 码表中的可打印字符。
示例 1: 输入:["h","e","l","l","o"] 输出:["o","l","l","e","h"]
示例 2: 输入:["H","a","n","n","a","h"] 输出:["h","a","n","n","a","H"]
双指针
- 时间复杂度:$O(N)$,其中 $N$ 为字符数组的长度。一共执行了 $N/2$ 的交换。
- 空间复杂度:$O(1)$。 只使用了常数空间来存放若干变量。
/**
Do not return anything, modify s in-place instead.
*/
function reverseString(s: string[]): void {
let L = 0
let R = s.length - 1;
while (L < R) {
const temp = s[L];
s[L] = s[R];
s[R] = temp;
L++;
R--;
}
};
541.反转字符串Ⅱ
给定一个字符串 s 和一个整数 k,从字符串开头算起, 每计数至 2k 个字符,就反转这 2k 个字符中的前 k 个字符。
如果剩余字符少于 k 个,则将剩余字符全部反转。
如果剩余字符小于 2k 但大于或等于 k 个,则反转前 k 个字符,其余字符保持原样。
示例:
输入: s = "abcdefg", k = 2 输出: "bacdfeg"
模拟
- 时间复杂度:$O(n)$,其中n是字符串 $s$ 的长度。
- 空间复杂度:$O(1$)或 $O(n)$,取决于使用的语言中字符串类型的性质。如果字符串是可修改的,那么我们可以直接在原字符串上修改,空间复杂度为 $O(1)$,否则需要使用 $O(n)$ 的空间将字符串临时转换为可以修改的数据结构(例如数组),空间复杂度为 $O(n)$。
反转每个下标从 $2k$ 的倍数开始的,长度为 $k$ 的子串。若该子串长度不足 $k$,则反转整个子串。
function reverse(arr: string[], left: number, right: number) {
while (left < right) {
[arr[left], arr[right]] = [arr[right], arr[left]];
left++;
right--;
}
}
function reverseStr(s: string, k: number): string {
const arr = s.split('');
for (let i = 0; i < arr.length; i += 2 * k) {
reverse(arr, i, Math.min(i + k, arr.length) - 1);
}
return arr.join('');
};
05.替换空格
请实现一个函数,把字符串
s
中的每个空格替换成"%20"。示例 1:
输入:s = "We are happy." 输出:"We%20are%20happy."
字符数组
- 时间复杂度:$O(N)$
- 空间复杂度:$O(N)$
function replaceSpace(s: string): string {
let arr = [];
for (let i of s) {
if (i === " ") {
arr.push("%20");
} else {
arr.push(i);
}
}
return arr.join("");
};
151.反转字符串中的单词
给定一个字符串,逐个翻转字符串中的每个单词。
示例 1:
输入: "the sky is blue" 输出: "blue is sky the"
示例 2:
输入: " hello world! " 输出: "world! hello" 解释: 输入字符串可以在前面或者后面包含多余的空格,但是反转后的字符不能包括。
示例 3:
输入: "a good example" 输出: "example good a" 解释: 如果两个单词间有多余的空格,将反转后单词间的空格减少到只含一个。
语言特性
思路:很多语言对字符串提供了 split(拆分),reverse(翻转)和 join(连接)等方法,因此我们可以简单的调用内置的 API 完成操作:
使用 split 将字符串按空格分割成字符串数组;
使用 reverse 将字符串数组进行反转;
使用 join 方法将字符串数组拼成一个字符串。
复杂度分析:
- 时间复杂度:$O(n)$,其中 $n$ 为输入字符串的长度。
- 空间复杂度:$O(n)$,用来存储字符串分割之后的结果。
function reverseWords(s: string): string {
return s.trim().split(/\s+/).reverse().join(" ");
};
双端队列
- 时间复杂度:$O(n)$,其中 $n$ 为输入字符串的长度。
- 空间复杂度:$O(n)$,双端队列存储单词需要 $O(n)$ 的空间。
function reverseWords(s: string): string {
let left = 0;
let right = s.length - 1;
let queue: string[] = [];
let temp: string[] = [];
while (left <= right && s[left] === " ") left++;
while (left <= right && s[right] === " ") right--;
while (left <= right) {
if (s[left] !== " ") {
temp.push(s[left]);
} else if (s[left] === " " && temp.length !== 0) {
queue.unshift(temp.join(""));
temp = [];
}
left++;
}
queue.unshift(temp.join(""));
return queue.join(" ");
};
剑指 Offer 58 - II. 左旋转字符串
字符串的左旋转操作是把字符串前面的若干个字符转移到字符串的尾部。请定义一个函数实现字符串左旋转操作的功能。比如,输入字符串"abcdefg"和数字2,该函数将返回左旋转两位得到的结果"cdefgab"。
示例 1:
输入: s = "abcdefg", k = 2 输出: "cdefgab"
示例 2:
输入: s = "lrloseumgh", k = 6 输出: "umghlrlose"
字符串切片
- 时间复杂度:$O(N)$,$N$ 为字符串s的长度。
- 空间复杂度:$O(N)$,两个字符串切片的总长度为 $N$。
function reverseLeftWords(s: string, n: number): string {
return s.slice(n) + s.slice(0, n)
};
列表遍历拼接
- 时间复杂度:$O(N)$,线性遍历 $s$ 并添加。
- 空间复杂度:$O(N)$,新建的辅助 $arr$ 使用 $O(N)$ 大小的额外空间。
function reverseLeftWords(s: string, n: number): string {
const arr: string[] = [];
for (let i = n; i < s.length; i++) {
arr.push(s[i]);
}
for (let i = 0; i < n; i++) {
arr.push(s[i]);
}
return arr.join("");
};
28.找出字符串中第一个匹配项的下标
xxx
暴力匹配
我们可以让字符串 needle 与字符串 haystack 的所有长度为 $m$ 的子串均匹配一次。
为了减少不必要的匹配,我们每次匹配失败即立刻停止当前子串的匹配,对下一个子串继续匹配。如果当前子串匹配成功,我们返回当前子串的开始位置即可。如果所有子串都匹配失败,则返回 -1。
- 时间复杂度:$O(m*n)$。
- 空间复杂度:$O(1)$。
function strStr(haystack: string, needle: string): number {
for (let i = 0; i < haystack.length; i++) {
let a = i;
let b = 0;
if (haystack[i] === needle[b]) {
while (b < needle.length && haystack[a] === needle[b]) {
a++;
b++;
}
if (b === needle.length) {
return i;
}
}
}
return -1;
};
KMP
KMP算法是一种改进的字符串匹配算法,避免了朴素算法中不必要的字符比较,提高了匹配效率。它的主要思想是当出现字符比较不匹配时,可以记录一部分之前已经匹配的文本内容,利用这些信息使得下一步的搜索更加快捷。
- 时间复杂度:$O(m+n)$。
- 空间复杂度:$O(m)$,其中 $m$ 是字符串 needle 的长度。
思路:
- 首先,函数检查needle的长度。如果needle的长度为0,那么函数就立即返回0(因为空字符串在任何位置都能被找到)。
- 然后,函数初始化next数组,并且开始填充它。这个过程就是在计算needle中每个位置的前缀和后缀的最长公共长度。
- 接下来,函数开始在haystack中查找needle。它从haystack的第一个字符开始,同时也从needle的第一个字符开始。每当找到一个匹配的字符,就将needle的当前位置向前移动一位(即j++)。如果在某个位置找不到匹配的字符,就回溯到needle的某个较早位置(即设置j为next[j - 1]),然后再从那里开始比较。这就是利用next数组进行快速跳跃的关键步骤。
- 如果在某个位置找到了整个needle(即j等于needle的长度),那么函数就返回这个位置(即返回i - m + 1,其中m是needle的长度)。
- 如果遍历了整个haystack都没有找到needle,那么函数就返回-1。
function strStr(haystack: string, needle: string): number {
let n = haystack.length, m = needle.length;
if (m === 0) return 0;
let next = new Array(m).fill(0);
// 构建前缀表
for (let i = 1, j = 0; i < m; i++) {
while (j > 0 && needle[i] !== needle[j]) {
j = next[j - 1];
}
if (needle[i] === needle[j]) {
j++;
}
next[i] = j;
}
for (let i = 0, j = 0; i < n; i++) {
while (j > 0 && haystack[i] !== needle[j]) {
j = next[j - 1];
}
if (haystack[i] === needle[j]) {
j++;
}
if (j === m) {
return i - m + 1;
}
}
return -1;
};
459.重复的子字符串
给定一个非空的字符串,判断它是否可以由它的一个子串重复多次构成。给定的字符串只含有小写英文字母,并且长度不超过10000。
示例 1: 输入: "abab" 输出: True 解释: 可由子字符串 "ab" 重复两次构成。
示例 2: 输入: "aba" 输出: False
示例 3: 输入: "abcabcabcabc" 输出: True 解释: 可由子字符串 "abc" 重复四次构成。 (或者子字符串 "abcabc" 重复两次构成。)
双倍长度字符串
思路:
- 将原始字符串
s
复制并连接到自身,形成s + s
,其长度为原始字符串的两倍。 - 移除新字符串的第一个和最后一个字符,也就是执行
.slice(1, -1)
操作。 - 在这个新生成的字符串中搜索原始字符串
s
。如果找到了(即indexOf(s)
的结果不为-1
),那么原始字符串s
包含重复的子字符串。如果没有找到,那么s
不存在重复的子字符串。
function repeatedSubstringPattern(s: string): boolean {
return (s+s).slice(1, -1).indexOf(s) !== -1;
};
KMP
方法一中使用了语言自带的查找函数indexOf
。同样我们也可以自己实现这个函数,例如使用比较经典的KMP算法。
// KMP算法
function kmp(str: string, substr: string) {
let n = str.length, m = substr.length;
let next: number[] = new Array(m).fill(0);
for (let i = 1, j = 0; i < m; i++) {
while (j > 0 && substr[i] !== substr[j]) {
j = next[j - 1];
}
if (substr[i] === substr[j]) {
j++;
}
next[i] = j;
}
for (let i = 0, j = 0; i < n; i++) {
while (j > 0 && str[i] !== substr[j]) {
j = next[j - 1];
}
if (str[i] === substr[j]) {
j++;
}
if (j === m) {
return i - m + 1;
}
}
return -1;
}
function repeatedSubstringPattern(s: string): boolean {
return kmp((s+s).slice(1, -1), s) !== -1;
};
栈与队列
232.用栈实现队列
使用栈实现队列的下列操作:
push(x)
-- 将一个元素放入队列的尾部。pop()
-- 从队列首部移除元素。peek()
-- 返回队列首部的元素。empty()
-- 返回队列是否为空。示例:
MyQueue queue = new MyQueue(); queue.push(1); queue.push(2); queue.peek(); // 返回 1 queue.pop(); // 返回 1 queue.empty(); // 返回 false
说明:
- 你只能使用标准的栈操作 -- 也就是只有 push to top, peek/pop from top, size, 和 is empty 操作是合法的。
- 你所使用的语言也许不支持栈。你可以使用 list 或者 deque(双端队列)来模拟一个栈,只要是标准的栈操作即可。
- 假设所有操作都是有效的 (例如,一个空的队列不会调用 pop 或者 peek 操作)。
双栈
class MyQueue {
inStack: number[] = [];
outStack: number[] = [];
push(x: number): void {
this.inStack.push(x);
}
provide() {
if (this.outStack.length === 0) {
while (this.inStack.length !== 0) {
this.outStack.push(this.inStack.pop())
}
}
}
pop(): number {
this.provide();
return this.outStack.pop();
}
peek(): number {
this.provide();
return this.outStack[this.outStack.length - 1];
}
empty(): boolean {
return this.inStack.length === 0 && this.outStack.length === 0;
}
}
/**
* Your MyQueue object will be instantiated and called as such:
* var obj = new MyQueue()
* obj.push(x)
* var param_2 = obj.pop()
* var param_3 = obj.peek()
* var param_4 = obj.empty()
*/
225.用队列实现栈
使用队列实现栈的下列操作:
- push(x) -- 元素 x 入栈
- pop() -- 移除栈顶元素
- top() -- 获取栈顶元素
- empty() -- 返回栈是否为空
注意:
- 你只能使用队列的基本操作-- 也就是 push to back, peek/pop from front, size, 和 is empty 这些操作是合法的。
- 你所使用的语言也许不支持队列。 你可以使用 list 或者 deque(双端队列)来模拟一个队列 , 只要是标准的队列操作即可。
- 你可以假设所有操作都是有效的(例如, 对一个空的栈不会调用 pop 或者 top 操作)。
两个队列
时间复杂度:入栈操作 $O(n)$,其余操作都是 $O(1)$,其中 n 是栈内的元素个数。
入栈操作需要将 $queue_1$ 中的几 个元素出队,并入队 $n+1$ 个元素到 $queue_2$,共有$2n +1$次操作,每次出队和入队操作的时间复杂度都是$O(1)$,因此入栈操作的时间复杂度是 $O(n)$。 出栈操作对应将 $queue_1$ 的前端元素出队,时间复杂度是 $O(1)$。 获得栈顶元素操作对应获得 $queue_1$ 的前端元素,时间复杂度是 $O(1)$。 判断栈是否为空操作只需要判断 $queue_1$,是否为空,时间复杂度是 $O(1)$。
空间复杂度:$O(n)$,其中 $n$ 是栈内的元素个数。需要使用两个队列存储栈内的元素。
class MyStack {
queue1: number[] = [];
queue2: number[] = [];
constructor() {
}
push(x: number): void {
this.queue2.push(x);
while(this.queue1.length !== 0) {
this.queue2.push(this.queue1.shift());
}
[this.queue1, this.queue2] = [this.queue2, this.queue1];
}
pop(): number {
return this.queue1.shift();
}
top(): number {
return this.queue1[0];
}
empty(): boolean {
return this.queue1.length === 0;
}
}
/**
* Your MyStack object will be instantiated and called as such:
* var obj = new MyStack()
* obj.push(x)
* var param_2 = obj.pop()
* var param_3 = obj.top()
* var param_4 = obj.empty()
*/
一个队列
时间复杂度:入栈操作 $O(n)$,其余操作都是 $O(1)$,其中 n 是栈内的元素个数。
入栈操作需要将 $queue_1$ 中的几 个元素出队,并入队 $n+1$ 个元素到 $queue_2$,共有$2n +1$次操作,每次出队和入队操作的时间复杂度都是$O(1)$,因此入栈操作的时间复杂度是 $O(n)$。 出栈操作对应将 $queue_1$ 的前端元素出队,时间复杂度是 $O(1)$。 获得栈顶元素操作对应获得 $queue_1$ 的前端元素,时间复杂度是 $O(1)$。 判断栈是否为空操作只需要判断 $queue_1$,是否为空,时间复杂度是 $O(1)$。
空间复杂度:$O(n)$,其中 $n$ 是栈内的元素个数。需要使用一个队列存储栈内的元素。
class MyStack {
queue: number[] = [];
constructor() {
}
push(x: number): void {
let n = this.queue.length;
this.queue.push(x);
while (n > 0) {
n--;
this.queue.push(this.queue.shift());
}
}
pop(): number {
return this.queue.shift();
}
top(): number {
return this.queue[0];
}
empty(): boolean {
return this.queue.length === 0;
}
}
/**
* Your MyStack object will be instantiated and called as such:
* var obj = new MyStack()
* obj.push(x)
* var param_2 = obj.pop()
* var param_3 = obj.top()
* var param_4 = obj.empty()
*/
20. 有效的括号
给定一个只包括 '(',')','{','}','[',']' 的字符串,判断字符串是否有效。
有效字符串需满足:
- 左括号必须用相同类型的右括号闭合。
- 左括号必须以正确的顺序闭合。
- 注意空字符串可被认为是有效字符串。
示例 1:
- 输入: "()"
- 输出: true
示例 2:
- 输入: "()[]{}"
- 输出: true
示例 3:
- 输入: "(]"
- 输出: false
示例 4:
- 输入: "([)]"
- 输出: false
示例 5:
- 输入: "{[]}"
- 输出: true
栈
- 时间复杂度:$O(N)$ ,$N$ 为字符串的长度。
- 空间复杂度:$O(N)$,哈希表和栈使用线性的空间大小。
function isValid(s: string): boolean {
if (s.length % 2 === 1) return false;
const stack: string[] = [];
for (let str of s) {
switch (str) {
case '(':
case '[':
case '{':
stack.unshift(str);
break;
case ')':
if (stack.shift() !== '(') return false;
break;
case ']':
if (stack.shift() !== '[') return false;
break;
case '}':
if (stack.shift() !== '{') return false;
break;
}
}
return stack.length === 0;
};
1047.删除字符串中的所有相邻重复项
给出由小写字母组成的字符串 S,重复项删除操作会选择两个相邻且相同的字母,并删除它们。
在 S 上反复执行重复项删除操作,直到无法继续删除。
在完成所有重复项删除操作后返回最终的字符串。答案保证唯一。
示例:
- 输入:"abbaca"
- 输出:"ca"
- 解释:例如,在 "abbaca" 中,我们可以删除 "bb" 由于两字母相邻且相同,这是此时唯一可以执行删除操作的重复项。之后我们得到字符串 "aaca",其中又只有 "aa" 可以执行重复项删除操作,所以最后的字符串为 "ca"。
提示:
- 1 <= S.length <= 20000
- S 仅由小写英文字母组成。
栈
- 时间复杂度:$O(n)$
- 空间复杂度:$O(n)$或$O(1)$,取决于使用的语言提供的字符串类是否提供了类似「入栈」和「出栈」的接口。
function removeDuplicates(s: string): string {
const stack: string[] = [];
for (let str of s) {
if (stack[stack.length - 1] === str) {
stack.pop();
} else {
stack.push(str);
}
}
return stack.join("");
};
0150.逆波兰表达式求值
根据 逆波兰表示法,求表达式的值。
有效的运算符包括 + , - , * , / 。每个运算对象可以是整数,也可以是另一个逆波兰表达式。
说明:
整数除法只保留整数部分。 给定逆波兰表达式总是有效的。换句话说,表达式总会得出有效数值且不存在除数为 0 的情况。
示例 1:
- 输入: ["2", "1", "+", "3", " * "]
- 输出: 9
- 解释: 该算式转化为常见的中缀算术表达式为:((2 + 1) * 3) = 9
示例 2:
- 输入: ["4", "13", "5", "/", "+"]
- 输出: 6
- 解释: 该算式转化为常见的中缀算术表达式为:(4 + (13 / 5)) = 6
示例 3:
输入: ["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 + 2 ) * ( 3 + 4 ) 。
该算式的逆波兰表达式写法为 ( ( 1 2 + ) ( 3 4 + ) * ) 。
逆波兰表达式主要有以下两个优点:
- 去掉括号后表达式无歧义,上式即便写成 1 2 + 3 4 + * 也可以依据次序计算出正确结果。
- 适合用栈操作运算:遇到数字则入栈;遇到运算符则取出栈顶两个数字进行计算,并将结果压入栈中。
栈
- 时间复杂度:$O(n)$,其中 $n$ 是数组 tokens 的长度。
- 空间复杂度:$O(n)$,其中 $n$ 是数组 tokens 的长度。
function evalRPN(tokens: string[]): number {
const stack: number[] = [];
for (let token of tokens) {
switch (token) {
case '+':
stack.unshift(stack.shift() + stack.shift());
break;
case '-':
let sub = stack.shift();
stack.unshift(stack.shift() - sub);
break;
case '*':
stack.unshift(stack.shift() * stack.shift());
break;
case '/':
let divided = stack.shift()
let res = stack.shift() / divided;
stack.unshift(res > 0 ? Math.floor(res) : Math.ceil(res));
break;
default:
stack.unshift(Number(token));
}
}
return stack.shift();
};
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]
提示:
1 <= nums.length <= 105
-104 <= nums[i] <= 104
1 <= k <= nums.length
单调队列
双端队列(Deque,全称double-ended queue)是一种具有队列和栈的性质的数据结构。双端队列的元素可以从两端弹出,其限制插入和删除操作在表的两端进行。这意味着你可以在其前端以及后端进行插入和删除操作。
双端队列就像是一个队列和栈的结合体,结合了它们的一些功能。你可以将元素添加或删除到队列的前面或后面,就像在栈中一样。
当双端队列用来维护滑动窗口中的最大值或最小值时,我们通常将其称为单调队列。在这种情况下,双端队列将始终保持单调递增或递减的顺序。新元素从队列一端加入,在另一端移出。为了保持队列的单调性,有些元素可能会在其正常出队前就被提前移出。因此,双端队列在此应用中也被称为单调双端队列。
- 时间复杂度:$O(n)$,其中 n 是数组 $nums$ 的长度。
- 空间复杂度:$O(k)$。
function maxSlidingWindow(nums: number[], k: number): number[] {
if (nums.length === 0) return [];
const res: number[] = [];
const deque: number[] = [];
for (let i = 0; i < k; i++) {
while (deque.length !== 0 && deque[deque.length - 1] < nums[i]) {
deque.pop();
}
deque.push(nums[i]);
}
res.push(deque[0]);
for (let i = k; i < nums.length; i++) {
if (nums[i - k] === deque[0]) {
deque.shift();
}
while (deque.length !== 0 && deque[deque.length - 1] < nums[i]) {
deque.pop();
}
deque.push(nums[i]);
res.push(deque[0]);
}
return res;
};
347.前K个高频元素
给定一个非空的整数数组,返回其中出现频率前 k 高的元素。
示例 1:
- 输入: nums = [1,1,1,2,2,3], k = 2
- 输出: [1,2]
示例 2:
- 输入: nums = [1], k = 1
- 输出: [1]
提示:
- 你可以假设给定的 k 总是合理的,且 1 ≤ k ≤ 数组中不相同的元素的个数。
- 你的算法的时间复杂度必须优于 $O(n longn)$ , n 是数组的大小。
- 题目数据保证答案唯一,换句话说,数组中前 k 个高频元素的集合是唯一的。
- 你可以按任意顺序返回答案。
哈希表+优先队列
优先级队列是一种抽象数据类型,它类似于一个常规的队列或栈数据结构,但每个元素都有一定的关联优先级。在优先级队列中,元素被赋予优先级。当访问元素时,具有最高优先级的元素首先被删除。当两个元素具有相同优先级时,按照它们在队列中的顺序进行访问。优先级队列在许多算法中都有应用,包括Dijkstra's algorithm和heap sort。
优先级队列通常使用堆(Heap)数据结构来实现,但也可以使用其他数据结构,如有序数组、有序链表、平衡树等。在堆的实现中,元素可以在O(1)时间内获取(查看)最大/最小元素,而删除最大元素和插入新元素则需要O(log n)的时间。其中,n是队列中的元素数量。
- 时间复杂度:$O(Nlogk)$,其中 N 为数组的长度。由于堆的大小至多为 k,因此每次堆操作需要 $O(log k)$的时间。
- 空间复杂度:$O(N)$。哈希表的大小为$O(N)$,而堆的大小为$O(k)$,共计为$O(N)$。
class MiniHeap {
private heap: [number, number][] = [[0, 0]];
getHeap() {
return this.heap;
}
swap(i1: number, i2: number) {
[this.heap[i1], this.heap[i2]] = [this.heap[i2], this.heap[i1]];
}
getParentIndex(i: number) {
return Math.floor(i / 2);
}
getLeftIndex(i: number) {
return 2 * i;
}
getRightIndex(i: number) {
return 2 * i + 1;
}
swim(index: number) {
if (index === 1) return;
const parentIndex = this.getParentIndex(index);
if (this.heap[parentIndex][1] > this.heap[index][1]) {
this.swap(parentIndex, index);
this.swim(parentIndex);
}
}
sink(index: number) {
const leftIndex = this.getLeftIndex(index);
const rightIndex = this.getRightIndex(index);
if (this.heap[leftIndex] && this.heap[leftIndex][1] < this.heap[index][1]) {
this.swap(leftIndex, index);
this.sink(leftIndex);
}
if (this.heap[rightIndex] && this.heap[rightIndex][1] < this.heap[index][1]) {
this.swap(rightIndex, index);
this.sink(rightIndex);
}
}
insert(value: [number, number]) {
this.heap.push(value);
this.swim(this.heap.length - 1);
}
pop() {
if (this.size() === 1) return this.heap.splice(1, 1)[0];
const top = this.heap[1];
this.heap[1] = this.heap.pop();
this.sink(1);
return top;
}
peek() {
return this.heap[1];
}
size() {
return this.heap.length - 1;
}
}
function topKFrequent(nums: number[], k: number): number[] {
const map = new Map<number, number>();
for (let i = 0; i < nums.length; i++) {
map.set(nums[i], map.has(nums[i]) ? map.get(nums[i]) + 1 : 1);
}
const heap = new MiniHeap();
for (let [key, value] of map.entries()) {
heap.insert([key, value]);
if (heap.size() > k) {
heap.pop();
}
}
return heap.getHeap().slice(1).map(item => item[0]);
};
二叉树
144.二叉树的前序遍历
给定一个二叉树的根节点
root
,返回 它的 前序 遍历 。示例1:
输入:root = [1,null,2,3] 输出:[1,2,3]
示例 2:
输入:root = [] 输出:[]
示例 3:
输入:root = [1] 输出:[1]
递归
- 时间复杂度:$O(n)$,其中 $n$ 是二叉树的节点数。
- 空间复杂度:$O(n)$,为递归过程中栈的开销,平均情况下为 $O(log n)$,最坏情况下树呈现链栈,为 $O(n)$。
/**
* Definition for a binary tree node.
* class TreeNode {
* val: number
* left: TreeNode | null
* right: TreeNode | null
* constructor(val?: number, left?: TreeNode | null, right?: TreeNode | null) {
* this.val = (val===undefined ? 0 : val)
* this.left = (left===undefined ? null : left)
* this.right = (right===undefined ? null : right)
* }
* }
*/
function preorderTraversal(root: TreeNode | null): number[] {
if (root === null) return;
let res = [];
res.push(root.val);
res = res.concat(preorderTraversal(root.left));
res = res.concat(preorderTraversal(root.right));
return res;
};
迭代
迭代与递归的区别在于递归的时候隐式地维护了一个栈,而迭代需要显式将这个栈模拟出来。
- 时间复杂度:$O(n)$,其中 $n$ 是二叉树的节点数。
- 空间复杂度:$O(n)$,为递归过程中栈的开销,平均情况下为 $O(log n)$,最坏情况下树呈现链栈,为 $O(n)$。
/**
* Definition for a binary tree node.
* class TreeNode {
* val: number
* left: TreeNode | null
* right: TreeNode | null
* constructor(val?: number, left?: TreeNode | null, right?: TreeNode | null) {
* this.val = (val===undefined ? 0 : val)
* this.left = (left===undefined ? null : left)
* this.right = (right===undefined ? null : right)
* }
* }
*/
function preorderTraversal(root: TreeNode | null): number[] {
const stack: TreeNode[] = [];
const res: number[] = [];
stack.push(root);
while (stack.length > 0) {
let temp = stack.pop();
res.push(temp.val);
if (temp.right !== null) {
stack.push(temp.right);
}
if (temp.left !== null) {
stack.push(temp.left);
}
console.log(stack.length)
}
return res;
};
Morris遍历
- 时间复杂度:$O(n)$,其中 $n$ 是二叉树的节点数。没有左子树的节点只被访问依次,有左子树的节点被访问两次。
- 空间复杂度:$O(1)$。只操作已经存在的指针,因此只需要常数的额外空间。
/**
* Definition for a binary tree node.
* class TreeNode {
* val: number
* left: TreeNode | null
* right: TreeNode | null
* constructor(val?: number, left?: TreeNode | null, right?: TreeNode | null) {
* this.val = (val===undefined ? 0 : val)
* this.left = (left===undefined ? null : left)
* this.right = (right===undefined ? null : right)
* }
* }
*/
function preorderTraversal(root: TreeNode | null): number[] {
if (root === null) return;
let cur1: TreeNode = root;
let cur2: TreeNode = null;
const res: number[] = [];
while (cur1 !== null) {
cur2 = cur1.left;
if (cur2 !== null) {
while (cur2.right !== null && cur2.right !== cur1) {
cur2 = cur2.right;
}
if (cur2.right === null) {
cur2.right = cur1;
res.push(cur1.val);
cur1 = cur1.left;
continue;
} else {
cur2.right = null;
}
} else {
res.push(cur1.val);
}
cur1 = cur1.right;
}
return res;
};
颜色标记法
其核心思想如下:
使用颜色标记节点的状态,新节点为白色,已访问的节点为灰色。
如果遇到的节点为白色,则将其标记为灰色,然后将其右子节点、自身、左子节点依次入栈。
如果遇到的节点为灰色,则将节点的值输出。
/**
* Definition for a binary tree node.
* class TreeNode {
* val: number
* left: TreeNode | null
* right: TreeNode | null
* constructor(val?: number, left?: TreeNode | null, right?: TreeNode | null) {
* this.val = (val===undefined ? 0 : val)
* this.left = (left===undefined ? null : left)
* this.right = (right===undefined ? null : right)
* }
* }
*/
function preorderTraversal(root: TreeNode | null): number[] {
const WHITE = 0, GRAY = 1;
const res: number[] = [];
const stack: [number, TreeNode][] = [[WHITE, root]];
while (stack.length > 0) {
const [color, node] = stack.pop();
if (node === null) continue;
if (color === WHITE) {
stack.push([WHITE, node.right]);
stack.push([WHITE, node.left]);
stack.push([GRAY, node]);
} else {
res.push(node.val);
}
}
return res;
};
94.二叉树的中序遍历
给定一个二叉树的根节点
root
,返回 它的 中序 遍历 。示例1:
输入:root = [1,null,2,3] 输出:[1,3,2]
示例 2:
输入:root = [] 输出:[]
示例 3:
输入:root = [1] 输出:[1]
递归
/**
* Definition for a binary tree node.
* class TreeNode {
* val: number
* left: TreeNode | null
* right: TreeNode | null
* constructor(val?: number, left?: TreeNode | null, right?: TreeNode | null) {
* this.val = (val===undefined ? 0 : val)
* this.left = (left===undefined ? null : left)
* this.right = (right===undefined ? null : right)
* }
* }
*/
function inorderTraversal(root: TreeNode | null): number[] {
if (root === null) return [];
let res: number[] = [];
res = res.concat(inorderTraversal(root.left));
res.push(root.val);
res = res.concat(inorderTraversal(root.right));
return res;
};
迭代
/**
* Definition for a binary tree node.
* class TreeNode {
* val: number
* left: TreeNode | null
* right: TreeNode | null
* constructor(val?: number, left?: TreeNode | null, right?: TreeNode | null) {
* this.val = (val===undefined ? 0 : val)
* this.left = (left===undefined ? null : left)
* this.right = (right===undefined ? null : right)
* }
* }
*/
function inorderTraversal(root: TreeNode | null): number[] {
let res: number[] = [];
let stack: TreeNode[] = [];
while (stack.length > 0 || root !== null) {
while (root !== null) {
stack.push(root);
root = root.left;
}
root = stack.pop();
res.push(root.val);
root = root.right;
}
return res;
};
颜色标记法
/**
* Definition for a binary tree node.
* class TreeNode {
* val: number
* left: TreeNode | null
* right: TreeNode | null
* constructor(val?: number, left?: TreeNode | null, right?: TreeNode | null) {
* this.val = (val===undefined ? 0 : val)
* this.left = (left===undefined ? null : left)
* this.right = (right===undefined ? null : right)
* }
* }
*/
function inorderTraversal(root: TreeNode | null): number[] {
const WHITE = 0, GRAY = 1;
const res: number[] = [];
const stack: [number, TreeNode][] = [[WHITE, root]];
while (stack.length > 0) {
const [color, node] = stack.pop();
if (node === null) continue;
if (color === WHITE) {
stack.push([WHITE, node.right]);
stack.push([GRAY, node]);
stack.push([WHITE, node.left]);
} else {
res.push(node.val);
}
}
return res;
};
145.二叉树的后序遍历
给定一个二叉树的根节点
root
,返回 它的 后序 遍历 。示例1:
输入:root = [1,null,2,3] 输出:[3,2,1]
示例 2:
输入:root = [] 输出:[]
示例 3:
输入:root = [1] 输出:[1]
递归
/**
* Definition for a binary tree node.
* class TreeNode {
* val: number
* left: TreeNode | null
* right: TreeNode | null
* constructor(val?: number, left?: TreeNode | null, right?: TreeNode | null) {
* this.val = (val===undefined ? 0 : val)
* this.left = (left===undefined ? null : left)
* this.right = (right===undefined ? null : right)
* }
* }
*/
function postorderTraversal(root: TreeNode | null): number[] {
if (root === null) return [];
let res: number[] = [];
res = res.concat(postorderTraversal(root.left));
res = res.concat(postorderTraversal(root.right));
res.push(root.val);
return res;
};
颜色标记法
/**
* Definition for a binary tree node.
* class TreeNode {
* val: number
* left: TreeNode | null
* right: TreeNode | null
* constructor(val?: number, left?: TreeNode | null, right?: TreeNode | null) {
* this.val = (val===undefined ? 0 : val)
* this.left = (left===undefined ? null : left)
* this.right = (right===undefined ? null : right)
* }
* }
*/
function postorderTraversal(root: TreeNode | null): number[] {
const WHITE = 0, GRAY = 1;
const res: number[] = [];
const stack: [number, TreeNode][] = [[WHITE, root]];
while (stack.length > 0) {
const [color, node] = stack.pop();
if (node === null) {
continue;
}
if (color === WHITE) {
stack.push([GRAY, node]);
stack.push([WHITE, node.right]);
stack.push([WHITE, node.left]);
} else {
res.push(node.val);
}
}
return res;
};
102.二叉树的层序遍历
给你二叉树的根节点
root
,返回其节点值的 层序遍历 。 (即逐层地,从左到右访问所有节点)。
BFS
使用队列维护节点。
- 时间复杂度:每个点进队出队各一次,故复杂度为$O(n)$。
- 空间复杂度:队列中元素的个数不超过 $n$ 个,故复杂度为$O(n)$。
/**
* Definition for a binary tree node.
* class TreeNode {
* val: number
* left: TreeNode | null
* right: TreeNode | null
* constructor(val?: number, left?: TreeNode | null, right?: TreeNode | null) {
* this.val = (val===undefined ? 0 : val)
* this.left = (left===undefined ? null : left)
* this.right = (right===undefined ? null : right)
* }
* }
*/
function levelOrder(root: TreeNode | null): number[][] {
if (root === null) return [];
const queue: TreeNode[] = [root];
const res: number[][] = [];
while (queue.length > 0) {
let n = queue.length;
const temp: number[] = [];
for (let i = 0; i < n; i++) {
let node = queue.shift();
temp.push(node.val);
if (node.left !== null) {
queue.push(node.left);
}
if (node.right !== null) {
queue.push(node.right);
}
}
res.push(temp);
}
return res;
};
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]
BFS-迭代
用一个队列来临时存放需要遍历到的元素。
- 时间复杂度:$O(N)$,每个节点需要入队/出队一次。
- 空间复杂度:$O(N)$。
/**
* Definition for a binary tree node.
* class TreeNode {
* val: number
* left: TreeNode | null
* right: TreeNode | null
* constructor(val?: number, left?: TreeNode | null, right?: TreeNode | null) {
* this.val = (val===undefined ? 0 : val)
* this.left = (left===undefined ? null : left)
* this.right = (right===undefined ? null : right)
* }
* }
*/
function invertTree(root: TreeNode | null): TreeNode | null {
if (root === null) return null;
let queue: TreeNode[] = [root];
while (queue.length !== 0) {
let node = queue.shift();
if (node.left) {
queue.push(node.left);
}
if (node.right) {
queue.push(node.right);
}
[node.left, node.right] = [node.right, node.left];
}
return root;
};
DFS-递归
- 时间复杂度:$O(N)$,每个元素都必须访问一次。
- 空间复杂度:$O(N)$。使用的空间由递归栈的深度决定,它等于当前节点在二叉树中的高度。在平均情况下,二叉树的高度与节点个数为对数关系,即$O(log N)$。而在最坏情况下,树形成链状,空间复杂度为$O(N)$。
/**
* Definition for a binary tree node.
* class TreeNode {
* val: number
* left: TreeNode | null
* right: TreeNode | null
* constructor(val?: number, left?: TreeNode | null, right?: TreeNode | null) {
* this.val = (val===undefined ? 0 : val)
* this.left = (left===undefined ? null : left)
* this.right = (right===undefined ? null : right)
* }
* }
*/
function invertTree(root: TreeNode | null): TreeNode | null {
if (root === null) return null;
if (root.left) invertTree(root.left);
if (root.right) invertTree(root.right);
[root.left, root.right] = [root.right, root.left];
return root;
};
100.相同的树
给你两棵二叉树的根节点
p
和q
,编写一个函数来检验这两棵树是否相同。如果两个树在结构上相同,并且节点具有相同的值,则认为它们是相同的。
DFS
- 时间复杂度:$O(min(m,n))$,其中 m 和 n 分别是两个二叉树的节点数。对两个二叉树同时进行深度优先搜索,只有当两个二叉树中的对应节点都不为空时才会访问到该节点,因此被访问的节点数不会超过较小的二叉树的节点数。
- 空间复杂度:$O(min(m,n))$,其中 m 和 n 分别是两个二叉树的节点数。空间复杂度取决于递归调用的层数,递归调用的层数不会超过较小的二叉树的最大高度,最坏情况下,二叉树的高度等于节点数。
/**
* Definition for a binary tree node.
* class TreeNode {
* val: number
* left: TreeNode | null
* right: TreeNode | null
* constructor(val?: number, left?: TreeNode | null, right?: TreeNode | null) {
* this.val = (val===undefined ? 0 : val)
* this.left = (left===undefined ? null : left)
* this.right = (right===undefined ? null : right)
* }
* }
*/
function isSameTree(p: TreeNode | null, q: TreeNode | null): boolean {
if (p === null && q === null) return true;
if (p === null || q === null) return false;
return p.val === q.val && isSameTree(p.left, q.left) && isSameTree(p.right, q.right);
};
101.对称二叉树
给你一个二叉树的根节点
root
, 检查它是否轴对称。示例 1:
输入:root = [1,2,2,3,4,4,3] 输出:true
示例 2:
输入:root = [1,2,2,null,3,null,3] 输出:false
递归
- 时间复杂度:$O(N)$,遍历整棵树。
- 空间复杂度:$O(N)$,空间复杂度与递归使用的栈空间有关,递归层树不超过n。
/**
* Definition for a binary tree node.
* class TreeNode {
* val: number
* left: TreeNode | null
* right: TreeNode | null
* constructor(val?: number, left?: TreeNode | null, right?: TreeNode | null) {
* this.val = (val===undefined ? 0 : val)
* this.left = (left===undefined ? null : left)
* this.right = (right===undefined ? null : right)
* }
* }
*/
function check(p: TreeNode, q: TreeNode): boolean {
if (p === null && q === null) return true;
if (p === null || q === null) return false;
return p.val === q.val && check(p.left, q.right) && check(p.right, q.left);
}
function isSymmetric(root: TreeNode | null): boolean {
if (root === null) return;
return check(root.left, root.right);
};
迭代
用一个队列来维护节点,一次取出两个节点进行比较。
- 时间复杂度:$O(N)$。
- 空间复杂度:这里需要用一个队列来维护节点,每个节点最多进队一次,出队一次,队列中最多不会超过n个点,故为$O(N)$。
/**
* Definition for a binary tree node.
* class TreeNode {
* val: number
* left: TreeNode | null
* right: TreeNode | null
* constructor(val?: number, left?: TreeNode | null, right?: TreeNode | null) {
* this.val = (val===undefined ? 0 : val)
* this.left = (left===undefined ? null : left)
* this.right = (right===undefined ? null : right)
* }
* }
*/
function isSymmetric(root: TreeNode | null): boolean {
const queue: TreeNode[] = [root, root];
while (queue.length !== 0) {
const u = queue.shift();
const v = queue.shift();
if (u === null && v === null) continue;
if ((u === null || v === null) || (u.val !== v.val)) return false;
queue.push(u.left);
queue.push(v.right);
queue.push(u.right);
queue.push(v.left);
}
return true;
};
104.二叉树的最大深度
给定一个二叉树,找出其最大深度。
二叉树的深度为根节点到最远叶子节点的最长路径上的节点数。
说明: 叶子节点是指没有子节点的节点。
示例: 给定二叉树 [3,9,20,null,null,15,7],
3 / \ 9 20 / \ 15 7
返回它的最大深度 3 。
DFS-递归
- 时间复杂度:$O(n)$,其中n为二叉树的个数。每个节点在递归中只被遍历一次。
- 空间复杂度:$O(height)$,其中 $height$ 表示二叉树的高度。递归函数需要栈空间,而栈空间取决于递归的深度,因此空间复杂度等于二叉树的高度。
/**
* Definition for a binary tree node.
* class TreeNode {
* val: number
* left: TreeNode | null
* right: TreeNode | null
* constructor(val?: number, left?: TreeNode | null, right?: TreeNode | null) {
* this.val = (val===undefined ? 0 : val)
* this.left = (left===undefined ? null : left)
* this.right = (right===undefined ? null : right)
* }
* }
*/
function maxDepth(root: TreeNode | null, level = 1): number {
if (root === null) return 0;
if (root.left === null && root.right === null) return level;
let leftLevel = 0;
let rightLevel = 0;
if (root.left) {
leftLevel = maxDepth(root.left, level + 1);
}
if (root.right) {
rightLevel = maxDepth(root.right, level + 1);
}
level = Math.max(leftLevel, rightLevel);
return level;
};
BFS-迭代
- 时间复杂度:$O(n)$,其中 n 为二叉树的节点个数。与方法一同样的分析,每个节点只会被访问一次。
- 空间复杂度:此方法空间的消耗取决于队列存储的元素数量,其在最坏情况下会达到 $O(n)$。
/**
* Definition for a binary tree node.
* class TreeNode {
* val: number
* left: TreeNode | null
* right: TreeNode | null
* constructor(val?: number, left?: TreeNode | null, right?: TreeNode | null) {
* this.val = (val===undefined ? 0 : val)
* this.left = (left===undefined ? null : left)
* this.right = (right===undefined ? null : right)
* }
* }
*/
function maxDepth(root: TreeNode | null): number {
if (root === null) return 0;
const queue: TreeNode[] = [root];
let ans = 0;
while (queue.length > 0) {
let size = queue.length;
while (size > 0) {
const node = queue.shift();
if (node.left) queue.push(node.left);
if (node.right) queue.push(node.right);
size -= 1;
}
ans += 1;
}
return ans;
};
111.二叉树的最小深度
给定一个二叉树,找出其最小深度。
最小深度是从根节点到最近叶子节点的最短路径上的节点数量。
**说明:**叶子节点是指没有子节点的节点。
示例 1:
输入:root = [3,9,20,null,null,15,7] 输出:2
示例 2:
输入:root = [2,null,3,null,4,null,5,null,6] 输出:5
DFS-递归
与上一题是同样的套路。
- 时间复杂度:$O(N)$,其中 N 是数的节点数。对每个节点访问一次。
- 空间复杂度:$O(H)$,其中 H 是树的高度。空间复杂度主要取决于递归时栈空间的开销,最坏情况下,树呈现链状,空间复杂度为$O(N)$。平均情况下树的高度与节点数的对数正相关,空间复杂度为$O(logN)$。
/**
* Definition for a binary tree node.
* class TreeNode {
* val: number
* left: TreeNode | null
* right: TreeNode | null
* constructor(val?: number, left?: TreeNode | null, right?: TreeNode | null) {
* this.val = (val===undefined ? 0 : val)
* this.left = (left===undefined ? null : left)
* this.right = (right===undefined ? null : right)
* }
* }
*/
function minDepth(root: TreeNode | null, level = 1): number {
if (root === null) return 0;
if (root.left === null && root.right === null) return level;
let leftLevel = Infinity;
let rightLevel = Infinity;
if (root.left) {
leftLevel = minDepth(root.left, level + 1);
}
if (root.right) {
rightLevel = minDepth(root.right, level + 1);
}
level = Math.min(leftLevel, rightLevel);
return level;
};
BFS-迭代
- 时间复杂度:$O(N)$,其中 N 是树的节点数。对每个节点访问一次。
- 空间复杂度:$O(N)$,其中 N 是树的节点数。空间复杂度主要取决于队列的开销,队列中的元素个数不会超过树的节点数。
/**
* Definition for a binary tree node.
* class TreeNode {
* val: number
* left: TreeNode | null
* right: TreeNode | null
* constructor(val?: number, left?: TreeNode | null, right?: TreeNode | null) {
* this.val = (val===undefined ? 0 : val)
* this.left = (left===undefined ? null : left)
* this.right = (right===undefined ? null : right)
* }
* }
*/
function minDepth(root: TreeNode | null): number {
if (root === null) return 0;
const queue: TreeNode[] = [root];
let ans = 1;
while (queue.length > 0) {
let size = queue.length;
while (size > 0) {
const node = queue.shift();
if (node.left) queue.push(node.left);
if (node.right) queue.push(node.right);
size -= 1;
if (node.left === null && node.right === null) {
return ans;
}
}
ans += 1;
}
};
222.完全二叉树的节点个数
给你一棵 完全二叉树 的根节点 root ,求出该树的节点个数。
完全二叉树 的定义如下:在完全二叉树中,除了最底层节点可能没填满外,其余每层节点数都达到最大值,并且最下面一层的节点都集中在该层最左边的若干位置。若最底层为第 h 层,则该层包含 1~ 2h 个节点。
示例 1:
输入:root = [1,2,3,4,5,6] 输出:6
示例 2:
输入:root = [] 输出:0
示例 3:
输入:root = [1] 输出:1
满二叉树+递归
思路:利用满二叉树的特性,判断左右子树如果深度相同,则直接返回$2^h-1$(可以利用位移特性)。否则继续递归传入左右子节点并加+1,继续计算子树的节点,也是利用满二叉树的特性。
- 时间复杂度:$O(logn * logn)$。
- 空间复杂度:$O(logn)$。
/**
* Definition for a binary tree node.
* class TreeNode {
* val: number
* left: TreeNode | null
* right: TreeNode | null
* constructor(val?: number, left?: TreeNode | null, right?: TreeNode | null) {
* this.val = (val===undefined ? 0 : val)
* this.left = (left===undefined ? null : left)
* this.right = (right===undefined ? null : right)
* }
* }
*/
function countNodes(root: TreeNode | null): number {
if (root === null) return 0;
let leftCount = 0;
let rightCount = 0;
let leftNode = root.left;
let rightNode= root.right;
while (leftNode) {
leftNode = leftNode.left;
leftCount++;
}
while (rightCount) {
rightNode = rightNode.right;
rightCount++;
}
if (leftCount === rightCount) {
return (2 << leftCount) - 1;
}
return countNodes(root.left) + countNodes(root.right) + 1;
};
110.平衡二叉树
xxxx
自底向上递归
自底向上使用后序遍历。
- 时间复杂度:$O(n)$,其中 n 是二叉树中的节点个数。使用自底向上的递归,每个节点的计算高度和判断是否平衡都只需要处理一次,最坏情况下需要遍历二叉树中的所有节点,因此时间复杂度是$O(n)$。
- 空间复杂度:$O(n)$,其中 n 是二叉树中的节点个数。空间复杂度主要取决于递归调用的层树,递归调用的层树不会超过 n。
/**
* Definition for a binary tree node.
* class TreeNode {
* val: number
* left: TreeNode | null
* right: TreeNode | null
* constructor(val?: number, left?: TreeNode | null, right?: TreeNode | null) {
* this.val = (val===undefined ? 0 : val)
* this.left = (left===undefined ? null : left)
* this.right = (right===undefined ? null : right)
* }
* }
*/
function height(root: TreeNode): number {
if (root === null) return 0;
let leftHeight = height(root.left);
let rightHeight = height(root.right);
if (leftHeight === -1 || rightHeight === -1 || Math.abs(leftHeight - rightHeight) > 1) {
return -1
} else {
return Math.max(leftHeight, rightHeight) + 1;
}
}
function isBalanced(root: TreeNode | null): boolean {
return height(root) >= 0;
};
257.二叉树的所有路径
给你一个二叉树的根节点
root
,按 任意顺序 ,返回所有从根节点到叶子节点的路径。叶子节点 是指没有子节点的节点。
示例 1:
输入:root = [1,2,3,null,5] 输出:["1->2->5","1->3"]
示例 2:
输入:root = [1] 输出:["1"]
DFS-前序遍历-递归-回溯
/**
* Definition for a binary tree node.
* class TreeNode {
* val: number
* left: TreeNode | null
* right: TreeNode | null
* constructor(val?: number, left?: TreeNode | null, right?: TreeNode | null) {
* this.val = (val===undefined ? 0 : val)
* this.left = (left===undefined ? null : left)
* this.right = (right===undefined ? null : right)
* }
* }
*/
function binaryTreePaths(root: TreeNode | null, path: number[] = []): string[] {
if (root === null) return [];
path = path.concat([root.val]);
if (root.left === null && root.right === null) {
return [path.join("->")];
}
let leftPath: string[] = [];
let rightPath: string[] = [];
if (root.left) {
leftPath = binaryTreePaths(root.left, path);
}
if (root.right) {
rightPath = binaryTreePaths(root.right, path);
}
return leftPath.concat(rightPath);
};
404.左叶子之和
给定二叉树的根节点
root
,返回所有左叶子之和。示例 1:
输入: root = [3,9,20,null,null,15,7] 输出: 24 解释: 在这个二叉树中,有两个左叶子,分别是 9 和 15,所以返回 24
示例 2:
输入: root = [1] 输出: 0
DFS-递归
- 时间复杂度:$O(n)$,其中 n 是树中的节点个数。
- 空间复杂度:$O(n)$。空间复杂度与深度优先搜索使用的栈的最大深度相关。在最坏的情况下,树呈现链式结构,深度为 $O(n)$,对应的空间复杂度也为 $O(n)$。
/**
* Definition for a binary tree node.
* class TreeNode {
* val: number
* left: TreeNode | null
* right: TreeNode | null
* constructor(val?: number, left?: TreeNode | null, right?: TreeNode | null) {
* this.val = (val===undefined ? 0 : val)
* this.left = (left===undefined ? null : left)
* this.right = (right===undefined ? null : right)
* }
* }
*/
function sumOfLeftLeaves(root: TreeNode | null, isLeft = false): number {
if (root === null) return 0;
if (root.left === null && root.right === null) {
if (isLeft) return root.val;
else {
return 0;
}
}
let sum = 0;
if (root.left) {
sum += sumOfLeftLeaves(root.left, true);
}
if (root.right) {
sum += sumOfLeftLeaves(root.right, false);
}
return sum;
};
BFS-队列
/**
* Definition for a binary tree node.
* class TreeNode {
* val: number
* left: TreeNode | null
* right: TreeNode | null
* constructor(val?: number, left?: TreeNode | null, right?: TreeNode | null) {
* this.val = (val===undefined ? 0 : val)
* this.left = (left===undefined ? null : left)
* this.right = (right===undefined ? null : right)
* }
* }
*/
function isLeafNode(node: TreeNode) {
return node.left === null && node.right === null;
}
function sumOfLeftLeaves(root: TreeNode | null): number {
if (root === null) return 0;
const queue: TreeNode[] = [root];
let sum = 0;
while (queue.length > 0) {
let node = queue.shift();
if (node.left) {
if (isLeafNode(node.left)) {
sum += node.left.val;
}
else {
queue.push(node.left);
}
}
if (node.right) {
queue.push(node.right);
}
}
return sum;
};
513.找树左下角的值
给定一个二叉树的 根节点
root
,请找出该二叉树的 最底层 最左边 节点的值。假设二叉树中至少有一个节点。
示例 1:
输入: root = [2,1,3] 输出: 1
示例 2:
输入: [1,2,3,4,null,5,6,null,null,7] 输出: 7
BFS-层序遍历-队列
- 时间复杂度:$O(n)$,其中 n 是二叉树的节点数目。
- 空间复杂度:$O(n)$。如果二叉树是满完全二叉树,那么队列 q 最多保存 $[n/2]$ 个节点。
/**
* Definition for a binary tree node.
* class TreeNode {
* val: number
* left: TreeNode | null
* right: TreeNode | null
* constructor(val?: number, left?: TreeNode | null, right?: TreeNode | null) {
* this.val = (val===undefined ? 0 : val)
* this.left = (left===undefined ? null : left)
* this.right = (right===undefined ? null : right)
* }
* }
*/
function isLeafNode(root: TreeNode) {
return root.left === null && root.right === null;
}
function findBottomLeftValue(root: TreeNode | null): number {
if (root === null) return root.val;
const queue: TreeNode[] = [root];
let res = 0;
while (queue.length > 0) {
let size = queue.length;
let isRecord = false;
while (size > 0) {
let node = queue.shift();
if (isLeafNode(node) && !isRecord) {
res = node.val;
isRecord = true;
}
if (node.left) {
queue.push(node.left);
}
if (node.right) {
queue.push(node.right);
}
size--;
}
}
return res;
};
112.路径总和
给你二叉树的根节点 root 和一个表示目标和的整数 targetSum 。判断该树中是否存在 根节点到叶子节点 的路径,这条路径上所有节点值相加等于目标和 targetSum 。如果存在,返回 true ;否则,返回 false 。
叶子节点 是指没有子节点的节点。
示例 1:
输入:root = [5,4,8,11,null,13,4,7,2,null,null,null,1], targetSum = 22 输出:true 解释:等于目标和的根节点到叶节点路径如上图所示。
DFS+递归
- 时间复杂度:$O(N)$,其中 N 是树的节点数。对每个节点访问一次。
- 空间复杂度:$O(H)$,其中 H 是树的高度。空间复杂度主要取决于递归时栈空间的开销,最坏情况下,树呈现链状,空间复杂度为$O(N)$。平均情况下树的高度与节点数的对数正相关,空间复杂度为$O(logN)$。
/**
* Definition for a binary tree node.
* class TreeNode {
* val: number
* left: TreeNode | null
* right: TreeNode | null
* constructor(val?: number, left?: TreeNode | null, right?: TreeNode | null) {
* this.val = (val===undefined ? 0 : val)
* this.left = (left===undefined ? null : left)
* this.right = (right===undefined ? null : right)
* }
* }
*/
function hasPathSum(root: TreeNode | null, targetSum: number): boolean {
if (root === null) return false;
targetSum = targetSum - root.val;
if (root.left === null && root.right === null) {
return targetSum === 0;
}
return hasPathSum(root.left, targetSum) || hasPathSum(root.right, targetSum);
};
BFS-层序遍历-双队列
- 时间复杂度:$O(N)$,其中 N 是树的节点数。对每一个节点访问一次。
- 空间复杂度:$O(N)$,其中 N 是树的节点数。空间复杂度主要取决于队列的开销,队列中的元素个数不会超过树的节点数。
/**
* Definition for a binary tree node.
* class TreeNode {
* val: number
* left: TreeNode | null
* right: TreeNode | null
* constructor(val?: number, left?: TreeNode | null, right?: TreeNode | null) {
* this.val = (val===undefined ? 0 : val)
* this.left = (left===undefined ? null : left)
* this.right = (right===undefined ? null : right)
* }
* }
*/
function hasPathSum(root: TreeNode | null, targetSum: number): boolean {
if (root === null) return false;
const nodeQueue: TreeNode[] = [root];
const valQueue: number[] = [root.val];
while (nodeQueue.length > 0) {
let node = nodeQueue.shift();
let nodeVal = valQueue.shift();
if (node.left === null && node.right === null && nodeVal === targetSum) return true;
if (node.left) {
nodeQueue.push(node.left);
valQueue.push(nodeVal + node.left.val);
}
if (node.right) {
nodeQueue.push(node.right);
valQueue.push(nodeVal + node.right.val);
}
}
return false;
};
105.从前序与中序遍历序列构造二叉树
给定两个整数数组
preorder
和inorder
,其中preorder
是二叉树的先序遍历,inorder
是同一棵树的中序遍历,请构造二叉树并返回其根节点。示例 1:
输入: preorder = [3,9,20,15,7], inorder = [9,3,15,20,7] 输出: [3,9,20,null,null,15,7]
示例 2:
输入: preorder = [-1], inorder = [-1] 输出: [-1]
递归
- 时间复杂度:$O(n)$,其中 n 是树中的节点个数。
- 空间复杂度:$O(n)$。我们需要使用 $O(n)$的空间存储哈希表,以及 $O(h)$的空间表示递归时栈空间。这里 $h<m$, 所以总空间复杂度为 $O(n)$。
/**
* Definition for a binary tree node.
* class TreeNode {
* val: number
* left: TreeNode | null
* right: TreeNode | null
* constructor(val?: number, left?: TreeNode | null, right?: TreeNode | null) {
* this.val = (val===undefined ? 0 : val)
* this.left = (left===undefined ? null : left)
* this.right = (right===undefined ? null : right)
* }
* }
*/
function buildTree(preorder: number[], inorder: number[]): TreeNode | null {
let preIndex = 0;
const mapIndex = new Map<number, number>();
inorder.forEach((item, index) => {
mapIndex.set(item, index);
})
const helper = (left: number, right: number): TreeNode | null => {
if (left > right) return null;
const rootVal = preorder[preIndex];
const root = new TreeNode(rootVal);
const index = mapIndex.get(rootVal);
preIndex++;
root.left = helper(left, index - 1);
root.right = helper(index + 1, right);
return root;
}
return helper(0, inorder.length - 1);
};
106.从中序与后序遍历序列构造二叉树
给定两个整数数组 inorder 和 postorder ,其中 inorder 是二叉树的中序遍历, postorder 是同一棵树的后序遍历,请你构造并返回这颗 二叉树 。
示例 1:
输入:inorder = [9,3,15,20,7], postorder = [9,15,7,20,3] 输出:[3,9,20,null,null,15,7]
示例 2:
输入:inorder = [-1], postorder = [-1] 输出:[-1]
递归
- 时间复杂度:$O(n)$,其中 n 是树中的节点个数。
- 空间复杂度:$O(n)$。我们需要使用 $O(n)$的空间存储哈希表,以及 $O(h)$的空间表示递归时栈空间。这里 $h<m$, 所以总空间复杂度为 $O(n)$。
/**
* Definition for a binary tree node.
* class TreeNode {
* val: number
* left: TreeNode | null
* right: TreeNode | null
* constructor(val?: number, left?: TreeNode | null, right?: TreeNode | null) {
* this.val = (val===undefined ? 0 : val)
* this.left = (left===undefined ? null : left)
* this.right = (right===undefined ? null : right)
* }
* }
*/
function buildTree(inorder: number[], postorder: number[]): TreeNode | null {
let postIndex = postorder.length - 1;
const mapIndex = new Map<number, number>();
inorder.forEach((item, index) => {
mapIndex.set(item, index);
})
const helper = (left: number, right: number): TreeNode | null => {
if (left > right) return null;
let rootVal = postorder[postIndex];
const root = new TreeNode(rootVal);
const index = mapIndex.get(rootVal);
postIndex--;
root.right = helper(index + 1, right);
root.left = helper(left, index - 1);
return root;
}
return helper(0, inorder.length - 1);
};
654.最大二叉树
给定一个不重复的整数数组
nums
。 最大二叉树 可以用下面的算法从nums
递归地构建:
- 创建一个根节点,其值为
nums
中的最大值。- 递归地在最大值 左边 的 子数组前缀上 构建左子树。
- 递归地在最大值 右边 的 子数组后缀上 构建右子树。
返回
nums
构建的 最大二叉树 。示例 1:
输入:nums = [3,2,1,6,0,5] 输出:[6,3,5,null,2,0,null,null,1] 解释:递归调用如下所示: - [3,2,1,6,0,5] 中的最大值是 6 ,左边部分是 [3,2,1] ,右边部分是 [0,5] 。 - [3,2,1] 中的最大值是 3 ,左边部分是 [] ,右边部分是 [2,1] 。 - 空数组,无子节点。 - [2,1] 中的最大值是 2 ,左边部分是 [] ,右边部分是 [1] 。 - 空数组,无子节点。 - 只有一个元素,所以子节点是一个值为 1 的节点。 - [0,5] 中的最大值是 5 ,左边部分是 [0] ,右边部分是 [] 。 - 只有一个元素,所以子节点是一个值为 0 的节点。 - 空数组,无子节点。
递归
- 时间复杂度:$O(n^2)$,其中 n 是数组
nums
的长度。在最坏情况下,数组严格递增或递减,需要递归 n 层,第 $i(o \le i \le n)$ 层需要遍历 $n-i$ 个元素以找出最大值,总时间复杂度为 $O(n^2)$。 - 空间复杂度:$O(n)$,即最坏情况下需要使用的栈空间。
/**
* Definition for a binary tree node.
* class TreeNode {
* val: number
* left: TreeNode | null
* right: TreeNode | null
* constructor(val?: number, left?: TreeNode | null, right?: TreeNode | null) {
* this.val = (val===undefined ? 0 : val)
* this.left = (left===undefined ? null : left)
* this.right = (right===undefined ? null : right)
* }
* }
*/
function constructMaximumBinaryTree(nums: number[]): TreeNode | null {
if (nums.length === 0) return null;
let maxNum: number = nums[0];
let index: number = 0;
for (let i = 0; i < nums.length; i++) {
if (nums[i] > maxNum) {
maxNum = nums[i];
index = i;
}
}
const root = new TreeNode(maxNum);
root.left = constructMaximumBinaryTree(nums.slice(0, index));
root.right = constructMaximumBinaryTree(nums.slice(index + 1));
return root;
};
单调栈
- 时间复杂度:$O(n)$,其中 n 是数组
nums
的长度。单调栈求解左右边界和构造树均需要 $O(n)$ 的时间。 - 空间复杂度:$O(n)$,即为单调栈和数组
tree
需要使用的空间。
/**
* Definition for a binary tree node.
* class TreeNode {
* val: number
* left: TreeNode | null
* right: TreeNode | null
* constructor(val?: number, left?: TreeNode | null, right?: TreeNode | null) {
* this.val = (val===undefined ? 0 : val)
* this.left = (left===undefined ? null : left)
* this.right = (right===undefined ? null : right)
* }
* }
*/
function constructMaximumBinaryTree(nums: number[]): TreeNode | null {
if (nums.length === 0) return null;
const dequeue: TreeNode[] = [];
for (let i = 0; i < nums.length; i++) {
const node = new TreeNode(nums[i]);
if (dequeue.length === 0) {
dequeue.push(node);
continue;
}
while (dequeue.length > 0) {
// 入栈元素小于栈顶元素,入队
if (dequeue[dequeue.length - 1].val > nums[i]) {
dequeue[dequeue.length - 1].right = node;
break;
}
// 入栈元素大于栈顶元素,出队
else if (dequeue[dequeue.length - 1].val < nums[i]) {
node.left = dequeue.pop();
}
}
dequeue.push(node);
}
return dequeue[0];
};
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]
DFS-递归
- 时间复杂度:$O(min(m,n))$,其中 m 和 n 分别是两个二叉树的节点个数。对两个二叉树同时进行深度优先搜索,只有当两个二叉树的对应节点都不为空时才会对该结点进行显性合并操作,因此被访问到的节点数不会超过较小的二叉树的节点数。
- 空间复杂度:$O(min(m,n))$,其中 m 和 n 分别是两个二叉树的节点个数。空间复杂度取决于递归调用的层数,递归调用的层数不会超过较小的最大高度,最坏情况下,二叉树的高度等于节点数。
/**
* Definition for a binary tree node.
* class TreeNode {
* val: number
* left: TreeNode | null
* right: TreeNode | null
* constructor(val?: number, left?: TreeNode | null, right?: TreeNode | null) {
* this.val = (val===undefined ? 0 : val)
* this.left = (left===undefined ? null : left)
* this.right = (right===undefined ? null : right)
* }
* }
*/
function mergeTrees(root1: TreeNode | null, root2: TreeNode | null): TreeNode | null {
if (root1 === null && root2 === null) return null;
if (root1 === null) return root2;
if (root2 === null) return root1;
let root: TreeNode = new TreeNode(root1.val + root2.val);
root.left = mergeTrees(root1.left, root2.left);
root.right = mergeTrees(root1.right, root2.right);
return root;
};
BFS-迭代
- 时间复杂度:$O(min(m,n))$,其中 m 和 n 分别是两个二叉树的节点个数。对两个二叉树同时进行广度优先搜索,只有当两个二叉树的对应节点都不为空时才会访问到该节点,因此被访问到的节点数不会超过较小的二叉树的节点数。
- 空间复杂度:$O(min(m,n))$,其中 m 和 n 分别是两个二叉树的节点个数。空间复杂度取决于队列中元素个数,队列中的元素个数不会超过较小的二叉树的节点数。
/**
* Definition for a binary tree node.
* class TreeNode {
* val: number
* left: TreeNode | null
* right: TreeNode | null
* constructor(val?: number, left?: TreeNode | null, right?: TreeNode | null) {
* this.val = (val===undefined ? 0 : val)
* this.left = (left===undefined ? null : left)
* this.right = (right===undefined ? null : right)
* }
* }
*/
function mergeTrees(root1: TreeNode | null, root2: TreeNode | null): TreeNode | null {
if (root1 === null) return root2;
if (root2 === null) return root1;
const root = new TreeNode(root1.val + root2.val);
const queue: TreeNode[] = [root];
const queue1: TreeNode[] = [root1];
const queue2: TreeNode[] = [root2];
while (queue.length > 0) {
const node = queue.shift();
const node1 = queue1.shift();
const node2 = queue2.shift();
if (node1.left !== null && node2.left !== null) {
const merge = new TreeNode(node1.left.val + node2.left.val);
node.left = merge;
queue.push(merge);
queue1.push(node1.left);
queue2.push(node2.left);
} else if (node1.left === null) {
node.left = node2.left;
} else if (node2.left === null) {
node.left = node1.left;
}
if (node1.right !== null && node2.right !== null) {
const merge = new TreeNode(node1.right.val + node2.right.val);
node.right = merge;
queue.push(merge);
queue1.push(node1.right);
queue2.push(node2.right);
}
else if (node1.right === null) {
node.right = node2.right;
} else if (node2.right === null) {
node.right = node1.right;
}
}
return root;
};
700.二叉搜索树中的搜索
给定二叉搜索树(BST)的根节点
root
和一个整数值val
。你需要在 BST 中找到节点值等于
val
的节点。 返回以该节点为根的子树。 如果节点不存在,则返回null
。示例 1:
输入:root = [4,2,7,1,3], val = 2 输出:[2,1,3]
示例 2:
输入:root = [4,2,7,1,3], val = 5 输出:[]
DFS-递归
/**
* Definition for a binary tree node.
* class TreeNode {
* val: number
* left: TreeNode | null
* right: TreeNode | null
* constructor(val?: number, left?: TreeNode | null, right?: TreeNode | null) {
* this.val = (val===undefined ? 0 : val)
* this.left = (left===undefined ? null : left)
* this.right = (right===undefined ? null : right)
* }
* }
*/
function searchBST(root: TreeNode | null, val: number): TreeNode | null {
if (root === null) return null;
if (root.val === val) return root;
else if (root.val > val) return searchBST(root.left, val);
else return searchBST(root.right, val);
};
BFS-迭代
/**
* Definition for a binary tree node.
* class TreeNode {
* val: number
* left: TreeNode | null
* right: TreeNode | null
* constructor(val?: number, left?: TreeNode | null, right?: TreeNode | null) {
* this.val = (val===undefined ? 0 : val)
* this.left = (left===undefined ? null : left)
* this.right = (right===undefined ? null : right)
* }
* }
*/
function searchBST(root: TreeNode | null, val: number): TreeNode | null {
const queue: TreeNode[] = [root];
while (queue.length > 0) {
const node = queue.shift();
if (node === null) return null;
if (node.val === val) return node;
else if (node.val > val) queue.push(node.left);
else queue.push(node.right);
}
};
98.验证二叉搜索树
给你一个二叉树的根节点
root
,判断其是否是一个有效的二叉搜索树。有效 二叉搜索树定义如下:
- 节点的左子树只包含 小于 当前节点的数。
- 节点的右子树只包含 大于 当前节点的数。
- 所有左子树和右子树自身必须也是二叉搜索树。
示例 1:
输入:root = [2,1,3] 输出:true
示例 2:
输入:root = [5,1,4,null,null,3,6] 输出:false 解释:根节点的值是 5 ,但是右子节点的值是 4 。
递归
- 时间复杂度:$O(n)$,其中 n 为二叉树的节点个数。在递归调用的时候二叉树的每个节点最多被访问一次,因此时间复杂度为 $O(n)$。
- 空间复杂度:$O(n)$,其中 n 为二叉树的节点个数。递归函数在递归过程中需要为每一层递归函数分配栈空间,所以这里需要额外的空间且该空间取决于递归的深度,即二叉树的深度。最坏情况下二叉树为一条链,树的高度为 n,递归最深达到 n 层,故最坏情况下空间复杂度为 $O(n)$。
/**
* Definition for a binary tree node.
* class TreeNode {
* val: number
* left: TreeNode | null
* right: TreeNode | null
* constructor(val?: number, left?: TreeNode | null, right?: TreeNode | null) {
* this.val = (val===undefined ? 0 : val)
* this.left = (left===undefined ? null : left)
* this.right = (right===undefined ? null : right)
* }
* }
*/
function helper(root: TreeNode | null, low: number, upper: number) {
if (root === null) return true;
if (root.val <= low || root.val >= upper) {
return false;
}
return helper(root.left, low, root.val) && helper(root.right, root.val, upper);
}
function isValidBST(root: TreeNode | null): boolean {
return helper(root, -Infinity, Infinity);
};
中序遍历
思路:利用二叉搜索树中序遍历(递归)为递增序列的特点,如果不是递增序列则返回false,否则返回true。
- 时间复杂度:$O(n)$。
- 空间复杂度:$O(n)$。
/**
* Definition for a binary tree node.
* class TreeNode {
* val: number
* left: TreeNode | null
* right: TreeNode | null
* constructor(val?: number, left?: TreeNode | null, right?: TreeNode | null) {
* this.val = (val===undefined ? 0 : val)
* this.left = (left===undefined ? null : left)
* this.right = (right===undefined ? null : right)
* }
* }
*/
function isValidBST(root: TreeNode | null): boolean {
let pre = -Infinity;
const helper = (root: TreeNode | null): boolean => {
if (root === null) return true;
if (!helper(root.left)) {
return false;
}
if (root.val <= pre) {
return false;
}
pre = root.val;
return helper(root.right);
}
return helper(root);
};
530.二叉搜索树的最小绝对差
给你一个二叉搜索树的根节点
root
,返回 树中任意两不同节点值之间的最小差值 。差值是一个正数,其数值等于两值之差的绝对值。
示例 1:
输入:root = [4,2,6,1,3] 输出:1
示例 2:
输入:root = [1,0,48,null,null,12,49] 输出:1
中序遍历-递归
思路:通过中序遍历的方法,可以获得一个升序的节点值序列,这是因为二叉搜索树的性质是左子树的值 < 根节点的值 < 右子树的值。我们可以在遍历的过程中,比较相邻节点的差值,并记录下最小的差值。
- 时间复杂度:$O(n)$,其中 n 为二叉搜索树节点的个数。每个节点的中序遍历中都会被访问一次且只会被访问一次,因此总时间复杂度为 $O(n)$。
- 空间复杂度:$O(n)$。递归函数的空间复杂度取决于递归的栈深度,而栈深度在二叉搜索树为一条链的情况下会达到 $O(n)$级别。
/**
* Definition for a binary tree node.
* class TreeNode {
* val: number
* left: TreeNode | null
* right: TreeNode | null
* constructor(val?: number, left?: TreeNode | null, right?: TreeNode | null) {
* this.val = (val===undefined ? 0 : val)
* this.left = (left===undefined ? null : left)
* this.right = (right===undefined ? null : right)
* }
* }
*/
function getMinimumDifference(root: TreeNode | null): number {
let min = Infinity;
let pre: number = null;
const helper = (root: TreeNode | null) => {
if (root === null) return;
if (root.left) {
helper(root.left);
}
if (pre !== null) {
min = Math.min(Math.abs(pre - root.val), min);
}
pre = root.val;
if (root.right) {
helper(root.right);
}
}
helper(root);
return min;
};
501.二叉搜索树中的众数
给你一个含重复值的二叉搜索树(BST)的根节点
root
,找出并返回 BST 中的所有 众数(即,出现频率最高的元素)。如果树中有不止一个众数,可以按 任意顺序 返回。
假定 BST 满足如下定义:
- 结点左子树中所含节点的值 小于等于 当前节点的值
- 结点右子树中所含节点的值 大于等于 当前节点的值
- 左子树和右子树都是二叉搜索树
示例 1:
输入:root = [1,null,2,2] 输出:[2]
示例 2:
输入:root = [0] 输出:[0]
中序遍历-递归
思路:对二叉搜索树进行中序遍历,这样可以得到一个递增的序列。然后,我们可以在遍历的过程中记录当前元素的出现次数和最大出现次数,并用一个列表保存出现次数最多的元素。如果当前元素的出现次数超过了之前的最大出现次数,就更新这个列表。这样,当遍历结束时,我们就可以得到出现次数最多的元素。
- 时间复杂度:$O(n)$。
- 空间复杂度:$O(n)$。
/**
* Definition for a binary tree node.
* class TreeNode {
* val: number
* left: TreeNode | null
* right: TreeNode | null
* constructor(val?: number, left?: TreeNode | null, right?: TreeNode | null) {
* this.val = (val===undefined ? 0 : val)
* this.left = (left===undefined ? null : left)
* this.right = (right===undefined ? null : right)
* }
* }
*/
function findMode(root: TreeNode | null): number[] {
let arr: number[] = [];
let count = 0;
let maxCount = 0;
let pre = root !== null ? root.val : null;
const helper = (root: TreeNode | null) => {
if (root === null) return;
if (root.left) {
helper(root.left);
}
if (pre === root.val) {
count++;
} else {
count = 1;
}
if (count > maxCount) {
arr = [];
arr.push(root.val);
maxCount = count;
} else if (count === maxCount) {
arr.push(root.val);
}
pre = root.val;
if (root.right) {
helper(root.right);
}
}
helper(root);
return arr;
};
236.二叉树的最近公共祖先
给定一个二叉树, 找到该树中两个指定节点的最近公共祖先。
最近公共祖先的定义为:“对于有根树 T 的两个节点 p、q,最近公共祖先表示为一个节点 x,满足 x 是 p、q 的祖先且 x 的深度尽可能大(一个节点也可以是它自己的祖先)。”
示例 1:
输入:root = [3,5,1,6,2,0,8,null,null,7,4], p = 5, q = 1 输出:3 解释:节点 5 和节点 1 的最近公共祖先是节点 3 。
示例 2:
输入:root = [3,5,1,6,2,0,8,null,null,7,4], p = 5, q = 4 输出:5 解释:节点 5 和节点 4 的最近公共祖先是节点 5 。因为根据定义最近公共祖先节点可以为节点本身。
示例 3:
输入:root = [1,2], p = 1, q = 2 输出:1
提示:
- 树中节点数目在范围
[2, 105]
内。-109 <= Node.val <= 109
- 所有
Node.val
互不相同
。p != q
p
和q
均存在于给定的二叉树中。
DFS-后序遍历-递归-解法1
- 时间复杂度:$O(n)$,其中 n 为二叉树节点数;最差情况下,需要递归遍历树的所有节点。
- 空间复杂度:$O(n)$,最差情况下,递归深度达到 n。
/**
* Definition for a binary tree node.
* class TreeNode {
* val: number
* left: TreeNode | null
* right: TreeNode | null
* constructor(val?: number, left?: TreeNode | null, right?: TreeNode | null) {
* this.val = (val===undefined ? 0 : val)
* this.left = (left===undefined ? null : left)
* this.right = (right===undefined ? null : right)
* }
* }
*/
function lowestCommonAncestor(root: TreeNode | null, p: TreeNode | null, q: TreeNode | null): TreeNode | null {
if (root === null || root.val === p.val || root.val === q.val) return root;
const left = lowestCommonAncestor(root.left, p, q);
const right = lowestCommonAncestor(root.right, p, q);
if (left === null && right === null) return null;
if (left === null) return right;
if (right === null) return left;
return root;
};
DFS-后序遍历-递归-解法2
- 时间复杂度:$O(n)$,其中 n 为二叉树节点数;最差情况下,需要递归遍历树的所有节点。
- 空间复杂度:$O(n)$,最差情况下,递归深度达到 n。
/**
* Definition for a binary tree node.
* class TreeNode {
* val: number
* left: TreeNode | null
* right: TreeNode | null
* constructor(val?: number, left?: TreeNode | null, right?: TreeNode | null) {
* this.val = (val===undefined ? 0 : val)
* this.left = (left===undefined ? null : left)
* this.right = (right===undefined ? null : right)
* }
* }
*/
function lowestCommonAncestor(root: TreeNode | null, p: TreeNode | null, q: TreeNode | null): TreeNode | null {
let ans: TreeNode = null;
const helper = (root: TreeNode | null, p: TreeNode | null, q: TreeNode | null): boolean => {
if (root === null) return false;
let leftBool = helper(root.left, p, q);
let rightBool = helper(root.right, p, q);
if ((leftBool && rightBool) || ((root.val === p.val || root.val === q.val) && (leftBool || rightBool))) {
ans = root;
}
return leftBool || rightBool || root.val === p.val || root.val === q.val;
}
helper(root, p, q);
return ans;
};
235.二叉搜索树的最近公共祖先
给定一个二叉搜索树, 找到该树中两个指定节点的最近公共祖先。
最近公共祖先的定义为:“对于有根树 T 的两个结点 p、q,最近公共祖先表示为一个结点 x,满足 x 是 p、q 的祖先且 x 的深度尽可能大(一个节点也可以是它自己的祖先)。”
例如,给定如下二叉搜索树: root = [6,2,8,0,4,7,9,null,null,3,5]
示例 1:
输入: root = [6,2,8,0,4,7,9,null,null,3,5], p = 2, q = 8 输出: 6 解释: 节点 2 和节点 8 的最近公共祖先是 6。
示例 2:
输入: root = [6,2,8,0,4,7,9,null,null,3,5], p = 2, q = 4 输出: 2 解释: 节点 2 和节点 4 的最近公共祖先是 2, 因为根据定义最近公共祖先节点可以为节点本身。
说明:
- 所有节点的值都是唯一的。
- p、q 为不同节点且均存在于给定的二叉搜索树中。
二次遍历
解题思路:
利用二叉搜索树的查找性质
- 从根节点开始,沿着树往下遍历找到到达第一个节点的路径,并把经过的节点保存在一个列表或栈中。
- 再次从根节点开始,同样沿着树往下遍历找到到达第二个节点的路径,并把经过的节点保存在另一个列表或栈中。
最后,我们比较两个列表,找出最后一个相同的节点,这个节点就是两个节点的最近公共祖先。
- 时间复杂度:$O(n)$,其中 n 是给定的二叉搜索树中的节点个数。上述代码需要的时间与节点p和q在树中的深度线性相关,而在最坏的情况下,树呈现链式结构,p和q一个是树的唯一叶子结点,一个是该叶子结点的父结点,此时时间复杂度为 $O(n)$。
- 空间复杂度:$O(n)$,我们需要存储根结点到p和q的路径。和上面的分析方法相同,在最坏的情况下,路径的长度为 $O(n)$,因此需要 $O(n)$ 的空间。
/**
* Definition for a binary tree node.
* class TreeNode {
* val: number
* left: TreeNode | null
* right: TreeNode | null
* constructor(val?: number, left?: TreeNode | null, right?: TreeNode | null) {
* this.val = (val===undefined ? 0 : val)
* this.left = (left===undefined ? null : left)
* this.right = (right===undefined ? null : right)
* }
* }
*/
function getPath(root: TreeNode | null, node: TreeNode | null): TreeNode[] {
let temp = root;
const path: TreeNode[] = [];
while (temp !== null) {
path.push(temp);
if (temp.val > node.val) {
temp = temp.left;
} else if (temp.val < node.val) {
temp = temp.right;
} else {
return path;
}
}
}
function lowestCommonAncestor(root: TreeNode | null, p: TreeNode | null, q: TreeNode | null): TreeNode | null {
if (root === null) return null;
let pPath = getPath(root, p);
let qPath = getPath(root, q);
for (let i = pPath.length - 1; i >= 0; i--) {
for (let j = qPath.length - 1; j >= 0; j--) {
if (pPath[i].val === qPath[j].val) {
return pPath[i];
}
}
}
return null;
};
[推荐]一次遍历
解题思路:
将二次遍历变成一次遍历,步骤如下:
- 从根节点开始遍历。
- 如果当前节点的值大于两个节点的值,那么这意味着两个节点都在当前节点的左子树中,因此将遍历转向当前节点的左子节点。
- 如果当前节点的值小于两个节点的值,那么这意味着两个节点都在当前节点的右子树中,因此将遍历转向当前节点的右子节点。
- 如果当前节点的值在两个节点的值之间,或者等于其中一个节点的值,那么这意味着我们找到了最近的公共祖先,因为根据二叉搜索树的性质,一个节点在当前节点的左子树,另一个节点在右子树。
- 时间复杂度:$O(n)$,其中 n 是给定的二叉搜索树中的节点个数。
- 空间复杂度:$O(1)$。
/**
* Definition for a binary tree node.
* class TreeNode {
* val: number
* left: TreeNode | null
* right: TreeNode | null
* constructor(val?: number, left?: TreeNode | null, right?: TreeNode | null) {
* this.val = (val===undefined ? 0 : val)
* this.left = (left===undefined ? null : left)
* this.right = (right===undefined ? null : right)
* }
* }
*/
function lowestCommonAncestor(root: TreeNode | null, p: TreeNode | null, q: TreeNode | null): TreeNode | null {
if (root === null) return null;
let node = root;
while (node !== null) {
if (node.val > p.val && node.val > q.val) {
node = node.left;
} else if (node.val < p.val && node.val < q.val) {
node = node.right;
}
else {
return node;
}
}
return null;
};
701.二叉搜索树中的插入操作
给定二叉搜索树(BST)的根节点
root
和要插入树中的值value
,将值插入二叉搜索树。返回插入后二叉搜索树的根节点。 输入数据 保证 ,新值和原始二叉搜索树中的任意节点值都不同。注意,可能存在多种有效的插入方式,只要树在插入后仍保持为二叉搜索树即可。 你可以返回 任意有效的结果 。
示例 1:
输入:root = [4,2,7,1,3], val = 5 输出:[4,2,7,1,3,5]
解释:另一个满足题目要求可以通过的树是:
示例 2:
输入:root = [40,20,60,10,30,50,70], val = 25 输出:[40,20,60,10,30,50,70,null,null,25]
示例 3:
输入:root = [4,2,7,1,3,null,null,null,null,null,null], val = 5 输出:[4,2,7,1,3,5]
提示:
- 树中的节点数将在
[0, 104]
的范围内。-108 <= Node.val <= 108
- 所有值
Node.val
是 独一无二 的。-108 <= val <= 108
- 保证
val
在原始BST中不存在。
模拟
- 时间复杂度:$O(n)$,其中 n 为树中节点的数目。最坏情况下,我们需要将值插入到树的最深的叶子结点上,而叶子结点最深为 $O(n)$。
- 空间复杂度:$O(1)$。
/**
* Definition for a binary tree node.
* class TreeNode {
* val: number
* left: TreeNode | null
* right: TreeNode | null
* constructor(val?: number, left?: TreeNode | null, right?: TreeNode | null) {
* this.val = (val===undefined ? 0 : val)
* this.left = (left===undefined ? null : left)
* this.right = (right===undefined ? null : right)
* }
* }
*/
function insertIntoBST(root: TreeNode | null, val: number): TreeNode | null {
if (root === null) return new TreeNode(val);
let node = root;
while (node !== null) {
if (val > node.val) {
if (node.right !== null) {
node = node.right;
} else {
node.right = new TreeNode(val);
return root;
}
} else if (val < node.val) {
if (node.left !== null) {
node = node.left;
} else {
node.left = new TreeNode(val);
return root;
}
}
}
};
450.删除二叉搜索树中的节点
给定一个二叉搜索树的根节点 root 和一个值 key,删除二叉搜索树中的 key 对应的节点,并保证二叉搜索树的性质不变。返回二叉搜索树(有可能被更新)的根节点的引用。
一般来说,删除节点可分为两个步骤:
- 首先找到需要删除的节点;
- 如果找到了,删除它。
示例 1:
输入:root = [5,3,6,2,4,null,7], key = 3 输出:[5,4,6,2,null,null,7]
解释:给定需要删除的节点值是 3,所以我们首先找到 3 这个节点,然后删除它。
一个正确的答案是 [5,4,6,2,null,null,7], 如下图所示。
另一个正确答案是 [5,2,6,null,4,null,7]。
示例 2:
输入: root = [5,3,6,2,4,null,7], key = 0 输出: [5,3,6,2,4,null,7] 解释: 二叉树不包含值为 0 的节点
示例 3:
输入: root = [], key = 0 输出: []
提示:
- 节点数的范围
[0, 104]
.-105 <= Node.val <= 105
- 节点值唯一
root
是合法的二叉搜索树-105 <= key <= 105
递归
思路
- 如果目标节点大于当前节点值,则去右子树中删除;
- 如果目标节点小于当前节点值,则去左子树中删除;
- 如果目标节点就是当前节点,分为以下三种情况:
- 其无左子:其右子顶替其位置,删除了该节点;
- 其无右子:其左子顶替其位置,删除了该节点;
- 其左右子节点都有:其左子树转移到其右子树的最左节点的左子树上,然后右子树顶替其位置,由此删除了该节点。
- 时间复杂度:$O(n)$,其中 n 为root的节点个数。
- 空间复杂度:$O(n)$,其中 n 为root的节点个数。递归的深度最深为 $O(n)$。
/**
* Definition for a binary tree node.
* class TreeNode {
* val: number
* left: TreeNode | null
* right: TreeNode | null
* constructor(val?: number, left?: TreeNode | null, right?: TreeNode | null) {
* this.val = (val===undefined ? 0 : val)
* this.left = (left===undefined ? null : left)
* this.right = (right===undefined ? null : right)
* }
* }
*/
function deleteNode(root: TreeNode | null, key: number): TreeNode | null {
if (root === null) return null;
if (root.val > key) {
root.left = deleteNode(root.left, key);
}
else if (root.val < key) {
root.right = deleteNode(root.right, key);
}
else {
if (root.left === null) {
return root.right;
}
if (root.right === null) {
return root.left;
}
let node = root.right;
while (node.left !== null) {
node = node.left;
}
node.left = root.left;
root = root.right;
}
return root;
};
669.修剪二叉搜索树
给你二叉搜索树的根节点
root
,同时给定最小边界low
和最大边界high
。通过修剪二叉搜索树,使得所有节点的值在[low, high]
中。修剪树 不应该 改变保留在树中的元素的相对结构 (即,如果没有被移除,原有的父代子代关系都应当保留)。 可以证明,存在 唯一的答案 。所以结果应当返回修剪好的二叉搜索树的新的根节点。注意,根节点可能会根据给定的边界发生改变。
示例 1:
输入:root = [1,0,2], low = 1, high = 2 输出:[1,null,2]
示例 2:
输入:root = [3,0,4,null,2,null,null,1], low = 1, high = 3 输出:[3,2,null,1]
提示:
- 树中节点数在范围
[1, 104]
内0 <= Node.val <= 104
- 树中每个节点的值都是 唯一 的
- 题目数据保证输入是一棵有效的二叉搜索树
0 <= low <= high <= 104
递归
思路:
- 如果当前节点为空,返回空,因为一个空的树已经满足条件。
- 如果当前节点的值小于L,那么整个左子树都不需要,只需递归修剪右子树。
- 如果当前节点的值大于R,那么整个右子树都不需要,只需递归修剪左子树。
- 如果当前节点的值在[L, R]范围内,递归修剪它的左右子树,并返回当前节点。
- 时间复杂度:$O(n)$。
- 空间复杂度:$O(n)$。
/**
* Definition for a binary tree node.
* class TreeNode {
* val: number
* left: TreeNode | null
* right: TreeNode | null
* constructor(val?: number, left?: TreeNode | null, right?: TreeNode | null) {
* this.val = (val===undefined ? 0 : val)
* this.left = (left===undefined ? null : left)
* this.right = (right===undefined ? null : right)
* }
* }
*/
function trimBST(root: TreeNode | null, low: number, high: number): TreeNode | null {
if (root === null) return null;
if (root.val < low) {
return trimBST(root.right, low, high);
}
if (root.val > high) {
return trimBST(root.left, low, high);
}
if (root.left) {
root.left = trimBST(root.left, low, high)
}
if (root.right) {
root.right = trimBST(root.right, low, high);
}
return root;
};
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] 都是高度平衡二叉搜索树。
提示:
1 <= nums.length <= 104
-104 <= nums[i] <= 104
nums
按 严格递增 顺序排列
递归
思路:选择中间数字作为二叉搜索树的根节点,这样分给左右子树的数字个数相同或只相差 1,可以使得树保持平衡。
- 时间复杂度:$O(n)$,其中 n 是数组的长度。每个数字只访问一次。
- 空间复杂度:$O(logn)$,其中 n 是数组的长度。空间复杂度不考虑返回值,因此空间复杂度主要取决于递归栈的深度,递归栈的深度是 $O(logn)$。
/**
* Definition for a binary tree node.
* class TreeNode {
* val: number
* left: TreeNode | null
* right: TreeNode | null
* constructor(val?: number, left?: TreeNode | null, right?: TreeNode | null) {
* this.val = (val===undefined ? 0 : val)
* this.left = (left===undefined ? null : left)
* this.right = (right===undefined ? null : right)
* }
* }
*/
function sortedArrayToBST(nums: number[]): TreeNode | null {
if (nums.length === 0) return null;
const mid = Math.floor(nums.length / 2);
const node = new TreeNode(nums[mid]);
if (nums.length > 1) {
node.left = sortedArrayToBST(nums.slice(0, mid));
node.right = sortedArrayToBST(nums.slice(mid + 1));
}
return node;
};
538.把二叉搜索树转换为累加树
给出二叉 搜索 树的根节点,该树的节点值各不相同,请你将其转换为累加树(Greater Sum Tree),使每个节点
node
的新值等于原树中大于或等于node.val
的值之和。提醒一下,二叉搜索树满足下列约束条件:
- 节点的左子树仅包含键 小于 节点键的节点。
- 节点的右子树仅包含键 大于 节点键的节点。
- 左右子树也必须是二叉搜索树。
示例 1:
输入:[4,1,6,0,2,5,7,null,null,null,3,null,null,null,8] 输出:[30,36,21,36,35,26,15,null,null,null,33,null,null,null,8]
示例 2:
输入:root = [0,null,1] 输出:[1,null,1]
示例 3:
输入:root = [1,0,2] 输出:[3,3,2]
示例 4:
输入:root = [3,2,4,1] 输出:[7,9,4,10]
提示:
- 树中的节点数介于
0
和104
之间。- 每个节点的值介于
-104
和104
之间。- 树中的所有值 互不相同 。
- 给定的树为二叉搜索树。
反序中序遍历-DST-递归
- 时间复杂度:$O(n)$,其中 n 是二叉搜索树的节点数。每一个节点恰好被遍历一次。
- 空间复杂度:$O(n)$,为递归过程中栈的开销,平均情况下为 $O(logn)$,最坏情况下树呈现链状,为 $O(n)$。
/**
* Definition for a binary tree node.
* class TreeNode {
* val: number
* left: TreeNode | null
* right: TreeNode | null
* constructor(val?: number, left?: TreeNode | null, right?: TreeNode | null) {
* this.val = (val===undefined ? 0 : val)
* this.left = (left===undefined ? null : left)
* this.right = (right===undefined ? null : right)
* }
* }
*/
function convertBST(root: TreeNode | null): TreeNode | null {
let sum = 0;
const helper = (root: TreeNode | null) => {
if (root === null) return null;
helper(root.right);
sum += root.val;
root.val = sum;
helper(root.left);
}
helper(root);
return root;
};
回溯法
回溯三部曲
- 确定递归函数参数
- 确定终止条件
- 单层搜索过程
回溯算法能解决如下问题:
- 组合问题:N个数里面按一定规则找出k个数的集合
- 排列问题:N个数按一定规则全排列,有几种排列方式
- 切割问题:一个字符串按一定规则有几种切割方式
- 子集问题:一个N个数的集合里有多少符合条件的子集
- 棋盘问题:N皇后,解数独等等
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 <= n <= 20
1 <= k <= n
递归实现组合型枚举
- 时间复杂度:$O(\binom{n}{k} *k)$。
- 空间复杂度:$O(n+k)=O(n)$。
根据搜索起点画出二叉树
function combine(n: number, k: number): number[][] {
const res: number[][] = [];
let path: number[] = [];
const backtracking = (begin: number) => {
if (path.length === k) {
res.push(path.slice());
return;
}
for (let i = begin; i <= n; i++) {
path.push(i);
backtracking(i + 1);
path.pop(); // 回溯
}
}
backtracking(1);
return res;
};
优化:分析搜索起点的上界进行剪枝
如果 n = 7, k = 4
,从 5 开始搜索就已经没有意义了,这是因为:即使把 5 选上,后面的数只有 6 和 7,一共就 3 个候选数,凑不出 4 个数的组合。因此,搜索起点有上界。
如果for循环选择的起始位置之后的元素个数 已经不足 我们需要的元素个数了,那么就没有必要搜索了。
归纳出:
搜索起点的上界 + 接下来要选择的元素个数 - 1 = n
其中,接下来要选择的元素个数 = k - path.size()
,整理得到:
搜索起点的上界 = n - (k - path.size()) + 1
function combine(n: number, k: number): number[][] {
const res: number[][] = [];
let path: number[] = [];
const backtracking = (begin: number) => {
if (path.length === k) {
res.push(path.slice());
return;
}
for (let i = begin; i <= n - (k - path.length) + 1; i++) {
path.push(i);
backtracking(i + 1);
path.pop(); // 回溯
}
}
backtracking(1);
return res;
};
216.组合总和Ⅲ
找出所有相加之和为
n
的k
个数的组合,且满足下列条件:
- 只使用数字1到9
- 每个数字 最多使用一次
返回 所有可能的有效组合的列表 。该列表不能包含相同的组合两次,组合可以以任何顺序返回。
示例 1:
输入: k = 3, n = 7 输出: [[1,2,4]] 解释: 1 + 2 + 4 = 7 没有其他符合的组合了。
示例 2:
输入: k = 3, n = 9 输出: [[1,2,6], [1,3,5], [2,3,4]] 解释: 1 + 2 + 6 = 9 1 + 3 + 5 = 9 2 + 3 + 4 = 9 没有其他符合的组合了。
示例 3:
输入: k = 4, n = 1 输出: [] 解释: 不存在有效的组合。 在[1,9]范围内使用4个不同的数字,我们可以得到的最小和是1+2+3+4 = 10,因为10 > 1,没有有效的组合。
提示:
2 <= k <= 9
1 <= n <= 60
递归+for循环实现枚举
未剪枝
function combinationSum3(k: number, n: number): number[][] {
if (k > n) return [];
let res: number[][] = [];
let path: number[] = [];
const dfs = (begin: number, sum: number) => {
if (path.length === k) {
if (sum === n) {
res.push(path.slice());
}
return;
}
for (let i = begin; i < 10; i++) {
path.push(i);
sum += i;
dfs(i + 1, sum);
sum -= i; // 回溯
path.pop(); // 回溯
}
}
dfs(1, 0);
return res;
};
剪枝
function combinationSum3(k: number, n: number): number[][] {
if (k > n) return [];
let res: number[][] = [];
let path: number[] = [];
const dfs = (begin: number, sum: number) => {
if (sum > n) return; // 剪枝
if (path.length === k) {
if (sum === n) {
res.push(path.slice());
}
return;
}
for (let i = begin; i < 10; i++) {
path.push(i);
sum += i;
dfs(i + 1, sum);
sum -= i; // 回溯
path.pop(); // 回溯
}
}
dfs(1, 0);
return res;
};
17.电话号码的字母组合
给定一个仅包含数字
2-9
的字符串,返回所有它能表示的字母组合。答案可以按 任意顺序 返回。给出数字到字母的映射如下(与电话按键相同)。注意 1 不对应任何字母。
示例 1:
输入:digits = "23" 输出:["ad","ae","af","bd","be","bf","cd","ce","cf"]
示例 2:
输入:digits = "" 输出:[]
示例 3:
输入:digits = "2" 输出:["a","b","c"]
提示:
0 <= digits.length <= 4
digits[i]
是范围['2', '9']
的一个数字。
回溯
- 时间复杂度:$O(3^m \times 4^n)$,其中 m 是输入中对应3个字母的数字个数,n 是输入中对应4个字母的数字个数,m+n 是输入数字的总个数。当输入包含m个对应3个字母的数字和n个对应4个字母的数字时,不同的字母组合一共有 $3^m \times 4^n$ 种,需要遍历每一种字母组合。
- 空间复杂度:$O(m+n)$,空间复杂度主要取决于哈希表以及回溯过程中的递归调用层数,哈希表的大小与输入无关,可以看成常数,递归调用层数最大为 $m+n$。
function letterCombinations(digits: string): string[] {
if (digits.length === 0) return [];
const digitsMap = {
'2': ['a', 'b', 'c'],
'3': ['d', 'e', 'f'],
'4': ['g', 'h', 'i'],
'5': ['j', 'k', 'l'],
'6': ['m', 'n', 'o'],
'7': ['p', 'q', 'r', 's'],
'8': ['t', 'u', 'v'],
'9': ['w', 'x', 'y', 'z']
}
const res: string[] = [];
const backtracking = (index: number, combination: string) => {
if (index === digits.length) {
res.push(combination);
return;
}
const letters: string[] = digitsMap[digits[index]];
for (let i = 0; i < letters.length; i++) {
combination += letters[i];
backtracking(index + 1, combination);
combination = combination.slice(0, -1); // 回溯
}
}
backtracking(0, '');
return res;
};
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 <= candidates.length <= 30
2 <= candidates[i] <= 40
candidates
的所有元素 互不相同1 <= target <= 40
回溯
- 时间复杂度: $O(n * 2^n)$,注意这只是复杂度的上界,因为剪枝的存在,真实的时间复杂度远小于此
- 空间复杂度: $O(target)$
function combinationSum(candidates: number[], target: number): number[][] {
let res: number[][] = [];
let path: number[] = [];
let backtracking = (sum: number, begin: number) => {
if (sum > target) return; // 剪枝
if (sum === target) {
res.push(path.slice());
return;
}
for (let i = begin; i < candidates.length; i++) {
sum += candidates[i];
path.push(candidates[i]);
backtracking(sum, i);
path.pop(); // 回溯
sum -= candidates[i]; // 回溯
}
}
backtracking(0, 0);
return res;
};
40.组合总和Ⅱ
给定一个候选人编号的集合
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 <= candidates.length <= 100
1 <= candidates[i] <= 50
1 <= target <= 30
回溯+排序+数组记录
function combinationSum2(candidates: number[], target: number): number[][] {
candidates.sort((a, b) => a - b);
const res: number[][] = [];
const path: number[] = [];
const used: boolean[] = new Array(candidates.length).fill(false);
const backtracking = (sum: number, begin: number) => {
if (sum > target) return; // 剪枝
if (sum === target) {
res.push(path.slice());
}
for (let i = begin; i < candidates.length; i++) {
if (i > 0 && candidates[i] == candidates[i - 1] && used[i - 1] === false) {
continue;
}
path.push(candidates[i]);
sum += candidates[i];
used[i] = true;
backtracking(sum, i + 1);
path.pop(); // 回溯
sum -= candidates[i]; // 回溯
used[i] = false; // 回溯
}
}
backtracking(0, 0);
return res;
};
131.分割回文串
给你一个字符串
s
,请你将s
分割成一些子串,使每个子串都是 回文串 。返回s
所有可能的分割方案。回文串 是正着读和反着读都一样的字符串。
示例 1:
输入:s = "aab" 输出:[["a","a","b"],["aa","b"]]
示例 2:
输入:s = "a" 输出:[["a"]]
提示:
1 <= s.length <= 16
s
仅由小写英文字母组成
回溯
- 时间复杂度: $O(n * 2^n)$
- 空间复杂度: $O(n^2)$
function isPalindrome(s: string, start: number, end: number) {
for (let i = start, j = end; i < j; i++, j--) {
if (s[i] !== s[j]) {
return false;
}
}
return true;
}
function partition(s: string): string[][] {
const res: string[][] = [];
const path: string[] = [];
const backtracking = (begin: number) => {
if (begin >= s.length) {
res.push(path.slice());
return;
}
for (let i = begin; i < s.length; i++) {
if (isPalindrome(s, begin, i)) {
const str = s.slice(begin, i + 1);
path.push(str);
} else { // 剪枝
continue;
}
backtracking(i + 1);
path.pop(); // 回溯
}
}
backtracking(0);
return res;
};
回溯+动态规划
待补充
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
仅由数字组成
回溯
- 时间复杂度: $O(3^4)$,IP地址最多包含4个数字,每个数字最多有3种可能的分割方式,则搜索树的最大深度为4,每个节点最多有3个子节点。
- 空间复杂度: $O(n)$。
function isVaild(s: string) {
if (s[0] === '0' && s.length > 1) return false;
const num = Number(s);
if (num >= 0 && num <= 255) {
return true;
}
return false;
}
function restoreIpAddresses(s: string): string[] {
const res: string[] = [];
const path: string[] = [];
const backtracking = (begin: number) => {
if (path.length === 4) {
if (isVaild(path[path.length - 1])) {
res.push(path.join('.'));
}
return; // 剪枝
}
for (let i = begin; i < s.length; i++) {
if (path.length === 3) {
path.push(s.slice(i));
backtracking(i + 1);
path.splice(path.length - 1, 1); // 回溯
return; // 剪枝
} else if (isVaild(s.slice(begin, i + 1))) {
path.push(s.slice(begin, i + 1));
} else {
continue; // 剪枝
}
backtracking(i + 1);
path.pop(); // 回溯
}
}
backtracking(0);
return res;
};
78.子集
给你一个整数数组
nums
,数组中的元素 互不相同 。返回该数组所有可能的子集(幂集)。解集 不能 包含重复的子集。你可以按 任意顺序 返回解集。
示例 1:
输入:nums = [1,2,3] 输出:[[],[1],[2],[1,2],[3],[1,3],[2,3],[1,2,3]]
示例 2:
输入:nums = [0] 输出:[[],[0]]
提示:
1 <= nums.length <= 10
-10 <= nums[i] <= 10
nums
中的所有元素 互不相同
回溯
- 时间复杂度: $O(n * 2^n)$。
- 空间复杂度: $O(n)$。
function subsets(nums: number[]): number[][] {
const res: number[][] = [];
const collection: number[] = [];
const backtracking = (begin: number) => {
res.push(collection.slice());
if (begin === nums.length) {
return;
}
for (let i = begin; i < nums.length; i++) {
collection.push(nums[i]);
backtracking(i + 1);
collection.pop(); // 回溯
}
}
backtracking(0);
return res;
};
90.子集Ⅱ
给你一个整数数组
nums
,其中可能包含重复元素,请你返回该数组所有可能的子集(幂集)。解集 不能 包含重复的子集。返回的解集中,子集可以按 任意顺序 排列。
示例 1:
输入:nums = [1,2,2] 输出:[[],[1],[1,2],[1,2,2],[2],[2,2]]
示例 2:
输入:nums = [0] 输出:[[],[0]]
提示:
1 <= nums.length <= 10
-10 <= nums[i] <= 10
回溯
- 时间复杂度: $O(n * 2^n)$。
- 空间复杂度: $O(n)$。
function subsetsWithDup(nums: number[]): number[][] {
nums.sort((a, b) => a - b); // 排序
const res: number[][] = [];
const collection: number[] = [];
const backtracking = (begin: number) => {
res.push(collection.slice());
if (begin === nums.length) {
return
}
for (let i = begin; i < nums.length; i++) {
if (i > 0 && begin !== i && nums[i] === nums[i - 1]) { // 过滤重复元素
continue;
}
collection.push(nums[i]);
backtracking(i + 1);
collection.pop(); // 回溯
}
}
backtracking(0);
return res;
};
491.递增子序列
给你一个整数数组
nums
,找出并返回所有该数组中不同的递增子序列,递增子序列中 至少有两个元素 。你可以按 任意顺序 返回答案。数组中可能含有重复元素,如出现两个整数相等,也可以视作递增序列的一种特殊情况。
示例 1:
输入:nums = [4,6,7,7] 输出:[[4,6],[4,6,7],[4,6,7,7],[4,7],[4,7,7],[6,7],[6,7,7],[7,7]]
示例 2:
输入:nums = [4,4,3,2,1] 输出:[[4,4]]
提示:
1 <= nums.length <= 15
-100 <= nums[i] <= 100
回溯+哈希表
- 时间复杂度: $O(n * 2^n)$。
- 空间复杂度: $O(n)$。
function findSubsequences(nums: number[]): number[][] {
const res: number[][] = [];
const path: number[] = [];
const backtracking = (begin: number) => {
if (path.length >= 2) {
res.push(path.slice());
}
if (begin === nums.length) {
return;
}
const set = new Set<number>();
for (let i = begin; i < nums.length; i++) {
if (begin !== i && set.has(nums[i])) continue; // 同层相同的元素排除
set.add(nums[i]);
if (path.length === 0 || path[path.length - 1] <= nums[i]) {
path.push(nums[i]);
} else {
continue; // 剪枝
}
backtracking(i + 1);
path.pop(); // 回溯
}
}
backtracking(0);
return res;
};
46.全排列
给定一个不含重复数字的数组
nums
,返回其 所有可能的全排列 。你可以 按任意顺序 返回答案。示例 1:
输入:nums = [1,2,3] 输出:[[1,2,3],[1,3,2],[2,1,3],[2,3,1],[3,1,2],[3,2,1]]
示例 2:
输入:nums = [0,1] 输出:[[0,1],[1,0]]
示例 3:
输入:nums = [1] 输出:[[1]]
提示:
1 <= nums.length <= 6
-10 <= nums[i] <= 10
nums
中的所有整数 互不相同
回溯+数组哈希
- 时间复杂度: $O(n!)$。
- 空间复杂度: $O(n)$。
function permute(nums: number[]): number[][] {
const res: number[][] = [];
const path: number[] = [];
const arrMap: number[] = new Array(nums.length).fill(0);
const backtracking = () => {
if (path.length === nums.length) {
res.push(path.slice());
return;
}
for (let i = 0; i < arrMap.length; i++) {
if (arrMap[i] === 0) {
path.push(nums[i]);
arrMap[i] = 1;
backtracking();
arrMap[i] = 0; // 回溯
path.pop(); // 回溯
}
}
}
backtracking();
return res;
};
47.全排列Ⅱ
给定一个可包含重复数字的序列
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 <= nums.length <= 8
-10 <= nums[i] <= 10
回溯+排序+相邻判断去重
- 时间复杂度: $O(n)$。
- 空间复杂度: $O(n)$。
function permuteUnique(nums: number[]): number[][] {
nums.sort((a, b) => a - b);
const res: number[][] = [];
const path: number[] = [];
const backtracking = (used: boolean[]) => {
if (path.length === nums.length) {
res.push(path.slice());
return;
}
for (let i = 0; i < nums.length; i++) {
if (i > 0 && nums[i] === nums[i - 1] && !used[i-1]) { // 相邻之间去重
continue;
}
if (!used[i]) {
used[i] = true;
path.push(nums[i]);
backtracking(used);
used[i] = false; // 回溯
path.pop(); // 回溯
}
}
}
backtracking([]);
return res;
};
回溯+非排序+哈希表去重
- 时间复杂度: $O(n)$。
- 空间复杂度: $O(n)$。
function permuteUnique(nums: number[]): number[][] {
const res: number[][] = [];
const path: number[] = [];
const arrMap: number[] = new Array(nums.length).fill(0);
const backtracking = () => {
if (path.length === nums.length) {
res.push(path.slice());
return;
}
const set = new Set<number>(); // 哈希表,只在当前层,所以无须回溯
for (let i = 0; i < arrMap.length; i++) {
if (arrMap[i] === 0 && !set.has(nums[i])) {
set.add(nums[i]);
path.push(nums[i]);
arrMap[i] = 1;
backtracking();
arrMap[i] = 0; // 回溯
path.pop(); // 回溯
}
}
}
backtracking();
return res;
};
332.重新安排行程
给你一份航线列表
tickets
,其中tickets[i] = [fromi, toi]
表示飞机出发和降落的机场地点。请你对该行程进行重新规划排序。所有这些机票都属于一个从
JFK
(肯尼迪国际机场)出发的先生,所以该行程必须从JFK
开始。如果存在多种有效的行程,请你按字典排序返回最小的行程组合。
- 例如,行程
["JFK", "LGA"]
与["JFK", "LGB"]
相比就更小,排序更靠前。假定所有机票至少存在一种合理的行程。且所有的机票 必须都用一次 且 只能用一次。
示例 1:
输入:tickets = [["MUC","LHR"],["JFK","MUC"],["SFO","SJC"],["LHR","SFO"]] 输出:["JFK","MUC","LHR","SFO","SJC"]
示例 2:
输入:tickets = [["JFK","SFO"],["JFK","ATL"],["SFO","ATL"],["ATL","JFK"],["ATL","SFO"]] 输出:["JFK","ATL","JFK","SFO","ATL","SFO"] 解释:另一种有效的行程是 ["JFK","SFO","ATL","JFK","ATL","SFO"] ,但是它字典排序更大更靠后。
提示:
1 <= tickets.length <= 300
tickets[i].length == 2
fromi.length == 3
toi.length == 3
fromi
和toi
由大写英文字母组成fromi != toi
回溯
function findItinerary(tickets: string[][]): string[] {
// 按字典排序
tickets.sort((a, b) => {
return a[1] < b[1] ? -1 : 1;
})
// Map会的键会按插入顺序排序
type TicketsMap = {
[index: string]: Map<string, number>
}
const ticketMap: TicketsMap = {};
for (const [from, to] of tickets) {
if (ticketMap[from] === undefined) {
ticketMap[from] = new Map();
}
ticketMap[from].set(to, (ticketMap[from].get(to) || 0) + 1);
}
const resRoute = ['JFK'];
const backtracking = (): boolean => {
if (resRoute.length === tickets.length + 1) return true;
const targetMap = ticketMap[resRoute[resRoute.length - 1]];
if (targetMap !== undefined) {
for (const [to, count] of targetMap.entries()) {
if (count > 0) {
resRoute.push(to);
targetMap.set(to, count - 1);
if (backtracking() === true) return true;
targetMap.set(to, count);
resRoute.pop();
}
}
}
return false;
}
backtracking();
return resRoute;
};
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
回溯+二维数组
- 时间复杂度: $O(n!)$。
- 空间复杂度: $O(n)$。
function solveNQueens(n: number): string[][] {
const res: string[][] = [];
const chessboard: string[][] = Array.from({ length: n }, () => Array.from({ length: n }, () => '.'));
function isValid(row: number, col: number) {
// 检查列
for (let i = 0; i < row; i++) {
if (chessboard[i][col] === 'Q') {
return false;
}
}
// 检查45度斜线
for (let i = row - 1, j = col - 1; i >= 0 && j >= 0; i--, j--) {
if (chessboard[i][j] === 'Q') {
return false
}
}
// 检查135度斜线
for (let i = row - 1, j = col + 1; i >= 0 && j < n; i--, j++) {
if (chessboard[i][j] === 'Q') {
return false
}
}
return true;
}
function backtraking(row: number) {
if (row === n) {
res.push(chessboard.map(item => item.join('').slice()));
return;
}
for (let col = 0; col < n; col++) {
if (isValid(row, col)) {
chessboard[row][col] = 'Q';
backtraking(row + 1);
chessboard[row][col] = '.';
}
}
}
backtraking(0);
return res;
};
37.解数独
编写一个程序,通过填充空格来解决数独问题。
数独的解法需 遵循如下规则:
- 数字
1-9
在每一行只能出现一次。- 数字
1-9
在每一列只能出现一次。- 数字
1-9
在每一个以粗实线分隔的3x3
宫内只能出现一次。(请参考示例图)数独部分空格内已填入了数字,空白格用
'.'
表示。示例 1:
输入:board = [["5","3",".",".","7",".",".",".","."],["6",".",".","1","9","5",".",".","."],[".","9","8",".",".",".",".","6","."],["8",".",".",".","6",".",".",".","3"],["4",".",".","8",".","3",".",".","1"],["7",".",".",".","2",".",".",".","6"],[".","6",".",".",".",".","2","8","."],[".",".",".","4","1","9",".",".","5"],[".",".",".",".","8",".",".","7","9"]] 输出:[["5","3","4","6","7","8","9","1","2"],["6","7","2","1","9","5","3","4","8"],["1","9","8","3","4","2","5","6","7"],["8","5","9","7","6","1","4","2","3"],["4","2","6","8","5","3","7","9","1"],["7","1","3","9","2","4","8","5","6"],["9","6","1","5","3","7","2","8","4"],["2","8","7","4","1","9","6","3","5"],["3","4","5","2","8","6","1","7","9"]] 解释:输入的数独如上图所示,唯一有效的解决方案如下所示:
提示:
board.length == 9
board[i].length == 9
board[i][j]
是一位数字或者'.'
- 题目数据 保证 输入数独仅有一个解
回溯-二维数组递归
/**
Do not return anything, modify board in-place instead.
*/
function solveSudoku(board: string[][]): void {
const N = board.length;
function isValid(row: number, col: number, val: string) {
// 检查行
for (let i = 0; i < N; i++) {
if (board[row][i] === val) return false;
}
// 检查列
for (let j = 0; j < N; j++) {
if (board[j][col] === val) return false;
}
// 检查9宫格
const startRow = 3 * Math.floor(row / 3);
const startCol = 3 * Math.floor(col / 3);
for (let i = startRow; i < startRow + 3; i++) {
for (let j = startCol; j < startCol + 3; j++) {
if (board[i][j] === val) return false;
}
}
return true;
}
function backtracking(): boolean {
for (let row = 0; row < N; row++) {
for (let col = 0; col < N; col++) {
if (board[row][col] !== ".") continue;
for (let val = 1; val <= 9; val++) {
if (isValid(row, col, String(val))) {
board[row][col] = String(val);
if (backtracking()) return true;
board[row][col] = "."; // 回溯
}
}
return false; // 没有找到合适的,返回false
}
}
return true; // 遍历后没有返回false,说明找到了合适的棋盘位置
}
backtracking();
};
贪心算法
贪心算法是一种基于贪心策略的算法,用于解决最优化问题。在贪心算法中,每一步都选择当前看起来最优的选择,而不考虑该选择对以后的步骤的影响。贪心算法通常通过一系列的局部最优选择来达到全局最优解。
刷题或者面试的时候,手动模拟一下感觉可以局部最优推出整体最优,而且想不到反例,那么就试一试贪心。
贪心算法一般分为如下四步:
- 将问题分解为若干个子问题
- 找出适合的贪心策略
- 求解每一个子问题的最优解
- 将局部最优解堆叠成全局最优解
455.分发饼干
假设你是一位很棒的家长,想要给你的孩子们一些小饼干。但是,每个孩子最多只能给一块饼干。
对每个孩子
i
,都有一个胃口值g[i]
,这是能让孩子们满足胃口的饼干的最小尺寸;并且每块饼干j
,都有一个尺寸s[j]
。如果s[j] >= g[i]
,我们可以将这个饼干j
分配给孩子i
,这个孩子会得到满足。你的目标是尽可能满足越多数量的孩子,并输出这个最大数值。示例 1:
输入: g = [1,2,3], s = [1,1] 输出: 1 解释: 你有三个孩子和两块小饼干,3个孩子的胃口值分别是:1,2,3。 虽然你有两块小饼干,由于他们的尺寸都是1,你只能让胃口值是1的孩子满足。 所以你应该输出1。
示例 2:
输入: g = [1,2], s = [1,2,3] 输出: 2 解释: 你有两个孩子和三块小饼干,2个孩子的胃口值分别是1,2。 你拥有的饼干数量和尺寸都足以让所有孩子满足。 所以你应该输出2.
提示:
1 <= g.length <= 3 * 104
0 <= s.length <= 3 * 104
1 <= g[i], s[j] <= 231 - 1
贪心+双指针
- 时间复杂度:$O(mlogm+nlogn)$,其中 $m$ 和 $n$ 分别是数组 $g$ 和 $s$ 的长度。对两个数组排序的时间复杂度是$O(mlogm+nlogn)$,遍历数组的时间复杂度是$O(m+n)$,因此总时间复杂度是$O(mlogm+nlogn)$。
- 空间复杂度:$O(logm+logn)$,其中 $m$ 和 $n$ 分别是数组 $g$ 和 $s$ 的长度。空间复杂度主要是排序的额外空间开销。
function findContentChildren(g: number[], s: number[]): number {
g.sort((a, b) => a - b); // 从小到大排序
s.sort((a, b) => a - b);
let si = 0;
let gi = 0;
let res = 0;
while (si < s.length && gi < g.length) {
if (s[si] >= g[gi]) {
gi++;
res++;
}
si++;
}
return res;
};
376.摆动序列
如果连续数字之间的差严格地在正数和负数之间交替,则数字序列称为 **摆动序列 。**第一个差(如果存在的话)可能是正数或负数。仅有一个元素或者含两个不等元素的序列也视作摆动序列。
- 例如,
[1, 7, 4, 9, 2, 5]
是一个 摆动序列 ,因为差值(6, -3, 5, -7, 3)
是正负交替出现的。- 相反,
[1, 4, 7, 2, 5]
和[1, 7, 4, 5, 5]
不是摆动序列,第一个序列是因为它的前两个差值都是正数,第二个序列是因为它的最后一个差值为零。子序列 可以通过从原始序列中删除一些(也可以不删除)元素来获得,剩下的元素保持其原始顺序。
给你一个整数数组
nums
,返回nums
中作为 摆动序列 的 最长子序列的长度 。示例 1:
输入:nums = [1,7,4,9,2,5] 输出:6 解释:整个序列均为摆动序列,各元素之间的差值为 (6, -3, 5, -7, 3) 。
示例 2:
输入:nums = [1,17,5,10,13,15,10,5,16,8] 输出:7 解释:这个序列包含几个长度为 7 摆动序列。 其中一个是 [1, 17, 10, 13, 10, 16, 8] ,各元素之间的差值为 (16, -7, 3, -3, 6, -8) 。
示例 3:
输入:nums = [1,2,3,4,5,6,7,8,9] 输出:2
提示:
1 <= nums.length <= 1000
0 <= nums[i] <= 1000
贪心解法一
思路:在遍历数组时,维护两个变量up和down,分别记录到当前位置为止,以上升和以下降结尾的最长摇摆子序列长度。当元素上升时,更新up为down+1;当元素下降时,更新down为up+1。最终结果是max(up, down)。
- 时间复杂度:$O(n)$。
- 空间复杂度:$O(1)$。
function wiggleMaxLength(nums: number[]): number {
if (nums.length < 2) { return nums.length };
let down = 1;
let up = 1;
for (let i = 1; i < nums.length; i++) {
if (nums[i] > nums[i - 1]) { // 上升
up = down + 1;
}
else if (nums[i] < nums[i - 1]) { // 下降
down = up + 1;
}
}
return Math.max(up, down);
};
贪心解法二
计算 prediff(nums[i] - nums[i-1]) 和 curdiff(nums[i+1] - nums[i]),如果prediff < 0 && curdiff > 0
或者 prediff > 0 && curdiff < 0
此时就有波动就需要统计。
本题要考虑三种情况:
- 情况一:上下坡中有平坡
- 情况二:数组首尾两端
- 情况三:单调坡中有平坡
- 时间复杂度:$O(n)$。
- 空间复杂度:$O(1)$。
function wiggleMaxLength(nums: number[]): number {
if (nums.length < 2) return nums.length;
let preDiff = 0;
let curDiff = 0;
let result = 1;
for (let i = 0; i < nums.length - 1; i++) {
curDiff = nums[i+1] - nums[i];
if ((preDiff <= 0 && curDiff > 0) || (preDiff >= 0 && curDiff < 0)) {
result++;
preDiff = curDiff;
}
}
return result;
};
动态规划
待完善
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
提示:
1 <= nums.length <= 105
-104 <= nums[i] <= 104
贪心
- 时间复杂度:$O(n)$。
- 空间复杂度:$O(1)$。
function maxSubArray(nums: number[]): number {
let res = -Infinity;
let sum = 0;
for (let i = 0; i < nums.length; i++) {
sum += nums[i];
res = Math.max(sum, res);
if (sum < 0) sum = 0;
}
return res;
};
动态规划
待完善
122.买卖股票的最佳时机Ⅱ
给你一个整数数组
prices
,其中prices[i]
表示某支股票第i
天的价格。在每一天,你可以决定是否购买和/或出售股票。你在任何时候 最多 只能持有 一股 股票。你也可以先购买,然后在 同一天 出售。
返回 你能获得的 最大 利润 。
示例 1:
输入:prices = [7,1,5,3,6,4] 输出:7 解释:在第 2 天(股票价格 = 1)的时候买入,在第 3 天(股票价格 = 5)的时候卖出, 这笔交易所能获得利润 = 5 - 1 = 4 。 随后,在第 4 天(股票价格 = 3)的时候买入,在第 5 天(股票价格 = 6)的时候卖出, 这笔交易所能获得利润 = 6 - 3 = 3 。 总利润为 4 + 3 = 7 。
示例 2:
输入:prices = [1,2,3,4,5] 输出:4 解释:在第 1 天(股票价格 = 1)的时候买入,在第 5 天 (股票价格 = 5)的时候卖出, 这笔交易所能获得利润 = 5 - 1 = 4 。 总利润为 4 。
示例 3:
输入:prices = [7,6,4,3,1] 输出:0 解释:在这种情况下, 交易无法获得正利润,所以不参与交易可以获得最大利润,最大利润为 0 。
提示:
1 <= prices.length <= 3 * 104
0 <= prices[i] <= 104
贪心
- 时间复杂度:$O(n)$。
- 空间复杂度:$O(1)$。
function maxProfit(prices: number[]): number {
let res = 0;
for (let i = 1; i < prices.length; i++) {
const price = prices[i] - prices[i - 1];
if (price > 0) {
res += price; // 贪心,只收集每天正利润
}
}
return res;
};
55.跳跃游戏
给定一个非负整数数组
nums
,你最初位于数组的 第一个下标 。数组中的每个元素代表你在该位置可以跳跃的最大长度。
判断你是否能够到达最后一个下标。
示例 1:
输入:nums = [2,3,1,1,4] 输出:true 解释:可以先跳 1 步,从下标 0 到达下标 1, 然后再从下标 1 跳 3 步到达最后一个下标。
示例 2:
输入:nums = [3,2,1,0,4] 输出:false 解释:无论怎样,总会到达下标为 3 的位置。但该下标的最大跳跃长度是 0 , 所以永远不可能到达最后一个下标。
提示:
1 <= nums.length <= 3 * 104
0 <= nums[i] <= 105
贪心
- 时间复杂度:$O(n)$。
- 空间复杂度:$O(1)$。
function canJump(nums: number[]): boolean {
let cover = 0;
for (let i = 0; i <= cover; i++) {
cover = Math.max(nums[i] + i, cover);
if (cover >= nums.length - 1) return true;
}
return false;
};
45.跳跃游戏Ⅱ
给定一个长度为
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]
。示例 1:
输入: nums = [2,3,1,1,4] 输出: 2 解释: 跳到最后一个位置的最小跳跃数是 2。 从下标为 0 跳到下标为 1 的位置,跳 1 步,然后跳 3 步到达数组的最后一个位置。
示例 2:
输入: nums = [2,3,0,1,4] 输出: 2
提示:
1 <= nums.length <= 104
0 <= nums[i] <= 1000
- 题目保证可以到达
nums[n-1]
贪心
- 时间复杂度:$O(n)$。
- 空间复杂度:$O(1)$。
function jump(nums: number[]): number {
if (nums.length === 1) return 0;
let ans = 0;
let start = 0;
let end = 1;
while (end < nums.length) {
let max = 0;
for (let i = start; i < end; i++) {
max = Math.max(nums[i] + i, max);
}
start = end;
end = max + 1;
ans++;
}
return ans;
};
1005.K次取反最大化的数组和
给你一个整数数组
nums
和一个整数k
,按以下方法修改该数组
- 选择某个下标
i
并将nums[i]
替换为-nums[i]
。重复这个过程恰好
k
次。可以多次选择同一个下标i
。以这种方式修改数组后,返回数组 可能的最大和 。
示例 1:
输入:nums = [4,2,3], k = 1 输出:5 解释:选择下标 1 ,nums 变为 [4,-2,3] 。
示例 2:
输入:nums = [3,-1,0,2], k = 3 输出:6 解释:选择下标 (1, 2, 2) ,nums 变为 [3,1,0,2] 。
示例 3:
输入:nums = [2,-3,-1,5,-4], k = 2 输出:13 解释:选择下标 (1, 4) ,nums 变为 [2,3,-1,5,4] 。
提示:
1 <= nums.length <= 104
-100 <= nums[i] <= 100
1 <= k <= 104
贪心
思路:
第一步:将数组按照绝对值大小从大到小排序,注意要按照绝对值的大小
第二步:从前向后遍历,遇到负数将其变为正数,同时K--
第三步:如果K还大于0,那么反复转变数值最小的元素,将K用完
第四步:求和
时间复杂度:$O(nlogn)$。
空间复杂度:$O(1)$。
function largestSumAfterKNegations(nums: number[], k: number): number {
nums.sort((a, b) => Math.abs(b) - Math.abs(a)); // 按绝对值从大到小排
for (let i = 0; i < nums.length; i++) {
if (nums[i] < 0 && k > 0) {
nums[i] = -nums[i];
k--;
}
if (k === 0) break;
}
if (k % 2 === 1) nums[nums.length - 1] *= -1;
let res = 0;
for (let num of nums) {
res += num;
}
return res;
};
134.加油站
在一条环路上有
n
个加油站,其中第i
个加油站有汽油gas[i]
升。你有一辆油箱容量无限的的汽车,从第
i
个加油站开往第i+1
个加油站需要消耗汽油cost[i]
升。你从其中的一个加油站出发,开始时油箱为空。给定两个整数数组
gas
和cost
,如果你可以按顺序绕环路行驶一周,则返回出发时加油站的编号,否则返回-1
。如果存在解,则 保证 它是 唯一 的。示例 1:
输入: gas = [1,2,3,4,5], cost = [3,4,5,1,2] 输出: 3 解释: 从 3 号加油站(索引为 3 处)出发,可获得 4 升汽油。此时油箱有 = 0 + 4 = 4 升汽油 开往 4 号加油站,此时油箱有 4 - 1 + 5 = 8 升汽油 开往 0 号加油站,此时油箱有 8 - 2 + 1 = 7 升汽油 开往 1 号加油站,此时油箱有 7 - 3 + 2 = 6 升汽油 开往 2 号加油站,此时油箱有 6 - 4 + 3 = 5 升汽油 开往 3 号加油站,你需要消耗 5 升汽油,正好足够你返回到 3 号加油站。 因此,3 可为起始索引。
示例 2:
输入: gas = [2,3,4], cost = [3,4,3] 输出: -1 解释: 你不能从 0 号或 1 号加油站出发,因为没有足够的汽油可以让你行驶到下一个加油站。 我们从 2 号加油站出发,可以获得 4 升汽油。 此时油箱有 = 0 + 4 = 4 升汽油 开往 0 号加油站,此时油箱有 4 - 3 + 2 = 3 升汽油 开往 1 号加油站,此时油箱有 3 - 3 + 3 = 3 升汽油 你无法返回 2 号加油站,因为返程需要消耗 4 升汽油,但是你的油箱只有 3 升汽油。 因此,无论怎样,你都不可能绕环路行驶一周。
提示:
gas.length == n
cost.length == n
1 <= n <= 105
0 <= gas[i], cost[i] <= 104
贪心
- 时间复杂度:$O(n)$。
- 空间复杂度:$O(1)$。
function canCompleteCircuit(gas: number[], cost: number[]): number {
let spare = 0;
let minSpare = Infinity;
let minIndex = 0;
for (let i = 0; i < gas.length; i++) {
spare += gas[i] - cost[i];
if (spare < minSpare) {
minSpare = spare;
minIndex = i + 1;
}
}
return spare < 0 ? -1 : minIndex % gas.length;
};
135.分发糖果
n
个孩子站成一排。给你一个整数数组ratings
表示每个孩子的评分。你需要按照以下要求,给这些孩子分发糖果:
- 每个孩子至少分配到
1
个糖果。- 相邻两个孩子评分更高的孩子会获得更多的糖果。
请你给每个孩子分发糖果,计算并返回需要准备的 最少糖果数目 。
示例 1:
输入:ratings = [1,0,2] 输出:5 解释:你可以分别给第一个、第二个、第三个孩子分发 2、1、2 颗糖果。
示例 2:
输入:ratings = [1,2,2] 输出:4 解释:你可以分别给第一个、第二个、第三个孩子分发 1、2、1 颗糖果。 第三个孩子只得到 1 颗糖果,这满足题面中的两个条件。
提示:
n == ratings.length
1 <= n <= 2 * 104
0 <= ratings[i] <= 2 * 104
贪心
- 时间复杂度:$O(N)$,遍历两遍数组即可得到结果;
- 空间复杂度:$O(N)$,需要借用
leftArr
和rightArr
的线性额外空间。
function candy(ratings: number[]): number {
let leftArr = new Array(ratings.length).fill(1);
let rightArr = new Array(ratings.length).fill(1);
for (let i = 1; i < leftArr.length; i++) {
if (ratings[i] > ratings[i - 1]) {
leftArr[i] = leftArr[i - 1] + 1;
}
}
let count = leftArr[ratings.length - 1];
for (let i = rightArr.length - 2; i >= 0; i--) {
if (ratings[i] > ratings[i + 1]) {
rightArr[i] = rightArr[i+1] + 1;
}
count += Math.max(leftArr[i], rightArr[i]);
}
return count;
};
860.柠檬水找零
在柠檬水摊上,每一杯柠檬水的售价为
5
美元。顾客排队购买你的产品,(按账单bills
支付的顺序)一次购买一杯。每位顾客只买一杯柠檬水,然后向你付
5
美元、10
美元或20
美元。你必须给每个顾客正确找零,也就是说净交易是每位顾客向你支付5
美元。注意,一开始你手头没有任何零钱。
给你一个整数数组
bills
,其中bills[i]
是第i
位顾客付的账。如果你能给每位顾客正确找零,返回true
,否则返回false
。示例 1:
输入:bills = [5,5,5,10,20] 输出:true 解释: 前 3 位顾客那里,我们按顺序收取 3 张 5 美元的钞票。 第 4 位顾客那里,我们收取一张 10 美元的钞票,并返还 5 美元。 第 5 位顾客那里,我们找还一张 10 美元的钞票和一张 5 美元的钞票。 由于所有客户都得到了正确的找零,所以我们输出 true。
示例 2:
输入:bills = [5,5,10,10,20] 输出:false 解释: 前 2 位顾客那里,我们按顺序收取 2 张 5 美元的钞票。 对于接下来的 2 位顾客,我们收取一张 10 美元的钞票,然后返还 5 美元。 对于最后一位顾客,我们无法退回 15 美元,因为我们现在只有两张 10 美元的钞票。 由于不是每位顾客都得到了正确的找零,所以答案是 false。
提示:
1 <= bills.length <= 105
bills[i]
不是5
就是10
或是20
贪心
思路:
有如下三种情况:
情况一:账单是5,直接收下。
情况二:账单是10,消耗一个5,增加一个10
情况三:账单是20,优先消耗一个10和一个5,如果不够,再消耗三个5(贪心,先消耗10和5,不行再消耗3个5)
function lemonadeChange(bills: number[]): boolean {
let five = 0, ten = 0;
for (let i = 0; i < bills.length; i++) {
if (bills[i] === 5) {
five++;
} else if (bills[i] === 10) {
if (five > 0) {
five--;
ten++;
} else {
return false;
}
} else {
if (five > 0 && ten > 0) {
five--;
ten--;
} else if (five > 2) {
five -= 3;
} else {
return false
}
}
}
return true;
};
406.根据身高重建队列
假设有打乱顺序的一群人站成一个队列,数组
people
表示队列中一些人的属性(不一定按顺序)。每个people[i] = [hi, ki]
表示第i
个人的身高为hi
,前面 正好 有ki
个身高大于或等于hi
的人。请你重新构造并返回输入数组
people
所表示的队列。返回的队列应该格式化为数组queue
,其中queue[j] = [hj, kj]
是队列中第j
个人的属性(queue[0]
是排在队列前面的人)。示例 1:
输入:people = [[7,0],[4,4],[7,1],[5,0],[6,1],[5,2]] 输出:[[5,0],[7,0],[5,2],[6,1],[4,4],[7,1]] 解释: 编号为 0 的人身高为 5 ,没有身高更高或者相同的人排在他前面。 编号为 1 的人身高为 7 ,没有身高更高或者相同的人排在他前面。 编号为 2 的人身高为 5 ,有 2 个身高更高或者相同的人排在他前面,即编号为 0 和 1 的人。 编号为 3 的人身高为 6 ,有 1 个身高更高或者相同的人排在他前面,即编号为 1 的人。 编号为 4 的人身高为 4 ,有 4 个身高更高或者相同的人排在他前面,即编号为 0、1、2、3 的人。 编号为 5 的人身高为 7 ,有 1 个身高更高或者相同的人排在他前面,即编号为 1 的人。 因此 [[5,0],[7,0],[5,2],[6,1],[4,4],[7,1]] 是重新构造后的队列。
示例 2:
输入:people = [[6,0],[5,0],[4,0],[3,2],[2,2],[1,4]] 输出:[[4,0],[5,0],[2,2],[3,2],[1,4],[6,0]]
提示:
1 <= people.length <= 2000
0 <= hi <= 106
0 <= ki < people.length
- 题目数据确保队列可以被重建
排序+贪心
思路:
身高从大到小排列,k从小到大排列。
局部最优:优先按身高高的people的k来插入。插入操作过后的people满足队列属性
全局最优:最后都做完插入操作,整个队列满足题目队列属性
- 时间复杂度:$O(n^2)$,n 是数组people的长度。我们需要 $O(nlogn)$的时间进行排序,随后需要 $O(n^2)$的时间遍历每一个人并将他们放入队列中。
- 空间复杂度:$O(logn)$。
function reconstructQueue(people: number[][]): number[][] {
people.sort((a, b) => a[0] === b[0] ? a[1] - b[1] : b[0] - a[0]); // 身高从大到小,k从小到大
const res: number[][] = [];
for (let i = 0; i < people.length; i++) {
res.splice(people[i][1], 0, people[i]);
}
return res;
};
用最少数量的箭引爆气球
452.有一些球形气球贴在一堵用 XY 平面表示的墙面上。墙面上的气球记录在整数数组
points
,其中points[i] = [xstart, xend]
表示水平直径在xstart
和xend
之间的气球。你不知道气球的确切 y 坐标。一支弓箭可以沿着 x 轴从不同点 完全垂直 地射出。在坐标
x
处射出一支箭,若有一个气球的直径的开始和结束坐标为x``start
,x``end
, 且满足xstart ≤ x ≤ x``end
,则该气球会被 引爆 。可以射出的弓箭的数量 没有限制 。 弓箭一旦被射出之后,可以无限地前进。给你一个数组
points
,返回引爆所有气球所必须射出的 最小 弓箭数 。示例 1:
输入:points = [[10,16],[2,8],[1,6],[7,12]] 输出:2 解释:气球可以用2支箭来爆破: -在x = 6处射出箭,击破气球[2,8]和[1,6]。 -在x = 11处发射箭,击破气球[10,16]和[7,12]。
示例 2:
输入:points = [[1,2],[3,4],[5,6],[7,8]] 输出:4 解释:每个气球需要射出一支箭,总共需要4支箭。
示例 3:
输入:points = [[1,2],[2,3],[3,4],[4,5]] 输出:2 解释:气球可以用2支箭来爆破: - 在x = 2处发射箭,击破气球[1,2]和[2,3]。 - 在x = 4处射出箭,击破气球[3,4]和[4,5]。
提示:
1 <= points.length <= 105
points[i].length == 2
-231 <= xstart < xend <= 231 - 1
排序+贪心
局部最优:当气球出现重叠,一起射,所用弓箭最少。全局最优:把所有气球射爆所用弓箭最少。
- 时间复杂度:$O(nlog n)$,因为有一个快排
- 空间复杂度:$O(1)$,有一个快排,最差情况(倒序)时,需要n次递归调用。因此确实需要$O(n)$的栈空间
function findMinArrowShots(points: number[][]): number {
let res = 0;
points.sort((a, b) => a[1] - b[1]);
let curNum = Infinity;
let i = 0;
while (i < points.length) {
if (curNum < points[i][0] || curNum > points[i][1]) {
curNum = points[i][1]; // 贪心,取最大边界
res++;
}
i++;
}
return res;
};
无重叠区间
435.给定一个区间的集合
intervals
,其中intervals[i] = [starti, endi]
。返回 需要移除区间的最小数量,使剩余区间互不重叠 。示例 1:
输入: intervals = [[1,2],[2,3],[3,4],[1,3]] 输出: 1 解释: 移除 [1,3] 后,剩下的区间没有重叠。
示例 2:
输入: intervals = [ [1,2], [1,2], [1,2] ] 输出: 2 解释: 你需要移除两个 [1,2] 来使剩下的区间没有重叠。
示例 3:
输入: intervals = [ [1,2], [2,3] ] 输出: 0 解释: 你不需要移除任何区间,因为它们已经是无重叠的了。
提示:
1 <= intervals.length <= 105
intervals[i].length == 2
-5 * 104 <= starti < endi <= 5 * 104
排序+贪心
思路:
- 将区间按照结束时间从小到大进行排序。
- 初始化一个变量来记录不重叠区间的数量,比如命名为
count
,并设置其初始值为1,因为我们总可以选择第一个区间。同时,维护一个变量end
来记录当前已选区间的结束时间,初始值为排序后的第一个区间的结束时间。 - 从第二个区间开始,遍历每一个区间。对于每个区间,比较它的起始时间与
end
的值,如果起始时间大于等于end
,则说明该区间与前面已选择的区间不重叠,我们可以选择这个区间,将count
增加1,并更新end
的值为当前区间的结束时间。 - 遍历完所有区间后,
count
就是最多的不重叠区间的数量。原问题要求移除的最少区间数量,因此答案是总区间数减去count
。
- 时间复杂度:$O(nlogn)$。
- 空间复杂度:$O(n)$,有一个快排,最差情况(倒序)时,需要n次递归调用。因此确实需要$O(n)$的栈空间。
function eraseOverlapIntervals(intervals: number[][]): number {
intervals.sort((a, b) => a[1] - b[1]);
let count = 1; // 不重复区间数量
let end = intervals[0][1];
for (let i = 1; i < intervals.length; i++) {
if (intervals[i][0] >= end) { // 说明是另外一个区间
end = intervals[i][1];
count++;
}
}
return intervals.length - count;
};
动态规划
待完善
763.划分字母区间
给你一个字符串
s
。我们要把这个字符串划分为尽可能多的片段,同一字母最多出现在一个片段中。注意,划分结果需要满足:将所有划分结果按顺序连接,得到的字符串仍然是
s
。返回一个表示每个字符串片段的长度的列表。
示例 1:
输入:s = "ababcbacadefegdehijhklij" 输出:[9,7,8] 解释: 划分结果为 "ababcbaca"、"defegde"、"hijhklij" 。 每个字母最多出现在一个片段中。 像 "ababcbacadefegde", "hijhklij" 这样的划分是错误的,因为划分的片段数较少。
示例 2:
输入:s = "eccbbbbdec" 输出:[10]
提示:
1 <= s.length <= 500
s
仅由小写英文字母组成
贪心
思路:
- 遍历字符串,记录每个字母最后一次出现的位置。
- 再次遍历字符串,用两个指针
start
和end
来表示当前片段的开始和结束位置。end
初始时应该是第一个字母最后出现的位置。 - 对于每个字母,找到它最后出现的位置,并用它来更新
end
。 - 当我们到达
end
位置时,我们找到了一个片段,将该片段的长度加入结果列表,并将start
设为end + 1
,继续寻找下一个片段。 - 重复步骤3和4,直到遍历完整个字符串。
- 时间复杂度:$O(n)$。
- 空间复杂度:$O(k)$,k是字符集的大小。
function partitionLabels(s: string): number[] {
const letterLocation: Map<string, number> = new Map();
for (let i = 0; i < s.length; i++) {
letterLocation.set(s[i], i);
}
const res: number[] = [];
let start = 0, end = 0;
for (let i = 0; i < s.length; i++) {
end = Math.max(end, letterLocation.get(s[i])); // 局部最优
if (i === end) { // 说明到达字母的最后位置
res.push(end - start + 1);
start = end + 1;
}
}
return res;
};
合并区间
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 <= intervals.length <= 104
intervals[i].length == 2
0 <= starti <= endi <= 104
排序+贪心
思路:
我们将列表中的区间按照左端点升序排序。然后我们将第一个区间加入 res
数组中,并按顺序依次考虑之后的每个区间:
- 如果当前区间的左端点在数组
res
中最后一个区间的右端点之后,那么它们不会重合,我们可以直接将这个区间加入数组 merged 的末尾; - 否则,它们重合,我们需要用当前区间的右端点更新数组
res
中最后一个区间的右端点,将其置为二者的较大值。
- 时间复杂度:$O(nlogn)$。
- 空间复杂度:$O(n)$。
function merge(intervals: number[][]): number[][] {
intervals.sort((a, b) => a[0] - b[0]);
const res: number[][] = [];
for (let i = 0; i < intervals.length; i++) {
if (!res.length || res[res.length - 1][1] < intervals[i][0]) {
res.push(intervals[i]);
} else {
// 局部最优
res[res.length - 1][1] = Math.max(res[res.length - 1][1], intervals[i][1]);
}
}
return res;
};
单调递增的数字
738.当且仅当每个相邻位数上的数字
x
和y
满足x <= y
时,我们称这个整数是单调递增的。给定一个整数
n
,返回 小于或等于n
的最大数字,且数字呈 单调递增 。示例 1:
输入: n = 10 输出: 9
示例 2:
输入: n = 1234 输出: 1234
示例 3:
输入: n = 332 输出: 299
提示:
0 <= n <= 109
贪心
思路:
- 从右到左遍历输入数字的每一位,设置一个 marker 标记
- 对于每一位,如果发现它比其左边的位小,则将左边的位减一,并将当前位及其右边的所有位都设置为9,因为我们希望数值尽可能大。
- 完成遍历后,从marker的位置从左到右遍历,将每个下标对应的值置为 9
- 时间复杂度:$O(n)$,n为数字长度。
- 空间复杂度:$O(n)$,需要一个字符数组。
function monotoneIncreasingDigits(n: number): number {
const strArr = String(n).split("");
let marker = strArr.length;
for (let i = strArr.length - 1; i > 0; i--) {
if (Number(strArr[i - 1]) > Number(strArr[i])) { // 局部最优
strArr[i] = '9';
marker = i;
strArr[i - 1] = String(Number(strArr[i - 1]) - 1);
}
}
// 将后面的数字都变成9
for (let i = marker; i < strArr.length; i++) {
strArr[i] = '9';
}
return Number(strArr.join(""));
};
968.监控二叉树
给定一个二叉树,我们在树的节点上安装摄像头。
节点上的每个摄影头都可以监视其父对象、自身及其直接子对象。
计算监控树的所有节点所需的最小摄像头数量。
示例 1:
输入:[0,0,null,0,0] 输出:1 解释:如图所示,一台摄像头足以监控所有节点。
示例 2:
输入:[0,0,null,0,null,0,null,null,0] 输出:2 解释:需要至少两个摄像头来监视树的所有节点。 上图显示了摄像头放置的有效位置之一。
提示:
- 给定树的节点数的范围是
[1, 1000]
。- 每个节点的值都是 0。
后序遍历-DFS+贪心
解题思路:
使用深度优先搜索(DFS)对二叉树进行后序遍历。
定义三种状态来描述节点的覆盖情况:
- 0:该节点未被覆盖。
- 1:该节点已被覆盖,且该节点上安装了摄像头。
- 2:该节点已被覆盖,但该节点上没有摄像头。
对于每个节点,根据其左右子节点的状态来决定该节点的状态:
如果左右子节点都被覆盖但没有摄像头(状态2),那么当前节点未被覆盖(状态0)。
如果左或右子节点未被覆盖(状态0),那么在当前节点安装摄像头,使其变为状态1,并增加摄像头计数。
如果左或右子节点上有摄像头(状态1),那么当前节点已被覆盖但没有摄像头(状态2)。
对于根节点,如果其状态为0(未被覆盖),则在根节点上安装摄像头,并增加摄像头计数。
返回总的摄像头计数。
/**
* Definition for a binary tree node.
* class TreeNode {
* val: number
* left: TreeNode | null
* right: TreeNode | null
* constructor(val?: number, left?: TreeNode | null, right?: TreeNode | null) {
* this.val = (val===undefined ? 0 : val)
* this.left = (left===undefined ? null : left)
* this.right = (right===undefined ? null : right)
* }
* }
*/
function minCameraCover(root: TreeNode | null): number {
let count = 0;
function dfs(cur: TreeNode | null): number {
if (cur === null) return 2;
const left = dfs(cur.left);
const right = dfs(cur.right);
if (left === 2 && right === 2) { // 左右子节点都有覆盖
return 0;
}
if (left === 0 || right === 0) { // 左或右子节点无覆盖,局部最优
count++;
return 1;
}
if (left === 1 || right === 1) { // 左或右子节点有摄像头
return 2;
}
}
if (dfs(root) === 0) {
count++;
}
return count;
};
动态规划
动态规划(Dynamic Programming),简称DP,如果某一问题有很多重叠子问题,使用动态规划是最有效的。
动态规划中每一个状态一定是由上一个状态推导出来的,这一点就区分于贪心,贪心没有状态推导,而是从局部直接选最优的。
动态规划五步曲:
- 确定dp数组(dp table)以及下标的含义
- 确定递推公式
- dp数组如何初始化
- 确定遍历顺序
- 举例推导dp数组
斐波那契数
509.斐波那契数 (通常用
F(n)
表示)形成的序列称为 斐波那契数列 。该数列由0
和1
开始,后面的每一项数字都是前面两项数字的和。也就是:F(0) = 0,F(1) = 1 F(n) = F(n - 1) + F(n - 2),其中 n > 1
给定
n
,请计算F(n)
。示例 1:
输入:n = 2 输出:1 解释:F(2) = F(1) + F(0) = 1 + 0 = 1
示例 2:
输入:n = 3 输出:2 解释:F(3) = F(2) + F(1) = 1 + 1 = 2
示例 3:
输入:n = 4 输出:3 解释:F(4) = F(3) + F(2) = 2 + 1 = 3
提示:
0 <= n <= 30
递归
- 时间复杂度:$O(2^n)$。
- 空间复杂度:$O(n)$。
function fib(n: number): number {
if (n <= 1) return n;
return fib(n - 1) + fib(n - 2);
};
动态规划一
动态规划五部曲思路:
- dp[i]为第i个斐波那契数值;
- 递推公式为
dp[i] = dp[i-1] + dp[i-2]
; - dp数组初始化:
dp[0]=0;dp[1]=1
; - 遍历顺序:从前到后遍历;
- 举例推导dp数组:dp[10]时为[0,1,1,2,3,5,8,13,21,34,55]。
- 时间复杂度:$O(n)$。
- 空间复杂度:$O(n)$。
function fib(n: number): number {
if (n <= 1) return n;
const dp: number[] = [];
dp[0] = 0; // dp初始化
dp[1] = 1; // dp初始化
for (let i = 2; i <= n; i++) { // 遍历顺序
dp[i] = dp[i-1] + dp[i-2]; // 每一个状态由上一个状态推导出来
}
return dp[n];
};
动态规划二
- 时间复杂度:$O(n)$。
- 空间复杂度:$O(1)$。
function fib(n: number): number {
if (n <= 1) return n;
let p = 0,
q = 1
for (let i = 2; i <= n; i++) {
const sum = p + q;
p = q;
q = sum;
}
return q;
};
70.爬楼梯
假设你正在爬楼梯。需要
n
阶你才能到达楼顶。每次你可以爬
1
或2
个台阶。你有多少种不同的方法可以爬到楼顶呢?示例 1:
输入:n = 2 输出:2 解释:有两种方法可以爬到楼顶。 1. 1 阶 + 1 阶 2. 2 阶
示例 2:
输入:n = 3 输出:3 解释:有三种方法可以爬到楼顶。 1. 1 阶 + 1 阶 + 1 阶 2. 1 阶 + 2 阶 3. 2 阶 + 1 阶
提示:
1 <= n <= 45
动态规划
- 时间复杂度:$O(n)$。
- 空间复杂度:$O(1)$。
// 写法一,滚动数组
function climbStairs(n: number): number {
let p = 0;
let q = 1;
for (let i = 1; i <= n; i++) {
let r = p + q;
p = q;
q = r;
}
return q;
};
- 时间复杂度:$O(n)$。
- 空间复杂度:$O(n)$。
// 写法二
function climbStairs(n: number): number {
if (n <= 3) return n;
let dp: number[] = [0, 1, 2];
for (let i = 3; i <= n; i++) {
dp[i] = dp[i - 1] + dp[i - 2];
}
return dp[n];
};
动态规划-完全背包-滚动数组
- 时间复杂度: $O(nm)$。
- 空间复杂度: $O(n)$。
function climbStairs(n: number): number {
const dp: number[] = new Array(n + 1).fill(0);
dp[0] = 1;
const nums = [1, 2];
for (let i = 0; i <= n; i++) {
for (let j = 0; j < nums.length; j++) {
if (i >= nums[j]) {
dp[i] += dp[i - nums[j]];
}
}
}
return dp[n];
};
746.使用最小花费爬楼梯
给你一个整数数组
cost
,其中cost[i]
是从楼梯第i
个台阶向上爬需要支付的费用。一旦你支付此费用,即可选择向上爬一个或者两个台阶。你可以选择从下标为
0
或下标为1
的台阶开始爬楼梯。请你计算并返回达到楼梯顶部的最低花费。
示例 1:
输入:cost = [10,15,20] 输出:15 解释:你将从下标为 1 的台阶开始。 - 支付 15 ,向上爬两个台阶,到达楼梯顶部。 总花费为 15 。
示例 2:
输入:cost = [1,100,1,1,1,100,1,1,100,1] 输出:6 解释:你将从下标为 0 的台阶开始。 - 支付 1 ,向上爬两个台阶,到达下标为 2 的台阶。 - 支付 1 ,向上爬两个台阶,到达下标为 4 的台阶。 - 支付 1 ,向上爬两个台阶,到达下标为 6 的台阶。 - 支付 1 ,向上爬一个台阶,到达下标为 7 的台阶。 - 支付 1 ,向上爬两个台阶,到达下标为 9 的台阶。 - 支付 1 ,向上爬一个台阶,到达楼梯顶部。 总花费为 6 。
提示:
2 <= cost.length <= 1000
0 <= cost[i] <= 999
动态规划
思路
- 定义一个数组dp,其中dp[i]表示到达第i个台阶的最小花费。
- 初始化数组:到达第0个和第1个台阶不需要任何花费,因此设置dp[0] 和 dp[1] 都为0。
- 遍历从2到cost的长度,对于每个台阶i,计算达到该台阶的最小花费。有两种方式到达台阶i,一种是从第i-1个台阶一步到达,另一种是从第i-2个台阶一步到达。因此,到达第i个台阶的最小花费是这两种方式的较小值,即
dp[i] = Math.min(dp[i - 1] + cost[i - 1], dp[i - 2] + cost[i - 2])
。 - dp[cost.length] 就是达到顶部的最小花费,返回这个值。
- 时间复杂度:$O(n)$。
- 空间复杂度:$O(n)$。
// 写法一
function minCostClimbingStairs(cost: number[]): number {
const dp: number[] = [];
dp[0] = 0; // 爬下标0无须花费
dp[1] = 0; // 爬下标1无须花费
for (let i = 2; i <= cost.length; i++) {
dp[i] = Math.min(dp[i - 1] + cost[i - 1], dp[i - 2] + cost[i - 2]);
}
return dp[cost.length];
};
- 时间复杂度:$O(n)$。
- 空间复杂度:$O(1)$。
// 写法二,优化空间复杂度
function minCostClimbingStairs(cost: number[]): number {
let dp0 = 0;
let dp1 = 0;
for (let i = 2; i <= cost.length; i++) {
const dpi = Math.min(dp1 + cost[i - 1], dp0 + cost[i - 2]);
dp0 = dp1;
dp1 = dpi;
}
return dp1;
};
不同路径
62.一个机器人位于一个
m x n
网格的左上角 (起始点在下图中标记为 “Start” )。机器人每次只能向下或者向右移动一步。机器人试图达到网格的右下角(在下图中标记为 “Finish” )。
问总共有多少条不同的路径?
示例 1:
输入:m = 3, n = 7 输出:28
示例 2:
输入:m = 3, n = 2 输出:3 解释: 从左上角开始,总共有 3 条路径可以到达右下角。 1. 向右 -> 向下 -> 向下 2. 向下 -> 向下 -> 向右 3. 向下 -> 向右 -> 向下
示例 3:
输入:m = 7, n = 3 输出:28
示例 4:
输入:m = 3, n = 3 输出:6
提示:
1 <= m, n <= 100
- 题目数据保证答案小于等于
2 * 109
动态规划
- 时间复杂度:$O(m*n)$。
- 空间复杂度:$O(m*n)$。
// 写法一
function uniquePaths(m: number, n: number): number {
let dp: number[][] = [];
dp = Array.from({ length: m }, () => new Array(n).fill(0)); // 初始化
for (let i = 0; i < m; i++) dp[i][0] = 1;
for (let j = 0; j < n; j++) dp[0][j] = 1;
for (let i = 1; i < m; i++) {
for (let j = 1; j < n; j++) {
dp[i][j] = dp[i][j - 1] + dp[i - 1][j]; // 递推关系
}
}
return dp[m - 1][n - 1];
};
- 时间复杂度:$O(m*n)$。
- 空间复杂度:$O(n)$。
// 写法二,空间优化
function uniquePaths(m: number, n: number): number {
const dp = new Array(n).fill(1); // 对应m行
for (let i = 1; i < m; i++) {
for (let j = 1; j < n; j++) {
dp[j] += dp[j - 1];
}
}
return dp[n - 1];
};
不同路径Ⅱ
63.一个机器人位于一个
m x n
网格的左上角 (起始点在下图中标记为 “Start” )。机器人每次只能向下或者向右移动一步。机器人试图达到网格的右下角(在下图中标记为 “Finish”)。
现在考虑网格中有障碍物。那么从左上角到右下角将会有多少条不同的路径?
网格中的障碍物和空位置分别用
1
和0
来表示。示例 1:
输入:obstacleGrid = [[0,0,0],[0,1,0],[0,0,0]] 输出:2 解释:3x3 网格的正中间有一个障碍物。 从左上角到右下角一共有 2 条不同的路径: 1. 向右 -> 向右 -> 向下 -> 向下 2. 向下 -> 向下 -> 向右 -> 向右
示例 2:
输入:obstacleGrid = [[0,1],[0,0]] 输出:1
提示:
m == obstacleGrid.length
n == obstacleGrid[i].length
1 <= m, n <= 100
obstacleGrid[i][j]
为0
或1
动态规划
- 时间复杂度:$O(m*n)$。
- 空间复杂度:$O(m*n)$。
// 写法一
function uniquePathsWithObstacles(obstacleGrid: number[][]): number {
const m = obstacleGrid.length;
const n = obstacleGrid[0].length;
if (obstacleGrid[m - 1][n - 1] === 1 || obstacleGrid[0][0] === 1) return 0;
let dp: number[][] = [];
dp = Array.from({ length: m }, () => new Array(n).fill(0)); // 初始化
for (let i = 0; i < m && obstacleGrid[i][0] !== 1; i++) {
dp[i][0] = 1;
}
for (let j = 0; j < n && obstacleGrid[0][j] !== 1; j++) {
dp[0][j] = 1;
}
for (let i = 1; i < m; i++) {
for (let j = 1; j < n; j++) {
if (obstacleGrid[i][j] === 1) continue;
dp[i][j] = dp[i - 1][j] + dp[i][j - 1];
}
}
return dp[m - 1][n - 1];
};
343.整数拆分
给定一个正整数
n
,将其拆分为k
个 正整数 的和(k >= 2
),并使这些整数的乘积最大化。返回 你可以获得的最大乘积 。
示例 1:
输入: n = 2 输出: 1 解释: 2 = 1 + 1, 1 × 1 = 1。
示例 2:
输入: n = 10 输出: 36 解释: 10 = 3 + 3 + 4, 3 × 3 × 4 = 36。
提示:
2 <= n <= 58
动态规划
思路:
dp[i]中i下标代表最大乘积。递推公式:
从1遍历j,然后有两种渠道得到dp[i].
- 一个是j * (i - j) 直接相乘。
- 一个是j * dp[i - j],相当于是拆分(i - j),dp[i-j]相当于拆分多个正整数。
得出:dp[i] = max(dp[i], max(i * (i-j), j * dp[i-j]))
- 时间复杂度:$O(n^2)$。
- 空间复杂度:$O(n)$。
function integerBreak(n: number): number {
const dp: number[] = new Array(n + 1).fill(1); // 初始化
for (let i = 3; i <= n; i++) {
for (let j = 1; j < i; j++) {
dp[i] = Math.max(dp[i], Math.max(j * (i - j), j * dp[i - j])); // 状态转移公式
}
}
return dp[n];
};
不同的二叉搜索树
96.给你一个整数
n
,求恰由n
个节点组成且节点值从1
到n
互不相同的 二叉搜索树 有多少种?返回满足题意的二叉搜索树的种数。示例 1:
输入:n = 3 输出:5
示例 2:
输入:n = 1 输出:1
提示:
1 <= n <= 19
动态规划
思路:
dp[i],下标i表示二叉搜索树的种类个数;
dp[3],就是 元素1为头结点搜索树的数量 + 元素2为头结点搜索树的数量 + 元素3为头结点搜索树的数量
- 元素1为头结点搜索树的数量 = 右子树有2个元素的搜索树数量 * 左子树有0个元素的搜索树数量
- 元素2为头结点搜索树的数量 = 右子树有1个元素的搜索树数量 * 左子树有1个元素的搜索树数量
- 元素3为头结点搜索树的数量 = 右子树有0个元素的搜索树数量 * 左子树有2个元素的搜索树数量
得出状态转移公式为
dp[i] += dp[j-1] * dp[i-j]
。dp[0] = 1,dp[1] = 1
for (int i = 1; i <= n; i++) { for (int j = 1; j <= i; j++) { dp[i] += dp[j - 1] * dp[i - j]; } }
- 时间复杂度:$O(n^2)$。
- 空间复杂度:$O(n)$。
function numTrees(n: number): number {
const dp: number[] = new Array(n + 1).fill(0);
dp[0] = 1; // 初始化。0也是一颗空树;
dp[1] = 1;
for (let i = 2; i <= n; i++) {
for (let j = 1; j <= i; j++) {
dp[i] += dp[j - 1] * dp[i - j]; // 以j为根结点,j-i为左子树,i-j为右子树
}
}
return dp[n];
};
背包问题
01背包二维数组状态转移方程:
dp[i][j] = max(dp[i - 1][j], dp[i - 1][j - weight[i]] + value[i]);
01背包滚动数组状态转移方程:
dp[j] = Math.max(dp[j], dp[j-weight[i]] + value[i]);
01背包内嵌的循环是从大到小遍历,为了保证每个物品仅被添加一次。
而完全背包的物品是可以添加多次的,所以要从小到大去遍历,即:
// 先遍历物品,再遍历背包 for(int i = 0; i < weight.size(); i++) { // 遍历物品 for(int j = weight[i]; j <= bagWeight ; j++) { // 遍历背包容量 dp[j] = max(dp[j], dp[j - weight[i]] + value[i]); } }
416.分割等和子集
给你一个 只包含正整数 的 非空 数组
nums
。请你判断是否可以将这个数组分割成两个子集,使得两个子集的元素和相等。示例 1:
输入:nums = [1,5,11,5] 输出:true 解释:数组可以分割成 [1, 5, 5] 和 [11] 。
示例 2:
输入:nums = [1,2,3,5] 输出:false 解释:数组不能分割成两个元素和相等的子集。
提示:
1 <= nums.length <= 200
1 <= nums[i] <= 100
动态规划-01背包-二维数组
思路:
只有确定了如下四点,才能把01背包问题套到本题上来。
- 背包的体积为sum / 2
- 背包要放入的商品(集合里的元素)重量为 元素的数值,价值也为元素的数值
- 背包如果正好装满,说明找到了总和为 sum / 2 的子集。
- 背包中每一个元素是不可重复放入。
将数组看作是一堆物体,每个物体的重量是数组的元素值,背包的最大重量是数组和的一半。我们的任务是从物体中选择一些,使得它们的重量总和恰好等于背包的最大重量。在这个问题中,我们只关心能否达到背包的最大重量,而不关心选择了哪些物体或者选择了多少物体。
- 时间复杂度:$O(n*m)$,其中 n 是数组的长度,m 是数组和的一半。
- 空间复杂度:$O(n*m)$,
function canPartition(nums: number[]): boolean {
const len = nums.length;
const bagweight = nums.reduce((pre, cur) => pre + cur) / 2;
if (!Number.isInteger(bagweight)) return false; // 不是偶数,说明一定无法分割
const dp: number[][] = Array.from({ length: len }, () => new Array(bagweight + 1).fill(0)); // 初始化为0
// 初始化第一个物体
for (let j = nums[0]; j <= bagweight; j++) {
dp[0][j] = nums[0];
}
for (let i = 1; i < nums.length; i++) {
for (let j = 1; j <= bagweight; j++) {
if (j <= nums[i]) dp[i][j] = dp[i - 1][j];
else dp[i][j] = Math.max(dp[i - 1][j], dp[i - 1][j - nums[i]] + nums[i]);
if (dp[i][j] === bagweight) {
return true;
};
}
}
return false;
};
动态规划-01背包-滚动数组
- dp定义:dp[j]表示容量为j的背包,所背的物品价值最大可以为dp[j];
- 递推公式:
dp[j]=max(dp[j], dp[j-weight[i]] + value[i])
; - 初始化:dp[0]=0,由于是正整数,所有下标初始化为0即可;
- 遍历顺序:一维数组只能先遍历物品,内层倒序遍历重量;
- 举例推导dp数组:
function canPartition(nums: number[]): boolean {
const bagweight = nums.reduce((pre, cur) => pre + cur) / 2;
if (!Number.isInteger(bagweight)) return false; // 不是偶数
const dp: number[] = new Array(bagweight + 1).fill(0); // 初始化
for (let i = 0; i < nums.length; i++) {
for (let j = bagweight; j >= nums[i]; j--) {
dp[j] = Math.max(dp[j], dp[j - nums[i]] + nums[i]);
if (dp[j] === bagweight) return true;
}
}
return false;
};
1049.最后一块石头的重量Ⅱ
有一堆石头,用整数数组
stones
表示。其中stones[i]
表示第i
块石头的重量。每一回合,从中选出任意两块石头,然后将它们一起粉碎。假设石头的重量分别为
x
和y
,且x <= y
。那么粉碎的可能结果如下:
- 如果
x == y
,那么两块石头都会被完全粉碎;- 如果
x != y
,那么重量为x
的石头将会完全粉碎,而重量为y
的石头新重量为y-x
。最后,最多只会剩下一块 石头。返回此石头 最小的可能重量 。如果没有石头剩下,就返回
0
。示例 1:
输入:stones = [2,7,4,1,8,1] 输出:1 解释: 组合 2 和 4,得到 2,所以数组转化为 [2,7,1,8,1], 组合 7 和 8,得到 1,所以数组转化为 [2,1,1,1], 组合 2 和 1,得到 1,所以数组转化为 [1,1,1], 组合 1 和 1,得到 0,所以数组转化为 [1],这就是最优值。
示例 2:
输入:stones = [31,26,33,21,40] 输出:5
提示:
1 <= stones.length <= 30
1 <= stones[i] <= 100
动态规划-01背包-滚动数组
思路:
问题转化为:把一堆石头分成两堆,求两堆石头重量差最小值。
进一步分析:要让差值小,两堆石头的重量都要接近sum/2;我们假设两堆分别为A、B,A < sum/2
,B > sum/2
,若A更接近sum/2,B也相应更接近sum/2。
进一步转化:将一堆stone放进最大容量为sum/2的背包,求放进去的石头的最大重量MaxWeight,最终答案即为sum-2*MaxWeight;
function lastStoneWeightII(stones: number[]): number {
const sum = stones.reduce((pre, cur) => pre + cur);
const bagweight = Math.floor(sum / 2);
const dp = new Array(bagweight + 1).fill(0);
for (let i = 0; i < stones.length; i++) {
for (let j = bagweight; j >= stones[i]; j--) {
dp[j] = Math.max(dp[j], dp[j - stones[i]] + stones[i])
}
}
return sum - 2 * dp[bagweight];
};
目标和
494.给你一个整数数组
nums
和一个整数target
。向数组中的每个整数前添加
'+'
或'-'
,然后串联起所有整数,可以构造一个 表达式 :
- 例如,
nums = [2, 1]
,可以在2
之前添加'+'
,在1
之前添加'-'
,然后串联起来得到表达式"+2-1"
。返回可以通过上述方法构造的、运算结果等于
target
的不同 表达式 的数目。示例 1:
输入:nums = [1,1,1,1,1], target = 3 输出:5 解释:一共有 5 种方法让最终目标和为 3 。 -1 + 1 + 1 + 1 + 1 = 3 +1 - 1 + 1 + 1 + 1 = 3 +1 + 1 - 1 + 1 + 1 = 3 +1 + 1 + 1 - 1 + 1 = 3 +1 + 1 + 1 + 1 - 1 = 3
示例 2:
输入:nums = [1], target = 1 输出:1
提示:
1 <= nums.length <= 20
0 <= nums[i] <= 1000
0 <= sum(nums[i]) <= 1000
-1000 <= target <= 1000
动态规划-二维数组-01背包
解题思路:
首先,题目可以转换为一个子集和问题。可以将问题理解为在nums中找到一个子集P,使得$sum(P)-sum(nums-P)=target$。也可以化简为$sum(P)= (target+sum(nums))/2$,也就是找一个和为$(target+sum(nums))/2$的子集。因此,可以转化为一个01背包问题。假设dp[i][j]
表示从数组的前i个数中选取一些使得和为j的方案数。那么有以下两种情况:
- 不选择
nums[i]
,那么从前i-1个数中选取一些和为j的方案数就是dp[i-1][j]
; - 选择
nums[i]
,那么从前i-1个数中选取一些和为j-nums[i]
的方案数就是dp[i-1][j-nums[i]]
。
因此可以得到状态转移方程:
dp[i][j] = dp[i-1][j] + dp[i-1][j-nums[i]] (j >= nums[i])
初始化:dp[0][0] = 1
,表示不选择任何元素的情况。对于其他的j>=1,dp[0][j]=0
,因为没有元素可选。
迭代:外层循环遍历所有的物品,内层循环遍历所有的重量。
下面给出一个demo表格:
假设nums = [1, 1, 1, 1, 1], target = 3,那么问题可以转化为找出nums的一个子集,它的和是4。
初始化dp数组:
0 | 1 | 2 | 3 | 4 | |
---|---|---|---|---|---|
0 | 1 | 0 | 0 | 0 | 0 |
1 | |||||
2 | |||||
3 | |||||
4 | |||||
5 |
然后进行状态转移:
0 | 1 | 2 | 3 | 4 | |
---|---|---|---|---|---|
0 | 1 | 0 | 0 | 0 | 0 |
1 | 1 | 1 | 0 | 0 | 0 |
2 | 1 | 2 | 1 | 0 | 0 |
3 | 1 | 3 | 3 | 1 | 0 |
4 | 1 | 4 | 6 | 4 | 1 |
5 | 1 | 5 | 10 | 10 | 5 |
最后答案是dp[5][4] = 5
,所以存在5种可能的方法可以使得nums的一个子集和为4。
function findTargetSumWays(nums: number[], target: number): number {
let sum = nums.reduce((pre, cur) => pre + cur);
if (Math.abs(target) > sum) return 0;
if ((target + sum) % 2 === 1) return 0;
let bagSize = Math.floor((target + sum) / 2);
const dp: number[][] = Array.from({length: nums.length + 1}, () => new Array(bagSize + 1).fill(0));
dp[0][0] = 1;
for (let i = 1; i <= nums.length; i++) {
for (let j = 0; j <= bagSize; j++) {
dp[i][j] = dp[i - 1][j];
if (j >= nums[i - 1]) {
dp[i][j] += dp[i - 1][j - nums[i - 1]];
}
}
}
return dp[nums.length][bagSize];
};
动态规划-滚动数组-01背包
- 时间复杂度:$O(n*m)$,n为整数个数,m为背包容量。
- 空间复杂度:$O(m)$,m为背包容量。
function findTargetSumWays(nums: number[], target: number): number {
let sum = nums.reduce((pre, cur) => pre + cur);
if (Math.abs(target) > sum) return 0;
if ((target + sum) % 2 === 1) return 0;
let bagSize = Math.floor((target + sum) / 2);
const dp: number[] = new Array(bagSize + 1).fill(0);
dp[0] = 1;
for (let i = 0; i < nums.length; i++) {
for (let j = bagSize; j >= nums[i]; j--) {
dp[j] += dp[j - nums[i]];
}
}
return dp[bagSize];
};
474.一和零
给你一个二进制字符串数组
strs
和两个整数m
和n
。请你找出并返回
strs
的最大子集的长度,该子集中 最多 有m
个0
和n
个1
。如果
x
的所有元素也是y
的元素,集合x
是集合y
的 子集 。示例 1:
输入:strs = ["10", "0001", "111001", "1", "0"], m = 5, n = 3 输出:4 解释:最多有 5 个 0 和 3 个 1 的最大子集是 {"10","0001","1","0"} ,因此答案是 4 。 其他满足题意但较小的子集包括 {"0001","1"} 和 {"10","1","0"} 。{"111001"} 不满足题意,因为它含 4 个 1 ,大于 n 的值 3 。
示例 2:
输入:strs = ["10", "0", "1"], m = 1, n = 1 输出:2 解释:最大的子集是 {"0", "1"} ,所以答案是 2 。
提示:
1 <= strs.length <= 600
1 <= strs[i].length <= 100
strs[i]
仅由'0'
和'1'
组成1 <= m, n <= 100
动态规划-01背包
思路:
这道题是一个二维背包问题,我们可以将此问题视为一个背包问题,每个字符串可以看作是一个物品,每个物品有两个属性:0的个数和1的个数。我们希望选择一些物品,使得0的总数不超过m,1的总数不超过n,且选取的物品数量最多。
这样我们可以定义一个三维的动态规划数组dp,其中dp[i][j][k]表示在前i个物品中选取一些物品,使得0的总数不超过j,1的总数不超过k,的最大物品数量。
状态转移方程:
- 如果不选第i个物品,那么
dp[i][j][k] = dp[i-1][j][k]
。 - 如果选第i个物品,那么
dp[i][j][k] = dp[i-1][j-zeros[i]][k-ones[i]] + 1
,其中zeros[i]
和ones[i]
分别表示第i个物品中0和1的个数。
因此,dp[i][j][k] = max(dp[i-1][j][k], dp[i-1][j-zeros[i]][k-ones[i]] + 1)
。
初始化:dp[0][j][k] = 0
,表示在前0个物品中选取一些物品,使得0的总数不超过j,1的总数不超过k,的最大物品数量为0。
迭代:外层循环遍历所有的物品,内层循环遍历所有的j和k。
假设输入是strs = ["10", "0001", "111001", "1", "0"], m = 5, n = 3,我们可以给出以下的动态规划表格:
j\k→0 | 1 | 2 | 3 | |
---|---|---|---|---|
0 | 0 | 0 | 0 | 0 |
1 | 0 | 1 | 1 | 1 |
2 | 1 | 1 | 1 | 1 |
3 | 1 | 2 | 3 | 4 |
4 | 2 | 3 | 4 | 4 |
5 | 2 | 3 | 4 | 4 |
这个表格表示的是dp[i][j][k]在i=5时的状态,也就是在前5个物品中选取一些物品,使得0的总数不超过j,1的总数不超过k,的最大物品数量。
最后的结果是dp[5][5][3]
= 4,所以最多可以选择4个字符串。
- 时间复杂度:$O(kmn)$,k为strs的长度。
- 空间复杂度:$O(mn)$。
function findMaxForm(strs: string[], m: number, n: number): number {
const dp: number[][] = Array.from({ length: m + 1 }, () => new Array(n + 1).fill(0));
for (const str of strs) {
let oneNum = 0, zeroNum = 0;
for (let c of str) {
if (c === '0') zeroNum++;
else oneNum++;
}
for (let i = m; i >= zeroNum; i--) {
for (let j = n; j >= oneNum; j--) {
dp[i][j] = Math.max(dp[i][j], dp[i - zeroNum][j - oneNum] + 1);
}
}
}
return dp[m][n];
};
518.零钱兑换Ⅱ
给你一个整数数组
coins
表示不同面额的硬币,另给一个整数amount
表示总金额。请你计算并返回可以凑成总金额的硬币组合数。如果任何硬币组合都无法凑出总金额,返回
0
。假设每一种面额的硬币有无限个。
题目数据保证结果符合 32 位带符号整数。
示例 1:
输入:amount = 5, coins = [1, 2, 5] 输出:4 解释:有四种方式可以凑成总金额: 5=5 5=2+2+1 5=2+1+1+1 5=1+1+1+1+1
示例 2:
输入:amount = 3, coins = [2] 输出:0 解释:只用面额 2 的硬币不能凑成总金额 3 。
示例 3:
输入:amount = 10, coins = [10] 输出:1
提示:
1 <= coins.length <= 300
1 <= coins[i] <= 5000
coins
中的所有值 互不相同0 <= amount <= 5000
动态规划-完全背包-滚动数组
解题思路:
定义 dp 数组的含义: 在这个问题中,我们定义 dp[i] 为凑成总金额 i 的组合数。我们需要求解的就是
dp[amount]
。确定状态转移方程: 对于总金额 i,我们需要考虑所有面额的硬币,假设当前考虑的硬币面额为 coin,如果
i>=coin
,那么我们可以选择使用这枚硬币,剩下的金额为i-coin
,所得的组合数为dp[i-coin]
。因为我们需要计算的是所有可能的组合数,所以我们需要将所有dp[i-coin]
相加。所以状态转移方程为:dp[i] += dp[i-coin] for each coin in coins if i>=coin
。确定初始化的值: 这里
dp[0] = 1
,表示凑成总金额 0 有一种方法,即不选择任何硬币。确定迭代的顺序: 我们需要先遍历硬币,再遍历金额,因为对于每种面额的硬币,我们需要考虑所有可能达到的总金额。
现在我们以 coins = [1, 2, 5] 和 amount = 5 为例,展示动态规划的过程。我们会得到一个长度为 6 的 dp 数组(从 0 到 5):
i | 0 | 1 | 2 | 3 | 4 | 5 |
---|---|---|---|---|---|---|
dp[i] | 1 | 1 | 2 | 2 | 3 | 4 |
- dp[0] = 1 是我们初始化的值
- dp[1] = dp[1] + dp[1-1] = 1 + 1 = 2
- dp[2] = dp[2] + dp[2-1] = 2 + 1 = 3
- dp[3] = dp[3] + dp[3-1] = 2 + 2 = 4
- dp[4] = dp[4] + dp[4-1] = 3 + 3 = 6
- dp[5] = dp[5] + dp[5-1] = 4 + 5 = 9
所以答案就是 dp[5] = 4。
如果求组合数就是外层for循环遍历物品,内层for遍历背包。
如果求排列数就是外层for遍历背包,内层for循环遍历物品。
- 时间复杂度:$O(n*m)$,其中m是amount,n是coins的长度。
- 空间复杂度:$O(m)$,因为我们需要一个长度为 n+1 的 dp 数组来保存所有的 dp 值。
function change(amount: number, coins: number[]): number {
const dp: number[] = new Array(amount + 1).fill(0);
dp[0] = 1;
for (let i = 0; i < coins.length; i++) {
for (let j = coins[i]; j <= amount; j++) {
dp[j] += dp[j - coins[i]];
}
}
return dp[amount];
};
377.组合总和Ⅳ
给你一个由 不同 整数组成的数组
nums
,和一个目标整数target
。请你从nums
中找出并返回总和为target
的元素组合的个数。题目数据保证答案符合 32 位整数范围。
示例 1:
输入:nums = [1,2,3], target = 4 输出:7 解释: 所有可能的组合为: (1, 1, 1, 1) (1, 1, 2) (1, 2, 1) (1, 3) (2, 1, 1) (2, 2) (3, 1) 请注意,顺序不同的序列被视作不同的组合。
示例 2:
输入:nums = [9], target = 3 输出:0
提示:
1 <= nums.length <= 200
1 <= nums[i] <= 1000
nums
中的所有元素 互不相同1 <= target <= 1000
回溯(超时)
function combinationSum4(nums: number[], target: number): number {
let res = 0;
let sum = 0;
const backtracking = () => {
if (sum === target) {
res++;
return;
}
for (let i = 0; i < nums.length; i++) {
if (sum + nums[i] > target) continue;
sum += nums[i];
backtracking();
sum -= nums[i];
}
}
backtracking();
return res;
};
动态规划-完全背包-滚动数组
解题思路:
定义 dp 数组的含义: 在这个问题中,我们定义 dp[i] 为和为 i 的序列的个数。所以我们需要求的就是 dp[target]。
确定状态转移方程: 对于 dp[i],我们需要考虑数组中所有的元素。假设当前考虑的元素为 num,如果 i>=num,那么对于每一个和为 i-num 的序列,在序列的最后加上 num 就能得到一个和为 i 的序列,所以 dp[i] 应该增加 dp[i-num]。所以我们的状态转移方程为:
dp[i] = sum(dp[i-num] for num in nums if i>=num)
确定初始化的值: 我们可以将 dp[0] 初始化为 1,表示和为 0 的序列有 1 种(就是没有任何元素)。其它的 dp[i] 应该初始化为 0。
确定迭代的顺序: 我们需要从小到大计算 dp[i],因为 dp[i] 的值依赖于 dp[i-num](num 是 nums 中的元素),所以需要先计算 dp[i-num]。
现在我们以 nums = [1,2,3] 和 target = 4 为例,展示动态规划的过程。我们会得到一个长度为 5 的 dp 数组(从 0 到 4):
i | 0 | 1 | 2 | 3 | 4 |
---|---|---|---|---|---|
dp[i] | 1 | 1 | 2 | 4 | 7 |
- dp[0] = 1 是我们初始化的值
- dp[1] = dp[1-1] = dp[0] = 1,因为我们可以选择 1 这个数字
- dp[2] = dp[2-1] + dp[2-2] = dp[1] + dp[0] = 2,因为我们可以选择数字 1 或 2
- dp[3] = dp[3-1] + dp[3-2] + dp[3-3] = dp[2] + dp[1] + dp[0] = 4,因为我们可以选择数字 1,2 或 3
- dp[4] = dp[4-1] + dp[4-2] + dp[4-3] = dp[3] + dp[2] + dp[1] = 7,因为我们可以选择数字 1,2 或 3
所以答案就是 dp[4] = 7。
如果求组合数就是外层for循环遍历物品,内层for遍历背包。
如果求排列数就是外层for遍历背包,内层for循环遍历物品。
- 时间复杂度: $O(target * n)$,其中 n 为 nums 的长度。
- 空间复杂度: $O(target)$。
function combinationSum4(nums: number[], target: number): number {
const dp: number[] = new Array(target + 1).fill(0);
dp[0] = 1;
for (let j = 0; j <= target; j++) {
for (let i = 0; i < nums.length; i++) {
if (j >= nums[i]) {
dp[j] += dp[j - nums[i]];
}
}
}
return dp[target];
};
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
提示:
1 <= coins.length <= 12
1 <= coins[i] <= 231 - 1
0 <= amount <= 104
动态规划-完全背包-滚动数组
解题思路:
定义 dp 数组的含义: 在这个问题中,我们定义 dp[i] 为凑成总金额 i 所需要的最少的硬币数量。我们需要求解的就是 dp[amount]。
确定状态转移方程: 对于总金额 i,我们需要考虑所有面额的硬币,假设当前考虑的硬币面额为 coin,如果 i>=coin,那么我们可以选择使用这枚硬币,剩下的金额为 i-coin,所需硬币数目为 dp[i-coin]+1。因为我们需要找到最少的硬币数量,所以我们应该在所有可选的 coin 中找到一个最小的 dp[i-coin]+1。所以状态转移方程为:dp[i] = min(dp[i-coin]+1 for coin in coins if i>=coin)。
确定初始化的值: 由于 dp[i] 代表的是最少的硬币数量,为了在状态转移时可以找到最小值,我们需要将 dp 数组初始化为一个大的数,例如 amount+1。这里 dp[0] = 0,表示凑成总金额 0 不需要任何硬币。
确定迭代的顺序: 我们需要从小到大计算 dp[i],因为 dp[i] 的值依赖于 dp[i-coin](coin 是 coins 中的元素),所以需要先计算 dp[i-coin]。
现在我们以 coins = [1, 2, 5] 和 amount = 11 为例,展示动态规划的过程。我们会得到一个长度为 12 的 dp 数组(从 0 到 11):
i | 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | 10 | 11 |
---|---|---|---|---|---|---|---|---|---|---|---|---|
dp[i] | 0 | 1 | 1 | 2 | 2 | 1 | 2 | 2 | 3 | 3 | 2 | 3 |
- dp[0] = 0 是我们初始化的值
- dp[1] = min(dp[1-1]+1, dp[1-2]+1, dp[1-5]+1) = min(dp[0]+1, +∞, +∞) = 1
- dp[2] = min(dp[2-1]+1, dp[2-2]+1, dp[2-5]+1) = min(dp[1]+1, dp[0]+1, +∞) = 1
- dp[3] = min(dp[3-1]+1, dp[3-2]+1, dp[3-5]+1) = min(dp[2]+1, dp[1]+1, +∞) = 2
- dp[4] = min(dp[4-1]+1, dp[4-2]+1, dp[4-5]+1) = min(dp[3]+1, dp[2]+1, +∞) = 2
- dp[5] = min(dp[5-1]+1, dp[5-2]+1, dp[5-5]+1) = min(dp[4]+1, dp[3]+1, dp[0]+1) = 1
- ……
- dp[11] = min(dp[11-1]+1, dp[11-2]+1, dp[11-5]+1) = min(dp[10]+1, dp[9]+1, dp[6]+1) = 3
所以答案就是 dp[11] = 3。
function coinChange(coins: number[], amount: number): number {
const dp = new Array(amount + 1).fill(Infinity);
dp[0] = 0;
for (let i = 0; i <= amount; i++) {
for (let j = 0; j < coins.length; j++) {
if (i >= coins[j]) {
dp[i] = Math.min(dp[i], dp[i - coins[j]] + 1);
}
}
}
return dp[amount] === Infinity ? -1 : dp[amount];
};
279.完全平方数
给你一个整数
n
,返回 和为n
的完全平方数的最少数量 。完全平方数 是一个整数,其值等于另一个整数的平方;换句话说,其值等于一个整数自乘的积。例如,
1
、4
、9
和16
都是完全平方数,而3
和11
不是。示例 1:
输入:n = 12 输出:3 解释:12 = 4 + 4 + 4
示例 2:
输入:n = 13 输出:2 解释:13 = 4 + 9
提示:
- $1 <= n <= 10^4$
动态规划-完全背包-滚动数组
解题思路:
定义 dp 数组的含义: 在这个问题中,我们定义 dp[i] 为组成总数 i 所需要的最少的完全平方数数量。我们需要求解的就是 dp[n]。
确定状态转移方程: 对于总数 i,我们需要考虑所有小于等于 i 的完全平方数(1, 4, 9, ...),假设当前考虑的完全平方数为
j*j
,那么我们可以选择使用这个完全平方数,剩下的数为i-j*j
,所需完全平方数的数量为dp[i-j*j]+1
。因为我们需要找到最少的完全平方数数量,所以我们应该在所有可选的j*j
中找到一个最小的 dp[i-j*j]+1。所以状态转移方程为:dp[i] = min(dp[i-j*j]+1 for all j such that j*j<=i)
。确定初始化的值: 由于 dp[i] 代表的是最少的完全平方数数量,为了在状态转移时可以找到最小值,我们需要将 dp 数组初始化为一个大的数,例如 n+1。这里 dp[0] = 0,表示组成总数 0 不需要任何完全平方数。
确定迭代的顺序: 我们需要从小到大计算 dp[i],因为 dp[i] 的值依赖于
dp[i-j*j]
(j*j
是小于等于 i 的完全平方数),所以需要先计算dp[i-j*j]
。
现在我们以 n = 13 为例,展示动态规划的过程。我们会得到一个长度为 14 的 dp 数组(从 0 到 13):
i | 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | 10 | 11 | 12 | 13 |
---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|
dp[i] | 0 | 1 | 2 | 3 | 1 | 2 | 3 | 4 | 2 | 1 | 2 | 3 | 3 | 2 |
- dp[0] = 0 是我们初始化的值
- dp[1] = min(dp[1-1*1]+1) = min(dp[0]+1) = 1
- dp[2] = min(dp[2-1*1]+1) = min(dp[1]+1) = 2
- dp[3] = min(dp[3-1*1]+1) = min(dp[2]+1) = 3
- dp[4] = min(dp[4-11]+1, dp[4-22]+1) = min(dp[3]+1, dp[0]+1) = 1
- ……
- dp[13] = min(dp[13-11]+1, dp[13-22]+1, dp[13-3*3]+1) = min(dp[12]+1, dp[9]+1, dp[4]+1) = 2
所以答案就是 dp[13] = 2。
- 时间复杂度:$O(nsqrt(n))$,因为对于每个 i,我们需要遍历所有小于等于 i 的完全平方数(最多 $sqrt(i)$ 个),所以总的时间复杂度是 $O(nsqrt(n))$。
- 空间复杂度:$O(n)$,因为我们需要一个长度为 $n+1$ 的 dp 数组来保存所有的 dp 值。
function numSquares(n: number): number {
const dp: number[] = new Array(n + 1).fill(Infinity);
dp[0] = 0;
for (let i = 0; i <= n; i++) {
for (let j = 1; j * j <= i; j++) {
dp[i] = Math.min(dp[i], dp[i - j * j] + 1);
}
}
return dp[n];
};
单词拆分
139.给你一个字符串
s
和一个字符串列表wordDict
作为字典。请你判断是否可以利用字典中出现的单词拼接出s
。**注意:**不要求字典中出现的单词全部都使用,并且字典中的单词可以重复使用。
示例 1:
输入: s = "leetcode", wordDict = ["leet", "code"] 输出: true 解释: 返回 true 因为 "leetcode" 可以由 "leet" 和 "code" 拼接成。
示例 2:
输入: s = "applepenapple", wordDict = ["apple", "pen"] 输出: true 解释: 返回 true 因为 "applepenapple" 可以由 "apple" "pen" "apple" 拼接成。 注意,你可以重复使用字典中的单词。
示例 3:
输入: s = "catsandog", wordDict = ["cats", "dog", "sand", "and", "cat"] 输出: false
提示:
1 <= s.length <= 300
1 <= wordDict.length <= 1000
1 <= wordDict[i].length <= 20
s
和wordDict[i]
仅有小写英文字母组成wordDict
中的所有字符串 互不相同
回溯(超时)
- 时间复杂度:$O(2^n)$,因为每一个单词都有两个状态,切割和不切割
- 空间复杂度:$O(n)$,算法递归系统调用栈的空间
function wordBreak(s: string, wordDict: string[]): boolean {
const set: Set<string> = new Set(wordDict);
function backtracking(startIndex) {
if (startIndex >= s.length) {
return true;
}
for (let i = startIndex; i < s.length; i++) {
const word = s.substring(startIndex, i + 1);
if (set.has(word) && startIndex < s.length && backtracking(i + 1)) {
return true;
}
}
return false
}
return backtracking(0);
};
动态规划-完全背包-滚动数组
解题思路:
定义 dp 数组的含义: 在这个问题中,我们定义 dp[i] 表示字符串 s 的前 i 个字符是否可以被空格拆分为一个或多个在字典中出现的单词。
确定状态转移方程: 对于字符串的前 i 个字符,如果存在 j(0 <= j < i),使得 dp[j] 为真,并且从第 j+1 个字符到第 i 个字符的子串在字典中,那么 dp[i] 就为真。所以,状态转移方程为 dp[i] = dp[j] && wordDict.contains(s.substring(j, i)),对所有的 0 <= j < i。
确定初始化的值: 为了保证边界条件的正确性,我们需要初始化 dp[0] = true,表示空字符串可以被拆分。
确定迭代的顺序: 我们需要从前往后计算 dp[i],因为 dp[i] 的值依赖于 dp[j](j < i)。本题是求排列,所以先遍历背包再遍历物品。
现在我们以 s = "leetcode",wordDict = ["leet", "code"] 为例,展示动态规划的过程。我们会得到一个长度为 9 的 dp 数组(从 0 到 8):
i | 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 |
---|---|---|---|---|---|---|---|---|---|
dp[i] | T | F | F | F | T | F | F | F | T |
- dp[0] = True 是我们初始化的值
- dp[4] = dp[0] && wordDict.contains("leet") = True && True = True
- dp[8] = dp[4] && wordDict.contains("code") = True && True = True
所以,答案是 dp[8] = True,表示字符串 "leetcode" 可以被拆分为 "leet" 和 "code"。
- 时间复杂度是:$O(n^2 * m)$,其中 n 是字符串 s 的长度,m 是 wordDict 中最长的单词的长度。这是因为对于每一个 i,我们需要遍历所有的 j(0 <= j < i),并且可能需要 O(m) 的时间来检查一个子串是否存在于 wordDict 中。
- 空间复杂度: $O(n)$,因为我们需要一个长度为 n+1 的 dp 数组来保存所有的 dp 值。
function wordBreak(s: string, wordDict: string[]): boolean {
const set: Set<string> = new Set(wordDict);
const dp: boolean[] = new Array(s.length + 1).fill(false);
dp[0] = true;
for (let i = 0; i <= s.length; i++) { // 遍历背包
for (let j = 0; j < i; j++) { // 遍历物品
if (dp[j] && set.has(s.slice(j, i))) {
dp[i] = true;
}
}
}
return dp[s.length];
};
198.打家劫舍
你是一个专业的小偷,计划偷窃沿街的房屋。每间房内都藏有一定的现金,影响你偷窃的唯一制约因素就是相邻的房屋装有相互连通的防盗系统,如果两间相邻的房屋在同一晚上被小偷闯入,系统会自动报警。
给定一个代表每个房屋存放金额的非负整数数组,计算你 不触动警报装置的情况下 ,一夜之内能够偷窃到的最高金额。
示例 1:
输入:[1,2,3,1] 输出:4 解释:偷窃 1 号房屋 (金额 = 1) ,然后偷窃 3 号房屋 (金额 = 3)。 偷窃到的最高金额 = 1 + 3 = 4 。
示例 2:
输入:[2,7,9,3,1] 输出:12 解释:偷窃 1 号房屋 (金额 = 2), 偷窃 3 号房屋 (金额 = 9),接着偷窃 5 号房屋 (金额 = 1)。 偷窃到的最高金额 = 2 + 9 + 1 = 12 。
提示:
1 <= nums.length <= 100
0 <= nums[i] <= 400
动态规划
解题思路:
定义 dp 数组的含义: 在这个问题中,我们定义 dp[i] 表示从第 0 个房子到第 i 个房子可以得到的最大金额。
确定状态转移方程: 对于第 i 个房子,我们可以选择偷或者不偷。如果我们选择偷,那么我们就不能偷第 i-1 个房子,所以可能得到的最大金额就是 dp[i-2] + nums[i];如果我们选择不偷,那么可能得到的最大金额就是 dp[i-1]。所以,状态转移方程为 dp[i] = max(dp[i-2] + nums[i], dp[i-1])。
确定初始化的值: 因为 dp[i] 依赖于 dp[i-2] 和 dp[i-1],所以我们需要初始化 dp[0] 和 dp[1]。dp[0] = nums[0],表示只有一个房子时可以得到的最大金额就是这个房子中的金额;dp[1] = max(nums[0], nums[1]),表示有两个房子时可以得到的最大金额就是这两个房子中金额较大的那个。
确定迭代的顺序: 我们需要从前往后计算 dp[i],因为 dp[i] 的值依赖于 dp[i-2] 和 dp[i-1]。
现在我们以 nums = [1, 2, 3, 1] 为例,展示动态规划的过程。我们会得到一个长度为 4 的 dp 数组:
i | 0 | 1 | 2 | 3 |
---|---|---|---|---|
dp[i] | 1 | 2 | 4 | 4 |
- dp[0] = nums[0] = 1 是我们初始化的值
- dp[1] = max(nums[0], nums[1]) = max(1, 2) = 2
- dp[2] = max(dp[0] + nums[2], dp[1]) = max(1 + 3, 2) = 4
- dp[3] = max(dp[1] + nums[3], dp[2]) = max(2 + 1, 4) = 4
所以,答案是 dp[3] = 4,表示在不触发报警装置的情况下,今晚能够盗取的最高金额为 4。
- 时间复杂度是 $O(n)$,其中 n 是数组 nums 的长度。因为我们只需要遍历一次数组就可以得到结果。
- 空间复杂度是 $O(n)$,因为我们需要一个长度为 n 的 dp 数组来保存所有的 dp 值。如果我们注意到每次更新 dp[i] 时,我们只使用了 dp[i-2] 和 dp[i-1],所以我们可以通过使用两个变量来代替 dp 数组,从而将空间复杂度降低到 $O(1)$。
// 写法一,一维数组
function rob(nums: number[]): number {
const dp: number[] = new Array(nums.length).fill(0);
dp[0] = nums[0];
dp[1] = Math.max(nums[0], nums[1]);
for (let i = 2; i < nums.length; i++) {
dp[i] = Math.max(dp[i - 2] + nums[i], dp[i - 1]);
}
return dp[nums.length - 1];
};
// 写法2,滚动数组
function rob(nums: number[]): number {
if (nums.length === 1) return nums[0];
let dp1 = nums[0], dp2 = Math.max(nums[0], nums[1]);
for (let i = 2; i < nums.length; i++) {
let temp = Math.max(dp1 + nums[i], dp2);
dp1 = dp2;
dp2 = temp;
}
return dp2;
};
213.打家劫舍Ⅱ
你是一个专业的小偷,计划偷窃沿街的房屋,每间房内都藏有一定的现金。这个地方所有的房屋都 围成一圈 ,这意味着第一个房屋和最后一个房屋是紧挨着的。同时,相邻的房屋装有相互连通的防盗系统,如果两间相邻的房屋在同一晚上被小偷闯入,系统会自动报警 。
给定一个代表每个房屋存放金额的非负整数数组,计算你 在不触动警报装置的情况下 ,今晚能够偷窃到的最高金额。
示例 1:
输入:nums = [2,3,2] 输出:3 解释:你不能先偷窃 1 号房屋(金额 = 2),然后偷窃 3 号房屋(金额 = 2), 因为他们是相邻的。
示例 2:
输入:nums = [1,2,3,1] 输出:4 解释:你可以先偷窃 1 号房屋(金额 = 1),然后偷窃 3 号房屋(金额 = 3)。 偷窃到的最高金额 = 1 + 3 = 4 。
示例 3:
输入:nums = [1,2,3] 输出:3
提示:
1 <= nums.length <= 100
0 <= nums[i] <= 1000
动态规划
解题思路:
定义 dp 数组的含义: dp[i] 表示从第0间到第i间房子可得到的最大金额。
状态转移方程: 对于第i间房子,我们可以选择偷或者不偷。如果我们选择偷,那么我们就不能偷第i-1间房子,所以可能得到的最大金额就是 dp[i-2] + nums[i];如果我们选择不偷,那么可能得到的最大金额就是 dp[i-1]。所以,状态转移方程为 dp[i] = max(dp[i-2] + nums[i], dp[i-1])。
初始化值: dp[0] = nums[0],dp[1] = max(nums[0], nums[1])。
迭代顺序: 从前往后。
对于数组 nums = [2, 3, 2],我们先考虑从第1家到第n-1家,再考虑从第2家到第n家:
- 第1家到第n-1家:nums = [2, 3], 得到 dp 数组为 [2, 3],最大金额为3。
- 第2家到第n家:nums = [3, 2], 得到 dp 数组为 [3, 2],最大金额为3。
所以,最终结果为3。
- 时间复杂度为$O(n)$,因为我们只需要遍历一次数组。
- 空间复杂度为$O(n)$,因为我们需要一个长度为n的dp数组。同样地,如果使用两个变量来替代dp数组,可以将空间复杂度降至$O(1)$。
// 写法一,一维数组
function rob(nums: number[]): number {
function robRange(start: number, end: number) {
if (start === end + 1) return nums[start];
const dp: number[] = new Array(nums.length).fill(0);
dp[start] = nums[start];
dp[start + 1] = Math.max(nums[start], nums[start + 1]);
for (let i = start + 2; i < end; i++) {
dp[i] = Math.max(dp[i - 1], dp[i - 2] + nums[i]);
}
return dp[end - 1];
}
if (nums.length === 1) return nums[0];
return Math.max(robRange(0, nums.length - 1), robRange(1, nums.length));
};
// 写法二,滚动数组
function rob(nums: number[]): number {
function robRange(start: number, end: number) {
if (start === end - 1) return nums[start];
let dp1 = nums[start], dp2 = Math.max(nums[start], nums[start + 1]);
for (let i = start + 2; i < end; i++) {
const temp = Math.max(dp2, dp1 + nums[i]);
dp1 = dp2;
dp2 = temp;
}
return dp2;
}
if (nums.length === 1) return nums[0];
return Math.max(robRange(0, nums.length - 1), robRange(1, nums.length));
};
337.打家劫舍Ⅲ
小偷又发现了一个新的可行窃的地区。这个地区只有一个入口,我们称之为
root
。除了
root
之外,每栋房子有且只有一个“父“房子与之相连。一番侦察之后,聪明的小偷意识到“这个地方的所有房屋的排列类似于一棵二叉树”。 如果 两个直接相连的房子在同一天晚上被打劫 ,房屋将自动报警。给定二叉树的
root
。返回 在不触动警报的情况下 ,小偷能够盗取的最高金额 。示例 1:
输入: root = [3,2,3,null,3,null,1] 输出: 7 解释: 小偷一晚能够盗取的最高金额 3 + 3 + 1 = 7
示例 2:
输入: root = [3,4,5,1,3,null,1] 输出: 9 解释: 小偷一晚能够盗取的最高金额 4 + 5 = 9
提示:
- 树的节点数在 $[1, 10^4]$ 范围内
- $0 <= Node.val <= 10^4$
动态规划+后序遍历
解题思路:
从底向上,在每个节点处都计算出偷这个节点能获得的最大收益以及不偷这个节点能获得的最大收益。
dp是一个长度为2的数组,下标0代表不偷的最大金钱,下标1代表偷的最大金钱
- 如果是偷当前节点,那么左右孩子就不能偷,val1 = cur->val + left[0] + right[0];
- 如果不偷当前节点,那么左右孩子就可以偷,至于到底偷不偷一定是选一个最大的,所以:val2 = max(left[0], left[1]) + max(right[0], right[1]);
- 最后当前节点的状态就是{val2, val1}; 即:{不偷当前节点得到的最大金钱,偷当前节点得到的最大金钱}
/**
* Definition for a binary tree node.
* class TreeNode {
* val: number
* left: TreeNode | null
* right: TreeNode | null
* constructor(val?: number, left?: TreeNode | null, right?: TreeNode | null) {
* this.val = (val===undefined ? 0 : val)
* this.left = (left===undefined ? null : left)
* this.right = (right===undefined ? null : right)
* }
* }
*/
function robTree(root: TreeNode | null): [number, number] {
if (root === null) return [0, 0];
const leftVal = robTree(root.left);
const rightVal = robTree(root.right);
// 偷当前节点
const val1 = root.val + leftVal[0] + rightVal[0];
// 不偷当前节点
const val2 = Math.max(leftVal[0], leftVal[1]) + Math.max(rightVal[0], rightVal[1]);
return [val2, val1];
}
function rob(root: TreeNode | null): number {
const rootVal = robTree(root);
return Math.max(rootVal[0], rootVal[1]);
};
121.买卖股票的最佳时机
给定一个数组
prices
,它的第i
个元素prices[i]
表示一支给定股票第i
天的价格。你只能选择 某一天 买入这只股票,并选择在 未来的某一个不同的日子 卖出该股票。设计一个算法来计算你所能获取的最大利润。
返回你可以从这笔交易中获取的最大利润。如果你不能获取任何利润,返回
0
。示例 1:
输入:[7,1,5,3,6,4] 输出:5 解释:在第 2 天(股票价格 = 1)的时候买入,在第 5 天(股票价格 = 6)的时候卖出,最大利润 = 6-1 = 5 。 注意利润不能是 7-1 = 6, 因为卖出价格需要大于买入价格;同时,你不能在买入前卖出股票。
示例 2:
输入:prices = [7,6,4,3,1] 输出:0 解释:在这种情况下, 没有交易完成, 所以最大利润为 0。
提示:
1 <= prices.length <= 105
0 <= prices[i] <= 104
贪心
- 时间复杂度:
O(n)
- 空间复杂度:
O(1)
function maxProfit(prices: number[]): number {
let min = Infinity;
let res = 0;
for (let i = 0; i < prices.length; i++) {
min = Math.min(min, prices[i]);
res = Math.max(res, prices[i] - min);
}
return res
};
动态规划
解题思路:
定义 dp 数组: 我们定义一个 dp 数组,其中
dp[i][0]
表示在第 i 天没有持有股票的最大利润,dp[i][1]
表示在第 i 天持有股票的最大利润。状态转移方程: 对于
dp[i][0]
,我们可以选择保持昨天的状态,或者是卖掉今天的股票,所以有dp[i][0] = max(dp[i-1][0], dp[i-1][1] + prices[i])
。对于dp[i][1]
,我们可以选择保持昨天的状态,或者是买入今天的股票(由于只能交易一次,所以购买的钱应该是0 - prices[i]
),所以有dp[i][1] = max(dp[i-1][1], 0 - prices[i])
。初始化值:
dp[0][0]
的值为 0,因为在第 0 天如果我们没有持有股票,那么我们的利润当然是 0。dp[0][1]
的值为-prices[0]
,因为在第 0 天如果我们购买了股票,那么我们的利润就是-prices[0]
。迭代顺序: 我们可以从 i=1 开始,一直迭代到最后一天。
i | dp[i][0] | dp[i][1] |
---|---|---|
0 | 0 | -prices[0] |
1 | max(0, prices[1]-prices[0]) | max(-prices[0], -prices[1]) |
2 | max(dp[1][0], dp[1][1] + prices[2])`` | max(dp[1][1], -prices[2]) |
... | ... | ... |
n | max(dp[n-1][0], dp[n-1][1] + prices[n]) | max(dp[n-1][1], -prices[n]) |
我们的目标是在最后一天手中没有股票的情况下获取最大的利润,所以最后的结果就是 dp[n-1][0]
。
- 时间复杂度:$O(n)$。我们需要遍历一遍价格数组,其中 n 是价格数组的长度。
- 空间复杂度:$O(n)$。我们需要一个二维数组来存储每一天的状态。如果使用滚动数组的技术,可以将空间复杂度降低到 $O(1)$。
function maxProfit(prices: number[]): number {
const dp: number[][] = Array.from({ length: prices.length }, () => new Array(2).fill(0));
dp[0][0] = 0;
dp[0][1] = -prices[0];
for (let i = 1; i < prices.length; i++) {
dp[i][0] = Math.max(dp[i - 1][0], dp[i - 1][1] + prices[i]);
dp[i][1] = Math.max(dp[i - 1][1], -prices[i]);
}
return dp[prices.length - 1][0];
};
122.买卖股票的最佳时机Ⅱ
给你一个整数数组
prices
,其中prices[i]
表示某支股票第i
天的价格。在每一天,你可以决定是否购买和/或出售股票。你在任何时候 最多 只能持有 一股 股票。你也可以先购买,然后在 同一天 出售。
返回 你能获得的 最大 利润 。
示例 1:
输入:prices = [7,1,5,3,6,4] 输出:7 解释:在第 2 天(股票价格 = 1)的时候买入,在第 3 天(股票价格 = 5)的时候卖出, 这笔交易所能获得利润 = 5 - 1 = 4 。 随后,在第 4 天(股票价格 = 3)的时候买入,在第 5 天(股票价格 = 6)的时候卖出, 这笔交易所能获得利润 = 6 - 3 = 3 。 总利润为 4 + 3 = 7 。
示例 2:
输入:prices = [1,2,3,4,5] 输出:4 解释:在第 1 天(股票价格 = 1)的时候买入,在第 5 天 (股票价格 = 5)的时候卖出, 这笔交易所能获得利润 = 5 - 1 = 4 。 总利润为 4 。
示例 3:
输入:prices = [7,6,4,3,1] 输出:0 解释:在这种情况下, 交易无法获得正利润,所以不参与交易可以获得最大利润,最大利润为 0 。
提示:
1 <= prices.length <= 3 * 104
0 <= prices[i] <= 104
动态规划
解题思路:
- 定义 dp 数组: 我们定义一个 dp 数组,其中 dp[i][0] 表示在第 i 天没有持有股票的最大利润,dp[i][1] 表示在第 i 天持有股票的最大利润。
- 状态转移方程: 对于
dp[i][0]
,我们可以选择保持昨天的状态,或者是卖掉今天的股票,所以有dp[i][0] = max(dp[i-1][0], dp[i-1][1] + prices[i])
。对于 dp[i][1],我们可以选择保持昨天的状态,或者是买入今天的股票,所以有dp[i][1] = max(dp[i-1][1], dp[i-1][0] - prices[i])
。 - 初始化值:
dp[0][0]
的值为 0,因为在第 0 天如果我们没有持有股票,那么我们的利润当然是 0。dp[0][1]
的值为-prices[0]
,因为在第 0 天如果我们购买了股票,那么我们的利润就是-prices[0]
。
- 时间复杂度:$O(n)$。我们需要遍历一遍价格数组,其中 n 是价格数组的长度。
- 空间复杂度:$O(n)$。我们需要一个二维数组来存储每一天的状态。如果使用滚动数组的技术,可以将空间复杂度降低到 $O(1)$。
function maxProfit(prices: number[]): number {
const dp: number[][] = Array.from({ length: prices.length }, () => new Array(2).fill(0));
dp[0][0] = 0;
dp[0][1] = -prices[0];
for (let i = 1; i < prices.length; i++) {
dp[i][0] = Math.max(dp[i-1][0], dp[i-1][1] + prices[i]);
dp[i][1] = Math.max(dp[i-1][1], dp[i-1][0] - prices[i]);
}
return dp[prices.length - 1][0];
};
123.买卖股票的最佳时机Ⅲ
给定一个数组,它的第
i
个元素是一支给定的股票在第i
天的价格。设计一个算法来计算你所能获取的最大利润。你最多可以完成 两笔 交易。
**注意:**你不能同时参与多笔交易(你必须在再次购买前出售掉之前的股票)。
示例 1:
输入:prices = [3,3,5,0,0,3,1,4] 输出:6 解释:在第 4 天(股票价格 = 0)的时候买入,在第 6 天(股票价格 = 3)的时候卖出,这笔交易所能获得利润 = 3-0 = 3 。 随后,在第 7 天(股票价格 = 1)的时候买入,在第 8 天 (股票价格 = 4)的时候卖出,这笔交易所能获得利润 = 4-1 = 3 。
示例 2:
输入:prices = [1,2,3,4,5] 输出:4 解释:在第 1 天(股票价格 = 1)的时候买入,在第 5 天 (股票价格 = 5)的时候卖出, 这笔交易所能获得利润 = 5-1 = 4 。 注意你不能在第 1 天和第 2 天接连购买股票,之后再将它们卖出。 因为这样属于同时参与了多笔交易,你必须在再次购买前出售掉之前的股票。
示例 3:
输入:prices = [7,6,4,3,1] 输出:0 解释:在这个情况下, 没有交易完成, 所以最大利润为 0。
示例 4:
输入:prices = [1] 输出:0
提示:
1 <= prices.length <= 105
0 <= prices[i] <= 105
动态规划
定义dp
一天一共有四个状态:
- 没有操作(可以去掉)
- 第一次持有股票
- 第一次不持有股票
- 第二次持有股票
- 第二次不持有股票
dp[i][j]
表示第i天,j为[0-4]五个状态,dp[i][j]
表示第i天状态j所剩最大现金。递归公式
dp[i][1]
状态有两种方式:- 第i天第一次买入股票:
dp[i][1] = -prices[i]
- 第i天没有操作:
dp[i][1] = dp[i-1][1]
dp[i][2]
状态也有两种方式:- 第i天第一次卖出股票,那么
dp[i][2] = dp[i-1][1] + prices[i]
- 第i天没有操作,
dp[i][2] = dp[i-1][2]
dp[i][3]
状态:- 第i天第二次买入股票:
dp[i][3] = dp[i-1][2] - prices[i]
- 第i天没有操作:
dp[i][3] = dp[i-1][3]
dp[i][4]
状态:- 第i天第二次卖出股票:
dp[i][4] = dp[i-3] + prices[i]
- 第i天没有操作:
dp[i][4] = dp[i-1][4]
- 第i天第一次买入股票:
初始化
dp[0][0] = 0
dp[0][1] = -prices[0]
dp[0][2] = 0
dp[0][3] = -prices[0]
dp[0][4] = 0
遍历顺序
因为
dp[i]
依赖dp[i-1]
,所有从左往右遍历推导举例
- 时间复杂度:$O(n)$
- 空间复杂度:$O(n*5)$
function maxProfit(prices: number[]): number {
const dp: number[][] = Array.from({ length: prices.length }, () => new Array(5).fill(0));
dp[0][1] = -prices[0];
dp[0][3] = -prices[0];
for (let i = 1; i < prices.length; i++) {
dp[i][1] = Math.max(dp[i - 1][1], -prices[i]);
dp[i][2] = Math.max(dp[i - 1][2], dp[i - 1][1] + prices[i]);
dp[i][3] = Math.max(dp[i - 1][3], dp[i - 1][2] - prices[i]);
dp[i][4] = Math.max(dp[i - 1][4], dp[i - 1][3] + prices[i]);
}
return dp[prices.length - 1][4];
};
买卖股票的最佳时机Ⅳ
188.给定一个整数数组
prices
,它的第i
个元素prices[i]
是一支给定的股票在第i
天的价格,和一个整型k
。设计一个算法来计算你所能获取的最大利润。你最多可以完成
k
笔交易。也就是说,你最多可以买k
次,卖k
次。**注意:**你不能同时参与多笔交易(你必须在再次购买前出售掉之前的股票)。
示例 1:
输入:k = 2, prices = [2,4,1] 输出:2 解释:在第 1 天 (股票价格 = 2) 的时候买入,在第 2 天 (股票价格 = 4) 的时候卖出,这笔交易所能获得利润 = 4-2 = 2 。
示例 2:
输入:k = 2, prices = [3,2,6,5,0,3] 输出:7 解释:在第 2 天 (股票价格 = 2) 的时候买入,在第 3 天 (股票价格 = 6) 的时候卖出, 这笔交易所能获得利润 = 6-2 = 4 。 随后,在第 5 天 (股票价格 = 0) 的时候买入,在第 6 天 (股票价格 = 3) 的时候卖出, 这笔交易所能获得利润 = 3-0 = 3 。
提示:
0 <= k <= 100
0 <= prices.length <= 1000
0 <= prices[i] <= 1000
动态规划
定义dp
使用二维数组 dp[i][j] :第i天的状态为j,所剩下的最大现金是dp[i][j]
j的状态表示为:
- 0 表示不操作
- 1 第一次买入
- 2 第一次卖出
- 3 第二次买入
- 4 第二次卖出
- .....
递推公式
达到dp[i][1]状态,有两个具体操作:
- 操作一:第i天买入股票了,那么
dp[i][1] = dp[i - 1][0] - prices[i]
- 操作二:第i天没有操作,而是沿用前一天买入的状态,即:
dp[i][1] = dp[i - 1][1]
选最大的,所以
dp[i][1] = max(dp[i - 1][0] - prices[i], dp[i - 1][1])
;同理
dp[i][2]
也有两个操作:- 操作一:第i天卖出股票了,那么
dp[i][2] = dp[i - 1][1] + prices[i]
- 操作二:第i天没有操作,沿用前一天卖出股票的状态,即:
dp[i][2] = dp[i - 1][2]
所以
dp[i][2] = max(dp[i - 1][1] + prices[i], dp[i - 1][2])
- 操作一:第i天买入股票了,那么
初始化
第0天没有操作,这个最容易想到,就是0,即:
dp[0][0] = 0
;第0天做第一次买入的操作,
dp[0][1] = -prices[0]
;同理可以推出
dp[0][j]
当j为奇数的时候都初始化为-prices[0]
遍历顺序
从递归公式其实已经可以看出,一定是从前向后遍历,因为dp[i]
,依靠dp[i - 1]
的数值。
举例推导
function maxProfit(k: number, prices: number[]): number {
const dp: number[][] = Array.from({ length: prices.length }, () => new Array(k * 2 + 1).fill(0));
for (let j = 1; j <= 2 * k; j += 2) {
dp[0][j] = -prices[0]
}
for (let i = 1; i < prices.length; i++) {
for (let j = 0; j < 2 * k - 1; j += 2) {
dp[i][j + 1] = Math.max(dp[i - 1][j + 1], dp[i - 1][j] - prices[i]);
dp[i][j + 2] = Math.max(dp[i - 1][j + 2], dp[i - 1][j + 1] + prices[i]);
}
}
return dp[prices.length - 1][2 * k]
};
图论
待补充