7.整数反转
利用long来进行中转。
class Solution {
public int reverse(int x) {
long res = 0;
while (x != 0) {
res = res * 10 + x % 10;
x = x/10;
}
return (int)res == res?(int)res : 0;
}
}9. 回文数
解法一
回文数，其实跟回文字符串差不多，只是处理不同而已，我这里就直接将数字转换成了字符串然后对比。
class Solution {
public boolean isPalindrome(int x) {
if(x < 0) return false;
if (x < 10) return true;
String str = String.valueOf(x);
for(int i = 0; i < str.length()/2; i++) {
if(str.charAt(i) != str.charAt(str.length() - 1 - i))
return false;
}
return true;
}
}也可以直接将字符串反转在和原来的字符串相对比，不过效率第一点。
class Solution {
public boolean isPalindrome(int x) {
if(x < 0) return false;
if (x < 10) return true;
String str = String.valueOf(x);
String rev = new StringBuffer(str).reverse().toString();
if(rev.equals(str))
return true;
else
return false;
}
}解法二
直接求出反转后的数字，然后比较是否相等。虽然会有溢出的情况，但是会溢出的就不是回文了，所以可以不用考虑溢出的情况，实在要考虑可以直接来个try-catch来捕获异常。
class Solution {
public boolean isPalindrome(int x) {
if(x < 0) return false;
int rev = 0;
int p = x;
int temp = 0;
while(p!=0){
temp = p % 10;
rev = rev * 10+temp;
p = p/10;
}
return x == rev;
}
}11. 盛最多水的容器
解法一
因为这道题可以不用管中间的高度，所以直接嵌套for循环找出最大面积就好了，不过效率很低。明显看出这是O(n^2)的算法，应该算是效率最差的算法了。
class Solution {
public int maxArea(int[] height) {
int res = Integer.MIN_VALUE;
for(int i = 0; i < height.length; i++) {
for(int j = i; j <height.length; j++) {
if(height[j] <= height[i]) {
int val = height[j] * (j - i);
if(val > res) res = val;
} else {
int val = height[i] * (j - i);
if(val > res) res = val;
}
}
}
return res;
}
}解法二
这题明显可以使用双指针的方法。不断选取高度最高的值，并且长方形面积尽量大。最坏的时间复杂度为O(n)。
class Solution {
public int maxArea(int[] height) {
int i = 0;
int j = height.length - 1;
int res = 0;
while(i < j) {
int val = Math.min(height[i],height[j]) * (j - i);
if (val > res) res = val;
// 选择高度更高的逼急
if(height[i] < height[j]) i++;
else j--;
}
return res;
}
}14.最长公共前缀
最开始是直接两个for循环的，但是看到了别人的解法，只能流出智商低的类水。
class Solution {
public String longestCommonPrefix(String[] strs) {
if(strs.length == 0) return "";
String s = strs[0];
for (String str : strs) {
while(!str.startsWith(s)) {
if (s.length() == 0) return "";
s = s.substring(0,s.length() - 1);
}
}
return s;
}
}20.有效的括号
这经典题目了，直接用栈就可以判断了。
class Solution {
public boolean isValid(String s) {
Stack<Character> stack = new Stack<>();
for(char c : s.toCharArray()) {
if (c == '(') stack.push(')');
else if (c == '[') stack.push(']');
else if (c == '{') stack.push('}');
else if (stack.isEmpty() || c != stack.pop()) return false;
}
return stack.isEmpty();
}
}21. 合并两个有序的链表
这个题因为两个都是有序的连边，所以一个个赋值就可以了。
class Solution {
public ListNode mergeTwoLists(ListNode l1, ListNode l2) {
ListNode pre = new ListNode();
ListNode res = pre;
while(l1 != null && l2 != null) {
if(l1.val >= l2.val) {
pre.next = new ListNode(l2.val);
l2 = l2.next;
} else {
pre.next = new ListNode(l1.val);
l1 = l1.next;
}
pre = pre.next;
}
if(l1 == null) {
pre.next = l2;
}
if(l2 == null) {
pre.next = l1;
}
return res.next;
}
}还有一种递归写法。
class Solution {
public ListNode mergeTwoLists(ListNode l1, ListNode l2) {
if(l1 == null) return l2;
if(l2 == null) return l1;
ListNode res;
if(l1.val > l2.val) {
res = l2;
l2 = l2.next;
} else {
res = l1;
l1 = l1.next;
}
res.next = mergeTwoLists(l1,l2);
return res;
}
}26. 删除排序数组中的重复项
这题考虑的是原地修改数组，那就把这个数组当作一个新的数组就好了，碰到不相同的就放到前面。所以就有了这个算法。
class Solution {
public int removeDuplicates(int[] nums) {
if (null == nums || nums.length == 1) return nums.length;
int res = 1;
for(int i = 1;i < nums.length; i++) {
if(nums[i] != nums[i - 1]) {
nums[res] = nums[i];
res++;
}
}
return res;
}
}46.全排列
看题目就知道，一道典型的全排列的题目，我就用了递归的写法。不过这个写法遇到有重复的数字的时候会有重复的数据，这题没有重复数据所以不需要去重，要是有重复数据可以需要考虑去重。
class Solution {
List<List<Integer>> res = new ArrayList<>();
public List<List<Integer>> permute(int[] nums) {
fun(nums,0);
return res;
}
public void fun(int[] nums,int start) {
if(start == nums.length -1){
List<Integer> list = new ArrayList<>();
for(int i:nums) list.add(i);
res.add(list);
}
for(int i = start;i < nums.length; i++) {
swap(nums,i,start);
fun(nums,start + 1);
swap(nums,i,start);
}
}
public void swap(int[] nums,int i,int j) {
int temp = nums[i];
nums[i] = nums[j];
nums[j] = temp;
}
}53. 最大子序和
这题一开始我用的是双指针逼近，但是发现无法确定逼近的条件，所以就放弃了这个想法。
实在没想出。看了下答案，发现不是题难，是我太菜了。
其实这题用动态规划来解是最好的。
首先确定一下状态，那就是子数组的和最大。
然后是状态变化，因为是求子数组的和最大，所以开头是不可能是负的，如果是正的，但是加了后面的负数也是会抵消。
class Solution {
public int maxSubArray(int[] nums) {
int res = nums[0];
int sum = 0;
for(int num : nums) {
// 状态变化
if(sum > 0) sum += num;
else sum = num;
// 保存状态
res = Math.max(res,sum);
}
return res;
}
}59. 螺旋矩阵 II
这道题以前写过类似的，可以直接一个个的赋值，这题的难点就是边界的判断，在while循环中很容易就超出数组的边界了，或者是转过头了没刹住，注意好边界条件就不难了。
class Solution {
public int[][] generateMatrix(int n) {
int[][] res = new int[n][n];
int count = 1;
int x = 0,y = 0;
res[0][0] = 1;
while(count != n*n) {
// 向右移动
while(y + 1 < n && res[x][y + 1] == 0) {
res[x][y + 1] = ++count;
y++;
}
// 向下移动
while(x + 1 < n && res[x + 1][y] == 0) {
res[x + 1][y] = ++count;
x++;
}
// 向左移动
while(y - 1 >= 0 && res[x][y - 1] == 0) {
res[x][y - 1] = ++count;
y--;
}
// 向上移动
while(x - 1 >= 0 && res[x - 1][y] == 0) {
res[x - 1][y] = ++count;
x--;
}
}
return res;
}
}62. 不同路径
一看题目，直接递归搜索。
class Solution {
public int uniquePaths(int m, int n) {
return dfs(m,n);
}
public int dfs(int x,int y) {
if(x == 1 && y == 1) return 1;
if(x == 1) return dfs(x,y - 1);
if(y == 1) return dfs(x -1,y);
return dfs(x - 1,y) + dfs(x,y - 1);
}
}但是当图大的时候，就不行了，直接超时，所以不能直接搜索了，还要优化才行。因为当x或者y等于一的时候，就只有一条路了，所以可以进行优化一下。
class Solution {
public int uniquePaths(int m, int n) {
return dfs(m,n);
}
public int dfs(int x,int y) {
if(x == 1 || y == 1) return 1;
return dfs(x - 1,y) + dfs(x,y - 1);
}
}但还是超时了，所以直接递归应该是不可行。所以得考虑其他想法了，比如说动态规划。
class Solution {
public int uniquePaths(int m, int n) {
int[][] dp = new int[m][n];
for(int i = 0; i < m; i++) {
for(int j = 0; j < n; j++) {
if(i == 0 || j == 0) dp[i][j] = 1;
else dp[i][j] = dp[i - 1][j] + dp[i][j - 1];
}
}
return dp[m - 1][n - 1];
}
}虽然可以通过了，但是时间和空间的消耗还是挺多的。
看了一下评论区的解法，发现有一个解法就很有想法。那就是用排列组合的方式。
class Solution {
public int uniquePaths(int m, int n) {
int N = m + n -2;
// 因为行列互换答案是一样的，所以直接找最小值使用
int M = Math.min(m-1,n-1);
// 使用int类型就会溢出了，所以要用long类型
long res = 1;
for(int i = 0; i < M; i++) {
// C = N! / (M! + (N -M)!)简化后得到下面这个式子
res = res * (N - i) / (i + 1);
}
return (int)res;
}
}70.爬楼梯
这题的本质就是斐波那契数列。
首先就是dp数组。
class Solution {
public int climbStairs(int n) {
if (n <= 2) return n;
int[] dp = new int[n + 1];
dp[1] = 1;
dp[2] = 2;
for (int i = 3;i < n + 1; i++) {
dp[i] = dp[i - 1] + dp[i - 2];
}
return dp[n];
}
}直接递归，不需要存储状态。
class Solution {
public int climbStairs(int n) {
if (n <= 2) return n;
int a = 1;
int b = 2;
for (int i = 3;i < n + 1; i+=2) {
a = a + b;
b = a + b;
}
if (n % 2 == 0) return b;
else return a;
}
}78. 子集
这题的思路就是遍历数组，遇到新的元素，就把这个元素加到所有子集里，形成新的子集。
class Solution {
public List<List<Integer>> subsets(int[] nums) {
List<List<Integer>> res = new ArrayList<>();
res.add(new ArrayList<>());
for(int i = 0;i < nums.length; i++) {
int size = res.size();
for(int j = 0; j < size; j++) {
List<Integer> list = new ArrayList<>(res.get(j));
list.add(nums[i]);
res.add(list);
}
}
return res;
}
}88. 合并两个有序数组
解法一
直接就把这两个数组合并，然后在排一次序就好了。这应该是最简单，也是最花时间的算法。
class Solution {
public void merge(int[] nums1, int m, int[] nums2, int n) {
int re = 0;
for(int i = m; i < m + n; i++) {
nums1[i] = nums2[re];
re++;
}
Arrays.sort(nums1);
}
}解法二
可以使用类似双指针的方法，选取最大的依次放入数组。
class Solution {
public void merge(int[] nums1, int m, int[] nums2, int n) {
int temp = m + n - 1;
int i = m - 1;
int j = n - 1;
while(i >=0 && j >= 0) {
if(nums1[i] < nums2[j]) {
nums1[temp] = nums2[j];
temp--;
j--;
} else{
nums1[temp] = nums1[i];
temp--;
i--;
}
}
while(j >= 0) {
nums1[temp] = nums2[j];
temp--;
j--;
}
}
}简化之后可以得到。
class Solution {
public void merge(int[] nums1, int m, int[] nums2, int n) {
int temp = m + n - 1;
int i = m - 1;
int j = n - 1;
while(i >=0 && j >= 0) {
nums1[temp--] = nums1[i] < nums2[j] ? nums2[j--] : nums1[i--];
}
while(j >= 0) {
nums1[temp--] = nums2[j--];
}
}
}89. 格雷编码
这题真的不会写了，题目描述的不是很清楚，看的都不是很明白，直接查了维基百科，看懂了格雷码转二进制数的规律之后，就很简单了。
由于G(n) = B(n+1) + B(n)
故而B(n) = -B(n+1)+ G(n)
自高位至低位运算即可，无需考虑借位。
例： 格雷码0111，为4位数，故设二进制数自第5位至第1位分别为：0 b3 b2 b1 b0。
b3= 0-0 =0
b2=b3-1=0-1=1
b1=b2-1=1-1=0
b0=b1-1=0-1=1
因此所转换为之二进制码为0101class Solution {
public List<Integer> grayCode(int n) {
List<Integer> res = new ArrayList<>();
int len = 1<<n;
for(int i = 0; i < len; i++) {
res.add(i ^ i>>1);
}
return res;
}
}136. 只出现一次的数字
这题直接用异或就好了，因为异或运算符和下面这样的规律。
- 异或符和交换律
- n与0异或答案为n
- 两个相同的数异或答案为0
class Solution {
public int singleNumber(int[] nums) {
int res = 0;
for(int i:nums) res ^= i;
return res;
}
}141.环形列表
这题可以先直接遍历，然后判断是否有重复的就好了。
public class Solution {
public boolean hasCycle(ListNode head) {
Set<ListNode> set = new HashSet<>();
ListNode node = head;
while(node != null) {
if (!set.add(node)) return true;
node = node.next;
}
return false;
}
}见到一种很有趣的解法。将每一个的节点指向自己，有环就会出现指向自己的节点。
public class Solution {
public boolean hasCycle(ListNode head) {
if (head == null || head.next == null) return false;
while(head.next != head) {
if (head == null || head.next == null) return false;
ListNode node = head.next;
head.next = head;
head = node;
}
return true;
}
}快慢指针。
public class Solution {
public boolean hasCycle(ListNode head) {
if (head == null || head.next == null) return false;
ListNode slow = head;
ListNode fast = head.next;
while(fast != slow) {
if (fast == null || fast.next == null) return false;
fast = fast.next.next;
slow = slow.next;
}
return true;
}
}142. 环形链表 II
这题和上面的题其实差不多，只是要返回交接的点。
public class Solution {
public ListNode detectCycle(ListNode head) {
if(head == null) return null;
if(head.next == null) return null;
ListNode p1 = head;
ListNode p2 = head;
while(p2.next != null && p2.next.next != null) {
p1 = p1.next;
p2 = p2.next.next;
if(p1 == p2) {
ListNode res = head;
while(res != p1) {
p1 = p1.next;
res = res.next;
}
return res;
}
}
return null;
}
}155. 最小栈
这题直接就是数据结构了，但是不知道会存多少个数字，所以使用了List来当存储数组。
class MinStack {
List<Integer> res = new ArrayList<>();
int min = Integer.MAX_VALUE;
public MinStack() {}
public void push(int x) {
res.add(x);
if(min > x) {
min = x;
}
}
public void pop() {
res.remove(res.size() - 1);
min = Integer.MAX_VALUE;
for(int num:res) {
if(num < min) min = num;
}
}
public int top() {
return res.get(res.size() - 1);
}
public int getMin() {
return min;
}
}题目要求常数时间内检索到最小元素，这个其实没算实现，因为这里获取最小数的时间复杂度加到了pop方法上了，而且这个的效率不是很好。
所以有了下面种写法，用链表的方法，每一个链表都存储一个最小值，这样pop的时候也会自动变更最小值。
class MinStack {
private class ListNode{
int min;
int val;
ListNode next;
public ListNode(int val,int min) {
this.val = val;
this.min = min;
}
public ListNode(int val,int min,ListNode next) {
this.val = val;
this.min = min;
this.next = next;
}
}
private ListNode head;
public void push(int x) {
if(head == null) {
head = new ListNode(x,x);
} else {
// 使用头插，因为尾插不好pop
head = new ListNode(x,x > head.min?head.min:x,head);
}
}
public void pop() {
head = head.next;
}
public int top() {
return head.val;
}
public int getMin() {
return head.min;
}
public MinStack() {}
}160. 相交链表
这题我原本是想用两个指针一个个遍历，可是这两个链表不是等长的，所以找不到那个相交点，用for嵌套for又不符合题目要求，所以没写出来，看到人家的答案才知道，可以把这两个链表连起来，连起来这两个链表就等长了，双指针遍历就行。
public class Solution {
public ListNode getIntersectionNode(ListNode headA, ListNode headB) {
if(headA == null || headB == null) return null;
ListNode a = headA,b = headB;
while(a != b) {
a = a==null ? headB : a.next;
b = b==null ? headA : b.next;
}
return a;
}
}169. 多数元素
这题写了几次了，可以用摩尔投票法来找出大于一半的元素。
class Solution {
public int majorityElement(int[] nums) {
if (nums.length == 1) return nums[0];
int count = 1,res = nums[0];
for(int i = 1;i < nums.length; i++) {
if(nums[i] == res) count++;
if(nums[i] != res) {
count--;
if(count == 0) res = nums[i + 1];
}
}
return res;
}
}还看到有一个写法，因为是多数元素，所以一定是跨过中位数的，所以直接排序，寻找中位数就可以了。
class Solution {
public int majorityElement(int[] nums) {
Arrays.sort(nums);
return nums[(nums.length/2)];
}
}206. 反转链表
反转链表也算简单，注意要存储一下下一个变量，不然引用方向一变链表断开就找不到之后的值了。
递归写法
class Solution {
public ListNode reverseList(ListNode head) {
return reverse(null,head);
}
private static ListNode reverse(ListNode prev,ListNode curr){
if(curr==null) return prev;
ListNode node = curr.next;
curr.next = prev;
return reverse(curr,node);
}
}另一种写法。
class Solution {
public ListNode reverseList(ListNode head) {
if(head == null) return null;
if (head.next == null) return head;
ListNode last = reverseList(head.next);
head.next.next = head;
head.next = null;
return last;
}
}迭代写法
class Solution {
public ListNode reverseList(ListNode head) {
ListNode prev = null;
ListNode curr = head;
while(curr != null) {
ListNode node = curr.next;
curr.next = prev;
prev = curr;
curr = node;
}
return prev;
}
}215 数组中的第K个最大元素
这道题很简单，直接排序取第K大就好了。
class Solution {
public int findKthLargest(int[] nums, int k) {
Arrays.sort(nums);
return nums[nums.length - k];
}
}看了下评论，发现用库函数都能被骂，真的是服了，那顺便手写下快排。
class Solution {
public int findKthLargest(int[] nums, int k) {
quicksort(nums,0,nums.length - 1);
return nums[nums.length - k];
}
public void quicksort(int[] nums,int left,int right) {
if(left > right) return;
int temp = nums[left];
int i = left;
int j = right;
while(i != j) {
while(nums[j] >= temp && i < j) j--;
while(nums[i] <= temp && i < j) i++;
if(i < j) {
nums[i] ^= nums[j];
nums[j] ^= nums[i];
nums[i] ^= nums[j];
}
}
nums[left] = nums[i];
nums[i] = temp;
quicksort(nums,left,i - 1);
quicksort(nums,i + 1,right);
}
}217. 存在重复元素
解法一
一开始是直接暴力破解，两个for循环，发现超时了，所以就想到了先排序，然后一个for循环查看附近的值是否相同。
class Solution {
public boolean containsDuplicate(int[] nums) {
Arrays.sort(nums);
for(int i = 1; i < nums.length; i++) {
if(nums[i] == nums[i-1]) return true;
}
return false;
}
}解法二
可以直接用Set去重，判断set集合中的元素与数组元素的个数是否相同就可以得到答案。
class Solution {
public boolean containsDuplicate(int[] nums) {
Set<Integer> set = new HashSet<>();
for(int i:nums) {
set.add(i);
}
return set.size()==nums.length?false:true;
}
}改进一下就是加入失败的时候就直接跳出，可以像这么写。
class Solution {
public boolean containsDuplicate(int[] nums) {
Set<Integer> set = new HashSet<>();
for(int i:nums) {
if(!set.add(i)) return true;
}
return false;
}
}230. 二叉搜索树中第K小的元素
这道题和之前写的那道剑指Offer54是有点相似的，指路------>这里
这里我就不写这么详细了，就简单写两个方法。
// 中序遍历取第k个值
class Solution {
List<Integer> list = new ArrayList<>();
public int kthSmallest(TreeNode root, int k) {
inorder(root);
return list.get(k-1);
}
public void inorder(TreeNode root) {
if(root == null) return;
inorder(root.left);
list.add(root.val);
inorder(root.right);
}
}class Solution {
int res = 0,sum = 0;
public int kthSmallest(TreeNode root, int k) {
inorder(root,k);
return res;
}
public void inorder(TreeNode root,int k) {
if(root.left != null) {
inorder(root.left,k);
}
sum++;
if(sum == k) {
res = root.val;
}
if(root.right != null) {
inorder(root.right,k);
}
}
}231. 2的幂
这题真的看起来简单，又没怎么简单，想了好几个方法全是超时的，想到是用二进制了，但是还是不懂写只能借鉴别人的方法了，看了之后只能说太强了。
解法一
满足n & -n == n就是2的幂。
在二进制下，如果这个数是2的幂，那么它的二进制位上就会只有一个1。比如1是1，2是10，4是100，8是1000。
它的负数，在二进制是补码，所以会在各个位数上取反然后加1,这样就只有左边全为1右边全为0 。比如1是…1111..1，2是…1110，4是…1100,8是…111000。
所以按位与就会是本身。
class Solution {
public boolean isPowerOfTwo(int n) {
return (n > 0) && (n & -n) == n;
}
}解法二
满足(1<<30) % n == 0就是2的幂。
1 << 30位是最大的2的幂，对n取余如果等于0就表示n是2的幂。
class Solution {
public boolean isPowerOfTwo(int n) {
return (n > 0) && (1 << 30) % n == 0;
}
}236. 二叉树的最近公共祖先
class Solution {
public TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) {
if(root == null || root == p || root == q) return root;
TreeNode left = lowestCommonAncestor(root.left, p, q);
TreeNode right = lowestCommonAncestor(root.right, p, q);
if(left == null) return right;
if(right == null) return left;
return root;
}
}237. 删除链表中的节点
这道题，emm，描述的就离谱，其实就是给定一个链表的你要删掉的结点，删掉它。
class Solution {
public void deleteNode(ListNode node) {
node.val = node.next.val;
node.next = node.next.next;
}
}238. 除自身以外数组的乘积
这题不难，只是题目要求时间复杂度为O(n)和不能使用除法。这样的话就只能单个的for循环了，所以就可以考虑从左开始乘到当前树（不包含当前数），然后再加个for循环，再乘右边。这种方法速度很快，但是内存消耗太多，暂时还找不到内存消耗小的方法。
class Solution {
public int[] productExceptSelf(int[] nums) {
int len = nums.length;
int[] output = new int[len];
int left = 1;
int right = 1;
for(int i =0;i < len; i++) {
output[i] = left;
left = left * nums[i];
}
for(int i = len - 1; i >= 0; i--) {
output[i] = output[i] * right;
right = right * nums[i];
}
return output;
}
}292. Nim 游戏
这题有点搞，我大费周章的想了很久，结果看到评论我傻了，这就是一道脑经急转弯。
这就是巴什博弈，先手的话，只要是n%(m+1)==0的时候就是一定会输。反之就一定是赢的。在两个人都是最优解的情况。
class Solution {
public boolean canWinNim(int n) {
if(n%4==0) {
return false;
}
return true;
}
}简化一下就一行
class Solution {
public boolean canWinNim(int n) {
return n%4!=0;
}
}344. 反转字符串
这个就直接用遍历双指针遍历就好了，不同的就是交换变量的方式而已。
class Solution {
public void reverseString(char[] s) {
int front = 0;
int rear = s.length-1;
while(front < rear) {
s[front] ^= s[rear];
s[rear] ^= s[front];
s[front] ^= s[rear];
front++;
rear--;
}
}
}class Solution {
public void reverseString(char[] s) {
int front = 0;
int rear = s.length-1;
while(front < rear) {
char c = s[front];
s[front] = s[rear];
s[rear] = c;
front++;
rear--;
}
}
}557. 反转字符串中的单词 III
解法一
这题就是先用split方法分割字串，然后可以用StringBuffer的字符串反转方法进行反转。
class Solution {
public String reverseWords(String s) {
String[] arr = s.split(" ");
StringBuffer buffer = new StringBuffer();
for(int i = 0; i < arr.length; i++) {
if(i == arr.length-1) {
arr[i] = new StringBuffer(arr[i]).reverse().toString();
res = res + arr[i];
continue;
}
arr[i] = new StringBuffer(arr[i]).reverse().toString();
res = res + arr[i] + " ";
}
return res;
}
}这样效率是很低，字符串这样拼接不好，建议使用StringBuffer。时间和内存消耗效率都很低。
解法二
先用split方法分割字串，使用StringBuffer进行拼接；
class Solution {
public String reverseWords(String s) {
String[] arr = s.split(" ");
StringBuffer res = new StringBuffer();
for(int i = 0; i < arr.length; i++) {
res.append(new StringBuffer(arr[i]).reverse().toString());
res.append(" ");
}
// trim去除首尾空格
return res.toString().trim();
}
}解法三
直接在原数组上进行反转。
class Solution {
public String reverseWords(String s) {
char[] arr = s.toCharArray();
int front = 0;
int rear = 0;
for(int i = 0;i < s.length(); i++) {
if(arr[i] == ' ') {
rear = i - 1;
while(front < rear) {
arr[front] ^= arr[rear];
arr[rear] ^= arr[front];
arr[front] ^= arr[rear];
front++;
rear--;
}
front = i + 1;
}
}
// 反转最后一个单词
rear = s.length()-1;
while(front < rear) {
arr[front] ^= arr[rear];
arr[rear] ^= arr[front];
arr[front] ^= arr[rear];
front++;
rear--;
}
return new String(arr);
}
}在优化一下
class Solution {
public String reverseWords(String s) {
char[] arr = s.toCharArray();
int front = 0;
for(int i = 0;i < s.length(); i++) {
if(arr[i] == ' ') {
reverse(arr,front,i - 1);
front = i + 1;
}
}
// 反转最后一个单词
reverse(arr,front,s.length()-1);
return new String(arr);
}
public void reverse(char[] arr,int front,int rear){
while(front < rear) {
arr[front] ^= arr[rear];
arr[rear] ^= arr[front];
arr[front] ^= arr[rear];
front++;
rear--;
}
}
}另外一个搜索的思路
class Solution {
public String reverseWords(String s) {
char[] arr = s.toCharArray();
for(int i = 0;i < s.length(); i++) {
if(arr[i] == ' ') {
continue;
}
int front = i;
while(i < s.length() && arr[i]!=' ') {
i++;
}
reverse(arr,front,i - 1);
}
return new String(arr);
}
public void reverse(char[] arr,int front,int rear){
while(front < rear) {
arr[front] ^= arr[rear];
arr[rear] ^= arr[front];
arr[front] ^= arr[rear];
front++;
rear--;
}
}
}