数组

二分法

二分（左闭右闭）

循环判断条件

while(left <= right) 因为左闭右闭的情况下，left是可以等于right的

区间的处理

left = mid + 1 right = mid -1 因为当mid不符合条件时，不应该再将mid放入闭区间里

最后结果

right 等于 left -1

代码

1
2
3
4
5
6
while(left <= right) {
    mid = left + ((right - left) << 1)
    if(nums[mid] > target) right = mid - 1;
    else if(num[mid] < target) left = mid + 1;
    else return mid;
}

二分（左闭右开）

判断条件

while(left<right) 因为左闭右开的情况下，left不可以等于right

最后结果

left等于right

区间的处理

left = mid + 1 right = mid因为此时右边是开区间 把mid赋值到右边不会影响

代码

1
2
3
4
5
6
while(left < right) {
    mid = left + ((right - left) << 1)
    if(nums[mid] > target) right = mid;
    else if(num[mid] < target) left = mid + 1;
    else return mid;
}

35 搜索插入位置

给定排序数组nums和一个目标值target

找到目标值并返回索引

如果目标值不存在数组中，返回其按顺序插入的位置

思路

二分查找，找到目标值返回索引很简单

重点在于不在数组中返回其 应该插入位置的情况

左闭右闭时 未找到的情况

最后一次查找，开始时 left等于right mid等于left等于right，结束时left等于right + 1

如果target > nums[mid] ,target应该在mid右端一位，即target的索引应该是mid + 1,此时left = mid + 1 ，所以返回left或者right+1

如果target < nums[mid], target应该在mid左端一位，即target的索引应该是mid,此时right = mid - 1,所以返回 left或者right + 1

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
/**
 * @param {number[]} nums
 * @param {number} target
 * @return {number}
 */

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

左闭右开时 未找到的情况

最后一次查找，开始时right等于left+1 mid等于left等于right-1 ，结束时left等于right

如果target > nums[mid] ,target应该在mid右端一位，即target的索引应该是mid + 1,此时left = mid + 1,所以返回left或者right

如果target < nums[mid], target应该在mid左端一位，即target的索引应该是mid,此时right = mid - 1,所以返回 left或者right

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
/**
 * @param {number[]} nums
 * @param {number} target
 * @return {number}
 */

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

34 在排序数组中查找元素的第一个和最后一个位置

给一个非递减的数组nums和目标值target

给定目标值在数组中的开始位置和结束位置

如果数组中不存在目标值，返回[-1,-1]

思路

将查找元素的第一个和最后一个位置问题转换成 查找元素的左边界（不含该元素）和右边界问题（不含该元素）

重点如何寻找左右边界呢？改写二分法。

如果要寻找左边界，那就是要找尽可能小于目标值的地方,即使找到了target也不返回，而是继续向左查找,直到最后一个target为mid时 right就是左边界

1
2
3
4
5
6
7
8
9
10
11
12
13
var searchLeftBorder = function(nums, target) {
    let left = 0, right = nums.length - 1, leftBorder = -2;
    while(left <= right) {
        let mid = left + ((right - left) >> 1);
        if(nums[mid] >= target) {
            right = mid - 1;
            leftBorder = right;
        } else {
            left = mid + 1;
        }
    }
    return leftBorder;
}

如果要寻找右边界，那就是要找尽可能小于目标值的地方,即使找到了target也不返回，而是继续向右查找,直到最后一个target为mid时 left就是左边界

1
2
3
4
5
6
7
8
9
10
11
12
13
var searchRightBorder = function(nums, target) {
    let left = 0, right = nums.length - 1, rightBorder = -2;
    while(left <= right) {
        let mid = left + ((right - left) >> 1);
        if(nums[mid] > target) {
            right = mid - 1;
        } else {
            left = mid + 1;
            rightBorder = left;
        }
    }
    return rightBorder;
}

现在讨论leftBorder和rightBorder各种取值的情况

初始时 leftBorder和rightBorder都为 -2

  1. 如果数组中所有元素都大于 target 那么rightBorder一直都不被赋值，试图在最左边找leftBorder 最后 leftBorder为-1
  2. 如果数组中所有元素都小于target 那么leftBorder一直都不被赋值，试图在最右边找rightBorder 最后rightBorder为-1
  3. 如果target在数组中元素的范围内，但不在数组内。那么leftBorder + 1等于rightBorder
  4. target在数组中元素的范围内 ，那么rightBorder > leftBorder + 1
1
2
3
4
5
6
7
8
9
10
11
12
13
14
/**
 * @param {number[]} nums
 * @param {number} target
 * @return {number[]}
 */
var searchRange = function(nums, target) {
    let leftBorder = searchLeftBorder(nums, target);
    let rightBorder = searchRightBorder(nums, target);
    if(leftBorder === -2 || rightBorder === -2) {
        return [-1, -1];
    }
    if(rightBorder - leftBorder > 1) return [leftBorder + 1, rightBorder - 1];
    return [-1, -1];
};

删除数组元素（原地修改）

leetcode27题

题干：给定一个数组 nums 和一个值 val，你需要 原地 移除所有数值等于 val 的元素，并返回移除后数组的新长度。

原地：不要使用额外的数组空间，你必须仅使用 O(1) 额外空间并原地修改输入数组。

暴力解法

两重循环，第一次循环遍历元素，当元素值为val时，进入第二重循环，将所有数右移

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
/**
 * @param {number[]} nums
 * @param {number} val
 * @return {number}
 */

var removeElement = function(nums, val) {
    let len = nums.length;
    for(let i = 0; i < len; i++){
        if(nums[i] == val) {
            for(let j = i + 1; j < len; j++){
                nums[j-1] = nums[j];
            }
            i--;
            len--;
        }
    }
    console.log(len);
    
    return len;
};

双指针法

fast指针遍历数组，slow指针指向新数组

当fast指向的值为val时，fast指针右移动

当fast指向的值不为val时，将fast的值赋给slow指针，slow指针向右移动

1
2
3
4
5
6
7
8
9
10
11
12
13
/**
 * @param {number[]} nums
 * @param {number} val
 * @return {number}
 */

var removeElement = function(nums, val) {
    let slow = 0, fast = 0;
    for(fast = 0; fast < nums.length; fast++){
        if(nums[fast] != val) nums[slow++] = nums[fast];
    }
    return slow
};

26 删除有序数组中的重复项

给定非降序数组nums

删除所有重复的元素，并将剩下的元素排序 ，并返回新数组的长度

nums唯一元素的数量为k，其余元素与大小并不重要

思路

双指针， slow指针和fast指针初始都指向0

fast指针遍历数组

当fast指针和slow指针指的元素不一样的时候，++nums[slow] = nums[fast]

删除后新数组的长度为slow+1

1
2
3
4
5
6
7
8
9
10
11
12
/**
 * @param {number[]} nums
 * @return {number}
 */

