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

Edit distance: https://leetcode.com/problems/edit-distance/

idea: 动态规划。觉得这题比较难，不看别人的答案的话

1. 
   
2. public class Solution {
   
3.     public int minDistance(String word1, String word2) {
   
4.         int len1 = word1.length();
   
5.         int len2 = word2.length();
   
6.         
   
7.         int[][] dp = new int[len1+1][len2+1];
   
8.         
   
9.         for(int i = 0; i <= len1; i++)
   
10.         {
    
11.             dp[0] = i;
    
12.         }
    
13.         
    
14.         for(int j = 0; j <= len2; j++)
    
15.         {
    
16.             dp[0][j] = j;
    
17.         }
    
18.         
    
19.         for(int i = 0; i < len1; i++)
    
20.         {
    
21.             char c1 = word1.charAt(i);
    
22.             for(int j = 0; j < len2; j++)
    
23.             {
    
24.                 char c2 = word2.charAt(j);
    
25.                
    
26.                 if(c1 == c2)
    
27.                 {
    
28.                     dp[i+1][j+1] = dp[j];
    
29.                 }
    
30.                 else
    
31.                 {
    
32.                     int replace = dp[j] + 1;
    
33.                     int insert = dp[j+1] + 1;
    
34.                     int delete = dp[i+1][j] + 1;
    
35.                     
    
36.                     int min = replace > insert ? insert : replace;
    
37.                     min = delete > min ? min: delete;
    
38.                     dp[i+1][j+1] = min;
    
39.                 }
    
40.             }
    
41.         }
    
42.         return dp[len1][len2];
    
43.     }
    
44. }

复制代码

lz能不能发github上或者blog上...论坛的code snippet工具有点渣...

enirinth 发表于 2015-6-1 17:56
lz能不能发github上或者blog上...论坛的code snippet工具有点渣...

嗯，但是直接放在一亩三分地更多人看得的啊。放github 链接可能没那么多人可以看到
谢谢你的建议

你可以把代码直接复制到leetcode去运行

有问题欢迎讨论哈

Remove element: https://leetcode.com/problems/remove-element/

idea: 这题题题意很好理解。当遇到数组里的元素和要被删除的数不相同时，我们进行赋值，且计数加一。遇到就是要被删除的数，不处理。7.2.2015, update: 注意返回的是 result, 而不是nums.length

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

复制代码

Container with most water:  https://leetcode.com/problems/container-with-most-water/

idea： 该题题目读起来需要花点时间，画画图，其实题目实质模型比较简单，用左右指针相向指，面积就是长乘高。

1. 
   
2. public class Solution {
   
3.     public int maxArea(int[] height) {
   
4.         if(height == null || height.length < 2)
   
5.         {
   
6.             return 0;
   
7.         }
   
8.         
   
9.         int result = 0;
   
10.         int left = 0;
    
11.         int right = height.length -1 ;
    
12.         
    
13.         while(left < right)
    
14.         {
    
15.             result = Math.max(result, (right-left)*Math.min(height[left],height[right]));
    
16.             
    
17.             if(height[left] < height[right])
    
18.             {
    
19.                 left++;
    
20.             }
    
21.             else
    
22.             {
    
23.                 right--;
    
24.             }
    
25.         }
    
26.         return result;
    
27.     }
    
28. }

复制代码

Same tree:  https://leetcode.com/problems/same-tree/

idea: 递归方法解决。记住，凡是用到递归，一定要有出口。有四种情况，比如， 1.  [][].         2.  [][val].            3. [val][].             4. [val][val].
所以第一个if处理 第一种情况，第二个if处理 2,3. 第三个if处理第4种。

1. 
   
2. public class Solution {
   
3.     public boolean isSameTree(TreeNode p, TreeNode q) {
   
4.         if(p == null && q == null)
   
5.         {
   
6.             return true;
   
7.         }
   
8.         
   
9.         if(p == null || q == null)
   
10.         {
    
11.             return false;   
    
12.         }
    
13.         
    
14.         if(p.val != q.val)
    
15.         {
    
16.             return false;
    
17.         }
    
18.         return isSameTree(p.left, q.left) && isSameTree(p.right, q.right);
    
19.         
    
20.     }
    
21. }

复制代码

strstr楼主试着用KMP解解看呢？

laoxie09 发表于 2015-6-2 11:14
strstr楼主试着用KMP解解看呢？

没必要吧。面试官没几个会的

Symmetric tree:  https://leetcode.com/problems/symmetric-tree/

idea: 这题比较简单，递归做法

1. 
   
2. public class Solution {
   
3.     public boolean isSymmetric(TreeNode root) {
   
4.         if(root == null)
   
5.         {
   
6.             return true;
   
7.         }
   
8.         
   
9.         return helper(root.left, root.right);
   
10.         
    
11.     }
    
12.     public boolean helper(TreeNode p, TreeNode q)
    
13.     {
    
14.         if(p == null && q == null)
    
15.         {
    
16.             return true;
    
17.         }
    
18.         
    
19.         if(p == null || q == null)
    
20.         {
    
21.             return false;
    
22.         }
    
23.         
    
24.         if(p.val != q.val)
    
25.         {
    
26.             return false;
    
27.         }
    
28.         
    
29.         return helper(p.left, q.right) && helper(p.right, q.left);
    
30.     }
    
31. }

复制代码

Pascal's triangle ii:  https://leetcode.com/problems/pascals-triangle-ii/

idea: 这道题比 pascals-triangle-i 简单了，所以说ii不一定比i难

1. public class Solution {
   
2.     public ArrayList<Integer> getRow(int rowIndex) {
   
3.         ArrayList<Integer> result = new ArrayList<Integer>();
   
4.         
   
5.         result.add(1);
   
6.         
   
7.         for(int i = 0; i < rowIndex; i++)
   
8.         {
   
9.             for(int j = result.size()-2; j >= 0; j--)
   
10.             {
    
11.                 result.set(j+1, result.get(j)+result.get(j+1));
    
12.             }
    
13.            
    
14.             result.add(1);
    
15.         }
    
16.         return result;
    
17.     }
    
18. }

复制代码