每日一题03

每日一题

滑动窗口

leetcode 209 长度最小的子数组

https://leetcode.cn/problems/minimum-size-subarray-sum/

代码：

cpp

class Solution {
public:
    int minSubArrayLen(int target, vector<int>& nums) {
        int sum = 0;
        int j = 0;
        int res = nums.size() + 10;
        for(int i = 0; i < nums.size(); i++ ){   
            sum += nums[i];
            while(sum >= target ){
                res = min(res, i - j + 1);
                sum -= nums[j++];
            }
        }
        res = (res == nums.size() + 10 ? 0 : res);
        return res;
    }
};

python:

class Solution:
    def minSubArrayLen(self, target: int, nums: List[int]) -> int:
        res = len(nums) + 10
        sum = 0
        j = 0
        for i in range(len(nums)):
            sum += nums[i]
            while sum >= target: 
                res = min(res, i - j + 1)
                sum -= nums[j]
                j += 1
        if res == len(nums) + 10:
            res = 0
        return res

leetcode 904 水果成篮

https://leetcode.cn/problems/fruit-into-baskets/

代码：

cpp:

class Solution {
public:
    int totalFruit(vector<int>& fruits) {
        int res = 0;
        unordered_map<int, int> cnt;
        int j = 0;
        for(int i = 0; i < fruits.size(); i++){
            cnt[fruits[i]]++;
            while(cnt.size() > 2){
                auto it = cnt.find(fruits[j]);
                it->second--;
                if(it->second == 0) cnt.erase(fruits[j]);
                j++;
            }
            res = max(res, i - j + 1);
        }
        return res;
    }
};

python

可以使用哈希表cnt维护当前窗口内的水果数量和对应的数量

class Solution:
    def totalFruit(self, fruits: List[int]) -> int:
        res = j = 0
        cnt = Counter()
        for i, x in enumerate(fruits):
            cnt[x] += 1
            while len(cnt) > 2:
                cnt[fruits[j]] -= 1
                if cnt[fruits[j]] == 0:
                    cnt.pop(fruits[j])
                j += 1
            res = max(res, i - j + 1)
        return res 

leetcode 76.最小覆盖字串

https://leetcode.cn/problems/minimum-window-substring/

代码:

cpp

class Solution {
public:
    string minWindow(string s, string t) {
        unordered_map<char, int> hs, ht;
        for(auto c: t) ht[c] ++;
        int j = 0;
        string res;
        int cnt = 0;
        for(int i = 0; i < s.size(); i ++){
            hs[s[i]]++;
            if(hs[s[i]] <= ht[s[i]]) cnt++;

            while(hs[s[j]] > ht[s[j]]) hs[s[j++]]--;
            if(cnt == t.size()){
                if(res.empty() || i - j + 1 < res.size()){
                    res = s.substr(j, i - j + 1);
                }
            }
        }
        return res;
    }
};

python

class Solution:
    def minWindow(self, s: str, t: str) -> str:
        ans_left, ans_right = -1, len(s)
        left = 0
        cnt_s = Counter()
        cnt_t = Counter(t)
        for right, c in enumerate(s):
            cnt_s[c] += 1

            while cnt_s >= cnt_t:
                if right - left < ans_right - ans_left:
                   ans_left, ans_right = left, right
                
                cnt_s[s[left]] -= 1
                left += 1
        return "" if ans_left < 0 else s[ans_left: ans_right + 1]

模拟过程

leetcode 59 螺旋矩阵

https://leetcode.cn/problems/spiral-matrix-ii/

代码：

cpp

class Solution {
public:
    vector<vector<int>> generateMatrix(int n) {
        int maxNum = n * n;
        int curNum = 1;
        vector<vector<int>> martix(n, vector<int>(n));
        int row = 0;
        int cloumn = 0;
        vector<vector<int>> directions = {{0,1}, {1,0}, {0,-1}, {-1,0}};
        int index = 0;
        while(curNum <= maxNum){
            martix[row][cloumn] = curNum;
            curNum ++;
            int nextRow = row + directions[index][0];
            int nextColumn = cloumn + directions[index][1];

            if(nextRow < 0 || nextRow >= n || nextColumn < 0 || nextColumn >= n || martix[nextRow][nextColumn] != 0){
                index = (index + 1) % 4;
            }
            row = row + directions[index][0];
            cloumn = cloumn + directions[index][1];
        }
        return martix;
    }
};

python

class Solution:
    def generateMatrix(self, n: int) -> List[List[int]]:
        dirs = [(0, 1), (1, 0), (0, -1), (-1, 0)]
        matrix = [[0] * n for _ in range(n)]
        row, col, dirIdx = 0, 0, 0
        for i in range(n * n):
            matrix[row][col] = i + 1
            dx, dy = dirs[dirIdx]
            r, c = row + dx, col + dy
            if r < 0 or r >= n or c < 0 or c >= n or matrix[r][c] > 0:
                dirIdx = (dirIdx + 1) % 4   # 顺时针旋转至下一个方向
                dx, dy = dirs[dirIdx]
            row, col = row + dx, col + dy
        
        return matrix

leetcode 54 螺旋矩阵

https://leetcode.cn/problems/spiral-matrix/

该题同时也是剑指offer146，即LCR 146 螺旋遍历二维数组

https://leetcode.cn/problems/shun-shi-zhen-da-yin-ju-zhen-lcof/

代码：

cpp

class Solution {
public:
    vector<int> spiralOrder(vector<vector<int>>& matrix) {
        if (matrix.size() == 0 || matrix[0].size() == 0) {
            return {};
        }
        vector<vector<int>> directions = {{0,1}, {1,0}, {0,-1}, {-1,0}};
        int index = 0;
        int cnt = 0;
        vector<vector<bool>> visit(matrix.size(),vector<bool>(matrix[0].size()));
        vector<int> res(matrix.size() * matrix[0].size());
        int row = 0;
        int column = 0;
        while(cnt < matrix.size()*matrix[0].size()){
            res[cnt] = matrix[row][column];
            visit[row][column] = true;
            cnt ++ ;

            int nextRow = row + directions[index][0];
            int nextColumn = column + directions[index][1];
            if(nextRow < 0 || nextRow >= matrix.size() || nextColumn < 0 || nextColumn >= matrix[0].size() || visit[nextRow][nextColumn]){
                index = (index + 1) % 4;
            } 
            row = row + directions[index][0];
            column = column + directions[index][1];
        }
        return res;
    }
};

python

class Solution:
    def spiralOrder(self, matrix: List[List[int]]) -> List[int]:
        rows = len(matrix)
        columns = len(matrix[0])
        visit = [[False]*columns for _ in range(rows)]
        res = [0] * (rows * columns)
        row, column = 0, 0
        directions = [[0,1],[1,0],[0,-1],[-1,0]]
        index = 0
        for i in range(rows * columns):
            res[i] = matrix[row][column]
            visit[row] [column] = True
            nextRow = row + directions[index][0]
            nextColumn = column + directions[index][1]
            if nextRow < 0 or nextRow >= rows or nextColumn < 0 or nextColumn >= columns or visit[nextRow][nextColumn]:
                index = (index + 1) % 4
            row += directions[index][0]
            column += directions[index][1]
        return res