前言
- 整体进度
上题
- 206. 反转链表|简单、高频">206. 反转链表|简单、高频
- 102. 二叉树的层序遍历|中等、高频">102. 二叉树的层序遍历|中等、高频
- 15. 三数之和|中等、高频">15. 三数之和|中等、高频
- 215. 数组中的第K个最大元素|中等、高频">215. 数组中的第K个最大元素|中等、高频
- 121. 买卖股票的最佳时机|简单、高频">121. 买卖股票的最佳时机|简单、高频
- 5. 最长回文子串|中等、高频">5. 最长回文子串|中等、高频
- 141. 环形链表|简单、中频
- 912. 排序数组|中等|手写排序算法">912. 排序数组|中等|手写排序算法
- 129. 求根节点到叶节点数字之和|中等|递归|树|深搜|dfs">129. 求根节点到叶节点数字之和|中等|递归|树|深搜|dfs
  - 题目描述
  - 解题思路

前言

okkjoo-leetcodeHot-byJs带你用 JS 刷高频面试算法题~ 每周日/周一更新~ 合集仓库：okkjoo-leetcodeHot-byJs

这是第二周的刷题记录与题解分享，如果你已经按题型分类系统地刷了一遍算法面试题的各个题型，想感受一下面试题的”随机性”的话，欢迎一起~

本周只刷了九题

整体进度

上题

206. 反转链表|简单、高频

题目描述

反转一个单链表。

解题思路

链表入门题，用三个指针：

前驱 pre
后续 nxt
当前 cur

注意：

链表指针基本操作
while 循环什么时候结束

时间复杂度O(n),空间复杂度O(1)

代码

/**
 * Definition for singly-linked list.
 * function ListNode(val, next) {
 *     this.val = (val===undefined ? 0 : val)
 *     this.next = (next===undefined ? null : next)
 * }
 */
/**
 * @param {ListNode} head
 * @return {ListNode}
 */
var reverseList = function(head) {
    if(!head || !head.next) return head 
    let cur = head, pre = null, nxt
    while(cur != null){
        nxt = cur.next
        cur.next = pre
        pre = cur
        cur = nxt
    }
    return pre
};

102. 二叉树的层序遍历|中等、高频

题目描述

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

解题思路

二叉树经典题目——遍历专题中的层序遍历

常用递归或者队列来写：

递归

将当前节点和所在level、存储结果的数组一起传入递归函数，在递归中取出节点的value，根据level将value存储在对应的位置

队列

队列简单一点，第一步将节点放入队列中，再以 null 为该层结束的标志放入队列中。

每处理一个节点都将其左右节点放入队列中，注意这里要保持左右的顺序

不断出队，当出到 null 就表示该层出完到下一层了，这时再往队列中塞一个 null，作为下一层结束的标志

时间复杂度O(n)，空间复杂度O(n)

注意⭐：

注意 JS 数组重置的方式，虽然经测试arr.length = 0的速度会比arr = []快很多，但是这样是得不到正确答案的，原因是因为：

arr =[]创建的是一个新的数组，并为其赋予一个新的引用。其他引用不收影响，仍指向原数组

arr.length = 0修改数组本身，就算通过不同的变量访问它，得到的是同一个数组

我还顺手写(水)了篇文章：JS 基础! |清空数组性能最好的方式是…但能全都用这个吗?

还有就是队列要还有子节点再添加 null 作为标志~ 不然就要掉进循环里咯~

代码

/**
 * Definition for a binary tree node.
 * function TreeNode(val, left, right) {
 *     this.val = (val===undefined ? 0 : val)
 *     this.left = (left===undefined ? null : left)
 *     this.right = (right===undefined ? null : right)
 * }
 */
/**
 * @param {TreeNode} root
 * @return {number[][]}
 */
var levelOrder = function(root) {
    if(!root) return[]
    const res = [],
          que = [root, null]
    let     tmpLevel = []
    while(que.length){
        const t = que.shift()
        if(t){
            tmpLevel.push(t.val)
            t.left && que.push(t.left)
            t.right && que.push(t.right)
        }else {// t为null
            res.push(tmpLevel)
            // tmpLevel.length = 0
            // tmpLevel.splice(0,tmpLevel.length)
            tmpLevel = []
            que.length && que.push(null) //注意这里
        }
    }
    return res
};

