关于leetcode:刷题心得-leetcode-977-leetcode-209-leetcode-59

32次阅读

共计 1612 个字符,预计需要花费 5 分钟才能阅读完成。

leetcode 977 题目链接:
https://leetcode.com/problems/squares-of-a-sorted-array/

最终 ac 代码:(双指针法)

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

        reverse(v.begin(), v.end());
        return v;
    }
};

std::vector operator[] 不做越界查看,vector::at 才查看

leetcode 209 题目链接:
https://leetcode.com/problems/minimum-size-subarray-sum/

ac 代码:(滑动窗口) 毛病:圈复杂度比拟大

class Solution
{
public:
    int minSubArrayLen(int target, vector<int> &nums)
    {
        int wl = 0;
        int wr = 0;
        int wsum = 0;
        int minWlen = INT_MAX;
        while (true)
        {if (wsum < target)
            {if (wr == nums.size())
                    break;
                wsum += nums[wr];
                ++wr;
            }
            else
            {
                int wlen = wr - wl;
                if (wlen < minWlen)
                    minWlen = wlen;
                wsum -= nums[wl];
                ++wl;
            }
        }
        if (minWlen == INT_MAX)
            return 0;
        return minWlen;
    }
};

双循环版本 (复杂度依然是 O(n),圈复杂度升高 ):

class Solution
{
public:
    int minSubArrayLen(int target, vector<int> &nums)
    {
        int wl = 0;
        int wsum = 0;
        int minWlen = INT_MAX;
        for (int wr = 0; wr < nums.size(); ++wr)
        {wsum += nums[wr];
            while (wsum >= target)
            {
                int wlen = wr - wl + 1;
                if (wlen < minWlen)
                    minWlen = wlen;
                wsum -= nums[wl++];
            }
        }
        if (minWlen == INT_MAX)
            return 0;
        return minWlen;
    }
};

leetcode 59
https://leetcode.com/problems/spiral-matrix-ii/
ac 代码:

class Solution
{
public:
    vector<vector<int>> generateMatrix(int n)
    {vector<vector<int>> v(n);
        for (int i = 0; i < v.size(); i++)
        {v[i] = vector<int>(n);
        }

        int square = n * n;
        int loopnum = n / 2;
        if (n % 2 == 1)
        {v[loopnum][loopnum] = square;
        }

        int num = 1;
        for (int i = 0; i < loopnum; i++)
        {for (int j = i; j < n - 1 - i; ++j)
            {v[i][j] = num++;
            }

            for (int j = i; j < n - 1 - i; ++j)
            {v[j][n - i - 1] = num++;
            }

            for (int j = n - i - 1; j > i; --j)
            {v[n - i - 1][j] = num++;
            }

            for (int j = n - i - 1; j > i; --j)
            {v[j][i] = num++;
            }
        }

        return v;
    }
};

正文完
 0