hxy的博客

Mia san Mia!

0%

哈希堆栈队列刷题

发表于 更新于 分类于 Valine：

按照算法和数据结构进行分类，一起来刷题，用于自己在面试前查漏补缺。我的意向岗位是前端，选择用javascript来刷题，优点是动态语言，语法简单，缺点是遇见复杂数据结构会出现较难的写法，如堆、并查集，每题对应leetcode的题号。本篇是哈希堆栈队列

专题部分

哈希堆栈队列

1. 两数之和

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

你可以假设每种输入只会对应一个答案。但是，数组中同一个元素在答案里不能重复出现。

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

示例 1：

1
2
3
输入：nums = [2,7,11,15], target = 9
输出：[0,1]
解释：因为 nums[0] + nums[1] == 9 ，返回 [0, 1] 。

示例 2：

1
2
输入：nums = [3,2,4], target = 6
输出：[1,2]

示例 3：

1
2
输入：nums = [3,3], target = 6
输出：[0,1]

提示：

  • 2 <= nums.length <= 104
  • -109 <= nums[i] <= 109
  • -109 <= target <= 109
  • 只会存在一个有效答案

进阶：你可以想出一个时间复杂度小于 $$O(n^2)$$的算法吗？

哈希表

1
2
3
4
5
6
7
8
9
10
11
12
13
14
/**
 * @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++){
        if (map[target - nums[i]] !== undefined){
            return [map[target - nums[i]], i];
        }
        map[nums[i]] = i;
    }
};

4. 寻找两个正序数组的中位数

给定两个大小分别为 m 和 n 的正序（从小到大）数组 nums1 和 nums2。请你找出并返回这两个正序数组的 中位数 。

示例 1：

1
2
3
输入：nums1 = [1,3], nums2 = [2]
输出：2.00000
解释：合并数组 = [1,2,3] ，中位数 2

示例 2：

1
2
3
输入：nums1 = [1,2], nums2 = [3,4]
输出：2.50000
解释：合并数组 = [1,2,3,4] ，中位数 (2 + 3) / 2 = 2.5

示例 3：

1
2
输入：nums1 = [0,0], nums2 = [0,0]
输出：0.00000

示例 4：

1
2
输入：nums1 = [], nums2 = [1]
输出：1.00000

示例 5：

1
2
输入：nums1 = [2], nums2 = []
输出：2.00000

提示：

  • nums1.length == m
  • nums2.length == n
  • 0 <= m <= 1000
  • 0 <= n <= 1000
  • 1 <= m + n <= 2000
  • -106 <= nums1[i], nums2[i] <= 106

进阶：你能设计一个时间复杂度为 O(log (m+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
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
/**
 * @param {number[]} nums1
 * @param {number[]} nums2
 * @return {number}
 */
var findMedianSortedArrays = function(nums1, nums2) {
    let len1 = nums1.length, len2 = nums2.length;
    let totallen =len1 + len2;
    if (totallen & 1){
        //总长度为奇数
        let minIndex = totallen >> 1;
        return getKthElement(nums1, nums2, minIndex + 1);
    } else {
        //总长度为偶数
        let minIndex1 = (totallen >> 1) - 1, minIndex2 = totallen >> 1;
        return (getKthElement(nums1, nums2, minIndex1 + 1) + getKthElement(nums1, nums2, minIndex2 + 1)) / 2;
    } 
};

