LeetCode 刷题贴 JAVA代码，每日更新

BINARY TREE
Minimum Depth of Binary Tree

O(n) runtime, O(log n) space – DFS:
496 ms

1. public int minDepth(TreeNode root) {
   
2.         if (root == null) {
   
3.             return 0;
   
4.         }
   
5. 
   
6.         if (root.left == null) {
   
7.             return minDepth(root.right) + 1;
   
8.         }
   
9. 
   
10.         if (root.right == null) {
    
11.             return minDepth(root.left) + 1;
    
12.         }
    
13.         return Math.min(minDepth(root.left), minDepth(root.right)) + 1;
    
14. }

复制代码

O(n) runtime, O(n) space – BFS:
428 ms

1. public int minDepthBFS(TreeNode root) {
   
2.         if (root == null) {
   
3.             return 0;
   
4.         }
   
5.         Queue<TreeNode> queue = new LinkedList<TreeNode>();
   
6.         int depth = 1;
   
7.         queue.add(root);
   
8.         TreeNode rightMost = root;
   
9.         while (!queue.isEmpty()) {
   
10.             TreeNode node = queue.poll();
    
11.             if (node.left == null && node.right == null) {
    
12.                 break;
    
13.             }
    
14.             if (node.left != null) {
    
15.                 queue.add(node.left);
    
16.             }
    
17.             if (node.right != null) {
    
18.                 queue.add(node.right);
    
19.             }
    
20.             if (node == rightMost) {
    
21.                 depth++;
    
22.                 rightMost = (node.right != null) ? node.right : node.left;
    
23.             }
    
24.         }
    
25.         return depth;
    
26. }

复制代码

ARRAY
Missing Ranges

Given a sorted integer array where the range of elements are [0, 99] inclusive, return its
missing ranges.
For example, given [0, 1, 3, 50, 75], return [“2”, “4->49”, “51->74”, “76->99”]

Example Questions Candidate Might Ask:
Q: What if the given array is empty?
A: Then you should return [“0->99”] as those ranges are missing.
Q: What if the given array contains all elements from the ranges?
A: Return an empty list, which means no range is missing.

Code:GitHub link

1. public class MissingRanges {
   
2.     public List<String> findMissingRanges(int[] A, int lower, int upper) {
   
3.         List<String> ranges = new ArrayList<String>();
   
4.         if (A == null || A.length == 0) {
   
5.             ranges.add(getRange(lower, upper));
   
6.             return ranges;
   
7.         }
   
8.         int n = A.length;
   
9.         int prev = lower - 1;
   
10.         for (int i = 0; i <= n; i++) {
    
11.             int curr;
    
12.             if (i == n) {
    
13.                 curr = upper + 1;
    
14.             } else {
    
15.                 curr = A\[i\];
    
16.             }
    
17.             if (curr - prev >= 2) {
    
18.                 ranges.add(getRange(prev + 1, curr - 1));
    
19.             }
    
20.             prev = curr;
    
21.         }
    
22.         return ranges;
    
23.     }
    
24. 
    
25.     private String getRange(int from, int to) {
    
26.         if (from == to) {
    
27.             return String.valueOf(from);
    
28.         } else {
    
29.             return from + "->" + to;
    
30.         }
    
31.     }
    
32. }

复制代码

STRING
Longest Substring with At Most Two Distinct Characters

Given a string S, find the length of the longest substring T that contains at most two
distinct characters.
For example,
Given S = “eceba”,
T is "ece" which its length is 3.

Code:

1. public int lengthOfLongestSubstring(String s) {
   
2.         if (s == null || s.length() == 0) {
   
3.             return 0;
   
4.         }
   
5.         if (s.length() == 1) {
   
6.             return 1;
   
7.         }
   
8.         Queue<Character> queue = new LinkedList<Character>();
   
9.         int i = 0;
   
10.         int maxLength = 0;
    
11.         for (int j = 0; j < s.length(); j++) {
    
12.             while (queue.contains(s.charAt(j))) {
    
13.                 queue.poll();
    
14.                 i++;
    
15.             }
    
16.             queue.offer(s.charAt(j));
    
17.             maxLength = Math.max(j - i + 1, maxLength);
    
18.         }
    
19.         return maxLength;
    
20.     }

复制代码

ARRAY
Two Sum II – Input array is sorted

Similar to Question [1. Two Sum], except that the input array is already sorted in
ascending order.
github link
Code:

