Test cases
|
|
Solution 1: Accepted
This is an easy one.
|
|
001.Two sum
Posted on
|
In
LeetCode
Solution 1: time limit exceeded
Time complexity: O(n^2)
Space complexity: O(1)12345678910111213141516public static int[] twoSum(int[] nums, int target) { if (nums == null) return null; int len = nums.length; for (int i = 0; i < nums.length; i++) { for (int j = i + 1; j < nums.length; j++) { if (nums[i] + nums[j] == target) { System.out.println(i + " " + j); return new int[] {i,j}; } } } return new int[] {0,0};}
Solution 2: accepted
Two-pass hashing, using Hashmap to reduce the time for each lookup to O(1).
Time complexity: O(n)
Space complexity: O(n)
|
|
Solution 3
Array Approaching
Time complexity: O(nlogn + n) (time used to sort the array should be counted)
Space complexity: O(n)
We can also use array. We order the array first and then we find the indices of the minimum (0) and the maximum (n-1), and then add these two numbers together and compare the result with the target. If the result is larget than the target, we decrement the maximum index, otherwise we increment the minimum index.
Other Notes
Creating a temporary array almost does not cost time:
1234int[] array = new int[2];array[0] = i; same as return new int[] {i, j};array[1] = j; ======>return array;Should verify the input;
- Should return null while the result is not excepted;
- Define nums.length to get a tiny gain;
003.Longest substring without repeating characters
Posted on
|
In
LeetCode
Solution 1: Time limit exceeded
Time: O(n^2), Space: O(n)
The look-backs lead to maximum O(n^2) time complexity.123456789101112131415161718192021222324252627282930public static int lengthOfLongestSubstring(String s) { if (s == null) return 0; int len = s.length(); if (len < 2) return len; HashMap<Character, Integer> map = new HashMap<>(); int left = 0; int right = 0; int max = 0; for (int i = 0; i < len; i++) { char current = s.charAt(i); if (map.containsKey(current)) { i = map.get(current); // ISSUE: look back left = i; right = i; map.clear(); max = max > right - left? max : right - left; } else { map.put(current, i); right++; }}max = max > right - left? max : right - left;return max;}
Solution 2: Accepted
Time: O(n), Space: O(n)
Store the previous result rather than looking back.
Interesting: change from String to StringBuilder does not bring any performance boost.
Using String1234567891011121314151617181920212223public class Solution { public int lengthOfLongestSubstring(String s) { int max = 0; String temp = ""; if (s.equals("") || s == null) return 0; for (int i = 0; i < s.length(); i++) { String current = s.charAt(i) + ""; if (temp.length() == 0 || temp.indexOf(current) == -1) { temp = temp + current; } else { max = max > temp.length()? max : temp.length(); temp = temp.substring(temp.indexOf(current) + 1, temp.length()) + current; // store previous result } } max = max > temp.length()? max : temp.length(); return max; }}
Using StringBuilder1234567891011121314151617181920212223public int lengthOfLongestSubstring(String s) { int max = 0; StringBuilder temp = new StringBuilder(); if (s.equals("") || s == null) return 0; for (int i = 0; i < s.length(); i++) { String current = Character.toString(s.charAt(i)); if (temp.length() == 0 || temp.indexOf(current) == -1) { temp.append(current); } else { max = max > temp.length()? max : temp.length(); String head = temp.substring(temp.indexOf(current) + 1, temp.length()) + current; temp.setLength(0); temp.append(head); } } max = max > temp.length()? max : temp.length(); return max;}
Solution 3: Accepted
Improved solution 1 without looking back.123456789101112131415161718public int lengthOfLongestSubstring(String s) { if (s == null) return 0; if (s.length() == 0) return 0; HashMap<Character, Integer> map = new HashMap<Character, Integer>(); int left = 0; int max = 0; for (int right = 0; right < s.length(); right++){ char current = s.charAt(right); if (map.containsKey(current)){ left = Math.max(left, map.get(current) + 1); // ignores the "current" char BEFORE the left pointer // left = map.get(current); // returns "7" in test case "adbccba" } map.put(current, right); max = Math.max(max, right - left + 1); } return max;}
Solution 4: Accepted
Improved solution 3, replacing hashmap with array. Even faster.1234567891011121314151617public static int lengthOfLongestSubstring2(String s) { if (s == null) return 0; if (s.length() == 0) return 0; int[] cache = new int[256]; // char int left = 0; int max = 0; for (int right = 0; right < s.length(); right++) { char current = s.charAt(right); if (cache[current] > 0) { left = Math.max(left, cache[current]); } cache[current] = right + 1; max = Math.max(max, right - left + 1); } return max;}
Test case 1
Solution 1: ~70ms
Solution 2: ~20ms
Solution 3: ~10ms
Solution 4: ~4ms
|
|
029.Divide Two Integers
Posted on
|
In
LeetCode
Test cases
|
|
Solution 1: TLE
Brute force, TLE with no doubt.
Time: O(n)
Space: O(1)
|
|
Solution 2: accepted 38ms 72.8%
Double the base if we can, decrease the time complexity to approximately logn.
Time: O(logn)
Space: O(1)
|
|
104.Maximum Depth of Binary Tree
Posted on
|
In
LeetCode
Solution 1: accepted 1ms
DFS.
|
|
Simplified 0ms12345public int maxDepth(TreeNode root) { if (root == null) return 0; return Math.max(maxDepth(root.left), maxDepth(root.right)) + 1;}
108.Convert Sorted Array to Binary Search Tree
Posted on
|
In
LeetCode
Solution 1: accepted 2ms
A very readable solution with extra spaces used.
|
|
002.Add two numbers
Posted on
|
In
LeetCode
Solution 1: accepted
Try to make it simple and readable.
Be aware of the concepts of reference and pointer, know how Java pass values.
|
|
111.Minimum Depth of Binary Tree
Posted on
|
In
LeetCode
Solution 1: accepted 1ms
DFS.
|
|
113.Path Sum II
Posted on
|
In
LeetCode
Solution 1: accepted 2ms
- Need to reset the condition of ArrayList using
temp.remove(temp.size() - 1). - Why
result.add(new ArrayList<Integer>(temp))? It passes a reference rather than an object. So if we useresult.add(temp), we will get the same temp multiple times. In addition, temp will contains no elements at the end of the recursion, so we will always get a list of[]at the end.
|
|
Alternative
|
|
112.Path Sum
Posted on
|
In
LeetCode
Solution 1: accepted 1ms
DFS.
|
|
Simplified123456public boolean hasPathSum(TreeNode root, int sum) { if (root == null) return false; else if (sum - root.val == 0 && root.left == null && root.right == null) return true; return (hasPathSum(root.left, sum - root.val) || hasPathSum(root.right, sum - root.val));}