跟练代码随想录之数组篇
写在前面，这个系列是跟着B站的代码随想录跟练算法的部分。算法还是比较薄弱，慢慢打基础吧，这篇文章很久以前就写好了，只是发布的时间比较晚了，最近也是打算迁移一下自己的文章。
友链到卡哥
https://www.programmercarl.com/
1.二分查找（leetcode704）
看懂了，有两种写法，如果是左闭右闭的写法的话，那么left可以等于right，right=mid-1，left=mid+1；
如果是左闭右开的写法的话，那么left
总结：最好是用左闭右闭的写法。
1
2
3
4
5
6
7
8
9
10
11
12
13
| class Solution {
public int search(int[] nums, int target) {
int left = 0;
int right = nums.length-1;
while(left<=right){
int middle = (left+right)/2;
if (nums[middle]>target) right=middle-1;
else if (nums[middle]<target) left=middle+1;
else return middle;
}
return -1;
}
}
|
2.移除数组元素（leetcode27）
这题就是移除数组中所有值为val的元素，用一个快慢数组来解决，代码一看就能明白，能想到吗？跟数组有关的，大概率是要用双指针来优化，将n2的复杂度优化为n。
1
2
3
4
5
6
7
8
9
10
11
| class Solution {
public int removeElement(int[] nums, int val) {
int fast=0;
int low=0;
for(fast=0;fast<nums.length;fast++){
if (nums[fast]!=val) nums[low++] = nums[fast];
}
return low;
}
}
|
3.有序数组的平方（leetcode977）
如果用暴力sort来排序的话，那么时间复杂度是n+nlogn，用双指针可以有效地变为n。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
| class Solution {
public int[] sortedSquares(int[] nums) {
int i=0,j=nums.length-1;
int[] result = new int[nums.length];
int k = nums.length-1;
while(i<=j){
if (Math.pow(nums[i],2)>Math.pow(nums[j],2)) result[k--] = (int)Math.pow(nums[i++],2);
else result[k--] = (int)Math.pow(nums[j--],2);
}
return result;
}
}
|
4.长度最小的子数组（leetcode209）
这题是用滑动窗口来解决，记住，j 是 窗口的终止节点，并且，此滑动窗口的时间复杂度是On，严格来说是O2n。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
| class Solution {
public int minSubArrayLen(int target, int[] nums) {
int i=0,j=0,sum=0,result=Integer.MAX_VALUE;
for(;j<nums.length;j++){
sum+=nums[j];
while(sum>=target){
if (j-i+1<result) result = j-i+1;
sum-=nums[i];
i++;
}
}
return result==Integer.MAX_VALUE?0:result;
}
}
|
5.螺旋矩阵（leetcode59）
这题真的还挺有意思的，为什么呢？
第一，确定不变量，我们要的是左闭右开，这样子做完4次处理，每个数都能被处理到，如果是左闭右闭，那么会有四个数被重复赋值了；
第二，确定起始位置和偏移量，startx,starty,offset，startx和starty决定了每一轮从哪儿开始进行遍历，offset决定了每一轮遍历的终点，其实startx，starty就是每一轮最左上角那个点。
第三，每次遍历时，要严格遵守上面的规则，左闭右开和起始位置、偏移位置的规则。
看代码：
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
| class Solution {
public int[][] generateMatrix(int n) {
int[][] matrix =new int[n][n];
int startx=0,starty=0;
int offset=1;
int count=1;
int cnt=n/2;
int i=0,j=0;
while(cnt>0){
for (j=starty;j<n-offset;j++) matrix[startx][j]=count++;
for (i=startx;i<n-offset;i++) matrix[i][j] = count++;
for (;j>starty;j--) matrix[i][j] = count++;
for (;i>startx;i--) matrix[i][j] = count++;
startx++;
starty++;
offset++;
cnt--;
}
if (n%2==1) matrix[n/2][n/2]=count;
return matrix;
}
}
|
