Leetcode 刷题记录！！！不信自己今年找不到工作！！！

Length of last word: https://leetcode.com/problems/length-of-last-word/
idea: 这题题目理解起来不是很难，记住用 if （flag） 来判断比较方便。

1. 
   
2. public class Solution {
   
3.     public int lengthOfLastWord(String s) {
   
4.         int result = 0;
   
5.         boolean flag = false;
   
6.         for(int i = s.length()-1; i >= 0; i--)
   
7.         {   
   
8.             char c = s.charAt(i);
   
9.             
   
10.             if(c >= 'a' && c <= 'z' || c >= 'A' && c <= 'Z')
    
11.             {
    
12.                 flag = true;
    
13.                 result++;
    
14.             }
    
15.             else
    
16.             {
    
17.                 if(flag)
    
18.                 {
    
19.                     return result;
    
20.                 }
    
21.             }
    
22.         }
    
23.         return result;
    
24.     }
    
25. }

复制代码

Pow(x, n):  https://leetcode.com/problems/powx-n/
idea: 用二分法来做。 陷阱就是 整数 / 整数 还是整数

1. 
   
2. public class Solution {
   
3.     public double myPow(double x, int n) {
   
4.           if(n == 0)
   
5.         {
   
6.             return 1.0;
   
7.         }
   
8.         double half = myPow(x, n/2);
   
9.       
   
10.         if(n % 2 == 0)
    
11.         {
    
12.             return half * half;
    
13.         }
    
14.         else if(n > 0)
    
15.         {
    
16.             return half * half * x;
    
17.         }
    
18.         else
    
19.         {
    
20.             return half * half / x;
    
21.         }
    
22.     }
    
23. }

复制代码

Major element: https://leetcode.com/problems/majority-element/
idea: 这应该是lc最短的代码了吧。后面还有其他做法，用hashmap

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

复制代码

Merge sorted array:  https://leetcode.com/problems/merge-sorted-array/
idea: 思路很简单。但要记得从后面比较起，大的赋过去。

1. 
   
2. public class Solution {
   
3.     public void merge(int[] nums1, int m, int[] nums2, int n) {
   
4.         while(m > 0 && n > 0)
   
5.         {
   
6.             if(nums1[m-1] > nums2[n-1])
   
7.             {
   
8.                 nums1[m+n-1] = nums1[m-1];
   
9.                 m--;
   
10.             }
    
11.             else
    
12.             {
    
13.                 nums1[m+n-1] = nums2[n-1];
    
14.                 n--;
    
15.             }
    
16.         }
    
17.         while(n > 0)
    
18.         {
    
19.             nums1[m+n-1] = nums2[n-1];
    
20.             n--;
    
21.         }
    
22.     }
    
23. }

复制代码

Find peak element:  https://leetcode.com/problems/find-peak-element/
idea: 6.24.2015改成自己的代码风格重新写了一遍。思路很简单，就是按照题目定义来写代码，比较相邻的数字. 第一个if是根据[1] 这个test case 加上的。注意单独判断第一个数字和最后一个数字。中间的数字之间用for循环进行判断。

1. public class Solution {
   
2.     public int findPeakElement(int[] nums) {
   
3.         if(nums.length == 1)
   
4.         {
   
5.             return 0;
   
6.         }
   
7.         if(nums[0] > nums[1])
   
8.         {
   
9.             return 0;
   
10.         }
    
11.         for(int i = 1; i < nums.length - 1; i++)
    
12.         {
    
13.             if(nums[i] > nums[i-1] && nums[i] > nums[i+1])
    
14.             {
    
15.                 return i;
    
16.             }
    
17.         }
    
18.         if(nums[nums.length - 1] > nums[nums.length - 2])
    
19.         {
    
20.             return nums.length - 1;
    
21.         }
    
22.         return 0;
    
23.     }
    
24. }

复制代码

Path sum:  https://leetcode.com/problems/path-sum/
idea: 不难，理解后再记住。这些if 也不是一下子就能写出来，很多都会是有些test case过不去才写出这些if的。递归一定要有出口，前面两个if就是出口。一般树的题目可以递归做

1. 
   
2. public class Solution {
   
3.     public boolean hasPathSum(TreeNode root, int sum) {
   
4.         if(root == null)
   
5.         {
   
6.             return false;
   
7.         }
   
8.         
   
9.         
   
10.         if(root.left == null && root.right == null && root.val == sum)
    
11.         {
    
12.             return true;
    
13.         }
    
14.         else
    
15.         {
    
16.             return hasPathSum(root.left, sum-root.val) || hasPathSum(root.right, sum-root.val);
    
17.         }
    
18.     }
    
19. }

复制代码

重复了，已删

Maximum subarray: https://leetcode.com/problems/maximum-subarray/
idea:  这题按照如下代码走一边程序，不少题目需要用到如下套路

1. 
   
2. public class Solution {
   
3.     public int maxSubArray(int[] nums) {
   
4.         int local = nums[0];
   
5.         int max = nums[0];
   
6.         
   
7.         for(int i = 1; i < nums.length; i++)
   
8.         {
   
9.             local = Math.max(local + nums,nums);
   
10.             max = Math.max(local,max);
    
11.         }
    
12.         return max;
    
13.     }
    
14. }

复制代码

Jump game:  https://leetcode.com/problems/jump-game/
idea: 找的了更好解法，已更新，可用贪心算法跟着例子过一遍代码，代码也容易记忆下来

1. public class Solution {
   
2.     public boolean canJump(int[] nums) {
   
3.         int max = nums[0];
   
4.         for(int i = 1; i < nums.length; i++)
   
5.         {
   
6.             if(i <= max && i + nums[i] >= max)
   
7.             {
   
8.                 max = i + nums[i];
   
9.             }
   
10.         }
    
11.         return max >= nums.length - 1;
    
12.     }
    
13. }

复制代码

Rotate image:  https://leetcode.com/problems/rotate-image/
idea: 在纸上画一画，打些草稿，找到规律，重点在这行 copy[j][m-1-i] = matrix[j];

1. 
   
2. public class Solution {
   
3.     public void rotate(int[][] matrix) {
   
4.         int m = matrix.length;
   
5.         int[][] copy = new int[m][m];
   
6.         for(int i = 0; i < m; i++)
   
7.         {
   
8.             for(int j = 0; j < m; j++)
   
9.             {
   
10.                 copy[j][m-1-i] = matrix[j];
    
11.             }
    
12.         }
    
13.         
    
14.         for(int i = 0; i < m; i++)
    
15.         {
    
16.             for(int j = 0; j < m; j++)
    
17.             {
    
18.                 matrix[j] = copy[j];
    
19.             }
    
20.         }
    
21.         
    
22.     }
    
23. }

复制代码