# 算法解题模板
# 回溯算法解题模板
# 回溯算法模板
注意：递归操作传入的路径数组一定要做一层浅拷贝，不然结果不一致
result = []
function backtrack(路径，选择列表) {
if 满足结束条件：
result.push(路径)
return
for 选择 in 选择列表：
做选择
backtrack(路径，选择列表)
撤销选择
}
1、路径：也就是已经做出的选择。
2、选择列表：也就是你当前可以做的选择。
3、结束条件：也就是到达决策树底层，无法再做选择的条件。
简单讲就是定义一个回溯方法
第一步确定结束条件，也就是到达决策树底部
第二部就是去遍历选择列表，三部曲：做选择(track.push(num))+递归回溯+撤销选择(track.pop())
# 快速理解回溯算法
计算[1,2,3]的全排列二维数组结果
解题步骤:
- 画出决策树
- 总结出以下规律:
- 每次做出决策之后，路径数组都会添加已经选择的节点，选择列表删除已选择节点
- 遍历过程中，路径中绝对不会包含下一选择节点，有则跳过此轮循环
- 当路径元素和选择列表元素相同，结束循环，返回结果
for 选择 in 选择列表：
# 做选择
将该选择从选择列表移除
路径.push(选择)
backtrack(路径，选择列表)
# 撤销操作
路径.pop(选择)
将该选择再加入选择列表
所以以上解法
var permute = function(nums) {
let res = [];
function backTrack(track) {
if (track.length === nums.length) {
res.push(track);
return;
}
for (let num of nums) {
// 下一选择节点不能再路径中
if (track.includes(num)) {
continue;
}
// 做选择
track.push(num);
// 递归
backTrack(track.slice());
// 撤销选择
track.pop();
}
}
backTrack([]);
return res;
};
# 解决全排列，N 皇后问题
全排列前文已经讲解
题目大概描述:
给定一个 NxN 的棋盘，如何将 n 个皇后放置在 n×n 的棋盘上，并且使皇后彼此之间不能相互攻击(皇后的左上方，右上方，本列都不允许出现另一个皇后)
解题思路:
这道题也是经典的回溯算法(有去的路也有死路)，决策树上的每一层代表棋盘的行，这一行的所有列代表选择列表
还是老样子首先第一步还是先写出选择列表，路径和结束条件
1. 选择列表: 每一层row的任意行，都可以放置皇后
2. 路径: 这里的路径和全排列的路径不同，这里比较抽象，将它想象成row在遍历着，皇后也在放置着，最后的棋盘长啥样，路径就是啥
3. 结束条件: row = 棋盘的N
套公式即可
var solveNQueens = function(n) {
const res = [];
// 路径参数为棋盘和row
function backStack(board, row) {
// 结束递归
if (row === n) {
res.push(board);
return;
}
// 遍历选择列表
for (var col = 0; col < n; i++) {
// 1. 排除不合法的棋子
if (!isValid(board, row, col)) {
continue;
}
var letter = board[row].split("");
// 做选择
letter[col] = "Q";
board[row] = letter.join("");
// 递归
backStack(board.slice(), row + 1);
//撤销
letter[col] = ".";
board[row] = letter.join("");
}
}
// 题意：左上方，右上方，本列不允许出现皇后
function isVaild(board, row, col) {
// 本列
for (let i = 0; i < n; i++) {
if (board[i][col] === "Q") {
return false;
}
}
// 左上方
for (let i = row - 1, j = col - 1; i >= 0 && j >= 0; i--, j--) {
if (board[i][j] === "Q") {
return false;
}
}
// 右上方
for (let i = row - 1, j = col + 1; i >= 0 && j < n; i--, j++) {
if (board[i][j] === "Q") {
return false;
}
}
return true;
}
/* 初始化棋盘 ，Array(4).fill(".".repeat(4))其实就是 声明长度为4的数组然后 填满4个点的字符串的元素
* ===>["....","....","....","...."]
*/
backStack(Array(4).fill(".".repeat(4)), 0);
return res;
};
总结：
凡是遇到有可寻的路径也有死路的问题都可以往回溯算法想，遇到题目先把三要素(选择列表，路径，结束条件)写出来，然后套用模板解题
# BFS 解题模板
BFS 是用来求最短路径的，但代价就是空间复杂度比 DFS 大很多
常见使用 BFS 场景
解题模板
// 计算从起点 start 到终点 target 的最近距离
int BFS(Node start, Node target) {
Queue<Node> q; // 核心数据结构
Set<Node> visited; // 避免走回头路
q.offer(start); // 将起点加入队列
visited.add(start);
int step = 0; // 记录扩散的步数
while (q not empty) {
int sz = q.size();
/* 将当前队列中的所有节点向四周扩散 */
for (int i = 0; i < sz; i++) {
Node cur = q.poll();
/* 划重点：这里判断是否到达终点 */
if (cur is target)
return step;
/* 将 cur 的相邻节点加入队列 */
for (Node x : cur.adj())
if (x not in visited) {
q.offer(x);
visited.add(x);
}
}
/* 划重点：更新步数在这里 */
step++;
}
}
可转换为 JS 版本
bfs = (root, target) => {
let q = [[root, 1]]; //初始化队列
while (q.length) {
let [n, level] = q.shift();
if (n === target) {
return level;
}
if (n.left) {
q.push([n.left, level + 1]);
}
if (n.right) {
q.push([n.right, level + 1]);
}
}
};
# 二分查找解题模板
在排序数组中查找元素的第一个和最后一个位置 (opens new window)
# 常规
首先常规的二分查找不用多说直接上
function binarySearch(arr, item) {
let low = 0;
let high = arr.length - 1;
while (low <= high) {
let mid = Math.floor((low + high) / 2);
let Element = arr[mid];
if (Element === item) {
return mid;
} else if (Element > item) {
high = mid - 1;
} else if (Element < item) {
low = mid + 1;
}
}
return -1;
}
# 数组边界问题
但是这个常规的二分查找无法处理一下情形
输入 [1,2,3,3,4] ,3
这个时候我们在搜索的如果中间位元素等于搜索元素就不能直接返回，要分两种情况了。 一句话就是，寻找数组左侧第一位，就要缩小右侧边界范围，寻找右侧第一位，就要缩小左侧边界范围,然后检查数组越界也需要格外注意
左侧边界查找：[left,right), 当nums[mid] == target时不要立即返回而要收紧右侧边界(high = mid -1)以锁定左侧边界
function leftBoundSearch(arr, item) {
let low = 0;
let high = arr.length - 1;
while (low <= high) {
// 切记 取值一定要定义在里面，不然会报错
let mid = Math.floor((low + high) / 2);
let Element = arr[mid];
if (Element === item) {
high = mid - 1;
} else if (Element > item) {
high = mid - 1;
} else if (Element < item) {
low = mid + 1;
}
}
// 检查数组越界
if (low >= arr.length || arr[left] !== item) {
return -1;
}
return left;
}
右侧边界查找：(left,right],当nums[mid] == target时不要立即返回而要收紧左侧边界(low = mid +1)以锁定右侧边界
function rightBoundSearch(arr, item) {
let low = 0;
let high = arr.length - 1;
while (low <= high) {
let mid = Math.floor((low + high) / 2);
let Element = arr[mid];
if (Element === item) {
low = mid + 1;
} else if (Element > item) {
high = mid - 1;
} else if (Element < item) {
low = mid + 1;
}
}
// 检查数组越界
if (high < 0 || arr[right] !== item) {
return -1;
}
return right;
}
# 双指针解题模板
需要注意的是链表里面的值计算有一定的技巧，比如设置 head 变量，它代表整个链表。
双指针技巧再分为两类，一类是「快慢指针」，一类是「左右指针」。前者解决主要解决链表中的问题，比如典型的判定链表中是否包含环；后者主要解决数组（或者字符串）中的问题，比如二分查找。
# 快慢指针
快慢指针一般会这样初始化
let fast = head;
let slow = head;
快满指针都初始化为 head 头结点，解决链表问题,如果没有成环则代表 fast === null,保证快慢指针能走下去的条件是 fast && fast.next
一般分为以下几种情况:
# 判定链表中是否含有环
一快一慢指针遍历，相遇即成环
var cicleList = head => {
let fast = head;
let slow = head;
while (fast && fast.next) {
fast = fast.next.next;
slow = slow.next;
if (fast === slow) {
return true;
}
}
return false;
};
# 已知链表中含有环，返回这个环的起始位置
快慢指针先跑一圈，成环之后，再让快慢指针匀速跑，相遇点就是成环的第一个入环点,记得考虑第一次未成环情况和匀速跑之前重新将一个指针指向 head
理由：fast 指针走 2k 步，slow 指针走 k 步。指针从相遇点到入环点和第一次成环相遇点到入环点的距离相同
var detectCycle = function(head) {
// 首先快指针和满指针先成环，跑一圈
let fast = head;
let slow = head;
while (fast && fast.next) {
fast = fast.next.next;
slow = slow.next;
if (fast === slow) {
break;
}
}
// 如果没有成环
if (!fast || !fast.next) {
return null;
}
// 然后再匀速跑,再次相遇就是第一个入环的节点
// 这里一定要将slow重新指向head
slow = head;
while (fast !== slow) {
fast = fast.next;
slow = slow.next;
}
return slow;
};
# 寻找链表的中点
一快一慢指针遍历，指针遍历完成时，慢指针就是中点
var middleNode = function(head) {
let fast = head;
let slow = head;
while (fast && fast.next) {
fast = fast.next.next;
slow = slow.next;
}
return slow;
};
# 寻找链表的倒数第 N 个元素
先让快指针走 n 步，然后两个指针同时遍历，到最后慢指针的下一个节点就是删除的节点，记得考虑一开始头指针就是要删除的节点，这时返回head.next
var removeNthFromEnd = function(head, n) {
let fast = head;
let slow = head;
// 快指针先走n步
for (let i = 0; i < n; i++) {
fast = fast.next;
}
// 如果删除的倒数第n个节点是头结点，直接返回下一节点
if (fast === null) {
return head.next;
}
// 快指针走完之后双指针匀速前行，到头则slow.next就是要删除的倒数第n个节点
while (fast && fast.next) {
fast = fast.next;
slow = slow.next;
}
slow.next = slow.next.next;
return head;
};
# 左右指针
左右指针一般这样初始化
let left = 0;
let right = nums.length - 1;
左右指针问题一般是处理二分查找(数组或者字符串)
# 二分查找
# 两数之和 II - 输入有序数组
二分法
var twoSum = function(numbers, target) {
let left = 0;
let right = numbers.length - 1;
while (left < right) {
let sum = numbers[left] + numbers[right];
if (sum === target) {
return [left + 1, right + 1];
} else if (sum < target) {
// 让sum大点
left++;
} else if (sum > target) {
// 让sum小点
right--;
}
}
return [-1, -1];
};
# 反转字符数组
二分法，一前一后遍历更换值
var reverseString = function(s) {
let left = 0;
let right = s.length - 1;
while (left < right) {
const temp = s[left];
s[left] = s[right];
s[right] = temp;
left++;
right--;
}
};
# 滑动窗口解题模板
滑动窗口一般会初始化两个指针let left = 0 let right =0
解决子串、子数组的通用技巧
原版滑动窗口解题模板
/* 滑动窗口算法框架 */
void slidingWindow(string s, string t) {
unordered_map<char, int> need, window;
for (char c : t) need[c]++;
int left = 0, right = 0;
int valid = 0;
while (right < s.size()) {
// c 是将移入窗口的字符
char c = s[right];
// 右移窗口
right++;
// 进行窗口内数据的一系列更新
...
/*** debug 输出的位置 ***/
printf("window: [%d, %d)\n", left, right);
/********************/
// 判断左侧窗口是否要收缩
while (window needs shrink) {
// d 是将移出窗口的字符
char d = s[left];
// 左移窗口
left++;
// 进行窗口内数据的一系列更新
...
}
}
}
转成 javascript 版
function slidingwindow(s){
let left = 0
let right = 0
let res = 0
const map = new Map()
// 如果需要下标操作，则需要改成for循环
while(right < s.length){
// 移入窗口字符
map.add(s[right])
right++
// 更新数据
update(res)
// 判断左侧窗口是否需要收缩
while(map need shrink){
map.add(s[left])
left++
// 更新数据
update(res)
}
}
}
# 最小覆盖子串(建议熟记)
在 S(source) 中找到包含 T(target) 中全部字母的一个子串，且这个子串一定是所有可能子串中最短的
解题思路:
- 找到包含 T 的所有子串
- 在这些子串中返回长度最短的
首先我们可以利用滑动窗口解决这个问题，写滑动窗口的题目最重要的就是确定左指针和右指针的分工问题，比如我们将这个题目变动下，变为找到最小不重复子串的大小，我们就可以这样想：
- 右指针干的事情：不停的移入窗口字符，更新最后返回长度
- 左指针干的事情：当 map 里面有了当前字符，就移动左指针，最后返回的就是
right-left+1即最小长度 - 确定什么时候移动左指针：遇到重复字符时
所以这道题我们思路可以这样展开
- 首先初始化一个 need 的 map，用来记录指针滑动过程中遇到符合条件的字符的个数(例如
T="ABC",初始化need={'A':1,'B':1,'C':1})，初始化一个变量初始值为 map 的大小变量(needSize)，初始化返回字符串为空字符串 - 右指针干的事情：当右指针遇到需要的字符就更新对应字符的 value，更新 Map 和 needSize
- 左指针干的事情：移动左指针，每次遇到需要的字符，更新 Map 和 needSize，每次都要更新最后返回值
- 确定什么时候移动左指针：needSize=0
var minWindow = function(s, t) {
// 前期初始化数据
let left = 0;
let right = 0;
let need = new Map();
for (let c of t) {
need.set(c, need.has(c) ? need.get(c) + 1 : 1);
}
let needSize = need.size;
let res = "";
while (right < s.length) {
let c1 = s[right];
//右滑，更新数据
if (need.has(c1)) {
need.set(c1, need.get(c1) - 1);
if (need.get(c1) === 0) {
needSize--;
}
}
/*
* 当目标子串已经完全覆盖，也代表needSize=0，左滑,
* 更新(将value+1,也就是慢慢删除覆盖子串)数据和返回数据
* */
while (needSize == 0) {
const newStr = s.substring(left, right + 1);
// 保证第一次赋值，并且每次更新返回值
if (!res || res.length > newStr.length) {
res = newStr;
}
let c2 = s[left];
need.set(c2, need.get(c2) + 1);
if (need.get(c2) === 1) {
needSize++;
}
left++;
}
// 这里右指针累加只能放在最后，不然会出问题
right++;
}
return res;
};
# 字符串的排列
这道题换句话来说和上一道题的唯一区别：上一题是从众多包含子串求最小的子串长度，这一题是求众多包含子串中长度刚好和 target 子串长度相同的子串，只是修改了条件，做法相同。
var checkInclusion = function(s1, s2) {
/**
* 初始化: need = {'a':1,'b':1} left=0 right=0 needSize = 2，res=false
*
* 右指针需做事情: 滑动指针，如果need碰到集合中有当前遍历字符， 更新need,更新needSize
*
* 左指针需做事情: 滑动指针，如果need碰到集合中有当前字符，更新need和needSize，在这之前更新res，
* 如果窗口大小的等于s1的大小，则代表完全覆盖，res=true
*
* 左指针滑动的条件: needSize = 0
*/
let left = 0;
let right = 0;
let need = new Map();
// 初始化need
for (let c of s1) {
need.set(c, need.has(c) ? need.get(c) + 1 : 1);
}
let needSize = need.size;
while (right < s2.length) {
let c1 = s2[right];
// 右滑，当前字符在need中
if (need.has(c1)) {
// 更新need,value - 1
need.set(c1, need.get(c1) - 1);
// 更新needSize
if (need.get(c1) === 0) {
needSize--;
}
}
// 移动左指针
while (needSize === 0) {
// 更新最终结果
if (right - left + 1 === s1.length) {
return true;
}
let c2 = s2[left];
// 左滑，更新need
if (need.has(c2)) {
need.set(c2, need.get(c2) + 1);
}
// 更新needSize
if (need.get(c2) === 1) {
needSize++;
}
left++;
}
// 这里的right指针位置具有玄学
right++;
}
return false;
};
# 找所有字母异位词
这道题和上一道题兼简直就是一道题，上一道题是只求一个包含子串长度等于 target 字符长度相同的子串，这道题会有多个这样的结果，我们需要将他们的第一个字符下标以数组返回即可
var findAnagrams = function(s, p) {
let left = 0;
let right = 0;
let need = new Map();
for (let c of p) {
need.set(c, need.has(c) ? need.get(c) + 1 : 1);
}
let needSize = need.size;
let res = [];
while (right < s.length) {
let c1 = s[right];
if (need.has(c1)) {
need.set(c1, need.get(c1) - 1);
if (need.get(c1) === 0) {
needSize--;
}
}
while (needSize === 0) {
let c2 = s[left];
if (right - left + 1 === p.length) {
res.push(left);
}
if (need.has(c2)) {
need.set(c2, need.get(c2) + 1);
if (need.get(c2) === 1) {
needSize++;
}
}
left++;
}
right++;
}
return res;
};
# 无重复字符的最长子串长度
这道题比较特殊，不是求某个字符串包含哪个target字符，而是求最小的不重复的字符串。
首先确定思路:
- 滑动右窗口，将字符存入 map 中
- 每次遍历都进行比较当前字符和 map 中的 key，如有相同，则代表重复，接着将左指针移动到 map 中的指针下一位即可，这里需要同时满足左指针不能越位
- 每次右移更新返回数据
var lengthOfLongestSubstring = function(s) {
let left = 0;
let map = new Map();
let res = 0;
for (let right = 0; right < s.length; s++) {
// 如果碰到已有元素，则代表出现重复字符，左指针要改变指向
// 满足左指针不越位，然后赋值
if (map.has(s[right]) && map.get(s[right]) >= left) {
left = map.get(s[right]) + 1;
}
map.set(s[r], r);
res = Math.max(res, right - left + 1);
}
return res;
};
# 动态规划解题模板
# 动态规划模板
动态规划三要素:
- 重叠子问题
- 最优子结构
- 状态转移方程
动态规划解题思维:
- 明确 base case
- 明确「状态」
- 明确「选择」
- 定义 dp 数组 / 函数的含义
动态规划套用模板:
# 初始化 base case
dp[0][0][...] = base
# 进行状态转移
for 状态1 in 状态1的所有取值：
for 状态2 in 状态2的所有取值：
for ...
dp[状态1][状态2][...] = 求最值(选择1，选择2...)
# 通过斐波那契函数理解动态规划
下面分析几种解法来体现动态规划的优势和概念
暴力递归
function fn(n) {
if (n === 0) {
return 0;
}
if (n === 1 || n === 2) {
return 1;
}
return fn(n - 1) + fn(n - 2);
}
无脑递归，这种方式如果画图就会发现重复调用很多次相同的 f(n)函数，也就是重叠子问题
这种方式的事件复杂度是什么呢？
首先需要知道递归的时间复杂度怎么计算：子问题个数 x 以解决一个子问题需要的时间
由于递归树是二叉树，所以子问题的数量为O(2^n),每个子问题计算时间是O(1)，所以这个时间复杂度为O(2^n)，呈指数增长，非常低效。
记忆递归法
function fn(n) {
if (n === 0) {
return 0;
}
if (n === 1 || n === 2) {
return 1;
}
const map = new Map();
if (map.has(n)) {
return map.get(n);
}
const res = fn(n - 1) + fn(n + 1);
map.set(n, res);
return res;
}
通过记录子问题的结果，递归的时候每种方法只会调用一次。JS 可以利用 Map 数据结构进行处理。
这种方式的子问题的数量就变成了了 O(N)，每个子问题计算时间是O(1)，所以时间复杂度为 O(N)
动态规划解法
function fn(n) {
const dp = [0, 1, 1];
for (let i = 3; i <= n; i++) {
dp[i] = dp[i - 1] + dp[i - 2];
}
return dp[n];
}
上面两种解法都是 自上而下 的想问题，动态规划解法是基于 自下而上 的解决问题，先考虑 f(0),f(1),f(2)，然后考虑 n,这种方式的时间复杂度为 O(N)
引出动态规划概念
将原问题拆解成多个子问题，同时保存子问题的答案，是的每个子问题只求解一次，最后得到原问题的答案。
状态转移方程的概念
状态压缩
其实上面的动态规划解法还可以进一步优化，我们可以将空间复杂度优化到 O(n)
function fn(n) {
if (n === 1 || n === 2) {
return 1;
}
let pre = 1;
let cur = 1;
for (let i = 3; i <= n; i++) {
let sum = pre + cur;
pre = cur;
cur = sum;
}
return cur;
}
这个技巧就是所谓的 「状态压缩」 ，如果我们发现状态转移只需要 DP table 中的一部分，那么可以尝试用状态压缩来缩小 DP table 的大小，只记录必要的数据。
# 凑硬币问题熟悉动态规划解题步骤
给你 k 种面值的硬币，面值分别为 c1, c2 ... ck，每种硬币的数量无限，再给一个总金额 amount，问你最少需要几枚硬币凑出这个金额，如果不可能凑出，算法返回 -1
比如说 k = 3，面值分别为 1，2，5，总金额 amount = 11。那么最少需要 3 枚硬币凑出，即 11 = 5 + 5 + 1。
1.列出正确的状态转移方程的步骤
我们按照前面的模板依次进行
确定 base case ，这个很简单，显然目标金额 amount = 0 时算法返回 0，因为不需要任何硬币就可以凑出目标金额。
确定「状态」，也就是原问题和子问题中会变化的变量。 由于硬币的数量无限，硬币的面额也是题目给定的，只有目标金额会不断向 base case 靠近，所以唯一的「状态」就是目标金额 amount。
确定「选择」，也就是导致「状态」产生变化的行为。 目标金额为什么变化呢，因为你在选择硬币，你每选择一枚硬币，就相当于减少了目标金额，所以说所有硬币的面值就是你的「选择」。
明确 dp 函数 / 数组的定义。 我们这里讲的是自顶向下的解法，所以会有一个递归的 dp 函数，一般来说函数的参数就是状态转移中会变化的量，即上面说到的「状态」；函数的返回值就是我们要求的值。就本题来说，状态只有一个，即「目标金额」，题目要求我们计算凑出目标金额所需的最少硬币数量，所以我们可以这样定义 dp 函数：
dp(n) ：输入一个目标金额 n，返回凑出目标金额 n 的最少硬币数量
然后就可以列出伪代码(暴力递归)
function coinChange(coins, amount) {
function dp(n) {
// 确定base-case
if (n === 0) {
return 0;
}
if (n < 0) {
return -1;
}
let res = Infinity; //设置上限制
for (const coin of coins) {
// 子问题不成立
if (n - coin < 0) {
continue;
}
// 取最值 每次循环代表取一次硬币，剩余值递归即可
res = Math.min(res, 1 + dp[n - coin]);
}
return res === Infinity ? -1 : res;
}
return dp(amount);
}
2.列出备忘录写法
function coinChange(coins, amount) {
const map = new Map();
function dp(n) {
let res = Infinity;
// 如果当前有记录，直接返回
if (map.has(n)) {
return map.get(n);
}
if (n === 0) {
return 0;
}
if (n < 0) {
return -1;
}
for (const coin of coins) {
if (n - coin < 0) {
continue;
}
res = Math.min(res, 1 + dp(n - coin));
}
map.set(n, res === Infinity ? -1 : res);
return map.get(n);
}
return dp(amount);
}
3.动态规划解法(自底向上)
var coinChange = function(coins, amount) {
/**
* 1. 初始化dp
* 2. 初始化base-case
* 3. for循环所有的状态取值
* 4. dp[状态] = 求最值(选择1，选择2,...)
*/
// amount 作为上限值
let dp = Array(amount + 1).fill(amount + 1);
dp[0] = 0;
for (let i = 0; i < dp.length; i++) {
for (const coin of coins) {
// 子问题结果不成立
if (i - coin < 0) {
continue;
}
dp[i] = Math.min(dp[i], 1 + dp[i - coin]);
}
}
return dp[amount] === amount + 1 ? -1 : dp[amount];
};
# 0-1 背包问题
- 首先我们可以确定状态，换句话说就是确定递归函数在做什么
dp(n,C) 代表考虑将 n 个物品放入容量为 C 的背包，使得价值最大。
- 书写状态转移方程
由于第 n 个背包存在两种情况，被选择和不选，所以：
dp(n,C) = Math.max(dp(n-1,C),v(n) + dp(n-1,C - w(n)))
如果不选择第 n 个物品，方程为
dp(n-1,C),否则方程为dp(n-1,C-w(n)) + v(n)，然后取最大值即可
合理利用矩阵的思维考虑背包问题
根据矩阵我们所要求的的最终返回值应该是 dp[N][W]
- 书写代码
首先可以很容易的写出暴力递归法和记忆搜索代码
// 递归
function knapsack(W, N, weight = [], value = []) {
/**
* 代表物品[0...index]在背包重量为C时的最大价值
* @param {*} w 可选物品的重量数组
* @param {*} v 可选物品的价值数组
* @param {*} index 传入index
* @param {*} C 传入的背包容量
*/
function bestValue(w, v, index, C) {
// base-case
if (index < 0 || W <= 0) {
return 0;
}
let res = bestValue(w, v, index - 1, C);
if (C >= w[index]) {
res = Math.max(res, v[index] + bestValue(w, v, index - 1, C - weight[index]));
}
return res;
}
// 此处N和weight.length 应该是同一个意思
return bestValue(weight, value, N - 1, W);
}
// 记忆搜索
function knapsack(W, N, weight = [], value = []) {
var map = new Map();
/**
* 代表物品[0...index]在背包重量为C时的最大价值
* @param {*} w 可选物品的重量数组
* @param {*} v 可选物品的价值数组
* @param {*} index 传入index
* @param {*} C 传入的背包容量
*/
function bestValue(w, v, index, C) {
// base-case
if (index < 0 || W <= 0) {
return 0;
}
let key = `${index}-${C}`;
if (map.has(key)) {
return map.get(key);
}
let res = bestValue(w, v, index - 1, C);
if (C >= w[index]) {
res = Math.max(res, v[index] + bestValue(w, v, index - 1, C - weight[index]));
}
map.set(key, res);
return res;
}
// 此处N和weight.length 应该是同一个意思
return bestValue(weight, value, N - 1, W);
}
/*N = 3, W = 4
wt = [2, 1, 3]
val = [4, 2, 3]*/
console.log(knapsack(4, 3, [2, 1, 3], [4, 2, 3]));
然后我们根据矩阵来书写动态规划式的解法,我们要求的是 dp[N][w]
function knapsack(W, N, weights, values) {
if (N === 0) {
return 0;
}
let dp = Array(N).fill(Array(W + 1).fill(-1));
// 首先考虑只有物品0的情况
for (let j = 0; j <= W; j++) {
// 放不下
if (weights[0] > j) {
dp[0][j] = 0;
} else {
dp[0][j] = values[0];
}
}
// 其次考虑物品0以外的情况
for (let i = 1; i < N; i++) {
for (let j = 0; i <= W; j++) {
dp[i][j] = dp[i - 1][j];
// 放的下
if (j >= weights[i]) {
dp[i][j] = Math.max(dp[i][j], values[i] + dp[i - 1][j - weights[i]]);
}
}
}
return dp[N - 1][W];
}
java 版本解法:
int knapsack(int W, int N, vector<int>& wt, vector<int>& val) {
// vector 全填入 0，base case 已初始化
vector<vector<int>> dp(N + 1, vector<int>(W + 1, 0));
for (int i = 1; i <= N; i++) {
for (int w = 1; w <= W; w++) {
if (w - wt[i-1] < 0) {
// 当前背包容量装不下，只能选择不装入背包
dp[i][w] = dp[i - 1][w];
} else {
// 装入或者不装入背包，择优
dp[i][w] = max(dp[i - 1][w - wt[i-1]] + val[i-1],
dp[i - 1][w]);
}
}
}
return dp[N][W];
}
# 打家劫舍问题
思路： 偷取的房子是不相邻的，还需要保证是所有方法里面的最大的数额的。
首先考虑暴力解法：假设所有房子有 n 个组合，我们对每个组合进行检查，保证其不相邻，然后记录其价值，最后从里面返回最大值。时间复杂度 O((2^n)*n)。在组合中求最大值，我们可以想到使用递归解决这个问题，如果递归中拥有重叠子问题和最优子结构，那么就可以归为动态规划问题。
画出递归树
- 确定： base-case、状态、选择、明确 dp 函数定义
- base-case:当考虑(不代表一定会偷)偷取最后一间房子时，偷取的数额为 0，所以 base-case 确定
- 状态:原问题和子问题都在考虑偷哪个下标范围的房子，所以状态为考虑偷取下标为
[x...n-1]的房子。其实也可以想成盗窃某号房子的最大价值，不同的想法递归树不同，但是解题思路和步骤都是一样的 - 选择: 改变状态的行为：偷房子之后下一个状态就需要改了，所以为偷房子
- 确定 dp 函数(状态转移方程)：假设从 0 开始偷取，最后求到的结果
dp(0) =Math.max(v(0) + dp(2) + v(1) + dp(3) ... + v(n-3) + dp(n-1) + v(n-2) + v(n-1))
ps: V(x)：决定偷取 x 号房子,dp(x)：考虑偷取[x..n-1]的房子
dp(n) = Math.max(dp(n - 1) + dp(n - 2) + V[n]);
- 暴力解法
var rob = function(nums) {
// 函数的含义为：考虑抢劫[index...nums.length-1]的房子
function tryRob(nums, index) {
// 不成立子问题规则
if (index >= nums.length) {
return 0;
}
// 实行抢劫,每次抢劫完更新最大值
let res = 0;
for (let i = index; i < nums.length; i++) {
// 抢劫nums[i]，并且要考虑抢劫i+2号开始到nums-1下标的房子，然后取最大值
res = Math.max(res, nums[i] + tryRob(i + 2));
}
return res;
}
return tryRob(nums, 0);
};
备忘录写法，使用 Map 数据结构即可
动态规划
var rob = function(nums) {
/**
* dp表示盗窃某号房子的最大价值
* dp[i] = Math.max(dp[i-1],dp[i-2] + nums[i]):
* 代表第i号房子可盗窃的最大价值是第i-1号房子可盗窃的最大价值和第i-2号房子可盗窃的最大价值
* 加上本身的价值作比较，取最大值
*
* 举例说明: nums = [2,4,3],1号房子可盗窃最大价值就是本身nums[0]=2,2号房子可盗窃最大价值也是本身nums[1] = 4,3号房子可盗窃的最大价值dp[2] = Math.max(4,2+3) = 5,状态转移方程成立
* */
let n = nums.length;
if (!n) {
return 0;
}
if (n === 1) {
return nums[0];
}
let dp = [];
dp[0] = nums[0];
dp[1] = Math.max(nums[0], nums[1]);
for (let i = 2; i <= n; i++) {
dp[i] = Math.max(dp[i - 1], dp[i - 2] + nums[i]);
}
return dp[n - 1];
};
# 最长递增子序列问题(子串和子序列区分)
首先需要区分子序列和子串的关系：
- 子序列（subsequence）：子序列并不要求连续，例如：序列 [4, 6, 5] 是 [1, 2, 4, 3, 7, 6, 5] 的一个子序列；
- 子串（substring、subarray）：子串一定是原始字符串的连续子串，例如：「力扣」第 3 题：无重复字符的最长子串，「力扣」第 53 题：最大子序和。
动态规划解法：
首先考虑题目问什么，就把什么定义成状态。题目问最长上升子序列的长度，其实可以把「子序列的长度」定义成状态，但是发现「状态转移」不好做。
对于子序列而言，一个数是否被选中很重要，因此我们在设计状态的时候，一个数是否被选中就是隐含的状态。根据这个问题的目标，如果一个较大的数接在较小的数后面，就会形成一个更长的子序列。因此将状态定义成：dp[i] 表示以 nums[i] 结尾的「上升子序列」的长度。
简单来说，碰到子序列问题，一个数是否被选中很重要。这个问题就是 nums[i]之前的数满足
- base-case，dp[1] = 1
- 考虑状态：
nums[i]结尾的子序列的长度 - 考虑选择：子序列是否被选中
- 确定 dp 函数的定义和含义：表示 nums[i] 结尾的上升子序列的长度
- 遍历到 nums[i] 时，需要把下标 i 之前的所有的数都看一遍；
- 只要 nums[i] 严格大于在它位置之前的某个数，那么 nums[i] 就可以接在这个数后面形成一个更长的上升子序列；
- 因此，dp[i] 就等于下标 i 之前严格小于 nums[i] 的状态值的最大者 +1
function lengthOfLIS(nums) {
let n = nums.length;
// base-case
if (!n) {
return 0;
}
if (n === 1) {
return 1;
}
// 假设每一个下标对应的元素都为1
let dp = Array(n).fill(1);
// 双层循环，i代表选中子序列的最后一个数，j代表在它之前的数，在它之前的数必须小于第i个元素,0<=j<i
for (let i = 1; i < nums.length; i++) {
for (let j = 0; j < i; j++) {
if (nums[j] < nums[j]) {
// dp[i] 就等于下标 i 之前严格小于 nums[i] 的状态值的最大者 +1
dp[i] = Math.max(dp[i], dp[j] + 1);
}
}
}
// 现在dp是个数组，里面存着每个下标所对应的子序列长度，取最大值即可
return Math.max(...dp);
}
# 股票买卖问题(通解)
# 使用穷举框架
for 状态1 in 状态1的所有取值：
for 状态2 in 状态2的所有取值：
for ...
dp[状态1][状态2][...] = 择优(选择1，选择2...)
每天都有三种「选择」：买入、卖出、无操作，我们用 buy, sell, rest 表示这三种选择。但问题是，并不是每天都可以任意选择这三种选择的，因为 sell 必须在 buy 之后，buy 必须在 sell 之后。那么 rest 操作还应该分两种状态，一种是 buy 之后的 rest（持有了股票），一种是 sell 之后的 rest（没有持有股票）。而且别忘了，我们还有交易次数 k 的限制，就是说你 buy 还只能在 k > 0 的前提下操作。
dp[i][k][0 or 1]
0 <= i <= n-1, 1 <= k <= K
n 为天数，大 K 为最多交易数
此问题共 n × K × 2 种状态，全部穷举就能搞定。
for 0 <= i < n:
for 1 <= k <= K:
for s in {0, 1}:
dp[i][k][s] = max(buy, sell, rest)
dp[3][2][1] 的含义就是：今天是第三天，我现在手上持有着股票，至今最多进行 2 次交易的最大利润
我们想求的最终答案是 dp[n - 1][K][0]，即最后一天，最多允许 K 次交易，最多获得多少利润。读者可能问为什么不是 dp[n - 1][K][1]？因为 [1] 代表手上还持有股票，[0] 表示手上的股票已经卖出去了，很显然后者得到的利润一定大于前者。
# 书写动态转移方程
dp 方程
// 未持有股票的dp方程
两种情况:
1. 我昨天没有持有股票，然后今天选择rest，还是没有持有
2. 我昨天持有股票，然后今天把昨天的股票卖掉，今天选择sell掉，变成没有持有
dp[i][k][0] = Math.max(dp[i-1][k][0],dp[i-1][k][1] + price[i])
// 持有股票的dp方程 买入记得k-1
两种情况:
1. 我昨天持有股票，然后今天选择rest，还是持有
2. 我昨天没有持有股票，然后今天选择buy，变成持有
dp[i][k][1] = Math.max(dp[i-1][k][1],dp[i-1][k-1][0] - price[i])
base-case
dp[-1][k][0] = 0
解释：因为 i 是从 0 开始的，所以 i = -1 意味着还没有开始，这时候的利润当然是 0 。
dp[-1][k][1] = -infinity
解释：还没开始的时候，是不可能持有股票的，用负无穷表示这种不可能。
dp[i][0][0] = 0
解释：因为 k 是从 1 开始的，所以 k = 0 意味着根本不允许交易，这时候利润当然是 0 。
dp[i][0][1] = -infinity
解释：不允许交易的情况下，是不可能持有股票的，用负无穷表示这种不可能。
总结
base case：
dp[-1][k][0] = dp[i][0][0] = 0
dp[-1][k][1] = dp[i][0][1] = -infinity
状态转移方程：
dp[i][k][0] = max(dp[i-1][k][0], dp[i-1][k][1] + prices[i])
dp[i][k][1] = max(dp[i-1][k][1], dp[i-1][k-1][0] - prices[i])
# 几种股票问题解法
k=1
k=1 不会影响 dp 方程，所以去掉
状态转移方程可写为
dp[i][0][0] = 0;
dp[i][0] = Math.max(dp[i - 1][0], dp[i - 1][1] + price[i]);
dp[i][1] = Math.max(dp[i - 1][1], -price[i]);
java 解法
for (int i = 0; i < n; i++) {
if (i - 1 == -1) {
dp[i][0] = 0;
// 解释：
// dp[i][0]
// = max(dp[-1][0], dp[-1][1] + prices[i])
// = max(0, -infinity + prices[i]) = 0
dp[i][1] = -prices[i];
//解释：
// dp[i][1]
// = max(dp[-1][1], dp[-1][0] - prices[i])
// = max(-infinity, 0 - prices[i])
// = -prices[i]
continue;
}
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[n - 1][0];
这样写比较复杂，我们可以使用变量代替状态数组，这样就可以将空间复杂度变成 O(1)
function maxProfit_k_1(price = []) {
// base-case 相当 dp[-1][0] = 0, dp[-1][1] = -infinity
let dp_i_0 = 0;
let dp_i_1 = -Infinity;
for (let i = 0; i < price.length; i++) {
// 相当于dp[i][0] = Math.max(dp[i][0],dp[i][1]+price[i])
dp_i_0 = Math.max(dp_i_0, dp_i_1 + price[i]);
dp_i_1 = Math.max(dp_i_1, -price[i]);
}
return dp_i_0;
}
k = infinity
此时 k 和 k-1 相同
状态转移方程可写为
dp[i][0] = Math.max(dp[i - 1][0], dp[i - 1][1] + price[i]);
dp[i][1] = Math.max(dp[i - 1][1], dp[i - 1][0] - price[i]);
dp_i_0 = Math.max(dp_i_0, dp_i_1 + price[i]);
dp_i_1 = Math.max(dp_i_1, dp_i_0 - price[i]);
function maxProfit_k_infinity(price = []) {
// base-case 相当 dp[-1][0] = 0, dp[-1][1] = -infinity
let dp_i_0 = 0;
let dp_i_1 = -Infinity;
for (let i = 0; i < price.length; i++) {
// 相当于dp[i][0] = Math.max(dp[i][0],dp[i][1]+price[i])
dp_i_0 = Math.max(dp_i_0, dp_i_1 + price[i]);
dp_i_1 = Math.max(dp_i_1, dp_i_0 - price[i]);
}
return dp_i_0;
}
- 有手续费，买入需要减去手续费
var maxProfit = function(prices, fee) {
let dp_i_0 = 0;
let dp_i_1 = -Infinity;
for (let i = 0; i < prices.length; i++) {
dp_i_0 = Math.max(dp_i_0, dp_i_1 + prices[i]);
dp_i_1 = Math.max(dp_i_1, dp_i_0 - prices[i] - fee);
}
return dp_i_0;
};
- 有冷冻期一天，也就是说买入需要用上次利润减去当前买入股票的价格
dp[i][0] = max(dp[i-1][0], dp[i-1][1] + prices[i])
dp[i][1] = max(dp[i-1][1], dp[i-2][0] - prices[i])
解释：第 i 天选择 buy 的时候，要从 i-2 的状态转移，而不是 i-1 。
var maxProfit = function(prices) {
let dp_i_0 = 0;
let dp_i_1 = -Infinity;
let dp_pre_0 = 0; // 相当于 dp[i-2][0]
for (let i = 0; i < prices.length; i++) {
// 记录上次的最大利润
let temp = dp_i_0;
dp_i_0 = Math.max(dp_i_0, dp_i_1 + prices[i]);
dp_i_1 = Math.max(dp_i_1, dp_pre_0 - prices[i]);
dp_pre_0 = temp;
}
return dp_i_0;
};
# 贪心算法
# 通过分配饼干问题理解贪心算法
假设饼干大小数组为 [1,2,3]
小朋友的贪心指数数组为 [1,2]
我们要求的是如何分配饼干，让更多的小朋友开心，也就是求最后让多少个小朋友开心
如果饼干非常多的话，我们未来保证更多的小朋友开心(达到贪心指数)，
我们尽量的使用最大的饼干满足最贪心的小朋友，也就是 `3===>2`,
这样我们留给次贪心的小朋友也会得到次大的饼干。
这样我们在饼干的分配上留给了剩余小朋友很多的余地，能够让更多的小朋友都开心。
但是如果最大的饼干都没有满足最贪心的小朋友的话，那这个小朋友则无法获得饼干，接着需要去找下一个次贪心的小朋友
相对应，我们必须要使得这两个数组排序好
var findContentChildren = function(g, s) {
// 内置的排序方法效率最好
g = g.sort((a, b) => b - a);
s = s.sort((a, b) => b - a);
// 因为数组从大到小排序 通过控制两个数组的指针来分配饼干，其实下标为0
let g1 = 0;
let s1 = 0;
let res = 0;
while (g1 < g.length && s1 < s.length) {
// 代表最大的饼干可以让最贪心的小朋友开心,更新数据
if (s[s1] >= g[g1]) {
res++;
s1++;
g1++;
} else {
// 最大的饼干无法满足最贪心小朋友
g1++;
}
}
return res;
};
# 堆
堆是一种特殊的完全二叉树(只允许最底层子节点的右节点空缺，其余的子节点必须填满)
解决最值，第 K 个最大值，前 k 个最大值的通用技巧
堆可以细分为最小堆和最大堆，最小堆的父节点一定是小于等于子节点的，反之最大堆 ed 父节点大于等于子节点。
图中实例就是最小堆。
定义一个堆，使用数组 let q = [],剔除堆顶元素 pop()
堆的使用场景
- 计算最大值和最小值
- 计算数组的第 k 个最大值或者最小值
原理
首先毫不犹豫使用最小堆解决这个问题
思路：可以想象成原本 K 个人守一个擂台，插入元素就好比于去攻打擂台，打赢了(加一个，但是容积只有 K)，这时候只能删掉最弱的，也就是堆顶，最后循环结束返回堆顶。
- 将数组元素入堆
- 如果容积超过 K，删除堆顶元素(最小值)
- 插入结束，取出堆顶就是第 K 个最值
时间复杂度: O(1)
# 构建最小堆类
解决最值问题基础，学会构建最小堆类
实现最小堆的四要素: 插入(上移操作保证父节点小于子节点) 删除(下移操作保证子节点大于父节点) 获取堆顶 获取堆的大小
/**
* 堆是完全二叉树
* 堆的父节点下标: Math.floor(i-1/2)
* 堆的左子节点下标： 2i+1
* 堆的右子节点下标： 2i+2
*/
class MiniHeap {
constructor() {
// 定义堆
this.heap = [];
}
// 千万不要写成m和n交换
swap(m, n) {
let temp = this.heap[m];
this.heap[m] = this.heap[n];
this.heap[n] = temp;
}
/**
* 插入: 插入元素到底部，然后将该元素做上移操作(需要满足父节点必须小于等于子节点)
* @param {*} value 插入元素值
*/
insert(value) {
this.heap.push(value);
this.shiftUp(this.heap.length - 1);
}
// 上移，比较父节点和子节点的大小,如果不符合条件就交换元素，然后对新的元素继续进行上移操作
shiftUp(index) {
// 堆顶不上移
if (index === 0) {
return;
}
const parentIndex = Math.floor(index - 1 / 2);
if (this.heap[parentIndex] > this.heap[index]) {
this.swap(parentIndex, index);
this.shiftUp(parentIndex);
}
}
// 堆大小
len() {
return this.heap.length;
}
/**
* 删除: 不能直接删除堆顶元素，需要用数组尾元素替换堆顶元素，然后进行下移操作
*/
pop() {
// 替换堆顶元素先
this.heap[0] = this.heap.pop();
// 下移
this.shiftDown(0);
}
// 下移操作，这里我们需要保证子节点是大于等于父节点的
shiftDown(index) {
const leftChildIndex = 2 * index + 1;
const rightChildIndex = 2 * index + 2;
if (this.heap[index] > this.heap[leftChildIndex]) {
this.swap(index, leftChildIndex);
this.shiftDown(leftChildIndex);
}
if (this.heap[index] > this.heap[rightChildIndex]) {
this.swap(index, rightChildIndex);
this.shiftDown(rightChildIndex);
}
}
// 获取堆顶元素
heep() {
return this.heap[0];
}
}
let h1 = new MiniHeap();
console.log("堆元素 " + h1.heap, "堆大小 " + h1.len(), "堆顶 " + h1.heap);
h1.insert(4);
console.log("堆元素 " + h1.heap, "堆大小 " + h1.len(), "堆顶 " + h1.heap);
h1.insert(3);
h1.insert(2);
h1.insert(1);
console.log("堆元素 " + h1.heap, "堆大小 " + h1.len(), "堆顶 " + h1.heap);
h1.delete();
console.log("堆元素 " + h1.heap, "堆大小 " + h1.len(), "堆顶 " + h1.heap);
# 堆排序
/**
* 思路： 堆排序需要三个方法：主体函数 + 构建堆 + 调整堆 时间复杂度：O(nlogn)
*/
// 主方法: 首先构建堆，遍历数组，这个时候第一个元素就是最大值，将堆头和尾元素更换位置，length-1，继续调整堆调换位置
function heapsort(arr) {
buildHeap(arr);
for (let i = arr.length - 1; i > 0; i--) {
// 交换
swap(arr, 0, i);
// 下移调整
heapify(arr, 0, i);
}
return arr;
}
function buildHeap(arr) {
if (!arr.length) {
return;
}
// 只有Math.floor(len/2-1)需要调整，记得此处i可以等于0
for (let i = Math.floor(arr.length / 2 - 1); i >= 0; i--) {
heapify(arr, i, arr.length);
}
}
// 堆调整：找到子节点最大的，然后交换父子节点，循环结束要重新赋值父节点，表示找到了位置,可以理解为下移操作
function heapify(arr, parent, length) {
let temp = arr[parent];
let childIndex = 2 * parent + 1;
// 找到最大节点下标
while (childIndex < length) {
if (childIndex + 1 < length && arr[childIndex + 1] > arr[childIndex]) {
childIndex++;
}
// 不符合大顶堆则跳出循环
if (arr[childIndex] <= arr[parent]) {
break;
}
arr[parent] = arr[childIndex];
parent = childIndex;
childIndex = 2 * parent + 1;
}
//循环结束要重新赋值父节点
arr[parent] = temp;
}
function swap(arr, i, j) {
let temp = arr[i];
arr[i] = arr[j];
arr[j] = temp;
}
let arr1 = [1, 21, 12312312, 3312, 234, -1];
console.log(heapsort(arr1));
# 数组中的第 K 个最大元素 (opens new window)
class MiniHeap {
constructor() {
// 定义堆
this.heap = [];
}
// 千万不要写成m和n交换
swap(m, n) {
let temp = this.heap[m];
this.heap[m] = this.heap[n];
this.heap[n] = temp;
}
/**
* 插入: 插入元素到底部，然后将该元素做上移操作(需要满足父节点必须小于等于子节点)
* @param {*} value 插入元素值
*/
insert(value) {
this.heap.push(value);
this.shiftUp(this.heap.length - 1);
}
// 上移，比较父节点和子节点的大小,如果不符合条件就交换元素，然后对新的元素继续进行上移操作
shiftUp(index) {
// 堆顶不上移
if (index === 0) {
return;
}
const parentIndex = Math.floor(index - 1 / 2);
if (this.heap[parentIndex] > this.heap[index]) {
this.swap(parentIndex, index);
this.shiftUp(parentIndex);
}
}
// 堆大小
len() {
return this.heap.length;
}
/**
* 删除: 不能直接删除堆顶元素，需要用数组尾元素替换堆顶元素，然后进行下移操作
*/
pop() {
// 替换堆顶元素先
this.heap[0] = this.heap.pop();
// 下移
this.shiftDown(0);
}
// 下移操作，这里我们需要保证子节点是大于等于父节点的
shiftDown(index) {
const leftChildIndex = 2 * index + 1;
const rightChildIndex = 2 * index + 2;
if (this.heap[index] > this.heap[leftChildIndex]) {
this.swap(index, leftChildIndex);
this.shiftDown(leftChildIndex);
}
if (this.heap[index] > this.heap[rightChildIndex]) {
this.swap(index, rightChildIndex);
this.shiftDown(rightChildIndex);
}
}
// 获取堆顶元素
heep() {
return this.heap[0];
}
}
var findKthLargest = function(nums, k) {
let h1 = new MiniHeap();
nums.forEach(num => {
h1.insert(num);
if (h1.len() > k) {
h1.pop();
}
});
return h1.heep();
};
# 前 K 个高频元素 (opens new window)
class MinHeep {
constructor() {
this.heep = [];
}
swap(m, n) {
let temp = this.heep[m];
this.heep[m] = this.heep[n];
this.heep[n] = temp;
}
shiftUp(index) {
if (index === 0) {
return;
}
let parentIndex = Math.floor(index - 1 / 2);
// 可能会取到undefined
if (this.heep[parentIndex].value && this.heep[parentIndex].value > this.heep[index].value) {
this.swap(parentIndex, index);
this.shiftUp(parentIndex);
}
}
shifDown(index) {
let leftChildIndex = 2 * index + 1;
let rightChildIndex = 2 * index + 2;
// 可能会取到undefined
if (this.heep[leftChildIndex] && this.heep[leftChildIndex].value < this.heep[index].value) {
this.swap(leftChildIndex, index);
this.shifDown(leftChildIndex);
}
if (this.heep[rightChildIndex] && this.heep[rightChildIndex].value < this.heep[index].value) {
this.swap(rightChildIndex, index);
this.shifDown(rightChildIndex);
}
}
insert(value) {
this.heep.push(value);
this.shiftUp(this.heep.length - 1);
}
delete() {
this.heep[0] = this.heep.pop();
this.shifDown(0);
}
size() {
return this.heep.length;
}
top() {
return this.heep[0];
}
}
var topKFrequent = function(nums, k) {
/**
* 按照题意有两种解法：
* 1. 用map保存每个数出现的次数为value，数为key，然后将map转为数组进行排序，最后截取前k个元素即可，时间复杂度：O(nlogn),不符合题意
* 2. 用map保存每个数出现的次数为value，数为key，然后使用最小堆将{key,value}对象插入，这时需要改造下最小堆的类。当容积大于k时，移除堆顶元素，最后返回堆的key组成的数组即可
*/
// 最优做法：O(klogn)
// 首先使用map记录各个元素出现的次数
let map = new Map();
nums.forEach(num => {
map.set(num, map.has(num) ? map.get(num) + 1 : 1);
});
// 使用最小堆解决问题
let h1 = new MinHeep();
// 记住这里是value-key
map.forEach((value, key) => {
h1.insert({ value, key });
// 如果超过k
if (h1.size() > k) {
h1.delete();
}
});
return h1.heep.map(obj => obj.key);
// // 使用排序O(nlogn)
// let sortMapArray = Array.from(map).sort((a,b)=>b[1]-a[1])
// return sortMapArray.map(arr=>arr[0]).slice(0,k)
};
# 前缀和
计算前缀和的方法
如果要求计算从下标j到下标i的和为k的情况的个数的话，可以使用前缀和
如图，首先
pre[i+1] = pre[i] + nums[i+1]
pre[i] - pre[j] = nums[j+1]+..+nums[i]
pre[j] = pre[j-1] + nums[j]
==> pre[i] - pre[j-1] = k
← 算法基础 力扣 hot100 题刷题 →