也可以每次都存储队列当前的长度作为该层的个数，就不用 null 作为结束标志了，在 while 里面用 for 根据队列长度遍历

15. 三数之和|中等、高频

题目描述

给你一个包含 n 个整数的数组 nums，判断 nums 中是否存在三个元素 a，b，c ，使得 a + b + c = 0 ？请你找出所有和为 0 且不重复的三元组。

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

解题思路

要是直接暴力，那可就是O(n^3)的时间复杂度，没人顶得住~

ok，那我们先剩下一个n，我们可以直接认为 nums 中的每一项 nums[i] 都能成为三数中的一数，所以我们现在就可以将问题转换为 两数之和 = 0 - nums[i]，那看来模仿第一道题两数之和就能以 O(n) 的复杂度通过了。

no，这道题所求的组数不止是一组，那一道两数之和只要求一组，所以才能找到的时候就 return

还有一个要注意的点：不重复的三元组，怎么样保证不重复？

前面循环得到的元素不小于后面循环得到的元素，当然不大于也可以，只要有序就行

ok，我们就选不小于，所以要求最后的三元组[a, b, c]，要满足 a <= b <= c。那么首先就要先对数组排一下序，排序算法时间复杂度为O(nlogn)

然后再用双指针遍历~

最终时间复杂度为O(n^2)，空间复杂度没什么消耗，主要在于排序算法可能会消耗空间

代码

/**
 * @param {number[]} nums
 * @return {number[][]}
 */
var threeSum = function(nums) {
    //特例
    if(nums.length < 3) return []
    const res = []
    nums.sort((a, b) => a - b) //升序
    for(let i = 0; i < nums.length; i++){
        if(nums[i] > 0) break; //升序的数组，她大于0就不会后面的加上他能等于0了
        if(i > 0 && nums[i] === nums[i - 1]) continue //一样就跳过，避免重复三元组
        //双指针
        let left = i + 1, right = nums.length - 1
        while(left < right){ // 保证 i < left < right
            if(nums[left] + nums[right] + nums[i] === 0){//找到合适的
                res.push([nums[i], nums[left], nums[right]])
                //跳过重复的
                while(nums[left] === nums[left + 1]) left++
                left++
                while(nums[right] === nums[right + 1]) right--
                right--
             // 不符合的根据情况调整
            }else if(nums[left] + nums[right] + nums[i] > 0){
                right--
            }else left++
        }
    }
    return res
};

215. 数组中的第K个最大元素|中等、高频

题目描述

给定整数数组 nums 和整数 k，请返回数组中第 k 个最大的元素。

请注意，你需要找的是数组排序后的第 k 个最大的元素，而不是第 k 个不同的元素。

解题思路

直接排序

最直观的就是直接排序，然后选择下标为k的就好了

时间复杂度O(nlogn)

小顶堆

维护一个大小为 k 的小顶堆，当堆大小大于 k ，就删除堆顶。等遍历完数组的时候，堆顶就是第k大的元素了

时间复杂度O(nlogk)，空间复杂度O(k)

快速选择

快选有点像快排，就是找基准，然后将大于他的放一边，小于他的放一边。如果大于他的树有 k-1 个，那他自然就是第 k 个大的。

时间复杂度平均为O(n)，最坏为O(n^2)

代码

小顶堆

/**
 * @param {number[]} nums
 * @param {number} k
 * @return {number}
 */
class MinHeap {
    constructor() {
        this.heap = [];
    }
    swap(a, b) {
        [this.heap[a], this.heap[b]] = [this.heap[b], this.heap[a]];
    }
    getParentIndex(i) {
        return (i - 1) >> 1;
    }
    getleftIndex(i) {
        return 2 * i + 1;
    }
    getrightIndex(i) {
        return 2 * i + 2;
    }
    shiftUp(index) {
        if (index === 0) return;
        const parentIndex = this.getParentIndex(index);
        if (this.heap[parentIndex] > this.heap[index]) {
            this.swap(parentIndex, index);
            this.shiftUp(parentIndex);
        }
    }
    shiftDown(index) {
        const leftIndex = this.getleftIndex(index);
        const rightIndex = this.getrightIndex(index);
        if (this.heap[leftIndex] < this.heap[index]) {
            this.swap(leftIndex, index);
            this.shiftDown(leftIndex);
        }
        if (this.heap[rightIndex] < this.heap[index]) {
            this.swap(rightIndex, index);
            this.shiftDown(rightIndex);
        }
    }
    insert(value) {
        this.heap.push(value);
        this.shiftUp(this.heap.length - 1);
    }
    pop() {
        // pop删除数组最后一个元素并返回，赋值给堆顶
        this.heap[0] = this.heap.pop();
        // 对堆顶重新排序
        this.shiftDown(0);
    }
    peek() {
        return this.heap[0];
    }
    size() {
        return this.heap.length;
    }
}
const findKthLargest = (nums, k) => {
    const minHeap = new MinHeap();
    nums.forEach(n => {
        // 将数组元素依次插入堆中
        minHeap.insert(n);
        // 如果堆大小超过k，将堆顶(最小) 的去掉
        if (minHeap.size() > k) {
            minHeap.pop();
        }
    })
    // 返回堆顶，此时就是第k大的元素
    return minHeap.peek();
};

