David Xue
0%

前端常考算法题

发表于 更新于 分类于 阅读次数： 评论：

前端常考算法题

  1. 长度最小的子数组

描述：

  1. 给定一个含有 n 个正整数的数组和一个正整数 target 。
  2. 找出该数组中满足其和 ≥ target 的长度最小的 连续子数组 [numsl, numsl+1, …, numsr-1, numsr] ，并返回其长度。如果不存在符合条件的子数组，返回 0 。

示例 1：
输入：target = 7, nums = [2,3,1,2,4,3]
输出：2
解释：子数组 [4,3] 是该条件下的长度最小的子数组。

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

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

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
//暴力解法 
var minSubArrayLen = function (target, nums) {
    let result = Number.MAX_SAFE_INTEGER; // 最终的结果
    let sum = 0; // 子序列的数值之和    
    let subLength = 0; // 子序列的长度
    for (let i = 0; i < nums.length; i++) { // 设置子序列起点为i
        sum = 0;
        for (let j = i; j < nums.length; j++) { // 设置子序列终止位置为j
            sum += nums[j];
            if (sum >= target) { // 一旦发现子序列和超过了s，更新result
                subLength = j - i + 1; // 取子序列的长度
                result = result < subLength ? result : subLength;
                break; // 因为我们是找符合条件最短的子序列，所以一旦符合条件就break
            }
        }
    }
    // 如果result没有被赋值的话，就返回0，说明没有符合条件的子序列
    return result === Number.MAX_SAFE_INTEGER ? 0 : result;
};
//滑动窗口解法
var minSubArrayLen = function(target, nums) {
    // 长度计算一次
    const len = nums.length;
    let l = r = sum = 0,
        res = len + 1; // 子数组最大不会超过自身
    while (r < len) {
        sum += nums[r++];
        // 窗口滑动
        while (sum >= target) {
            // r始终为开区间 [l, r)
            res = res < r - l ? res : r - l;
            sum -= nums[l++];
        }
    }
    return res > len ? 0 : res;
};

转：https://leetcode-cn.com/problems/minimum-size-subarray-sum/solution/dai-ma-sui-xiang-lu-dai-ni-xue-tou-hua-d-kb06/
  1. 复原 IP 地址

描述：

  1. 有效 IP 地址 正好由四个整数（每个整数位于 0 到 255 之间组成，且不能含有前导 0），整数之间用 ‘.’ 分隔。
  2. 例如：”0.1.2.201” 和 “192.168.1.1” 是 有效 IP 地址，但是 “0.011.255.245”、”192.168.1.312” 和 “192.168@1.1“ 是 无效 IP 地址。
    给定一个只包含数字的字符串 s ，用以表示一个 IP 地址，返回所有可能的有效 IP 地址，这些地址可以通过在 s 中插入 ‘.’ 来形成。你不能重新排序或删除 s 中的任何数字。你可以按 任何 顺序返回答案。

示例 1：
输入：s = “25525511135”
输出：[“255.255.11.135”,”255.255.111.35”]

示例 2：
输入：s = “0000”
输出：[“0.0.0.0”]

示例 3：
输入：s = “1111”
输出：[“1.1.1.1”]

示例 4：
输入：s = “010010”
输出：[“0.10.0.10”,”0.100.1.0”]

