关于算法:面试必问leetcode高频题精选

算法始终是大厂前端面试常问的一块，而大家往往筹备这方面的面试都是通过 leetcode 刷题。

我顺便整顿了几道 leetcode 中「很有意思 」而且十分「 高频」的算法题目，别离给出了思路剖析（带图解）和代码实现。

认真仔细的浏览完本文，置信对于你在算法方面的面试肯定会有不小的帮忙！????

题目难度easy，波及到的算法常识有数组、哈希表

给定一个整数数组 nums 和一个目标值 target，请你在该数组中找出和为目标值的那 两个 整数，并返回他们的数组下标。

你能够假如每种输出只会对应一个答案。然而，数组中同一个元素不能应用两遍。

示例：

给定 nums = [2, 7, 11, 15], target = 9

因为 nums[0] + nums[1] = 2 + 7 = 9
所以返回 [0, 1]

大多数同学看到这道题目，心中必定会想：这道题目太简略了，不就两层遍历嘛：两层循环来遍历同一个数组；第一层循环遍历的值记为 a，第二层循环时遍历的值记为b；若a+b = 目标值，那么a 和b对应的数组下标就是咱们想要的答案。

这种解法没故障，但有没有优化的计划呢？????

要晓得两层循环很多状况下都意味着O(n^2) 的复杂度，这个复杂度非常容易导致你的算法超时。即使没有超时，在明明有一层遍历解法的状况下，你写了两层遍历，面试官也会对你的印象分大打折扣。????

其实咱们能够在遍历数组的过程中，减少一个 Map 构造来存储曾经遍历过的数字及其对应的索引值。而后每遍历到一个新数字的时候，都回到 Map 里去查问 targetNum 与该数的差值是否曾经在后面的数字中呈现过了。若呈现过，那么答案未然浮现，咱们就不用再往下走了。

咱们就以本题中的例子联合图片来阐明一下下面提到的这种思路：

这里用对象 diffs 来模仿 map 构造：

首先遍历数组第一个元素，此时 key 为 2，value为索引 0
往下遍历，遇到了 7:

计算 targetNum 和 7 的差值为 2，去 diffs 中检索 2 这个key，发现是之前呈现过的值。那么本题的答案就进去了！

/**
 * @param {number[]} nums
 * @param {number} target
 * @return {number[]}
 */
const twoSum = function (nums, target) {const diffs = {};
  // 缓存数组长度
  const len = nums.length;
  // 遍历数组
  for (let i = 0; i < len; i++) {
    // 判断以后值对应的 target 差值是否存在
    if (diffs[target - nums[i]] !== undefined) {
      // 若有对应差值，那么失去答案
      return [diffs[target - nums[i]], i];
    }
    // 若没有对应差值，则记录以后值
    diffs[nums[i]] = i;
  }
};

题目难度medium，波及到的算法常识有数组、双指针

给你一个蕴含 n 个整数的数组 nums，判断nums 中是否存在三个元素a，b，c，使得a + b + c = 0。请你找出所有满足条件且不反复的三元组。

留神：答案中不能够蕴含反复的三元组。

示例：

给定数组 nums = [-1, 0, 1, 2, -1, -4]，满足要求的三元组汇合为：[[-1, 0, 1],
  [-1, -1, 2]
]

和下面的 两数之和 一样，如果不认真思考，最快的形式可能就是多层遍历了。但有了前事不忘; 后事之师，咱们同样能够把求和问题变为求差问题：固定其中一个数，在剩下的数中寻找是否有两个数的和这个固定数相加是等于 0 的。

这里咱们采纳 双指针法 来解决问题，相比三层循环，效率会大大晋升。

双指针法的适用范围比拟广，个别像求和、比大小的都能够用它来解决。然而有一个前提：数组必须有序

因而咱们的第一步就是先将数组进行排序：

// 给 nums 排序
nums = nums.sort((a, b) => {return a - b;});

而后对数组进行遍历，每遍历到哪个数字，就固定以后的数字。同时左指针指向该数字前面的紧邻的那个数字，右指针指向数组开端。而后左右指针别离向两头聚拢：