var getKthElement = function(nums1, nums2, k) {
    /* 主要思路：要找到第 k (k>1) 小的元素，那么就取 pivot1 = nums1[k/2-1] 和 pivot2 = nums2[k/2-1] 进行比较
    * 这里的 "/" 表示整除
    * nums1 中小于等于 pivot1 的元素有 nums1[0 .. k/2-2] 共计 k/2-1 个
    * nums2 中小于等于 pivot2 的元素有 nums2[0 .. k/2-2] 共计 k/2-1 个
    * 取 pivot = min(pivot1, pivot2)，两个数组中小于等于 pivot 的元素共计不会超过 (k/2-1) + (k/2-1) <= k-2 个
    * 这样 pivot 本身最大也只能是第 k-1 小的元素
    * 如果 pivot = pivot1，那么 nums1[0 .. k/2-1] 都不可能是第 k 小的元素。把这些元素全部 "删除"，剩下的作为新的 nums1 数组
    * 如果 pivot = pivot2，那么 nums2[0 .. k/2-1] 都不可能是第 k 小的元素。把这些元素全部 "删除"，剩下的作为新的 nums2 数组
    * 由于我们 "删除" 了一些元素（这些元素都比第 k 小的元素要小），因此需要修改 k 的值，减去删除的数的个数
    */
    let len1 = nums1.length, len2 = nums2.length;
    let index1 = 0, index2 = 0;
    let kthElement = 0;

    while (true) {
        //边界情况
        if (index1 == len1) {
            return nums2[index2 + k - 1];
        }
        if (index2 == len2) {
            return nums1[index1 + k - 1];
        }
        if (k == 1) {
            return Math.min(nums1[index1], nums2[index2]);
        }

        //正常情况
        let half = k >> 1;
        let newIndex1 = Math.min(index1 + half, len1) - 1;
        let newIndex2 = Math.min(index2 + half, len2) - 1;
        let pivot1 = nums1[newIndex1], pivot2 = nums2[newIndex2];
        if (pivot1 <= pivot2) {
            // 排除数组1中的数
            k -= (newIndex1 - index1 + 1);
            index1 = newIndex1 + 1;
        } else {
            // 排除数组2中的数
            k -= (newIndex2 - index2 + 1);
            index2 = newIndex2 + 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
/**
 * @param {number[]} nums1
 * @param {number[]} nums2
 * @return {number}
 */
var findMedianSortedArrays = function(nums1, nums2) {
    let i = 0;
    for(; i < nums1.length; i++){
        if(nums2[0] < nums1[i]){
            nums1.splice(i, 0, nums2[0]);
            nums2.shift();
        }
        if(nums2.length == 0){
            break;
        }
    }
    if(i === nums1.length){
        nums1 = nums1.concat(nums2);
    }

    if(nums1.length % 2 == 0){
        return (nums1[parseInt((nums1.length - 1) / 2)] + nums1[parseInt((nums1.length) / 2) ]) / 2;
    }else{
        return nums1[(nums1.length - 1) / 2];
    }
};

20. 有效的括号

给定一个只包括 '('，')'，'{'，'}'，'['，']' 的字符串 s ，判断字符串是否有效。

有效字符串需满足：

  1. 左括号必须用相同类型的右括号闭合。
  2. 左括号必须以正确的顺序闭合。

示例 1：

1
2
输入：s = "()"
输出：true

示例 2：

1
2
输入：s = "()[]{}"
输出：true

示例 3：

1
2
输入：s = "(]"
输出：false

示例 4：

1
2
输入：s = "([)]"
输出：false

示例 5：

1
2
输入：s = "{[]}"
输出：true

提示：

  • 1 <= s.length <= 104
  • s 仅由括号 '()[]{}' 组成

栈存放最后一个 '([{' 

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
/**
 * @param {string} s
 * @return {boolean}
 */
var isValid = function(s) {
    if (s.length % 2) return false;
    let arr = [];
    //遇到({[往堆栈顶上压入，遇到)}]则取出顶上的元素判断是否为对应的左括号，如果不是返回错误
    for (char of s)
        switch (char) {
            case "(":
            case "[":
            case "{": arr.push(char); break;
            case ")": if (arr.pop() !== "(") return false; break;
            case "]": if (arr.pop() !== "[") return false; break;
            case "}": if (arr.pop() !== "{") return false; break;
        };
    return !arr.length;
};

用个哈希表存放对应索引

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
/**
 * @param {string} s
 * @return {boolean}
 */
var isValid = function(s) {
    let n = s.length;
    if (n & 1) return false;
    let map = new Map([[')', '('], [']', '['], ['}', '{']]);
    let stack = [];
    for (let char of s) {
        if (map.has(char)) {
            if (stack.length === 0 || stack.pop() !== map.get(char)) {
                return false;
            }
        } else {
            stack.push(char);
        }
    }
    return stack.length === 0;
};

49. 字母异位词分组

给定一个字符串数组，将字母异位词组合在一起。字母异位词指字母相同，但排列不同的字符串。

示例:

1
2
3
4
5
6
7
输入: ["eat", "tea", "tan", "ate", "nat", "bat"]
输出:
[
  ["ate","eat","tea"],
  ["nat","tan"],
  ["bat"]
]

说明：

  • 所有输入均为小写字母。
  • 不考虑答案输出的顺序。

使用哈希表+字符串字母排序

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
/**
 * @param {string[]} strs
 * @return {string[][]}
 * 哈希表排序
 */
var groupAnagrams = function(strs) {
    // 哈希表
    const map = new Map();
    for (let str of strs) {
        // 单词字母排序
        let array = Array.from(str);
        array.sort();
        let key = array.toString();
        let list = map.get(key) ? map.get(key) : new Array();
        list.push(str);
        map.set(key, list);
    }
    return Array.from(map.values());
};

改用数组统计各字符串的字母个数。适用于每个字符串比较长的情况

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[]} strs
 * @return {string[][]}
 * 哈希表
 */
var groupAnagrams = function(strs) {
    // 哈希表
	let hash = new Map();
    let asciiA = 'a'.charCodeAt();
    for (let str of strs) {
        // 26个字母个数
        let arr = new Array(26).fill(0);
        // 统计各字母的个数
        for (let j = 0; j < str.length; j++) {
            arr[str.charCodeAt(j) - asciiA]++;
        }
        // 作为键
        let hashKey = arr.join();
        if(hash.has(hashKey)) {
            // 当前单词加入字母异位词分组
            let temp = hash.get(hashKey);
            temp.push(str);
            hash.set(hashKey, temp);
        } else {
            // 当前单词创建新的字母异位词分组
            hash.set(hashKey, [str]);
        }
    }
    return [...hash.values()];
};

84. 柱状图中最大的矩形

给定 n 个非负整数，用来表示柱状图中各个柱子的高度。每个柱子彼此相邻，且宽度为 1 。

求在该柱状图中，能够勾勒出来的矩形的最大面积。

img

以上是柱状图的示例，其中每个柱子的宽度为 1，给定的高度为 [2,1,5,6,2,3]。

img

图中阴影部分为所能勾勒出的最大矩形面积，其面积为 10 个单位。

示例:

1
2
输入: [2,1,5,6,2,3]
输出: 10

要想找到第 i 位置最大面积是什么？

是以i 为中心，向左找第一个小于 heights[i] 的位置 left_i；向右找第一个小于于 heights[i] 的位置 right_i，即最大面积为 heights[i] * (right_i - left_i -1)，如下图所示：

img

所以，我们的问题就变成如何找 right_i 和 left_i？

最简单的思路就是，就是暴力法，直接分别在 i 左右移动。

但是，这是一个时间复杂度为 $$O(n^2)$$，超时。

接下来想办法优化。

思路一：
当我们找 i 左边第一个小于 heights[i] 如果 heights[i-1] >= heights[i] 其实就是和 heights[i-1] 左边第一个小于 heights[i-1] 一样。依次类推，右边同理。

思路二：栈
利用单调栈

维护一个单调递增的栈，就可以找到 left_i 和 right_i。

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[]} heights
 * @return {number}
 */
var largestRectangleArea = function(heights) {
    // 为了防止栈是单调递增的，在开始和最后加入0，使得无论哪种输入，都有出栈过程
    heights.unshift(0);
    heights.push(0);
    let ans = 0;
    // 单调递增栈
    let stack = [];
    for(let i = 0; i < heights.length; i++){
        // 当前bar比栈顶bar矮
        while(stack.length !== 0 && heights[stack[stack.length - 1]] > heights[i]){
            // 栈顶元素出栈，并保存栈顶bar的索引
           let cur = stack.pop();
           let left = stack[stack.length - 1] + 1;
           let right = i - 1;
           // 计算面积，并挑战最大面积
           ans = Math.max(ans, ((right - left + 1) * heights[cur]));
        }
        // 当前bar比栈顶bar高了，入栈
        stack.push(i);
    }
    return ans;
};

85. 最大矩形

给定一个仅包含 0 和 1 、大小为 rows x cols 的二维二进制矩阵，找出只包含 1 的最大矩形，并返回其面积。

示例 1：

img

1
2
3
输入：matrix = [["1","0","1","0","0"],["1","0","1","1","1"],["1","1","1","1","1"],["1","0","0","1","0"]]
输出：6
解释：最大矩形如上图所示。

示例 2：

1
2
输入：matrix = []
输出：0

示例 3：

1
2
输入：matrix = [["0"]]
输出：0

示例 4：

1
2
输入：matrix = [["1"]]
输出：1

示例 5：

1
2
输入：matrix = [["0","0"]]
输出：0

提示：

  • rows == matrix.length
  • cols == matrix[0].length
  • 0 <= row, cols <= 200
  • matrix[i][j] 为 '0' 或 '1'

大家可以先做84 题，然后回来考虑这道题。

再想一下这个题，看下边的橙色的部分，这完全就是上一道题呀！

img

算法有了，就是求出每一层的 heights[] 然后传给上一题的函数就可以了。

利用上一题的栈解法。

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 {character[][]} matrix
 * @return {number}
 * 单调栈
 */
var maximalRectangle = function(matrix) {
    if(!matrix || matrix.length === 0){
        return 0;
    }
    function largestRectangleArea (heights) {
        let stack = [-1];
        for(let i = 0; i < heights.length; i++){
            while (stack.length > 1 && heights[stack[stack.length - 1]] >= heights[i]) {
                maxarea = Math.max(maxarea, heights[stack.pop()] * (i - stack[stack.length - 1] - 1));
            }
            stack.push(i);
        }
        while (stack.length > 1) {
            maxarea = Math.max(maxarea, heights[stack.pop()] * (heights.length - stack[stack.length - 1] - 1));
        }
    };
    let row = matrix.length;
    let col = matrix[0].length;
    // 最大矩形面积
    let maxarea = 0;
    // 初始化每列首位置的1个数
    for(let j = 0; j < col; j++){
        if(matrix[0][j] == '1'){
            matrix[0][j] = 1;
        }
    }
    largestRectangleArea(matrix[0]);
    for (let i = 1; i < row; i++) {
        for (let j = 0; j < col; j++) {
            // 遍历每一列，更新高度
            if(matrix[i][j] == '1'){
                matrix[i][j] = Number(matrix[i - 1][j]) + 1;
            }
        }
        // 求该行每个位置结尾的最大位置
        largestRectangleArea(matrix[i]);
    }
    return maxarea;
};

128. 最长连续序列

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

进阶：你可以设计并实现时间复杂度为 O(n) 的解决方案吗？

示例 1：

1
2
3
输入：nums = [100,4,200,1,3,2]
输出：4
解释：最长数字连续序列是 [1, 2, 3, 4]。它的长度为 4。

示例 2：

1
2
输入：nums = [0,3,7,2,5,8,4,6,0,1]
输出：9

提示：

  • 0 <= nums.length <= 104
  • -109 <= nums[i] <= 109

不排序，使用哈希能做到时间复杂度为 O(n)

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 longestConsecutive = function (nums) {
    let set = new Set(nums);
    let maxCount = 0;
    for (let num of set) {
        if (!set.has(num - 1)) {
            let tempnum = num;
            let count = 1;
            while (set.has(tempnum + 1)){
                tempnum++;
                count++;
            }
            maxCount = Math.max(maxCount, count);
        }
    }
    return maxCount;
};

146. LRU 缓存机制

运用你所掌握的数据结构，设计和实现一个 LRU (最近最少使用) 缓存机制 。

实现 LRUCache 类：

  • LRUCache(int capacity) 以正整数作为容量 capacity 初始化 LRU 缓存
  • int get(int key) 如果关键字 key 存在于缓存中，则返回关键字的值，否则返回 -1 。
  • void put(int key, int value) 如果关键字已经存在，则变更其数据值；如果关键字不存在，则插入该组「关键字-值」。当缓存容量达到上限时，它应该在写入新数据之前删除最久未使用的数据值，从而为新的数据值留出空间。

进阶：你是否可以在 O(1) 时间复杂度内完成这两种操作？

示例：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
输入
["LRUCache", "put", "put", "get", "put", "get", "put", "get", "get", "get"]
[[2], [1, 1], [2, 2], [1], [3, 3], [2], [4, 4], [1], [3], [4]]
输出
[null, null, null, 1, null, -1, null, -1, 3, 4]

解释
LRUCache lRUCache = new LRUCache(2);
lRUCache.put(1, 1); // 缓存是 {1=1}
lRUCache.put(2, 2); // 缓存是 {1=1, 2=2}
lRUCache.get(1);    // 返回 1
lRUCache.put(3, 3); // 该操作会使得关键字 2 作废，缓存是 {1=1, 3=3}
lRUCache.get(2);    // 返回 -1 (未找到)
lRUCache.put(4, 4); // 该操作会使得关键字 1 作废，缓存是 {4=4, 3=3}
lRUCache.get(1);    // 返回 -1 (未找到)
lRUCache.get(3);    // 返回 3
lRUCache.get(4);    // 返回 4

提示：

  • 1 <= capacity <= 3000
  • 0 <= key <= 10000
  • 0 <= value <= 105
  • 最多调用 2 * 105 次 get 和 put

利用Map对于set的数值为顺序插入的原理实现LRU

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
/**
 * @param {number} capacity
 */
var LRUCache = function(capacity) {
    this.capacity = capacity;
    this.cache = new Map();
};

/** 
 * @param {number} key
 * @return {number}
 */
LRUCache.prototype.get = function(key) {
    if(this.cache.has(key)) {
        var val = this.cache.get(key);
        this.cache.delete(key);
        this.cache.set(key, val);
        return val;
    } else {
        return -1;
    }
};

/** 
 * @param {number} key 
 * @param {number} value
 * @return {void}
 */
LRUCache.prototype.put = function(key, value) {
    if(this.cache.size < this.capacity && !this.cache.has(key)) {
        this.cache.set(key, value);
    } else if(this.cache.has(key)) {
        this.cache.delete(key);
        this.cache.set(key, value);
    } else if (this.cache.size = this.capacity) {
        // Map.prototype.keys() 返回一个迭代对象，而不是数组
        // 迭代对象 Iterator.next() 是迭代对象的第一个对象，而不是值，需要 .value获取值
        this.cache.delete(this.cache.keys().next().value);
        this.cache.set(key, value);
    }
};

/**
 * Your LRUCache object will be instantiated and called as such:
 * var obj = new LRUCache(capacity)
 * var param_1 = obj.get(key)
 * obj.put(key,value)
 */

get 查找快： hash表
put 操作快： 双向链表

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
/**
 * 
 * 思路因为需要在常数时间插入和删除其实map都具备，但对最近使用有个顺序，所以map不能完成
 * 但我们联想队列是可以实现的，又因为要常数时间插入和删除，我们得使用双向链表来完成。
 * 
 * 因此我们需要有一个map来存储key，value，双向链表来存储顺序。
 * 
 */

class Node {
    constructor(key, value) {
        this.prev = null;
        this.next = null;
        this.key = key;
        this.value = value;
    }
}

class DoubleList {
    constructor() {
        this.head = new Node(0, 0);
        this.tail = new Node(0, 0);

        this.head.next = this.tail;
        this.tail.prev =  this.head;

        this.size = 0;
    }

    addFirst(node) {
        node.next = this.head.next;
        node.prev = this.head;

        this.head.next.prev = node;
        this.head.next = node;
        this.size++;
    }

    remove(node) {
        node.prev.next = node.next;
        node.next.prev = node.prev;
        this.size--;
    }

    removeLast() {
        if (this.tail.prev == this.head)
            return null;

        let last = this.tail.prev;
        this.remove(last);

        return last;
    }
}

/**
 * 
 * 
 * @param {number} capacity
 */
var LRUCache = function(capacity) {
    this.map = new Map();
    // 最大容量
    this.capacity = capacity;
    this.cache = new DoubleList();
};

/** 
 * @param {number} key
 * @return {number}
 */
LRUCache.prototype.get = function(key) {
    if (!this.map[key]) {
        return -1;
    }

    let value = this.map[key].value;
    // 利用 put 方法把该数据提前
    this.put(key, value);

    return value;
};

/** 
 * @param {number} key 
 * @param {number} value
 * @return {void}
 */
LRUCache.prototype.put = function(key, value) {
    let node = new Node(key, value);
    if (this.map[key]) {
        // 删除旧的节点，新的插到头部
        this.cache.remove(this.map[key]);
        this.cache.addFirst(node);
        // 更新 map 中对应的数据
        this.map[key] = node;
    } else {
        if (this.capacity == this.cache.size) {
            // 删除链表最后一个数据
            let last = this.cache.removeLast();
            delete this.map[last.key];
        }
        // 直接添加到头部
        this.cache.addFirst(node);
        this.map[key] = node;
    }
};

/**
 * Your LRUCache object will be instantiated and called as such:
 * var obj = new LRUCache(capacity)
 * var param_1 = obj.get(key)
 * obj.put(key,value)
 */

155. 最小栈

设计一个支持 push ，pop ，top 操作，并能在常数时间内检索到最小元素的栈。

  • push(x) —— 将元素 x 推入栈中。
  • pop() —— 删除栈顶的元素。
  • top() —— 获取栈顶元素。
  • getMin() —— 检索栈中的最小元素。

示例:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
输入：
["MinStack","push","push","push","getMin","pop","top","getMin"]
[[],[-2],[0],[-3],[],[],[],[]]

输出：
[null,null,null,null,-3,null,0,-2]

解释：
MinStack minStack = new MinStack();
minStack.push(-2);
minStack.push(0);
minStack.push(-3);
minStack.getMin();   --> 返回 -3.
minStack.pop();
minStack.top();      --> 返回 0.
minStack.getMin();   --> 返回 -2.

提示：

  • pop、top 和 getMin 操作总是在 非空栈 上调用。

最小栈

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
/**
 * initialize your data structure here.
 */
var MinStack = function() {
    this.stack = [];
    this.min = [];
};

/** 
 * @param {number} x
 * @return {void}
 */
MinStack.prototype.push = function(x) {
    this.stack.push(x);
    if (this.min.length === 0 || x <= this.min[this.min.length - 1]) this.min.push(x);
};

/**
 * @return {void}
 */
MinStack.prototype.pop = function() {
    if (this.stack.length === 0) {
        return null;
    } else {
        let temp = this.stack.pop();
        if (temp === this.min[this.min.length - 1]) {
            this.min.pop();
        }
        return temp;
    }
};

/**
 * @return {number}
 */
MinStack.prototype.top = function() {
    if (this.stack.length === 0) return null;
    return this.stack[this.stack.length - 1];
};

/**
 * @return {number}
 */
MinStack.prototype.getMin = function() {
    if (this.min.length === 0) return null;
    return this.min[this.min.length - 1];
};

/**
 * Your MinStack object will be instantiated and called as such:
 * var obj = new MinStack()
 * obj.push(x)
 * obj.pop()
 * var param_3 = obj.top()
 * var param_4 = obj.getMin()
 */

394. 字符串解码

给定一个经过编码的字符串，返回它解码后的字符串。

编码规则为: k[encoded_string]，表示其中方括号内部的 encoded_string 正好重复 k 次。注意 k 保证为正整数。

你可以认为输入字符串总是有效的；输入字符串中没有额外的空格，且输入的方括号总是符合格式要求的。

此外，你可以认为原始数据不包含数字，所有的数字只表示重复的次数 k ，例如不会出现像 3a 或 2[4] 的输入。

示例 1：

1
2
输入：s = "3[a]2[bc]"
输出："aaabcbc"

示例 2：

1
2
输入：s = "3[a2[c]]"
输出："accaccacc"

示例 3：

1
2
输入：s = "2[abc]3[cd]ef"
输出："abcabccdcdcdef"

示例 4：

1
2
输入：s = "abc3[cd]xyz"
输出："abccdcdcdxyz"

使用栈

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 {string} s
 * @return {string}
 */
var decodeString = function (s) {
    // 保存需要 repeat 的字符串
    let stack = [];
    // 乘以的倍数
    let num = '';
    let str = '';
    for (c of s) {
        if (c >= 0) {
            num += c;
        } else if (c === '[') {
            stack.push([str, +num]);
            str = '';
            num = '';
        } else if (c === ']') {
            const [last_str, last_num] = stack.pop();
            str = last_str + str.repeat(last_num);
        } else {
            str += c;
        }
    }
    return str;
};

560. 和为K的子数组

给定一个整数数组和一个整数 k，你需要找到该数组中和为 k 的连续的子数组的个数。

示例 1 :

1
2
输入:nums = [1,1,1], k = 2
输出: 2 , [1,1] 与 [1,1] 为两种不同的情况。

说明 :

  1. 数组的长度为 [1, 20,000]。
  2. 数组中元素的范围是 [-1000, 1000] ，且整数 k 的范围是 [-1e7, 1e7]。

构造前缀和并穷举

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[]} nums
 * @param {number} k
 * @return {number}
 */