var removeDuplicates = function(nums) {
    let slow = 0, fast = 0;
    for(; fast < nums.length; fast++){
        if(nums[fast] != nums[slow]) nums[++slow] = nums[fast];
    }
    return slow + 1;
};

283 移动零

给定数组nums

要求将所有0移动到末尾，并保持非零元素的相对顺序

要求 对原数组进行操作 空间复杂度o（1）

暴力解法

一遇到0就往后找不为0的数 并交换

时间复杂度O(n2)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
/**
 * @param {number[]} nums
 * @return {void} Do not return anything, modify nums in-place instead.
 */
var moveZeroes = function(nums) {
    for(let i = 0; i < nums.length; i++){
        if(nums[i] === 0) {
            for(let j = i + 1; j < nums.length; j++) {
                if(nums[j] !== 0) {
                    nums[i] = nums[j];
                    nums[j] = 0;
                    break;
                }
            }
        }
    }
};

双指针法

定义指针slow，fast，fast遍历数组

fast指向的是0 fast向右移动

fast指向的是非0 fast的值给slow fast和slow都向右移动

最后数组的fill方法填充元素0

有序数组的平方

leetcode 997题

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

暴力解法

先平方再排序（略）

双指针

每次都选最大的元素放到新数组里，因为原先是非递减排序的数组，所以平方后最大的值只可能在两端（绝对值最大）

左侧i指针，右侧j指针

当指针i的数值平方小于指针j的数值平方时，将指针j的值放到新数组末尾，将j左移

反之 将指针i的值放到数组末尾，将i右移动

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
/**
 * @param {number[]} nums
 * @return {number[]}
 */

var sortedSquares = function(nums) {
    let i = 0, j = nums.length-1, k = j;
    let results = [];
    while(i<=j){
        if(nums[i] * nums[i] < nums[j] * nums[j]) {
    		nums[k--] = nums[j] * nums[j];
            j--;
        }
        else {
            nums[k--] = nums[i] * nums[i];
            i++;
        }
    }
    return results;
};

长度最小的子数组

leetcode 209

给定数组和特定值，找出数组中满足其和>=特定值的长度最小的 连续 子数组，并返回其长度，如果不存在满足条件的子数组，返回0

滑动窗口

思路是，定义数组开头指针start 末尾指针end。

【end一直后移动，当子数组满足题目的条件时，start后移直到不满足条件，再让end后移动到满足条件】，如此循环，记录满足条件的最小长度

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
/**
 * @param {number} target
 * @param {number[]} nums
 * @return {number}
 */
var minSubArrayLen = function(target, nums) {
    let start = 0, end = 0, result = Infinity, sum = 0;
    for(; end < nums.length; end++) {
        sum += nums[end];
        while(sum >= target) {
            const subLen = end - start + 1
            result = result < subLen? result : subLen;
            sum -= nums[start++];
        }
    }
    return result === Infinity? 0 : result;
}

904 水果成篮

给定数组fruits，fruits[i]表示水果的种类。

两个篮子，每个篮子只能装一种水果，每个篮子无限装。

只能从前往后按顺序装。

思路

滑动窗口，end，start两个指针。

【end右移。当当前无法继续采摘时，start指针指向end指针前方的，最前的，与end指针同种的水果。然后继续end右移】

如此循环，每次end右移，记下最大长度

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
/**
 * @param {number[]} fruits
 * @return {number}
 */
var totalFruit = function(fruits) {
    let start = 0, end = 0, result = 0,basket = [];
    for(;end < fruits.length; end++){
        if(!basket.includes(fruits[end]) && basket.length < 2) {
            basket.push(fruits[end]);
        } else if(basket.includes(fruits[end])) {

        } else {
            start = end - 1
            while(fruits[start] === fruits[start-1]) {
                start--;
            }
            basket = [fruits[end], fruits[start]]
        }
        const subLen = end - start + 1;
        result = result > subLen? result: subLen;
        console.log(`从${start}到${end}，篮子里是${basket}`);
    }
    return result;
}

76 最小覆盖子串

leetcode 76

给定字符串s，t

要求在s中找到涵盖字符串t的最小字串

可以乱序 但要求t的所有字母都在s子串里出现过 重复的字母，次数也不能小于s子串的次数

思路

滑动窗口，指针start和end，当s子串涵盖了t时回退到不涵盖的情况

关键是如何表示涵盖了

为s子串创建cntS数组，t子串创建cntT数组，统计每个字母出现的次数，当s子串中每个字母出现的字数都大于t时 即为涵盖了

方法一 ：

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
/**
 * @param {string} s
 * @param {string} t
 * @return {string}
 */

var isCovered = function(cntS, cntT){
    for(let i = 'a'.charCodeAt(0); i <= 'z'.charCodeAt(0); i++) {
        if(cntS[i] < cntT[i]) return false;
    }
    for(let i = 'A'.charCodeAt(0); i <= 'Z'.charCodeAt(0); i++) {
        if(cntS[i] < cntT[i]) return false;
    }
    return true;
}

var minWindow = function(s, t) {
    let start = 0, end = 0, 
    cntS = Array(128).fill(0), cntT = Array(128).fill(0), ansLeft = -1, ansRight = s.length;
    for(let char of t) {
        cntT[char.charCodeAt(0)]++;
    }
    for(; end < s.length; end++){
        cntS[s[end].charCodeAt(0)]++;
        while(isCovered(cntS, cntT)) {
            if(end - start < ansRight - ansLeft) {
                ansLeft = start;
                ansRight = end;
            }
            cntS[s[start].charCodeAt(0)]--;
            start++;
        }
    }
    return ansLeft === -1? "": s.substring(ansLeft, ansRight + 1)
}

方法二：

用type表示t的字母种类，每当t有一个字母被s涵盖全，就将type–

直到type为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
/**
 * @param {string} s
 * @param {string} t
 * @return {string}
 */
var minWindow = function(s, t) {
    let start = 0, end = 0, 
    cntS = Array(128).fill(0), cntT = Array(128).fill(0), ansLeft = -1, ansRight = s.length,
    type = 0;
    for(let char of t) {
        if(cntT[char.charCodeAt(0)]++ === 0) {
            type++;
        }
    }
    for(; end < s.length; end++){
        let num = s[end].charCodeAt(0);
        if(++cntS[num] === cntT[num]) {
            type--;
        }
        while(type === 0) {
            if(end - start < ansRight - ansLeft) {
                ansLeft = start;
                ansRight = end;
            }
            const x = s[start++].charCodeAt(0);
            if(cntS[x]-- === cntT[x]){
                type++;
            }
        }
    }
    return ansLeft === -1? "": s.substring(ansLeft, ansRight + 1)
}

螺旋矩阵

59 螺旋矩阵II

给定一个正整数 n，生成一个包含 1 到 n^2 所有元素，且元素按顺时针顺序螺旋排列的正方形矩阵。

示例:

输入: 3 输出: [ [ 1, 2, 3 ], [ 8, 9, 4 ], [ 7, 6, 5 ] ]

思路

循环不变量

填充分为4部分

