labuladong 的算法小抄

最底层的就是数组和链表

对于解决 hash 冲突的办法: 拉链法和 线性探查法 树如果用 数组来实现就是堆

数组由于是连续紧凑型,可以随机访问,通过索引能够快速找到对应的元素,而且如果相对节约存储空间。 但正因为连续存储,内存空间必须一次性给足,时间复杂度 0(N); 如果想进行插入和删除操作,每次必须搬运后面的所有数据,时间复杂度度为 O(N);

链表因为元素不连续,靠指针指向下一个元素的位置,所以不存在数组的扩容问题;如果知道某一元素的前驱和后驱,操作指针即可删除该元素或者插入该元素,时间复杂度为 O(1); 但是正因为空间的不连续,你无法根据索引算出对应元素的地址,所以不能随机访问,而且每个元素必须存储指向前后元素位置的指针,会消耗更多的存储空间。

数据结构种类很多, 他们的目的就是无非就是不用的应用场景下高效的增删改查;

线性形式以 for/while 迭代为代表,非线性形式以递归为代表

二叉树有前中后序遍历 其实链表也有前序和后序遍历, 例如在前序遍历的时候打印 head.val 就是正序打印链表;在后序遍历的位置打印 head.val 就是倒序打印链表; 写过 web 中间件的朋友应该可以发现,中间件的调用链其实就是一个递归遍历链表的过程。 前置中间件 比如 session 的注入 在前序遍历的位置执行, 后置中间件(异常捕获)在后序遍历的位置执行 而一些中间件(计算调用总耗时)在前序和后序遍历的位置都有代码

只要是递归基本上都是树的问题

1.2 动态规划解题套路框架 1.首先,动态规划问题的一般形式就是求最值, 求解动态规划的核心问题是穷举

动态规划的穷举有点特别, 存在『重叠子问题』 所以需要『备忘录』或者『DP table』来优化穷举过程 动态规划问题一定会具备『最有子结构』,虽然穷举所有可行解并不是一件容易的事,只有列出正确的『状态转移方程』,才能正确的穷举。

要想写出正确的状态转移方程, 一定要思考以下几点: 1.这个问题的 base case(最简单情况)是什么? 2.这个问题有什么『状态』

但凡遇到需要递归解决的问题,最好都画出递归树。

递归算法的的时间复杂度怎么计算?就是用子问题个数乘以解决一个子问题需要的时间。

斐波那契数列 二叉树节点总数为指数级别的,所以求子问题个数的时间复杂度为 O(2 指数 n)

自顶向下

let fiber = function (num) {
  let cache = [];
  let fib = function (cache, num) {
    if (num <= 1) return 1;
    if (cache[num]) {
      return cache[num];
    } else {
      cache[num] = fib(cache, num - 1) + fib(cache, num - 2);
    }
    return cache[num];
  };
  return fib(cache, num);
};
console.log(fiber(200));

自底向上 DP table 来消除重叠子问题

let fiber = function (n) {
  if (n === 0) return 0;
  if (n === 1 || n === 2) return 1;
  let dp = [];
  dp[1] = dp[2] = 1;
  for (let i = 3; i <= n; i++) {
    dp[i] = dp[i - 1] + dp[i - 2];
  }
  return dp[n];
};
console.log(fiber(8));

凑零钱

如何列出正确的状态转移方程

  1. 确定 base case

  2. 确定『状态』, 也就是原问题和子问题的变量

  3. 确定『选择』, 也就是导致『状态』产生变化的行为

  4. 明确 dp 函数、数组的定义

dp(n)的定义:输入一个目标金额 n, 返回凑出目标金额 n 的最少硬币数量

let coinChange = function (coins, amount) {
  let dp = function (num) {
    // 确定base case
    if (num == 0) return 0;
    if (num < 1) return -1;
    let res = num;
    for (coin of coins) {
      // 确定状态
      let subProblem = dp(num - coin);
      if (subProblem === -1) continue;
      // 确定 选择
      res = Math.min(res, 1 + subProblem);
    }
    return res;
  };
  return dp(amount);
};
console.log(coinChange([1, 3, 5], 11));

// 带备忘录的