每次指针挪动一次地位，就计算一下两个指针指向数字之和加上固定的那个数之后，是否等于 0。如果是，那么咱们就失去了一个指标组合；否则，分两种状况来看：

相加之和大于 0，阐明右侧的数偏大了，右指针左移
相加之和小于 0，阐明左侧的数偏小了，左指针右移

/**
 * @param {number[]} nums
 * @return {number[][]}
 */
const threeSum = function (nums) {
  // 用于寄存后果数组
  let res = [];
  // 目标值为 0
  let sum = 0;
  // 给 nums 排序
  nums = nums.sort((a, b) => {return a - b;});
  // 缓存数组长度
  const len = nums.length;
  for (let i = 0; i < len - 2; i++) {
    // 左指针 j
    let j = i + 1;
    // 右指针 k
    let k = len - 1;
    // 如果遇到反复的数字，则跳过
    if (i > 0 && nums[i] === nums[i - 1]) {continue;}
    while (j < k) {
      // 三数之和小于 0，左指针后退
      if (nums[i] + nums[j] + nums[k] < 0) {
        j++;
        // 解决左指针元素反复的状况
        while (j < k && nums[j] === nums[j - 1]) {j++;}
      } else if (nums[i] + nums[j] + nums[k] > 0) {
        // 三数之和大于 0，右指针后退
        k--;

        // 解决右指针元素反复的状况
        while (j < k && nums[k] === nums[k + 1]) {k--;}
      } else {
        // 失去指标数字组合，推入后果数组
        res.push([nums[i], nums[j], nums[k]]);

        // 左右指针一起后退
        j++;
        k--;

        // 若左指针元素反复，跳过
        while (j < k && nums[j] === nums[j - 1]) {j++;}

        // 若右指针元素反复，跳过
        while (j < k && nums[k] === nums[k + 1]) {k--;}
      }
    }
  }

  // 返回后果数组
  return res;
};

题目难度medium，波及到的算法常识有数组、双指针

给你 n 个非负整数 a1，a2，…，an，每个数代表坐标中的一个点 (i, ai)。在坐标内画 n 条垂直线，垂直线 i 的两个端点别离为 (i, ai) 和 (i, 0)。找出其中的两条线，使得它们与 x 轴独特形成的容器能够包容最多的水。

阐明：你不能歪斜容器，且 n 的值至多为 2。

图中垂直线代表输出数组[1,8,6,2,5,4,8,3,7]。在此状况下，容器可能包容水（示意为蓝色局部）的最大值为 49。

示例：

输出：[1,8,6,2,5,4,8,3,7]
输入：49

首先，咱们能疾速想到的一种办法：两两进行求解，计算能够承载的水量。而后不断更新最大值，最初返回最大值即可。

这种解法，须要两层循环，工夫复杂度是 O(n^2)。这种相对来说比拟暴力，对应就是 暴力法。

/**
 * @param {number[]} height
 * @return {number}
 */
var maxArea = function (height) {
  let max = 0;
  for (let i = 0; i < height.length - 1; i++) {for (let j = i + 1; j < height.length; j++) {let area = (j - i) * Math.min(height[i], height[j]);
      max = Math.max(max, area);
    }
  }

  return max;
};

那么有没有更好的方法呢？答案是必定有。

其实有点相似 双指针 的概念，左指针指向下标 0，右指针指向length-1。而后别离从左右两侧向两头挪动，每次取小的那个值（因为水的高度肯定是以小的那个为准）。

如果左侧小于右侧，则 i++，否则j--（这一步其实就是取所有高度中比拟高的，咱们晓得面积等于 长 * 宽 ）。对应就是 双指针动静滑窗

/**
 * @param {number[]} height
 * @return {number}
 */
var maxArea = function (height) {
  let max = 0;
  let i = 0;
  let j = height.length - 1;
  while (i < j) {let minHeight = Math.min(height[i], height[j]);
    let area = (j - i) * minHeight;
    max = Math.max(max, area);
    if (height[i] < height[j]) {i++;} else {j--;}
  }
  return max;
};

题目难度easy，波及到的算法常识有斐波那契数列、动静布局。

假如你正在爬楼梯。须要 n 阶你能力达到楼顶。