var subarraySum = function(nums, k) {
    let n = nums.length;
    // 构造前缀和
    let sum = new Array(n + 1);
    sum[0] = 0;
    for (let i = 0; i < n; i++) {
        sum[i + 1] = sum[i] + nums[i];
    }

    let ans = 0;
    // 穷举所有子数组
    for (let i = 1; i <= n; i++) {
        for (let j = 0; j < i; j++) {
            // sum of nums[j..i-1]
            if (sum[i] - sum[j] === k) {
                ans++;
            }
        }
    }
    return ans;
};

使用哈希优化时间

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
/**
 * @param {number[]} nums
 * @param {number} k
 * @return {number}
 */
var subarraySum = function(nums, k) {
    let count = 0, psum = 0;
    let hashmap = new Map();
    // 初始化很重要
    hashmap.set(0, 1);
    for (let num of nums) {
        psum += num;
        count += hashmap.get(psum - k) || 0;
        hashmap.set(psum, (hashmap.get(psum) || 0) + 1);
    }
    return count;
};

581. 最短无序连续子数组

给你一个整数数组 nums ，你需要找出一个 连续子数组 ，如果对这个子数组进行升序排序，那么整个数组都会变为升序排序。

请你找出符合题意的 最短 子数组，并输出它的长度。

示例 1：

