数组篇
1.二分查找
给定一个 n 个元素有序的（升序）整型数组 nums 和一个目标值 target ，写一个函数搜索 nums 中的 target，如果目标值存在返回下标，否则返回 -1。
class Solution {
public int search(int[] nums, int target) {
int left=0,right=nums.length-1;
int mid=0;
while(left<=right){
mid=(left+right)/2;
if(nums[mid]>target) right=mid-1;
else if(nums[mid]<target) left=mid+1;
else return mid;
}
return -1;
}
}
//返回位置和插入位置时，最后return left
2.移除元素
给你一个数组 nums 和一个值 val，你需要 原地 移除所有数值等于 val 的元素，并返回移除后数组的新长度。
不要使用额外的数组空间，你必须仅使用 O(1) 额外空间并 原地 修改输入数组。
元素的顺序可以改变。你不需要考虑数组中超出新长度后面的元素。
class Solution {
public int removeElement(int[] nums, int val) {
//定义两个指针，一个不断向前移动，另一个获取到第一个不是val的值后再移动
int j=0;
for(int i=0;i<nums.length;i++){
if(nums[i]!=val){
nums[j]=nums[i];
j++;
}
}
return j;
}
}
3.有序数组的平方
给你一个按 非递减顺序 排序的整数数组 nums，返回 每个数字的平方 组成的新数组，要求也按 非递减顺序 排序。
class Solution {
public int[] sortedSquares(int[] nums) {
int l=nums.length;
for(int i=0;i<l;i++){
nums[i]=nums[i]*nums[i];
}
int []result=new int[l];
int index=l-1;
int j=l-1,i=0;
while(index!=-1){
if(j==i){//遍历到最后了，结束
result[index]=nums[i];
break;
}
else if(nums[j]>nums[i]){
result[index]=nums[j];
j--;
}
else{
result[index]=nums[i];
i++;
}
index--;
}
return result;
}
}
每个数平方后快排，一次循环找到最小的然后向两边遍历
如果按照更好的办法，当然是找到绝对值最小的，向两边使用双指针法
但是那个找最小的还要遍历，所以可以从两边向中间使用双指针法
4.长度最小的子数组
给定一个含有 n 个正整数的数组和一个正整数 target 。
找出该数组中满足其和 ≥ target 的长度最小的 连续子数组 [numsl, numsl+1, ..., numsr-1, numsr] ，并返回其长度。如果不存在符合条件的子数组，返回 0 。
class Solution {
public int minSubArrayLen(int target, int[] nums) {
//滑动窗口，这类问题关键在于什么时候向左向右动
//如果大于目标值，左指针向右移动，如果小于目标值，右指针向右移动
int i=0,j=0,result=0,l=nums.length;
Boolean a=true;
int nowLength=1,nowCount=nums[0];
while(j<l){
if(nowCount>=target){//达到要求，保存长度值
if(a==true) {result=nowLength;a=false;}
else result=nowLength<result?nowLength:result;
nowCount=nowCount-nums[j];
j++;
nowLength--;
}
else{
if(i<l-1){
i++;
nowCount=nowCount+nums[i];
nowLength++;
}
else break;
}
}
return result;
}
}
5.螺旋数组II
给你一个正整数 n ，生成一个包含 1 到 n2 所有元素，且元素按顺时针顺序螺旋排列的 n x n 正方形矩阵 matrix 。
class Solution {
public int[][] generateMatrix(int n) {
int [][]result=new int[n][n];
int a=1;
int p=1;
while(a<=n*n){
for(int i=p-1;i<=n-p;i++){
result[p-1][i]=a;a++;
}
if(a>n*n) break;
for(int i=p;i<=n-p;i++){
result[i][n-p]=a;a++;
}
if(a>n*n) break;
for(int i=n-p-1;i>=p-1;i--){
result[n-p][i]=a;a++;
}
if(a>n*n) break;
for(int i=n-p-1;i>=p;i--){
result[i][p-1]=a;a++;
}
if(a>n*n) break;
p++;
}
return result;
}
}