破酥 | C4iN
LeetCodeHot100笔记

LeetCodeHot100笔记

2024年09月08日 13.1k 字 大概 62 分钟

本文章用于记录刷LeetCodeHot100 ez&mid遇到的知识点。

唉算法，这方面我完全是个小白

哈希

这部分学到了可以用哈希来用空间换时间

两数之和

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

1
2
3
4
5
6
7
8
9
10
11
function twoSum(nums: number[], target: number): number[] {
    var map = new Map();
    for(let i=0; i<nums.length; i++) {
        if(map.has(target - nums[i])) {
            return [map.get(target - nums[i]), i]
        } else {
            map.set(nums[i], i)
        }
    }
    return []
};

思路：用哈希存储数组值和对应的索引，而后在循环中根据target - nums[i]来找到与nums[i]和为目标值 target的整数。

字母异位词分组

给你一个字符串数组，请你将 字母异位词 组合在一起。可以按任意顺序返回结果列表。

字母异位词 是由重新排列源单词的所有字母得到的一个新单词。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
function groupAnagrams(strs: string[]): string[][] {
    let result: Array<string[]> = []  
    // 键：存储单词字母的按顺序排序后的字符串，值：对应result数组索引值
    let strMap: Map<string, string[]> = new Map()

    for (let i = 0 ; i < strs.length ; i++) {
        const letters = strs[i].split("").sort().join("")
        let key = letters
        let keyValue: string[] = (strMap.get(letters) ? strMap.get(letters) :  new Array<string>()) as string[]
        keyValue.push(strs[i])
        strMap.set(key, keyValue)
    }

    return Array.from(strMap.values())
}

思路：哈希存储排序后的组成单词的字符，这里注意sortBy的用处。

最长连续序列

给定一个未排序的整数数组 nums ，找出数字连续的最长序列（不要求序列元素在原数组中连续）的长度。

请你设计并实现时间复杂度为 O(n) 的算法解决此问题。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
function longestConsecutive(nums: number[]): number {
    let result: Array<number> = []

    // 输入为空则直接返回0
    if (nums[0] === undefined) {
        return 0
    }
    // 去重
    const set = new Set(nums.sort(function(a, b){return a - b}))
    const sortedNums = Array.from(set)
    // 当前递增序列长度，初始值为1
    let len = 1
    // 序列起始值
    let min: number = sortedNums[0]
    // 存储每个序列的长度, 键：序列最小值， 值：序列长度
    let maxlengthMap = new Map();
    maxlengthMap.set(min, 1)

    // console.log(sortedNums)
    
    for (let i = 1 ; i < sortedNums.length ; i++) {
        if (sortedNums[i] === sortedNums[i-1] + 1) {
            // 如果当前元素是上一元素的递增，则最大长度+1
            maxlengthMap.set(min, ++len)
            // console.log("length:", len, sortedNums[i])
        } else {
            // 如果不是，则说明有新的序列
            // console.log("new")
            min = sortedNums[i]
            maxlengthMap.set(min, 1)
            len = 1
        }
    }

    result = Array.from(maxlengthMap.values()).sort(function(a, b){return a - b})
    // console.log(result)
    return result[result.length - 1]
};

思路：集合去重，哈希存储各个序列的每个序列的长度，键为序列最小值， 值为序列长度。

双指针

这部分知识点之前没怎么接触过。

移动零

这题的方法我第一次见，打个标记

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

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

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
/**
 Do not return anything, modify nums in-place instead.
 */
function moveZeroes(nums: number[]): void {
    // 快慢指针
    // 快指针不断向后遍历    
    // 如果没有碰到0，快慢指针一起移动，并把快指针的值赋值给慢指针
    // 如果碰到0，快指针继续移动，慢指针不动
    // 慢指针此刻指到的位置就是0的位置，等待后序被覆盖
    let slow = 0
    for (let fast = 0 ; fast < nums.length; fast++) {
        if (nums[fast] !== 0) {
            nums[slow] = nums[fast]
            slow++
        }
    }

    // 循环结束后slow指针位置就是末尾0的位置，调用fill填充即可
    nums.fill(0, slow)
};

思路：快慢指针

盛最多水的容器

给定一个长度为 n 的整数数组 height 。有 n 条垂线，第 i 条线的两个端点是 (i, 0) 和 (i, height[i]) 。

找出其中的两条线，使得它们与 x 轴共同构成的容器可以容纳最多的水。

返回容器可以储存的最大水量。

说明：你不能倾斜容器。

本来的思路是用最大高度扫描，然后获取对应的索引，但是indexOf，lastIndexOf方法的时间复杂度就很高，会超时

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
function maxArea(height: number[]): number {
    let maxValue = 0
    // 双指针，移动对应元素最小值的指针
    let start = 0
    let end = height.length - 1
    while(start !== end) {
        const h = Math.min(height[start], height[end])
        const currentMax = h * (end - start)
        if (currentMax > maxValue) maxValue = currentMax
        if (height[start] - height[end] <= 0) start++
        else end--
    }


    return maxValue
};

思路：类似快速排序算法思路，首尾指针遍历数组，对应数组元素较小的那个指针移动。

三数之和

给你一个整数数组 nums ，判断是否存在三元组 [nums[i], nums[j], nums[k]] 满足 i != j、i != k 且 j != k ，同时还满足 nums[i] + nums[j] + nums[k] == 0 。请你返回所有和为 0 且不重复的三元组。

注意：答案中不可以包含重复的三元组。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
function threeSum(nums: number[]): number[][] {
    const result: Array<number[]> = [] 
    const len = nums.length
    if (nums === null || len < 3) return result
    nums.sort((a,b) => a-b)
    
    for (let i = 0; i < len - 1; i++) {
        // 由于从小到大排序，不需要考虑 > 0 的元素
        if (nums[i] > 0) break
        // 去重
        if (i > 0 && nums[i] === nums[i-1]) continue
        // 双指针
        let start = i + 1
        let end = len - 1
        while (start < end) {
            // 根据三数和与 0 的大小关系判断双指针移动
            const sum = nums[i] + nums[start] + nums[end]
            if (sum < 0) {
                // 偏小，需要移动左指针
                start++
            } else if (sum > 0) {
                // 偏大，移动右指针
                end--
            } else {
                result.push([nums[i], nums[start], nums[end]])
                // 移动左指针，跳过左侧重复
                while(start < end && nums[start] === nums[start+1]) start++
                // 移动右指针，跳过右侧侧重复
                while(start < end && nums[end] === nums[end-1]) end--
                start++
                end--
            }
        }

    }
    return result
};

  • 一种做法是对每一个元素进行一次两数之和，复杂度也是O(n^2)

  • 这里需要特别注意[0,0,0,0]的情况

  • 理解基本思路后，要注意去重的处理

  • 原本用哈希表去重，但是实在太慢了

思路：先排序数组，方便去重操作。建立循环遍历，然后创建指向除当前元素剩下元素组首尾的双指针，计算当前元素、首指针元素、尾指针元素之和，并与0比较：

  • 偏小移动左指针
  • 偏大移动右指针
  • 等于0则将三个数存入结果中

我们着重讲怎么去重：

如上图，遍历时对于重复的元素总是有部分相同的后续元素，于是我们只需要处理第一次遇到的元素即可。

找到匹配的三元组后，我们需要更新start和end的值。不难发现，如果后续还有相同的值，需要跳过避免重复，此时移动双端指针。

移动窗口

无重复字符的最长子串

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

1
2
3
4
5
6
7
8
9
10
11
12
13
14
function lengthOfLongestSubstring(s: string): number {
    let result = 0
    let window = new Set<string>()

    for (let i = 0; i < s.length; i++) {
        while (window.has(s[i])) {
            window.delete(s.charAt(i - window.size))
        }
        window.add(s[i])
        result = Math.max(result, window.size)
    }

    return result
};

