代码随想录算法训练营第二天|LeetCode977,209,59-创新互联

代码随想录算法训练营第二天|LeetCode977,209,59 有序数组的平方-977

第一感觉是针对排序的考察,题目的进阶要求设计时间复杂度为O(n)的算法,而采用快排的时间复杂度为O(nlogn),在参考网站给出的解题思路后,注意到数组为非递减排序,那么数组平方的大值就在数组的两端,此时考虑双指针法,分别指向起始位置与终止止位置。

创新互联-专业网站定制、快速模板网站建设、高性价比淮安区网站开发、企业建站全套包干低至880元,成熟完善的模板库,直接使用。一站式淮安区网站制作公司更省心,省钱,快速模板网站建设找我们,业务覆盖淮安区地区。费用合理售后完善,十载实体公司更值得信赖。
public int[] sortedSquares(int[] nums) {int len = nums.length;

        int index = len - 1;
        int[] results = new int[len];

        int j = len - 1;
        int i = 0;

        while (index >= 0){int tmp1 = nums[i] * nums[i];
            int tmp2 = nums[j]* nums[j];
            if (tmp1<=tmp2){results[index] = tmp2;
                j--;
            }else {results[index] = tmp1;
                i++;
            }
            index--;
        }
        return results;
    }
长度最小的子数组-209

看到题的第一想法还是暴力,但时间复杂度太高。
参考博客给出的思路实现滑动窗口,窗口内为满足条件的子数组;若当前窗口的值大于s了,窗口向前移动;窗口结束位置则为遍历数组的指针。

public static int minSubArrayLen(int target, int[] nums) {//记录最小子数组的长度
        int flag = Integer.MAX_VALUE;
        //记录子数组的和
        int sum = 0;
        //记录子数组的起始索引
        int start = 0;
        for (int i = 0; i< nums.length; i++){sum += nums[i];
            while (sum >= target){int len = i - start + 1;
                flag = len< flag? len:flag;
                sum -= nums[start];
                start++;
            }
        }
        return flag==Integer.MAX_VALUE? 0: flag;
    }
螺旋矩阵 II - 59

需要先想清楚整个循环的步骤,在循环过程中如何保持住循环不变量

public int[][] generateMatrix(int n) {//记录循环起始位置
        int i = 0;
        int j = 0;
        //记录最终生成的数组
        int[][] res = new int[n][n];
        //记录循环条件,总共要循环n/2圈
        int loop = 0;
        //给每个位置要赋值的值
        int value = 1;
        //记录每次循环的开始点
        int start = 0;
        //开始循环
        while( loop ++< n/2){//这里loop在判断完之后就已经加1了
            //循环每一条边的时候都采用左闭右开的方式
            //上侧从左到右
            for( j = start ; j< n - loop; j++){res[start][j] = value++;
            }
            //右侧从上到下
            for (i = start; i< n - loop ; i++){res[i][j] = value++;
            }
            //下侧从右往左
            for (; j >= loop; j--){res[i][j] = value++;
            }

            for (; i >= loop; i--){res[i][j] = value++;
            }
            start++;
        }

        //如果n为奇数的话,要给最中间的单独赋值
        if ( n % 2 != 0 ){res[n/2][n/2] = n * n;
        }

你是否还在寻找稳定的海外服务器提供商?创新互联www.cdcxhl.cn海外机房具备T级流量清洗系统配攻击溯源,准确流量调度确保服务器高可用性,企业级服务器适合批量采购,新人活动首月15元起,快前往官网查看详情吧


网页标题:代码随想录算法训练营第二天|LeetCode977,209,59-创新互联
当前URL:http://pwwzsj.com/article/coeoje.html