7.整数反转

利用long来进行中转。

1
2
3
4
5
6
7
8
9
10
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. 回文数

解法一

回文数,其实跟回文字符串差不多,只是处理不同而已,我这里就直接将数字转换成了字符串然后对比。

1
2
3
4
5
6
7
8
9
10
11
12
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;
}
}

也可以直接将字符串反转在和原来的字符串相对比,不过效率第一点。

1
2
3
4
5
6
7
8
9
10
11
12
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来捕获异常。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
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)的算法,应该算是效率最差的算法了。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
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)。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
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循环的,但是看到了别人的解法,只能流出智商低的类水。

1
2
3
4
5
6
7
8
9
10
11
12
13
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.有效的括号

这经典题目了,直接用栈就可以判断了。

1
2
3
4
5
6
7
8
9
10
11
12
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. 合并两个有序的链表

这个题因为两个都是有序的连边,所以一个个赋值就可以了。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
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;
}
}

还有一种递归写法。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
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. 删除排序数组中的重复项

这题考虑的是原地修改数组,那就把这个数组当作一个新的数组就好了,碰到不相同的就放到前面。所以就有了这个算法。

1
2
3
4
5
6
7
8
9
10
11
12
13
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.全排列

看题目就知道,一道典型的全排列的题目,我就用了递归的写法。不过这个写法遇到有重复的数字的时候会有重复的数据,这题没有重复数据所以不需要去重,要是有重复数据可以需要考虑去重。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
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. 最大子序和

这题一开始我用的是双指针逼近,但是发现无法确定逼近的条件,所以就放弃了这个想法。

实在没想出。看了下答案,发现不是题难,是我太菜了。

其实这题用动态规划来解是最好的。

首先确定一下状态,那就是子数组的和最大。

然后是状态变化,因为是求子数组的和最大,所以开头是不可能是负的,如果是正的,但是加了后面的负数也是会抵消。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
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循环中很容易就超出数组的边界了,或者是转过头了没刹住,注意好边界条件就不难了。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
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. 不同路径

一看题目,直接递归搜索。

1
2
3
4
5
6
7
8
9
10
11
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等于一的时候,就只有一条路了,所以可以进行优化一下。

1
2
3
4
5
6
7
8
9
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);
}
}

但还是超时了,所以直接递归应该是不可行。所以得考虑其他想法了,比如说动态规划。

1
2
3
4
5
6
7
8
9
10
11
12
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];
}
}

虽然可以通过了,但是时间和空间的消耗还是挺多的。

看了一下评论区的解法,发现有一个解法就很有想法。那就是用排列组合的方式。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
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数组。

1
2
3
4
5
6
7
8
9
10
11
12
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];
}
}

直接递归,不需要存储状态。

1
2
3
4
5
6
7
8
9
10
11
12
13
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. 子集

这题的思路就是遍历数组,遇到新的元素,就把这个元素加到所有子集里,形成新的子集。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
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. 合并两个有序数组

解法一

直接就把这两个数组合并,然后在排一次序就好了。这应该是最简单,也是最花时间的算法。

1
2
3
4
5
6
7
8
9
10
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);
}
}

解法二

可以使用类似双指针的方法,选取最大的依次放入数组。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
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--;
}
}
}

简化之后可以得到。

1
2
3
4
5
6
7
8
9
10
11
12
13
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. 格雷编码

这题真的不会写了,题目描述的不是很清楚,看的都不是很明白,直接查了维基百科,看懂了格雷码转二进制数的规律之后,就很简单了。

1
2
3
4
5
6
7
8
9
10
由于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
因此所转换为之二进制码为0101
1
2
3
4
5
6
7
8
9
10
class 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. 只出现一次的数字

这题直接用异或就好了,因为异或运算符和下面这样的规律。

  1. 异或符和交换律
  2. n与0异或答案为n
  3. 两个相同的数异或答案为0
1
2
3
4
5
6
7
class Solution {
public int singleNumber(int[] nums) {
int res = 0;
for(int i:nums) res ^= i;
return res;
}
}

141.环形列表

这题可以先直接遍历,然后判断是否有重复的就好了。