思路：用集合作为滑动窗口存储当前最长字串，如果遇到重复字符，删除集合中包括该重复字符前的所有字符。

找到字符串中所有字母异位词

给定两个字符串 s 和 p，找到 s 中所有 p 的 异位词 的子串，返回这些子串的起始索引。不考虑答案输出的顺序。

异位词 指由相同字母重排列形成的字符串（包括相同的字符串）。·

1
2
3
4
5
6
7
8
9
10
11
12
function findAnagrams(s: string, p: string): number[] {
    let result: number[] = []
    const sortedP = p.split('').sort().join()
    for (let i = 0 ; i < s.length - p.length + 1; i++) {
        const sortedS = s.substring(i, i+ p.length).split('').sort().join()
        if (sortedS === sortedP) {
            result.push(i)
        }
    }

    return result
};

直接使用数组方法会超时

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
function findAnagrams(s: string, p: string): number[] {
    
    let result: number[] = []
    let strMap = new Map()
    
    if (s.length < p.length) return result
    
    for (let i = 0; i <  p.length ; i++) {
        // 存储p中出现的字母以及出现次数
        strMap.set(p[i], (strMap.get(p[i]) || 0) + 1)
    }
    
    // 创建窗口
    let r = 0
    for ( ; r < p.length; r++) {
        if (strMap.has(s[r])) {
            strMap.set(s[r], strMap.get(s[r]) - 1)
        }
    }   

    // 移动窗口，找到异位词
    // 注意这里要是等号，到达尾部也要进行判断
    for (let l = 0 ; r <= s.length ; r++, l++) {
        // 如果map中所有字符数量均被消费完毕，则说明找到异位词
        if ([...strMap.values()].every(v => v===0)) {
            result.push(l)
        }

        // 遍历已被消费的异位词，重新填充strMap
        if (strMap.has(s[l])) {
            strMap.set(s[l], strMap.get(s[l]) + 1)
        }

        // 如果遇到匹配的字符，则消费
        if (strMap.has(s[r])) {
            strMap.set(s[r], strMap.get(s[r]) - 1)
        }

        console.log(strMap)
    }

    return result
};

思路：根据异位词的特征，每个异位词中字母出现的次数都一样，我们先创建哈希表存储p中出现的字母以及出现次数，而后使用滑动窗口，窗口右端遇到匹配的字母则消费次数，窗口左端遇到匹配字母则增加出现次数。当哈希表中所有字母的出现次数均为0时，则说明找到了一个异位词，将窗口左端索引添加到结果中。

子串

和为 K 的子数组

给你一个整数数组 nums 和一个整数 k ，请你统计并返回 该数组中和为 k 的子数组的个数 。

子数组是数组中元素的连续非空序列。

特别注意整数包括负数，我做这题的时候想用剩余值来判断是否找到，直接爆了

双循环复杂度太高，采用前缀和来降低复杂度

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
function subarraySum(nums: number[], k: number): number {
    let result = 0

    // 当前连续子串和
    let sum = 0

    // 前缀和
    const map = new Map([[0,1]])

    for (let i = 0 ; i < nums.length ; i++) {
        sum += nums[i]
        // 如果当前和等于k则返回1，否则返回0
        result += map.get(sum - k) || 0
        // 更新前缀和
        map.set(sum, (map.get(sum) || 0) + 1)
    }

    return result
};

思路：使用前缀和Hash存储前原数组n个元素的总和，值为和出现的次数，由于前缀和数组中任意两个值相减都是原数组中某几个连续元素之和，因此我们可以逐步求原数组前n项之和sum，再查找sum-k是否存在hash中，如果存在则将次数加到结果中，否则则说明不存在连续元素之和等于目标值。由于当前sum的值与当前遍历的元素相关，且前缀和在遍历时更新，所以满足条件的元素一定是连续的（包括自身单个元素）。

当sum-k == 0时，则说明当前原数组前n个元素的总和就为目标值k。当sum-k为当前前缀和数组中任意元素时，则说明存在一组连续元素，使得他们的总和为目标值。

普通数组

最大子数组和

给你一个整数数组 nums ，请你找出一个具有最大和的连续子数组（子数组最少包含一个元素），返回其最大和。子数组是数组中的一个连续部分。

解法一：前缀和（线性DP）

1
2
3
4
5
6
7
8
9
10
11
12
13
function maxSubArray(nums: number[]): number {
    let result = -1000000
    let min = 0
    let sum = 0 

    for (let i = 0 ; i < nums.length; i++) {
        sum += nums[i]
        result = Math.max(result, sum - min)
        min = Math.min(sum, min)
    }

    return result
};

从前缀和思想来看，我们并不直接构造前缀和，而是在遍历过程中计算当前的前缀和。由于前缀和是前n个连续元素之和，我们保存当前遇到的最小前缀和，而后判断当前最大值与当前前缀和与最小前缀和之差大小，并将较大的那个作为新的最大值，而后更新最小前缀和。

从动态规划的思想来看，定义f[i]为考虑前 i 个元素，且第nums[i]必选的情况下，形成子数组的最大和。不难发现，仅考虑前i个元素，且nums[i]必然参与的子数组中。要么是nums[i]自己一个成为子数组，要么与前面的元素共同组成子数组。因此有状态转移方程：

由于 f[i] 仅依赖于 f[i−1] 进行转移，可使用有限变量进行优化，因此写出来的代码也是和上述前缀和角度分析的类似。

解法二：分治法

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
export function maxSubArray(nums: number[]): number {
    /**
     * 分治法
     * @param l - 左端点索引
     * @param r - 右端点索引
     */
    function divide(l: number, r: number) {
        if (l === r) {
            // 由于可能存在空数组，故与0比较作为最大值
            const max = Math.max(nums[l], 0)
            return [nums[l], max, max, max]
        }
        // 二分法划分子区间递归处理
        const mid = (l+r) >> 1
        const left = divide(l, mid), right = divide(mid+1, r)
        // 构造结果数组
        const result = Array(4).fill(0)
        // 结构为[sum, lm, rm, max]
        // [区间和，前缀最大值，后缀最大值，最大和]

        // 区间和等于左右子区间和之和
        result[0] = left[0] + right[0]

        // 前缀最大值可能为左子区间前缀最大值
        // 也可能是右子区间前缀最大值加上左子区间区间和
        result[1] = Math.max(left[1], left[0] + right[1])

        // 后缀最大值可能是右子区间后缀最大值
        // 或者右子区间区间和加上左子区间的后缀最大值
        result[2] = Math.max(right[2], right[0] + left[2])

        // 最大和可能是左子问题、右子问题
        // 或者跨越左右两个子问题的边界

        result[3] = Math.max(left[3], right[3], left[2] + right[1])

        return result

    }

    // 处理全为负数的情况
    const max = Math.max(...nums)
    if (max < 0) {
        return max
    }

    return divide(0, nums.length-1)[3]

};

“分治法”的核心思路是将大问题拆分成更小且相似的子问题，通过递归解决这些子问题，最终合并子问题的解来得到原问题的解。实现分治，关键在于对“递归函数”的设计（入参 & 返回值）。

具体的，我们可以将返回值设计成四元组，分别代表 区间和，前缀最大值，后缀最大值 和 最大子数组和，用 [sum, lm, rm, max] 表示。

合并区间

以数组 intervals 表示若干个区间的集合，其中单个区间为 intervals[i] = [starti, endi] 。请你合并所有重叠的区间，并返回 一个不重叠的区间数组，该数组需恰好覆盖输入中的所有区间 。