例如输入为3时，从左到右填1，2；从上到下填3，4；从右到左填5，6；从下到上填7，8

输入n，循环n/2(向下取整)，如果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
/**
 * @param {number} n
 * @return {number[][]}
 */
var generateMatrix = function(n) {
    let mid = Math.floor(n / 2)
    let loop = Math.floor(n / 2)
    let matrix = new Array(n).fill(0).map(() => new Array(n).fill(0))
    let offset = 1, startx = 0, starty = 0
    let count = 1
    while (loop--) {
        let col = starty, row = startx
        for(; col < n - offset; col++) matrix[row][col] = count++
        for(; row < n - offset; row++) matrix[row][col] = count++
        for(; col > starty; col--) matrix[row][col] = count++
        for(; row > startx; row--) matrix[row][col] = count++

        startx++,starty++
        offset++
    }

    if(n % 2 === 1) {
        matrix[mid][mid] = count
    }
    return matrix
};

54 螺旋矩阵

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

思路：

循环loop次，loop = m > n ? Math.floor(m / 2) : Math.floor(n / 2)

循环过程中，当res里已经有了所有元素时，返回

特殊情况，m，n相等且都为奇数时，matrix中间元素填充到res

前缀和

前缀和概念：

一个长度为n的数组a[1] ~ a[n]，前缀和sum[i]等于a[1] ~ a[i]的和：

sum[i] = a[1] + a[2] + … + a[i]

递推公式：sum[i]=sum[i-1]+a[i]

差分概念：

差分是前缀和的逆运算，一个长度为n的数组a[1]~a[n],差分d[i]等于a[i]-a[i-1]

公式：a[i]=a[i-1]+d[i]

区间和

题目链接

给定一个整数数组 Array，请计算该数组在每个指定区间内元素的总和。

代码

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
const readline = require('readline')
const rl = readline.createInterface({
    input: process.stdin,
    output: process.stdout
})

let n
let num = []
let s = []
let inputStep = 0
let ranges = []
rl.on('line', (line) => {
    if (inputStep === 0) {
        n = parseInt(line.trim())
        inputStep++
    } else if (inputStep <=n) {
        inputStep++
        num.push(parseInt(line.trim()))
    } else {
        range = line.trim().split(' ').map(Number)
        ranges.push(range)
    }
    
})
rl.on('close', () => {
    s = new Array(num.length).fill(0)
    s[0] = num[0]
    for(let i = 1; i < num.length; i++) {
        s[i] = s[i-1] + num[i] 
    }
    ranges.forEach(range => {
        const [start, end] = range
        let sum = s[end]
        if(start > 0) sum -= s[start - 1]
        console.log(sum)
    })
})

开发商购买土地

题目链接

本题也是用前缀和优化时间复杂度

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
51
52
53
const readline = require('readline')
const rl = readline.createInterface({
    input: process.stdin,
    output: process.stdout
})

let n,m
let inputStep = 0
let num = []
let prefixColSum = []
let prefixRowSum = []
rl.on('line', (line) => {
    if(inputStep === 0) {
        [n, m] = line.trim().split(' ').map(Number)
        inputStep++
        num = new Array(n).fill(0).map(() => new Array(m).fill(0))
    } else if(inputStep <= n) {
        num[inputStep - 1] = line.trim().split(' ').map(Number)
        inputStep++
    } else {

    }
})
rl.on('close', () => {
    prefixColSum = new Array(m).fill(0)
    let colSum = new Array(m).fill(0)
    prefixRowSum = new Array(n).fill(0)
    let rowSum = new Array(n).fill(0)
    for(let i = 0; i < m; i++) {
        for(let j = 0; j < n; j++) {
            colSum[i] += num[j][i]
        }
        if (i === 0) prefixColSum[i] = colSum[i]
        else prefixColSum[i] = prefixColSum[i-1] + colSum[i]
    }
    for (let i = 0; i < n; i++) {
        for (let j = 0; j < m; j++) {
            rowSum[i] += num[i][j]
        }
        if(i === 0) prefixRowSum[i] = rowSum[i]
        else prefixRowSum[i] = prefixRowSum[i-1] + rowSum[i]
    }
    let sum = Infinity
    for(let i = 1; i < m; i++) {
        let res = Math.abs(prefixColSum[m - 1] - 2 * prefixColSum[i - 1])
        sum = sum < res ? sum : res
    }
    for(let i = 1; i < n; i++) {
        let res = Math.abs(prefixRowSum[n - 1] - 2 * prefixRowSum[i - 1])
        sum = sum < res ? sum : res
    }
    console.log(sum)
})

链表

移除链表元素

203 移除链表元素

题意：删除链表中等于给定值 val 的所有节点。

两种方法：

  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
    class ListNode {
        val
        next = null
        constructor (value) {
            this.val = value
            this.next = null
        }
    }
    /**
     * @param {ListNode} head
     * @param {number} val
     * @return {ListNode}
     */
    var removeElements = function (head, val) {
        while (head && head.val === val) {
            head = head.next
        }
        if (head === null) return head
        let cur = head
        while (cur.next) {
            if(cur.next.val === val) cur.next = cur.next.next
            else cur = cur.next
        }
        return head
    };

  2. 使用虚拟头结点，统一操作

    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    16
    17
    18
    19
    20
    21
    22
    23
    class ListNode {
        val
        next = null
        constructor (value) {
            this.val = value
            this.next = null
        }
    }
    /**
     * @param {ListNode} head
     * @param {number} val
     * @return {ListNode}
     */
    var removeElements = function (head, val) {
        let dummyHead = new ListNode(0)
        dummyHead.next = head
        let cur = dummyHead
        while (cur.next) {
            if(cur.next.val === val) cur.next = cur.next.next
            else cur = cur.next
        }
        return dummyHead.next
    };

链表常用操作

707 设计链表

  • MyLinkedList() 初始化 MyLinkedList 对象。
  • int get(int index) 获取链表中下标为 index 的节点的值。如果下标无效，则返回 -1 。
  • void addAtHead(int val) 将一个值为 val 的节点插入到链表中第一个元素之前。在插入完成后，新节点会成为链表的第一个节点。
  • void addAtTail(int val) 将一个值为 val 的节点追加到链表中作为链表的最后一个元素。
  • void addAtIndex(int index, int val) 将一个值为 val 的节点插入到链表中下标为 index 的节点之前。如果 index 等于链表的长度，那么该节点会被追加到链表的末尾。如果 index 比长度更大，该节点将 不会插入 到链表中。
  • void deleteAtIndex(int index) 如果下标有效，则删除链表中下标为 index 的节点。

注意链表的自身属性size和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
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
class LinkNode {
    val
    next = null
    constructor (value) {
        this.val = value
        this.next = null
    }
}
var MyLinkedList = function () {
    this._size = 0
    this._head = null 
};

/** 
 * @param {number} index
 * @return {number}
 */
MyLinkedList.prototype.get = function (index) {
    if (index < 0 || index >= this._size ) return -1
    let cur = this._head
    while (index) {
        cur = cur.next
        index--
    }
    return cur.val
};

