代碼隨想錄算法訓練營第二天|LeetCode977,209,59 有序數(shù)組的平方-977

第一感覺是針對排序的考察，題目的進階要求設(shè)計時間復(fù)雜度為O(n)的算法，而采用快排的時間復(fù)雜度為O（nlogn），在參考網(wǎng)站給出的解題思路后，注意到數(shù)組為非遞減排序，那么數(shù)組平方的大值就在數(shù)組的兩端，此時考慮雙指針法，分別指向起始位置與終止止位置。

創(chuàng)新互聯(lián)-專業(yè)網(wǎng)站定制、快速模板網(wǎng)站建設(shè)、高性價比淮安區(qū)網(wǎng)站開發(fā)、企業(yè)建站全套包干低至880元,成熟完善的模板庫,直接使用。一站式淮安區(qū)網(wǎng)站制作公司更省心,省錢,快速模板網(wǎng)站建設(shè)找我們，業(yè)務(wù)覆蓋淮安區(qū)地區(qū)。費用合理售后完善，十載實體公司更值得信賴。

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

長度最小的子數(shù)組-209

看到題的第一想法還是暴力，但時間復(fù)雜度太高。
參考博客給出的思路實現(xiàn)滑動窗口，窗口內(nèi)為滿足條件的子數(shù)組；若當前窗口的值大于s了，窗口向前移動；窗口結(jié)束位置則為遍歷數(shù)組的指針。

public static int minSubArrayLen(int target, int[] nums) {//記錄最小子數(shù)組的長度
        int flag = Integer.MAX_VALUE;
        //記錄子數(shù)組的和
        int sum = 0;
        //記錄子數(shù)組的起始索引
        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

需要先想清楚整個循環(huán)的步驟，在循環(huán)過程中如何保持住循環(huán)不變量

public int[][] generateMatrix(int n) {//記錄循環(huán)起始位置
        int i = 0;
        int j = 0;
        //記錄最終生成的數(shù)組
        int[][] res = new int[n][n];
        //記錄循環(huán)條件，總共要循環(huán)n/2圈
        int loop = 0;
        //給每個位置要賦值的值
        int value = 1;
        //記錄每次循環(huán)的開始點
        int start = 0;
        //開始循環(huán)
        while( loop ++< n/2){//這里loop在判斷完之后就已經(jīng)加1了
            //循環(huán)每一條邊的時候都采用左閉右開的方式
            //上側(cè)從左到右
            for( j = start ; j< n - loop; j++){res[start][j] = value++;
            }
            //右側(cè)從上到下
            for (i = start; i< n - loop ; i++){res[i][j] = value++;
            }
            //下側(cè)從右往左
            for (; j >= loop; j--){res[i][j] = value++;
            }

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

        //如果n為奇數(shù)的話，要給最中間的單獨賦值
        if ( n % 2 != 0 ){res[n/2][n/2] = n * n;
        }

你是否還在尋找穩(wěn)定的海外服務(wù)器提供商？創(chuàng)新互聯(lián)www.cdcxhl.cn海外機房具備T級流量清洗系統(tǒng)配攻擊溯源，準確流量調(diào)度確保服務(wù)器高可用性，企業(yè)級服務(wù)器適合批量采購，新人活動首月15元起，快前往官網(wǎng)查看詳情吧

文章題目：代碼隨想錄算法訓練營第二天|LeetCode977,209,59-創(chuàng)新互聯(lián)
轉(zhuǎn)載來于：http://weahome.cn/article/coeoje.html