Leetcode 20天算法学习计划 - 算法入门

第一天 · 二分查找

二分查找又称折半查找、二分搜索、折半搜索等，是在分治算法基础上设计出来的查找算法，对应的时间复杂度为 $O(log^n)$ ,二分查找算法仅适用于有序序列，它只能用在升序序列或者降序序列中查找目标元素。

二分查找算法的实现思路

在有序序列中，使用二分查找算法搜索目标元素的核心思想是：不断地缩小搜索区域，降低查找目标元素的难度。

首先确定整个查找区间的中间位置 $mid=(low+high)/2$ ;

用待查关键字值与中间位置关键字值进行比较；若相等，则查找成功；若大于，则在后半个区域中继续进行折半查找。若小于，则在前半个区域中继续进行折半查找。查找成功，返回关键字所在数组下标，没找到返回-1；

Leetcode 704 二分查找

Description

给定一个 $n$ 个元素有序的（升序）整型数组 $nums$ 和一个目标值 $target$ ，写一个函数搜索 $nums$ 中的 $target$ ，如果目标值存在返回下标，否则返回 -1。

Example

示例 1:

输入: nums = [-1,0,3,5,9,12], target = 9
输出: 4
解释: 9 出现在 nums 中并且下标为 4
示例 2:

输入: nums = [-1,0,3,5,9,12], target = 2
输出: -1
解释: 2 不存在 nums 中因此返回 -1

Example Hint

你可以假设 $nums$ 中的所有元素是不重复的。
$n$ 将在 [1, 10000]之间。
$nums$ 的每个元素都将在 [-9999, 9999]之间。

思路

二分查找有两个前提，第一是有序排列，第二是无重复元素。当满足以上两点的时候就可以考虑是不是可以使用二分法了。(本题题目就是二分查找，所以直接用就可以了)

AC 代码

var search = function(nums, target) {
  let low = 0, high = nums.length - 1;
  while (low <= high) {
    const mid = Math.floor((high - low) / 2) + low;
    const num = nums[mid];
    if (num === target) {
      return mid;
    } else if (num > target) {
      high = mid - 1;
    } else {
      low = mid + 1;
    }
  }
  return -1;
};

复杂度分析

时间复杂度： $O(logn)$ ，其中 $n$ 是数组的长度。
空间复杂度： $O(1)$ 。

Leetcode 278 第一个错误的版本

Description

你是产品经理，目前正在带领一个团队开发新的产品。不幸的是，你的产品的最新版本没有通过质量检测。由于每个版本都是基于之前的版本开发的，所以错误的版本之后的所有版本都是错的。

假设你有 $n$ 个版本 [1, 2, …, n]，你想找出导致之后所有版本出错的第一个错误的版本。

你可以通过调用 bool isBadVersion(version) 接口来判断版本号 version 是否在单元测试中出错。实现一个函数来查找第一个错误的版本。你应该尽量减少对调用 API 的次数。

Example

示例 1：

输入：n = 5, bad = 4
输出：4
解释：
调用 isBadVersion(3) -> false
调用 isBadVersion(5) -> true
调用 isBadVersion(4) -> true
所以，4 是第一个错误的版本。
示例 2：

输入：n = 1, bad = 1
输出：1

Example Hint

$1 <= bad <= n <= 231 - 1$

思路

二分法的变种:当一个版本为正确版本，则该版本之前的所有版本均为正确版本，当一个版本为错误版本，则该版本之后的所有版本均为错误版本。

AC 代码

int firstBadVersion(int n) {
  int left = 1, right = n;
  while (left < right) {  // 循环直至区间左右端点相同
    int mid = left + (right - left) / 2;  // 防止溢出
    if (isBadVersion(mid)) {
      right = mid;  // 答案在 [left, mid] 中
    } else {
      left = mid + 1;  // 答案在 [mid+1, right] 中
    }
  }
  // left == right，即为答案
  return left;
}

复杂度分析

时间复杂度： $O(logn)$ ，其中 $n$ 是给定版本的数量。
空间复杂度： $O(1)$ 。

Leetcode 35 搜索插入位置

Description

给定一个排序数组和一个目标值，在数组中找到目标值，并返回其索引。如果目标值不存在于数组中，返回它将会被按顺序插入的位置。

请必须使用时间复杂度为 $O(log n)$ 的算法。

Example

示例 1:

输入: nums = [1,3,5,6], target = 5
输出: 2
示例 2:

输入: nums = [1,3,5,6], target = 2
输出: 1
示例 3:

输入: nums = [1,3,5,6], target = 7
输出: 4

Example Hint

$1 <= nums.length <= 104$
$-104 <= nums[i] <= 104$
$nums$ 为无重复元素的升序排列数组
$-104 <= target <= 104$

思路

直接套用二分法即可，即不断用二分法逼近查找第一个大于等于 $target$ 的下标。

AC 代码

var searchInsert = function(nums, target) {
  const n = nums.length;
  let left = 0, right = n - 1, ans = n;
  while (left <= right) {
    let mid = ((right - left) >> 1) + left;
    if (target <= nums[mid]) {
      ans = mid;
      right = mid - 1;
    } else {
      left = mid + 1;
    }
  }
  return ans;
};

复杂度分析

时间复杂度： $O(logn)$ ，其中 $n$ 为数组的长度。
空间复杂度： $O(1)$ 。

第二天 · 双指针

双指针，顾名思义，就是利用两个指针去遍历数组，一般来说，遍历数组采用的是单指针（index)去遍历，两个指针一般是在有序数组中使用，一个放首，一个放尾，同时向中间遍历，直到两个指针相交，完成遍历，时间复杂度是 $O(n)$ 。

Leetcode 977 有序数组的平方

Description

给你一个按非递减顺序排序的整数数组 nums，返回每个数字的平方组成的新数组，要求也按非递减顺序排序。

Example

示例 1：

输入：nums = [-4,-1,0,3,10]
输出：[0,1,9,16,100]
解释：平方后，数组变为 [16,1,0,9,100]
排序后，数组变为 [0,1,9,16,100]
示例 2：

