【JavaScript】LeetCode：86-90

文章目录

86 只出现一次的数字
87 颜色分类
88 下一个排列
89 寻找重复数
90 前K个高频元素

86 只出现一次的数字

在这里插入图片描述

异或
x ^ x = 0，x ^ 0 = x，相同为0，相异为1，且满足交换律。
例如：[4, 1, 2, 1, 2] => 1 ^ 1 ^ 2 ^ 2 ^ 4 = 0 ^ 0 ^ 4 = 0 ^ 4 = 4，最后的结果即为重复一次的数字。

/*** @param {number[]} nums* @return {number}*/
var singleNumber = function(nums) {let res = 0;for(let item of nums){res ^= item;}return res;  
};

87 颜色分类

在这里插入图片描述

双指针
i 指向0的下一个位置，j 指向1的下一个位置。
k 遍历数组，① 若该位置为0，则将当前数与 i 指向的数进行交换，i 和 j 指针都向后移动一位；② 若该位置为1，则将当前数与 j 指向的数进行交换，j 指针向后移动一位。
注意：情况①时，若 i < j，则说明 i 指向的数为1，做交换时会把1换到后面去（即k指向的数），应该将当前数与 j 指向的数进行交换，把1换回去。

/*** @param {number[]} nums* @return {void} Do not return anything, modify nums in-place instead.*/
var sortColors = function(nums) {let i = 0, j = 0;for(let k = 0; k <= nums.length; k++){if(nums[k] == 0){[nums[i], nums[k]] = [nums[k], nums[i]];if(i < j){[nums[j], nums[k]] = [nums[k], nums[j]];}i++;j++;}else if(nums[k] == 1){[nums[j], nums[k]] = [nums[k], nums[j]];j++;}}
};

88 下一个排列

在这里插入图片描述

例子：数组nums = [1, 2, 3, 5, 4]。
从后往前遍历数组，查找第一个升序的数对，记为 i 和 j 。
i = 3，j = 5。
从后往前遍历数组，查找第一个 > nums[i]的数，记为tmp。
tmp = 4。
交换nums[i]和nums[tmp]。
nums = [1, 2, 4, 5, 3]。
将 i 后面的元素按升序进行排序，得到结果。
nums = [1, 2, 4, 3, 5]。

/*** @param {number[]} nums* @return {void} Do not return anything, modify nums in-place instead.*/
var nextPermutation = function(nums) {let len = nums.length;let i = len - 2, j = len - 1;while(i >= 0){if(nums[i] < nums[j]){break;}i--, j--;}let tmp = -1;for(let k = len - 1; k > i; k--){if(nums[k] > nums[i]){tmp = k;break;}}[nums[tmp], nums[i]] = [nums[i], nums[tmp]];let right = nums.slice(j, len);right.sort((a, b) => a - b);let n = 0, m = i + 1;while(m < len){nums[m] = right[n];m++, n++;}
};

89 寻找重复数

在这里插入图片描述

快慢指针找环形链表的入口。
创建一个链表，节点为[0, 1, …, n]，nums索引值 i 的next为nums[i]。
若存在重复元素s，链表中一定会同时有两条边指向节点x，节点x即为环的入口。
例如：nums = [1, 3, 4, 2, 2]，链表为：0 => 1，1 => 3，2 => 4，3 => 2，4 => 2，这里可以发现，2为环形链表的入口，即为重复元素。

var next = function(nums, index){return nums[index];
}/*** @param {number[]} nums* @return {number}*/
var findDuplicate = function(nums) {let slow = 0, fast = 0;while((slow == 0 && fast == 0) || slow != fast){fast = next(nums, next(nums, fast));slow = next(nums, slow);}slow = 0;while(slow != fast){slow = next(nums, slow);fast = next(nums, fast);}return slow;
};

90 前K个高频元素

在这里插入图片描述

最小堆

节点索引值
当前节点 i
父节点 (i - 1) / 2向下取整
左孩子 2 * i + 1
右孩子 2 * i + 2
最后一个非叶子节点 (length - 2) / 2向下取整
自上往下：与左右孩子进行比较，若均 > 左右孩子，则与左右孩子中较小值交换，否则与 < 自身的孩子交换。
自下往上：与父节点进行比较，若 > 父节点，则与父节点交换。
push()：插入末尾，然后自下而上判断一次。
pop()：取出堆顶元素，将堆中最后一个元素与堆顶元素交换，然后自上往下判断一次。

节点	索引值
当前节点	i
父节点	(i - 1) / 2向下取整
左孩子	2 * i + 1
右孩子	2 * i + 2
最后一个非叶子节点	(length - 2) / 2向下取整

/*** @param {number[]} nums* @param {number} k* @return {number[]}*/
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);}}peek(){if(this.size() === 0) return null;return this.data[0];}insert(value){this.data.push(value);this.bubbleUp(this.size() - 1);}pop(){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);}return result;}bubbleUp(index){while(index > 0){const parentIndex = Math.floor((index - 1) / 2);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;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);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 topKFrequent = function(nums, k) {const map = new Map();for(const num of nums) {map.set(num, (map.get(num) || 0) + 1);}const priorityQueue = new Heap((a, b) => a[1] - b[1]);for(const items of map.entries()){priorityQueue.insert(items);if(priorityQueue.size() > k){priorityQueue.pop();}}const res = [];for(let i = priorityQueue.size() - 1; i >= 0; i--){res[i] = priorityQueue.pop()[0];}return res;
};