let coinChange = function (coins, amount) {
  let memo = [];
  let dp = function (num) {
    // 查备忘录 避免重复计算
    if (memo[n]) return memo[n];
    // 确定base case
    if (num == 0) return 0;
    if (num < 1) return -1;
    let res = num;
    for (coin of coins) {
      // 确定状态
      let subProblem = dp(num - coin);
      if (subProblem === -1) continue;
      // 确定 选择
      res = Math.min(res, 1 + subProblem);
    }
    // 记入备忘录中
    memo[num] = res;
    return memo[num];
  };
  return dp(amount);
};
console.log(coinChange([1, 3, 5], 11));

DP table dp 数组的定义: 当目标金额为 i 时,至少需要 dp[i] 枚硬币凑出;

let coinChange = function (coins, amount) {
  let dp = function (num) {
    // 确定base case
    dp[0] == 0;
    let dp = Array.from(num);
    for (let i = 0; i < dp.length; i++) {
      for (coin of coins) {
        // 确定状态
        if (i - coin < 0) continue;
        dp[i] = Math.min(dp(i), dp[num - coin]);
      }
    }
  };
  return dp[amount] === amount + 1 ? -1 : dp[amount];
};
console.log(coinChange([1, 3, 5], 11));

回溯算法解题套路框架

解决一个回溯问题, 实际上就是决策树的遍历过程

  1. 路径: 也就是已经做出的选择

  2. 选择列表: 也就是你当前可以做的选择

  3. 结束条件: 也就是到达决策树底层,无法在做选择的条件

1.3 回溯的算法框架 result = []; def backtrack(路径, 选择列表): if 满足结束条件: result.add(路径) return for 选择 in 选择列表: 做选择 backtrack(路径, 选择列表) 撤销选择

其核心就是 for 循环里面的递归,在递归调用之前『做选择』, 在递归调用之后『撤销选择』

// 全排列

我们定义的 backtrack 函数其实就像一个指针,在这颗树上遍历,同时要正确维护每个节点的属性,每当走到树的底层,其『路径』就是一个全排列

// 遍历 前序遍历的代码在进入某一个节点之前的那个时间点执行,后序遍历的代码在离开某个节点之后的那个时间点执行

我们需要在递归之前做出选择,在递归之后撤销刚才的选择

这样是回溯算法的一个特点,不像动态规划的存在重叠子问题可以优化,回溯算法就是纯暴力穷举,复杂度一般都很高。

// 主函数,输入一组不重复的数字,返回它们的全排列
function permutation(arr) {
  var result = [];
  if (arr.length === 0) {
    return result;
  }
  var temp = [];
  backtrack(arr, temp, result);
  return result;
}
// 全排列的核心函数

// 路径:记录track中
// 选择列表: nums中不存在于track'的那些元素
// 结束条件: nums 中的元素全都在track中出现
function backtrack(nums, track, result) {
  // 触发结束条件
  if (track.length === nums.length) {
    result.push(track);
    return;
  }

  for (let i = 0; i < nums.length; i++) {
    // 排除不合法的选择
    if (track.indexOf(nums[i]) !== -1) continue;
    // 做选择
    track.push(nums[i]);
    // 进入下一层决策树
    backtrack(nums, track);
    // 取消选择
    track.pop();
  }
}

写 backtrack 函数时,需要维护走过的『路径』和当前可以做的『选择列表』,当触发『结束条件』时,将『路径』记入结果集。

回溯算法: 走过的『路径』、当前的『选择列表』和『结束条件』; 动态规划: 『状态』、『选择』、『base case』;

1.4 BFS 算法框架 BFS(broad first search) ,广度优先搜索和 DFS(深度优先搜索)

BFS 算法框架套路

问题的本质就是让你在一副『图』中找到起点 start 和终点 target 的最近距离

队列需要回头,visited 的主要作用就是防止走回头路,大部分都是必需的,但是像一般的二叉树结构,没有子节点到父节点的指针,不会走回头路就不需要 visited。

寻找二叉树最小节点