输入：nums = [-7,-3,2,3,11]
输出：[4,9,9,49,121]

Example Hint

$1 <= nums.length <= 104$
$-104 <= nums[i] <= 104$
$nums$ 已按非递减顺序排序

思路

双指针

AC 代码

const sortedSquares = nums => {
  let [start, end, result] = [0, nums.length - 1, Array(nums.length)]
  for (let i = 0; i < nums.length; i++) {
    const [s, e] = [nums[start] ** 2, nums[end] ** 2]
    if (s > e) {
      result[nums.length - i - 1] = s
      start++
    } else {
      result[nums.length - i - 1] = e
      end--
    }
  }
  return result
}

Leetcode 189 轮转数组

Description

给你一个数组，将数组中的元素向右轮转 k 个位置，其中 k 是非负数。

Example

示例 1:

输入: nums = [1,2,3,4,5,6,7], k = 3
输出: [5,6,7,1,2,3,4]
解释:
向右轮转 1 步: [7,1,2,3,4,5,6]
向右轮转 2 步: [6,7,1,2,3,4,5]
向右轮转 3 步: [5,6,7,1,2,3,4]
示例 2:

输入：nums = [-1,-100,3,99], k = 2
输出：[3,99,-1,-100]
解释:
向右轮转 1 步: [99,-1,-100,3]
向右轮转 2 步: [3,99,-1,-100]

Example Hint

$1 <= nums.length <= 105$
$-231 <= nums[i] <= 231 - 1$
$0 <= k <= 105$

思路

使用额外的数组,最后将新数组拷贝至原数组即可。

AC 代码

var rotate = function(nums, k) {
  const n = nums.length;
  const newArr = new Array(n);
  for (let i = 0; i < n; ++i) {
    newArr[(i + k) % n] = nums[i];
  }
  for (let i = 0; i < n; ++i) {
    nums[i] = newArr[i];
  }
};

第三天 · 双指针

一般双指针在有序数组中使用的特别多。

两数求和: 一般这种问题是问，寻找两个数的和为一个特定的值，这时候，如果数组有序，我们采用两个指针，分别从前和后往中间遍历，front移动和增大，tail移动和减小，通过特定的判断，可以求出特定的和。时间复杂度为 $O(n)$ ,如果用双重循环则要 $O(n^2)$ 。

in place交换: 数组的in place(就地)交换一般得用双指针，不然数组中添加或删除一个元素，需要移动大量元素。这时候，一般是一个指针遍历，一个指针去找可以用来交换的元素。

Leetcode 283 移动零

Description

给定一个数组 nums，编写一个函数将所有 0 移动到数组的末尾，同时保持非零元素的相对顺序。

请注意，必须在不复制数组的情况下原地对数组进行操作。

Example

示例 1:

输入: nums = [0,1,0,3,12]
输出: [1,3,12,0,0]
示例 2:

输入: nums = [0]
输出: [0]

Example Hint

$1 <= nums.length <= 104$
$-231 <= nums[i] <= 231 - 1$

思路

双指针快慢指针

AC 代码

var moveZeroes = function(nums) {
  let slow = 0, fast = 0;
  while (fast < nums.length) {
    if (nums[fast]) {
      nums[slow] = nums[fast]
      slow++
    }
    fast++
  }
  for (let i = slow; i < nums.length; i++) nums[i] = 0
};

Leetcode 167 两数之和 II - 输入有序数组

Description

给你一个下标从 1 开始的整数数组 numbers ，该数组已按非递减顺序排列，请你从数组中找出满足相加之和等于目标数 target 的两个数。如果设这两个数分别是 numbers[index1] 和 numbers[index2] ，则 1 <= index1 < index2 <= numbers.length 。

以长度为 2 的整数数组 [index1, index2] 的形式返回这两个整数的下标 index1 和 index2。

你可以假设每个输入只对应唯一的答案，而且你不可以重复使用相同的元素。

你所设计的解决方案必须只使用常量级的额外空间。

Example

示例 1：

输入： $numbers = [2,7,11,15], target = 9$
输出：[1,2]
解释：2 与 7 之和等于目标数 9 。因此 index1 = 1, index2 = 2 。返回 [1, 2] 。
示例 2：

输入： $numbers = [2,3,4], target = 6$
输出：[1,3]
解释：2 与 4 之和等于目标数 6 。因此 index1 = 1, index2 = 3 。返回 [1, 3] 。
示例 3：

输入： $numbers = [-1,0], target = -1$
输出：[1,2]
解释：-1 与 0 之和等于目标数 -1 。因此 index1 = 1, index2 = 2 。返回 [1, 2] 。

Example Hint

$2 <= numbers.length <= 3 * 104$
$-1000 <= numbers[i] <= 1000$
$numbers$ 按非递减顺序排列
$-1000 <= target <= 1000$
仅存在一个有效答案

思路

二分查找: 在数组中找到两个数，使得它们的和等于目标值，可以首先固定第一个数，然后寻找第二个数，第二个数等于目标值减去第一个数的差。
双指针: 初始时两个指针分别指向第一个元素位置和最后一个元素的位置。每次计算两个指针指向的两个元素之和，并和目标值比较。

AC 代码

function twoSum(numbers: number[], target: number): number[] {
  let left = 0, right = numbers.length - 1;
  while(left < right){
    if(numbers[left] + numbers[right] === target){
      return [++left, ++right];
    }
    if(numbers[left] + numbers[right] > target){
      right--;
    }else{
      left++;
    }
  }
};

第四天 · 双指针

Leetcode 344 反转字符串

Description

编写一个函数，其作用是将输入的字符串反转过来。输入字符串以字符数组 $s$ 的形式给出。

不要给另外的数组分配额外的空间，你必须原地修改输入数组、使用 $O(1)$ 的额外空间解决这一问题。

Example

示例 1：

输入：s = [“h”,“e”,“l”,“l”,“o”]
输出：[“o”,“l”,“l”,“e”,“h”]
示例 2：