快速选择

/**
 * @param {number[]} nums
 * @param {number} k
 * @return {number}
 */
const findKthLargest = (nums, k) => {
    const n = nums.length;
    const quick = (l, r) => {
        if (l > r) return;//递归终止条件
        let random = Math.floor(Math.random() * (r - l + 1)) + l; //随机选一个索引
        swap(nums, random, r); //将它和位置r的元素交换，让nums[r]作为基准元素
        //对基准元素进行partition
        let pivotIndex = partition(nums, l, r);
        /*
          partition之后，基准左边的都小于它 右边的都大于它
          基准元素的位置pivotIndex正好是n-k 则找大了第k大的数
          如果n-k<pivotIndex,说明偏大了，去pivotIndex的左边递归查找
          如果n-k>pivotIndex，说明偏小了，去pivotIndex的右边递归查找
        */
        if (n - k < pivotIndex) {
            quick(l, pivotIndex - 1);
        } else {
            quick(pivotIndex + 1, r);
        }
    };
    quick(0, n - 1);//函数开始传入的left=0，right= n - 1
    return nums[n - k]; //最后找到了正确的位置 也就是n-k等于pivotIndex 这个位置的元素就是第k大的数
};
function partition(nums, left, right) {
    let pivot = nums[right];                 //最右边的元素为基准
    let pivotIndex = left;                   //pivotIndex初始化为left
    for (let i = left; i < right; i++) {     //遍历left到right-1的元素
        if (nums[i] < pivot) {                 //如果当前元素比基准元素小
            swap(nums, i, pivotIndex);           //把它交换到pivotIndex的位置
            pivotIndex++;                        //pivotIndex往前移动一步
        }
    }
    swap(nums, right, pivotIndex);           //最后交换pivotIndex和right
    return pivotIndex;                       //返回pivotIndex
}
function swap(nums, p, q) {//交换数组中的两个元素
    const temp = nums[p];
    nums[p] = nums[q];
    nums[q] = temp;
}

121. 买卖股票的最佳时机|简单、高频

题目描述

给定一个数组 prices ，它的第 i 个元素 prices[i] 表示一支给定股票第 i 天的价格。

你只能选择某一天买入这只股票，并选择在未来的某一个不同的日子卖出该股票。设计一个算法来计算你所能获取的最大利润。

返回你可以从这笔交易中获取的最大利润。如果你不能获取任何利润，返回 0 。

解题思路

获取最大利润，看起来就像贪心~

只有一笔交易，那想要获取最多利润，那就是在最低点买，最高点卖。当然，两个点的出现时间要注意~

其实很简单，在遍历的时候，记录到当前这个时间节点前的最低点价格即可。后面出现更高价格的时候，就与之相减再比较是否是最高利润，出现更低价格的时候就更新最低点价格。

代码

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

5. 最长回文子串|中等、高频

题目描述

给你一个字符串 s，找到 s 中最长的回文子串。

解题思路

暴力

没啥好说的，O(n^3)

dp

dp[i][j]表示 [i, j]字符串可以形成回文，那么往两边延展一下，就可以有这样的转台转移

if(s[i] === s[j] && dp[i+1][j-1]) dp[i+1][j-1] = true

时间复杂度O(n^2)，空间复杂度O(n^2)

manacher 马拉车算法

这是一个专门处理回文串的算法~

