代码随想录算法——数组
目录
1、二分查找法
2、移除元素
3、有序数组的平方
4、长度最小的子数组
5、螺旋矩阵II
1、二分查找法
给定一个 n 个元素有序的（升序）整型数组 nums 和一个目标值 target ，写一个函数搜索 nums 中的 target，如果目标值存在返回下标，否则返回 -1。
import java.util.*;public class Solution {/*** 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可** * @param nums int整型一维数组 * @param target int整型 * @return int整型*/public int search (int[] nums, int target) {// write code hereint left=0;int right=nums.length-1;while(left<=right){int mid=(left+right)/2;if(nums[mid]==target){return mid;}else if(nums[mid]>target){right=mid-1;}elseleft=mid+1;}return -1;}
}2、移除元素
给你一个数组 nums 和一个值 val，你需要 原地 移除所有数值等于 val 的元素，并返回移除后数组的新长度。
不要使用额外的数组空间，你必须仅使用 O(1) 额外空间并原地修改输入数组。
元素的顺序可以改变。你不需要考虑数组中超出新长度后面的元素。
示例 1: 给定 nums = [3,2,2,3], val = 3, 函数应该返回新的长度 2, 并且 nums 中的前两个元素均为 2。 你不需要考虑数组中超出新长度后面的元素。
示例 2: 给定 nums = [0,1,2,2,3,0,4,2], val = 2, 函数应该返回新的长度 5, 并且 nums 中的前五个元素为 0, 1, 3, 0, 4。
你不需要考虑数组中超出新长度后面的元素
class Solution {public int removeElement(int[] nums, int val) {int last=nums.length-1;// //自己想的方法// /*// 改变元素相对位置// 思想就是从头开始遍历，如果碰到val值就与数组后面的待检测值交换，// 交换后的值还可能是val，所以while继续交换，last用于保存待检测数组的最后边界// */// for(int i=0;i<=last;i++){ // while(nums[i]==val&&last>=i){ //[2,3,2,3] [3,3]// nums[i]=nums[last];// last=last-1;// }// }// return last+1;/**这个别人的方法，也是改变元素位置*/// int leftIndex = 0;// int rightIndex = nums.length - 1;// while (leftIndex <= rightIndex) {// // 找左边等于val的元素// while (leftIndex <= rightIndex && nums[leftIndex] != val){// ++leftIndex;// }// // 找右边不等于val的元素// while (leftIndex <= rightIndex && nums[rightIndex] == val) {// -- rightIndex;// }// // 将右边不等于val的元素覆盖左边等于val的元素// if (leftIndex < rightIndex) {// nums[leftIndex++] = nums[rightIndex--];// }// }// return leftIndex; // leftIndex一定指向了最终数组末尾的下一个元素/*快慢指针方法我的理解就是慢指针相当于一个虚拟数组，当不等于val值，就存储fast数组的元素*/int slowIndex = 0;for (int fastIndex = 0; fastIndex < nums.length; fastIndex++) {if (val != nums[fastIndex]) {nums[slowIndex++] = nums[fastIndex];}}return slowIndex;}
}3、有序数组的平方
给你一个按 非递减顺序 排序的整数数组 nums，返回 每个数字的平方 组成的新数组，要求也按 非递减顺序 排序。
示例 1：
- 输入：nums = [-4,-1,0,3,10]
- 输出：[0,1,9,16,100]
- 解释：平方后，数组变为 [16,1,0,9,100]，排序后，数组变为 [0,1,9,16,100]
示例 2：
- 输入：nums = [-7,-3,2,3,11]
- 输出：[4,9,9,49,121]
class Solution {public int[] sortedSquares(int[] nums) {/**数组其实是有序的， 只不过负数平方之后可能成为最大数了。那么数组平方的最大值就在数组的两端，不是最左边就是最右边，不可能是中间。双指针法 i指向起始位置，j指向终止位置。前后依次遍历，定义一个新数组result，选择最大值从后往前填入新数组， */int i=0;int j=nums.length-1;int k=nums.length-1;int[] res=new int[nums.length];while(i<=j){if(nums[i]*nums[i]<=nums[j]*nums[j]){res[k--]=nums[j]*nums[j];j--;}else{res[k--]=nums[i]*nums[i];i++;}}return res;}
}4、长度最小的子数组
给定一个含有 n 个正整数的数组和一个正整数 s ，找出该数组中满足其和 ≥ s 的长度最小的 连续 子数组，并返回其长度。如果不存在符合条件的子数组，返回 0。
示例：
- 输入：s = 7, nums = [2,3,1,2,4,3]
- 输出：2
- 解释：子数组 [4,3] 是该条件下的长度最小的子数组。
提示：
- 1 <= target <= 10^9
- 1 <= nums.length <= 10^5
- 1 <= nums[i] <= 10^5
import java.util.*;
class Solution {public int minSubArrayLen(int target, int[] nums) {/**定义i,j快慢指针，找到最小连续数组，那么有起始位置和结束位置只有结束指针遍历了整个数组，所以可确定，i,j形成滑动窗口，窗口里面是满足和大于等于target值,固定结束指针，把起始指针往前移动，不满足和的条件再移动结束位置*/int sum=0;int minlen=Integer.MAX_VALUE;for(int i=0,j=0;j<nums.length;j++){sum+=nums[j];while(sum>=target){minlen=minlen>(j-i+1)?(j-i+1):minlen;sum-=nums[i];i++;}}return minlen==Integer.MAX_VALUE?0:minlen;}
}5、螺旋矩阵II
给定一个正整数 n，生成一个包含 1 到 n^2 所有元素，且元素按顺时针顺序螺旋排列的正方形矩阵。示例:
输入: 3 输出: [ [ 1, 2, 3 ], [ 8, 9, 4 ], [ 7, 6, 5 ]
class Solution {public int[][] generateMatrix(int n) {/**总共4条边，要遵循不变量原则,左闭右开这里n为奇数时，中间单独处理，最大的数*/int res[][]=new int[n][n];int a=1;int i=0,j=0;int x=0;//x是循环的次数，也是用于边界限定的int aa=n*n+1;if(n%2!=0){aa-=1;}while(a<aa){//从左到右，for(;j<n-1-x;j++){//每一圈循环边界减少1res[i][j]=a;System.out.println(i+" "+j+" ="+a);a++;}//从上到下for(;i<n-1-x;i++){res[i][j]=a;System.out.println(i+" "+j+" ="+a);a++;}//从右到左 for(;j>0+x;j--){res[i][j]=a;System.out.println(i+" "+j+" ="+a);a++;}//从下到上for(;i>0+x;i--){res[i][j]=a;System.out.println(i+" "+j+" ="+a);a++;}x++;//x是作为圈数，也是边界减少的数量i=x;//这里定义ij为每次循环的起点，都是 00 11 22 33因此和x相同j=x;}if(n%2!=0){res[n/2][n/2]=a;}return res;}
}