输入：s = [“H”,“a”,“n”,“n”,“a”,“h”]
输出：[“h”,“a”,“n”,“n”,“a”,“H”]

Example Hint

$1 <= s.length <= 105$
s[i] 都是 ASCII 码表中的可打印字符

思路

使用双指针通过中间值进行交换

AC 代码

var reverseString = function (s) {
  let l = 0
  let r = s.length - 1
  let n = null
  while (l < r) {
    n = s[l]
    s[l] = s[r]
    s[r] = n
    l++
    r--
  }
};

Leetcode 557 反转字符串中的单词 III

Description

给定一个字符串 $s$ ，你需要反转字符串中每个单词的字符顺序，同时仍保留空格和单词的初始顺序。

Example

示例 1:

输入： $s = "Let's take LeetCode contest"$
输出： $"s'teL ekat edoCteeL tsetnoc"$

示例 2:

输入： s = “God Ding”
输出：“doG gniD”

Example Hint

$1 <= s.length <= 5 * 104$
s 包含可打印的 ASCII 字符。
s 不包含任何开头或结尾空格。
s 里至少有一个词。
s 中的所有单词都用一个空格隔开。

思路

使用Javascript API

AC 代码

/**
 * @param {string} s
 * @return {string}
 */
var reverseWords = function(s) {
    return s.split(' ').map(function(item) {
        return item.split('').reverse().join('');
    }).join(' ')
};

第五天 · 双指针

876. 链表的中间结点

Description

给定一个头结点为 $head$ 的非空单链表，返回链表的中间结点。

如果有两个中间结点，则返回第二个中间结点。

Example

示例 1：

输入：[1,2,3,4,5]
输出：此列表中的结点 3 (序列化形式：[3,4,5])
返回的结点值为 3 。 (测评系统对该结点序列化表述是 [3,4,5])。
注意，我们返回了一个 ListNode 类型的对象 ans，这样：
$ans.val = 3, ans.next.val = 4, ans.next.next.val = 5$ , 以及 $ans.next.next.next = NULL$ .
示例 2：

输入：[1,2,3,4,5,6]
输出：此列表中的结点 4 (序列化形式：[4,5,6])
由于该列表有两个中间结点，值分别为 3 和 4，我们返回第二个结点。

Example Hint

给定链表的结点数介于 $1$ 和 $100$ 之间。

思路

快慢指针遍历，直到快指针到达最后

AC 代码

var middleNode = function(head) {
  slow = fast = head;
  while (fast && fast.next) {//快慢指针遍历，直到快指针到达最后
    slow = slow.next;
    fast = fast.next.next;
  }
  return slow;
};

Leetcode 19 删除链表的倒数第 N 个结点

Description

给你一个链表，删除链表的倒数第 n 个结点，并且返回链表的头结点。

Example

示例 1：

输入：head = [1,2,3,4,5], n = 2
输出：[1,2,3,5]
示例 2：

输入：head = [1], n = 1
输出：[]
示例 3：

输入：head = [1,2], n = 1
输出：[1]

Example Hint

链表中结点的数目为 sz
$1 <= sz <= 30$
$0 <= Node.val <= 100$
$1 <= n <= sz$

思路

快慢指针一次遍历

AC 代码

var removeNthFromEnd = function(head, n) {
  if( head == null) return false
  let slow = head ,fast = head
  //让快指针先走
  for(let i = 0 ; i < n ; i++){
    fast = fast.next
  }
  if(!fast){ //判断是否n=1的情况，若是n=1的情况，fast此时应该为null，所以能触发这个条件
    return head.next
  }
  while(fast.next != null){
    slow = slow.next
    fast = fast.next
  }
  slow.next = slow.next.next //对要删除的值，指向进行更改，巧妙避开
  return head
};

第六天 · 滑动窗口

滑动窗口算法可以用以解决数组/字符串的子元素问题，它可以将嵌套的循环问题，转换为单循环问题，降低时间复杂度。

简而言之，滑动窗口算法在一个特定大小的字符串或数组上进行操作，而不在整个字符串和数组上操作，这样就降低了问题的复杂度，从而也达到降低了循环的嵌套深度。

Leetcode 3 无重复字符的最长子串

Description

给定一个字符串 s ，请你找出其中不含有重复字符的最长子串的长度。

Example

示例 1:

输入: s = “abcabcbb”
输出: 3
解释: 因为无重复字符的最长子串是 “abc”，所以其长度为 3。
示例 2:

输入: s = “bbbbb”
输出: 1
解释: 因为无重复字符的最长子串是 “b”，所以其长度为 1。
示例 3:

输入: s = “pwwkew”
输出: 3
解释: 因为无重复字符的最长子串是 “wke”，所以其长度为 3。请注意，你的答案必须是子串的长度，“pwke” 是一个子序列，不是子串。

Example Hint

$0 <= s.length <= 5 * 104$
s 由英文字母、数字、符号和空格组成

思路

暴力解法时间复杂度较高，会达到 $O(n^2)$ ，故而采取滑动窗口的方法降低时间复杂度

AC 代码

/**
 * @param {string} s
 * @return {number}
 */
var lengthOfLongestSubstring = function(s) {
  const n = s.length
  if (n <= 1) return n

  let left = 0, right = 0   //双指针之间的为无重复子串
  const win = new Map()     //键为字符，值为下标
  let res = 0     //记录最长值

  while (right < n) {
    //判断map中是否有当前字符
    const isHave = win.has(s[right]) ? win.get(s[right]) : -1

    if(isHave == -1 || isHave < left) {   //如果没有 或者 有但不在窗口内
      win.set(s[right], right)    //扩大窗口
      res = Math.max(res, right - left + 1)
      right++
    }else {
      left = isHave + 1   //说明有重复，则移动左指针到重复的字符右边，保证窗口内无重复字符
    }
  }
  return res
};

Leetcode 567 字符串的排列

Description