先对字符串进行预处理，两个字符之间加上特殊符号#
然后遍历整个字符串，用一个数组来记录以该字符为中心的回文长度，为了方便计算右边界，在数组中记录长度的一半（向下取整）
每一次遍历的时候，如果该字符在已知回文串最右边界的覆盖下，那么就计算其相对最右边界回文串中心对称的位置，得出已知回文串的长度
判断该长度和右边界，如果达到了右边界，那么需要进行中心扩展探索。当然，如果第3步该字符没有在最右边界的“羽翼”下，则直接进行中心扩展探索。进行中心扩展探索的时候，同时又更新右边界
最后得到最长回文之后，去掉其中的特殊符号即可

时间复杂度的O(n)

这个代码我不背真写不下来… 希望面试只回答出思路就够了…😂

代码

/**
 * dp
 * @param {string} s
 * @return {string}
 */
var longestPalindrome = function (s) {
    if (!s || !s.length) return "";
    let res = s[0];
    const dp = [];
    // dp[i][] 依赖 dp[i-1][] --> 干脆反着遍历
    for (let i = s.length - 1; i >= 0; i--) {
        dp[i] = [];
        for (let j = i; j < s.length; j++) {
            if (j === i) dp[i][j] = true; // d[i][i] 一个字符当然回文
            else if (j === i + 1 && s[i] === s[j]) dp[i][j] = true; //dp[i][i+1]
            else if (s[i] === s[j] && dp[i + 1][j - 1]) dp[i][j] = true;
            // 有更长的就要更新
            if (dp[i][j] && j - i + 1 > res.length) res = s.slice(i, j + 1);
        }
    }
    return res;
};
/**
 * dp
 * @param {string} s
 * @return {string}
 */
var longestPalindrome = function (s) {
    if (!s || !s.length) return "";
    let res = s[0];
    const dp = [];
    // dp[i][] 依赖 dp[i-1][] --> 干脆反着遍历
    for (let i = s.length - 1; i >= 0; i--) {
        dp[i] = [];
        for (let j = i; j < s.length; j++) {
            if (j === i) dp[i][j] = true; // d[i][i] 一个字符当然回文
            else if (j === i + 1 && s[i] === s[j]) dp[i][j] = true; //dp[i][i+1]
            else if (s[i] === s[j] && dp[i + 1][j - 1]) dp[i][j] = true;
            // 有更长的就要更新
            if (dp[i][j] && j - i + 1 > res.length) res = s.slice(i, j + 1);
        }
    }
    return res;
};
/**
 * manacher
 * @param {string} s
 * @return {string}
 */
var longestPalindrome = function (s) {
    const lens = s.length;
    // 预处理字符数组
    let str = "#";
    for (let i = 0; i < lens; i++) {
        str = str + s[i] + "#";
    }
    // 当前回文子串能到达的右边界和它的中心
    let mid = 0,
        right = 0;
    // 最长的回文子串的中心和长度
    let maxLen = 0,
        maxLenMid = 0;
    // child[i]: 以i为中心的最长回文
    const child = [];
    // 遍历处理过的字符串，以每个字符中心进行扩展
    for (let i = 0; i < str.length; i++) {
        // 第i个字符，如果在最右边界的羽翼下，就选择对称字符的回文长度
        // 不在右边界内就赋值1
        child[i] = i < right ? Math.min(child[2 * mid - i], right - i) : 1;
        // 不论怎么样都要试一试暴力扩展
        while (
            i - child[i] >= 0 &&
            i + child[i] < str.length &&
            str.charAt(i + child[i]) == str.charAt(i - child[i])
        ) {
            child[i]++;
        }
        // 更新右边界
        if (right < child[i] + i) {
            mid = i;
            right = child[i] + i;
        }
        // 是否更新最长回文子串
        if (maxLen < child[i]) {
            maxLen = child[i];
            maxLenMid = i;
        }
    }
    return s.substring(
        (maxLenMid + 1 - maxLen) / 2,
        (maxLenMid - 1 + maxLen) / 2
    );
};

141. 环形链表|简单、中频

题目描述

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

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

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

解题思路

map

遍历所有节点并记录，遇到以及记录过的节点就说明有环，直接return。如遍历完了都还没有return就说明没环。

时间O(n)，空间O(n)

代码简单，不写了

快慢指针

两个指针，一开始都在 head

快指针一次走两个节点
慢指针一次走一个节点

快指针绕一圈追上慢指针就说明有环~