示例 5：
输入：s = “101023”
输出：[“1.0.10.23”,”1.0.102.3”,”10.1.0.23”,”10.10.2.3”,”101.0.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
//回溯算法
var restoreIpAddresses = function(s) {
    const SEG_COUNT = 4;
    const segments = new Array(SEG_COUNT);
    const ans = [];

    const dfs = (s, segId, segStart) => {
        // 如果找到了 4 段 IP 地址并且遍历完了字符串，那么就是一种答案
        if (segId === SEG_COUNT) {
            if (segStart === s.length) {
                ans.push(segments.join('.'));
            }
            return;
        }

        // 如果还没有找到 4 段 IP 地址就已经遍历完了字符串，那么提前回溯
        if (segStart === s.length) {
            return;
        }

        // 由于不能有前导零，如果当前数字为 0，那么这一段 IP 地址只能为 0
        if (s.charAt(segStart) === '0') {
            segments[segId] = 0;
            dfs(s, segId + 1, segStart + 1);
        }

        // 一般情况，枚举每一种可能性并递归
        let addr = 0;
        for (let segEnd = segStart; segEnd < s.length; ++segEnd) {
            addr = addr * 10 + (s.charAt(segEnd) - '0');
            if (addr > 0 && addr <= 0xFF) {
                segments[segId] = addr;
                dfs(s, segId + 1, segEnd + 1);
            } else {
                break;
            }
        }
    }

    dfs(s, 0, 0);
    return ans;
};

转：https://leetcode-cn.com/problems/restore-ip-addresses/solution/fu-yuan-ipdi-zhi-by-leetcode-solution/
  1. 数组中的第K个最大元素

描述：

  1. 给定整数数组 nums 和整数 k，请返回数组中第 k 个最大的元素。
  2. 请注意，你需要找的是数组排序后的第 k 个最大的元素，而不是第 k 个不同的元素。

示例 1:
输入: [3,2,1,5,6,4] 和 k = 2
输出: 5

示例 2:
输入: [3,2,3,1,2,4,5,5,6] 和 k = 4
输出: 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
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
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
228
229
230
231
232
233
234
235
236
237
238
239
240
241
242
243
244
245
246
247
//暴力解法 时间复杂度O(nlogn),空间复杂度O(1) ,快排
var findKthLargest = function(nums, k) {
    return nums.sort((a,b)=>{return b-a})[k-1];
};
//快速排序：时间复杂度O(nlogn)，递归复杂度是O(logn),分区复杂度O(n)
//分区：从数组中选一个基准值，比基准值小的放在它的前面，比基准值大的放在它的后面
//递归：递归对基准值前后的子数组进行第一步的操作
function quickSort(arr, left, right) {
    var len = arr.length,
        partitionIndex,
        left = typeof left != 'number' ? 0 : left,
        right = typeof right != 'number' ? len - 1 : right;

    if (left < right) {
        partitionIndex = partition(arr, left, right);
        quickSort(arr, left, partitionIndex-1);
        quickSort(arr, partitionIndex+1, right);
    }
    return arr;
}

function partition(arr, left ,right) {     //分区操作
  	//设定基准值位置（pivot）当然也可以选择最右边的元素为基准 也可以随机选择然后和最左或最右元素交换
    var pivot = left,                      
        index = pivot + 1;
    for (var i = index; i <= right; i++) {
        if (arr[i] < arr[pivot]) {
            swap(arr, i, index);
            index++;
        }        
    }
    swap(arr, pivot, index - 1);
    return index-1;
}

function swap(arr, i, j) {
    var temp = arr[i];
    arr[i] = arr[j];
    arr[j] = temp;
}

//方法1.维护大小为k的小顶堆，当堆的元素个数小于等于k时，遍历数组，让数组的元素不断加入堆，当堆的大小大于k时，让堆顶元素出列，遍历完数组之后，小顶堆堆顶的元素就是第k大元素。
//复杂度：时间复杂度O(nlogk)，循环n次，每次堆的操作是O(logk)。空间复杂度O(k)

![](66-2.png)

class Heap {
    constructor(comparator = (a, b) => a - b, data = []) {
        this.data = data;
        this.comparator = comparator;//比较器
        this.heapify();//堆化
    }

    heapify() {
        if (this.size() < 2) return;
        for (let i = Math.floor(this.size() / 2) - 1; i >= 0; i--) {
            this.bubbleDown(i);//bubbleDown操作
        }
    }

    peek() {
        if (this.size() === 0) return null;
        return this.data[0];//查看堆顶
    }

    offer(value) {
        this.data.push(value);//加入数组
        this.bubbleUp(this.size() - 1);//调整加入的元素在小顶堆中的位置
    }

    poll() {
        if (this.size() === 0) {
            return null;
        }
        const result = this.data[0];
        const last = this.data.pop();
        if (this.size() !== 0) {
            this.data[0] = last;//交换第一个元素和最后一个元素
            this.bubbleDown(0);//bubbleDown操作
        }
        return result;
    }

    bubbleUp(index) {
        while (index > 0) {
            const parentIndex = (index - 1) >> 1;//父节点的位置
            //如果当前元素比父节点的元素小，就交换当前节点和父节点的位置
            if (this.comparator(this.data[index], this.data[parentIndex]) < 0) {
                this.swap(index, parentIndex);//交换自己和父节点的位置
                index = parentIndex;//不断向上取父节点进行比较
            } else {
                break;//如果当前元素比父节点的元素大，不需要处理
            }
        }
    }

    bubbleDown(index) {
        const lastIndex = this.size() - 1;//最后一个节点的位置
        while (true) {
            const leftIndex = index * 2 + 1;//左节点的位置
            const rightIndex = index * 2 + 2;//右节点的位置
            let findIndex = index;//bubbleDown节点的位置
            //找出左右节点中value小的节点
            if (
                leftIndex <= lastIndex &&
                this.comparator(this.data[leftIndex], this.data[findIndex]) < 0
            ) {
                findIndex = leftIndex;
            }
            if (
                rightIndex <= lastIndex &&
                this.comparator(this.data[rightIndex], this.data[findIndex]) < 0
            ) {
                findIndex = rightIndex;
            }
            if (index !== findIndex) {
                this.swap(index, findIndex);//交换当前元素和左右节点中value小的
                index = findIndex;
            } else {
                break;
            }
        }
    }

    swap(index1, index2) {//交换堆中两个元素的位置
        [this.data[index1], this.data[index2]] = [this.data[index2], this.data[index1]];
    }

    size() {
        return this.data.length;
    }
}



var findKthLargest = function (nums, k) {
    const h = new Heap((a, b) => a - b);

    for (const num of nums) {
        h.offer(num);//加入堆
        if (h.size() > k) {//堆的size超过k时，出堆
            h.poll();
        }
    }

    return h.peek();
};

//思路：利用原地堆排序的思想，将前k-1大的元素加入队尾，最后队顶的元素就是第k大的元素
//复杂度：时间复杂度O(nlogn)，堆的创建复杂度是O(n)，移动前k-1大的元素然后堆化复杂度是O(klogn)，k<=n，最差的情况下是O(nlogn)，空间复杂度O(logn)，递归的栈空间

![](66-3.gif)

var findKthLargest = function (nums, k) {
    let heapSize = nums.length;
    buildMaxHeap(nums, heapSize); //构建大顶堆 大小为heapSize
    //大顶堆 前k-1个堆顶元素不断和数组的末尾元素交换 然后重新heapify堆顶元素
    //这个操作就是之前小顶堆出堆顶的操作，只不过现在是原地排序
    for (let i = nums.length - 1; i >= nums.length - k + 1; i--) {
        swap(nums, 0, i);//交换堆顶和数组末尾元素
        --heapSize; //堆大小减1
        maxHeapify(nums, 0, heapSize);//重新heapify
    }
    return nums[0];//返回堆顶元素，就是第k大的元素

    function buildMaxHeap(nums, heapSize) {
        for (let i = Math.floor(heapSize / 2) - 1; i >= 0; i--) {//从第一个非叶子节点开始构建
            maxHeapify(nums, i, heapSize);
        }
    }
    // 从左向右，自上而下的调整节点
    function maxHeapify(nums, i, heapSize) {
        let l = i * 2 + 1;//左节点
        let r = i * 2 + 2;//右节点
        let largest = i;
        if (l < heapSize && nums[l] > nums[largest]) {
            largest = l;
        }
        if (r < heapSize && nums[r] > nums[largest]) {
            largest = r;
        }
        if (largest !== i) {
            swap(nums, i, largest); //找到左右节点中大的元素交换
            //递归交换后面的节点
            maxHeapify(nums, largest, heapSize);
        }
    }

    function swap(a, i, j) {//交换函数
        let temp = a[i];
        a[i] = a[j];
        a[j] = temp;
    }
};

//1. 思路：借鉴快排的思路，不断随机选择基准元素，看进行partition之后，该元素是不是在n-k的位置。
//2. 复杂度：时间复杂度O(nlogn),空间复杂度O(logn)，递归的深度

![](66-4.png)

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之后，基准元素左边的元素都小于它 右边的元素都大于它
        //如果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;
}

转：https://leetcode-cn.com/problems/kth-largest-element-in-an-array/solution/xie-gei-qian-duan-tong-xue-de-ti-jie-yi-kt5p2/
转：https://leetcode-cn.com/problems/kth-largest-element-in-an-array/solution/215-shu-zu-zhong-de-di-kge-zui-da-yuan-s-2zkk/
转：https://xiaochen1024.com/courseware/60b4f11ab1aa91002eb53b18/6196d34dc1553b002e57bf29
  1. 翻转二叉树 2
  2. 二叉树的中序遍历 2
  3. 零钱兑换 1
  4. 求根到叶子节点数字之和 1
  5. 合并两个有序数组 1
  6. 买卖股票 1
  7. 二叉树中的最大路径和 1
  8. 二叉树的最大深度
  • 本文作者： David Xue
  • 本文链接： https://xdw-h.github.io/66/
  • 版权声明： 本博客所有文章除特别声明外，均采用 BY-NC-SA 许可协议。转载请注明出处！