给你两个字符串 s1 和 s2 ，写一个函数来判断 s2 是否包含 s1 的排列。如果是，返回 true ；否则，返回 false 。
换句话说，s1 的排列之一是 s2 的子串。

Example

示例 1：

输入：s1 = “ab” s2 = “eidbaooo”
输出：true
解释：s2 包含 s1 的排列之一 (“ba”).
示例 2：

输入：s1= “ab” s2 = “eidboaoo”
输出：false

Example Hint

$1 <= s1.length, s2.length <= 104$
s1 和 s2 仅包含小写字母

思路

滑动窗口

AC 代码

/**
 * @param {string} s1
 * @param {string} s2
 * @return {boolean}
 */
var checkInclusion = function(s1, s2) {
  let len = s1.length;

  let arr1 = new Array(26).fill(0);
  let arr2 = new Array(26).fill(0);

  for(let el of s1) {
    arr1[el.charCodeAt(0) - 'a'.charCodeAt(0)] ++
  }

  let start = 0;
  for(let end = 0; end < s2.length; end ++) {
    arr2[s2[end].charCodeAt(0) - 'a'.charCodeAt(0)] ++
    if(end - start + 1 === len) {
      if(arr1.toString() === arr2.toString()) {
        return true
      }
    }

    if(end >= len - 1) {
      arr2[s2[start].charCodeAt(0) - 'a'.charCodeAt(0)]--;
      start ++;
    }
  }
  return false;
};

第七天 · 广度优先搜索 / 深度优先搜索

广度优先搜索和深度优先搜索一样，都是对图进行搜索的算法，都是从起点开始顺着边搜索，此时并不知道图的整体结构，直到找到指定节点(即终点)。在此过程中每走到一个节点，就会判断一次它是否为终点。

广度优先搜索会根据离起点的距离，按照从近到远的顺序对各节点进行搜索。而深度优先搜索会沿着一条路径不断往下搜索直到不能再继续为止，然后再折返，开始搜索下一条路径。

在广度优先搜索中，保存候补节点的队列，队列的性质就是先进先出，即先进入该队列的候补节点就先进行搜索。

在深度优先搜索中，保存候补节点是栈，栈的性质就是先进后出，即最先进入该栈的候补节点就最后进行搜索。

Leetcode 733 图像渲染

Description

有一幅以 $m x n$ 的二维整数数组表示的图画 image ，其中 $image[i][j]$ 表示该图画的像素值大小。

你也被给予三个整数 sr , sc 和 newColor 。你应该从像素 $image[sr][sc]$ 开始对图像进行上色填充。

为了完成上色工作，从初始像素开始，记录初始坐标的上下左右四个方向上像素值与初始坐标相同的相连像素点，接着再记录这四个方向上符合条件的像素点与他们对应四个方向上像素值与初始坐标相同的相连像素点，……，重复该过程。将所有有记录的像素点的颜色值改为 newColor 。

最后返回经过上色渲染后的图像。

Example

示例 1:

输入: image = [[1,1,1],[1,1,0],[1,0,1]]，sr = 1, sc = 1, newColor = 2
输出: [[2,2,2],[2,2,0],[2,0,1]]
解析: 在图像的正中间，(坐标(sr,sc)=(1,1)),在路径上所有符合条件的像素点的颜色都被更改成2。
注意，右下角的像素没有更改为2，因为它不是在上下左右四个方向上与初始点相连的像素点。
示例 2:

输入: image = [[0,0,0],[0,0,0]], sr = 0, sc = 0, newColor = 2
输出: [[2,2,2],[2,2,2]]

Example Hint

$m == image.length$
$n == image[i].length$
$1 <= m, n <= 50$
$0 <= image[i][j], newColor < 216$
$0 <= sr < m$
$0 <= sc < n$

思路

DFS(深度搜索优先)递归

AC 代码

var floodFill = function(image, sr, sc, newColor) {
  const row = image.length, col = image[0].length
  const oldColor = image[sr][sc]
  //如果新老颜色相同则无需填充更改
  if (oldColor == newColor) return image
  //开启dfs递归
  const dfs = (i, j) => {
    //判断边界条件，若越界或不同色，则直接返回上一轮递归
    if (i < 0 || i >= row || j < 0 || j >= col || image[i][j] != oldColor) return
    image[i][j] = newColor
    //分别向四个方向dfs深度优先遍历
    dfs(i - 1, j)   
    dfs(i + 1, j) 
    dfs(i, j - 1) 
    dfs(i, j + 1) 
  }
  dfs(sr, sc)
  return image
};

Leetcode 695 岛屿的最大面积

Description

给你一个大小为 $m$ $x$ $n$ 的二进制矩阵 grid 。

岛屿是由一些相邻的 1 (代表土地) 构成的组合，这里的「相邻」要求两个 1 必须在 $水平或者竖直的四个方向上$ 相邻。你可以假设 grid 的四个边缘都被 0（代表水）包围着。

岛屿的面积是岛上值为 1 的单元格的数目。

计算并返回 grid 中最大的岛屿面积。如果没有岛屿，则返回面积为 0 。

Example

示例 1

输入：grid = [[0,0,1,0,0,0,0,1,0,0,0,0,0],[0,0,0,0,0,0,0,1,1,1,0,0,0],[0,1,1,0,1,0,0,0,0,0,0,0,0],[0,1,0,0,1,1,0,0,1,0,1,0,0],[0,1,0,0,1,1,0,0,1,1,1,0,0],[0,0,0,0,0,0,0,0,0,0,1,0,0],[0,0,0,0,0,0,0,1,1,1,0,0,0],[0,0,0,0,0,0,0,1,1,0,0,0,0]]
输出：6
解释：答案不应该是 11 ，因为岛屿只能包含水平或垂直这四个方向上的 1 。
示例 2

输入：grid = [[0,0,0,0,0,0,0,0]]
输出：0

Example Hint

$m == grid.length$
$n == grid[i].length$
$1 <= m, n <= 50$
$grid[i][j] 为 0 或 1$

思路

DFS(深度搜索优先)

