黎平网站开发,室内设计学校哪个好,网站建设前期费用,在郑州做网站目录 一. 反转字符串中的单词思路和代码#xff1a;I. 博主的做法II. 东哥的做法III. 其他做法1补充知识点#xff1a; IV. 其他做法2 二. 旋转图像思路和代码#xff1a;I. 博主的做法II. 东哥的做法 三. 旋转图像#xff08;逆时针旋转90#xff09;思路和代码#xff… 目录 一. 反转字符串中的单词思路和代码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();// 正则匹配连续的空白字符作为分隔符分割ListString 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来存单词DequeString 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 ListInteger spiralOrder(int[][] matrix) {int top 0, left 0, right matrix[0].length-1, bottom matrix.length-1;ListInteger 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. 东哥的做法
和博主想的一样设置四个边界
ListInteger 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;ListInteger 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/