1
2
3
输入：nums = [2,6,4,8,10,9,15]
输出：5
解释：你只需要对 [6, 4, 8, 10, 9] 进行升序排序，那么整个表都会变为升序排序。

示例 2：

1
2
输入：nums = [1,2,3,4]
输出：0

示例 3：

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

提示：

  • 1 <= nums.length <= 104
  • -105 <= nums[i] <= 105

进阶：你可以设计一个时间复杂度为 O(n) 的解决方案吗？

我们将数组 nums 进行排序，记为 nums_sorted​ 。然后我们比较 nums 和 nums_sorted 的元素来决定最左边和最右边不匹配的元素。它们之间的子数组就是要求的最短无序子数组。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
/**
 * @param {number[]} nums
 * @return {number}
 */
var findUnsortedSubarray = function(nums) {
    let snums = [...nums];
    nums.sort((a, b) => a - b);
    let start = nums.length, end = 0;
    for (let i = 0; i < nums.length; i++) {
        if (snums[i] !== nums[i]) {
            start = Math.min(start, i);
            end = Math.max(end, i);
        }
    }
    return (end - start >= 0 ? end - start + 1 : 0);
};

使用栈

这个方法背后的想法仍然是选择排序。我们需要找到无序子数组中最小元素和最大元素分别对应的正确位置，来求得我们想要的无序子数组的边界。

