解题思路1:利用Set对象的特性,只能存储任意类型的唯一值,来筛选出重复的数据,再与保存的set对象里面的值进行比较
1 var singleNumber = function(nums) { 2 let mySet = new Set(); 3 let repeatList = []; 4 for(let i = 0; i < nums.length; i++) { 5 if (mySet.has(nums[i])) { 6 repeatList.push(nums[i]); 7 } else { 8 mySet.add(nums[i]) 9 } 10 11 } 12 //console.log("mySet",mySet); 13 //console.log("repeatList",repeatList); 14 const singleNum = Array.from(mySet).filter(item=>!repeatList.includes(item)); 15 console.log("singleNum",singleNum); 16 return singleNum; 17 }; 18 singleNumber([1,2,1,2,4,6,7,7,6]);
解题思路2:利用两层循环,找到重复的数据,再和原数组比较
1 /** 2 * @param {number[]} nums 3 * @return {number} 4 */ 5 var singleNumber = function(nums) { 6 let repeatList = []; 7 for (let i = 0; i < nums.length; i++) { 8 const outItem = nums[i]; 9 for(let j = i + 1; j < nums.length; j++){ 10 const innerItem = nums[j]; 11 if (outItem === innerItem) { 12 repeatList.push(innerItem);
} 15 } 16 } 17 console.log("repeatList", repeatList); 18 const singleNum = nums.filter(item=>!repeatList.includes(item)) 19 console.log("singleNum", singleNum); 20 return singleNum[0]; 21 }; 22 singleNumber([1,2,2,1,3])
2.给定一个数组,将数组中的元素向右移动 k
个位置,其中 k
是非负数。
解题思路1:根据位置k,截取数组,再重新组合
1
/**
* @param {number[]} nums
* @param {number} k
* @return {void} Do not return anything, modify nums in-place instead.
*/
var rotate = function(nums, k) {
2 const len = nums.length
3 const index = len? len - k : len
4 const arr = nums.splice(index)
5 const dataset = arr.concat(nums)
6 dataset.forEach((item,index)=>{
7 nums[index] = item
8 })
9 };
解题思路2:无限轮播思想,复制一份原数组,再与原数组组合形成新数组
1
/**
* @param {number[]} nums
* @param {number} k
* @return {void} Do not return anything, modify nums in-place instead.
*/
var rotate = function(nums, k) { 2 const len = nums.length 3 const copyNums = [...nums,...nums] 4 const index = len ? len - k%len : len 5 const _nums = copyNums.splice(index, len) 6 for(let i = 0; i < _nums.length; i++){ 7 nums[i] = _nums[i] 8 } 9 };
3.两个数组的交集
例:输入:nums1 = [4,9,5], nums2 = [9,4,9,8,4] 输出:[4,9]
解题思路:先找出交集元素,然后统计交集元素在每个数组的出现次数,最后输出结果
// 如果有交集,获取交集元素在当前数组的出现次数 function getTimes(data=[], num){ let times = 0 data.forEach(item=>{ if (item === num) { times+=1 } }) return times } /** * @param {number[]} nums1 * @param {number[]} nums2 * @return {number[]} */ var intersect = function(nums1, nums2) { let dataMap= {}; // 储存数组交集 let data = []; // 返回交集 for(let i = 0; i < nums1.length; i++) { const outItem = nums1[i]; let crossObj = {} for(let j = 0; j < nums2.length; j++) { const innerItem = nums2[j] if (outItem === innerItem) { crossObj = { num: outItem, num1Times: getTimes(nums1, outItem), num2Times: getTimes(nums2, innerItem) } } } if (Object.keys(crossObj).length) { dataMap[crossObj.num] = crossObj } } for (let key in dataMap) { const val = dataMap[key] const len = Math.min(val.num1Times, val.num2Times) for (let m = 0; m < len; m++) { data.push(val.num) } } return data }; intersect([1,2,2,1], [2,2]) // 返回结果[2,2]
返回所需的 K 位翻转的最小次数,以便数组没有值为 0 的元素。如果不可能,返回 -1。
解题思路:遍历数组A,遇到为0的开始翻转K个长度
1 /**
2 * @param {number[]} A
3 * @param {number} K
4 * @return {number}
5 */
6 var minKBitFlips = function(A, K) {
7 const len = A.length
8 let count = 0;
9 for(let i = 0; i <len; i++) {
10 // 开始翻转K个长度
11 if (A[i] === 0 && len - i >= K) {
12 count++
13 for(let j = i; j < i + K; j++){
14 A[j] = A[j]^1 // 异或运算符 reverseNum(A[j])
15 }
16
17 }
18 }
19 console.log(A)
20 if (A.includes(0)) {
21 count = -1
22 }
23 return count
24 };
25
26 function reverseNum(num){
27 return typeof num === 'number'
28 ? num === 1 ? 0 : 1
29 : num
30 }
解题思路:各自与比较左上方数值比较,如果不相等则不是托普利茨矩阵
1 /** 2 * @param {number[][]} matrix 3 * @return {boolean} 4 */ 5 var isToeplitzMatrix = function(matrix) { 6 const len = matrix.length 7 const nLen = matrix[0].length 8 // 各自跟左上角的数值比较 9 for(let i = 1; i<len; i++) { 10 for(j = 1; j<nLen; j++) { 11 if(matrix[i][j]!== matrix[i-1][j-1]){ 12 return false 13 } 14 } 15 } 16 return true 17 }; 18 19 isToeplitzMatrix([[1,2,3,4],[5,1,2,3],[9,5,1,2]]) // true
6.爱生气的书店老板
输入:customers = [1,0,1,2,1,1,7,5], grumpy = [0,1,0,1,0,1,0,1], X = 3
输出:16
解释:
书店老板在最后 3 分钟保持冷静。
感到满意的最大客户数量 = 1 + 1 + 1 + 1 + 7 + 5 = 16.
解题思路:滑动窗口解法。先求不生气时间内的顾客数,然后滑动X个,找出各挽留了多少顾客数,找出挽留顾客数的最大值,再相加即可得最大满意顾客数
1 /** 2 * @param {number[]} customers 3 * @param {number[]} grumpy 4 * @param {number} X 5 * @return {number} 6 */ 7 var maxSatisfied = function(customers, grumpy, X) { 8 // 思路:先求不生气时间内的顾客数,然后滑动X个,找出各挽留了多少顾客数,找出挽留顾客数的最大值,再相加即可得最大满意顾客数 9 // 1.不生气时顾客数 10 let cusNum = 0 11 for(let i = 0; i < grumpy.length; i++){ 12 if (grumpy[i] === 0) { 13 cusNum+= customers[i] 14 } 15 } 16 // console.log("cusNum", cusNum) 17 18 // 2.挽留的顾客数集合 19 const reserveList = [] 20 for(let j = 0; j < grumpy.length; j++){ 21 if (j + X <= grumpy.length) { 22 let num = 0 23 for(let k = 0; k < X; k++) { 24 if (grumpy[j+k] === 1) { 25 num += customers[j+k] 26 } 27 } 28 reserveList.push(num) 29 } 30 31 } 32 // console.log("reserveList", reserveList) 33 // 找出挽留顾客数的最大值 34 const reserve = Math.max(...reserveList) 35 36 return cusNum + reserve 37 };
nums
,求出数组从索引 i
到 j
(i ≤ j
)范围内元素的总和,包含 i
、j
两点。解题思路:先找出前缀和preSum,对于数组任意索引之间的总和sumRange,有sumRange = sums[j+1] - sums[i]
1 /** 2 * @param {number[]} nums 3 */ 4 var NumArray = function(nums) { 5 // 前缀和 6 const len = nums.length 7 this.preSum = new Array(len + 1).fill(0) 8 for (let i = 0; i < len; i++) { 9 this.preSum[i+1] = this.preSum[i] + nums[i] 10 } 11 console.log("preSum", this.preSum) 12 }; 13 14 /** 15 * @param {number} i 16 * @param {number} j 17 * @return {number} 18 */ 19 NumArray.prototype.sumRange = function(i, j) { 20 return this.preSum[j+1] - this.preSum[i] 21 }; 22 23 // 输入:["NumArray","sumRange","sumRange","sumRange"] [[[-2,0,3,-5,2,-1]],[0,2],[2,5],[0,5]] 24 // 输出:[null,1,-1,-3] 25 /** 26 * Your NumArray object will be instantiated and called as such: 27 * var obj = new NumArray(nums) 28 * var param_1 = obj.sumRange(i,j) 29 */
8.接雨水
解题思路1:先找出每个位置i能接多少水,每个位置能接多少水取决于左右两侧最大值中的小的一个。 时间复杂度 O(n^2) 空间复杂度(1)
1 /** 2 * @param {number[]} height 3 * @return {number} 4 */ 5 var trap = function(height) { 6 if (height.length === 0) { 7 return 0 8 } 9 // 思路:先找出每个位置i能接多少水,每个位置能接多少水取决于左右两侧最大值中的小的一个。 10 const len = height.length 11 let res = 0 12 for (let i = 1; i < len - 1; i++) { 13 let leftMax = 0; 14 let rightMax = 0; 15 // 找出左边最高的柱子 16 for (let j = i; j >=0; j--) { 17 leftMax = Math.max(leftMax, height[j]) 18 } 19 // 找出右边最高的柱子 20 for(let j = i; j < len; j++){ 21 rightMax = Math.max(rightMax, height[j]) 22 } 23 24 res += Math.min(leftMax, rightMax) - height[i] 25 } 26 return res 27 };
解题思路2:先找出左右最高柱子,再算能接多少水,降低复杂度,时间复杂度O(n),空间复杂度O(n)
1 /** 2 * @param {number[]} height 3 * @return {number} 4 */ 5 var trap = function(height) { 6 if (height.length === 0) { 7 return 0 8 } 9 // 思路2:先找出左右最高柱子,再算能接多少水。 10 // 优化性能 11 const len = height.length 12 let res = 0 13 14 const leftMax = new Array(len) 15 const rightMax = new Array(len) 16 17 leftMax[0] = height[0] 18 rightMax[len-1] = height[len-1] 19 20 //计算leftMax从左到右 21 for (let i = 1; i < len; i++) { 22 leftMax[i] = Math.max(height[i], leftMax[i-1]) 23 } 24 25 // 计算rightMax从右到左 26 for(let j = len - 2; j >= 0; j--) { 27 rightMax[j] = Math.max(height[j], rightMax[j + 1]) 28 } 29 30 for (let i = 1; i < len - 1; i++) { 31 res += Math.min(leftMax[i], rightMax[i]) - height[i] 32 } 33 return res 34 };
解题思路3:双指针法
1 /** 2 * @param {number[]} height 3 * @return {number} 4 */ 5 var trap = function(height) { 6 if (height.length === 0) { 7 return 0; 8 } 9 // 双指针法 10 const len = height.length; 11 let res = 0; 12 13 let left = 0; 14 let right = len - 1; 15 16 let leftMax = height[0]; 17 let rightMax = height[len - 1]; 18 19 while(left <= right){ 20 leftMax = Math.max(leftMax, height[left]); 21 rightMax = Math.max(rightMax, height[right]); 22 23 // 木桶原理,能装多少水取决于矮的一边 24 if (leftMax < rightMax) { 25 // 只看左边的 26 res += leftMax - height[left]; 27 left++; 28 } else { 29 // 只看右边 30 res += rightMax - height[right]; 31 right--; 32 } 33 } 34 return res; 35 };
持续更新中...
联系客服