每次你能够爬 1 或 2 个台阶。你有多少种不同的办法能够爬到楼顶呢？

留神：给定 n 是一个正整数。

示例 1：

输出：2
输入：2
解释：有两种办法能够爬到楼顶。1.  1 阶 + 1 阶
2.  2 阶

示例 2：

输出：3
输入：3
解释：有三种办法能够爬到楼顶。1.  1 阶 + 1 阶 + 1 阶
2.  1 阶 + 2 阶
3.  2 阶 + 1 阶

这道题目是一道十分高频的面试题目，也是一道十分经典的 斐波那契数列 类型的题目。

解决本道题目咱们会用到动静布局的算法思维 - 能够分成多个子问题，爬第 n 阶楼梯的办法数量，等于 2 局部之和：

爬上 n−1 阶楼梯的办法数量。因为再爬 1 阶就能到第 n 阶
爬上 n−2 阶楼梯的办法数量，因为再爬 2 阶就能到第 n 阶

能够失去公式：

climbs[n] = climbs[n - 1] + climbs[n - 2];

同时须要做如下初始化：

climbs[0] = 1;
climbs[1] = 1;

/**
 * @param {number} n
 * @return {number}
 */
var climbStairs = function (n) {let climbs = [];
  climbs[0] = 1;
  climbs[1] = 1;
  for (let i = 2; i <= n; i++) {climbs[i] = climbs[i - 1] + climbs[i - 2];
  }
  return climbs[n];
};

题目难度easy，波及到的算法常识有链表、快慢指针。

给定一个链表，判断链表中是否有环。

为了示意给定链表中的环，咱们应用整数 pos 来示意链表尾连贯到链表中的地位（索引从 0 开始）。如果 pos 是 -1，则在该链表中没有环。

示例 1：

输出：head = [3,2,0,-4], pos = 1
输入：true
解释：链表中有一个环，其尾部连贯到第二个节点。

示例 2：

输出：head = [1,2], pos = 0
输入：true
解释：链表中有一个环，其尾部连贯到第一个节点。

示例 3：

输出：head = [1], pos = -1
输入：false
解释：链表中没有环。

链表成环 问题也是十分经典的算法问题，在面试中也常常会遇到。

解决这种问题个别有常见的两种办法：标记法 和快慢指针法。

给每个已遍历过的节点加标记位，遍历链表，当呈现下一个节点已被标记时，则证实单链表有环。

/**
 * Definition for singly-linked list.
 * function ListNode(val) {
 *     this.val = val;
 *     this.next = null;
 * }
 */

/**
 * @param {ListNode} head
 * @return {boolean}
 */
var hasCycle = function (head) {while (head) {if (head.flag) return true;
    head.flag = true;
    head = head.next;
  }
  return false;
};

设置快慢两个指针，遍历单链表，快指针一次走两步，慢指针一次走一步，如果单链表中存在环，则快慢指针终会指向同一个节点，否则直到快指针指向 null 时，快慢指针都不可能相遇。

/**
 * Definition for singly-linked list.
 * function ListNode(val) {
 *     this.val = val;
 *     this.next = null;
 * }
 */

/**
 * @param {ListNode} head
 * @return {boolean}
 */
var hasCycle = function (head) {if (!head || !head.next) {return false;}
  let slow = head,
    fast = head.next;
  while (slow !== fast) {if (!fast || !fast.next) return false;
    fast = fast.next.next;
    slow = slow.next;
  }
  return true;
};

题目难度easy，波及到的算法常识有栈、哈希表。

给定一个只包含'('，')'，'{'，'}'，'['，']' 的字符串，判断字符串是否无效。

无效字符串需满足：

1、左括号必须用雷同类型的右括号闭合。
2、左括号必须以正确的程序闭合。

留神空字符串可被认为是无效字符串。

示例 1:

输出: "()";
输入: true;

示例 2:

输出: "()[]{}";
输入: true;

示例 3:

输出: "(]";
输入: false;

示例 4:

输出: "([)]";
输入: false;

示例 5:

输出: "{[]}";
输入: true;

这道题能够利用 栈构造。