为了达到这一目的，此方法中，我们使用 栈。我们从头遍历 nums 数组，如果遇到的数字大小一直是升序的，我们就不断把对应的下标压入栈中，这么做的目的是因为这些元素在目前都是处于正确的位置上。一旦我们遇到前面的数比后面的数大，也就是 nums[j] 比栈顶元素小，我们可以知道 nums[j]一定不在正确的位置上。

为了找到 nums[j] 的正确位置，我们不断将栈顶元素弹出，直到栈顶元素比 nums[j] 小，我们假设栈顶元素对应的下标为 k ，那么我们知道 nums[j] 的正确位置下标应该是 k + 1。

我们重复这一过程并遍历完整个数组，这样我们可以找到最小的 k， 它也是无序子数组的左边界。

类似的，我们逆序遍历一遍 nums 数组来找到无序子数组的右边界。这一次我们将降序的元素压入栈中，如果遇到一个升序的元素，我们像上面所述的方法一样不断将栈顶元素弹出，直到找到一个更大的元素，以此找到无序子数组的右边界。

我们可以看下图作为参考。我们观察到上升还是下降决定了相对顺序，我们还可以观察到指针 b 在下标 0 后面标记着无序子数组的左边界，指针 a 在下标 7 前面标记着无序子数组的右边界。

