典型算法题汇总
本文题单来自LABULADONG 的算法网站
链表
合并两个有序链表
类似拉拉链,维护一个指针,与当前链表的头指针不断比较
var mergeTwoLists = function (list1, list2) {
//虚拟链表头
const dummy = { next: null };
let p = dummy;
while (list1 && list2) {
if (list1.val > list2.val) {
p.next = list2;
list2 = list2.next;
} else {
p.next = list1;
list1 = list1.next;
}
p = p.next;
}
// 多余列表,默认增序的,直接接上
if (list1) {
p.next = list1;
}
if (list2) {
p.next = list2;
}
return dummy.next;
};
合并 k 个有序链表
用最小堆优先队列,js 没有这种东西,得自己写一个(java 自带了一个,羡慕 😂)
二叉最大/小堆优先队列,通过数组的下标来与二叉树节点建立来联系 设队列为
queue=[]
,二叉树根节点从下标1
开始(从0
的话相乘就还是0
了),左子树对应下标 则为1*2=2
,右子树1*2+1=3
,左子树的左子树1*2*2=4
…以此类推,对于每一个节点,设其下标 为i
,则可知道它的父节点下为Math.floor(i/2)
,左子点下标i*2
,右子节点i*2+1
var mergeKLists = function (lists) {
// 过滤空链表,测试用例十分操蛋
lists = lists.filter((l) => !!l);
if (!lists.length) return null;
// Class实现二叉最小堆优先队列
class MinPQ {
constructor(array = []) {
this.array = [undefined, ...array];
}
// 上浮操作
swim(idx) {
while (
idx > 1 &&
this.array[this.parent(idx)].val > this.array[idx].val
) {
this.exch(this.parent(idx), idx);
idx = this.parent(idx);
}
}
// 下沉
sink(idx) {
const size = this.array.length;
while (this.left(idx) < size) {
// 先假设左边节点较小
let less = this.left(idx);
// 如果右边节点存在,比一下大小
if (
this.right(idx) < size &&
this.array[this.right(idx)].val < this.array[this.left(idx)].val
)
less = this.right(idx);
// 结点 idx 比俩孩子都小,就不必下沉了
if (this.array[idx].val <= this.array[less].val) break;
// 否则,不符合最小堆的结构,下沉 idx 结点
this.exch(idx, less);
idx = less;
}
}
// pop出最小值,同时更新队列
popMin() {
if (this.array.length === 2) {
return this.array.pop();
}
const min = this.array[1];
this.array[1] = this.array.pop();
this.sink(1);
return min;
}
// 插入节点
insert(node) {
this.array.push(node);
this.swim(this.array.length - 1);
}
// 交换节点
exch(idx1, idx2) {
const idx2Val = this.array[idx2];
this.array[idx2] = this.array[idx1];
this.array[idx1] = idx2Val;
}
// 下标查询
parent(idx) {
return Math.floor(idx / 2);
}
left(idx) {
return idx * 2;
}
right(idx) {
return idx * 2 + 1;
}
}
// 各列表头节点入队
const pq = new MinPQ(lists.sort((a, b) => a.val - b.val));
const dummy = { next: null };
let p = dummy;
// 依次从优先队列取出最小的,放到结果链表里
while (pq.array.length > 1) {
const min = pq.popMin();
p.next = min;
p = p.next;
// 如果取出的节点还有后续,则入队
if (min?.next) {
pq.insert(min.next);
}
}
return dummy.next;
};
删除链表的倒数第 N 个结点
快慢指针,快的比慢的先走 N 步
var removeNthFromEnd = function (head, n) {
const dummy = { next: head };
let point = dummy;
let lastNPoint = dummy;
while (n >= 0) {
n--;
point = point.next;
}
while (point) {
lastNPoint = lastNPoint.next;
point = point.next;
}
lastNPoint.next = lastNPoint.next.next;
return dummy.next;
};
链表的中间节点
快慢指针,快的每走两步,慢的走一步,快指针到终点时,满指针刚好在中点
var middleNode = function (head) {
let fast = head;
let slow = head;
while (fast && fast.next) {
fast = fast.next.next;
slow = slow.next;
}
return slow;
};
判断链表是否有环
快慢指针(快两倍),当快指针没有下一个节点时,没有环,两指针相遇时,有环
var hasCycle = function (head) {
let fast = head;
let slow = head;
while (fast && fast.next) {
fast = fast.next.next;
slow = slow.next;
if (slow === fast) {
return true;
}
}
return false;
};
判断环形列表的起点
快慢指针,两指针相遇时将任一指针放回起点,然后已相同速度前进,再次相遇的节点则为环起点
var detectCycle = function (head) {
if (!head?.next) return null;
let slow = head;
let fast = head;
while (fast && fast.next) {
fast = fast.next.next;
slow = slow.next;
if (fast === slow) {
break;
}
}
if (!fast?.next) return null;
fast = head;
while (fast !== slow) {
fast = fast.next;
slow = slow.next;
}
return fast;
};
两个链表是否相交
双指针遍历两个链表(同速度),假设两个链表相交长度为 z,不相交的长度为 x 和 y,两个指针同时走,
如果两个指针都在走完自己的 时候走另一条,那么两指针必定在相交点相遇,应为此时两指针走的距离相等x+z+y=y+z+x
var getIntersectionNode = function (headA, headB) {
let pA = headA;
let pB = headB;
while (pA !== pB) {
if (pA === null) {
pA = headB;
} else {
pA = pA.next;
}
if (pB === null) {
pB = headA;
} else {
pB = pB.next;
}
}
return pA;
};
反转单链表
普通做法,做一个新链表,不断的包上父节点
var reverseList = function (head) {
let res = null;
let p = head;
while (p) {
res = {
val: p.val,
next: res,
};
p = p.next;
}
return res;
};
递归实现,dp 问题返回的是反转后的头节点,在父问题中这个头节点则需要作为最后一个节点
var reverseList = function (head) {
if (!head?.next) {
return head;
}
const last = reverseList(head.next);
head.next.next = head;
head.next = null;
return last;
};
反转列表的一部分
将链表先砍成三段,反转中间那段,再重新拼接
var reverseBetween = function (head, left, right) {
//反转整条
const reverse = (head) => {
if (!head?.next) {
return head;
}
const last = reverse(head.next);
head.next.next = head;
head.next = null;
return last;
};
// 截取之前的
let prepend = { next: head };
while (left > 1) {
prepend = prepend.next;
left--;
right--;
}
// 截取需要反转的那段
let needReverse = prepend.next;
let p = needReverse;
while (right > 1) {
p = p.next;
right--;
}
let append = p.next;
// 临时砍掉
p.next = null;
// 反转
const reversedHead = reverse(needReverse);
// 拼接
prepend.next.next = append;
prepend.next = reversedHead;
return prepend.val ? head : prepend.next;
};
K 个一组反转链表
更上面类似,分段反转,注意拼接问题
判断回文链表
类似二叉树后续遍历,对链表进行遍历,前后续分别维护一个指针,达到两端对比的效果
var isPalindrome = function (head) {
// 倒序对比
let left = head;
let right;
let res = true;
const deep = (node) => {
// 前序遍历,从有段开始
if (!node.next) {
right = node;
return;
}
deep(node.next);
// 后续遍历,从左端开始
res = res && left.val === right.val;
left = left.next;
right = node;
};
deep(head);
return res;
};
也可以东通过快慢指针找到中间节点,然后反转后半段链表,再依次进行比较
// TODO
数组
删除有序数组中的重复项
注意题目中是需要原地操作数组的,使用快慢指针即可,慢指针维护不重复项,快指针正常遍历
var removeDuplicates = function (nums) {
let slow = 0;
let fast = 1;
const length = nums.length;
while (fast < length) {
// 当快指针与慢指针不同时,慢指针挪一步,将快指针的值赋给它
if (nums[slow] !== nums[fast]) {
slow++;
nums[slow] = nums[fast];
}
fast++;
}
nums.length = slow + 1;
};
删除排序链表中的重复元素
和上面这个一样的道理,编程了操作节点而已
var deleteDuplicates = function (head) {
if (!head || !head.next) return head;
let slow = head;
let fast = head.next;
while (fast) {
if (fast.val !== slow.val) {
slow.next = fast;
slow = slow.next;
}
fast = fast.next;
}
slow.next = null;
return head;
};
移除元素
也是需要原地操作数组,使用快慢指针,慢指针维护当前不需要删除的元素,快指针正常遍历, 遇到不需要删除的,将值赋给慢指针,随后慢指针挪一步,遇到需要删除的则跳过
var removeElement = function (nums, val) {
let slow = 0;
let fast = 0;
while (fast < nums.length) {
if (nums[fast] !== val) {
nums[slow] = nums[fast];
slow++;
}
fast++;
}
return slow;
};
移动零
需要原地操作,使用快慢指针,慢指针维护非零值,快指针正常遍历,遇到了非零的值则与慢指针交换,然后慢指针挪一步
var moveZeroes = function (nums) {
let slow = 0;
let fast = 0;
const length = nums.length;
while (fast < length) {
if (nums[fast] !== 0) {
const slowVal = nums[slow];
nums[slow] = nums[fast];
nums[fast] = slowVal;
slow++;
}
fast++;
}
};
两数之和 II
因为数组是递增的,可以使用左右指针不断调整
var twoSum = function (numbers, target) {
let left = 0;
let right = numbers.length - 1;
while (left < right) {
if (numbers[left] + numbers[right] === target) {
return [left + 1, right + 1];
} else if (numbers[left] + numbers[right] > target) {
right--;
} else {
left++;
}
}
};
反转字符串
左右指针向中间靠拢,交换两端值
var reverseString = function (s) {
let left = 0;
let right = s.length - 1;
while (left < right) {
const rightV = s[right];
s[right] = s[left];
s[left] = rightV;
left++;
right--;
}
return s;
};
最长回文子串
通过从中心向两端扩散的双指针判断是否回文,需要注意的是回文字串的中心可能是一个字符,也可能是两个字符
var longestPalindrome = function (s) {
// 找以某一点为中心的最长回文字串
const findPalidrom = (s, l, r) => {
while (l >= 0 && r < s.length && s[l] === s[r]) {
l--;
r++;
}
return s.slice(l + 1, r);
};
let res = "";
for (let i = 0; i < s.length; i++) {
const s1 = findPalidrom(s, i, i);
const s2 = findPalidrom(s, i, i + 1);
if (s1.length > res.length) res = s1;
if (s2.length > res.length) res = s2;
}
return res;
};
区域和检索 - 数组不可变
使用前缀和绩效,维护每个点的前缀和,区间的和只需要求起点和终点的前缀和差值即可
var NumArray = function (nums) {
const sums = [0];
for (const i of nums) {
const last = sums.slice(-1)[0];
sums.push(last + i);
}
this.sums = sums;
};
NumArray.prototype.sumRange = function (left, right) {
return this.sums[right + 1] - this.sums[left];
};
二维区域和检索 - 矩阵不可变
也是使用前缀和技巧,不同的是,矩阵中的区域差值计算
var NumMatrix = function (matrix) {
const colNum = matrix[0].length;
const rowNum = matrix.length;
if (rowNum === 0 || colNum === 0) return;
const preSum = [new Array(colNum + 1).fill(0)];
for (let i = 1; i <= rowNum; i++) {
if (!preSum[i]) preSum[i] = [0];
for (let j = 1; j <= colNum; j++) {
// 计算每个矩阵 [0, 0, i, j] 的元素和
preSum[i][j] =
preSum[i - 1][j] +
preSum[i][j - 1] +
matrix[i - 1][j - 1] -
preSum[i - 1][j - 1];
}
}
this.sums = preSum;
};
// 相当于计算面积
// ┍ ┬ ┐
// │a│b│
// ┝ ┾ ┤
// │c│d│
// ┕ ┶ ┘
// 由r1*c1=a,r1*c2=a+b,r2*c1=a+c,r2*c2=a+b+c+d
// 得d=r2c2-r1c2-r2c1+r1c1
NumMatrix.prototype.sumRegion = function (r1, c1, r2, c2) {
return (
this.sums[r2 + 1][c2 + 1] -
this.sums[r1][c2 + 1] -
this.sums[r2 + 1][c1] +
this.sums[r1][c1]
);
};
二叉树
动态规划
动态规划基本条件:符合最优子结构,问题相互独立 基本步骤:确定base case->确定状态->确定选择->明确dp函数/数组的定义 状态指的是原问题和子问题会变化的量,选择指的是能使状态发生变化的行为
斐波那契数
正常的递归会有很多字问题重复求解,可以用备忘录优化,但最优解法使用 dp 状态转移
var fib = function (n) {
if (n < 2) return n;
// 维护两个状态就够了,不需要用状态数组,节省空间
let dp_1 = 0,
dp_2 = 1;
for (let i = 2; i <= n; i++) {
const newDp = dp_1 + dp_2;
dp_1 = dp_2;
dp_2 = newDp;
}
return dp_2;
};
零钱兑换
var coinChange = function(coins, amount) {
// 备忘录,cache[amount]记录该金额下的最少零钱数
const cache = []
}