思路大略是：遇到左括号，一律推入栈中，遇到右括号，将栈顶部元素拿出，如果不匹配则返回 false，如果匹配则持续循环。

第一种解法是利用switch case。

`switch case`

/**
 * @param {string} s
 * @return {boolean}
 */
var isValid = function (s) {let arr = [];
  let len = s.length;
  if (len % 2 !== 0) return false;
  for (let i = 0; i < len; i++) {let letter = s[i];
    switch (letter) {
      case "(": {arr.push(letter);
        break;
      }
      case "{": {arr.push(letter);
        break;
      }
      case "[": {arr.push(letter);
        break;
      }
      case ")": {if (arr.pop() !== "(") return false;
        break;
      }
      case "}": {if (arr.pop() !== "{") return false;
        break;
      }
      case "]": {if (arr.pop() !== "[") return false;
        break;
      }
    }
  }
  return !arr.length;
};

第二种是保护一个 map 对象：

哈希表`map`

/**
 * @param {string} s
 * @return {boolean}
 */
var isValid = function (s) {
  let map = {"(": ")",
    "{": "}",
    "[": "]",
  };
  let stack = [];
  let len = s.length;
  if (len % 2 !== 0) return false;
  for (let i of s) {if (i in map) {stack.push(i);
    } else {if (i !== map[stack.pop()]) return false;
    }
  }
  return !stack.length;
};

题目难度hard，波及到的算法常识有双端队列。

给定一个数组 nums，有一个大小为 k 的滑动窗口从数组的最左侧挪动到数组的最右侧。你只能够看到在滑动窗口内的 k 个数字。滑动窗口每次只向右挪动一位。

返回滑动窗口中的最大值。

进阶：你能在线性工夫复杂度内解决此题吗？

示例:

输出: 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

提醒：

1 <= nums.length <= 10^5
-10^4 <= nums[i] <= 10^4
1 <= k <= nums.length

第一种办法，比较简单。也是大多数同学很快就能想到的办法。

遍历数组
顺次遍历每个区间内的最大值，放入数组中

/**
 * @param {number[]} nums
 * @param {number} k
 * @return {number[]}
 */
var maxSlidingWindow = function (nums, k) {
  let len = nums.length;
  if (len === 0) return [];
  if (k === 1) return nums;
  let resArr = [];
  for (let i = 0; i <= len - k; i++) {
    let max = Number.MIN_SAFE_INTEGER;
    for (let j = i; j < i + k; j++) {max = Math.max(max, nums[j]);
    }
    resArr.push(max);
  }
  return resArr;
};

这道题还能够用双端队列去解决，外围在于在窗口产生挪动时，只依据发生变化的元素对最大值进行更新。

联合下面动图 (图片起源) 咱们梳理下思路：

查看队尾元素，看是不是都满足大于等于以后元素的条件。如果是的话，间接将以后元素入队。否则，将队尾元素一一出队、直到队尾元素大于等于以后元素为止。（这一步是为了维持队列的递减性：确保队头元素是以后滑动窗口的最大值。这样咱们每次取最大值时，间接取队头元素即可。）
将以后元素入队
查看队头元素，看队头元素是否曾经被排除在滑动窗口的范畴之外了。如果是，则将队头元素出队。（这一步是维持队列的有效性：确保队列里所有的元素都在滑动窗口圈定的范畴以内。）
排除掉滑动窗口还没有初始化实现、第一个最大值还没有呈现的非凡状况。

/**
 * @param {number[]} nums
 * @param {number} k
 * @return {number[]}
 */
var maxSlidingWindow = function (nums, k) {
  // 缓存数组的长度
  const len = nums.length;
  const res = [];
  const deque = [];
  for (let i = 0; i < len; i++) {
    // 队尾元素小于以后元素
    while (deque.length && nums[deque[deque.length - 1]] < nums[i]) {deque.pop();
    }
    deque.push(i);

    // 当队头元素的索引曾经被排除在滑动窗口之外时
    while (deque.length && deque[0] <= i - k) {
      // 队头元素出对
      deque.shift();}
    if (i >= k - 1) {res.push(nums[deque[0]]);
    }
  }
  return res;
};