AC 代码

let area = 0
var maxAreaOfIsland = function (grid) {
  let max = -1
  for (let i = 0; i < grid.length; i++) {
      for (let j = 0; j < grid[0].length; j++) {
        area = 0
        dfs(grid, i, j)
        max = Math.max(max, area)
      }
  }
  return max
};

const dfs = (grid, cr, cc) => {
  // 越界
  if (cr < 0 || cr >= grid.length || cc < 0 || cc >= grid[0].length) return
  // 已访问过, 或者不是岛屿
  if (grid[cr][cc] === -1 || grid[cr][cc] === 0) return
  // 面积+1, 并标记已经访问
  area++
  grid[cr][cc] = -1
  dfs(grid, cr - 1, cc) // 上
  dfs(grid, cr, cc + 1) // 右
  dfs(grid, cr + 1, cc) // 下
  dfs(grid, cr, cc - 1) // 左
}

第八天 · 广度优先搜索 / 深度优先搜索

Leetcode 617 合并二叉树

Description

给你两棵二叉树： root1 和 root2 。

想象一下，当你将其中一棵覆盖到另一棵之上时，两棵树上的一些节点将会重叠（而另一些不会）。你需要将这两棵树合并成一棵新二叉树。合并的规则是：如果两个节点重叠，那么将这两个节点的值相加作为合并后节点的新值；否则，不为 null 的节点将直接作为新二叉树的节点。

返回合并后的二叉树。

注意: 合并过程必须从两个树的根节点开始。

Example

示例 1

输入：root1 = [1,3,2,5], root2 = [2,1,3,null,4,null,7]
输出：[3,4,5,5,4,null,7]
示例 2

输入：root1 = [1], root2 = [1,2]
输出：[2,2]

Example Hint

两棵树中的节点数目在范围 [0, 2000] 内
$-104 <= Node.val <= 104$

思路

使用深度优先搜索合并两个二叉树。从根节点开始同时遍历两个二叉树，并将对应的节点进行合并。

AC 代码

/**
 * @param {TreeNode} root1
 * @param {TreeNode} root2
 * @return {TreeNode}
 */
var mergeTrees = function (root1, root2) {
  // 如果一棵树有，另一棵树没有，接上去
  if (root1 == null) return root2;
  if (root2 == null) return root1;
  // 两棵树都有的节点，叠加节点值
  root1.val += root2.val;
  // 递归合并左右子树
  root1.left = mergeTrees(root1.left, root2.left);
  root1.right = mergeTrees(root1.right, root2.right);
  return root1;
};

Leetcode 116 填充每个节点的下一个右侧节点指针

Description

给定一个完美二叉树，其所有叶子节点都在同一层，每个父节点都有两个子节点。二叉树定义如下：

struct Node {
  int val;
  Node *left;
  Node *right;
  Node *next;
}

填充它的每个 next 指针，让这个指针指向其下一个右侧节点。如果找不到下一个右侧节点，则将 next 指针设置为 NULL。
初始状态下，所有 next 指针都被设置为 NULL。

Example

示例 1