/** 
 * @param {number} val
 * @return {void}
 */
MyLinkedList.prototype.addAtHead = function (val) {
    let newNode = new LinkNode(val)
    newNode.next = this._head
    this._head = newNode
    this._size++
};

/** 
 * @param {number} val
 * @return {void}
 */
MyLinkedList.prototype.addAtTail = function (val) {
    let dummyHead = new LinkNode(0)
    dummyHead.next = this._head
    let newNode = new LinkNode(val)
    if(!dummyHead.next) {
        dummyHead.next = newNode
    } else {
        let cur = dummyHead.next
        while(cur.next) {
            cur = cur.next
        }
        newNode.next = null
        cur.next = newNode
    }
    this._size++
    this._head = dummyHead.next
};

/** 
 * @param {number} index 
 * @param {number} val
 * @return {void}
 */
MyLinkedList.prototype.addAtIndex = function (index, val) {
    if(index > this._size) return
    let dummyHead = new LinkNode(0)
    dummyHead.next = this._head
    let cur = dummyHead
    while (index--) {
        cur = cur.next
    }
    let newNode = new LinkNode(val)
    newNode.next = cur.next
    cur.next = newNode
    this._head = dummyHead.next
    this._size++
};

/** 
 * @param {number} index
 * @return {void}
 */
MyLinkedList.prototype.deleteAtIndex = function (index) {
    if(index < 0 || index >= this._size) return
    let dummyHead = new LinkNode(0)
    dummyHead.next = this._head
    let cur = dummyHead
    while(index) {
        cur = cur.next
        index--
    }
    cur.next = cur.next.next
    this._head = dummyHead.next
    this._size--
};

/**
 * Your MyLinkedList object will be instantiated and called as such:
 * var obj = new MyLinkedList()
 * var param_1 = obj.get(index)
 * obj.addAtHead(val)
 * obj.addAtTail(val)
 * obj.addAtIndex(index,val)
 * obj.deleteAtIndex(index)
 */
let myLinkedList = new MyLinkedList();
myLinkedList.addAtHead(1);
myLinkedList.addAtTail(3);
myLinkedList.addAtIndex(1, 2);    // 链表变为 1->2->3
myLinkedList.get(1);              // 返回 2
myLinkedList.deleteAtIndex(1);    // 现在，链表变为 2->3
console.log(myLinkedList);
    
myLinkedList.get(0);              // 返回 2
console.log(myLinkedList);

翻转链表

206 翻转链表

反转一个单链表

每次只操作两个节点

pre指向前一个节点，cur指向后一个节点

链表为空或只有一个节点时，返回head

1
2
3
4
5
6
7
8
9
10
11
12
var reverseList = function(head) {
    if(!head || !head.next) return head
    let cur = head
    let pre = null
    while (cur) {
        let temp = cur.next
        cur.next = pre
        pre = cur
        cur = temp
    }
    return pre
};

两两交换链表的节点

24 两两交换链表中的节点

使用虚拟头节点

1
2
3
4
5
6
7
8
9
10
11
12
13
14
var swapPairs = function(head) {
    let dummyHead = new ListNode(0, head)
    let cur = dummyHead
    while(cur.next && cur.next.next) {
        let temp = cur.next
        let temp1 = cur.next.next
        let temp2 = cur.next.next.next
        cur.next = temp1
        temp1.next = temp
        temp.next = temp2
        cur = temp
    }
    return dummyHead.next
};

删除链表的第n个节点

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

重点在于使用双指针，一次实现找到倒数第n个

使用虚拟头节点

  1. 先让fast移动n+1次
  2. 再同时移动slow和fast直到fast为null
  3. 这样slow就移动了 size - （n+1）次，刚好指向倒数第n个结点的前一个节点 可以执行删除操作
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
var removeNthFromEnd = function(head, n) {
    let dummyHead = new ListNode(0, head)
    let fast = dummyHead
    let slow = dummyHead
    n++
    while (n--) {
        fast = fast.next
    } 
    while (fast) {
        fast = fast.next
        slow = slow.next
    }
    slow.next = slow.next.next
    return dummyHead.next
}

链表相交

160 链表相交

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
/**
 * Definition for singly-linked list.
 * function ListNode(val) {
 *     this.val = val;
 *     this.next = null;
 * }
 */

/**
 * @param {ListNode} headA
 * @param {ListNode} headB
 * @return {ListNode}
 */
var getListLength = function(head) {
    let len = 0, cur = head
    while(cur) {
        len++
        cur = cur.next
    }
    return len
}
var getIntersectionNode = function(headA, headB) {
    let lenA = getListLength(headA)
    let lenB = getListLength(headB)
    let curA = headA
    let curB = headB
    if(lenA < lenB) {
        let temp = curA
        curA = curB
        curB = temp

        temp = lenA
        lenA = lenB
        lenB = temp
    }
    let i = lenA - lenB
    while(i--) {
        curA = curA.next
    }
    while(curA && curA !==curB) {
        curA = curA.next
        curB = curB.next
    }
    return curA
};

环形链表

142 环形链表

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

判断环？

遍历链表过程中，如果指到null，就是有环，反之就是没有

找出环的入口

假设链表非环部分长度为a 环长度为b

设置快慢指针，快指针每次都比慢多移动一次，当二者相遇时，若慢指针移动次数为s，快指针fast移动次数为s+nb，由于快指针移动距离为慢指针2倍，所以s等于nb，慢指针移动了nb

由于环的入口为a + nb ，所以只需让慢指针移动a即可，只需让fast再指向a，当fast和slow相遇时，即为所求

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
/**
 * Definition for singly-linked list.
 * function ListNode(val) {
 *     this.val = val;
 *     this.next = null;
 * }
 */

/**
 * @param {ListNode} head
 * @return {ListNode}
 */
var detectCycle = function(head) {
    let fast = head
    let slow = head
    while (fast && fast.next) {
        fast = fast.next.next
        slow = slow.next
        if(slow === fast) {
            fast = head
            while(fast !== slow) {
                slow = slow.next
                fast = fast.next
            }
            return slow
        }
    }
    return null
};

哈希表

有效的字母异位词

242 有效的字母异位词

数组也是一种哈希表

用空间存储换时间

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
/**
 * @param {string} s
 * @param {string} t
 * @return {boolean}
 */
var isAnagram = function(s, t) {
    let checkArray = new Array(26).fill(0)
    for (let char of s) {
        const index = char.charCodeAt(0) - 'a'.charCodeAt(0)
        checkArray[index]++
    }
    for (let char of t) {
        const index = char.charCodeAt(0) - 'a'.charCodeAt(0)
        checkArray[index]--
    }
    for (let index in checkArray) {
        if(checkArray[index] !== 0) return false 
    }
    return true
};

383 赎金信

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
/**
 * @param {string} ransomNote
 * @param {string} magazine
 * @return {boolean}
 */
