目录
- 一. 反转字符串中的单词
- 思路和代码:
- I. 博主的做法
- II. 东哥的做法
- III. 其他做法1
- IV. 其他做法2
- 二. 旋转图像
- 思路和代码:
- I. 博主的做法
- II. 东哥的做法
- 三. 旋转图像(逆时针旋转90°)
- 思路和代码:
- I. 博主和东哥的做法
- 四. 矩阵的螺旋遍历
- 思路和代码:
- I. 博主的做法
- II. 东哥的做法
- 五. 构建螺旋矩阵
- 思路和代码:
- I. 博主的做法
- II. 东哥的做法
一. 反转字符串中的单词
- 题目链接: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)
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/