每日一题
滑动窗口
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