题目难度medium，波及到的算法常识有栈。

依据每日气温列表，请从新生成一个列表，对应地位的输入是须要再期待多久温度才会升高超过该日的天数。如果之后都不会升高，请在该地位用 0 来代替。

例如，给定一个列表 temperatures = [73, 74, 75, 71, 69, 72, 76, 73]，你的输入应该是 [1, 1, 4, 2, 1, 1, 0, 0]。

提醒：气温列表长度的范畴是 [1, 30000]。每个气温的值的均为华氏度，都是在 [30, 100] 范畴内的整数。

看到这道题，大家很容易就会想到暴力遍历法：间接两层遍历，第一层定位一个温度，第二层定位离这个温度最近的一次升温是哪天，而后求出两个温度对应索引的差值即可。

然而这种解法须要两层遍历，工夫复杂度是O(n^2)，显然不是最优解法。

本道题目能够采纳栈去做一个优化。

大略思路就是：保护一个递加栈。当遍历过的温度，维持的是一个枯燥递加的态势时，咱们就对这些温度的索引下标执行入栈操作；只有呈现了一个数字，它突破了这种枯燥递加的趋势，也就是说它比前一个温度值高，这时咱们就对前后两个温度的索引下标求差，得出前一个温度间隔第一次升温的指标差值。

/**
 * @param {number[]} T
 * @return {number[]}
 */
var dailyTemperatures = function (T) {
  const len = T.length;
  const stack = [];
  const res = new Array(len).fill(0);
  for (let i = 0; i < len; i++) {while (stack.length && T[i] > T[stack[stack.length - 1]]) {const top = stack.pop();
      res[top] = i - top;
    }
    stack.push(i);
  }
  return res;
};

题目难度medium，波及到的算法常识有递归、回溯。

数字 n 代表生成括号的对数，请你设计一个函数，用于可能生成所有可能的并且无效的括号组合。

示例：

输出：n = 3
输入：["((()))",
       "(()())",
       "(())()",
       "()(())",
       "()()()"]

这道题目通过递归去实现。

因为左右括号须要匹配、闭合。所以对应“(”和“)”的数量都是n，当满足这个条件时，一次递归就完结，将对应值放入后果数组中。

这里有一个潜在的限度条件：无效的 括号组合。对应逻辑就是在往每个地位去放入“(”或“)”前：