输入：root = [1,2,3,4,5,6,7]
输出：[1,#,2,3,#,4,5,6,7,#]
解释：给定二叉树如图 A 所示，你的函数应该填充它的每个 next 指针，以指向其下一个右侧节点，如图 B 所示。序列化的输出按层序遍历排列，同一层节点由 next 指针连接，‘#’ 标志着每一层的结束。
示例 2

输入：root = []
输出：[]

Example Hint

树中节点的数量在 [0, 212 - 1] 范围内
$-1000 <= node.val <= 1000$

思路

DFS(深度优先搜索)递归

AC 代码

const connect = (root) => {
  if (root == null) {
    return root;
  }

  const dfs = (root) => {
    if (root.left == null && root.right == null) {
      return;
    }
    root.left.next = root.right;
    if (root.next) {
      root.right.next = root.next.left;
    }
    dfs(root.left);
    dfs(root.right);
  };

  dfs(root);
  return root;
};

第九天 · 广度优先搜索 / 深度优先搜索

Leetcode 542 01 矩阵

Description

给定一个由 0 和 1 组成的矩阵 mat ，请输出一个大小相同的矩阵，其中每一个格子是 mat 中对应位置元素到最近的 0 的距离。

两个相邻元素间的距离为 1 。

Example

示例 1

输入：mat = [[0,0,0],[0,1,0],[0,0,0]]
输出：[[0,0,0],[0,1,0],[0,0,0]]
示例 2

输入：mat = [[0,0,0],[0,1,0],[1,1,1]]
输出：[[0,0,0],[0,1,0],[1,2,1]]

Example Hint

$m == mat.length$
$n == mat[i].length$
$1 <= m, n <= 104$
$1 <= m * n <= 104$
$mat[i][j] is either 0 or 1.$
$mat 中至少有一个 0 $

思路

先将矩阵中所有为0的元素的坐标加入队列，并且置其为已访问

队首出元素，从当前节点扩散，扩散的条件是在矩阵范围内且并未被访问过

目标元素的距离就等于上一个元素的距离+1

AC 代码

/**
 * @param {number[][]} mat
 * @return {number[][]}
 */
var updateMatrix = function (mat) {
  let rows = mat.length, cols = mat[0].length;
  // 目标返回结果集
  let dist = new Array(rows).fill(0).map(() => new Array(cols).fill(0));
  // 判断是否访问过 默认为false
  let vis = new Array(rows).fill(false).map(() => new Array(cols).fill(false));
  // 方向数组
  let directions = [
    [0, 1],
    [0, -1],
    [-1, 0],
    [1, 0],
  ];
  let queue = [];
  for (let i = 0; i < rows; i++) {
    for (let j = 0; j < cols; j++) {
      if (mat[i][j] == 0) {
        queue.push([i, j]);
        // 这里要置为true  就不会存在0 到 0 扩散的路径了
        vis[i][j] = true;
      }
    }
  }
  while (queue.length) {
    let [curI, curJ] = queue.shift();
    for (let dir of directions) {
      let newI = curI + dir[0],
        newJ = curJ + dir[1];
      // 超出边界 或者已经访问过了
      if (
        newI < 0 ||
        newI >= rows ||
        newJ < 0 ||
        newJ >= cols ||
        vis[newI][newJ]
      )
        continue;
      // 从上一个点扩散到当前点  路径长度加1
      dist[newI][newJ] = dist[curI][curJ] + 1;
      vis[newI][newJ] = true;
      queue.push([newI, newJ]);
    }
  }
  return dist;
};

Leetcode 994 腐烂的橘子

Description

在给定的 m x n 网格 grid 中，每个单元格可以有以下三个值之一：

值 0 代表空单元格；
值 1 代表新鲜橘子；
值 2 代表腐烂的橘子。
每分钟，腐烂的橘子周围 4 个方向上相邻的新鲜橘子都会腐烂。

返回直到单元格中没有新鲜橘子为止所必须经过的最小分钟数。如果不可能，返回 -1 。

Example

示例 1

输入：grid = [[2,1,1],[1,1,0],[0,1,1]]
输出：4
示例 2

输入：grid = [[2,1,1],[0,1,1],[1,0,1]]
输出：-1
解释：左下角的橘子（第 2 行，第 0 列）永远不会腐烂，因为腐烂只会发生在 4 个正向上。
示例 3

输入：grid = [[0,2]]
输出：0
解释：因为 0 分钟时已经没有新鲜橘子了，所以答案就是 0 。

Example Hint

m == grid.length
n == grid[i].length
1 <= m, n <= 10
grid[i][j] 仅为 0、1 或 2

思路

BFS(广度优先搜索)

AC 代码

/**
 * @param {number[][]} grid
 * @return {number}
 */
const dirs = [[0, 1], [1, 0], [0, -1], [-1, 0]]
var orangesRotting = function(grid) {
  const m = grid.length, n = grid[0].length
  let cnts = 0, cost = 0, queue = new Array()
  for(let i = 0; i < m; i++)
    for(let j = 0; j < n; j++)
      if(grid[i][j] > 0){
        cnts++
        if(grid[i][j] == 2)
          queue.push([i, j])
      }
  while(queue.length > 0){
    const nxt = new Array()
    cnts -= queue.length
    for(const p of queue){
      for(const d of dirs){
        const nx = p[0] + d[0], ny = p[1] + d[1]
        if(nx >= 0 && ny >= 0 && nx < m && ny < n && grid[nx][ny] == 1){
          grid[nx][ny] = 2
          nxt.push([nx, ny])
        }
      }
    }
    queue = nxt
    if(queue.length > 0)
      cost++
  }
  return cnts == 0 ? cost : -1
};

第十天 · 递归 / 回溯

递归是一种算法结构，递归会出现在子程序中自己调用自己或间接地自己调用自己。最直接的递归应用就是计算连续数的阶乘，计算规律： $n!=(n-1)!*n$ 。

回溯是一种算法思想，可以用递归实现。通俗点讲回溯就是一种试探，类似于穷举，但回溯有“剪枝”功能。

剪枝顾名思义，就是删去一些不重要的节点，来减小计算或搜索的复杂度。在搜索算法中，可以减小搜索范围，提高搜索效率。

Leetcode 21 合并两个有序链表

Description

将两个升序链表合并为一个新的升序链表并返回。新链表是通过拼接给定的两个链表的所有节点组成的。

Example

示例 1

输入：l1 = [1,2,4], l2 = [1,3,4]
输出：[1,1,2,3,4,4]
示例 2

输入：l1 = [], l2 = []
输出：[]
示例 3

输入：l1 = [], l2 = [0]
输出：[0]

Example Hint

两个链表的节点数目范围是 [0, 50]
$-100 <= Node.val <= 100$
l1 和 l2 均按非递减顺序排列

思路

递归

AC 代码

var mergeTwoLists = function(l1, l2) {
  if (l1 === null) {
    return l2;
  } else if (l2 === null) {
    return l1;
  } else if (l1.val < l2.val) {
    l1.next = mergeTwoLists(l1.next, l2);
    return l1;
  } else {
    l2.next = mergeTwoLists(l1, l2.next);
    return l2;
  }
};

Leetcode 206 反转链表

Description

给你单链表的头节点 head ，请你反转链表，并返回反转后的链表。

Example

示例 1

输入：head = [1,2,3,4,5]
输出：[5,4,3,2,1]
示例 2

输入：head = [1,2]
输出：[2,1]
示例 3

输入：head = []
输出：[]

Example Hint

链表中节点的数目范围是 [0, 5000]
$-5000 <= Node.val <= 5000$

思路

迭代

AC 代码

var reverseList = function(head) {
  let prev = null, curr = head
  while (curr) {
    const next = curr.next
    curr.next = prev
    prev = curr
    curr = next
  }
  return prev
};

第十一天 · 递归 / 回溯

Leetcode 77 组合

Description

给定两个整数 n 和 k，返回范围 [1, n] 中所有可能的 k 个数的组合。

你可以按任何顺序返回答案。

Example

示例 1

输入：n = 4, k = 2
输出：
[
  [2,4],
  [3,4],
  [2,3],
  [1,2],
  [1,3],
  [1,4],
]

示例 2
1
2
输入：n = 1, k = 1
输出：[[1]]

Example Hint

$1 <= n <= 20$
$1 <= k <= n$

思路

回溯+剪枝

AC 代码

let res: number[][]
function combine(n: number, k: number): number[][] {
  res = new Array()
  dfs(n, k, 1, new Array())
  return res
};

const dfs = function (n: number, k: number, begin: number, path: number[]) {
  // 剪枝
  if (path.length + (n - begin + 1) < k) return;
  if (path.length == k) {
    res.push([...path]);
    return;
  }
  for (let i = begin; i <= n; i++) {
    path.push(i)
    dfs(n, k, i + 1, path);
    // 回溯
    path.pop()
  }
}

Leetcode 46 全排列

Description

给定一个不含重复数字的数组 nums ，返回其所有可能的全排列。你可以 按任意顺序 返回答案。

Example

示例 1

输入：nums = [1,2,3]
输出：[[1,2,3],[1,3,2],[2,1,3],[2,3,1],[3,1,2],[3,2,1]]
示例 2

输入：nums = [0,1]
输出：[[0,1],[1,0]]
示例 3

输入：nums = [1]
输出：[[1]]

Example Hint

$1 <= nums.length <= 6$
$-10 <= nums[i] <= 10$
$nums$ 中的所有整数互不相同

思路

用递归模拟出所有情况,遇到包含重复元素的情况,就回溯,收集所有到达递归终点的情况，并返回.

AC 代码

/**
 * @param {number[]} nums
 * @return {number[][]}
 */
var permute = function(nums) {
  const res = []
  const backtrack = (path) => {
    if(path.length === nums.length) {
      res.push(path)
      return 
    }
    nums.forEach(n => {
      if(path.includes(n)) return;
      backtrack(path.concat(n))
    })
  }
  backtrack([])
  return res
};

Leetcode 784 字母大小写全排列

Description

给定一个字符串 s ，通过将字符串 s 中的每个字母转变大小写，我们可以获得一个新的字符串。

返回所有可能得到的字符串集合。以 任意顺序 返回输出。

Example

示例 1

输入：s = “a1b2”
输出：[“a1b2”, “a1B2”, “A1b2”, “A1B2”]
示例 2

输入: s = “3z4”
输出: [“3z4”,“3Z4”]

Example Hint

$1 <= s.length <= 12$
s 由小写英文字母、大写英文字母和数字组成

思路

Leetcode 官方题解思路
如果下一个字符 c 是字母，将当前已遍历过的字符串全排列复制两份，在第一份的每个字符串末尾添加 lowercase©，在第二份的每个字符串末尾添加 uppercase©。

如果下一个字符 c 是数字，将 c 直接添加到每个字符串的末尾。

AC 代码

class Solution(object):
  def letterCasePermutation(self, S):
    ans = [[]]
    for char in S:
      n = len(ans)
      if char.isalpha():
        for i in xrange(n):
          ans.append(ans[i][:])
          ans[i].append(char.lower())
          ans[n+i].append(char.upper())
      else:
        for i in xrange(n):
          ans[i].append(char)
  return map("".join, ans)

第十二天 · 动态规划

Leetcode 70 爬楼梯

Description

假设你正在爬楼梯。需要 n 阶你才能到达楼顶。

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

Example

示例 1
输入：n = 2
输出：2
解释：有两种方法可以爬到楼顶。
1. 1 阶 + 1 阶
2. 2 阶
示例 2
输入：n = 3
输出：3
解释：有三种方法可以爬到楼顶。
1. 1 阶 + 1 阶 + 1 阶
2. 1 阶 + 2 阶
3. 2 阶 + 1 阶

Example Hint

$1 <= n <= 45$

思路

数学没学好的我留下了悔恨的泪水~
通过斐波那契数列通项公式 $a_n = \frac{1}{\sqrt{5}} \left[ \left( \frac{1+\sqrt{5}}{2} \right)^2 - \left( \frac{1-\sqrt{5}}{2} \right)^2 \right]$

AC 代码

/**
 * @param {number} n
 * @return {number}
 */
var climbStairs = function(n) {
  const sqrt_5 = Math.sqrt(5);
  const fib_n = Math.pow((1 + sqrt_5) / 2, n + 1) - Math.pow((1 - sqrt_5) / 2,n + 1);
  return Math.round(fib_n / sqrt_5);
};

Leetcode 198 打家劫舍

Description

你是一个专业的小偷，计划偷窃沿街的房屋。每间房内都藏有一定的现金，影响你偷窃的唯一制约因素就是相邻的房屋装有相互连通的防盗系统，如果两间相邻的房屋在同一晚上被小偷闯入，系统会自动报警。

给定一个代表每个房屋存放金额的非负整数数组，计算你 不触动警报装置的情况下 ，一夜之内能够偷窃到的最高金额。

Example

示例 1

输入：[1,2,3,1]
输出：4
解释：偷窃 1 号房屋 (金额 = 1) ，然后偷窃 3 号房屋 (金额 = 3)。偷窃到的最高金额 = 1 + 3 = 4 。
示例 2

输入：[2,7,9,3,1]
输出：12
解释：偷窃 1 号房屋 (金额 = 2), 偷窃 3 号房屋 (金额 = 9)，接着偷窃 5 号房屋 (金额 = 1)。偷窃到的最高金额 = 2 + 9 + 1 = 12 。

Example Hint

$1 <= nums.length <= 100$
$0 <= nums[i] <= 400$

思路

动态规划

AC 代码

const rob = nums => {
  // 数组长度
  const len = nums.length;
  // dp数组初始化
  const dp = [nums[0], Math.max(nums[0], nums[1])];
  // 从下标2开始遍历
  for (let i = 2; i < len; i++) {
    dp[i] = Math.max(dp[i - 2] + nums[i], dp[i - 1]);
  }
  return dp[len - 1];
};

Leetcode 120 三角形最小路径和

Description

给定一个三角形 triangle ，找出自顶向下的最小路径和。

每一步只能移动到下一行中相邻的结点上。相邻的结点 在这里指的是下标与 上一层结点下标 相同或者等于 上一层结点下标 + 1 的两个结点。也就是说，如果正位于当前行的下标 i ，那么下一步可以移动到下一行的下标 i 或 i + 1 。

Example

示例 1

输入：triangle = [[2],[3,4],[6,5,7],[4,1,8,3]]
输出：11
解释：如下面简图所示：
1
2
3
4
2
3 4
6 5 7
4 1 8 3
自顶向下的最小路径和为 11（即，2 + 3 + 5 + 1 = 11）。
示例 2

输入：triangle = [[-10]]
输出：-10

Example Hint

$1 <= triangle.length <= 200$
$triangle[0].length == 1$
$triangle[i].length == triangle[i - 1].length + 1$
$-104 <= triangle[i][j] <= 104$

思路

动态规划：自底向上看，我们可以得出动态方程： $dp[i][j] = triangle[i][j] + Math.min(dp[i + 1][j] + dp[i + 1][j + 1])$

AC 代码

function minimumTotal(triangle: number[][]): number {
  const dp = [...triangle].map(item => item.map(i => i));
  for (let i = triangle.length - 2; i >=0; i--) {
    for (let j = 0; j <= triangle[i].length - 1; j++) {
      dp[i][j] = triangle[i][j] + Math.min(dp[i + 1][j], dp[i + 1][j + 1])
    }
  }
  return dp[0][0];
};

第十三天 · 位运算

Leetcode 231 2的幂

Description

给你一个整数 $n$ ，请你判断该整数是否是 $2$ 的幂次方。如果是，返回 $true$ ；否则，返回 $false$ 。

如果存在一个整数 $x$ 使得 $n == 2x$ ，则认为 $n$ 是 $2$ 的幂次方。

Example

示例 1

输入：n = 1
输出：true
解释：20 = 1
示例 2

输入：n = 16
输出：true
解释：24 = 16
示例 3

输入：n = 3
输出：false
示例 4

输入：n = 4
输出：true
示例 5

输入：n = 5
输出：false

Example Hint

$-231 <= n <= 231 - 1$

进阶

你能够不使用循环/递归解决此问题吗？

思路

位运算
取模

AC 代码

/**
 * @param {number} n
 * @return {boolean}
 */

// 位运算法 
var isPowerOfTwo = function(n) {
  return n > 0 && (n & (-n)) == n
};

// 取模法
var isPowerOfTwo = function(n) {
  while(n > 1){
    n /= 2;
  }
  if(n == 1){
    return true;
  }else{
    return false;
  }
};

Leetcode 191 位1的个数

Description

编写一个函数，输入是一个无符号整数（以二进制串的形式），返回其二进制表达式中数字位数为 ‘1’ 的个数（也被称为汉明重量）。
提示：

请注意，在某些语言（如 Java）中，没有无符号整数类型。在这种情况下，输入和输出都将被指定为有符号整数类型，并且不应影响您的实现，因为无论整数是有符号的还是无符号的，其内部的二进制表示形式都是相同的。
在 Java 中，编译器使用二进制补码记法来表示有符号整数。因此，在上面的示例 3 中，输入表示有符号整数 -3。

Example

示例 1

输入：00000000000000000000000000001011
输出：3
解释：输入的二进制串 00000000000000000000000000001011 中，共有三位为 ‘1’。
示例 2

输入：00000000000000000000000010000000
输出：1
解释：输入的二进制串 00000000000000000000000010000000 中，共有一位为 ‘1’。
示例 3

输入：11111111111111111111111111111101
输出：31
解释：输入的二进制串 11111111111111111111111111111101 中，共有 31 位为 ‘1’。

Example Hint

输入必须是长度为 $32$ 的二进制串。

进阶

如果多次调用这个函数，你将如何优化你的算法？

思路

对 int 的每一位进行检查，并统计 1 的个数。

AC 代码

public class Solution {
  public int hammingWeight(int n) {
    int ans = 0;
    for (int i = 0; i < 32; i++) {
      ans += ((n >> i) & 1);
    }
    return ans;
  }
}

第十四天 · 位运算

Leetcode 190 颠倒二进制位

Description

颠倒给定的 32 位无符号整数的二进制位。
tips:请注意，在某些语言（如 Java）中，没有无符号整数类型。在这种情况下，输入和输出都将被指定为有符号整数类型，并且不应影响您的实现，因为无论整数是有符号的还是无符号的，其内部的二进制表示形式都是相同的。在 Java 中，编译器使用二进制补码记法来表示有符号整数。因此，在示例 2 中，输入表示有符号整数 -3，输出表示有符号整数 -1073741825。

Example

示例 1

输入： $n = 00000010100101000001111010011100$
输出： $964176192 (00111001011110000010100101000000)$
解释：输入的二进制串 $00000010100101000001111010011100$ 表示无符号整数 $43261596$ ，因此返回 $964176192$ ，其二进制表示形式为 $00111001011110000010100101000000$ 。
示例 2

输入： $n = 11111111111111111111111111111101$
输出： $3221225471$ $(10111111111111111111111111111111)$
解释：输入的二进制串 $11111111111111111111111111111101$ 表示无符号整数 $4294967293$ ，因此返回 $3221225471$ 其二进制表示形式为 $10111111111111111111111111111111$ 。

Example Hint

输入是一个长度为 $32$ 的二进制字符串

思路

将 $n$ 视作一个长为 $32$ 的二进制串，从低位往高位枚举 $n$ 的每一位，将其倒序添加到翻转结果 $rev$ 中。代码实现中，每枚举一位就将 $n$ 右移一位，这样当前 $n$ 的最低位就是我们要枚举的比特位。当 $n$ 为 $0$ 时即可结束循环。

AC 代码

var reverseBits = function(n) {
  let rev = 0;
  for (let i = 0; i < 32 && n > 0; ++i) {
    rev |= (n & 1) << (31 - i);
    n >>>= 1;
  }
  return rev >>> 0;
};

Leetcode 136 只出现一次的数字

Description

给定一个非空整数数组，除了某个元素只出现一次以外，其余每个元素均出现两次。找出那个只出现了一次的元素。

说明：你的算法应该具有线性时间复杂度。你可以不使用额外空间来实现吗？

Example

示例 1

输入: [2,2,1]
输出: 1
示例 2

输入: [4,1,2,1,2]
输出: 4

思路

异或运算(看了评论区才知道 :P)

AC 代码

/**
 * @param {number[]} nums
 * @return {number}
 */
var singleNumber = function(nums) {
  let result = 0;
  for (let a of nums) {
    result ^= a;
  }
  return result;
};