思路：先根据区间左值排序，然后判断是否重叠即可。

解法一：暴力

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
function merge(intervals: number[][]): number[][] {
    let result: number[][] = []

    intervals.sort((a, b) => {
        return a[0]-b[0]
    })

    // l 始终指向第一个元素
    let l = 0
    let r = 1
    
    while (intervals.length > 0) {

        if (r === 0 || intervals.length === 1) {
            // 说明只剩下唯一一个元素，直接加入结果中
            result.push(intervals[l])
            // console.log("result", result)

            intervals.shift()
            break
        }
        
        if (intervals[l][1] >= intervals[r][0]) {
            // 合并到右指针位置的数组
            intervals[r] = [intervals[l][0], Math.max(intervals[r][1], intervals[l][1])]
            // 移除被合并的数组
            intervals.shift()
            // 此时在更新后的intervals中r为l的下一位

        } else {
            // 不存在重叠，则将第一个数组保存后，移出intervals
            result.push(intervals[l])
            intervals.shift()

            // 如果只剩下一个元素，则 l = r
            if (intervals.length === 1) {
                r = l
            }
        }
        
    }

    return result
};

解法二

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
function merge(intervals: number[][]): number[][] {
    
    intervals.sort((a, b) => {
        return a[0]-b[0]
    })
    
    let result: number[][] = [intervals[0]]

    for (let i = 0 ; i < intervals.length ; i++) {
        let item = intervals[i]
        let lastItem = result[result.length - 1]
        // 将当前遍历的数组与结果数组的末尾数组进行比较
        if (item[0] <= lastItem[1]) {
            // 满足则说明有重复，更新末位数组
            lastItem[1] = Math.max(lastItem[1], item[1])
        } else {
            // 否则直接添加到结果数组中
            result.push(item)
        }
    }
    
    return result
};

轮转数组

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

解法一：暴力

1
2
3
4
5
6
7
function rotate(nums: number[], k: number): void {
    let r = nums.length - 1
    for (let i = 0 ; i < k ; i++) {
        nums.unshift(nums[r])
        nums.pop()
    }
 };

解法二

1
2
3
4
5
6
7
8
9
10
function rotate(nums: number[], k: number): void {
    let n = nums.length
    const result: number[] = [] 
    for (let i = 0 ; i < n ; i++) {
       result[(i+k) % n] = nums[i]
    }
    for (let i = 0 ; i < n ; i++) {
        nums[i] = result[i]
    }
 };

除自身以外数组的乘积

给你一个整数数组 nums，返回 数组 answer ，其中 answer[i] 等于 nums 中除 nums[i] 之外其余各元素的乘积 。

题目数据 保证 数组 nums之中任意元素的全部前缀元素和后缀的乘积都在 32 位 整数范围内。

请 不要使用除法，且在 O(n) 时间复杂度内完成此题。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
function productExceptSelf(nums: number[]): number[] {
    let result: number[] = []

    let n = nums.length
    // 前缀积和后缀积
    let prefix = [1]
    let suffix = [1]


    for (let i = 1; i < n; i++) {
        prefix[i] = nums[i - 1] * prefix[i-1]
        suffix[i] = nums[n - i] * suffix[i-1]
    }

    for (let i = 0; i < n; i++) {
        result[i] = prefix[i] * suffix[n-i-1]
    }


    return result

};

思路：计算长度为nums.length的前缀积和后缀积，将前缀积与后缀积倒序相乘即可得到。特别注意这里前缀积和后缀积不计算超过nums.length-1个乘数相乘的乘积，毕竟我们要求的是某一个元素除自身以外数组的乘积。

我们可以改进该算法的空间复杂度为，即用结果数组充当前缀积数组，另外用一个变量记录当前后缀积，在计算当前后缀积的同时计算各个元素除自身以外数组的乘积：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
function productExceptSelf(nums: number[]): number[] {
    let result: number[] = []

    let n = nums.length
    // 前缀积和后缀积

    for (let i = 0; i < n-1; i++) {
        result[i+1] = nums[i] * result[i]
    }

    let suffix = 1
    for (let i = n - 1; i >= 0 ; i--) {
        result[i] = result[i]*suffix
        suffix *= nums[i]
    }

    return result

};

矩阵

矩阵置零

给定一个 的矩阵，如果一个元素为 0 ，则将其所在行和列的所有元素都设为 0 。请使用 原地 算法。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
function setZeroes(matrix: number[][]): void {
   let n = matrix.length
   let m = matrix[0].length

   // 记录第一列是否为0
   let isZero = false
   
   for (let i = 0; i < n; i++) {
       if (matrix[i][0] === 0) isZero = true
        for (let j = 1; j< m; j++) {
            if (matrix[i][j] === 0) {
                // 第一行记录列为0情况
                matrix[0][j] = 0
                // 第一列记录行为0情况
                matrix[i][0] = 0
            }
        }
   }

   // 为防止污染，我们需要倒序遍历行
   for (let i = n - 1; i >= 0; i--) {
        for (let j = 1; j < m; j++) {
            if (matrix[i][0] === 0 || matrix[0][j] === 0) {
                matrix[i][j] =0
            }
        }

        if (isZero) {
            matrix[i][0] = 0
        }
   }
 };

思路：当然我们也可以用额外的数组来记录行列为0的情况，这里我们只介绍空间复杂度为 的算法。我们知道只要某一行或某一列中含有0，则这个元素对应的行列均为0，于是我们就可以利用矩阵本身来记录行列为0的信息。我们先遍历一遍矩阵找到所有为0的元素，在这个过程中我们新建一个布尔值变量记录第一列是否含有0，接下来就只需要查找除了第一列以外的矩阵中元素为0的位置即可。最后我们根据布尔标记以及第一行和第一列的信息将对应的行列置零即可。

螺旋矩阵

给你一个 m 行 n 列的矩阵 matrix ，请按照 顺时针螺旋顺序 ，返回矩阵中的所有元素。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
function spiralOrder(matrix: number[][]): number[] {
    let result: number[] = []
    
    let m = matrix.length
    let n = matrix[0].length

    for (let i = 0; i < m; i++) {
        // 向右
        for (let j = i; j < n - i; j++) {
            if (matrix[i][j] !== undefined) {
                result.push(matrix[i][j])
            } else {
                continue
            }
        }
        // 向下
        for (let j = i + 1; j < m - i; j++) {
            if (matrix[j][n - i - 1] !== undefined) {
                result.push(matrix[j][n - i - 1])
            } else {
                continue
            }
        }
        // 向左
        for (let j = n - i - 2; j >= i; j--) {
            if (matrix[m - i - 1][j] !== undefined ) {
                result.push(matrix[m - i - 1][j])
            } else {
                continue
            }
        }
        // 向上
        for (let j = m - i - 2; j >= i + 1; j--) {
            if (matrix[j][i] !== undefined) {
                result.push(matrix[j][i])
            } else {
                continue
            }
        }
    }



    return result.slice(0, m * n)
};

思路：一次循环分为右下左上四步，分别找到对应的起始位置并按顺序添加到结果数组中即可。

旋转图像

给定一个 的二维矩阵 matrix 表示一个图像。请你将图像顺时针旋转 90 度。

你必须在原地旋转图像，这意味着你需要直接修改输入的二维矩阵。请不要 使用另一个矩阵来旋转图像。

解法一：置换

1
2
3
4
5
6
7
8
9
10
11
12
13
function rotate(matrix: number[][]): void {
    let n = matrix.length
    for (let i = 0; i < Math.floor(n / 2); i++) {
        for (let j = 0; j < Math.floor((n + 1) / 2); j++) {
            const temp = matrix[i][j]
            matrix[i][j] = matrix[n-j-1][i]
            matrix[n-j-1][i] = matrix[n-i-1][n-j-1]
            matrix[n-i-1][n-j-1] = matrix[j][n-i-1]
            matrix[j][n-i-1] = temp
        }
    }

};