var canConstruct = function(ransomNote, magazine) {
    let checkArray = new Array(128).fill(0)
    for (char of ransomNote) {
        const index = char.charCodeAt(0)
        checkArray[index]++
    }
    for (char of magazine) {
        const index = char.charCodeAt(0)
        checkArray[index]--
    }
    for (index in checkArray) {
        if(checkArray[index] > 0) return false 
    }
    return true
};

49 字母异位词分组

map的键能够是任何类型

这里将经过排序后的字母异位词分组，起到了索引作用

题中用到了几个方法

Array.from(map.values) 将哈希表的值转成数组

map.get(key) 已知键，获得哈希表的值

map.set(key, value) 设置哈希表的键值

map.values() 获得哈希表值的迭代器，迭代器效果就和let str of strs里的 strs一样 

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
/**
 * @param {string[]} strs
 * @return {string[][]}
 */
var groupAnagrams = function(strs) {
    const map = new Map()
    for (let str of strs) {
        let array = str.split('')
        let key = array.sort().toString()
        console.log(key)
        let value = map.get(key) ? map.get(key) : new Array()
        value.push(str)
        map.set(key, value)
    }
    return Array.from(map.values())
};

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

滑动窗口

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
/**
 * @param {string} s
 * @param {string} p
 * @return {number[]}
 */
let checkStr = function(sArray, pArray) {
    for (let i = 0; i < 26; i++) {
        if(sArray[i] !== pArray[i]) return false
    }
    return true
}
var findAnagrams = function(s, p) {
    if(s.length < p.length) return []
    let sArray = new Array(26).fill(0)
    let pArray = new Array(26).fill(0)
    let num = []
    let start = 0, end = 0
    for (let char of p) {
        const index = char.charCodeAt(0) - 'a'.charCodeAt(0)
        pArray[index]++
    }
    while (start <= end && end < s.length) {
        while (end + 1 - start < p.length) {
            const index = s[end].charCodeAt(0) - 'a'.charCodeAt(0)
            sArray[index]++
            end++
        }
        if(end + 1 - start === p.length) {
            let index = s[end].charCodeAt(0) - 'a'.charCodeAt(0)
            sArray[index]++
            if (checkStr(sArray, pArray)) {
                num.push(start)
            } 
            index = s[start].charCodeAt(0) - 'a'.charCodeAt(0)
            sArray[index]--
            start++
            end++
        }
    }
    return num
};

两个数组的交集

349 两个数组的交集

给定两个数组，返回交集

1
2
3
4
5
6
7
8
9
10
11
12
13
/**
 * @param {number[]} nums1
 * @param {number[]} nums2
 * @return {number[]}
 */
var intersection = function(nums1, nums2) {
    let nums1Map = new Set(nums1)
    let res = new Set()
    for (let num of nums2) {
        if(nums1Map.has(num)) res.add(num)
    }
    return Array.from(res)
};

350 两个数组的交集 II

给定两个数组，返回两个数组中都出现的数，次数是俩数组中较少的

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
/**
 * @param {number[]} nums1
 * @param {number[]} nums2
 * @return {number[]}
 */
var intersect = function(nums1, nums2) {
    let res = new Map()
    let ans = []
    for (let num1 of nums1) {
        if(res.has(num1)) {
            let value = res.get(num1)
            value++
            res.set(num1, value)
        } else {
            res.set(num1, 1)
        }
    }
    for (let num2 of nums2) {
        let value = res.get(num2)
        if(res.has(num2)) {
            if(value > 0) {
                ans.push(num2)
                value--
                res.set(num2, value)
            }
        }
    }
    return ans
};

快乐数

202 快乐数

如果在过程中，得到了之前变过的数，就不是快乐数，用set存放变过的数

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
/**
 * @param {number} n
 * @return {boolean}
 */
let trans = function (n) {
    let sum = 0
    while(n > 0) {
        let i = n % 10
        sum += i * i
        n = Math.floor(n / 10)
    }
    return sum
}
var isHappy = function(n) {
    let res = new Set([n])
    while(n !== 1){
        n = trans(n)
        console.log(n)
        if(res.has(n)) return false
        else res.add(n)
    }
    return true
};

两数之和

1 两数之和

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
/**
 * @param {number[]} nums
 * @param {number} target
 * @return {number[]}
 */
var twoSum = function(nums, target) {
    let map = new Map()
    for(let i = 0; i < nums.length; i++) {
        let index = nums[i]
        let value = i
        let key = target - index
        if(map.has(key)) return [map.get(key), value]
        else map.set(index, value)
    }
};

四数相加II

454 四数相加

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
/**
 * @param {number[]} nums1
 * @param {number[]} nums2
 * @param {number[]} nums3
 * @param {number[]} nums4
 * @return {number}
 */
var fourSumCount = function(nums1, nums2, nums3, nums4) {
    let map = new Map()
    let res = 0
    for (let a of nums1) {
        for (let b of nums2) {
            let value = a + b
            if(map.has(value)) map.set(value, map.get(value) + 1)
            else map.set(value, 1)    
        } 
    }
    for(let c of nums3) {
        for(let d of nums4) {
            let value = 0 - c - d
            if(map.has(value)) res += map.get(value)    
        }
    }      
    return res
};

三数之和

15 三数之和

双指针，注意去重

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
/**
 * @param {number[]} nums
 * @return {number[][]}
 */
var threeSum = function(nums) {
    nums.sort((a, b) => a - b)
    let res = []
    for (let i = 0; i < nums.length; i++) {
        if (nums[i] > 0) return res
        if (i > 0 && nums[i] === nums[i - 1]) continue
        let left = i + 1
        let right = nums.length - 1
        while (left < right) {
            let sum = nums[left] + nums[right]
            let target = 0 - nums[i]
            // console.log(sum, target)
            if(sum > target) right--
            else if(sum < target) left++
            else {
                res.push([nums[i], nums[left], nums[right]])
                left++
                while (left < right && nums[left] === nums[left - 1]) {
                    left++
                }
                right--
                while (left < right && nums[right] === nums[right + 1]) {
                    right--
                }
            }
        }
    }
    return res
};

四树之和

18 四数之和

同理，注意剪枝和去重

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
/**
 * @param {number[]} nums
 * @param {number} target
 * @return {number[][]}
 */
var fourSum = function(nums, target) {
    nums.sort((a, b) => a - b)
    let res = []
    for (let k = 0; k < nums.length; k++) {
        if(nums[k] > target && target > 0) break
        if(k > 0 && nums[k] === nums[k - 1]) continue
        for(let i = k + 1; i < nums.length; i++) {
            if(nums[i] + nums[k] > target && target > 0) break
            if(i > k + 1 && nums[i] === nums[i - 1]) continue
            let left = i + 1
            let right = nums.length - 1
            while(left < right) {
                let sum1 = nums[left] + nums[right]
                let sum2 = target - nums[k] - nums[i]
                if(sum1 > sum2) right--
                else if(sum1 < sum2) left++
                else {
                    res.push([nums[k], nums[i], nums[left], nums[right]])
                    left++
                    while(left < right && nums[left] === nums[left - 1]) {
                        left++
                    }
                    right--
                    while(left < right && nums[right] === nums[right + 1]) {
                        right--
                    }
                } 
            } 
        }
    }
    return res
};

