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 ); long res = 1 ; for (int i = 0 ; i < M; i++) { 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. 只出现一次的数字 这题直接用异或就好了，因为异或运算符和下面这样的规律。
异或符和交换律
n与0异或答案为n
两个相同的数异或答案为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 { 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 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(" " ); } 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--; } } }