思路：找到要交换的四个元素之间的位置关系，按顺序交换即可。

解法二：翻转

1
2
3
4
5
6
7
8
9
function rotate(matrix: number[][]): void {
   matrix.reverse()

   for(let i = 0;i < matrix.length;i++){
    for(let j = 0;j < i;j++){
        [matrix[i][j],matrix[j][i]] = [matrix[j][i],matrix[i][j]]
    }
   }
};

思路：将整个矩阵沿对角线翻转后，将各个元素按 对称互换即可。

我自己做的时候是把各行翻转，处理对称较为麻烦

搜索二维矩阵 II

编写一个高效的算法来搜索 矩阵 matrix 中的一个目标值 target 。该矩阵具有以下特性：

  • 每行的元素从左到右升序排列。
  • 每列的元素从上到下升序排列。

解法一：暴力解

逐个遍历逐个判断，时间复杂度 。

解法二：二分查找

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
function searchMatrix(matrix: number[][], target: number): boolean {
    // Z查找
    const search = (row: number[], target: number) => {
        let start = 0
        let end = row.length - 1
        while(start <= end) {
            const mid = Math.floor((end + start) / 2)
            const midNum = row[mid]
            if (midNum === target) {
                return mid
            } else if (midNum >= target) {
                end = mid - 1
            } else {
                start = mid + 1
            }
        }

        return -1

    }

    for (let i = 0; i < matrix.length; i++) {
        const index = search(matrix[i], target)
        if (index >= 0) {
            return true
        }
    }

    return false

};

思路：按行二分查找，较为通用的解法，时间复杂度为 。

解法三：Z型查找

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
function searchMatrix(matrix: number[][], target: number): boolean {
    // Z查找
    const m = matrix.length
    const n = matrix[0].length

    let x = 0, y = n - 1
    while (x < m && y >= 0) {
        if (matrix[x][y] > target) {
            y--
        } else if (matrix[x][y] < target) {
            x++
        } else {
            return true
        }
    }

    return false

};

思路：注意到本题特殊条件：

  • 每行的元素从左到右升序排列。
  • 每列的元素从上到下升序排列。

于是我们可以从矩阵的右上角开始查找，即x = 0, y = n - 1，如果当前元素大于目标值，则说明第y列中不存在等于目标值的元素，y递减；如果当前元素小于目标值，则说明第y列中不存在等于目标值的元素，x递增。

链表

相交链表

给你两个单链表的头节点 headA 和 headB ，请你找出并返回两个单链表相交的起始节点。如果两个链表不存在相交节点，返回 null 。题目数据 保证 整个链式结构中不存在环。

注意，函数返回结果后，链表必须 保持其原始结构 。

解法一：哈希

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
function getIntersectionNode(headA: ListNode | null, headB: ListNode | null): ListNode | null {
    let set: Set<ListNode> = new Set;

    let curr = headA;
    while (curr !== null) {
        set.add(curr);
        curr = curr.next;
    }

    curr = headB;
    while (curr !== null) {
        if (set.has(curr)) return curr;
        curr = curr.next;
    }

    return null;
};

思路：先遍历A链表并将所有节点存入集合中，再遍历B链表找到集合中存在的第一个相同的节点。

解法二：双指针遍历

1
2
3
4
5
6
7
8
9
10
11
12
13
function getIntersectionNode(headA: ListNode | null, headB: ListNode | null): ListNode | null {
    if (headA === null || headB === null) return null
    
    let pA: ListNode | null = headA
    let pB: ListNode | null = headB

    while (pA !== pB) {
        pA = pA === null ? headB : pA.next
        pB = pB === null ? headA : pB.next
    }

    return pA
};

思路：创建两个指针分别遍历链表A和B，遍历完当前链表时将指针指向另一链表，开始遍历，由于相交后的节点都相同，当两指针指向同一节点时，该节点就是交点。

反转链表

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

解法一：暴力解法

思路：用另一个数组存倒过来的链表，再根据数组按顺序新建一个新的链表即可

解法二：双指针

1
2
3
4
5
6
7
8
9
10
11
12
function reverseList(head: ListNode | null): ListNode | null {
    let preNode: ListNode | null = null,
        curNode: ListNode | null = head,
        tempNode: ListNode | null;
    while (curNode) {
        tempNode = curNode.next;
        curNode.next = preNode;
        preNode = curNode;
        curNode = tempNode;
    }
    return preNode;
};

思路：用双指针，指针curNode指向当前节点，指针preNode指向当前节点的前一节点，移动时修改链表指向，将当前节点指向前一节点。

回文链表

给你一个单链表的头节点 head ，请你判断该链表是否为回文链表。如果是，返回 true ；否则，返回 false 。

解法一：暴力解

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
function isPalindrome(head: ListNode | null): boolean {
    if (head === null) return false
    
    let p: ListNode | null = head
    // 存储遇到过的字符
    let viewed: number[] = []
    while(p) {
       viewed.push(p.val)
       p = p.next
    }

    for (let i = 0, j = viewed.length - 1; i !== j; i++, j--) {
        if (viewed[i] !== viewed[j]) {
            return false
        }
    }

    return true
};

思路：求出倒叙后的链表，与原链表一一比对。

思路二：递归

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
function isPalindrome(head: ListNode | null): boolean {
    if (head === null) return false
    let preNode: ListNode | null = head
    return recursive(head)
    function recursive(node: ListNode | null) {
        if (!node) {
            return true
        }
        let result = recursive(node.next)
        if (preNode) {
            result = result && node.val === preNode.val
            preNode = preNode.next
            return result
        }

    }

};

思路：由于递归的思想时逐层寻找满足条件的元素，而后倒序处理各个元素（后序遍历），我们可以利用这一特点在倒序处理时一一比较是否满足回文。

思路三：快慢指针

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
const reverseList = (head: ListNode | null): ListNode | null => {
    let prev: ListNode | null = null;
    let curr: ListNode | null = head;
    while (curr !== null) {
        let nextTemp: ListNode | null = curr.next;
        curr.next = prev;
        prev = curr;
        curr = nextTemp;
    }
    return prev;
}

const endOfFirstHalf = (head: ListNode | null): ListNode | null => {
    let fast: ListNode = head as ListNode;
    let slow: ListNode = head as ListNode;
    while (fast !== null && fast.next !== null && fast.next.next !== null) {
        fast = fast.next.next;
        slow = slow.next as ListNode;
    }
    return slow;
}

function isPalindrome(head: ListNode | null): boolean {
    if (head === null) return true;

    // 找到前半部分链表的尾节点并反转后半部分链表
    const firstHalfEnd: ListNode = endOfFirstHalf(head) as ListNode;
    const secondHalfStart: ListNode = reverseList(firstHalfEnd.next) as ListNode;

    // 判断是否回文
    let p1: ListNode | null = head;
    let p2: ListNode | null = secondHalfStart;
    let result: boolean = true;
    while (result && p2 !== null) {
        if (p1!.val !== p2!.val) result = false;
        p1 = p1!.next;
        p2 = p2!.next;
    }

    // 还原链表并返回结果
    firstHalfEnd.next = reverseList(secondHalfStart);
    return result;
}

思路：利用前面实现的倒序算法以及快慢指针，快指针每次移动两个单位，慢指针每次移动一个单位，当快指针遍历完毕时，慢指针恰好位于中位，此时将链表对半分为两个部分，将后半部分倒序并与前半部分比较即可。

