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

Letter combinations of a phone number:  https://leetcode.com/problems/le ... -of-a-phone-number/

idea: dfs，感谢我问的那个关于dfs的帖子，dfs的模板其实真的很像。

1. public class Solution {
   
2.     public ArrayList<String> letterCombinations(String digits) {
   
3.         HashMap<Integer, String> map = new HashMap<Integer, String>();
   
4.         map.put(2, "abc");
   
5.         map.put(3, "def");
   
6.         map.put(4, "ghi");
   
7.         map.put(5, "jkl");
   
8.         map.put(6, "mno");
   
9.         map.put(7, "pqrs");
   
10.         map.put(8, "tuv");
    
11.         map.put(9, "wxyz");
    
12.         map.put(0, "");
    
13.         
    
14.         ArrayList<String> result = new ArrayList<String>();
    
15.         if(digits == null || digits.length() == 0)
    
16.         {
    
17.             return result;
    
18.         }
    
19.         ArrayList<Character> temp = new ArrayList<Character>();
    
20.         helper(digits, temp, result, map);
    
21.         return result;
    
22.     }
    
23.    
    
24.     public void helper(String digits, ArrayList<Character> temp, ArrayList<String> result, HashMap<Integer, String> map)
    
25.     {
    
26.         if(digits.length() == 0)
    
27.         {
    
28.             char[] arr = new char[temp.size()];
    
29.             for(int i = 0; i < temp.size(); i++)
    
30.             {
    
31.                 arr[i] = temp.get(i);
    
32.             }
    
33.             result.add(String.valueOf(arr));
    
34.             return;
    
35.         }
    
36.         
    
37.         Integer integer = Integer.valueOf(digits.substring(0,1));
    
38.         String str = map.get(integer);
    
39.         for(int i = 0; i < str.length(); i++)
    
40.         {
    
41.             temp.add(str.charAt(i));
    
42.             helper(digits.substring(1), temp, result, map);
    
43.             temp.remove(temp.size()-1);
    
44.         }
    
45.     }
    
46. }

复制代码

3 sum: https://leetcode.com/problems/3sum/

idea: 这题代码不难理解。关键是如何去重， 比如[-2，0，0，2，2]

1. public class Solution {
   
2.     public List<List<Integer>> threeSum(int[] nums) {
   
3.         List<List<Integer>> result = new ArrayList();
   
4.         if(nums == null || nums.length < 3)
   
5.         {
   
6.             return result;
   
7.         }
   
8.         Arrays.sort(nums);
   
9.         for(int i = 0; i < nums.length - 2; i++)
   
10.         {
    
11.             if(i != 0 && nums[i] == nums[i-1])
    
12.             {
    
13.                 continue;
    
14.             }
    
15.             int left = i + 1;
    
16.             int right = nums.length - 1;
    
17.             while(left < right)
    
18.             {
    
19.                 int sum = nums[i] + nums[left] + nums[right];
    
20.                 if(sum == 0)
    
21.                 {
    
22.                     ArrayList<Integer> temp = new ArrayList<Integer>();
    
23.                     temp.add(nums[i]);
    
24.                     temp.add(nums[left]);
    
25.                     temp.add(nums[right]);
    
26.                     result.add(temp);
    
27.                     left++;
    
28.                     right--;
    
29.                     
    
30.                     while(left < right && nums[left] == nums[left-1])
    
31.                     {
    
32.                         left++;
    
33.                     }
    
34.                     
    
35.                     while(left < right && nums[right] == nums[right+1])
    
36.                     {
    
37.                         right--;
    
38.                     }
    
39.                 }
    
40.                 else if(sum < 0)
    
41.                 {
    
42.                     left++;
    
43.                 }
    
44.                 else
    
45.                 {
    
46.                     right--;
    
47.                 }
    
48.                
    
49.             }
    
50.         }
    
51.         return result;
    
52.     }
    
53. }

复制代码

好励志，赞一个

chasedream1 发表于 2015-6-16 18:08
好励志，赞一个

多谢支持哈

已将所有题目编辑整理完毕，下一步，专题，比如 dfs题目等等

String 专题：

length of last word:   http://www.lintcode.com/en/problem/length-of-last-word/

Plus one: https://leetcode.com/problems/plus-one/

idea：把两个例子带入走代码。 [1，2， 3] -〉[1， 2， 4]，  [9，9，9] - 〉[1，0，0，0]

1. public class Solution {
   
2.     public int[] plusOne(int[] digits) {
   
3.         int flag = 1;
   
4.         for(int i = digits.length-1; i >= 0 && flag > 0; i--)
   
5.         {
   
6.             int sum = digits[i] + flag;
   
7.             digits[i] = sum % 10;
   
8.             flag = sum / 10;
   
9.         }
   
10.         if(flag == 0)
    
11.         {
    
12.             return digits;
    
13.         }
    
14.         int[] result = new int[digits.length + 1];
    
15.         result[0] = 1;
    
16.         for(int i = 1; i < result.length; i++)
    
17.         {
    
18.             result[i] = digits[i - 1];
    
19.         }
    
20.         return result;
    
21.     }
    
22. }

复制代码

Rectangle area:  https://leetcode.com/problems/rectangle-area/

idea: 其实这题考察没啥意义，估计面试也不会考，这题纯粹是数学的几何题，划划图，还是能做出了的，要耐心点。看过一遍答案下次还是能做出来的。就是，如果，两个矩阵不重合(就是最右横坐标小于另外一个最左横坐标，或者最上纵坐标小于另一个最低纵坐标)，两个面积相加。如果重合，就是两个矩阵面积减去重合面积。

1. public class Solution {
   
2.     public int computeArea(int A, int B, int C, int D, int E, int F, int G, int H) {
   
3.         if(C < E || G < A)
   
4.         {
   
5.             return (G - E) * (H - F) + (C - A) * (D - B);
   
6.         }
   
7.         
   
8.         if(D < F || H < B)
   
9.         {
   
10.             return (G - E) * (H - F) + (C - A) * (D - B);
    
11.         }
    
12.         
    
13.         int right = Math.min(C, G);
    
14.         int left = Math.max(A, E);
    
15.         int top = Math.min(H, D);
    
16.         int bottom = Math.max(F, B);
    
17.         return (G - E) * (H - F) + (C - A) * (D - B) - (right - left) * (top - bottom);
    
18.     }
    
19. }
    

复制代码

love1point 发表于 2015-6-18 10:00
Rectangle area:  https://leetcode.com/problems/rectangle-area/

idea: 其实这题考察没啥意义，估计面 ...

好励志的答案搬运贴
http://www.programcreek.com/2014/06/leetcode-rectangle-area-java/

love1point 发表于 2015-6-17 23:41
Plus one: https://leetcode.com/problems/plus-one/

idea：把两个例子带入走代码。 [1，2， 3] -〉[1， ...

好励志的答案搬运贴
http://www.jiuzhang.com/solutions/plus-one/