从0开始学习算法-第一天

数组-数组是存放在连续内存空间上的相同类型数据的集合

二分查找

时间复杂度：O(log n)
空间复杂度：O(1)

class Solution{
	public int search(int nums[],int target){
		//确保target在数组内
	  if(target<nums[0]||target>nums[length-1]){
		return -1;
	  }
	  int left=0;
	  int right=nums.length-1;
	  int middle=left+((right - left) >> 1);
	  while(left<=right){
	  if(target>nums[middle])
		left=middle+1;
	  else if(target<nums[middle])
		right=middle-1;
		else
		return middle; 
	}
	  return -1;
	}
}

力扣27:删除数组元素

class Solution{
	public int removeElement(int[] nums,int val){
	  //双指针
	  int slow=0;
	  for(int fast=0;fast<nums.length;fast++){
		if(nums[fast]!=val){
		  nums[slow]=nums[fast];
		  slow++;
		}
	  }
	  return slow;
	}
}

977.有序数组的平方

**************************

给你一个按非递减顺序排序的整数数组 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){
	int right=nums.length-1;
	int left=0;
	int[] result=new int[nums.length];
	int index=result.length-1;
	while(left<=right){
	  if(nums[left]*nums[left]>nums[right]*nums[right]){
		result[index--]=nums[left]*nums[left];
		left++;
	  }else{
		result[index--]=nums[right]*nums[right];
		right--;
	  }
	}
	return result;
  }
}

209.长度最小的子数组

**************************

给定一个含有 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

class Solution{
	public int minSubArrayLen(int s,int[]){
		int left=0;
		int sum=0;
		int res=Integer.MAX_VALUE;
		for(int right=0;right<nums.length;right++){
		  sum+=nums[right];
		  while(sum>=s){
			res=Math.min(result,right-left+1);
			sum-=nums[left];
			left++;
	}
		}
	  return result ==Integer.MAX_VALUE?0:result;
	}
}

59.螺旋矩阵II

**************************

给定一个正整数 n，生成一个包含 1 到 n^2 所有元素，且元素按顺时针顺序螺旋排列的正方形矩阵。

示例:

输入: 3 输出: [ [ 1, 2, 3 ], [ 8, 9, 4 ], [ 7, 6, 5 ] ]

class Solution(){
  public int[][] generateMatrix(int n){
	//使用二维数组定义结果矩阵
	int[][] res=new int[n][n];
	//定义每循环一个圈的起始位置
	int startx=0,starty=0;
	//每个圈循环几次,如果n是奇数的话单独处理
	int loop=n/2;
	//矩阵的中间位置
	int mid=n/2;
	//用来给矩阵中每一个空格赋值
	int offset=1;
	int i,j;
	while(loop--){
	  i=startx;//行
	  j=starty;//列
	//下面开始的四个for就是模拟转了一圈
	//模拟填充上行从左到右
	 for(j=starty;j<n-offset;j++){
	   res[startx][j]=count++;
	 }
	//填充右列
	for(i=startx;i<n-offset;i++){
	  res[i][j]=count++;
	}
	//填充下行
	for(;j>starty;j--){
	  res[i][j]=count++;
	}
	//填充左列
	 for(;i>startx;i--){
	   res[i][j]=count++;
	 }
	//第二圈开始,起始位置要加1
	startx++;
	starty++;
	//offset控制每一圈里每一条边的遍历长度
	offset+=1;
	 //如果n为奇数,需要给矩阵最中间位置赋值
	  if(n%2!=0){
		res[mid][mid]=count;
	  }
	  return res;
	}