img

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
 * @return {number}
 */
var findUnsortedSubarray = function(nums) {
    let stack = [];
    let l = nums.length, r = 0;
    for (let i = 0; i < nums.length; i++) {
        while(stack.length && nums[stack[stack.length - 1]] > nums[i]) {
            l = Math.min(l, stack.pop());
        }
        stack.push(i);
    }
    stack = [];
    for (let i = nums.length - 1; i >= 0; i--) {
        while(stack.length && nums[stack[stack.length - 1]] < nums[i]) {
            r = Math.max(r, stack.pop());
        }
        stack.push(i);
    }
    return r - l > 0 ? r - l + 1 : 0;
};

不使用额外空间

这个算法背后的思想是无序子数组中最小元素的正确位置可以决定左边界，最大元素的正确位置可以决定右边界。

因此，首先我们需要找到原数组在哪个位置开始不是升序的。我们从头开始遍历数组，一旦遇到降序的元素，我们记录最小元素为 min 。

类似的，我们逆序扫描数组 nums，当数组出现升序的时候，我们记录最大元素为 max。

然后，我们再次遍历 nums 数组并通过与其他元素进行比较，来找到 min 和 max 在原数组中的正确位置。我们只需要从头开始找到第一个大于 min 的元素，从尾开始找到第一个小于 max 的元素，它们之间就是最短无序子数组。

