最新要闻

广告

手机

英国房地产因利率上升陷入困境 房价正以2011年来最快速度下跌

英国房地产因利率上升陷入困境 房价正以2011年来最快速度下跌

 宁夏评选出上半年10名“宁夏好人” 95后消防员因敬业奉献入选

宁夏评选出上半年10名“宁夏好人” 95后消防员因敬业奉献入选

家电

  1. 首页
  2. 移动通信
  3. 内容

代码随想录算法训练营第二天|力扣977.有序数组的平方、力扣209.长度最小的子数组、力扣59.螺旋矩阵

来源：博客园


(资料图)

数组part2

有序数组的平方（力扣977.)

  • 暴力解：先平方再使用快排O(nlogn)
  • 双指针：数组两边的绝对值更大，从两边向中间找到平方值大的数，并从尾向头部插入
    1. 先设一个新数组
    2. k =numsize -1;
    3. for(i=0,j=maxsize-1;i<=j;)
    4. if(nums[i]Xnums[i]>nums[j]Xnums[j])
class Solution {    public int[] sortedSquares(int[] nums) {        //首尾双指针，想中间行进        int[] result = new int[nums.length];        int i = 0;        int j = nums.length - 1;        int k = nums.length - 1;        while(i<=j){            if(nums[i]*nums[i]<=nums[j]*nums[j]){                result[k] = nums[j]*nums[j];                j--;                k--;            }else{                result[k] = nums[i]*nums[i];                i++;                k--;            }        }        return result;    }}

长度最小的子数组（力扣209.）

思路：如何移动起始位置i？另一个指针j指向终止位置

代码：

  1. for（j=0;j<=maxsize;j++)
  2. sum+=num[j];
  3. 直到while(sum>=s)
  4. subL=j-i+1;
  5. result初始为最大值，result=min(result,subL)
  6. i移动->sum=sum-nums[i];i++
class Solution {    public int minSubArrayLen(int target, int[] nums) {        int i = 0;        int j = 0;        int sum = 0;        int result = nums.length + 1;        int subL = 0;        //移动后指针        for(j=0;j= target){                //临时结果值                subL = j - i +1;                if(result>subL){                    result = subL;                }                sum = sum - nums[i];                //移动前指针                i++;            }        }        return (result==nums.length+1)?0:result;    }}

螺旋矩阵（力扣59.）

  • 基本无算法，模拟转圈。
  • 处理转圈的边界条件很多
  • 循环不变量：对每条边的处理规则是左闭右开呢还是左闭右闭呢？
  • 循环是在"条件表达式"和"变量增值之间"执行的
  1. while( n / 2 )//转圈的圈数
  2. startx=0;starty=0;offset=1;count=1;
  3. for(j=starty;j
  4. nums [startx] [j]=count++;
  5. for(i=startx;i
  6. nums [i] [j] = count++;
  7. for(;j>starty;j-- )
  8. nums[i] [j] = count++;
  9. for(;i>startx;i--)
  10. nums[i] [j] =count++;
  11. startx++;starty++;offset++;
  12. if(n%2==1)
  13. name[startx] [starty] =count;
class Solution {    public int[][] generateMatrix(int n) {        int temp = n;//暂存n值        int start = 0;        int i = 0;        int j = 0;        int offset = 0;//表示循环次数        int count = 1;        int[][] nums = new int[n][n];        while( offset++ < n / 2){//判断循环次数            //第一行循环            for(j = start;j < n - offset;j++){//下标为0~(n-1)且遵循左闭右开                nums[start][j] = count++;            }            for(i = start;i < n - offset; i++){                nums[i][j] = count++;            }            for(;j > start;j--){//此时边界条件为start                nums[i][j] = count++;            }            for(;i > start;i--){                nums[i][j] = count++;            }            start++;        }        //如果n是奇数，则在[start][start]位置设定为最后一位结果        if(temp % 2 == 1){            nums[start][start] = count;        }        return nums;    }}

关键词：