环形链表

给你一个链表的头节点 head ，判断链表中是否有环。

如果链表中有某个节点，可以通过连续跟踪 next 指针再次到达，则链表中存在环。 为了表示给定链表中的环，评测系统内部使用整数 pos 来表示链表尾连接到链表中的位置（索引从 0 开始）。注意：pos 不作为参数进行传递 。仅仅是为了标识链表的实际情况。

如果链表中存在环 ，则返回 true 。 否则，返回 false 。

1
2
3
4
5
6
7
8
9
10
11
12
function hasCycle(head: ListNode | null): boolean {
    let fast = head, slow = head
    while (fast && fast.next && slow) {
        // 慢指针走一步，快指针走两步
        slow = slow.next
        fast = fast.next.next
        if (slow === fast) {
            return true
        }
    }
    return false
};

思路：使用快慢指针。与前面思路类似，快指针每次移动两个单位，慢指针每次移动一个单位，如果存在环形链路，由于快指针移动比慢指针快，快指针最终会与慢指针相遇，此时返回true，否则返回false。

环形链表 II

给定一个链表的头节点 head ，返回链表开始入环的第一个节点。 如果链表无环，则返回 null。

如果链表中有某个节点，可以通过连续跟踪 next 指针再次到达，则链表中存在环。 为了表示给定链表中的环，评测系统内部使用整数 pos 来表示链表尾连接到链表中的位置（索引从 0 开始）。如果 pos 是 -1，则在该链表中没有环。注意：pos 不作为参数进行传递，仅仅是为了标识链表的实际情况。不允许修改 链表。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
function detectCycle(head: ListNode | null): ListNode | null {
    let fast = head, slow = head
    while (fast && slow) {
        // 慢指针走一步，快指针走两步
        if (fast.next) {
            slow = slow.next
            fast = fast.next.next
            if (slow === fast) {
                break
            }

        } else {
            return null
        }
    }

    let pre = head
    while (pre && slow) {
        if (pre === slow) {
            return slow
        } 
        pre = pre.next
        slow = slow.next
    }
    return null
};

思路：接续上一题环形链表的思路，如果存在环路，我们先找到快慢指针相遇的位置。接下来我们来计算相交位置与慢指针之间的关系。我们设交点位置 ，慢指针相对于交点长度为 ，慢指针相对于链表末尾的长度为 ，不难发现快指针与慢指针走过的距离关系为 ，化简可以得到 ，于是有 ，所以如果我们设置一个新的指针指向链表头，与慢指针同时移动，在慢指针再次遍历一定次数后，两指针将会在环起点重合，此时我们就找到了链表开始入环的第一个节点。

合并两个有序链表

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

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
function mergeTwoLists(list1: ListNode | null, list2: ListNode | null): ListNode | null {
    let p1 = list1
    let p2 = list2
    let result: ListNode = new ListNode(), cur = result
    

    while (list1 && list2) {
        if (list1.val <= list2.val) {
            cur.next = list1
            list1 = list1.next
        } else if (list1.val > list2.val) {
            cur.next = list2
            list2 = list2.next
        }

        
        cur = cur.next as ListNode
    
        
    }

    // 补充剩下的节点
    cur.next = list1 ?? list2


    return result.next
};

思路：使用双指针，分别遍历两个链表，将当前的两个节点中较小的节点移入结果链表中，并移动对应的指针。

两数相加

给你两个 非空 的链表，表示两个非负的整数。它们每位数字都是按照 逆序 的方式存储的，并且每个节点只能存储 一位 数字。

请你将两个数相加，并以相同形式返回一个表示和的链表。

你可以假设除了数字 0 之外，这两个数都不会以 0 开头。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
function addTwoNumbers(l1: ListNode | null, l2: ListNode | null): ListNode | null {
    let result = new ListNode(0), cur = result
    // 进位标记
    let carry = 0

    while(carry || l1 || l2) {
        let val1 = l1?.val || 0
        let val2 = l2?.val || 0

        let sum = val1 + val2 + carry

        sum >= 10 ? carry = 1 : carry = 0

        cur.next = new ListNode(sum % 10)
        cur = cur.next

        if (l1) l1 = l1.next
        if (l2) l2 = l2.next

    }

    return result.next
};

思路：双指针同时移动，计算当前数位的和，如果超过十则进位，将和模10后存入链表对应位置，直到双指针都遍历完成且不存在进位情况。

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

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

解法一：翻转链表

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
function reverseList(head: ListNode | null): ListNode | null {
    let preNode: ListNode | null = null,
        curNode: ListNode | null = head,
        tempNode: ListNode | null;
    while (curNode) {
        tempNode = curNode.next;
        curNode.next = preNode;
        preNode = curNode;
        curNode = tempNode;
    }
    return preNode;
};

function removeNthFromEnd(head: ListNode | null, n: number): ListNode | null {
    // 翻转链表
    let result = reverseList(head), curSlow = new ListNode(-1, result), curFast = result
    // 找到倒数第 n 个结点的前一个节点
    for (let i = 0; i < n-1; i++) {
        // 删除节点的上一节点
        curSlow = (curSlow as ListNode).next
        // 要删除的节点
        curFast = (curFast as ListNode).next
    }
    // 删除节点
    if (curSlow && curFast) {
        if (curFast.next) {
            if (curSlow.val === -1) {
                return reverseList(curFast.next)
            }
            curSlow.next = curFast.next
        } else {
            if (curSlow.val === -1) {
                return null
            } else {
                curSlow.next = null
            }
        }
    }
    return reverseList(result)
};

解法二：快慢指针

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
function removeNthFromEnd(head: ListNode | null, n: number): ListNode | null {

    let result = new ListNode(-1, head)
   // 快慢指针
    let fast = result
    let slow = result

   // 快指针先移动 n 次
    while (n-- >= 0 && fast) {
        fast = fast.next as ListNode
    }

    // 一起移动，当fast处于链表末尾时，slow恰好位于要删除的元素的前一个节点
    while (fast && slow) {
        fast = fast.next as ListNode
        slow = slow.next as ListNode
    }

    // 删除节点
    slow!.next = slow!.next?.next ?? null

    return result.next

};

思路：快指针先走过 n 个单位，这样当快指针到达链表末尾时，慢指针恰好指向要删除的链表节点的前一节点。

两两交换链表中的节点

给你一个链表，两两交换其中相邻的节点，并返回交换后链表的头节点。你必须在不修改节点内部的值的情况下完成本题（即，只能进行节点交换）。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
function swapPairs(head: ListNode | null): ListNode | null {
    const result = new ListNode(-1, head)
    let cur = result

    while (cur && cur.next && cur.next.next) {
        let first: ListNode = cur.next,
            sec: ListNode = cur.next.next,
            third: ListNode | null = cur.next.next.next;
        cur.next = sec;
        sec.next = first;
        first.next = third;
        cur = first;
    }

    return result.next
};

思路：采用虚表头，这样我们可以找到每一个节点的前置节点，方便进行交换，交换过程如下图橙色实线。

随机链表的复制

给你一个长度为 n 的链表，每个节点包含一个额外增加的随机指针 random ，该指针可以指向链表中的任何节点或空节点。

构造这个链表的 深拷贝。 深拷贝应该正好由 n 个 全新 节点组成，其中每个新节点的值都设为其对应的原节点的值。新节点的 next 指针和 random 指针也都应指向复制链表中的新节点，并使原链表和复制链表中的这些指针能够表示相同的链表状态。复制链表中的指针都不应指向原链表中的节点 。

例如，如果原链表中有 X 和 Y 两个节点，其中 X.random --> Y 。那么在复制链表中对应的两个节点 x 和 y ，同样有 x.random --> y 。