1
2
3
4
5
6
7
8
9
10
11
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;
}
}

见到一种很有趣的解法。将每一个的节点指向自己,有环就会出现指向自己的节点。

1
2
3
4
5
6
7
8
9
10
11
12
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;
}
}

快慢指针。

1
2
3
4
5
6
7
8
9
10
11
12
13
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

这题和上面的题其实差不多,只是要返回交接的点。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
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来当存储数组。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
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的时候也会自动变更最小值。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
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又不符合题目要求,所以没写出来,看到人家的答案才知道,可以把这两个链表连起来,连起来这两个链表就等长了,双指针遍历就行。

1
2
3
4
5
6
7
8
9
10
11
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. 多数元素

这题写了几次了,可以用摩尔投票法来找出大于一半的元素。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
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;
}
}

还看到有一个写法,因为是多数元素,所以一定是跨过中位数的,所以直接排序,寻找中位数就可以了。

1
2
3
4
5
6
class Solution {
public int majorityElement(int[] nums) {
Arrays.sort(nums);
return nums[(nums.length/2)];
}
}

206. 反转链表

反转链表也算简单,注意要存储一下下一个变量,不然引用方向一变链表断开就找不到之后的值了。

递归写法

1
2
3
4
5
6
7
8
9
10
11
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);
}
}

另一种写法。

1
2
3
4
5
6
7
8
9
10
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;
}
}

迭代写法

1
2
3
4
5
6
7
8
9
10
11
12
13
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大就好了。

1
2
3
4
5
6
class Solution {
public int findKthLargest(int[] nums, int k) {
Arrays.sort(nums);
return nums[nums.length - k];
}
}

看了下评论,发现用库函数都能被骂,真的是服了,那顺便手写下快排。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
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循环查看附近的值是否相同。

1
2
3
4
5
6
7
8
9
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集合中的元素与数组元素的个数是否相同就可以得到答案。

1
2
3
4
5
6
7
8
9
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;
}
}

改进一下就是加入失败的时候就直接跳出,可以像这么写。

1
2
3
4
5
6
7
8
9
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是有点相似的,指路———>这里

这里我就不写这么详细了,就简单写两个方法。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
//	中序遍历取第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);
}
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
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。

所以按位与就会是本身。

1
2
3
4
5
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的幂。

1
2
3
4
5
class Solution {
public boolean isPowerOfTwo(int n) {
return (n > 0) && (1 << 30) % n == 0;
}
}

236. 二叉树的最近公共祖先

1
2
3
4
5
6
7
8
9
10
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,描述的就离谱,其实就是给定一个链表的你要删掉的结点,删掉它。

1
2
3
4
5
6
class Solution {
public void deleteNode(ListNode node) {
node.val = node.next.val;
node.next = node.next.next;
}
}

238. 除自身以外数组的乘积

这题不难,只是题目要求时间复杂度为O(n)和不能使用除法。这样的话就只能单个的for循环了,所以就可以考虑从左开始乘到当前树(不包含当前数),然后再加个for循环,再乘右边。这种方法速度很快,但是内存消耗太多,暂时还找不到内存消耗小的方法。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
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的时候就是一定会输。反之就一定是赢的。在两个人都是最优解的情况。

1
2
3
4
5
6
7
8
class Solution {
public boolean canWinNim(int n) {
if(n%4==0) {
return false;
}
return true;
}
}

简化一下就一行

1
2
3
4
5
class Solution {
public boolean canWinNim(int n) {
return n%4!=0;
}
}

344. 反转字符串

这个就直接用遍历双指针遍历就好了,不同的就是交换变量的方式而已。

1
2
3
4
5
6
7
8
9
10
11
12
13
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--;
}
}
}
1
2
3
4
5
6
7
8
9
10
11
12
13
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的字符串反转方法进行反转。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
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进行拼接;

1
2
3
4
5
6
7
8
9
10
11
12
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();
}
}

解法三

直接在原数组上进行反转。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
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);
}
}

在优化一下

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
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--;
}
}
}

另外一个搜索的思路

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
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--;
}
}
}