我们可以再次使用下图作为说明：

img

我们观察到指针 b 在下标 0 以后，标记着无序子数组的左边界，指针 a 在下标 7 以前，标记着无序子数组的右边界。

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
 * @return {number}
 */
var findUnsortedSubarray = function (nums) {
    if (nums.length === 0) return 0;

    let l = 0,
        r = nums.length - 1;
    while (nums[l + 1] >= nums[l]) l++;
    while (nums[r - 1] <= nums[r]) r--;

    if (r <= l) return 0;

    const unsorted = nums.slice(l, r + 1),
        min = Math.min(...unsorted),
        max = Math.max(...unsorted);
    
    while (nums[l - 1] > min) l--;
    while (nums[r + 1] < max) r++;
    return r - l + 1;
}

739. 每日温度

请根据每日 气温 列表 temperatures ，请计算在每一天需要等几天才会有更高的温度。如果气温在这之后都不会升高，请在该位置用 0 来代替。

示例 1:

1
2
输入: temperatures = [73,74,75,71,69,72,76,73]
输出: [1,1,4,2,1,1,0,0]

示例 2:

1
2
输入: temperatures = [30,40,50,60]
输出: [1,1,1,0]

示例 3:

1
2
输入: temperatures = [30,60,90]
输出: [1,1,0]

