数组题目总结 -- 花式遍历

一. 反转字符串中的单词

• 题目链接：https://leetcode.cn/problems/reverse-words-in-a-string/

思路和代码：

I. 博主的做法

• 先用trim()方法把字符串前后的多余空格全部去掉。
• 再用replaceAll(“\\s+”, " ")；把多个空格替换成一个空格，\s代表空格，+代表多个。
• 用split以空格为标志，切分字符串，放到字符串数组中。
• 之后使用StringBuffer反向存储。

class Solution {public String reverseWords(String s) {s = s.trim().replaceAll("\\s+", " ");String[] temp = s.split(" ");StringBuffer stb = new StringBuffer();for(int i = temp.length-1; i > 0; i--){stb.append(temp[i] + " ");}stb.append(temp[0]);return stb.toString();}
}

• 申请了额外的空间，原地反转，博主不会，，，
• 时间复杂度：O(n)
• 空间复杂度：O(n)

II. 东哥的做法

• 先反转整个字符串。
• 然后反转每一个单词。
  

class Solution {public StringBuilder trimSpace(String s){int left = 0, right = s.length()-1;//去除开头和结尾的空格while(left <= right && s.charAt(left) == ' ')left++;while(left <= right && s.charAt(right) == ' ')right--;//去除字符串中间的空格StringBuilder stb1 = new StringBuilder();while(left <= right){if(s.charAt(left) != ' ')stb1.append(s.charAt(left));else if(stb1.charAt(stb1.length()-1) != ' ')stb1.append(s.charAt(left));left++;}return stb1;}//写的挺巧妙的反转函数，可以积累public void reverse(StringBuilder stb, int left, int right){while (left < right) {char temp = stb.charAt(left);stb.setCharAt(left++, stb.charAt(right));   stb.setCharAt(right--, temp);}}public void reverseWord(StringBuilder stb){int start = 0, end = 0;while(start < stb.length()){while(end < stb.length() && stb.charAt(end) != ' ')end++;reverse(stb, start, end-1);//寻找下一个单词start = end + 1;end++;} }//总函数public String reverseWords(String s) {StringBuilder stb = trimSpace(s);//StringBuilder 不用再加返回值，直接就在原地操作了reverse(stb, 0, stb.length()-1);reverseWord(stb);return stb.toString();}
}

• StringBuilder一定要定义在循环外面，循环里面的属于临时变量，外面的函数是调用不了的。
• 如果是StringBuilder，就不用再有返回值，因为StringBuilder是可变的，而java中String是不可变的，需要额外申请空间进行操作。C++中，String是可变的，所以空间复杂度能降到O(1)，不需要额外申请空间。
• 时间复杂度：O(n)
• 空间复杂度：O(n)

III. 其他做法1

• 去除开头和末尾的空格。
• 运用正则表达式将字符串分成一个一个的单词（用一个或者多个空格当做分隔符），返回的数组转换成List。
• 反转List，相当于将单词的顺序做一个反转。
• 将空格加入到List当中。

class Solution {public String reverseWords(String s) {// 除去开头和末尾的空白字符s = s.trim();// 正则匹配连续的空白字符作为分隔符分割List<String> wordList = Arrays.asList(s.split("\\s+"));Collections.reverse(wordList);return String.join(" ", wordList);}
}

• 时间复杂度：O(n)
• 空间复杂度：O(n)

补充知识点：

• 在Java 8及以上版本中，String.join()方法最后一个参数可以传入任何对象类型的可迭代集合.
• 可迭代集合就是实现Iterable接口的集合，看下图：
  
• 需要注意的是：Java中数组也实现了Iterable接口，也就是，数组也可以通过join方法，返回字符串。

IV. 其他做法2

• 去掉头尾两头的空格
• 将字符串加入双端队列的头部或者直接加入栈中，如下图：
  

class Solution {public String reverseWords(String s) {int left = 0, right = s.length()-1;//去掉前后两头的空格while(left <= right && s.charAt(left) == ' ')left++;while(left <= right && s.charAt(right) == ' ')right--;//使用双端队列存字符串，使用StringBuilder来存单词Deque<String> deque = new ArrayDeque<>();StringBuilder stb = new StringBuilder();while(left <= right){//如果StringBuilder中不为空（单词存在），并且遇到下一个空格了，就从头部加入双端队列并清空StringBuilderif(stb.length() != 0 && s.charAt(left) == ' '){deque.offerFirst(stb.toString());stb.setLength(0);}else if(s.charAt(left) != ' ')stb.append(s.charAt(left));left++;}//记得加入最后一个单词，因为遇不到下一个空格了！！！   deque.offerFirst(stb.toString());return String.join(" ", deque);}
}

• 时间复杂度：O(n)
• 空间复杂度：O(n)

二. 旋转图像

• 题目链接：https://leetcode.cn/problems/rotate-image/

思路和代码：

I. 博主的做法

• 博主只能想到一圈一圈的进行迭代数组。。。太复杂了。

II. 东哥的做法

• 先将矩阵沿对角线，做对称矩阵操作

• 对矩阵的每一行进行反转
  
  

class Solution {//以对角线对称交换矩阵public void symmetry(int[][] matrix){for(int i = 0; i < matrix.length; i++)for(int j = 0; j < i; j++){int temp = matrix[i][j];matrix[i][j] = matrix[j][i];matrix[j][i] = temp;}}//将每一行进行反转public void reverse(int[] num){int left = 0, right = num.length-1;while(left <= right){int temp = num[left];num[left++] = num[right];num[right--] = temp;}}public void rotate(int[][] matrix) {symmetry(matrix);for(int[] n : matrix)reverse(n);}
}

• 常规的思路就是去寻找原始坐标和旋转后坐标的映射规律，但我们是否可以让思维跳跃跳跃，尝试把矩阵进行反转、镜像对称等操作，可能会出现新的突破口。
• 仔细想想，旋转二维矩阵的难点在于将「行」变成「列」，将「列」变成「行」，而只有按照对角线的对称操作是可以轻松完成这一点的，对称操作之后就很容易发现规律了。

三. 旋转图像（逆时针旋转90°）

• 题目链接：无。
• 函数名： public void rotate(int[][] matrix){ }

思路和代码：

I. 博主和东哥的做法

• 和上一道题真的很像，就是沿着另一条对角线旋转，然后反转每一行。
  

package 洛谷;import java.util.Scanner;public class Test {//沿逆对角线进行对称public static void romate(int[][] matrix){for(int i = 0; i < matrix.length; i++)for(int j = 0; j < matrix.length-i; j++){int temp = matrix[i][j];matrix[i][j] = matrix[matrix.length - 1 - j][matrix.length - 1 - i];matrix[matrix.length - 1 - j][matrix.length - 1 - i] = temp;}}//每行进行反转public static void reverse(int[] matrix){int left = 0, right = matrix.length-1;while(left <= right){int temp = matrix[left];matrix[left++] = matrix[right];matrix[right--] = temp;}}//主函数public static void main(String[] args){Scanner sc = new Scanner(System.in);int[][] a = {{1,2,3,4}, {5,6,7,8}, {7,6,5,4},{4,1,2,3}};romate(a);for(int[] num : a)reverse(num);for(int i = 0; i < a.length; i++){for(int j = 0; j < a.length; j++)System.out.print(a[i][j] + " ");System.out.println();}}}

• 顺逆对角线对称的逻辑还是不太会，仍需加强

四. 矩阵的螺旋遍历

• 题目链接：https://leetcode.cn/problems/spiral-matrix/

思路和代码：

I. 博主的做法

• 设置4个边界，然后模拟顺序输出的样子，进行遍历

class Solution {public List<Integer> spiralOrder(int[][] matrix) {int top = 0, left = 0, right = matrix[0].length-1, bottom = matrix.length-1;List<Integer> list = new ArrayList<>();while(left <= right && top <= bottom){for(int j = left; top <= bottom && j <= right; j++)list.add(matrix[top][j]);top++;for(int i = top; left <= right && i <= bottom; i++)list.add(matrix[i][right]);right--;for(int j = right; top <= bottom && j >= left; j--)list.add(matrix[bottom][j]);bottom--;for(int i = bottom; left <= right && i >= top; i--)list.add(matrix[i][left]);left++;}return list;}
}

• 这一行写成：for(int j = left; left <= right && j <= right; j++)，这显然是错的，j <= right已经判断过了；其次，如果上下都是负的空间，左右又有什么意义呢？？
• 还需要注意，螺旋输出，没拐个弯，对应的边界就要多走一格子。
• 列的个数一定是matrix[0].length - 1，行的个数是matrix.length

II. 东哥的做法

• 和博主想的一样，设置四个边界

List<Integer> spiralOrder(int[][] matrix) {int m = matrix.length, n = matrix[0].length;int upper_bound = 0, lower_bound = m - 1;int left_bound = 0, right_bound = n - 1;List<Integer> res = new LinkedList<>();// res.size() == m * n 则遍历完整个数组while (res.size() < m * n) {if (upper_bound <= lower_bound) {// 在顶部从左向右遍历for (int j = left_bound; j <= right_bound; j++) {res.add(matrix[upper_bound][j]);}// 上边界下移upper_bound++;}if (left_bound <= right_bound) {// 在右侧从上向下遍历for (int i = upper_bound; i <= lower_bound; i++) {res.add(matrix[i][right_bound]);}// 右边界左移right_bound--;}if (upper_bound <= lower_bound) {// 在底部从右向左遍历for (int j = right_bound; j >= left_bound; j--) {res.add(matrix[lower_bound][j]);}// 下边界上移lower_bound--;}if (left_bound <= right_bound) {// 在左侧从下向上遍历for (int i = lower_bound; i >= upper_bound; i--) {res.add(matrix[i][left_bound]);}// 左边界右移left_bound++;}}return res;
}

• 思路是一样的，大家看着哪个顺眼参考哪个

五. 构建螺旋矩阵

• 题目链接：https://leetcode.cn/problems/spiral-matrix-ii/

思路和代码：

I. 博主的做法

• 跟上个题几乎是一模一样，只是在每次循环当中进行的操作不同而已。

class Solution {public int[][] generateMatrix(int n) {int[][] matrix = new int[n][n];int top = 0, left = 0, right = n-1, bottom = n-1;int num = 1;while(top <= bottom && left <= right){for(int j = left; top <= bottom && j <= right; j++)//这里不一样，下面同理matrix[top][j] = num++;top++;for(int i = top; left <= right && i <= bottom; i++)matrix[i][right] = num++;right--;for(int j = right; top <= bottom && j >= left; j--)matrix[bottom][j] = num++;bottom--;for(int i = bottom; left <= right && i >= top; i--)matrix[i][left] = num++;left++;}return matrix;}
}

• 时间复杂度：O(n^2)，其中 n 是给定的正整数。矩阵的大小是 n×n，需要填入矩阵中的每个元素。
• 空间复杂度：O(1)，除了返回的矩阵以外，空间复杂度是常数。

II. 东哥的做法

• 和博主想的一样，设置四个边界

int[][] generateMatrix(int n) {int[][] matrix = new int[n][n];int upper_bound = 0, lower_bound = n - 1;int left_bound = 0, right_bound = n - 1;// 需要填入矩阵的数字int num = 1;while (num <= n * n) {if (upper_bound <= lower_bound) {// 在顶部从左向右遍历for (int j = left_bound; j <= right_bound; j++) {matrix[upper_bound][j] = num++;}// 上边界下移upper_bound++;}if (left_bound <= right_bound) {// 在右侧从上向下遍历for (int i = upper_bound; i <= lower_bound; i++) {matrix[i][right_bound] = num++;}// 右边界左移right_bound--;}if (upper_bound <= lower_bound) {// 在底部从右向左遍历for (int j = right_bound; j >= left_bound; j--) {matrix[lower_bound][j] = num++;}// 下边界上移lower_bound--;}if (left_bound <= right_bound) {// 在左侧从下向上遍历for (int i = lower_bound; i >= upper_bound; i--) {matrix[i][left_bound] = num++;}// 左边界右移left_bound++;}}return matrix;
}

参考：
https://labuladong.github.io/algo/di-yi-zhan-da78c/shou-ba-sh-48c1d/er-wei-shu-150fb/
https://leetcode.cn/problems/reverse-words-in-a-string/solution/fan-zhuan-zi-fu-chuan-li-de-dan-ci-by-leetcode-sol/