function minDepth(Q) {
  if (root == null) return 0;
  let depth = 1;
  let size = q.size();
  while (!q.isEmpty()) {
    for (let i = 0; i < size; i++) {
      let node = q.dequeue();
      if (node.left == null && node.right == null) {
        return depth;
      }
      if (node.left != null) {
        q.enqueue(node.left);
      }
      if (node.right != null) {
        q.enqueue(node.right);
      }
    }
    depth++;
  }
}

形象点说,DFS 是线,BFS 是面;DFS 是单打独斗,BFS 是集体行动。

既然 BFS 这么好,为什么要用 DFS? 一般来说在寻找最短路径的时候使用 BFS,其他时候用 DFS 多一些。

双指针技巧套路框架

双指针技巧分为两类:一类是『快、慢』指针, 一类是『左右指针』 快慢指针:主要解决链表的问题,比如典型的判定链表中是否存在包含环;后者主要解决数组(或者字符串)中的问题,比如二分搜索

1.XUNZ

function hasCycle(head) {
  // 初始化快、慢指针指向头节点
  fast = slow = head;
  while (fast != null && fast.next != null) {
    // 慢指针每次走一步
    slow = slow.next;
    // 快指针每次前进两步
    fast = fast.next.next;
    if (slow == fast) {
      return true;
    }
  }
  return false;
}

2.寻找这个环的起始位置

function detectCycle(head) {
  // 初始化快、慢指针指向头节点
  fast = slow = head;
  while (fast != null && fast.next != null) {
    // 慢指针每次走一步
    slow = slow.next;
    // 快指针每次前进两步
    fast = fast.next.next;
    if (slow == fast) {
      return true;
    }
  }
  slow = head;
  while (slow != fast) {
    // 两个指针以相同的速度前进
    fast = fast.next;
    slow = slow.next;
  }
  // 两个指针相遇的那个单链表节点就是环的起点
  return slow;
}

3.寻找无环单链表的中点

while (fast != null && fast.next != null) {
  fast = fast.next.next;
  slow = slow.nextl;
}
return slow;
  1. 寻找单链表的倒数第 K 个元素

while (k-- > 0) {
  fast = fast.next;
}
while (fast != null) {
  slow = slow.next;
  fast = fast.next;
}
return slow;

左右指针的常用算法

左右指针一般运用在数组问题上,实际上是指两个索引值,一般初始化为 left = 0,right = len(nums) - 1

1.二分搜索

// 二分搜索
    function binarySearch(){
        // 左、右指针在数组的两端初始化
        var left = 0;
        var right = nums.length - 1;
        while(left <= right){
            var mid = Math.floor((left + right) / 2);
            if(nums[mid] == target){
                return mid;
            }
            if(nums[mid] < target){
                left = mid + 1;
            }else{
                right = mid - 1;
            }
        }
        return -1
    }

为什么 while 的循环的条件是<=,而不是<? 因为初始化 right 的时候,nums.length - 1,即最后一个元素的索引,而不是 nums.length

nums.length -1 :相当于左闭右开[left, right),因为索引大小为 nums.length 是越界的。 nums.length: 相当于两端都闭区间[left, right]

理解下左闭右开的概念:

开闭区间是一个数学概念,开区间使用符号小括号()表示,闭区间使用符号中括号[]表示,闭区间包含了两个端点,而开区间则不包含两个端点

一共四种情况: (a,b):区间范围内,不包含 a 和 b [a,b]:区间范围内,包含 a,也包含 b (a,b]:区间范围内,不包含 a,包含 b [a,b):区间范围内,包含 a,不包含 b

2.两数之和

只要数组有序,就应该想到双指针技巧

function twoSum(nums, target) {
  let left = 0;
  let right = nums.length - 1;
  while (left < right) {
    let sum = nums[left] + nums[right];
    if (sum == target) {
      //题目要求索引从1开始的
      return [left + 1, right + 1];
    } else if (sum < target) {
      left++; //让sum大一点
    } else {
      right--; // 让sum小一点
    }
  }
  return [-1, -1];
}

3.反转数组

function reverseArray(nums) {
  let left = 0;
  let right = nums.length - 1;
  while (left < right) {
    let temp = nums[left];
    nums[left] = nums[right];
    nums[right] = temp;
    left++;
    right--;
  }
  return nums;
}

4.滑动窗口算法