字符串

反转字符串

344 反转字符串

双指针

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
/**
 * @param {character[]} s
 * @return {void} Do not return anything, modify s in-place instead.
 */
var reverseString = function(s) {
    let start = 0
    let end = s.length - 1
    while (start < end) {
        let temp = s[start]
        s[start] = s[end]
        s[end] = temp
        start++
        end--
    }
};

反转字符串II

541 反转字符串

只反转每2*k的k部分

最后如果要反转的小于k，就反转剩余

最后如果要反转的大于k小于2*k，就反转前k部分

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
/**
 * @param {string} s
 * @param {number} k
 * @return {string}
 */
let reverse = function(s, start, end) {
    s = Array.from(s)
    while(end > start) {
        let temp = s[end]
        s[end] = s[start]
        s[start] = temp
        start++
        end--
    }
    s = s.join('')
    return s
}
var reverseStr = function(s, k) {
    for(let i = 0; i < s.length; i += 2 * k) {
        if(i + k - 1 <= s.length - 1) {
            s = reverse(s, i , i + k - 1)
            continue
        }
        s = reverse(s, i, s.length - 1)
    }
    return s 
};

替换数字

不开额外数组，在原数组上进行改动

题目链接

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
const readline = require('readline')
const rl = readline.createInterface({
    input: process.stdin,
    output: process.stdout
})
function main () {
    const isAz = str => str >= 'a' && str <= 'z'
    const isNumber = str => str >= '0' && str <= '9'
    rl.on('line', line => {
        let n = 0
        
        for (let i = 0; i < line.length; i++) {
            let str = line[i]
            if (isAz(str)) n++
            if (isNumber(str)) n += 6
        }
        line = Array.from(line)
        let index = line.length - 1
        line.length = n
        for (let i = n - 1; i >= 0; i--) {
            let str = line[index]
            if(isAz(str)) line[i] = str
            if(isNumber(str)) {
                line[i] = 'r'
                line[i - 1] = 'e'
                line[i - 2] = 'b'
                line[i - 3] = 'm'
                line[i - 4] = 'u'
                line[i - 5] = 'n'
                i -= 5
            }
            index--
        }
        console.log(line.join(''))
    })
}
main()

151 反转字符串的单词

思路

  1. 翻转整个字符串
  2. 去除多余空格
  3. 翻转字符串中的每个单词

利用双指针，打到时间复杂度O(n)，空间复杂度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
37
38
39
40
41
42
43
44
45
46
47
/**
 * @param {string} s
 * @return {string}
 */
// 左闭右开
const reverse = (s, start, end) => {
    s = Array.from(s)
    end = end - 1
    while (start < end) {
        let temp = s[start]
        s[start] = s[end]
        s[end]= temp
        start++
        end--
    }
    return s.join('')
}
const removeSpace = s => {
    s = Array.from(s)
    let slow = 0, fast = 0
    while(fast < s.length) {
        if(s[fast] === ' ' && (slow === 0 || s[slow - 1] === ' ')) {
            fast++
        } else {
            s[slow++] = s[fast++]
        }
    }
    s.length = s[slow - 1] === ' ' ? slow - 1 : slow
    return s.join('')
}
var reverseWords = function(s) {
    s = reverse(s, 0, s.length)
    s = removeSpace(s)
    let slow = 0, fast = 0
    while (fast < s.length) {
        if(s[fast] === ' ') {
            s = reverse(s, slow, fast)
            slow = fast + 1
        }
        fast++
    }
    if(fast === s.length) s = reverse(s, slow, fast)
    return s
};
// console.log(reverse('winter is home again',0,7))
// console.log(removeSpace('  winter    is home again    '))
// console.log(reverseWords('the sky is blue'))

右旋转字符串

题目链接

思路：

先反转字符串，再反转前部分和后部分即可

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
const readline = require('readline')
const rl = readline.createInterface({
    input: process.stdin,
    output: process.stdout
})
const reverse  = (s, start, end) => {
    s = Array.from(s)
    end--
    while (start < end) {
        let temp = s[start]
        s[start] = s[end]
        s[end] = temp
        start++
        end--
    }
    return s.join('')
}
const main = () => {
    let input = []
    rl.on('line', line => {
        input.push(line)
    })
    rl.on('close', () => {
        let k = input[0] - '0'
        let s = input[1]
        s = reverse(s, 0, s.length)
        s = reverse(s, 0, k)
        s = reverse(s, k, s.length)
        console.log(s)
    })
}
main()

kmp子串匹配

28 找出字符串中第一个匹配的下标

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
/**
 * @param {string} haystack
 * @param {string} needle
 * @return {number}
 */
const getNext = (s) => {
    let next = new Array(s.length).fill(0)
    let j = 0, i = 1
    next[j] = 0
    for (let i = 1; i < s.length; i++) {
        while (s[i] !== s[j] && j > 0) {
            j = next[j - 1]
        }
        if (s[i] === s[j]) {
            j++
        }
        next[i] = j 
    }
    return next
}
var strStr = function(haystack, needle) {
    let next = getNext(needle)
    let i = 0, j = 0
    for (i = 0; i < haystack.length; i++) {
        while (haystack[i] !== needle[j] && j > 0) {
            j = next[j - 1]
        }
        if(haystack[i] === needle[j]) {
            j++
        }
        if(j === needle.length) return i - needle.length + 1
    }
    return -1
};

重复的子字符串

451 重复的子字符串

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
/**
 * @param {string} s
 * @return {boolean}
 */
const getNext = (s) => {
    let next = Array(s.length).fill(0)
    let j = 0, i = 1
    next[0] = 0
    for(i = 1; i < s.length; i++) {
        while (j > 0 && s[i] !== s[j]) {
            j = next[j - 1]
        }
        if (s[i] === s[j]) j++
        next[i] = j
    }
    return next
}
const find = (s, son) => {
    let next = getNext(son)
    let i = 0, j = 0
    for (i = 0; i < s.length; i++) {
        while (s[i] !== son[j] && j > 0) {
            j = next[j - 1]
        }
        if (s[i] === son[j]) j++
        if(j === son.length) return true
    }
    return false
}
var repeatedSubstringPattern = function(s) {
    let newS = s + s
    newS = newS.substring(1, newS.length - 1)
    return find(newS, s)
};
// repeatedSubstringPattern('abaababaab')

栈与队列

用栈模拟队列

232 用栈实现队列

思路

  1. 用两个栈模拟队列，一个进栈，一个出栈
  2. 执行入队列操作时，只从进栈入
  3. 执行出队列操作时，先将进栈的元素全部出到出栈，再对出栈进行pop操作
  4. 执行看队头操作时，执行出队列操作，再将队头元素压入出栈，并返回队头元素
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

