977.有序数组的平方
题目链接:https://leetcode.cn/problems/squares-of-a-sorted-array/
最初想法是用二分找到恰好大于0的数; 然后数组切片,负的一方反转, 然后按照合并两个有序数组类似方式合并;
看了提示用双指针, 发现切片和反转是没必要的
另外值得一提的是我对二分查找有了更深的理解;
尽管昨天就做了练习,但今天写这个二分仍然非常吃力,
写边界条件和判断部分一定要理清逻辑才行,最好举几个例子
最后结果如下
/**
* @param {number[]} nums
* @return {number[]}
*/
//思路: 二分查找到恰好小于0的数, 分割, 反转, 平方, 融合
//参考思路:直接用指针两向遍历就好了
var sortedSquares = function(nums) {
let zeroBound = lowerBound(nums,0,nums.length-1,0)
console.log(zeroBound)
let l = zeroBound-1, r = zeroBound
if(zeroBound == -1){
r = Infinity
l = nums.length-1
}
let result = []
while(l>=0||r<nums.length){
let leftSqrt = l>=0?nums[l]*nums[l]:Infinity
let rightSqrt = r<nums.length?nums[r]*nums[r]:Infinity
if(leftSqrt<rightSqrt){
result.push(leftSqrt)
l--
}else{
result.push(rightSqrt)
r++
}
}
return result
};
//寻找x, target<arr[x]且target>=arr[x-1]
//更进一步理解了二分查找;
//记住一个重要特性, 只要mid是偏向left的,所以left是必须+1的,否则无限循环
function lowerBound(arr, left,right,target){
let mid
while(left<right){
mid = Math.floor((left+right)/2)
if(target>=arr[mid]){
left = mid+1
}else if(target<arr[mid]){
right = mid
}
}
//return -1
return arr[left]>=target?left:-1
}
看了文章后发现, 完全可以反着来,先放大的再放小的, 这个二分有点小丑哈哈
209.长度最小的子数组
题目链接：https://leetcode.cn/problems/minimum-size-subarray-sum/
本题我做过,但仍然不是很熟练,滑动窗口看来还得多做
有好几种实现方式,有移动end的, 有移动start的; 还有一些判断;
例如官方题解中移动end就十分巧妙, 比我的省了不少代码;
移动start看似更直观,但需要多写不少if
/**
* @param {number} target
* @param {number[]} nums
* @return {number}
*/
//思路: 滑动窗口;定义sum为区间[start,end]的和,start前进会让sum减去开头的数, end前进会让sum减去结尾的数
//实现:定义start和end, 要么start逐步往前,要么end逐步往前;然后另一个适配
var minSubArrayLen = function(target, nums) {
let start = 0, end = -1;
let sum = 0;
let minLen = Infinity;
for(;start<nums.length;start++){
while(sum<target){
end++
if(end>=nums.length){
break
}else{
sum+=nums[end]
}
}
if(sum>=target){
minLen = end-start+1<minLen?end-start+1:minLen
}
sum -= nums[start]
}
return minLen === Infinity?0:minLen
};
看了文章后, 发现文章题解也是枚举滑动窗口终点
59. 螺旋矩阵 II
这个只想到比较笨的方法; 一圈一圈用类似贪吃蛇的方式生成
/**
* @param {number} n
* @return {number[][]}
*/
//定义一个函数, 能以x,y为起点,以num为开始数字,生成宽度为len的一圈数
var generateMatrix = function(n) {
let matrix = new Array(n).fill(0).map(e=>new Array(n).fill(0))
let hLen = Math.round(n/2)
let x=0, y=0;
let start = 1;
for(let i = 0; i< hLen;i++){
start = generateCycle(matrix,x,y,start,n-i*2)
x++
y++
}
return matrix
};
function generateCycle(mat,x,y,num,width){
mat[x][y] = num
if(width==1){
return
}
let tLen = width*4-4
let rLen = width-1
let tmp = num
let i =x, j =y
for(tmp = num;tmp<num+tLen;tmp++ ){
mat[i][j] = tmp
if(tmp<num+rLen){
j++
}else if (tmp <num+2*rLen){
i++
}else if(tmp <num+3*rLen){
j--
}else{
i--
}
}
return tmp
}
看了文章后发现, 坚持左闭右开的区间的理解,是很有用的
数组专题总结
作为一种线性结构, 数组是最简单的一种数据结构,也是很多数据结构的基础;
主要学习了
二分法
双指针法
滑动窗口法
看过文章后,还有一个模拟法
还有重要的循环不变量原则
出于时间不多总结