提示：

  • 1 <= temperatures.length <= 105
  • 30 <= temperatures[i] <= 100

单调递减栈

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
/**
 * @param {number[]} T
 * @return {number[]}
 */
var dailyTemperatures = function(T) {
    let len = T.length;
    let res = new Array(len).fill(0);
    let stack = [];
    for (let i = 0; i < len; i++) {
        let temperature = T[i];
        while (stack.length && temperature > T[stack[stack.length - 1]]) {
            let preIndex = stack.pop();
            res[preIndex] = i - preIndex;
        }
        stack.push(i);
    }
    return res;
};

1190. 反转每对括号间的子串

给出一个字符串 s（仅含有小写英文字母和括号）。

请你按照从括号内到外的顺序，逐层反转每对匹配括号中的字符串，并返回最终的结果。

注意，您的结果中 不应 包含任何括号。

示例 1：

1
2
输入：s = "(abcd)"
输出："dcba"

示例 2：

1
2
输入：s = "(u(love)i)"
输出："iloveu"

示例 3：

1
2
输入：s = "(ed(et(oc))el)"
输出："leetcode"

示例 4：

1
2
输入：s = "a(bcdefghijkl(mno)p)q"
输出："apmnolkjihgfedcbq"

提示：

  • 0 <= s.length <= 2000
  • 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
/**
 * @param {string} s
 * @return {string}
 * 使用栈反转每段字符串
 */
var reverseParentheses = function(s) {
    // 存储栈
    const stack = [];
    // 当前字符串
    let str = "";
    for (let char of s) {
        if (char === '(') {
            // 存入栈中
            stack.push(str);
            // 字符串清空
            str = '';
        } else if (char === ')') {
            // 翻转字符串
            str = str.split('').reverse().join('');
            // 字符串与最后一个拼接
            str = stack.pop() + str;
        } else {
            // 拼接字符串
            str = str + char;
        }
    }
    return str;
};

预处理括号

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 {string} s
 * @return {string}
 * 预处理括号
 */
var reverseParentheses = function(s) {
    const n = s.length;
    // 存储括号对应的位置
    const pair = new Array(n).fill(0);
    // 存储栈
    const stack = [];
    for (let i = 0; i < n; i++) {
        if (s[i] === '(') {
            // 存入栈中
            stack.push(i);
        } else if (s[i] === ')') {
            const j = stack.pop();
            pair[i] = j;
            pair[j] = i;
        }
    }
    const sb = [];
    let index = 0, step = 1;
    while (index < n) {
        if (s[index] === '(' || s[index] === ')') {
            // 找到其对应的配对括号位置
            index = pair[index];
            // 正反变化
            step = -step;
        } else {
            sb.push(s[index]);
        }
        // 按照顺序执行
        index += step;
    }
    return sb.join('');
};
-------------本文结束感谢您的阅读-------------

欢迎关注我的其它发布渠道