须要判断“(”的数量是否小于 n
“)”的数量是否小于“(”

/**
 * @param {number} n
 * @return {string[]}
 */
var generateParenthesis = function (n) {let res = [];
  const generate = (cur, left, right) => {if (left === n && right === n) {res.push(cur);
      return;
    }
    if (left < n) {generate(cur + "(", left + 1, right);
    }
    if (right < left) {generate(cur + ")", left, right + 1);
    }
  };
  generate("", 0, 0);
  return res;
};

题目难度medium，波及到的算法常识有递归、回溯。

给定一个仅蕴含数字 2-9 的字符串，返回所有它能示意的字母组合。

给出数字到字母的映射如下（与电话按键雷同）。留神 1 不对应任何字母。

示例:

输出："23"
输入：["ad", "ae", "af", "bd", "be", "bf", "cd", "ce", "cf"].

首先用一个对象 map 存储数字与字母的映射关系，接下来遍历对应的字符串，第一次将字符串存在后果数组 result 中，第二次及当前的就双层遍历生成新的字符串数组。

/**
 * @param {string} digits
 * @return {string[]}
 */
var letterCombinations = function (digits) {let res = [];
  if (digits.length === 0) return [];
  let map = {
    2: "abc",
    3: "def",
    4: "ghi",
    5: "jkl",
    6: "mno",
    7: "pqrs",
    8: "tuv",
    9: "wxyz",
  };
  for (let num of digits) {let chars = map[num];
    if (res.length > 0) {let temp = [];
      for (let char of chars) {for (let oldStr of res) {temp.push(oldStr + char);
        }
      }
      res = temp;
    } else {res.push(...chars);
    }
  }
  return res;
};

/**
 * @param {string} digits
 * @return {string[]}
 */
var letterCombinations = function (digits) {let res = [];
  if (!digits) return [];
  let map = {
    2: "abc",
    3: "def",
    4: "ghi",
    5: "jkl",
    6: "mno",
    7: "pqrs",
    8: "tuv",
    9: "wxyz",
  };
  function generate(i, str) {
    let len = digits.length;
    if (i === len) {res.push(str);
      return;
    }
    let chars = map[digits[i]];
    for (let j = 0; j < chars.length; j++) {generate(i + 1, str + chars[j]);
    }
  }
  generate(0, "");
  return res;
};

题目难度medium，波及到的算法常识有 DFS（深度优先搜寻）。

给你一个由 ‘1’（海洋）和 ‘0’（水）组成的的二维网格，请你计算网格中岛屿的数量。

岛屿总是被水突围，并且每座岛屿只能由程度方向或竖直方向上相邻的海洋连贯造成。

此外，你能够假如该网格的四条边均被水突围。

示例 1:

输出: 11110;
11010;
11000;
00000;
输入: 1;

示例 2:

输出:
11000
11000
00100
00011
输入: 3
解释: 每座岛屿只能由程度和 / 或竖直方向上相邻的海洋连贯而成。

如上图，咱们须要计算的就是图中相连（只能是程度和 / 或竖直方向上相邻）的绿色岛屿的数量。

这道题目一个经典的做法是 沉岛，大抵思路是：采纳DFS（深度优先搜寻），遇到 1 的就将以后的 1 变为 0，并将以后坐标的上下左右都执行 dfs，并计数。

终止条件是：超出二维数组的边界或者是遇到 0，间接返回。

/**
 * @param {character[][]} grid
 * @return {number}
 */
var numIslands = function (grid) {
  const rows = grid.length;
  if (rows === 0) return 0;
  const cols = grid[0].length;
  let res = 0;
  for (let i = 0; i < rows; i++) {for (let j = 0; j < cols; j++) {if (grid[i][j] === "1") {helper(grid, i, j, rows, cols);
        res++;
      }
    }
  }
  return res;
};
function helper(grid, i, j, rows, cols) {if (i < 0 || j < 0 || i > rows - 1 || j > cols - 1 || grid[i][j] === "0")
    return;

  grid[i][j] = "0";

  helper(grid, i + 1, j, rows, cols);
  helper(grid, i, j + 1, rows, cols);
  helper(grid, i - 1, j, rows, cols);
  helper(grid, i, j - 1, rows, cols);
}

题目难度easy，波及到的算法常识有贪婪算法。

假如你是一位很棒的家长，想要给你的孩子们一些小饼干。然而，每个孩子最多只能给一块饼干。对每个孩子 i，都有一个胃口值 gi，这是能让孩子们满足胃口的饼干的最小尺寸；并且每块饼干 j，都有一个尺寸 sj。如果 sj >= gi，咱们能够将这个饼干 j 调配给孩子 i，这个孩子会失去满足。你的指标是尽可能满足越多数量的孩子，并输入这个最大数值。

留神：

你能够假如胃口值为正。
一个小朋友最多只能领有一块饼干。

示例 1:

输出: [1,2,3], [1,1]

输入: 1

解释:
你有三个孩子和两块小饼干，3 个孩子的胃口值别离是：1,2,3。尽管你有两块小饼干，因为他们的尺寸都是 1，你只能让胃口值是 1 的孩子满足。所以你应该输入 1。

示例 2:

输出: [1,2], [1,2,3]

输入: 2

解释:
你有两个孩子和三块小饼干，2 个孩子的胃口值别离是 1,2。你领有的饼干数量和尺寸都足以让所有孩子满足。所以你应该输入 2.

这道题目是一道典型的 贪婪算法 类。解题思路大略如下：

优先满足胃口小的小朋友的需要
设最大可满足的孩子数量为maxNum = 0
胃口小的拿小的，胃口大的拿大的
两边升序，而后一一比照
- 当 饼干 j >= 胃口 i 时，i++、j++、maxNum++
- 当 饼干 j < 胃口 i 时，阐明饼干不够吃，换更大的，j++
到边界后进行

/**
 * @param {number[]} g
 * @param {number[]} s
 * @return {number}
 */
var findContentChildren = function (g, s) {g = g.sort((a, b) => a - b);
  s = s.sort((a, b) => a - b);
  let gLen = g.length,
    sLen = s.length,
    i = 0,
    j = 0,
    maxNum = 0;
  while (i < gLen && j < sLen) {if (s[j] >= g[i]) {
      i++;
      maxNum++;
    }
    j++;
  }
  return maxNum;
};

题目难度easy，波及到的算法常识有动静布局、贪婪算法。

给定一个数组，它的第 i 个元素是一支给定股票第 i 天的价格。

设计一个算法来计算你所能获取的最大利润。你能够尽可能地实现更多的交易（屡次交易一支股票）。

留神：你不能同时参加多笔交易（你必须在再次购买前发售掉之前的股票）。

示例 1:

输出: [7,1,5,3,6,4]
输入: 7
解释: 在第 2 天（股票价格 = 1）的时候买入，在第 3 天（股票价格 = 5）的时候卖出, 这笔交易所能取得利润 = 5-1 = 4。随后，在第 4 天（股票价格 = 3）的时候买入，在第 5 天（股票价格 = 6）的时候卖出, 这笔交易所能取得利润 = 6-3 = 3。

示例 2:

输出: [1,2,3,4,5]
输入: 4
解释: 在第 1 天（股票价格 = 1）的时候买入，在第 5 天（股票价格 = 5）的时候卖出, 这笔交易所能取得利润 = 5-1 = 4。留神你不能在第 1 天和第 2 天接连购买股票，之后再将它们卖出。因为这样属于同时参加了多笔交易，你必须在再次购买前发售掉之前的股票。

示例 3:

输出: [7,6,4,3,1]
输入: 0
解释: 在这种状况下, 没有交易实现, 所以最大利润为 0。

提醒：

1 <= prices.length <= 3 * 10 ^ 4
0 <= prices[i] <= 10 ^ 4

其实这道题目思路也比较简单：

保护一个变量 profit 用来存储利润
因为能够屡次交易，那么就要前面的价格比后面的大，那么就能够进行交易
因而，只有prices[i+1] > prices[i]，那么就去叠加profit
遍历实现失去的 profit 就是获取的最大利润

/**
 * @param {number[]} prices
 * @return {number}
 */
var maxProfit = function (prices) {
  let profit = 0;
  for (let i = 0; i < prices.length - 1; i++) {if (prices[i + 1] > prices[i]) profit += prices[i + 1] - prices[i];
  }
  return profit;
};

题目难度medium，波及到的算法常识有动静布局。

一个机器人位于一个 m x n 网格的左上角（起始点在下图中标记为“Start”）。

机器人每次只能向下或者向右挪动一步。机器人试图达到网格的右下角（在下图中标记为“Finish”）。

问总共有多少条不同的门路？

例如，上图是一个 7 x 3 的网格。有多少可能的门路？

示例 1:

输出: m = 3, n = 2
输入: 3
解释:
从左上角开始，总共有 3 条门路能够达到右下角。1. 向右 -> 向右 -> 向下
2. 向右 -> 向下 -> 向右
3. 向下 -> 向右 -> 向右

示例 2:

输出: (m = 7), (n = 3);
输入: 28;

由题可知：机器人只能向右或向下挪动一步，那么从左上角到右下角的走法 = 从左边开始走的门路总数 + 从下边开始走的门路总数。

所以可推出动静方程为：dp[i][j] = dp[i-1][j]+dp[i][j-1]。

这里采纳 Array(m).fill(Array(n).fill(1)) 进行了初始化，因为每一格至多有一种走法。

/**
 * @param {number} m
 * @param {number} n
 * @return {number}
 */
var uniquePaths = function (m, n) {let dp = Array(m).fill(Array(n).fill(1));
  for (let i = 1; i < m; i++) {for (let j = 1; j < n; j++) {dp[i][j] = dp[i - 1][j] + dp[i][j - 1];
    }
  }
  return dp[m - 1][n - 1];
};

题目难度medium，波及到的算法常识有动静布局。

给定不同面额的硬币 coins 和一个总金额 amount。编写一个函数来计算能够凑成总金额所需的起码的硬币个数。如果没有任何一种硬币组合能组成总金额，返回 -1。

示例 1:

输出: (coins = [1, 2, 5]), (amount = 11);
输入: 3;
解释: 11 = 5 + 5 + 1;

示例 2:

输出: (coins = [2]), (amount = 3);
输入: -1;

阐明:
你能够认为每种硬币的数量是有限的。

这道题目咱们同样采纳 动静布局 来解决。

假如给出的不同面额的硬币是[1, 2, 5]，指标是 60，问起码须要的硬币个数？

咱们须要先合成子问题，分层级找最优子结构。

dp[i]: 示意总金额为 i 的时候最优解法的硬币数

咱们想一下：求总金额 60 有几种办法？一共有 3 种形式，因为咱们有 3 种不同面值的硬币。

拿一枚面值为 1 的硬币 + 总金额为 59 的最优解法的硬币数量。即：dp[59] + 1
拿一枚面值为 2 的硬币 + 总金额为 58 的最优解法的硬币数。即：dp[58] + 1
拿一枚面值为 5 的硬币 + 总金额为 55 的最优解法的硬币数。即：dp[55] + 1

所以，总金额为 60 的最优解法就是下面这三种解法中最优的一种，也就是硬币数起码的一种，咱们上面用代码来示意一下：

dp[60] = Math.min(dp[59] + 1, dp[58] + 1, dp[55] + 1);

推导出 状态转移方程：

dp[i] = Math.min(dp[i - coin] + 1, dp[i - coin] + 1, ...)

其中 coin 有多少种可能，咱们就须要比拟多少次，遍历 coins 数组，别离去比照即可

/**
 * @param {number[]} coins
 * @param {number} amount
 * @return {number}
 */
var coinChange = function (coins, amount) {let dp = new Array(amount + 1).fill(Infinity);
  dp[0] = 0;
  for (let i = 0; i <= amount; i++) {for (let coin of coins) {if (i - coin >= 0) {dp[i] = Math.min(dp[i], dp[i - coin] + 1);
      }
    }
  }
  return dp[amount] === Infinity ? -1 : dp[amount];
};

大多数前端同学对于算法的零碎学习，其实是比拟茫然的，这里我整顿了一张思维导图，算是比拟全面的概括了前端算法体系。

另外我还保护了一个 github 仓库：https://github.com/Cosen95/js_algorithm，外面蕴含了大量的 leetcode 题解，并且还在不断更新中，感觉不错的给个 star 哈！????

1. 如果感觉这篇文章还不错，来个 分享、点赞、在看 三连吧，让更多的人也看到～

2. 关注公众号 前端森林，定期为你推送陈腐干货好文。

3. 非凡阶段，带好口罩，做好集体防护。

关于算法:面试必问leetcode高频题精选

引言（文末有福利）????

两数之和 ????

题目形容

思路剖析

代码实现

三数之和 ????

题目形容

思路剖析

代码实现

盛最多水的容器 ????

题目形容

思路剖析

暴力法

双指针 动静滑窗

爬楼梯 ????

题目形容

思路剖析

代码实现

环形链表 ????

题目形容

思路剖析

标记法

快慢指针（双指针法）

无效的括号 ????

题目形容

思路剖析

switch case

哈希表map

滑动窗口最大值 ⛵

题目形容

思路剖析

暴力求解

双端队列

每日温度 ????

题目形容

思路剖析

代码实现

括号生成 ????

题目形容

思路剖析

代码实现

电话号码的字母组合 ????

题目形容

思路剖析

代码实现

哈希映射 逐层遍历

递归

岛屿数量 ????

题目形容

思路剖析

代码实现

散发饼干 ????

题目形容

思路剖析

代码实现

交易股票的最佳时机 II ????

题目形容

思路剖析

代码实现

不同门路 ????

题目形容

思路剖析

代码实现

零钱兑换 ????

题目形容

思路剖析

代码实现

福利

❤️ 爱心三连击

Just My Socks（注册教程 内含优惠码）

双指针动静滑窗

`switch case`

哈希表`map`

哈希映射逐层遍历

Just My Socks（注册教程内含优惠码）