var MyQueue = function() {
    this.stackIn = []
    this.stackOut = []
};

/** 
 * @param {number} x
 * @return {void}
 */
MyQueue.prototype.push = function(x) {
    this.stackIn.push(x)
};

/**
 * @return {number}
 */
MyQueue.prototype.pop = function() {
    let size = this.stackOut.length
    if (size) {
        return this.stackOut.pop()
    } else {
        while (this.stackIn.length) {
            let x = this.stackIn.pop()
            this.stackOut.push(x)
        }
        return this.stackOut.pop()
    }
};

/**
 * @return {number}
 */
MyQueue.prototype.peek = function() {
    let x = this.pop()
    this.stackOut.push(x)
    return x
};

/**
 * @return {boolean}
 */
MyQueue.prototype.empty = function() {
    return !this.stackIn.length && !this.stackOut.length
};

用队列模拟栈

225 用队列实现栈

思路

  1. 用一个队列模拟栈

  2. 执行出栈操作时，将前面 n - 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

var MyStack = function() {
    this.queue = []
};

/** 
 * @param {number} x
 * @return {void}
 */
MyStack.prototype.push = function(x) {
    this.queue.push(x)
};

/**
 * @return {number}
 */
MyStack.prototype.pop = function() {
    let size = this.queue.length
    size--
    while (size--) {
        let x = this.queue.shift()
        this.queue.push(x)
    }
    return this.queue.shift()
};

/**
 * @return {number}
 */
MyStack.prototype.top = function() {
    let x = this.pop()
    this.push(x)
    return x
};

/**
 * @return {boolean}
 */
MyStack.prototype.empty = function() {
    return !this.queue.length
};

有效的括号

20 有效的括号

思路

  1. 遍历时，左括号全部进栈

  2. 遍历右括号时，匹配则出栈，不匹配或者栈为空则无效

  3. 最后栈为空有效，不为空无效

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
/**
 * @param {string} s
 * @return {boolean}
 */
const stackTop = (stack) => {
    let x = stack.pop()
    stack.push(x)
    return x
}
const stackEmpty = (stack) => !stack.length
var isValid = function(s) {
    if (s.length % 2 !== 0) return false
    let stack = []
    for (let i = 0; i < s.length; i++) {
        if (s[i] === '(') {
            stack.push(')')
        } else if (s[i] === '[') {
            stack.push(']')
        } else if (s[i] === '{') {
            stack.push('}')
        } else {
            if (!stackEmpty(stack) && stackTop(stack) === s[i]) {
                console.log(stack)
                stack.pop()
                console.log(stack)
            } else {
                return false
            }
        }
    }
    return stackEmpty(stack)
};

逆波兰表达式求值

150 逆波兰表达式求值

也是栈的一个经典应用 

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
/**
 * @param {string[]} tokens
 * @return {number}
 */
var evalRPN = function(tokens) {
    let stack = []
    for (let i = 0; i < tokens.length; i++) {
        if (isNaN(tokens[i] - '0')) {
            let num1 = stack.pop()
            let num2 = stack.pop()
            if (tokens[i] === '+') {
                stack.push(num2 + num1)
            }
            if (tokens[i] === '-') {
                stack.push(num2 - num1)
            }
            if (tokens[i] === '/') {
                stack.push(Math.trunc(num2 / num1))
            }
            if (tokens[i] === '*') {
                stack.push(num2 * num1)
            }
        } else {
            stack.push(tokens[i] - '0')
        }
        // console.log(stack)
    }
    return stack.pop()
};
// console.log(evalRPN(["2","1","+","3","*"]))

滑动窗口的最大值

239 滑动窗口最大值

单调队列求解

思路

  • 构建一个单调队列，队列有如下特点
    1. 队首到队尾单调递减
    2. 元素入队时如果队列中有小于自己的元素，直接剔除
    3. 元素出队时，只出队首的最大元素
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
/**
 * @param {number[]} nums
 * @param {number} k
 * @return {number[]}
 */
class MonoQueue {
    queue
    constructor () {
        this.queue = []
    }
    Empty = () => !this.queue.length
    Back = () => this.queue[this.queue.length - 1]
    enqueue = (value) => {
        while (!this.Empty() && value > this.Back()) {
            this.queue.pop()
        }
        this.queue.push(value)
    }
    dequeue = (value) => {
        if (this.Front() === value) this.queue.shift()
    }
    Front = () => this.queue[0]
} 
var maxSlidingWindow = function(nums, k) {
    let start = 0
    let end = 0
    let queue = new MonoQueue()
    let ans = []
    while (end < k) {
        queue.enqueue(nums[end])
        end++
    }
    ans.push(queue.Front())
    while (end < nums.length) {
        queue.enqueue(nums[end])
        queue.dequeue(nums[start])
        ans.push(queue.Front())
        start++
        end++
    }
    // console.log(ans)
    return ans
};
// maxSlidingWindow([1,3,-1,-3,5,3,6,7], 3)

前k个高频元素

347 前k个高频元素

解法1

利用哈希表map和排序

间复杂度O(nlogn) 空间复杂度O(n)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
/**
 * @param {number[]} nums
 * @param {number} k
 * @return {number[]}
 */
var topKFrequent = function(nums, k) {
    let map = new Map()
    for (let i =0; i < nums.length; i++) {
        let key = nums[i]
        map.set(key, (map.get(key) || 0) + 1)
    }
    let arr = [...map]
    arr.sort((a,b) => b[1] - a[1])
    let ans = []
    for (let i = 0; i < k; i++) {
        ans.push(arr[i][0])
    }
    return ans
};

解法2

小顶堆： 二叉树的父节点小于其子节点

大顶堆： 二叉树的父节点大于其子节点

使用优先级队列，手写堆实现优先级队列

  • 先用哈希表map存储元素key和元素出现次数value
  • 再利用小顶堆，将元素进k次，并将多余元素排除
  • 最后全部将优先级队列剩下的k个元素全部出队即可得到结果

写堆时需要注意的地方

  • 构造器的compare函数，使用传的参数compareFn决定了是大顶堆还是小顶堆，大于0时才交换，小于0时不交换

  • 当执行enqueue 操作时，将数据推入队列末尾，同时进行上浮操作

    上浮：二叉树里，当前元素和父元素对比，如果小（对于小顶堆而言）则进行上浮，否则则找到了对应的位置

  • 当执行dequeue操作时，保留队首元素并之后返回，并将队尾元素放到队首，进行下沉操作，

    下沉：二叉树里，当前元素和较小（小顶堆而言）子元素对比，如果大（对于小顶堆而言），则进行下沉，否则则找到了对应的位置

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
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
/**
 * @param {number[]} nums
 * @param {number} k
 * @return {number[]}
 */
