乐趣区

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

jiezi

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

算法始终是大厂前端面试常问的一块，而大家往往筹备这方面的面试都是通过 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;
};

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

题目难度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. 非凡阶段，带好口罩，做好集体防护。

退出移动版