数组
滑动窗口
给定一个含有 n 个正整数的数组和一个正整数 s ,找出该数组中满足其和 ≥ s 的长度最小的 连续 子数组,并返回其长度。如果不存在符合条件的子数组,返回 0。
示例:
输入:s = 7, nums = [2,3,1,2,4,3] 输出:2 解释:子数组 [4,3] 是该条件下的长度最小的子数组。
var minSubArrayLen = function(target, nums) {
// 长度计算一次
const len = nums.length;
let l = r = sum = 0,
res = len + 1; // 子数组最大不会超过自身
while(r < len) {
sum += nums[r++];
// 窗口滑动
while(sum >= target) {
res = Math.min(r - l,res)
sum-=nums[l++];
}
}
return res > len ? 0 : res;
};
哈希表
链表
反转链表
function reverse(head){
let pre=null,cur=head
while(cur){
let temp = cur
cur = cur.next
temp.next = pre
pre = temp
}
return pre
}
双指针
快慢指针
栈
单调栈
请根据每日 气温 列表,重新生成一个列表。对应位置的输出为:要想观测到更高的气温,至少需要等待的天数。如果气温在这之后都不会升高,请在该位置用 0 来代替。
例如,给定一个列表 temperatures = [73, 74, 75, 71, 69, 72, 76, 73],你的输出应该是 [1, 1, 4, 2, 1, 1, 0, 0]。
var dailyTemperatures = function(temperatures) {
const n = temperatures.length;
const res = Array(n).fill(0);
const stack = []; // 递减栈,后一个比前一个大出栈
stack.push(0);
for (let i = 1; i < n; i++) {
while (stack.length && temperatures[i] > temperatures[stack[stack.length - 1]]) {
const top = stack.pop();
res[top] = i - top;
}
stack.push(i);
}
return res;
};
队列
广度优先搜素
二叉树
基本概念
常见二叉树:
满二叉树:所有节点都有左右子节点,并且子节点处于同一层
完全二叉树:不需要满足子节点处于同层,且最末端只有左节点,或者都有
平衡二叉树:左右两个子节点高度小于等于1,map,set实现
搜索二叉树:大堆,或者小堆
数组存储: [a,b,c,d,e,f,g]
父节点索引i, 左子节点2*i+1 右子节点2*i+2
遍历方式指中间节点的顺序
定义二叉树:
function tree(value,left,right){
this.value=value===undefined ? 0 : value
this.left=left===undefined ? null : left
this.right=right===undefined ? null : right
}
迭代法
中序
let stack = []
while(root || stack.length){
while(root){
stack.push(root)
root= root.left
}
root = stack.pop()
result.push(root.val)
root = root.right
}
return result
前序
let stack=[]
let result=[]
while(root || stack.length){
while(root){
result.push(root.val)
stack.push(root)
root = root.left
}
root=stack.pop()
root= root.right
}
return result
后序
let stack=[]
let result=[]
while(root || stack.length){
while(root){
stack.push(root)
result.unshift(root.val)
root= root.right
}
root=stack.pop()
root = root.left
}
return result
动态规划
将原问题分解为相似的子问题,在求解的过程中通过子问题的解求出原问题的解。一般是
动态规划方法通常用来求解最优化问题,这类问题可以有很多可行解,每个解都有一个值,找到具有最优值的解称为问题的一个最优解
01背包
重量 价值
物品0 1 15
物品1 3 20
物品2 4 30
二维dp arr[i][j] i是物品 j是背包大小
// 遍历背包,重量顺序不影响
function testWeightBagProblem (weight, value, size) {
// 定义 dp 数组
const len = weight.length,
dp = Array(len).fill().map(() => Array(size + 1).fill(0));
// 初始化
for(let j = weight[0]; j <= size; j++) {
dp[0][j] = value[0];
}
// weight 数组的长度len 就是物品个数
for(let i = 1; i < len; i++) { // 遍历物品
for(let j = 0; j <= size; j++) { // 遍历背包容量
// 不放物品i,此时背包中只有i之前的物品
if(j < weight[i]) dp[i][j] = dp[i - 1][j];
//放入物品i,背包最大价值=之前物品最大价值 compare 放入物品i后,最大物品重量-现在物品重量的价值+现在物品价值
else dp[i][j] = Math.max(dp[i - 1][j], dp[i - 1][j - weight[i]] + value[i]);
}
}
console.table(dp)
return dp[len - 1][size];
}
// 重量,价值,最大重量
console.log(testWeightBagProblem([1, 3, 4, 5], [15, 20, 30, 55], 6));
一维dp dp[j]代表重量为j时最大价值
// 遍历顺序影响结果
function testWeightBagProblem(wight, value, size) {
const len = wight.length,
dp = Array(size + 1).fill(0);
for(let i = 0; i <= len; i++) {
// 保证物品只被添加一次
for(let j = size; j >= wight[i]; j--) {
dp[j] = Math.max(dp[j], value[i] + dp[j - wight[i]]);
}
}
return dp[size];
}
console.log(testWeightBagProblem([1, 3, 4, 5], [15, 20, 30, 55], 6));
完全背包
遍历背包,物品顺序无所谓,先遍历背包重量需要单独判断当前重量大于前一个背包重量
// 先遍历物品,再遍历背包容量
function test_completePack(weight,value,bagWeight) {
let dp = new Array(bagWeight + 1).fill(0)
for(let i = 0; i <= weight.length; i++) {
// 物品可以多次选择,所以是从前往后遍历背包
for(let j = weight[i]; j <= bagWeight; j++) {
dp[j] = Math.max(dp[j], dp[j - weight[i]] + value[i])
}
}
console.log(dp)
}
// 先遍历背包容量,再遍历物品
function test_completePack(weight,value,bagWeight) {
let dp = new Array(bagWeight + 1).fill(0)
for(let j = 0; j <= bagWeight; j++) {
for(let i = 0; i < weight.length; i++) {
if (j >= weight[i]) {
dp[j] = Math.max(dp[j], dp[j - weight[i]] + value[i])
}
}
}
console.log(dp);
}
test_completePack([1, 3, 5],[15, 20, 30],4)
最长递增子序列
给定一个数组,找出它的最大递增子序列 [4,2,5,7,3,9]
function maxAdd(nums){
let len = nums.length
let dp = new Array(len).fill(0)
let res = 1
for(let i=1;i<len;i++){
for(let j=0;j<i;j++){
if(nums[i]>nums[j]){
dp[i] = Math.max(dp[j]+1,dp[i])
}
}
res = Math.max(dp[i],res)
}
return res
}
贪心算法
在对问题求解时,总是做出在当前看来是最好的选择
平时购物找零钱时,为使找回的零钱的硬币数最少,不要求找零钱的所有方案,而是从最大面值的币种开始,按递减的顺序考虑各面额,先尽量用大面值的面额,当不足大面值时才去考虑下一个较小面值,这就是贪心算法
回溯法
通用模板
void backtracking(参数) {
if (终止条件) {
存放结果;
return;
}
for (选择:本层集合中元素（树中节点孩子的数量就是集合的大小）) {
处理节点;
backtracking(路径,选择列表); // 递归
回溯,撤销处理结果
}
}
生成括号
数字 n 代表生成括号的对数,请你设计一个函数,用于能够生成所有可能的并且 有效的 括号组合。
var generateParenthesis = function (n) {
const res = [];
const dfs = (lRemain, rRemain, str) => { // 左右括号所剩的数量,str是当前构建的字符串
if (str.length == 2 * n) { // 字符串构建完成
res.push(str); // 加入解集
return; // 结束当前递归分支
}
if (lRemain > 0) { // 只要左括号有剩,就可以选它,然后继续做选择（递归）
dfs(lRemain - 1, rRemain, str + "(");
}
if (lRemain < rRemain) { // 右括号比左括号剩的多,才能选右括号
dfs(lRemain, rRemain - 1, str + ")"); // 然后继续做选择（递归）
}
};
dfs(n, n, ""); // 递归的入口,剩余数量都是n,初始字符串是空串
return res;
};
电话号码组合
给定一个仅包含数字 2-9 的字符串,返回所有它能表示的字母组合。答案可以按 任意顺序 返回。
给出数字到字母的映射如下（与电话按键相同）。注意 1 不对应任何字母。
var letterCombinations = function(digits) {
//dfs
if(!digits) return []
let result =[]
let map = {2:'abc',3:'def',4:'ghi',5:'jkl',6:'mno',7:'pqrs',8:'tuv',9:'wxzy'}
function dfs(used,str){
if(used>=digits.length){
result.push(str.slice())
return
}
const cur = map[digits[used]]
for(const value of cur ){
dfs(used+1,str+value)
}
}
dfs(0,'')
return result
};
全排列
给定一个不含重复数字的数组 nums ,返回其 所有可能的全排列 。你可以 按任意顺序 返回答案。
var permute = function(nums) {
let result = []
let used = {}
function dfs(arr){
if(arr.length===nums.length){
result.push(arr.slice())
return
}
for(const item of nums){
if(used[item]) continue
used[item] = true
arr.push(item)
dfs(arr)
used[item] = false
arr.pop()
}
}
dfs([])
return result
};
子集
给定一组不含重复元素的整数数组 nums,返回该数组所有可能的子集（幂集）。
说明:解集不能包含重复的子集。
示例: 输入: nums = [1,2,3] 输出: [ [3], [1], [2], [1,2,3], [1,3], [2,3], [1,2], [] ]
const temp = [];
const ans = [];
const dfs = (cur) => {
if (cur === nums.length) {
ans.push(temp.slice());
return;
}
temp.push(nums[cur]);
dfs(cur + 1);
temp.pop();
dfs(cur + 1);
}
dfs(0);
return ans;
组合
给定两个整数 n 和 k，返回范围 [1, n] 中所有可能的 k 个数的组合。
let combine = function (n, k) {
const ans = []
const dfs = (cur, temp) => {
if (temp.length + (n - cur + 1) < k) {
return
}
if (temp.length === k) {
ans.push(temp)
return
}
dfs(cur + 1,[...temp, cur])
dfs(cur + 1,temp)
}
dfs(1,[])
return ans
}