返回复制链表的头节点。

用一个由 n 个节点组成的链表来表示输入/输出中的链表。每个节点用一个 [val, random_index] 表示：

  • val：一个表示 Node.val 的整数。
  • random_index：随机指针指向的节点索引（范围从 0 到 n-1）；如果不指向任何节点，则为 null 。

你的代码 只 接受原链表的头节点 head 作为传入参数。

解法一：迭代

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
// 迭代+拼接
function copyRandomList(head: Node | null): Node | null {
    if (head === null) return head;

    let curr = head;
    // 在原链表每一个节点后，续接一个新节点
    while (curr) {
        let tempNode = new Node(curr.val);

        tempNode.next = curr.next;
        curr.next = tempNode;
        curr = tempNode.next;
    }

    // 为当前链表的每一个新节点的 random 属性赋值
    curr = head;
    while (curr && curr.next) {
        if (curr.random) {
            // 为新节点的 random 赋值为原链表中应该的 random 指向的节点的相应的新节点
            curr.next.random = curr.random.next;
        }
        curr = curr.next.next;
    }

    // 将链表，按照一个间隔一个的顺序拆分开
    //  1、将新节点，串成一个新链表
    //  2、将原链表的节点，拆出来并组合成原链表
    curr = head.next;
    let preNode = head; // 原链表
    let newLinkList = head.next; // 新链表
    while (curr && curr.next) {
        preNode.next = preNode.next.next;
        curr.next = curr.next.next;
        preNode = preNode.next;
        curr = curr.next;
    }

    preNode.next = null;    // 将原链表的最后一个节点的 next 指针重新指向 null

    return newLinkList;
};

思路：在每个节点后复制一个一样的节点，再根据原节点为新节点的random赋值，最后去掉原节点即可。

解法二：哈希表

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
function copyRandomList(head: _Node | null): _Node | null {
    if (!head) return null

    let p = head
    let result = new _Node()
    let cur: _Node | null = result
    // 用哈希存储新旧节点对应关系
    let map = new Map<_Node | null, _Node | null>()

    // 先复制各个节点
    while (p) {
        cur!.val = p.val
        cur!.next = p.next ? new _Node() : null

        map.set(p, cur)

        cur = cur!.next
        p = p.next
    }

    cur = result
    // 处理随机指针
    while (head) {
        cur!.random = (head.random ? map.get(head.random) : null) as _Node | null
        cur = cur!.next
        head = head.next
    }


    return result

};

思路：哈希表存储原链表和复制后的链表节点的一一对应关系，并将random设置为空。在遍历完第一遍原链表后，再遍历一遍原链表，此时根据原链表的random信息来处理复制后新链表节点的random。

排序链表

给你链表的头结点 head ，请将其按 升序 排列并返回 排序后的链表 。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
function sortList(head: ListNode | null): ListNode | null {
    if (head == null || head.next == null) {
        return head
    }

    let fast: ListNode | null = head.next
    let slow: ListNode | null = head 

    // 将链表分为两个部分，slow为中位
    while (fast && slow && fast.next) {
        slow = slow.next
        fast = fast.next.next
    }

    let rightHead = slow!.next
    // 分割链表
    slow!.next = null

    let left = sortList(head)
    let right = sortList(rightHead)

    return mergeTwoLists(left, right)
};

function mergeTwoLists(list1: ListNode | null, list2: ListNode | null): ListNode | null {
    let p1 = list1
    let p2 = list2
    let result: ListNode = new ListNode(), cur = result
    
    while (list1 && list2) {
        if (list1.val <= list2.val) {
            cur.next = list1
            list1 = list1.next
        } else if (list1.val > list2.val) {
            cur.next = list2
            list2 = list2.next
        }

        
        cur = cur.next as ListNode
    
        
    }

    // 补充剩下的节点
    cur.next = list1 ?? list2


    return result.next
};

思路：使用分治法，将原链表不停的对半分开排序，最后用之前实现的合并排序两个升序链表的思路处理每对链表。

LRU缓存

请你设计并实现一个满足 LRU (最近最少使用) 缓存 约束的数据结构。

实现 LRUCache 类：

  • LRUCache(int capacity) 以 正整数 作为容量 capacity 初始化 LRU 缓存
  • int get(int key) 如果关键字 key 存在于缓存中，则返回关键字的值，否则返回 -1 。
  • void put(int key, int value) 如果关键字 key 已经存在，则变更其数据值 value ；如果不存在，则向缓存中插入该组 key-value 。如果插入操作导致关键字数量超过 capacity ，则应该 逐出 最久未使用的关键字。

函数 get 和 put 必须以 O(1) 的平均时间复杂度运行。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
class LRUCache {
  capacity: number
  map: Map<number, number> = new Map()

  constructor(capacity: number) {
    // 利用迭代器实现
    this.map = new Map()
    // 设置缓存最大个数
    this.capacity = capacity
  }

  get(key: number): number {
    if (this.map.has(key)) {
      let value = this.map.get(key)
      // 重新 set，相当于更新到 map 最后
      this.map.delete(key)
      this.map.set(key, value)
      return value
    } 
    return -1
  }

  put(key: number, value: number): void {
    // 如果有，就删了再赋值
    if (this.map.has(key)) {
      this.map.delete(key)
    }

    this.map.set(key, value)

    // 判断是不是容量超了，淘汰机制
    if (this.map.size > this.capacity) {
      this.map.delete(this.map.keys().next().value)
    }
  }
}

思路：主要是理解LRU的原理，缓存未满直接存入，如果缓存已满，则移除最旧的数据给新的数据腾出位置。

二叉树

二叉树的中序遍历

给定一个二叉树的根节点 root ，返回 它的 中序 遍历 。

解法一：递归

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
function inorderTraversal(root: TreeNode | null): number[] {
    let result: number[] = []

    const dfs = (root: TreeNode | null) => {
        if (!root) {
            return 
        }

        dfs(root!.left)
        result.push(root!.val)
        dfs(root!.right)

    }

    dfs(root)

    return result
};

解法二：栈

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
function inorderTraversal(root: TreeNode | null): number[] {
    const stk: TreeNode[] = [];
    const result: number[] = [];
    while (root || stk.length > 0) {
        if (root) {
            stk.push(root);
            root = root.left;
        } else {
            root = stk.pop() as TreeNode | null
            result.push(root!.val)
            root = root!.right
        }
    }
    return result;

}

二叉树的最大深度

给定一个二叉树 root ，返回其最大深度。

二叉树的 最大深度 是指从根节点到最远叶子节点的最长路径上的节点数。

解法一：递归

1
2
3
4
5
6
function maxDepth(root: TreeNode | null): number {
    let result: number = 0
    if (!root) return result

    return 1 + Math.max(maxDepth(root.left), maxDepth(root.right))
};

思路：后序遍历精简版，由于我们只需比较左右子树的深度，最后返回最大值，由此去掉了根节点步骤。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
function maxDepth(root: TreeNode | null): number {
    let result: number = 0
    const getDepth = (node: TreeNode | null, depth: number) => {
        result = Math.max(result, depth) 
        // 没有左右节点则说明是叶节点，结束递归
        if (node.left === null && node.right === null) return

        // 分别遍历左右节点
        if (node.left) {
            getDepth(node.left, depth + 1)
        }
        if (node.right) {
            getDepth(node.right, depth + 1)
        }
        return 
    }

    if (!root) return result
    getDepth(root, 1)

    return result
};

