从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;
}