时间复杂度O(n),空间复杂度O(1)

代码

/**
 * Definition for singly-linked list.
 * function ListNode(val) {
 *     this.val = val;
 *     this.next = null;
 * }
 */
/**
 * @param {ListNode} head
 * @return {boolean}
 */
var hasCycle = function(head) {
    let slow = head, fast = head
    while(fast && fast.next){
        slow = slow.next
        fast = fast.next.next
        if(fast == slow) return true
    }
    return false
};

912. 排序数组|中等|手写排序算法

题目描述

给你一个整数数组 nums，请你将该数组升序排列。

解题思路

肯定不是考API啦，手写排序算法啦

看题目的数据范围正负五万，总共十万，优先考虑O(n) 级别的算法~

计数排序

准备一个待排序数组取值范围的数组，遍历待排序数组，将每个元素放到对应下标位置，值就是其出现的次数

时间复杂度O(n+k)，空间复杂度O(50000*2+1) (中值取值范围，或者说为了下标不为负数的偏移diff)

快速排序

每次将数组分为两半，一部分比关键元素大，另一部分比关键元素小（小于等于）。然后递归~

关键元素的选取方式有多种，一般我是最左边的那个，你可以选中间或者最右边或者随机

时间复杂度O(nlogn)，空间复杂度O(logn)

代码

计数排序

/**
 * @param {number[]} nums
 * @return {number[]}
 */
var sortArray = function(nums) {
    const diff = 50000
    const counts = Array(diff * 2 + 1).fill(0)
    const res = []
    for(const a of nums) counts[a + diff]++
    for(let i in counts){
        while(counts[i]--) res.push(i - diff)
    }
    return res
};

快速排序

/**
 * 快速排序
 * @param {number[]} nums
 * @return {number[]}
 */
var sortArray = function (nums) {
    if (nums.length <= 1) return nums; //递归中止
    const pivotIdx = Math.floor(nums.length / 2);
    const pivot = nums.splice(pivotIdx, 1)[0];
    const left = [],
        right = [];
    for (let num of nums) {
        if (num < pivot) left.push(num);
        else right.push(num);
    }
    return sortArray(left).concat([pivot], sortArray(right));
};

129. 求根节点到叶节点数字之和|中等|递归|树|深搜|dfs

题目描述

给你一个二叉树的根节点 root ，树中每个节点都存放有一个 0 到 9 之间的数字。
每条从根节点到叶节点的路径都代表一个数字：

例如，从根节点到叶节点的路径 1 -> 2 -> 3 表示数字 123 。
计算从根节点到叶节点生成的所有数字之和。

叶节点是指没有子节点的节点

解题思路

简单的递归题，注意因为要存储节点深度方便计算该条路径的“value”，所以借助一个额外函数 dfs 进行递归

/**
 * Definition for a binary tree node.
 * function TreeNode(val, left, right) {
 *     this.val = (val===undefined ? 0 : val)
 *     this.left = (left===undefined ? null : left)
 *     this.right = (right===undefined ? null : right)
 * }
 */
/**
 * @param {TreeNode} root
 * @return {number}
 */
var sumNumbers = function (root) {
    return dfs(root, 0);
};
const dfs = (node, cur) => {
    if (node === null) return 0;
    const v = node.val + cur * 10;
    if (node.left === null && node.right === null) return v;
    return dfs(node.left, v) + dfs(node.right, v);
};

JS 刷高频面试算法题|第二周

前言

整体进度

上题

206. 反转链表|简单、高频

题目描述

解题思路

代码

102. 二叉树的层序遍历|中等、高频

题目描述

解题思路

递归

队列

注意⭐：

代码

15. 三数之和|中等、高频

题目描述

解题思路

代码

215. 数组中的第K个最大元素|中等、高频

题目描述

解题思路

直接排序

小顶堆

快速选择

代码

小顶堆

快速选择

121. 买卖股票的最佳时机|简单、高频

题目描述

解题思路

代码

5. 最长回文子串|中等、高频

题目描述

解题思路

暴力

dp

manacher 马拉车算法

代码

141. 环形链表|简单、中频

题目描述

解题思路

map

快慢指针

代码

912. 排序数组|中等|手写排序算法

题目描述

解题思路

计数排序

快速排序

代码

129. 求根节点到叶节点数字之和|中等|递归|树|深搜|dfs

题目描述

解题思路