解法二：迭代（层序遍历）

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
function maxDepth(root: TreeNode | null): number {
    let result: number = 0
    if (!root) return result
    
    // 用队列存储遍历过的节点
    let queue: Array<TreeNode | null>= []
    // 存储根节点
    queue.push(root)

    while (queue[0]) {
        let size = queue.length
        // 非空则说明有新的层数
        result++
        for (let i = 0; i < size; i++) {
            // 获取队首节点
            let node = queue[0]
            queue.shift()
            if (node.left) {
                queue.push(node.left)
            }
            if (node.right) {
                queue.push(node.right)
            }
        }
    }


    return result
};

思路：用队列存储遍历过的节点的子节点，此时队列长度就是当前层次中包含节点的个数，由此我们创建一个内循环处理各个层次节点，完成层序遍历。

翻转二叉树

给你一棵二叉树的根节点 root ，翻转这棵二叉树，并返回其根节点。

1
2
3
4
5
6
7
8
9
10
11

function invertTree(root: TreeNode | null): TreeNode | null {
    if (root === null) return root;
    let tempNode: TreeNode | null = root.left;
    root.left = root.right;
    root.right = tempNode;
    invertTree(root.left);
    invertTree(root.right);
    return root;

};

思路：遍历每个节点的左右子节点并交换。

对称二叉树

给你一个二叉树的根节点 root ， 检查它是否轴对称。

解法一：递归

1
2
3
4
5
6
7
8
9
10
11
12
function isSymmetric(root: TreeNode | null): boolean {

    return check(root, root)

    function check(l: TreeNode | null, r: TreeNode | null) {
        if (!l && !r) return true
        if (!l || !r) return false

        return l.val === r.val && check(l.left, r.right) && check(l.right, r.left)
    }

};

思路：使用双指针分别遍历根节点的左右子树，根据轴对称条件判断左右子树是否满足，在没有子节点或只存在左右只存在一个子节点时停止递归。

解法二：迭代

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
function isSymmetric(root: TreeNode | null): boolean {
    let l = root
    let r = root
    let queue: Array<TreeNode | null> = [l, r]

    while (queue.length) {
        l = queue.shift()!
        r = queue.shift()!

        if (!l && !r) continue
        if (!l || !r || l.val !== r.val) return false

        queue.push(l.left)
        queue.push(r.right)

        queue.push(l.right)
        queue.push(r.left)


    }

    return true

};

思路：同递归法，不过用了队列来去除递归，这也是将递归转为迭代的常用方法之一。

二叉树的直径

给你一棵二叉树的根节点，返回该树的 直径 。

二叉树的 直径 是指树中任意两个节点之间最长路径的 长度 。这条路径可能经过也可能不经过根节点 root 。

两节点之间路径的 长度 由它们之间边数表示。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
function diameterOfBinaryTree(root: TreeNode | null): number {
    let result = 0
    function maxDepth(root: TreeNode | null): number {
        if (!root) return 0
        let leftDepth = maxDepth(root!.left)
        let rightDepth = maxDepth(root!.right)

        result = Math.max(result, leftDepth + rightDepth)

        // 返回当前节点的最大深度
        return 1 + Math.max(leftDepth, rightDepth)
    }

    maxDepth(root)

    return result
};

思路：最长路径的 长度 就是各节点左右子树深度和的最大值，只需要遍历一遍二叉树并找出这个最大值即可。

二叉树层序遍历

给你二叉树的根节点 root ，返回其节点值的 层序遍历 。 （即逐层地，从左到右访问所有节点）。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
function levelOrder(root: TreeNode | null): number[][] {
    let queue: Array<TreeNode | null> = []
    let result: number[][] = [] 

    if (root) {
        queue.push(root)
    }
    
    while (queue.length) {

        let cur: number[] = []
        
        // 当前队列长度就是该层的节点个数，由于queue会变化，注意不能直接 i < queue.length
        for (let i = 0, len = queue.length; i < len; i++) {
            let node = queue.shift()!
            cur.push(node.val)

            // 将当前节点的左右节点存入队列中
            if (node.left) {
                queue.push(node.left)
            }
            if (node.right) {
                queue.push(node.right)
            }
        }
        result.push(cur)

    }

    return result
};

将有序数组转换为二叉搜索树

给你一个整数数组 nums ，其中元素已经按 升序 排列，请你将其转换为一棵平衡二叉搜索树。

平衡二叉树 是指该树所有节点的左右子树的深度相差不超过 1。

1
2
3
4
5
6
7
8
9
10
11
12
13
function sortedArrayToBST(nums: number[]): TreeNode | null {
    
    let mid = Math.ceil(nums.length / 2)
    let result = new TreeNode(nums[mid - 1])

    if (nums.length === 0) return null

    result.left = sortedArrayToBST(nums.slice(0, mid-1))
    result.right = sortedArrayToBST(nums.slice(mid, nums.length))

    return result

};

思路：分治法递归，每次对半处理数组，并将数组中点添加到结果中。

验证二叉搜索树

给你一个二叉树的根节点 root ，判断其是否是一个有效的二叉搜索树。

有效 二叉搜索树定义如下：

  • 节点的左子树只包含 小于 当前节点的数。
  • 节点的右子树只包含 大于 当前节点的数。
  • 所有左子树和右子树自身必须也是二叉搜索树。

解法一：中序遍历

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
function isValidBST(root: TreeNode | null): boolean {
    let maxVal = -Infinity;
    function inorderTraverse(root: TreeNode | null): boolean {
        if (root === null) return true;
        
        let leftValid: boolean = inorderTraverse(root.left);
        if (!leftValid) return false;
        
        if (maxVal < root.val) {
            maxVal = root.val
        } else {
            return false;
        }
        
        let rightValid: boolean = inorderTraverse(root.right);
        return leftValid && rightValid;
    }
    return inorderTraverse(root);
};

思路：不能单纯的比较左节点小于中间节点，右节点大于中间节点就完事了。采用中序遍历，先找到最左边的叶节点，在中序遍历时不断更新maxVal，如果maxVal >= root.val，则说明发现存在节点值不满足二叉搜索树的条件。当在遍历左子树时，出现上述情况说明节点的左子树存在大于等于当前节点的数，在遍历右子树时说明节点右子树存在小于等于当前节点的数。

解法二：辅助数组

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
function isValidBST(root: TreeNode | null): boolean {
    const traversalArr: number[] = [];
    function inorderTraverse(root: TreeNode | null): void {
        if (root === null) return;
        inorderTraverse(root.left);
        traversalArr.push(root.val);
        inorderTraverse(root.right);
    }
    inorderTraverse(root);
    for (let i = 0, length = traversalArr.length; i < length - 1; i++) {
        if (traversalArr[i] >= traversalArr[i + 1]) return false;
    }
    return true;
};

思路：用辅助数组存储中序遍历过的节点值，如果二叉树满足二叉搜索树，则该数组元素是递增排列的，否则说明该二叉树不是二叉搜索树。

二叉搜索树中第K小的元素

给定一个二叉搜索树的根节点 root ，和一个整数 k ，请你设计一个算法查找其中第 k 小的元素（从 1 开始计数）。

解法一：辅助数组

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
function inorderTraversal(root: TreeNode | null): number[] {
    const stk: TreeNode[] = [];
    const result: number[] = [];
    while (root || stk.length > 0) {
        if (root) {
            stk.push(root);
            root = root.left;
        } else {
            root = stk.pop() as TreeNode | null
            result.push(root!.val)
            root = root!.right
        }
    }
    return result;

}

function kthSmallest(root: TreeNode | null, k: number): number {
    const sorted: number[] = inorderTraversal(root)

    return sorted[k-1]
};

思路：中序遍历的二叉搜索树用数组存储后是数组元素是递增，第 k 个元素即为所求。

