数组系列
一、数组基础
1.理论基础
- 数组是存放在连续内存空间上的相同类型数据的集合。
- 正因为数组的在内存空间的地址是连续的，所以我们在删除或者添加元素的时候，就难免要移动其他元素的地址。
-
数组的元素是不能删的，只能覆盖：就是将删除元素后面的元素往前移动，覆盖原来的数据,达到删除的目的。
-
二维数组的长度问题：
//二维数组的长度通俗来讲就是行的长度和列的长度 //给定一个 4行5列 的二维数组 int[][] arr = new int[4][5]; //计算行的长度(即有几行)：4 int length1 = arr.length; //计算列的长度(即有几列)：5 int length2 = arr[0].length;//可以看做第一行的长度
-
2.常用API
- 对数组进行操作，一般可以用Arrays.方法名(数组名)
【注意】（1）是Arrays不是Array
（2）java Array和Arrays的区别？
---数组类Array属于java.lang：提供了动态创建和访问Java数组的方法。其中的元素的类型必须相同。 效率高，但容量固定且无法动态改变。 它无法判断其中实际存有多少元素，length只是告诉我们array的容量。
---静态类Arrays属于java.util：此静态类专门用来操作array ，提供搜索、排序、复制等静态方法。
---静态类Arrays属于java.util：此静态类专门用来操作array ，提供搜索、排序、复制等静态方法。
-
数组的定义
-
静态初始化
int[] arr = {1,2,3}; -
动态初始化
int[] arr = new int[length];
-
静态初始化
- 数组长度问题：
- java中数组是没有length()方法的，只有length属性，数组array.length返回的是该数组的长度。
- 字符串String是有length()方法的，str.length()返回的是该字符串的长度。
-
static void Arrays.sort(数组名) 将指定数组从小到大排序，无返回值。 static List<T> Arrays.asList(元素a,元素b,元素c...)
用来将数组转为list集合。List<String> stooges = Arrays.asList("Larry", "Moe", "Curly");
二、题目类型
1.二分查找
（1）解题技巧
- 适用条件：有序数组+无重复元素(重复元素会导致返回的元素下标不唯一，但不是说有重复元素一定不能用二分法，比如lc34找左右边界那道题)
-
二分法问题要确定区间，在每次查找时严格遵循“循环不变量”原则，确定好是左闭右闭，还是左闭右开：
-
左闭右闭时，while循环条件中的left=right才有意义，即区间[left, right]依然有效
#以查找目标值在数组中的位置为例 public int search(int[] nums, int target) { int left=0,right=nums.length-1; //左闭右闭 while(left<=right){ //要写上=，因为left=right是有意义的 int mid = (left + right)/2; if(nums[mid] < target){ left=mid+1; //这里要加1，因为nums[mid]一定不是target，所以下一次查找的左区间是在mid的右邻 }else if(nums[mid] > target){ right=mid-1; //这里要加1，因为nums[mid]一定不是target，所以下一次查找的右区间是在mid的左邻 }else{ return mid; } } return -1; } -
左闭右开时，因为left = right的时候，在[left, right)是无效的空间，所以左＝右就没有意义了，所以while循环条件不用写=
public int search(int[] nums, int target) { int left=0,right=nums.length; //左闭右开 while(left<right){ //不写=，因为左闭右开时left=right是没有意义的 int mid = (left + right)/2; if(nums[mid] < target){ left=mid+1; //这里要加1，因为nums[mid]一定不是target，所以下一次查找的左区间是在mid的右邻 }else if(nums[mid] > target){ right=mid; //这里不加1，因为nums[mid]一定不是target，所以下一次查找的右区间是在mid的左邻，同时要保持每次查找区间都是左闭右开的 //所以right等于mid即可 }else{ return mid; } } return -1; }确定好区间后，要保证每次查找都保持区间不变，即下一次查找区间也要保证相同的区间规则：
当左闭右闭，nums[mid] > target时，下一次查找的右区间是在mid的左邻，因为是右闭，所以right=mid-1；(nums[mid]肯定不是目标值了)
当左闭右开，nums[mid] > target时，下一次查找的右区间也是在mid的左邻，但由于是右开，所以right直接=mid就好。
-
左闭右闭时，while循环条件中的left=right才有意义，即区间[left, right]依然有效
-
如果目标值不在数组中，那么目标值的插入位置在哪呢？
目标值的插入位置无非三种情况：- 目标值在所有元素之前
- 目标值在所有元素之后
-
目标值插在数组中
无论是右闭还是右开，不在数组中的目标值的插入位置都是left所指位置，即left是数组中第一个大于target的数的位置。
-
当目标值不在数组中，循环结束时的left与right的关系？
- 右闭：left=right+1，即left是right的右邻。因为右闭时循环条件包括left=right，所以left=right时还会进入循环，所以退出循环时是left=right+1；
- 右开：left=right。因为右闭开时循环条件不包括left=right，所以left=right直接退出循环了。
-
当目标值不在数组中，循环结束时的left与right所指位置与目标值的关系？
- 右闭：当while循环结束时，则right指向最大小于目标值的值，left指向最小大于目标值的值，且两个指针是相邻的。
- 右开：当while循环结束时，left == right，且都指向最小大于目标值的值。
（2）相关题目推荐
1）704.二分查找
2）35.搜索插入位置——2.（2）
3）★★34.在【有重复元素】排序数组中查找元素的第一个和最后一个位置(找左右边界)
-
思路：使用两次二分分别找左右边界：
- nums[mid]不等于目标值时：无论是找左边界还是右边界都正常二分区间；
-
nums[mid]等于目标值时：
- 找左边界，就不断往左逼近，即right=mid-1，但是要记住左边界不是right，是mid，因为nums[mid]==target嘛；
- 找右边界，就不断往右逼近，即left=mid+1，同理，右边界不是left，是mid。
- 目标值不在数组中的情况：因为循环里更新左/右边界的判断条件是只有当nums[mid]等于目标值时才更新，由于目标值不在数组中，所以循环结束后根本不会更新左/右边界。
public int[] searchRange(int[] nums, int target) { int left=0,right=nums.length; int l_Idx=getl_Idx(left,right,nums,target); int r_Idx=getr_Idx(left,right,nums,target); if(l_Idx==-1){ return new int[] {-1,-1}; } return new int[] {l_Idx,r_Idx}; } //找左边界 public static int getl_Idx(int left,int right,int[] nums,int target){ int l_Idx=-1; while(left<right){ int mid = left+(right-left)/2; if(nums[mid]>target){ right=mid; }else if(nums[mid]<target){ left=mid+1; }else{ right=mid; l_Idx=right; } } return l_Idx; } //找右边界 public static int getr_Idx(int left,int right,int[] nums,int target){ int r_Idx=-1; while(left<right){ int mid = left+(right-left)/2; if(nums[mid]>target){ right=mid; }else if(nums[mid]<target){ left=mid+1; }else{ left=mid+1; r_Idx=left-1; } } return r_Idx; }
4）69. x 的平方根
-
思路一：二分法
public int mySqrt(int x) { int left=0,right=x;//右闭 while(left<=right){ int mid=left+(right-left)/2; //不能直接用mid*mid，会超int范围。 long result=(long)mid*mid; if(result>x){ right=mid-1; }else if(result<x){ left=mid+1; }else{ return mid; } } return right; } - 思路二：牛顿迭代法
5）367.有效的完全平方数
这道题跟lc69有点类似，思路差不多。
public boolean isPerfectSquare(int num) {
int left=1,right=num;
while(left<=right){
int mid=(left+right)/2;
long result=(long)mid*mid;
if(result>num){
right=mid-1;
}else if(result<num){
left=mid+1;
}else{
return true;
}
}
return false;
}
★不使用long处理：用除法，判断余数：
class Solution {
public boolean isPerfectSquare(int num) {
int left=1,right=num;
while(left<=right){
int mid = left+(right-left)/2;
if(num/mid>mid){
left=mid+1;
}else if(num/mid<mid){
right=mid-1;
}else{
//是完全平方数
if(num%mid==0){
return true;
}
//★因为/是向下取整，所以num/mid==mid但有余数的话，说明mid*mid<num，相当于num/mid>mid
left=mid+1;
}
}
return false;
}
}
2.双指针法
（1）什么是双指针法？
通过 快指针 和 慢指针 在一个for循环下完成两个for循环 的工作。
双指针法（快慢指针法）在数组和链表的操作中非常常见，很多数组、链表、字符串等操作题都使用双指针法。
（2）相关题目推荐
1）27. 移除元素
-
思路一：双指针法。
class Solution { public int removeElement(int[] nums, int val) { int j=0; for(int i=0;i<nums.length;i++){ if(nums[i]!=val){ nums[j]=nums[i]; j++; } } return j; } }【tips】最坏的情况是数组中没有val，这时需要i和j都遍历一遍数组。
-
思路二：双指针优化——相向双指针法：如果要移除的元素恰好在数组的开头，例如序列 [1,2,3,4,5]，当 val 为 1 时，我们需要把每一个元素都左移一位。题目中说元素的顺序可以改变，实际上我们可以直接将最后一个元素5移动到序列开头，取代元素 1，得到序列 [5,2,3,4]，同样满足题目要求。 如果左指针left 指向的元素等于val，此时将right 指向的元素复制到left 的位置，然后right 左移一位。如果赋值过来的元素恰好也等于val，可以继续把right 指向的元素的值赋值过来（left 指向的等于val 的元素的位置继续被覆盖），直到左指针指向的元素的值不等于 val 为止。
public int removeElement(int[] nums, int val) { int left=0,right=nums.length-1; while(left<=right){ if(nums[left]==val){ nums[left]=nums[right]; //这里left不能右移，因为赋过来的nums[right]也可能==val。如果把等于val的nums[right]赋过来了也不要紧，让right左移 //，下次再把下一个nums[right]赋过来就行了，直到把不等于val的nums[right]赋给nums[left] right--; }else{//只有当nums[left]!=val时，left才右移 left++; } } return left; }
2）26.删除排序数组中的重复项
- 思路一：判断nums[fast]与nums[fast+1]是否相等，但是会出现索引越界。
-
思路二：除去空数组和长度为1的数组，判断判断nums[fast]与nums[fast-1]是否相等，这样就避免了索引越界的情况。具体实现：当nums[fast]与nums[fast-1]相等时，右移fast；不相等时，将nums[fast]赋给nums[slow]，右移fast和slow。最终得到的slow就是目标数组的长度。一定要记住slow是目标数组中将要被赋值的位置，所以最后返回的数组长度不用+1了。
public int removeDuplicates(int[] nums) { //因为是有序数组，所以无论前两个元素是否相等，目标数组的第一个元素一定是旧数组的第一个元素，因此不需要给目标数组的第一个位置赋值 //，直接从第二个位置(下标1)开始赋值。 int slow=1; //为避免[fast-1]时索引越界，先处理空数组和长度为1的数组 if(nums.length < 2){ return nums.length; } for(int fast=1;fast<nums.length;fast++){ if(nums[fast]!=nums[fast-1]){ nums[slow++]=nums[fast]; } } return slow; }
3）★283.移动零
-
思路一：采用双指针，先找0将其覆盖，再将数组尾部补0。
public void moveZeroes(int[] nums) { //因为要保持非零元素的相对顺序，所以不能用相向双指针法 int slow=0,fast=0; //将非零元素按相对顺序前移 while(fast<=nums.length-1){ if(nums[fast]!=0){ nums[slow]=nums[fast]; slow++; } fast++; } //将零元素放到数组最后 for(int i=slow;i<=nums.length-1;i++){ nums[i]=0; } }【tips】优点：每个位置都只需要赋值一次即可；缺点：当数组是[0 0 0 ... 0 1]时，需要对每个零都赋值一次。
-
思路二：官方题解双指针法，基于交换元素，slow指向当前已经处理好的数组无零部分的尾部，fast指向数组待处理部分的头部。fast指针不断向右移动，每次fast指向非零元素，则将两指针对应的数交换，同时slow指针右移。注意两个指针始终保持如下性质，所以每次交换，都是将slow指向的零与fast指向的非零数交换，且非零数的相对顺序不改变。
- slow左边不含零
-
fast左边到slow处全是零
public void moveZeroes(int[] nums) { int slow=0,fast=0; while(fast<=nums.length-1){ if(nums[fast]!=0){ swap(nums,fast,slow); slow++; } fast++; } } public void swap(int[] nums,int fast,int slow){ int temp=nums[fast]; nums[fast]=nums[slow]; nums[slow]=temp; }【tips】这种做法的优点解决了思路一的缺点，当[0 0 0 ... 0 1]时只需要一次交换即可。但同时缺点是每次交换需要三次赋值。
4）★★844.比较含退格的字符串
-
思路：由于遇#会删除#前的字符，所以某字符是否被删除只取决于其后是否为#，因此考虑倒序遍历字符串，这样若遇#，则下一次字符直接跳过。 具体实现：
-
1.先判断是否遇到#并用sDel和tDel表示需要删除的元素个数：
- （1）遇#：sDel++，指针前移；
-
（2）不遇#：
- 1）且sDel>0（即需要删除元素）：sDel--,指针前移
- 2）且不需要删除元素：后半部分消除#和删除元素结束
-
2.判断元素是否相等：
-
（1）若两字符串都没遍历完：
- 1）若元素不等，返回false；
- 2）若元素相等，继续下一轮遍历
- （2）★若任一字符串遍历完，另一个未遍历完：必为false
-
（1）若两字符串都没遍历完：
-
3.若两字符串都遍历完，说明两字符串相同，返回true
public boolean backspaceCompare(String s, String t) { int sLen=s.length(); int tLen=t.length(); //待删除元素个数 int sDel=0; int tDel=0; //★同时倒序遍历s和t for(int i=sLen-1,j=tLen-1;i>=0||j>=0;i--,j--){//★注意j前面不用加int!!! //s字符串，一次性找#并删除元素，直到指针到头或不需要删除元素为止 while(i>=0){ //如果==#，待删除个数+1，指针前移(★因为是一次性找#，所以记得指针前移！！！) if(s.charAt(i)=='#'){ sDel++; i--; }else if(sDel>0){ //不等于#，分两种情况 //待删除个数大于0，需要前移(代表了删除元素) i--; sDel--; }else{ //不需要删除元素，直接跳出while，继续向下执行，准备进行下次处理 break; } } //t字符串 while(j>=0){ if(t.charAt(j)=='#'){ tDel++; j--; }else if(tDel>0){ j--; tDel--; }else{ break; } } //两个字符串都没遍历到头 if(i>=0&&j>=0){ if(s.charAt(i)!=t.charAt(j)){ return false; } }else if(i>=0||j>=0){//两个字符串其中一个遍历到头，另一个没到头，一定不相等 return false; } } return true; }
-
1.先判断是否遇到#并用sDel和tDel表示需要删除的元素个数：
★【tips】两个字符串都没遍历到头(i>=0&&j>=0)的else是【两个字符串都遍历到头了 —— i<0&&j<0】或【一个到头一个没到头 —— i>=0||j>=0】，而【两个字符串都遍历到头了】相当于大的for循环结束，直接返回true；【一个到头一个没到头】才是我们要判断的false的情况，所以最后是else if(i>=0||j>=0)，而不是直接else就return false。
5）977.有序数组的平方
-
思路：数组是非递减有序的，因此左边的负数平方后可能成右边的大数，那么对于初始数组来说，平方后最大的数只能在数组两端而不可能在中间，因此考虑双指针法，i,j分别指向起始和终止位置，再定义一个新数组，让指针k指向终止位置，比较i,j所指元素平方的大小，大的放进k指位置，大的和k移动一位。
public int[] sortedSquares(int[] nums) { int left=0,right=nums.length-1; //平方数组 int[] rsltNums=new int[nums.length]; //始终指向平方数组待插入位置 int k=nums.length-1; while(left<=right){ int rsltL=nums[left]*nums[left]; int rsltR=nums[right]*nums[right]; //比较左右指针所指元素的平方，大的放到平方数组，对应指针移动，k左移 if(rsltL>rsltR){ rsltNums[k]=rsltL; k--; left++; }else{ rsltNums[k]=rsltR; k--; right--; } } return rsltNums; }
3.滑动窗口
（1）什么是滑动窗口？
滑动窗口就是不断调节子序列的起始位置和终止位置，从而得出我们要想的结果。
可以发现滑动窗口也可以理解为双指针法的一种，只不过这种解法更像是一个窗口的移动，所以叫做滑动窗口更适合一些。在滑动窗口类型的问题中都会有两个指针，一个用于“延伸”现有窗口的右指针，和一个用于“收缩”窗口的左指针。
在解题时要注意以下几点：
- 明确窗口内是什么
- 注意窗口起始和终止位置的移动规则
- 注意移动窗口时，是否需要对匹配条件进行处理，比如左边滑出去的元素需不需要减掉等
- 临时窗口长度可以用right和left来表示，具体要不要+1取决于右指针；
（2）相关题目推荐
1）209.长度最小的子数组
-
思路：移动窗口右指针(终止位置)，计算窗口内元素之和来匹配目标值：
- 和小于目标值：继续移动右指针
-
和大于等于目标值：判断本次临时窗口长度与最终窗口长度大小：
- 临时窗口长度小：更新最终窗口长度和下次窗口内元素的初始和
- 最终窗口长度小：更新下次窗口内元素的初始和
-
没更新rsltLen，说明没有符合要求的连续子串，返回0
public int minSubArrayLen(int target, int[] nums) { int left=0,right=0; int sum=0; int rsltLen=Integer.MAX_VALUE;//记录最终窗口的长度，初始值给一个int型最大值。 //这里rsltLen初始值也可以给nums.length+1; //int tempLen=0;//记录临时窗口的长度 //临时窗口的长度可以用左右指针来表示：tempLen=right-left+1; while(right<nums.length){ sum+=nums[right]; //tempLen++; while(sum>=target){ /*这段代码的意思就是获取两数中的最小值，可以直接用Math.min(a,b)来代替这个if判断 //比较本次临时窗口长度和最终窗口长度 //临时窗户长度小，更新最终窗口长度和下次窗口内元素的初始和 if(tempLen<rsltLen){ rsltLen=tempLen; } */ rsltLen=Math.min(rsltLen,right-left+1); //临时窗口长度大，更新下次窗口内元素的初始和 //因为无论哪个窗口长度小，都需要更新下次窗口内元素的初始和，所以直接把这部分操作拿出来就行 sum-=nums[left]; left++;//滑动窗口 } right++; } //没更新rsltLen，说明没有符合要求的连续子串，返回0 if(rsltLen == Integer.MAX_VALUE){ return 0; } return rsltLen; }
2）★904. 水果成篮
-
思路：移动窗口右指针，根据下一个数是否在两个篮子里来进行操作：
- 下一个数在两个篮子里：要放，更新临时窗口的长度(水果的数量)和最终长度
-
★下一个数不在两个篮子里：移动左指针到第一次出现篮子1中的数的位置，更新两个篮子中的数，更新临时窗口的长度和最终长度
public int totalFruit(int[] fruits) { int left=0; //记录篮子里的数字 //这里不要纠结篮子2的初始值，直接等于fruits[0]。因为第一次遇到篮子2的数时的操作与之后遇到新数字(既不在篮子1也不在篮子2)的操作一样。 int basket1=fruits[0],basket2=fruits[0]; //因为题目说最少一棵树，所以最终结果一定大于等于1 int rsltLen=1; //循环索引从1开始，如果只有1棵树，不走循环直接return rsltLen(等于1，这也是为什么int rsltLen=1！) for(int right=1;right<fruits.length;right++){ //如果是篮子中的水果 if(fruits[right]==basket1 || fruits[right]==basket2){ //更新临时窗口长度和最终长度 int tempLen=right-left+1; rsltLen=Math.max(rsltLen,tempLen); }else{//如果不是篮子中的水果(同时考虑到了第一次遇到篮子2的情况) //★将左指针移到右指针前一位，但这并不是左指针最终位置 left=right-1; //更新两个篮子中的数字 basket1=fruits[left]; basket2=fruits[right]; //★寻找左指针最终位置：这里left>=1很关键！防止left=0时left-1=-1的指针越界 while(left>=1 && fruits[left-1]==basket1){ left--; } //更新临时窗口长度和最终长度 //★这里为什么还要更新呢？因为basket2初始值等于fruits[0]，考虑[1,2]的情况，如果不更新，结果就是1了。 int tempLen=right-left+1; rsltLen=Math.max(rsltLen,tempLen); } } return rsltLen; }【tips】①让basket2初始等于第一个数，此时要注意找到左指针最终位置后也要更新临时窗口长度和最终长度。②注意当left=0时left-1的索引越界问题。
3）★★76.最小覆盖子串
-
思路：在 s 上滑动窗口，通过右移right不断扩张窗口。当窗口包含 t 全部所需的字符后，再判断左边是否能收缩，如果能收缩就收缩窗口直到得到最小窗口(即最小覆盖子串)。同时本题要注意两点：
- 题目已告知所求最小覆盖子串唯一
- t中可以有重复字符，如 t=AABC
-
如何判断s的子串包含了t中的所有字符呢？
我们利用两个数组(字符频数数组)need和have，分别记录t中所有字符出现的次数，以及t中各字符在s的子串中出现的次数。所谓"s的子串包含t中所有字符"就是have中各字符的次数大于等于need中对应的各字符的次数。
我们可以挨个比较 s 和 t 中字符出现的次数的大小关系，从而判断 s 的子串是否包含 t 。但这样做太麻烦了，我们可以定义一个count(编辑距离)来表示滑动窗口中 t 字符的个数，当 count 等于 t 的长度时，说明滑动窗口包含(覆盖)了 t (此时还不是最小覆盖)。public String minWindow(String s, String t) { int sLen=s.length(),tLen=t.length(); int left=0,right=0;//代表滑动窗口的左右边界 int[] need=new int[128];//用来记录t中各字符出现的次数 int[] have=new int[128];//用来记录t中各字符在滑动窗口中出现的次数 int rsltLen=sLen+1; int count=0;//记录滑动窗口中出现t中字符的总次数 int start=0;//记录子串起始位置，再加上子串长度，就可以substring得到子串 //记录t中各字符出现的次数 for(int i=0;i<tLen;i++){ need[t.charAt(i)]++; } while(right<sLen){ //先处理右边界 char rChar=s.charAt(right); //如果rChar不在t中，右边界右移，继续下次循环 if(need[rChar]==0){ right++; continue; } //rChar在t中 //且如果rChar在s中出现的次数小于在t中出现的次数，count++，右边界右移，更新rChar在窗口中出现的次数 if(have[rChar]<need[rChar]){ count++; } //且如果rChar在s中出现的次数大于等于在t中出现的次数，右边界右移，更新rChar在窗口中出现的次数 right++; have[rChar]++; //当滑动窗口中出现t中字符的总次数等于t的长度，即滑动窗口中包含了t中所有字符时，处理左边界 while(count==tLen){ char lChar=s.charAt(left); //★更新rsltLen和子串起始位置 if(right-left<rsltLen){//因为right始终指向下一个待处理位置，所以窗口长度是right-left，不需要+1。 rsltLen=right-left; start=left; } //如果lChar不在t中，直接左边界右移，更新lChar在窗口中出现的次数 if(need[lChar]==0){ left++; have[lChar]--; continue; } //lChar在t中 //且lChar在s中出现的次数已经等于在t中出现的次数，此时就是符合要求的最小子串(但不是最终的最小子串) //这时移动左边界后就不满足覆盖t了 if(have[lChar]==need[lChar]){ count--; } //且lChar在s中出现的次数不等于在t中出现的次数，无论大于还是等于都不符合"最小覆盖"的要求，因此都要右移左边界，并更新have left++; have[lChar]--; } } //rsltLen未更新或s比t短，说明s中无法包含t，直接返回空字符串 if(rsltLen==sLen+1||sLen<tLen){ return ""; } return s.substring(start,start+rsltLen); }
4.螺旋矩阵/顺时针打印
（1）题目类型
这类题不涉及算法，主要是模拟螺旋或者顺时针的过程，在此期间要注意边界条件的判断。
要注意，题目中给出的全是方阵还是允许有非方阵。
要注意，题目中给出的全是方阵还是允许有非方阵。
（2）相关题目推荐
1）59. 螺旋矩阵 II
-
思路一：全是方阵。单纯模拟螺旋的过程，每次模拟时始终把握住“循环不变量”原则，这道题我们采用左闭右开，同时要注意边界的判断条件。
public int[][] generateMatrix(int n) { int[][] matrix=new int[n][n]; int circle=n/2;//一共需要转的圈数，如果是n奇数的话转完后剩中间一个数要单独处理 int len=n-1;//每次模拟时边长的长度，因为我们按照每次左闭右开的规则来模拟，所以第一次模拟的边长长度是n-1而不是n。 int num=1;//要填的数，从1到n方 int startX=0,startY=0;//每次模拟边长的起始位置 int end=0;//下行和左列的终止位置 //一圈一圈的模拟，每边左闭右开 while(circle>0){//circle==0表示已经转完了，所以不能让circle等于0 //模拟上行，左闭右开 while(startX<len){ matrix[startY][startX]=num++; startX++; } //模拟右列 while(startY<len){ matrix[startY][startX]=num++; startY++; } //模拟下行 while(startX>end){ matrix[startY][startX]=num++; startX--; } //模拟左列 while(startY>end){ matrix[startY][startX]=num++; startY--; } circle--; //每次循环完每个边长少两个点 len--; end++; //★第二圈开始的时候起始位置要各加1，因为这个螺旋其实是每一圈都在缩小的螺旋 startX++; startY++; } //★n是奇数，需要对中间单独赋值n方 if(n%2==1){ matrix[n/2][n/2]=n*n; } return matrix; } -
思路二(推荐)：分为上下左右四个边界，通过缩小边界不断缩小螺旋。
public int[][] generateMatrix(int n) { int[][] matrix=new int[n][n]; int num=1; //★定义上下左右边界初始位置 int top=0,bottom=n-1,left=0,right=n-1; //★使用num<=n*n而不是l<r || t<b作为迭代条件，是为了解决当n为奇数时，矩阵中心数字无法在迭代过程中被填充的问题。 while(num<=n*n){ /*几个细节： 1. i代表第i行，j代表第j列 2. 对于变量的边界怎么定义： 从左向右填充：填充的列(列变用j)肯定在[left,right]区间 从上向下填充：填充的行(行变用i)肯定在[top,bottom]区间 从右向左填充：填充的列肯定在[right,left]区间 从下向上填充：填充的行肯定在[bootom,top]区间 ★通过上面的总结会发现【边界的起始和结束与填充方向是对应的】 */ //从左到右填充 for(int j=left;j<=right;j++){ matrix[top][j]=num++; } //填充完，缩小top边界 top++; //从上到下填充 for(int i=top;i<=bottom;i++){ matrix[i][right]=num++; } //填充完，缩小right边界 right--; //从右到左填充 for(int j=right;j>=left;j--){ matrix[bottom][j]=num++; } //填充完，缩小bottom边界 bottom--; //从下到上填充 for(int i=bottom;i>=top;i--){ matrix[i][left]=num++; } //填充完，缩小left边界 left++; } return matrix; }
2）54. 螺旋矩阵剑指
-
思路：采用缩小边界的思路。注意由于所给矩阵可能是非方阵，边长长度两两不同，所以在取每条边界的元素之前都需要判断矩阵中的元素是否已经被取完了。
//lc54 public List<Integer> spiralOrder(int[][] matrix) { List<Integer> rslt=new ArrayList<Integer>(); //列数，行数 int xLen=matrix[0].length,yLen=matrix.length; //初始化上下左右边界的【初始位置】 int t=0,b=yLen-1,l=0,r=xLen-1; //最终集合的长度 int rsltLen=xLen*yLen; while(rslt.size()<rsltLen){ //★由于所给矩阵可能是非方阵，边长长度两两不同，所以在取每条边界的元素之前都需要判断矩阵中的元素是否已经被取完了 //从左到右取元素 for(int j=l;j<=r&&rslt.size()<rsltLen;j++){ rslt.add(matrix[t][j]); } //缩小上边界 t++; //从上到下填充 for(int i=t;i<=b&&rslt.size()<rsltLen;i++){ rslt.add(matrix[i][r]); } //缩小右边界 r--; //从右到左填充 for(int j=r;j>=l&&rslt.size()<rsltLen;j--){ rslt.add(matrix[b][j]); } //缩小下边界 b--; //从下到上填充 for(int i=b;i>=t&&rslt.size()<rsltLen;i--){ rslt.add(matrix[i][l]); } //缩小左边界 l++; } return rslt; }
3）剑指offer29. 顺时针打印矩阵
-
思路：这道题跟上面的题相同，唯一不同点是前者数组不为空，后者可能给个空数组，要注意判断并返回空数组
public int[] spiralOrder(int[][] matrix) { //行数 int yLen=matrix.length; if(yLen==0){ return new int[0]; } //列数 int xLen=matrix[0].length; //输出数组的长度，即要打印的数字个数 int rsltLen=xLen*yLen; //输出数组 int[] rslt=new int[rsltLen]; //初始化上下左右边界的【初始位置】 int t=0,b=yLen-1,l=0,r=xLen-1; //输出数组的索引下标 int index=0; //★用 rsltLen>0 而不是用index+1<rsltLen作循环条件，面对奇数边方阵(如三阶方阵)可以不用单独处理中间元素。 while(rsltLen>0){ //★由于所给矩阵可能是非方阵，边长长度两两不同，所以在取每条边界的元素之前都需要判断矩阵中的元素是否全打印完了 //从左到右取元素 for(int j=l;j<=r&&rsltLen>0;j++){ rslt[index]=matrix[t][j]; index++; rsltLen--; } //缩小上边界 t++; //从上到下填充 for(int i=t;i<=b&&rsltLen>0;i++){ rslt[index]=matrix[i][r]; index++; rsltLen--; } //缩小右边界 r--; //从右到左填充 for(int j=r;j>=l&&rsltLen>0;j--){ rslt[index]=matrix[b][j]; index++; rsltLen--; } //缩小下边界 b--; //从下到上填充 for(int i=b;i>=t&&rsltLen>0;i--){ rslt[index]=matrix[i][l]; index++; rsltLen--; } //缩小左边界 l++; } return rslt; }
查看3道真题和解析
