Problem Description
Given an array of n positive integers and a positive integer target, find the length of the shortest continuous subarray whose sum is at least target. Return the length of this subarray. If no such subarray exists, return 0.
Example 1:
Input: target = 7, nums = [2,3,1,2,4,3]
Output: 2
Explanation: The subarray [4,3] has the minimum length satisfying the condition.
Example 2:
Input: target = 4, nums = [1,4,4]
Output: 1
Example 3:
Input: target = 11, nums = [1,1,1,1,1,1,1,1]
Output: 0
Solution
class Solution {
public int minSubArrayLen(int target, int[] nums) {
int minLength = Integer.MAX_VALUE;
int windowSum = 0;
int left = 0;
for (int right = 0; right < nums.length; right++) {
windowSum += nums[right];
while (windowSum >= target) {
minLength = Math.min(minLength, right - left + 1);
windowSum -= nums[left];
left++;
}
}
return minLength == Integer.MAX_VALUE ? 0 : minLength;
}
}
- Maximum Length of Repeated Suabrray
Problem Description
Given two integer arrays nums1 and nums2, return the length of the longest common subarray that appears in both arrays.
Example 1:
Input: nums1 = [1,2,3,2,1], nums2 = [3,2,1,4,7]
Output: 3
Explanation: The longest common subarray is [3,2,1] with length 3.
Example 2:
Input: nums1 = [0,0,0,0,0], nums2 = [0,0,0,0,0]
Output: 5
Solution
class Solution {
public int findLength(int[] nums1, int[] nums2) {
int len1 = nums1.length;
int len2 = nums2.length;
int[][] dp = new int[len1 + 1][len2 + 1];
int maxLen = 0;
for (int i = 1; i <= len1; i++) {
for (int j = 1; j <= len2; j++) {
if (nums1[i - 1] == nums2[j - 1]) {
dp[i][j] = dp[i - 1][j - 1] + 1;
maxLen = Math.max(maxLen, dp[i][j]);
}
}
}
return maxLen;
}
}
- Fruit Into Baskets
Problem Description
You are visiting a farm with果树 arranged in a row. Each tree has a fruit type represented by an integer array fruits. You have two baskets and each basket can only contain one type of fruit. You start at any tree, pick one fruit from each tree you visit, and must move right. Once you encounter a tree with a fruit type that doesn't match either basket, you must stop. Return the maximum number of fruits you can collect.
Example 1:
Input: fruits = [1,2,1]
Output: 3
Explanation: You can pick all 3 trees.
Example 2:
Input: fruits = [0,1,2,2]
Output: 3
Explanation: You can pick trees [1,2,2].
Example 3:
Input: fruits = [1,2,3,2,2]
Output: 4
Explanation: You can pick trees [2,3,2,2].
Solution
class Solution {
public int totalFruit(int[] fruits) {
Map<Integer, Integer> basket = new HashMap<>();
int maxCount = 0;
int start = 0;
for (int end = 0; end < fruits.length; end++) {
int current = fruits[end];
basket.put(current, basket.getOrDefault(current, 0) + 1);
while (basket.size() > 2) {
int left = fruits[start];
basket.put(left, basket.get(left) - 1);
if (basket.get(left) == 0) {
basket.remove(left);
}
start++;
}
maxCount = Math.max(maxCount, end - start + 1);
}
return maxCount;
}
}
- Minimum Window Substring
Problem Description
Given two strings s and t, return the minimum window in s that contains all characters of t. If no such window exists, return an empty string.
Example 1:
Input: s = "ADOBECODEBANC", t = "ABC"
Output: "BANC"
Explanation: The minimum window "BANC" contains 'A', 'B', and 'C' from t.
Example 2:
Input: s = "a", t = "a"
Output: "a"
Example 3:
Input: s = "a", t = "aa"
Output: ""
Explanation: Both 'a' characters from t must be included, but s has only one.
LCR 146. Spiral Traverse 2D Array
Problem Description
Given a 2D array, perform a spiral traversal starting from the top-left corner, moving right, down, left, up in order, then repeating for inner layers until all elements are extracted.
Example 1:
Input: array = [[1,2,3],[8,9,4],[7,6,5]]
Output: [1,2,3,4,5,6,7,8,9]
Example 2:
Input: array = [[1,2,3,4],[12,13,14,5],[11,16,15,6],[10,9,8,7]]
Output: [1,2,3,4,5,6,7,8,9,10,11,12,13,14,15,16]
Solution
class Solution {
public int[] spiralArray(int[][] array) {
if (array == null || array.length == 0) {
return new int[]{};
}
int rows = array.length;
int cols = array[0].length;
int[] result = new int[rows * cols];
int pos = 0;
int leftBound = 0, rightBound = cols - 1;
int topBound = 0, bottomBound = rows - 1;
while (leftBound <= rightBound && topBound <= bottomBound) {
for (int col = leftBound; col <= rightBound; col++) {
result[pos++] = array[topBound][col];
}
for (int row = topBound + 1; row <= bottomBound; row++) {
result[pos++] = array[row][rightBound];
}
if (leftBound < rightBound && topBound < bottomBound) {
for (int col = rightBound - 1; col > leftBound; col--) {
result[pos++] = array[bottomBound][col];
}
for (int row = bottomBound; row > topBound; row--) {
result[pos++] = array[row][leftBound];
}
}
leftBound++;
rightBound--;
topBound++;
bottomBound--;
}
return result;
}
}
- Spiral Matrix II
Problem Description
Givan a positive integer n, generate an n x n matrix containing numbers from 1 to n² in clockwise spiral order.
Example 1:
Input: n = 3
Output: [[1,2,3],[8,9,4],[7,6,5]]
Example 2:
Input: n = 1
Output: [[1]]
Solution
class Solution {
public int[][] generateMatrix(int n) {
int[][] result = new int[n][n];
int num = 1;
int leftBound = 0, rightBound = n - 1;
int topBound = 0, bottomBound = n - 1;
while (leftBound <= rightBound && topBound <= bottomBound) {
for (int col = leftBound; col <= rightBound; col++) {
result[topBound][col] = num++;
}
for (int row = topBound + 1; row <= bottomBound; row++) {
result[row][rightBound] = num++;
}
if (leftBound < rightBound && topBound < bottomBound) {
for (int col = rightBound - 1; col > leftBound; col--) {
result[bottomBound][col] = num++;
}
for (int row = bottomBound; row > topBound; row--) {
result[row][leftBound] = num++;
}
}
leftBound++;
rightBound--;
topBound++;
bottomBound--;
}
return result;
}
}
- Spiral Matrix
Problem Description
Given an m x n matrix, return all elements in clockwise spiral order.
Example 1:
Input: matrix = [[1,2,3],[4,5,6],[7,8,9]]
Output: [1,2,3,6,9,8,7,4,5]
Example 2:
Input: matrix = [[1,2,3,4],[5,6,7,8],[9,10,11,12]]
Output: [1,2,3,4,8,12,11,10,9,5,6,7]
Solution
class Solution {
public List<Integer> spiralOrder(int[][] matrix) {
List<Integer> result = new ArrayList<>();
if (matrix == null || matrix.length == 0) {
return result;
}
int rows = matrix.length;
int cols = matrix[0].length;
int leftBound = 0, rightBound = cols - 1;
int topBound = 0, bottomBound = rows - 1;
while (leftBound <= rightBound && topBound <= bottomBound) {
for (int col = leftBound; col <= rightBound; col++) {
result.add(matrix[topBound][col]);
}
for (int row = topBound + 1; row <= bottomBound; row++) {
result.add(matrix[row][rightBound]);
}
if (leftBound < rightBound && topBound < bottomBound) {
for (int col = rightBound - 1; col > leftBound; col--) {
result.add(matrix[bottomBound][col]);
}
for (int row = bottomBound; row > topBound; row--) {
result.add(matrix[row][leftBound]);
}
}
leftBound++;
rightBound--;
topBound++;
bottomBound--;
}
return result;
}
}