解法二：递归

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
function kthSmallest(root: TreeNode | null, k: number): number {
    let result = 0

    function dfs(root: TreeNode | null) {
        if (!root) return

        dfs(root!.left)

        if (k === 0) return 
        if (--k === 0) result = root.val
        dfs(root!.right)
    }

    dfs(root)
    return result
};

思路：第 k 次递归获得的元素就是第 k 小的元素。

二叉树的右视图

给定一个二叉树的 根节点 root，想象自己站在它的右侧，按照从顶部到底部的顺序，返回从右侧所能看到的节点值。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
function rightSideView(root: TreeNode | null): number[] {
    let result: number[] = []
    let queue: (TreeNode | null)[] = []

    if (root) queue.push(root)

    while (queue.length) {
        let len = queue.length
        let level: number[] =[]
        for (let i = 0; i < len; i++) {
            let node = queue.shift()!
            level.push(node.val)
            if (node.left) {
                queue.push(node.left)
            }
            if (node.right) {
                queue.push(node.right)
            }
        }
        result.push(level[level.length - 1])
    }

    return result
};

思路：层序遍历，当前层次的最后一个元素就是二叉树的右视图元素之一。

二叉树展开为链表

给你二叉树的根结点 root ，请你将它展开为一个单链表：

  • 展开后的单链表应该同样使用 TreeNode ，其中 right 子指针指向链表中下一个结点，而左子指针始终为 null 。
  • 展开后的单链表应该与二叉树 先序遍历 顺序相同。

解法一：辅助数组

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
function flatten(root: TreeNode | null): void {
    let cur = root;

    while (cur) {
        // 若当前节点存在子节点
        if (cur.left) {
            let p = cur.left;

            while (p.right) p = p.right;

            p.right = cur.right;
            cur.right = cur.left;

            cur.left = null;
        }
        cur = cur.right;
    }
};

思路：由于展开后的单链表与二叉树的先序遍历顺序相同，所以我们用指针cur指向当前节点，另一个指针p指向当前节点的左节点，并用p找到左节点的右叶节点，并将当前节点cur的右子树接到该右叶节点后，以便后续处理；而后将当前节点的左节点作为当前节点的右节点，赋值后，将当前当前节点的左节点置空，并向右子节点移动当前节点，直至当前节点为空。

解法二：递归

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
function flatten(root: TreeNode | null): void {
    if (!root) return;
    flattenHelper(root);
}

function flattenHelper(node: TreeNode): void {
    if (!node) return;
    
    flattenHelper(node.left);
    flattenHelper(node.right);

    // 存储当前节点右子树
    let temp = node.right;

    // 将左子树设置为右子树，并置空左子树
    node.right = node.left;
    node.left = null;

    // 找到右子树的终点
    while (node.right) {
        node = node.right;
    }

    // 将当前节点的右子树接到该右叶节点
    node.right = temp;
}

前序中序遍历序列构造二叉树

给定两个整数数组 preorder 和 inorder ，其中 preorder 是二叉树的先序遍历， inorder 是同一棵树的中序遍历，请构造二叉树并返回其根节点。

解法一：暴力递归

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
function buildTree(preorder: number[], inorder: number[]): TreeNode | null {
    let len = preorder.length
    // 前序第一个节点即为根节点
    let rootVal = preorder[0]
    let root = new TreeNode(rootVal)

    // 当前序数组为空时，返回空节点
    if (len === 0) return null
    
    // 获取根节点在中序中的索引
    let rootIndex = inorder.indexOf(rootVal)
    // 获取左子树和右子树
    let leftInorder = inorder.slice(0, rootIndex)
    let leftPreorder = preorder.slice(1, 1 + leftInorder.length)
    let rightInorder = inorder.slice(rootIndex+1, len)
    let rightPreorder = preorder.slice(1 + leftInorder.length, len)

    root.left = buildTree(leftPreorder, leftInorder)
    root.right = buildTree(rightPreorder, rightInorder)
    

    return root
};

思路：根据前序遍历和中序遍历的特点，我们能够知道前序遍历的第一个节点就是根节点，而在中序遍历序列中根节点的左右两侧就是左右子树的节点。

每次递归调用都会重新计算leftInorder、leftPreorder、rightInorder和rightPreorder。这意味着对于每个节点，都会进行两次数组切片操作，这会随着树的深度线性增长，时间复杂度高。

解法二：哈希

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
function buildTree(preorder: number[], inorder: number[]): TreeNode | null {
    const n = preorder.length;
    const index = new Map<number, number>();
    for (let i = 0; i < n; i++) {
        index.set(inorder[i], i);
    }

    function dfs(preL: number, preR: number, inL: number, inR: number): TreeNode | null {
        if (preL === preR) { // 空节点
            return null;
        }
        const rootVal = preorder[preL];
        const inRootIndex = index.get(rootVal)!; // 断言inorder中一定有这个值
        const leftSize = inRootIndex - inL; // 左子树的大小

        const left = dfs(preL + 1, preL + 1 + leftSize, inL, inRootIndex);
        const right = dfs(preL + 1 + leftSize, preR, inRootIndex + 1, inR);
        return new TreeNode(rootVal, left, right);
    }
    return dfs(0, n, 0, n); // 左闭右开区间
}

思路：递归优化，用哈希表降低时间复杂度，用下标降低空间复杂度。

路径总和III

给定一个二叉树的根节点 root ，和一个整数 targetSum ，求该二叉树里节点值之和等于 targetSum 的 路径 的数目。

路径 不需要从根节点开始，也不需要在叶子节点结束，但是路径方向必须是向下的（只能从父节点到子节点）。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
function pathSum(root: TreeNode | null, targetSum: number): number {
  //对每个节点都做对叶子节点的路径检索

  function dfs(curr: TreeNode | null, sum: number) {
    if (curr == null) {
      //递归终止条件
      return;
    }
    sum = sum + curr.val;
    if (sum === targetSum) {
      pathNum++;
    }
    dfs(curr.left, sum);
    dfs(curr.right, sum);
  }
  function helper(curr: TreeNode | null) {
    if (curr == null) {
      return;
    }
    dfs(curr, 0);
    helper(curr.left);
    helper(curr.right);
  }
  let pathNum = 0;
  helper(root);
  return pathNum
}

思路：创建一个辅助函数，用于对每个节点都进行路径检索。

二叉树的最近公共祖先

给定一个二叉树, 找到该树中两个指定节点的最近公共祖先。

中最近公共祖先的定义为：“对于有根树 T 的两个节点 p、q，最近公共祖先表示为一个节点 x，满足 x 是 p、q 的祖先且 x 的深度尽可能大（一个节点也可以是它自己的祖先）。”

1
2
3
4
5
6
7
8
9
10
11
12
function lowestCommonAncestor(root: TreeNode | null, p: TreeNode | null, q: TreeNode | null): TreeNode | null {
	if (!root || root === p || root === q) return root 

    const left = lowestCommonAncestor(root.left, p, q)
    const right = lowestCommonAncestor(root.right, p, q)
    if (left && right) {
        return root
    }

    return left ?? right

};

思路：每个节点在左右子树中进行搜索是否含有两个节点 p、q，如果左右子树均有节点 p、q则直接返回当前节点，否则返回包含 p、q 的子树根节点，当递归结束时，找到的节点即为满足条件的深度最大的祖先。

图论

岛屿数量

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

岛屿总是被水包围，并且每座岛屿只能由水平方向和/或竖直方向上相邻的陆地连接形成。

此外，你可以假设该网格的四条边均被水包围。

Author：破酥 | C4iN
Link：https://c4in1.github.io/2024/09/08/算法/LeetCodeHot100笔记/
版权声明：本文采用 CC BY-NC-SA 3.0 CN 协议进行许可
leetcode刷题