一、209. 长度最小的子数组
题目连接:https://leetcode.cn/problems/minimum-size-subarray-sum/
思路:使用滑动窗口思想,for内是索引是窗口的终止位置,slow是窗口的起始位置,当窗口内元素和大于target时,调整起始位置slow的向前,直到target < sum,注意这里调整使用while 而不是if
class Solution {
public int minSubArrayLen(int target, int[] nums) {
int sum = 0;
int slow = 0;
int result = Integer.MAX_VALUE;
for (int fast = 0; fast < nums.length; fast++){
sum += nums[fast];
while (sum >= target){
result = Math.min(result, fast - slow + 1);
sum = sum - nums[slow++];
}
}
return result == Integer.MAX_VALUE ? 0 : result;
}
}
二、904. 水果成篮 ☆☆☆
题目连接:https://leetcode.cn/problems/fruit-into-baskets/
思路:本题统计数组中种类为2的最长长度 。使用for fast为滑动窗口的起始位置,slow为窗口的终止位置,使用hashmap统计窗口中的水果的种类,当种类大于2即hashmap.size() > 2 调整窗口的终止位置,直到==2,然后统计种类=2的最长的长度
class Solution {
public int totalFruit(int[] fruits) {
int slow = 0;
int result = 0;
HashMap<Integer, Integer> hashMap = new HashMap<>();
for (int fast = 0; fast < fruits.length; fast++) {
hashMap.put(fruits[fast], hashMap.getOrDefault(fruits[fast], 0) + 1);
while (hashMap.size() > 2) {
hashMap.put(fruits[slow], hashMap.get(fruits[slow]) - 1);
if (hashMap.get(fruits[slow]) == 0) {
hashMap.remove(fruits[slow]);
}
slow++;
}
result = Math.max(result, fast - slow + 1);
}
return result;
}
}
三、 76. 最小覆盖子串 ☆☆☆
题目连接:https://leetcode.cn/problems/minimum-window-substring/
思路:使用两个hashmap,当t的hashmap和s的hashmap中字符的数量相同时 个数count+1, 当s中的出现的个数和t的个数相同时,即是符合窗口的内条件,然后在循环内缩小窗口范围,返回最小长度的的左边界和长度。
class Solution {
public String minWindow(String s, String t) {
if (s == null || s.length() == 0) return "";
if (t == null || t.length() == 0) return "";
HashMap<Character, Integer> thashMap = new HashMap<>();
for (int i = 0; i < t.length(); i++){
thashMap.put(t.charAt(i), thashMap.getOrDefault(t.charAt(i), 0) + 1);
}
int slow = 0;
int count = 0;
int minLength = Integer.MAX_VALUE;
int left = 0;
HashMap<Character, Integer> shashMap = new HashMap<>();
for (int fast = 0; fast < s.length(); fast++){
char c = s.charAt(fast);
shashMap.put(c, shashMap.getOrDefault(c, 0) + 1);
if (shashMap.get(c).equals(thashMap.getOrDefault(c, 0))){
count++;
}
while (count == thashMap.size()){
int length = fast - slow + 1;
if (minLength > length) {
//更新;
minLength = length;
left = slow;
}
char cc = s.charAt(slow);
if (shashMap.get(cc).equals(thashMap.getOrDefault(cc, 0))) {
count--;
}
shashMap.put(cc, shashMap.get(cc) - 1);
slow++;
}
}
System.out.println(minLength + " " + left);
return minLength == Integer.MAX_VALUE ? "" : s.substring(left, left + minLength);
}
}
四、 59. 螺旋矩阵 II
题目连接:https://leetcode.cn/problems/spiral-matrix-ii/
思路:使用前闭后开的原则遍历,圈数= n / 2 如果是奇数中间的位置是(start, start) = count;
class Solution {
public int[][] generateMatrix(int n) {
int nums[][] = new int[n][n];
int loop = 0;
int start = 0;
int count = 1;
while (loop++ < n / 2){
int j = start;
for (;j < n - loop; j++){
nums[start][j] = count++;
}
int i = start;
for (; i < n - loop; i++){
nums[i][j] = count++;
}
for (; j >= loop; j--){
nums[i][j] = count++;
}
for (; i >= loop; i--) {
nums[i][j] = count++;
}
start++;
}
if (n % 2 == 1) nums[start][start] = count;
return nums;
}
}