?代碼隨想錄打卡第二天, 新手自我記錄一下刷題歷程, 僅為自我打卡使用.

今天刷了三道主題, 第一道雙指針和第三道模擬做出來了, 第二道寫出了暴力解法但是提交leetcode超時了, 測試用例過了18/20, 看了carl哥答案以后自己重新補寫了滑動窗口方法.

977. 有序數(shù)組的平方

簡單題, 要求時間復雜度O(n), 考慮使用雙指針.

觀察到數(shù)組為有序數(shù)組, 可能有負數(shù).

建立一個與輸入等長的新數(shù)組作為容器, 雙指針分別指向輸入數(shù)組的兩端, 不斷比較指針所指的元素的平方值的大小, 將較大的一端放入新容器并移動指針位置.

class Solution {
public:
    vector<int> sortedSquares(vector<int>& nums) {
        int left = 0;
        int right = nums.size() - 1;
        vector<int> result(nums);
        for (int i = result.size()-1; i >= 0; --i){
            if (nums[left]*nums[left] >= nums[right]*nums[right]){
                result[i] = nums[left]*nums[left];
                left++;
            }
            else {
                result[i] = nums[right]*nums[right];
                right--;
            }
        }
        return result;
    }
};

暴力解法時間復雜度O(n^2), 即對每個可能的起點都找一遍滿足條件的最小子數(shù)組長度.

據(jù)說leetcode更新數(shù)據(jù)以前是能過的.

class Solution {
public:
    int minSubArrayLen(int target, vector<int>& nums) {
        int min_len = nums.size() + 1;
        for (int i = 0; i < nums.size(); ++i){
            int sum = 0;
            int len = nums.size() + 1;
            for (int j = i; j < nums.size(); ++j){
                sum += nums[j];
                if (sum >= target){
                    len = j - i + 1;
                    break;
                }
            }
            if (len < min_len){
                min_len = len;
            }
        }
        if (min_len != nums.size() + 1){
            return min_len;
        }
        else{
            return 0;
        }
    }
};

滑窗: 一個for循環(huán), 每個元素進入和退出窗口時各操作一次, 時間復雜度O(2n) = O(n)

class Solution {
public:
    int minSubArrayLen(int target, vector<int>& nums) {

        int min_len = nums.size() + 1;
        int sum = 0;
        int sub_len = nums.size() + 1;
        // start i, end j
        int i = 0;

        for (int j = 0; j < nums.size(); ++j){
            sum += nums[j];
            while (sum >= target){
                sub_len = j - i + 1;
                sum -= nums[i];
                i++;
            }
            if (sub_len < min_len){
                min_len = sub_len;
            }
        }

        if (min_len != nums.size() + 1){
            return min_len;
        }
        else {
            return 0;
        }

    }
};

循環(huán)不變量, 寫的時候思路和標準答案稍有一點點區(qū)別, 想的是在每條新邊上走幾步, 代碼看起來比答案亂一點.

class Solution {
public:
    vector<vector<int>> generateMatrix(int n) {
        vector<vector<int>> result(n, vector<int>(n, 0));
        int start_idx = 0;
        int num = 1;
        int count = 0;

        for (int i = n; i > 0; i-=2){
            for (int j = start_idx; j < start_idx + i - 1; ++j){
                result[start_idx][j] = num;
                num++;
            }
            for (int j = start_idx; j < start_idx + i - 1; ++j){
                result[j][i-1+start_idx] = num;
                num++;
            }
            for (int j = start_idx; j < start_idx + i - 1; ++j){
                result[i-1+start_idx][i+2*count-1-j] = num;
                num++;
            }
            for (int j = start_idx; j < start_idx + i - 1; ++j){
                result[i+2*count-1-j][start_idx] = num;
                num++;
            }
            start_idx++;
            count++;
        }

        if (n % 2 == 1){
            result[n/2][n/2] = num;
        }

        return result;
    }
};

另外看leetcode網(wǎng)站大神題解中有一種上下左右移邊界的題解做法感覺更助于理解, 更有美感.

數(shù)組部分的主干題目刷完啦! 撒花!

明天開始鏈表!文章來源地址http://www.zghlxwxcb.cn/news/detail-454801.html

到了這里，關(guān)于[自我記錄]隨想錄刷題第二天 | 977.有序數(shù)組的平方，209.長度最小的子數(shù)組，59.螺旋矩陣II的文章就介紹完了。如果您還想了解更多內(nèi)容，請在右上角搜索TOY模板網(wǎng)以前的文章或繼續(xù)瀏覽下面的相關(guān)文章，希望大家以后多多支持TOY模板網(wǎng)！