1. public class Solution {
   
2.     public int[] twoSum(int[] numbers, int target) {
   
3.         if (numbers == null || numbers.length == 0) {
   
4.             return new int[]{-1, -1};
   
5.         }
   
6.         int arg1 = -1;
   
7.         int arg2 = -1;
   
8.         for (int i = 0; i < numbers.length; i++) {
   
9.             int j = binarySearch(numbers, target - numbers[i], i + 1);
   
10.             if (j != -1) {
    
11.                 arg1 = i + 1;
    
12.                 arg2 = j + 1;
    
13.                 break;
    
14.             }
    
15.         }
    
16.         return new int[]{arg1, arg2};
    
17.     }
    
18. 
    
19.     private int binarySearch(int[] numbers, int target, int start) {
    
20.         int l = start;
    
21.         int r = numbers.length - 1;
    
22.         int m = l;
    
23.         while (l + 1 < r) {
    
24.             m = l + (r - l) / 2;
    
25.             if (numbers[m] == target) {
    
26.                 return m;
    
27.             } else if (numbers[m] > target) {
    
28.                 r = m;
    
29.             } else {
    
30.                 l = m;
    
31.             }
    
32.         }
    
33. 
    
34.         if (numbers[l] == target) {
    
35.             return l;
    
36.         }
    
37.         if (numbers[r] == target) {
    
38.             return r;
    
39.         }
    
40.         return -1;
    
41.     }
    
42. }

复制代码

ARRAY
Two Sum
github link
Code:
Use O(n) extra space to store number's position

1. public class Solution {
   
2.     public int[] twoSum(int[] numbers, int target) {
   
3.         if (numbers == null || numbers.length == 0) {
   
4.             return new int[]{-1, -1};
   
5.         }
   
6.         int arg1 = -1;
   
7.         int arg2 = -1;
   
8.         Map<Integer, Integer> map = new HashMap<Integer, Integer>();
   
9.         for (int i = 0; i < numbers.length; i++) {
   
10.             int tmp = target - numbers[i];
    
11.             if (map.containsKey(tmp)) {
    
12.                 arg1 = map.get(tmp) + 1;
    
13.                 arg2 = i + 1;
    
14.                 break;
    
15.             }
    
16.             map.put(numbers[i], i);
    
17.         }
    
18.         return new int[]{arg1, arg2};
    
19.     }
    
20. }

复制代码

Code:
use two pointers with O(1) space

1. public int[] twoSumTwoPointers(int[] numbers, int target) {
   
2.         int i = 0;
   
3.         int j = numbers.length - 1;
   
4.         while (i < j) {
   
5.             if (numbers[i] + numbers[j] == target) {
   
6.                 return new int[]{i + 1, j + 1};
   
7.             } else if (numbers[i] + numbers[j] > target) {
   
8.                 j--;
   
9.             } else {
   
10.                 i++;
    
11.             }
    
12.         }
    
13.         return new int[]{-1, -1};
    
14.     }

复制代码

DP
Edit Distance

Given two words word1 and word2, find the minimum number of steps required to convert word1 to word2. (each operation is counted as 1 step.)

You have the following 3 operations permitted on a word:

a) Insert a character
b) Delete a character
c) Replace a character

Code:
github link

1. public class Solution {
   
2.     public int minDistance(String word1, String word2) {
   
3.         if (word1 == null && word2 == null) {
   
4.             return 0;
   
5.         }
   
6.         int len1 = word1.length();
   
7.         int len2 = word2.length();
   
8.         int[][] dp = new int[len1 + 1][len2 + 1];
   
9.         for (int i = 0; i <= len1; i++) {
   
10.             dp[i][0] = i;
    
11.         }
    
12.         for (int i = 0; i <= len2; i++) {
    
13.             dp[0][i] = i;
    
14.         }
    
15.         for (int i = 1; i <= len1; i++) {
    
16.             for (int j = 1; j <= len2; j++) {
    
17.                 if (word1.charAt(i - 1) == word2.charAt(j - 1)) {
    
18.                     dp[i][j] = dp[i - 1][j - 1];
    
19.                 } else {
    
20.                     dp[i][j] = Math.min(dp[i - 1][j], Math.min(dp[i - 1][j - 1], dp[i][j - 1])) + 1;
    
21.                 }
    
22.             }
    
23.         }
    
24.         return dp[len1][len2];
    
25.     }
    
26. }

复制代码

楼主你现在在美国吗？如果在国内的话，请教一下：怎么拿到的Amazon Online access？

这个都不确定能拿到，不过一般是内推

robend 发表于 2014-12-27 17:34
楼主你现在在美国吗？如果在国内的话，请教一下：怎么拿到的Amazon Online access？

在国内，有事可私聊

有些新题，不错啊