1.6 二分搜索框架

let binarySearch(){
    let left = 0; right = ...;
    while(...){
        let mid = left + (right - left) / 2;
        if(nums[mid] == target){

        } else if(nums[mid] < target)
            left = ...
        else if(nums[mid] > target){
            right = ...
        }
    }
    return ...
}

分析二分搜索的一个技巧是: 不要出现 else, 而是把所有情况用 else if 写清楚,这样可以清楚展现所有细节。 js 中找 mid 的 有以下几种形式

    var point = Math.ceil(arr.length / 2);
    let mid = Math.round((leftIndex + rightIndex) / 2);
    let mid = left + (right -left) / 2  // 解决 left 和 right 太大 溢出
  1. 寻找一个数(基本的二分搜索)

  2. 寻找左侧边界的二分搜索

搜索左、右边界的二分搜索算法和常规二分搜索算法的区别。让搜索区间变成左闭右开

模板总结:

  1. 分析二分搜索代码,不要出现 else,全部展开改成 else if,方便理解。

  2. 主义『搜索区间』和 while 的终止条件,搞清楚『搜索区间』的开闭情况非常重要,left 和 right 的更新完全取决与『搜索区间』,如果存在漏掉的元素,记得在最后检查。

  3. 若需要定义左闭右开的『搜索区间』搜索左、右边界,只要在 nums【mid】==target 时做修改即可,搜索右侧边界时需要减一。

  4. 如果将『搜索区间』全都统一成两端都闭,好记,只要稍微改 nums[mid]==target 条件处的代码和函数返回的代码逻辑即可。

滑动窗口算法框架

function slidingWindow(s, t) {
  var left = 0;
  right = 0;
  var valid = 0;
  while (right < s.length) {
    if (s[right] == t) {
      valid++;
    }
    // 右移窗口
    right++;
    // 进行窗口内数据的一系列更新
    //...
    if (valid > 0) {
      valid--;
    }
    // 判断左侧窗口是否要收缩
    while (window < s.length && valid < 0) {
      if (s[left] == t) {
        valid++;
      }
      left++;
      // ...
    }
  }
}

首先,初始化 window 和 needs 两个哈希表,记录窗口中的字符和需要凑齐的字符:

function minWindow(s, t) {
   var needs = {}; // 需要凑齐的字符
   var window = {}; //窗口中字符
   for(let a of t){
       //统计需要的字符
       needs[a] = (needs[a] || 0) + 1;
   }
   var left = 0; right = 0, valid = 0;
   // 最小覆盖子串的起始索引及长度
   var start = 0, min =  Number.MAX_VALUE;
   while(right < s.length){
       // 即将移入窗口的字符
       var c = s[right];
       // 其中valid变量表示窗口中满足needs条件的字符个数,如果valid和needs.length的大小相同,则说明窗口以满足条件,已经完全覆盖子串
       right++;
       if(needs[c]){
           // 当前字符在需要的字符中,则更新当前窗口统计
           window[c] = (window[c] || 0) + 1;
           if(window[c] == needs[c]){
               // 当前窗口和需要的字符匹配时,验证数量增加1
               valid++;
           }

       }
       // 判断左侧窗口是否要收缩,当验证数量与需要的字符个数一直时,就应该收缩窗口了
       while(valid == Object.keys(needs).length){
           // 更新最小覆盖子串
           if(right - left < min){
               start = left;
               min = right - left;
           }
           // d是将移出窗口的字符
           var d = s[left];
           left++;
           //进行窗口内数据的一系列更新
           if(needs[d]){
               if(window[d] == needs[d]){
                   valid--;
               }
               window[d]--;
           }
       }
   }
   //返回最小覆盖子串
   return min == Number.MAX_VALUE ? "" : s.substr(start, min);
}

套用模板:

  1. 当移动 right 扩大窗口,即加入字符时,应该更新哪些数据? 2.什么条件下,窗口应该暂停扩大,开始移动 left 缩小窗口? 3.当移动 left 缩小窗口,即移除字符时,应该更新哪些数据? 4.我们要的结果应该在扩大窗口时还是缩小窗口时进行更新?

最后更新于

这有帮助吗?