day01
704. 二分查找
题目
给定一个 n 个元素有序的（升序）整型数组 nums 和一个目标值 target ，写一个函数搜索 nums 中的 target，如果目标值存在返回下标，否则返回 -1。
示例 1:
输入: nums = [-1,0,3,5,9,12], target = 9
输出: 4
解释: 9 出现在 nums 中并且下标为 4
示例 2:
输入: nums = [-1,0,3,5,9,12], target = 2
输出: -1
解释: 2 不存在 nums 中因此返回 -1
提示：
你可以假设 nums 中的所有元素是不重复的。
n 将在 [1, 10000]之间。
nums 的每个元素都将在 [-9999, 9999]之间。
思路
我们定义 target 是在一个在左闭右闭的区间里，也就是[left, right] （这个很重要非常重要）。
区间的定义这就决定了二分法的代码应该如何写，因为定义target在[left, right]区间，所以有如下两点：
-
while (left <= right)要使用 <= ，因为left == right是有意义的，所以使用 <= -
if (nums[middle] > target)right 要赋值为 middle - 1，因为当前这个nums[middle]一定不是target，那么接下来要查找的左区间结束下标位置就是 middle - 1
例如在数组：1,2,3,4,7,9,10中查找元素2，如图所示：
代码实现
/**
* https://leetcode-cn.com/problems/binary-search/
*
* @author xiexu
* @create 2022-02-05 10:27 AM
*/
public class _704_二分查找 {
public int search(int[] nums, int target) {
if (target < nums[0] || target > nums[nums.length - 1]) {
return -1;
}
int left = 0;
// 定义target在左闭右闭的区间里，[left, right]
int right = nums.length - 1;
// 当left==right，区间[left, right]依然有效，所以用 <=
while (left <= right) {
// 防止溢出 等同于(left + right)/2
int mid = left + ((right - left) / 2);
if (nums[mid] > target) {
// target 在左区间，所以[left, middle - 1]
right = mid - 1;
} else if (nums[mid] < target) {
// target 在右区间，所以[middle + 1, right]
left = mid + 1;
} else { // nums[middle] == target
return mid; // 数组中找到目标值，直接返回下标
}
}
// 未找到目标值
return -1;
}
}
35. 搜索插入位置
题目
给定一个排序数组和一个目标值，在数组中找到目标值，并返回其索引。如果目标值不存在于数组中，返回它将会被按顺序插入的位置。
请必须使用时间复杂度为 O(log n) 的算法。
示例 1:
输入: nums = [1,3,5,6], target = 5
输出: 2
示例 2:
输入: nums = [1,3,5,6], target = 2
输出: 1
提示
1 <= nums.length <= 104
-104 <= nums[i] <= 104
nums 为无重复元素的升序排列数组
-104 <= target <= 104
代码实现
/**
* https://leetcode-cn.com/problems/search-insert-position/
*
* @author xiexu
* @create 2022-02-05 10:48 AM
*/
public class _35_搜索插入位置 {
public int searchInsert(int[] nums, int target) {
int n = nums.length;
int left = 0;
// 定义target在左闭右闭的区间里，[left, right]
int right = n - 1;
// 当left==right，区间[left, right]依然有效
while (left <= right) {
// 防止溢出 等同于(left + right)/2
int mid = left + ((right - left) / 2);
if (nums[mid] > target) {
// target 在左区间，所以[left, mid - 1]
right = mid - 1;
} else if (nums[mid] < target) {
// target 在右区间，所以[mid + 1, right]
left = mid + 1;
} else { // nums[mid] == target
return mid;
}
}
// 分别处理如下四种情况
// 目标值在数组所有元素之前 [0, -1]
// 目标值等于数组中某一个元素 return middle;
// 目标值插入数组中的位置 [left, right]，return right + 1
// 目标值在数组所有元素之后的情况 [left, right]， return right + 1
return right + 1;
}
}
34. 在排序数组中查找元素的第一个和最后一个位置
题目
给定一个按照升序排列的整数数组 nums，和一个目标值 target。找出给定目标值在数组中的开始位置和结束位置。
如果数组中不存在目标值 target，返回 [-1, -1]。
进阶：
- 你可以设计并实现时间复杂度为 O(log n) 的算法解决此问题吗？
示例 1：
输入：nums = [5,7,7,8,8,10], target = 8
输出：[3,4]
示例 2：
输入：nums = [5,7,7,8,8,10], target = 6
输出：[-1,-1]
示例 3：
输入：nums = [], target = 0
输出：[-1,-1]
提示：
0 <= nums.length <= 105
-109 <= nums[i] <= 109
nums 是一个非递减数组
-109 <= target <= 109
思路
寻找target在数组里的左右边界，有如下三种情况：
- 情况一：target 在数组范围的右边或者左边，例如数组{3, 4, 5}，target为2或者数组{3, 4, 5},target为6，此时应该返回{-1, -1}
- 情况二：target 在数组范围中，且数组中不存在target，例如数组{3,6,7},target为5，此时应该返回{-1, -1}
- 情况三：target 在数组范围中，且数组中存在target，例如数组{3,6,7},target为6，此时应该返回{1, 1}
这三种情况都考虑到，说明就想的很清楚了。
代码实现
/**
* https://leetcode-cn.com/problems/find-first-and-last-position-of-element-in-sorted-array/
*
* @author xiexu
* @create 2022-02-05 11:50 AM
*/
public class _34_在排序数组中查找元素的第一个和最后一个位置 {
public int[] searchRange(int[] nums, int target) {
int leftBorder = getLeftBorder(nums, target);
int rightBorder = getRightBorder(nums, target);
// 情况一
if (leftBorder == -2 || rightBorder == -2) {
return new int[]{-1, -1};
}
// 情况三
if (rightBorder - leftBorder > 1) {
return new int[]{leftBorder + 1, rightBorder - 1};
}
// 情况二
return new int[]{-1, -1};
}
// 二分查找，寻找target的右边界（不包括target）
// 如果rightBorder为没有被赋值（即target在数组范围的左边，例如数组[3,3]，target为2），为了处理情况一
public int getRightBorder(int[] nums, int target) {
int left = 0;
// 定义target在左闭右闭的区间里，[left, right]
int right = nums.length - 1;
// 记录一下rightBorder没有被赋值的情况
int rightBorder = -2;
while (left <= right) { // 当left==right，区间[left, right]依然有效
// 防止溢出 等同于(left + right)/2
int mid = left + ((right - left) / 2);
if (nums[mid] > target) {
// target 在左区间，所以[left, middle - 1]
right = mid - 1;
} else { // 当nums[mid] == target的时候，更新left，这样才能得到target的右边界
left = mid + 1;
rightBorder = left;
}
}
return rightBorder;
}
// 二分查找，寻找target的左边界leftBorder（不包括target）
// 如果leftBorder没有被赋值（即target在数组范围的右边，例如数组[3,3],target为4），为了处理情况一
public int getLeftBorder(int[] nums, int target) {
int left = 0;
// 定义target在左闭右闭的区间里，[left, right]
int right = nums.length - 1;
// 记录一下leftBorder没有被赋值的情况
int leftBorder = -2;
while (left <= right) {
int mid = left + ((right - left) / 2);
if (nums[mid] < target) {
left = mid + 1;
} else { // 寻找左边界，就要在nums[mid] == target的时候更新right
right = mid - 1;
leftBorder = right;
}
}
return leftBorder;
}
}
69. x 的平方根
题目
给你一个非负整数 x ，计算并返回 x 的 算术平方根 。
由于返回类型是整数，结果只保留 整数部分 ，小数部分将被 舍去 。
注意：不允许使用任何内置指数函数和算符，例如 pow(x, 0.5) 或者 x ** 0.5 。
示例 1：
输入：x = 4
输出：2
示例 2：
输入：x = 8
输出：2
解释：8 的算术平方根是 2.82842..., 由于返回类型是整数，小数部分将被舍去。
提示：
0 <= x <= 231 - 1
思路
- 整数x的平方根一定小于或等于x
- 除0之外的所有整数的平方根都大于或等于1
- 整数x的平方根一定是在1到x的范围内，取这个范围内的中间数字mid，并判断mid的平方是否小于或等于x，如果mid的平方小于x
- 那么接着判断(mid+1)的平方是否大于x，如果(mid+1)的平方大于x，那么mid就是x的平方根
- 如果mid的平方小于x并且(mid+1)的平方小于x，那么x的平方根比mid大，接下来搜索从mid+1到x的范围
- 如果mid的平方大于x，则x的平方根小于mid，接下来搜索1到mid-1的范围
- 然后在相应的范围内重复这个过程，总是取出位于范围中间的mid
代码实现
/**
* https://leetcode-cn.com/problems/sqrtx/
*
* @author xiexu
* @create 2022-02-05 1:06 PM
*/
public class _69_x的平方根 {
public int mySqrt(int x) {
// 整数x的平方根一定是在1到x的范围内
int left = 1;
int right = x;
while (left <= right) {
// 中间值 下面这样写是防止溢出
int mid = left + ((right - left) / 2);
// 判断mid的平方是否小于或等于x，如果mid的平方小于x
if (mid <= x / mid) { // 等价于：mid * mid <= x
// 判断(mid+1)的平方是否大于x，如果(mid+1)的平方大于x，那么mid就是x的平方根
if ((mid + 1) > x / (mid + 1)) {
return mid;
}
// 如果mid的平方小于x并且(mid+1)的平方小于x，那么x的平方根比mid大，接下来搜索从mid+1到x的范围
left = mid + 1;
} else if (mid > x / mid) { // 等价于：mid * mid > x
// 如果mid的平方大于x，则x的平方根小于mid，接下来搜索1到mid-1的范围
right = mid - 1;
}
}
// 如果输入参数是0，left等于1而right等于0，就直接返回0
return 0;
}
}
367. 有效的完全平方数
题目
给定一个 正整数 num ，编写一个函数，如果 num 是一个完全平方数，则返回 true ，否则返回 false 。
进阶：不要 使用任何内置的库函数，如 sqrt 。
示例 1：
输入：num = 16
输出：true
示例 2：
输入：num = 14
输出：false
提示：
1 <= num <= 2^31 - 1
代码实现
/**
* https://leetcode-cn.com/problems/valid-perfect-square/
* 注意：设置为long是为了防止乘法溢出
*
* @author xiexu
* @create 2022-02-05 1:39 PM
*/
public class _367_有效的完全平方数 {
public boolean isPerfectSquare(int num) {
long left = 1;
long right = num;
while (left <= right) {
long mid = left + ((right - left) / 2);
long res = mid * mid;
if (res == num) {
return true;
} else if (res < num) {
left = mid + 1;
} else { // res > num
right = mid - 1;
}
}
return false;
}
}
27. 移除元素
题目
给你一个数组 nums 和一个值 val，你需要 原地 移除所有数值等于 val 的元素，并返回移除后数组的新长度。
不要使用额外的数组空间，你必须仅使用 O(1) 额外空间并 原地 修改输入数组。
元素的顺序可以改变。你不需要考虑数组中超出新长度后面的元素。
示例 1：
输入：nums = [3,2,2,3], val = 3
输出：2, nums = [2,2]
解释：函数应该返回新的长度 2, 并且 nums 中的前两个元素均为 2。
你不需要考虑数组中超出新长度后面的元素。
例如，函数返回的新长度为 2 ，
而 nums = [2,2,3,3] 或 nums = [2,2,0,0]，也会被视作正确答案。
示例 2：
输入：nums = [0,1,2,2,3,0,4,2], val = 2
输出：5, nums = [0,1,4,0,3]
解释：函数应该返回新的长度 5, 并且 nums 中的前五个元素为 0, 1, 3, 0, 4。
注意这五个元素可为任意顺序。你不需要考虑数组中超出新长度后面的元素。
提示：
0 <= nums.length <= 100
0 <= nums[i] <= 50
0 <= val <= 100
思路
代码实现
/**
* https://leetcode-cn.com/problems/remove-element/
*
* @author xiexu
* @create 2022-02-05 1:46 PM
*/
public class _27_移除元素 {
public int removeElement(int[] nums, int val) {
// 快慢指针
int slow = 0;
int fast = 0;
while (fast < nums.length) {
if (nums[fast] != val) {
nums[slow] = nums[fast];
slow++;
}
fast++;
}
return slow;
}
}
26. 删除有序数组中的重复项
题目
给你一个有序数组 nums ，请你 原地 删除重复出现的元素，使每个元素 只出现一次 ，返回删除后数组的新长度。
不要使用额外的数组空间，你必须在 原地 修改输入数组 并在使用 O(1) 额外空间的条件下完成。
示例 1：
输入：nums = [1,1,2]
输出：2, nums = [1,2]
解释：函数应该返回新的长度 2 ，并且原数组 nums 的前两个元素被修改为 1, 2 。
不需要考虑数组中超出新长度后面的元素。
示例 2：
输入：nums = [0,0,1,1,1,2,2,3,3,4]
输出：5, nums = [0,1,2,3,4]
解释：函数应该返回新的长度 5 ， 并且原数组 nums 的前五个元素被修改为 0, 1, 2, 3, 4 。
不需要考虑数组中超出新长度后面的元素。
提示：
0 <= nums.length <= 3 * 10^4
-10^4 <= nums[i] <= 10^4
nums 已按升序排列
代码实现
/**
* https://leetcode-cn.com/problems/remove-duplicates-from-sorted-array/
*
* @author xiexu
* @create 2022-02-05 2:04 PM
*/
public class _26_删除有序数组中的重复项 {
public int removeDuplicates(int[] nums) {
if (nums.length == 0) {
return 0;
}
int slow = 0;
int fast = 0;
while (fast < nums.length) {
if (nums[fast] != nums[slow]) {
slow++;
// 维护 nums[0..slow] ⽆重复
nums[slow] = nums[fast];
}
fast++;
}
// 数组⻓度为索引 + 1
return slow + 1;
}
}
283. 移动零
题目
给定一个数组 nums，编写一个函数将所有 0 移动到数组的末尾，同时保持非零元素的相对顺序。
请注意 ，必须在不复制数组的情况下原地对数组进行操作。
示例 1:
输入: nums = [0,1,0,3,12]
输出: [1,3,12,0,0]
示例 2:
输入: nums = [0]
输出: [0]
提示 :
1 <= nums.length <= 10^4
-2^31 <= nums[i] <= 2^31 - 1
代码实现
/**
* https://leetcode-cn.com/problems/move-zeroes/
*
* @author xiexu
* @create 2022-02-05 2:19 PM
*/
public class _283_移动零 {
public void moveZeroes(int[] nums) {
int n = nums.length;
int slow = 0;
int fast = 0;
while (fast < n) {
if (nums[fast] != 0) {
nums[slow] = nums[fast];
slow++;
}
fast++;
}
while (slow < n) {
nums[slow] = 0;
slow++;
}
}
}
844. 比较含退格的字符串
题目
给定 s 和 t 两个字符串，当它们分别被输入到空白的文本编辑器后，请你判断二者是否相等。# 代表退格字符。
如果相等，返回 true ；否则，返回 false 。
注意：如果对空文本输入退格字符，文本继续为空。
示例 1：
输入：s = "ab#c", t = "ad#c"
输出：true
解释：S 和 T 都会变成 “ac”。
示例 2：
输入：s = "ab##", t = "c#d#"
输出：true
解释：s 和 t 都会变成 “”。
示例 3：
输入：s = "a##c", t = "#a#c"
输出：true
解释：s 和 t 都会变成 “c”。
示例 4：
输入：s = "a#c", t = "b"
输出：false
解释：s 会变成 “c”，但 t 仍然是 “b”。
提示：
1 <= s.length, t.length <= 200
s 和 t 只含有小写字母以及字符 '#'
代码实现
/**
* https://leetcode-cn.com/problems/backspace-string-compare/
*
* @author xiexu
* @create 2022-02-05 2:29 PM
*/
public class _844_比较含退格的字符串 {
public boolean backspaceCompare(String s, String t) {
char[] sarr = s.toCharArray();
char[] tarr = t.toCharArray();
// 求出s的结果字符串
int slow = 0;
int fast = 0;
while (fast < s.length()) {
if (sarr[fast] != '#') {
sarr[slow] = sarr[fast];
slow++;
} else if (sarr[fast] == '#' && slow > 0) {
slow--;
}
fast++;
}
int sLength = slow;
// 求出t的结果字符串
slow = 0;
fast = 0;
while (fast < t.length()) {
if (tarr[fast] != '#') {
tarr[slow] = tarr[fast];
slow++;
} else if (tarr[fast] == '#' && slow > 0) {
slow--;
}
fast++;
}
int tLength = slow;
if (sLength != tLength) {
return false;
}
for (int i = 0; i < sLength; i++) {
if (sarr[i] != tarr[i]) {
return false;
}
}
return true;
}
}
977. 有序数组的平方
题目
给你一个按 非递减顺序 排序的整数数组 nums，返回 每个数字的平方 组成的新数组，要求也按 非递减顺序 排序。
示例 1：
输入：nums = [-4,-1,0,3,10]
输出：[0,1,9,16,100]
解释：平方后，数组变为 [16,1,0,9,100]
排序后，数组变为 [0,1,9,16,100]
示例 2：
输入：nums = [-7,-3,2,3,11]
输出：[4,9,9,49,121]
提示：
1 <= nums.length <= 10^4
-10^4 <= nums[i] <= 10^4
nums 已按 非递减顺序 排序
思路
数组其实是有序的， 只不过负数平方之后可能成为最大数了。
那么数组平方的最大值就在数组的两端，不是最左边就是最右边，不可能是中间。
此时可以考虑双指针法了，left指向起始位置，right指向终止位置。
定义一个新数组 res，和A数组一样的大小，让 j 指向 res 数组终止位置。
代码实现
/**
* https://leetcode-cn.com/problems/squares-of-a-sorted-array/
*
* @author xiexu
* @create 2022-02-05 2:54 PM
*/
public class _977_有序数组的平方 {
public int[] sortedSquares(int[] nums) {
int left = 0;
int right = nums.length - 1;
int[] res = new int[nums.length];
int j = nums.length - 1;
while (left <= right) {
if (nums[left] * nums[left] > nums[right] * nums[right]) {
res[j] = nums[left] * nums[left];
j--;
left++;
} else {
res[j] = nums[right] * nums[right];
j--;
right--;
}
}
return res;
}
}
209. 长度最小的子数组
题目
给定一个含有 n 个正整数的数组和一个正整数 target 。
找出该数组中满足其和 ≥ target 的长度最小的 连续子数组 [numsl, numsl+1, ..., numsr-1, numsr] ，并返回其长度。如果不存在符合条件的子数组，返回 0 。
示例 1：
输入：target = 7, nums = [2,3,1,2,4,3]
输出：2
解释：子数组 [4,3] 是该条件下的长度最小的子数组。
示例 2：
输入：target = 4, nums = [1,4,4]
输出：1
示例 3：
输入：target = 11, nums = [1,1,1,1,1,1,1,1]
输出：0
提示：
1 <= target <= 10^9
1 <= nums.length <= 10^5
1 <= nums[i] <= 10^5
思路
以题目中的示例来举例，s=7， 数组是 2，3，1，2，4，3，来看一下查找的过程：
最后找到 4，3 是最短距离。
代码实现
/**
* https://leetcode-cn.com/problems/minimum-size-subarray-sum/
*
* @author xiexu
* @create 2022-02-07 6:27 PM
*/
public class _209_长度最小的子数组 {
public int minSubArrayLen(int target, int[] nums) {
int left = 0; // 滑动窗口起始位置
int sum = 0; // 滑动窗口数值之和
int result = Integer.MAX_VALUE;
for (int right = 0; right < nums.length; right++) {
sum += nums[right];
// 注意这里使用while，每次更新 left（起始位置），并不断比较子序列是否符合条件
while (sum >= target) {
result = Math.min(result, right - left + 1);
sum -= nums[left];
left++;
}
}
// 如果result没有被赋值的话，就返回0，说明没有符合条件的子序列
return result == Integer.MAX_VALUE ? 0 : result;
}
}
904. 水果成篮
题目
你正在探访一家农场，农场从左到右种植了一排果树。这些树用一个整数数组 fruits 表示，其中 fruits[i] 是第 i 棵树上的水果 种类 。
你想要尽可能多地收集水果。然而，农场的主人设定了一些严格的规矩，你必须按照要求采摘水果：
- 你只有 两个 篮子，并且每个篮子只能装 单一类型 的水果。每个篮子能够装的水果总量没有限制。
- 你可以选择任意一棵树开始采摘，你必须从 每棵 树（包括开始采摘的树）上 恰好摘一个水果 。采摘的水果应当符合篮子中的水果类型。每采摘一次，你将会向右移动到下一棵树，并继续采摘。
- 一旦你走到某棵树前，但水果不符合篮子的水果类型，那么就必须停止采摘。
给你一个整数数组 fruits ，返回你可以收集的水果的 最大 数目。
示例 1：
输入：fruits = [1,2,1]
输出：3
解释：可以采摘全部 3 棵树。
示例 2：
输入：fruits = [0,1,2,2]
输出：3
解释：可以采摘 [1,2,2] 这三棵树。
如果从第一棵树开始采摘，则只能采摘 [0,1] 这两棵树。
示例 3：
输入：fruits = [1,2,3,2,2]
输出：4
解释：可以采摘 [2,3,2,2] 这四棵树。
如果从第一棵树开始采摘，则只能采摘 [1,2] 这两棵树。
示例 4：
输入：fruits = [3,3,3,1,2,1,1,2,3,3,4]
输出：5
解释：可以采摘 [1,2,1,1,2] 这五棵树。
提示：
1 <= fruits.length <= 10^5
0 <= fruits[i] < fruits.length
代码实现
/**
* https://leetcode-cn.com/problems/fruit-into-baskets/
*
* @author xiexu
* @create 2022-02-07 7:01 PM
*/
public class _904_水果成篮 {
public int totalFruit(int[] fruits) {
HashMap<Integer, Integer> map = new HashMap<>();
int left = 0;
int res = 0;
for (int right = 0; right < fruits.length; right++) {
int num = fruits[right];
map.put(num, map.getOrDefault(num, 0) + 1);
while (map.size() > 2) {
int subNum = fruits[left];
left++;
map.put(subNum, map.get(subNum) - 1);
if (map.get(subNum) <= 0) {
map.remove(subNum);
}
}
res = Math.max(res, right - left + 1);
}
return res;
}
}
76. 最小覆盖子串
题目
给你一个字符串 s 、一个字符串 t 。返回 s 中涵盖 t 所有字符的最小子串。如果 s 中不存在涵盖 t 所有字符的子串，则返回空字符串 "" 。
注意：
- 对于
t中重复字符，我们寻找的子字符串中该字符数量必须不少于t中该字符数量。 - 如果
s中存在这样的子串，我们保证它是唯一的答案。
示例 1：
输入：s = "ADOBECODEBANC", t = "ABC"
输出："BANC"
示例 2：
输入：s = "a", t = "a"
输出："a"
示例 3:
输入: s = "a", t = "aa"
输出: ""
解释: t 中两个字符 'a' 均应包含在 s 的子串中，
因此没有符合条件的子字符串，返回空字符串。
提示：
1 <= s.length, t.length <= 10^5
s 和 t 由英文字母组成
代码实现
/**
* https://leetcode-cn.com/problems/minimum-window-substring/
*
* @author xiexu
* @create 2022-02-07 8:26 PM
*/
public class _76_最小覆盖子串 {
public String minWindow(String s, String t) {
HashMap<Character, Integer> need = new HashMap<>();
HashMap<Character, Integer> window = new HashMap<>();
for (char c : t.toCharArray()) {
need.put(c, need.getOrDefault(c, 0) + 1);
}
int left = 0;
// valid表示窗口中满足need条件的字符个数
int valid = 0;
// 记录最小覆盖子串的起始索引及长度
int start = 0;
int len = Integer.MAX_VALUE;
for (int right = 0; right < s.length(); right++) {
// c是将移入窗口的字符
char c = s.charAt(right);
// 进行窗口内数据的一系列更新
if (need.containsKey(c)) {
window.put(c, window.getOrDefault(c, 0) + 1);
if (window.get(c).equals(need.get(c))) {
valid++;
}
}
// 判断左侧窗口是否要收缩
while (valid == need.size()) {
// 在这里更新最小覆盖子串
if (right - left + 1 < len) {
start = left;
len = right - left + 1;
}
// d是将移出窗口的字符
char d = s.charAt(left);
// 左移窗口
left++;
// 进行窗口内数据的一系列更新
if (need.containsKey(d)) {
if (window.get(d).equals(need.get(d))) {
valid--;
}
window.put(d, window.get(d) - 1);
}
}
}
//返回最小覆盖子串
return len == Integer.MAX_VALUE ? "" : s.substring(start, start + len);
}
}
59. 螺旋矩阵 II
题目
给你一个正整数 n，生成一个包含 1到 n^2所有元素，且元素按顺时针顺序螺旋排列的 n x n正方形矩阵 matrix。
示例 1：
输入：n = 3
输出：[[1,2,3],[8,9,4],[7,6,5]]
示例 2：
输入：n = 1
输出：[[1]]
提示：
1 <= n <= 20
思路
- 生成一个
n×n空矩阵mat，随后模拟整个向内环绕的填入过程：- 定义当前左右上下边界
l,r,t,b，初始值num = 1，迭代终止值tar = n * n； - 当
num <= tar时，始终按照从左到右从上到下从右到左从下到上填入顺序循环，每次填入后：- 执行
num += 1：得到下一个需要填入的数字； - 更新边界：例如从左到右填完后，上边界
t += 1，相当于上边界向内缩 1。
- 执行
- 使用
num <= tar而不是l < r || t < b作为迭代条件，是为了解决当n为奇数时，矩阵中心数字无法在迭代过程中被填充的问题。
- 定义当前左右上下边界
- 最终返回
mat即可。
代码实现
/**
* https://leetcode-cn.com/problems/spiral-matrix-ii/
*
* @author xiexu
* @create 2022-02-07 8:52 PM
*/
public class _59_螺旋矩阵_II {
public int[][] generateMatrix(int n) {
int[][] res = new int[n][n];
int l = 0; // 左
int r = n - 1; // 右
int t = 0; // 上
int b = n - 1; // 下
int num = 1, tar = n * n;
while (num <= tar) {
for (int i = l; i <= r; i++) {
res[t][i] = num++; // left to right.
}
t++;
for (int i = t; i <= b; i++) {
res[i][r] = num++; // top to bottom.
}
r--;
for (int i = r; i >= l; i--) {
res[b][i] = num++; // right to left.
}
b--;
for (int i = b; i >= t; i--) {
res[i][l] = num++; // bottom to top.
}
l++;
}
return res;
}
}
54. 螺旋矩阵
题目
给你一个 m行 n列的矩阵 matrix，请按照 顺时针螺旋顺序，返回矩阵中的所有元素。
示例 1：
输入：matrix = [[1,2,3],[4,5,6],[7,8,9]]
输出：[1,2,3,6,9,8,7,4,5]
示例 2：
输入：matrix = [[1,2,3,4],[5,6,7,8],[9,10,11,12]]
输出：[1,2,3,4,8,12,11,10,9,5,6,7]
提示：
m == matrix.length
n == matrix[i].length
1 <= m, n <= 10
-100 <= matrix[i][j] <= 100
代码实现
/**
* https://leetcode-cn.com/problems/spiral-matrix/
*
* @author xiexu
* @create 2022-02-07 9:28 PM
*/
public class _54_螺旋矩阵 {
public List<Integer> spiralOrder(int[][] matrix) {
int m = matrix.length; //行
int n = matrix[0].length; //列
ArrayList<Integer> res = new ArrayList<>();
int t = 0; // 上
int b = m - 1; // 下
int l = 0; // 左
int r = n - 1; // 右
while (true) {
for (int i = l; i <= r; i++) {
res.add(matrix[t][i]); // left to right.
}
t++;
if (t > b) {
break;
}
for (int i = t; i <= b; i++) {
res.add(matrix[i][r]); // top to bottom.
}
r--;
if (r < l) {
break;
}
for (int i = r; i >= l; i--) {
res.add(matrix[b][i]); // right to left.
}
b--;
if (b < t) {
break;
}
for (int i = b; i >= t; i--) {
res.add(matrix[i][l]); // bottom to top.
}
l++;
if (l > r) {
break;
}
}
return res;
}
}
剑指 Offer 29. 顺时针打印矩阵
题目
输入一个矩阵，按照从外向里以顺时针的顺序依次打印出每一个数字。
示例 1：
输入：matrix = [[1,2,3],[4,5,6],[7,8,9]]
输出：[1,2,3,6,9,8,7,4,5]
示例 2：
输入：matrix = [[1,2,3,4],[5,6,7,8],[9,10,11,12]]
输出：[1,2,3,4,8,12,11,10,9,5,6,7]
限制：
0 <= matrix.length <= 100
0 <= matrix[i].length <= 100
代码实现
/**
* https://leetcode-cn.com/problems/shun-shi-zhen-da-yin-ju-zhen-lcof/
*
* @author xiexu
* @create 2022-02-07 10:11 PM
*/
public class _剑指Offer29_顺时针打印矩阵 {
public int[] spiralOrder(int[][] matrix) {
int m = matrix.length; //行
if (m == 0) {
return new int[0];
}
int n = matrix[0].length; //列
int[] res = new int[m * n];
int t = 0; // 上
int b = m - 1; // 下
int l = 0; // 左
int r = n - 1; // 右
int index = 0;
while (true) {
for (int i = l; i <= r; i++) {
res[index++] = matrix[t][i]; // left to right.
}
t++;
if (t > b) {
break;
}
for (int i = t; i <= b; i++) {
res[index++] = matrix[i][r]; // top to bottom.
}
r--;
if (r < l) {
break;
}
for (int i = r; i >= l; i--) {
res[index++] = matrix[b][i]; // right to left.
}
b--;
if (b < t) {
break;
}
for (int i = b; i >= t; i--) {
res[index++] = matrix[i][l]; // bottom to top.
}
l++;
if (l > r) {
break;
}
}
return res;
}
}