class Heap {
    constructor (compareFn) {
        this.compareFn = compareFn
        this.queue = [] 
    }
    size = () => this.queue.length
    compare = (index1, index2) => {
        if (this.queue[index1] === undefined) return -1
        if (this.queue[index2] === undefined) return -1
        return this.compareFn(this.queue[index1], this.queue[index2])
    }
    enqueue = (item) => {
        this.queue.push(item)

        // 进行上浮操作
        let index = this.size() - 1
        let parent = Math.floor((index - 1) / 2)
        while (parent >= 0 && this.compare(parent, index) > 0) {
            [this.queue[index], this.queue[parent]] = [this.queue[parent], this.queue[index]]
            index = parent
            parent = Math.floor((index - 1) / 2)
        }
    }
    dequeue = () => {
        if (this.size() <= 1) {
            return this.queue.pop()
        }
        const outer = this.queue[0]

        this.queue[0] = this.queue.pop()

        // 进行下沉操作
        let index = 0
        let left = 2 * index + 1
        let searchChild = this.compare(left, left + 1) > 0 ? left + 1: left
        while (this.compare(index, searchChild) > 0) {
            [this.queue[index], this.queue[searchChild]] = [this.queue[searchChild], this.queue[index]]
            index = searchChild
            left = 2 * index + 1
            searchChild = this.compare(left, left + 1) > 0 ? left + 1: left
        }
        return outer
    }
} 
var topKFrequent = function (nums, k) {
    const map = new Map();
    const res = [];
    //使用 map 统计元素出现频率
    for (const num of nums) {
      map.set(num, (map.get(num) || 0) + 1);
    }
    //创建小顶堆
    const heap = new Heap((a, b) => a.value - b.value)
    for (const [key, value] of map) {
      heap.enqueue({ key, value });
      if (heap.size() > k) heap.dequeue();
    }
    //处理输出
    while (heap.size()) res.push(heap.dequeue().key);
    // console.log(res)
    return res;
  };
// topKFrequent([1, 1, 1, 2, 2, 2, 9, 8, 1, 3, 4], 2)

二叉树

二叉树的递归遍历

144 145 94 二叉树的前序、后序、中序遍历

1
2
3
4
5
6
7
8
9
10
11
const traversal = (node, nums) => {
    if (node === null) return
    nums.push(node.val)
    traversal(node.left, nums)
    traversal(node.right, nums)
}
var preorderTraversal = function(root) {
    let res = []
    traversal(root, res)
    return res
};
1
2
3
4
5
6
7
8
9
10
11
const traversal = (node, nums) => {
    if (node === null) return
    traversal(node.left, nums)
    nums.push(node.val)
    traversal(node.right, nums)
}
var inorderTraversal = function(root) {
    let res = []
    traversal(root, res)
    return res
};
1
2
3
4
5
6
7
8
9
10
11
const traversal = (node, nums) => {
    if (node === null) return
    traversal(node.left, nums)
    traversal(node.right, nums)
    nums.push(node.val)
}
var inorderTraversal = function(root) {
    let res = []
    traversal(root, res)
    return res
};

二叉树的迭代遍历

144 145 94先序遍历 中序遍历 后序遍历

先序遍历的思路

  • 根节点结点进栈
  • 栈不为空，则出栈，出栈元素录入结果
  • 进出栈元素的右结点，再进左结点
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
/**
 * 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 preorderTraversal = function(root) {
    let res = []
    if(!root) return res
    let stack = [root]
    const stackEmpty = stack => !stack.length
    while (!stackEmpty(stack)) {
        const cur = stack.pop()
        res.push(cur.val)
        cur.right && stack.push(cur.right)
        cur.left && stack.push(cur.left)
    }
    return res
};

后序遍历的思路

在先序遍历的基础上 变为左结点入栈后 再右节点入栈，然后再倒序数组即可

即 中左右 -> 中右左 -> 左右中

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
/**
 * 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[]}
 */
const reverse = (res) =>{
    let start = 0, end = res.length - 1
    while (start < end) {
        [res[start], res[end]] = [res[end], res[start]]
        start++
        end--
    }
    return res
}
var postorderTraversal = function(root) {
    let res = []
    if(!root) return res
    let stack = [root]
    const stackEmpty = stack => !stack.length
    while (!stackEmpty(stack)) {
        const cur = stack.pop()
        res.push(cur.val)
        cur.left && stack.push(cur.left)
        cur.right && stack.push(cur.right)
    }
    res = reverse(res)
    return res
};

中序遍历的思路

  1. 根节点进栈，一路向左进栈

  2. 遇到为空结点，指针指向栈顶，栈顶元素进数组

  3. 指针指向栈顶元素右节点，返回步骤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
/**
 * 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 inorderTraversal = function(root) {
    let res = []
    let st = []
    let cur = root
    while (cur !== null || st.length) {
        if (cur !== null) {
            st.push(cur)
            cur = cur.left
        } else {
            cur = st.pop()
            res.push(cur.val)
            cur = cur.right
        }
    }
    return res
};

二叉树的统一迭代法

144 145 94先序遍历 中序遍历 后序遍历

思路： 标记法

将访问的节点放入栈中，对要处理的节点放入栈中但是做标记

做标记的方法：先放一个空指针进栈，再放元素进栈

中序代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
var inorderTraversal = function(root) {
    const top = stack => stack[stack.length - 1]
    let res = []
    let st = []
    if(root) {st.push(root)}
    while(st.length) {
        let node = top(st)
        if (node !== null) {
            st.pop()
            if (node.right) {st.push(node.right)}

            st.push(node)
            st.push(null)

            if (node.left) {st.push(node.left)}
        } else {
            st.pop()
            res.push(st.pop().val)
        }
    }    
    return res
};

前序代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
var preorderTraversal = function(root) {
    const top = stack => stack[stack.length - 1]
    let res = []
    let st = []
    if(root) {st.push(root)}
    while(st.length) {
        let node = top(st)
        if (node !== null) {
            st.pop()
            if (node.right) {st.push(node.right)}
            if (node.left) {st.push(node.left)}
            st.push(node)
            st.push(null)
        } else {
            st.pop()
            res.push(st.pop().val)
        }
    }    
    return res
};

后序

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
var postorderTraversal = function(root) {
    const top = stack => stack[stack.length - 1]
    let res = []
    let st = []
    if(root) {st.push(root)}
    while(st.length) {
        let node = top(st)
        if (node !== null) {
            st.pop()
            st.push(node)
            st.push(null)
            if (node.right) {st.push(node.right)}
            if (node.left) {st.push(node.left)}
        } else {
            st.pop()
            res.push(st.pop().val)
        }
    }    
    return res
};

二叉树的层序遍历

102 二叉树的层序遍历

队列

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
/**
 * @param {TreeNode} root
 * @return {number[][]}
 */
var levelOrder = function(root) {
    let res = []
    let queue = []
    if(root) {queue.push(root)}
    while (queue.length) {
        let len = queue.length
        let arr = []
        while(len--) {
            let node = queue.shift()
            if (node) {arr.push(node.val)}
            if (node.left) {queue.push(node.left)}
            if (node.right) {queue.push(node.right)}
        }
        res.push(arr)
    }
    return res
};