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

Anagrams:  https://leetcode.com/problems/anagrams/

idea: 用HashMap方法做，sorted string 为 Key, ArrayList<String>为Value

1. public class Solution {
   
2.     public ArrayList<String> anagrams(String[] strs) {
   
3.         ArrayList<String> result = new ArrayList<String>();
   
4.         
   
5.         HashMap<String, ArrayList<String>> map = new HashMap<String, ArrayList<String>>();
   
6.         
   
7.         for(int i = 0; i < strs.length; i++)
   
8.         {
   
9.             char[] array = strs[i].toCharArray();
   
10.             Arrays.sort(array);
    
11.             String s = String.valueOf(array);
    
12.             
    
13.             if(map.containsKey(s))
    
14.             {
    
15.                 map.get(s).add(strs[i]);
    
16.             }
    
17.             else
    
18.             {
    
19.                 ArrayList<String> arr = new ArrayList<String>();
    
20.                 arr.add(strs[i]);
    
21.                 map.put(s, arr);
    
22.             }
    
23.         }
    
24.         for(ArrayList<String> l : map.values())
    
25.         {
    
26.             if(l.size() > 1)
    
27.             {
    
28.                 result.addAll(l);
    
29.             }
    
30.         }
    
31.         return result;
    
32.     }
    
33. }

复制代码

Maximum product subarray:  https://leetcode.com/problems/maximum-product-subarray/

idea: 这题和 maximum subarry 很像，思路也是用动态规划，但记得要检查负数的影响，当负数乘以最小值就变最大了。

1. public class Solution {
   
2.     public int maxProduct(int[] nums) {
   
3.         if(nums == null || nums.length == 0)
   
4.         {
   
5.             return 0;
   
6.         }
   
7.         
   
8.         int maxLocal = nums[0];
   
9.         int minLocal = nums[0];
   
10.         int max = nums[0];
    
11.         
    
12.         for(int i = 1; i < nums.length; i++)
    
13.         {
    
14.             int temp = maxLocal;
    
15.             maxLocal = Math.max(Math.max(maxLocal * nums[i], nums[i]), minLocal * nums[i]);
    
16.             minLocal = Math.min(Math.min(temp * nums[i], nums[i]), minLocal * nums[i]);
    
17.             max = Math.max(maxLocal, max);
    
18.         }
    
19.         return max;
    
20.     }
    
21. }

复制代码

重复了，删。。。。

Invert binary tree : https://leetcode.com/problems/invert-binary-tree/
idea: 迭代解法

1. /**
   
2. * Definition for a binary tree node.
   
3. * public class TreeNode {
   
4. *     int val;
   
5. *     TreeNode left;
   
6. *     TreeNode right;
   
7. *     TreeNode(int x) { val = x; }
   
8. * }
   
9. */
   
10. public class Solution {
    
11.     public TreeNode invertTree(TreeNode root) {
    
12.         if(root == null)
    
13.         {
    
14.             return null;
    
15.         }
    
16.         LinkedList<TreeNode> queue = new LinkedList<TreeNode>();
    
17.         queue.offer(root);
    
18.         
    
19.         while(!queue.isEmpty())
    
20.         {
    
21.             TreeNode node = queue.poll();
    
22.             TreeNode left = node.left;
    
23.             node.left = node.right;
    
24.             node.right = left;
    
25.             
    
26.             if(node.left != null)
    
27.             {
    
28.                 queue.offer(node.left);
    
29.             }
    
30.             
    
31.             if(node.right != null)
    
32.             {
    
33.                 queue.offer(node.right);
    
34.             }
    
35.         }
    
36.         return root;
    
37. }
    
38. }

复制代码

Invert binary tree:   https://leetcode.com/problems/invert-binary-tree/

idea: 这两天相信大家看到了关于google不招聘某H大神，我们暂时不去讨论这件事，反正感谢这件事让我们多了一道leetcode题哈。

一看到binary tree, 非常容易用递归可以解决。

1. /**
   
2. * Definition for a binary tree node.
   
3. * public class TreeNode {
   
4. *     int val;
   
5. *     TreeNode left;
   
6. *     TreeNode right;
   
7. *     TreeNode(int x) { val = x; }
   
8. * }
   
9. */
   
10. public class Solution {
    
11.     public TreeNode invertTree(TreeNode root) {
    
12.         if(root == null)
    
13.         {
    
14.             return null;
    
15.         }
    
16.         TreeNode temp = root.left;
    
17.         root.left = root.right;
    
18.         root.right = temp;
    
19.         invertTree(root.left);
    
20.         invertTree(root.right);
    
21.         return root;
    
22. }
    
23. }

复制代码

随着leetcode刷到后期，更体会到算法思想对于解题的重要性！我们无法背诵代码。但当我们知道某道题的解题思路，解题步骤，这比记代码更容易了吧。当我们下次碰到相同或类似的题目，我们脑海就会懂得如何做了。后面的功夫，就是实际coding的能力了，也就是数据结构等基本功，其实，数据结构也就那么几种，熟练运用hashmap的containsKey，get(key), size()，put(k, v)等方法。String, 就是s. charAt()，equals() 等。ArrayList<>的get()等，Linkedlist<> 的 push(), poll()等。实际coding没别的办法了，就是多练，多敲，多错，错了就去查资料，记忆起来。

Combination sum: https://leetcode.com/problems/combination-sum/

idea：该题用dfs，dfs往往又用递归来实现

1. public class Solution {
   
2.     public ArrayList<ArrayList<Integer>> combinationSum(int[] candidates, int target) {
   
3.         ArrayList<ArrayList<Integer>> result = new ArrayList<ArrayList<Integer>>();
   
4.         ArrayList<Integer> curr = new ArrayList<Integer>();
   
5.         
   
6.         if(candidates == null || candidates.length == 0)
   
7.         {
   
8.             return result;
   
9.         }
   
10.         Arrays.sort(candidates);
    
11.         combinationSum(candidates, target, 0, curr, result);
    
12.         return result;
    
13.     }
    
14.    
    
15.     public void combinationSum(int[] candidates, int target, int j, ArrayList<Integer> curr, ArrayList<ArrayList<Integer>> result)
    
16.     {
    
17.         //递归的终止条件，递归一定要有终止条件
    
18.         if(target == 0)
    
19.         {
    
20.             ArrayList<Integer> temp = new ArrayList<Integer>(curr);
    
21.             result.add(temp);
    
22.             return;
    
23.         }
    
24.         
    
25.         for(int i = j; i < candidates.length; i++)
    
26.         {
    
27.             //如果该元素大于target，超过了，肯定不符合，退出
    
28.             if(target < candidates[i])
    
29.             {
    
30.                 return;
    
31.             }
    
32.             curr.add(candidates[i]);
    
33.             //递归
    
34.             combinationSum(candidates, target-candidates[i], i, curr, result);
    
35.             //如果没找到，回溯
    
36.             curr.remove(curr.size()-1);
    
37.         }
    
38.     }
    
39. }

复制代码

Subsets:  https://leetcode.com/problems/subsets/

idea： 这题用dfs递归出来。套用dfs模板，结果很快出来

1. public class Solution {
   
2.     public ArrayList<ArrayList<Integer>> subsets(int[] nums) {
   
3.         ArrayList<ArrayList<Integer>> result = new ArrayList<ArrayList<Integer>>();
   
4.         ArrayList<Integer> curr = new ArrayList<Integer>();
   
5.         if(nums == null || nums.length == 0)
   
6.         {
   
7.             return result;
   
8.         }
   
9.         Arrays.sort(nums);
   
10.         subsets(nums, 0, curr, result);
    
11.         return result;
    
12.     }
    
13.    
    
14.     public void subsets(int[] nums, int j, ArrayList<Integer> curr, ArrayList<ArrayList<Integer>> result)
    
15.     {
    
16.         ArrayList<Integer> temp = new ArrayList<Integer>(curr);
    
17.         result.add(temp);
    
18.         
    
19.         for(int i = j; i < nums.length; i++)
    
20.         {
    
21.             curr.add(nums[i]);
    
22.             subsets(nums, i+1, curr, result);
    
23.             curr.remove(curr.size()-1);
    
24.         }
    
25.     }
    
26. }

复制代码

love1point 发表于 2015-5-29 10:19
Spiral matrix:   https://leetcode.com/problems/spiral-matrix/
这道题，题目很容易理解，但如果自己写 ...

谢谢大神！！！

june2015 发表于 2015-6-15 23:52
谢谢大神！！！

我不是大神，多谢支持哈