108. Convert Sorted Array to Binary Search Tree
1. Two Sum
Given an array of integers, return indices of the two numbers such that they add up to a specific target. You may assume that each input would have exactly one solution, and you may not use the same element twice.
Example:
Given nums = [2, 7, 11, 15], target = 9,
Because nums[0] + nums[1] = 2 + 7 = 9,
return [0, 1].
Solution:
The idea: the naive way is to iterate every possible pairs and its time complexity is O(n2). Can it be faster? We can use a hashmap to store elements who have been visited and everytime when one element is being visited, the value (target - current element) will be looked up in the hashmap.
public class Solution {
public int[] twoSum(int[] nums, int target) {
if (nums == null || nums.length == 0) {
return null;
}
Map<Integer, Integer> map = new HashMap<>();
for (int i = 0; i < nums.length; i++) {
Integer tmp = map.get(target - nums[i]);
if (tmp == null) {
map.put(nums[i], i);
} else {
return new int[] {tmp, i};
}
}
return null;
}
}
Time complexity is O(n), and space complexity is O(n).
7. Reverser Integer
Reverse digits of an integer.
Example 1: x = 123, return 321
Example 2: x = -123, return -321
Have you thought about this?
Here are some good questions to ask before coding. Bonus points for you if you have already thought through this!
If the integer's last digit is 0, what should the output be? ie, cases such as 10, 100.
Did you notice that the reversed integer might overflow? Assume the input is a 32-bit integer, then the reverse of 1000000003 overflows. How should you handle such cases?
For the purpose of this problem, assume that your function returns 0 when the reversed integer overflows.
The input is assumed to be a 32-bit signed integer. Your function should return 0 when the reversed integer overflows
Solution:
public class Solution {
public int reverse(int x) {
int reversed_x = 0;
while (x != 0) {
int temp = reversed_x * 10 + x % 10;
x = x / 10;
if (temp / 10 != reversed_x) {
reversed_x = 0;
break;
}
reversed_x = temp;
}
return reversed_x;
}
}
The only thing worths mention is that how to determine the overflow. A number is "overflow" means that the process to get it by some operations is not reversible. For example, a + 10 = b where b is overflow, then b -10 != a.
Time complexity is O(n) where n is the length of input.
9. Palindrome Number
Determine whether an integer is a palindrome. Do this without extra space.
Could negative integers be palindromes? (ie, -1)
If you are thinking of converting the integer to string, note the restriction of using extra space.
You could also try reversing an integer. However, if you have solved the problem "Reverse Integer", you know that the reversed integer might overflow. How would you handle such case?
Solution:
public class Solution {
public boolean isPalindrome(int x) {
if (x < 0 || x !=0 && x % 10 == 0) return false;
int reversed_x = 0;
while (x > reversed_x) {
reversed_x = reversed_x * 10 + x % 10;
x = x / 10;
}
return (x == reversed_x || x == reversed_x / 10);
}
}
To get over the overflow issue, the idea is that to compare the left half of input with its right half. By definition, they should be equal. To get the left half part and right half part, while(x > reversed_x) will roughly do it. By "roughly", I mean when exiting from the while loop, there are two possible cases: either x's length is equal to reversed_x's or x's length is shorter by 1. For example, if x = 4321, then before the last round in the while loop, x = 43, reversed_x = 12, after the while loop finished, x = 4, reversed_x = 123. So the return conditions should include x == reversed_x / 10 .There is one corner case you need consider, which is x !=0 && x % 10 == 0 because for x= 100 or 1000010, the while loop can not stop at the right position. For x = 1000010, after the while loop, x = 100, reversed_x = 100. In summary, in this solution, a trivial property is used: a valid four digit number is always bigger than a three valid digit number and 'valid' here means the number can not start with 0.
13. Roman to Integer
Given a roman numeral, convert it to an integer. Input is guaranteed to be within the range from 1 to 3999.
Solution:
Wikipedia of roman numerals is here.
Method 1:
public class Solution {
public int romanToInt(String s) {
if (s == null || s.length() == 0) {
return 0;
}
Map<Character, Integer> m = new HashMap<Character, Integer>();
m.put('I', 1);
m.put('V', 5);
m.put('X', 10);
m.put('L', 50);
m.put('C', 100);
m.put('D', 500);
m.put('M', 1000);
int length = s.length();
int result = m.get(s.charAt(length - 1));
for (int i = length - 2; i >= 0; i--) {
if (m.get(s.charAt(i)) < m.get(s.charAt(i + 1))) {
result -= m.get(s.charAt(i));
} else {
result += m.get(s.charAt(i));
}
}
return result;
}
}
Time complexity is O(n) and space complexity is O(1).
Method 2:
public class Solution {
public int romanToInt(String s) {
if (s == null || s.length() == 0) {
return 0;
}
int[] nums = new int[s.length()];
for (int i = 0; i < s.length(); i++) {
switch(s.charAt(i)) {
case 'M':
nums[i]=1000;
break;
case 'D':
nums[i]=500;
break;
case 'C':
nums[i]=100;
break;
case 'L':
nums[i]=50;
break;
case 'X' :
nums[i]=10;
break;
case 'V':
nums[i]=5;
break;
case 'I':
nums[i]=1;
break;
}
}
int length = s.length();
int result = nums[length - 1];
for (int i = length - 2; i >= 0; i--) {
if (nums[i] < nums[i + 1]) {
result -= nums[i];
} else {
result += nums[i];
}
}
return result;
}
}
Time complexity is O(n) and space complexity is O(n). I put method 2 here is because that some of you may think method 2 is faster but it is difficult to tell because the size of HashMap in method 1 is small so it should takes O(1) to look up an element. In method 2, there are two parallel for loops and switch, so overall I think it is difficult to compare their speeds. But method 1 has a better space complexity so I would recommend method 1. Please contact me if you want share your opinions.
14. Longest Common Prefix
Write a function to find the longest common prefix string amongst an array of strings.
Solution:
There are two ways to solve it. The 1st way is starting from the first string, compare prefix with the next string and update prefix, till end. The 2nd way is starting from the 1st char, compare it with all strings, and then next char till end.
The 1st way:
public class Solution {
public String longestCommonPrefix(String[] strs) {
if(strs == null || strs.length == 0) {
return "";
}
String prefix = strs[0];
for (int i = 1; i < strs.length; i++) {
int j = 0;
while (j < strs[i].length() && j < prefix.length() && strs[i].charAt(j) == prefix.charAt(j)) {
j++;
}
if (j == 0) {
return "";
}
prefix = prefix.substring(0, j);
}
return prefix;
}
}
The 2nd way:
20. Valid Parentheses
Given a string containing just the characters '(', ')', '{', '}', '[' and ']', determine if the input string is valid. The brackets must close in the correct order, "()" and "()[]{}" are all valid but "(]" and "([)]" are not.
Solution:
The solution is simple: we need a stack to store visited characters. For left parentheses, push into the stack and for right parentheses, pop from the stack and the popped character must be the corresponding left parentheses.
public class Solution {
public boolean isValid(String s) {
Deque <Character> stack = new ArrayDeque<>();
for (char c : s.toCharArray()) {
if ("([{".contains(String.valueOf(c))) {
stack.push(c);
} else if (!stack.isEmpty() && validPair(stack.peek(), c)) {
stack.pop();
} else {
return false;
}
}
return stack.isEmpty();
}
private boolean validPair(char c1, char c2) {
return (c1 == '(' && c2 == ')') || (c1 == '{' && c2 == '}')
|| (c1 == '[' && c2 == ']');
}
}
The only thing I want to mention here is that if you need a Stack, use Deque. I also post another solution from LeetCode forum, they are essentially the same.
public class Solution {
public boolean isValid(String s) {
Deque <Character> stack = new ArrayDeque<>();
for (char c : s.toCharArray()) {
if (c == '(')
stack.push(')');
else if (c == '{')
stack.push('}');
else if (c == '[')
stack.push(']');
else if (stack.isEmpty() || stack.pop() != c)
return false;
}
return stack.isEmpty();
}
}
Time complexity is O(n) and space complexity is O(n).
21. Merge Two Sorted Lists
Merge two sorted linked lists and return it as a new list. The new list should be made by splicing together the nodes of the first two lists.
Solution:
Method 1: iterative way, and use dummy node.
/**
* Definition for singly-linked list.
* public class ListNode {
* int val;
* ListNode next;
* ListNode(int x) { val = x; }
* }
**/
public class Solution {
public ListNode mergeTwoLists(ListNode l1, ListNode l2) {
if (l1 == null) {
return l2;
}
if (l2 == null) {
return l1;
}
ListNode dummy = new ListNode(0);
ListNode current = dummy;
while (l1 != null && l2 != null) {
if (l1.val < l2.val) {
current.next = l1;
l1 = l1.next;
} else {
current.next = l2;
l2 = l2.next;
}
current = current.next;
}
if (l1 == null) {
current.next = l2;
} else {
current.next = l1;
}
//l1 == null ? current.next = l2 : current.next = l1;
return dummy.next;
}
}
Method 2: recursive way, no dummy node.
public class Solution {
public ListNode mergeTwoLists(ListNode l1, ListNode l2) {
if (l1 == null) return l2;
if (l2 == null) return l1;
if (l1.val < l2.val) {
l1.next = mergeTwoLists(l1.next, l2);
return l1;
} else {
l2.next = mergeTwoLists(l1, l2.next);
return l2;
}
}
}
26. Remove Duplicates from Sorted Array
Given a sorted array, remove the duplicates in place such that each element appear only once and return the new length.
Do not allocate extra space for another array, you must do this in place with constant memory. For example, given input array nums = [1,1,2], your function should return length = 2, with the first two elements of nums being 1 and 2 respectively. It doesn't matter what you leave beyond the new length.
Solution:
Use two pointers method: [0, slow] is no-duplicate area(including slow element), [fast, length-1] is unexplored area(including fast element). We don't care about the area between slow and fast.
public class Solution {
public int removeDuplicates(int[] nums) {
if (nums == null || nums.length == 0) {
return 0;
}
int slow = 0;
int fast = 1;
while (fast < nums.length) {
if (nums[slow] == nums[fast]) {
fast++;
} else {
nums[++slow] = nums[fast++];
}
}
return slow + 1;
}
}
It is very important to determine the physical meaning of slow/fast pointers before you write the code and maintain their physical meaning all the time during running. Actually this is the proof of correctness of our code.
Of course we can write another solution with different physical meaning of slow/fast pointers, for example, [0, slow] is no-duplicate area(including slow element), (fast, length-1] is unexplored area(not including fast element).
public class Solution {
public int removeDuplicates(int[] nums) {
if(nums == null || nums.length == 0) {
return 0;
}
int slow = 0;
int fast = 0;
while (fast < nums.length - 1) {
if (nums[slow] == nums[fast + 1]) {
fast++;
} else {
nums[++slow] = nums[++fast];
}
}
return slow + 1;
}
}
Time complexity is O(n) and space complexity is O(1).
27. Remove Element
Given an array and a value, remove all instances of that value in place and return the new length. Do not allocate extra space for another array, you must do this in place with constant memory. The order of elements can be changed. It doesn't matter what you leave beyond the new length.
Example:
Given input array nums = [3,2,2,3], val = 3, your function should return length = 2, with the first two elements of nums being 2.
Solution:
This is just a variant of problem 26.
Use two pointer method: [0, slow) is solution area(not including slow element), [fast, length-1] is unexplored area(including fast element).
public class Solution {
public int removeElement(int[] nums, int val) {
if(nums == null || nums.length == 0) {
return 0;
}
int slow = 0;
int fast = 0;
while (fast < nums.length) {
if(nums[fast] == val) {
fast++;
} else {
nums[slow++] = nums[fast++];
}
}
return slow;
}
}
28. Implement strStr()
Implement strStr(). Returns the index of the first occurrence of needle in haystack, or -1 if needle is not part of haystack.
Solution:
public class Solution {
public int strStr(String haystack, String needle) {
if (haystack == null ||needle == null) {
return -1;
} else if (needle.length() == 0) {
return 0;
}
int h_length = haystack.length();
int n_length = needle.length();
for (int i = 0; i < h_length - n_length + 1; i++) {
int j = 0;
while (j < n_length && haystack.charAt(i + j) == needle.charAt(j)) {
j++;
}
if (j == n_length) {
return i;
}
}
return -1;
}
}
35. Search Insert Position
Given a sorted array and a target value, return the index if the target is found. If not, return the index where it would be if it were inserted in order. You may assume no duplicates in the array.
Here are few examples.
[1,3,5,6], 5 → 2
[1,3,5,6], 2 → 1
[1,3,5,6], 7 → 4
[1,3,5,6], 0 → 0
Solution:
It is a variant of binary search. I used a "stop-one-step-ahead" method. I just refer it with this name, but you must have seen this method somewhere else. In the "stop-one-step-ahead" method, when existing from the loop, left and right elements are most solution-like and left + 1 = right.
The details of this method will be covered later.
public class Solution {
public int searchInsert(int[] nums, int target) {
if(nums == null) {
return -1;
}
// no need to include one-element input, becaseu it can be covered
int left = 0;
int right = nums.length - 1;
while (left < right - 1) {
int mid = left + (right - left) / 2; // don't use (left + right) / 2 because it might overflow
if (nums[mid] == target) {
return mid;
} else if (nums[mid] < target) {
left = mid;
} else {
right = mid;
}
}
if (nums[left] >= target) {
return left;
} else if (nums[right] >= target) {
return right;
} else {
return right + 1;
}
}
}
Time complexity is O(log n).
38. Count and Say
The count-and-say sequence is the sequence of integers beginning as follows:
1, 11, 21, 1211, 111221, ...
1 is read off as "one 1" or 11.
11 is read off as "two 1s" or 21.
21 is read off as "one 2, then one 1" or 1211.
Given an integer n, generate the nth sequence. Note: The sequence of integers will be represented as a string.
Solution:
public class Solution {
public String countAndSay(int n) {
String res = "1";
while (--n > 0) {
StringBuilder sb = new StringBuilder();
char [] char_res = res.toCharArray();
int length = char_res.length;
for (int i = 0; i < length; i++) {
int count = 1;
while ((i + 1) < length && char_res[i] == char_res[i+1]) {
count++;
i++;
}
sb.append(String.valueOf(count) + String.valueOf(char_res[i]));
}
res = sb.toString();
}
return res;
}
}
53. Maximum Subarray
Find the contiguous subarray within an array (containing at least one number) which has the largest sum.
For example, given the array [-2,1,-3,4,-1,2,1,-5,4],
the contiguous subarray [4,-1,2,1] has the largest sum = 6.
More practice:
If you have figured out the O(n) solution, try coding another solution using the divide and conquer approach, which is more subtle.
Solution:
It is a typical 1D DP problem.
We are filling in a 1D array M[i]. M[i] represents the maximum subarray from 0-th number to the i-th number, including the i-th number.
So the induction rule is that:
M[i] = M[i - 1] + array[i], if M[i - 1] > 0;M[i] = array[i], if M[i - 1] <= 0;
The code below uses sum to represent M[i].
public class Solution {
public int maxSubArray(int[] nums) {
if (nums == null || nums.length == 0) {
return 0;
}
int result = Integer.MIN_VALUE;
int sum = 0;
for (int i = 0; i < nums.length; i++) {
if (sum <= 0) {
sum = nums[i];
} else {
sum += nums[i];
}
result = Math.max(result, sum);
}
return result;
}
}
Time complexity is O(n) and space complexity is O(1).
58. Length of Last Word
Given a string s consists of upper/lower-case alphabets and empty space characters ' ', return the length of last word in the string. If the last word does not exist, return 0. Note: A word is defined as a character sequence consists of non-space characters only.
For example,
Given s = "Hello World", return 5.
Given s = "a "; return 1. (from debug message)
public class Solution {
public int lengthOfLastWord(String s) {
int length = s.length();
char [] s_char = s.toCharArray();
// remove ending space
while (length -1 >= 0 && s_char[length - 1] == ' ') {
length--;
}
int count = 0;
for (int i = length - 1; i >= 0; i--) {
if (s_char[i] == ' ') {
return count;
} else {
count++;
}
}
return count;
}
}
66. Plus One
Given a non-negative integer represented as a non-empty array of digits, plus one to the integer. You may assume the integer do not contain any leading zero, except the number 0 itself. The digits are stored such that the most significant digit is at the head of the list.
Solution:
public class Solution {
public int[] plusOne(int[] digits) {
if (digits == null) {
return null;
}
int carries = 1;
for (int i = digits.length - 1; i >= 0; i--) {
int temp = digits[i] + 1;
digits[i] = temp % 10;
carries = temp / 10;
if (carries == 0) { // fast return
return digits;
}
}
int[] newDigits = new int[digits.length + 1];
newDigits[0] = 1;
for (int i = 1; i < newDigits.length; i++) {
newDigits[i] = digits[i-1];
}
return newDigits;
}
}
67. Add Binary
Given two binary strings, return their sum (also a binary string).
For example,
a = "11"
b = "1"
Return "100".
69. Sqrt(x)
Implement int sqrt(int x). Compute and return the square root of x.
Solution:
The solution follows the idea of binary search, and particularly the "stop-one-step-ahead" method. It uses long type number to avoid overflow.
public class Solution {
public int mySqrt(int x) {
long left = 0; // left can also be 1
long right = x;
while (left < right - 1) {
long mid = left + (right - left) / 2;
if (mid * mid <= x) {
left = mid;
} else {
right = mid;
}
}
if (right * right <= x) {
return (int) right;
}
return (int) left;
}
}
70. Climbing Stairs
You are climbing a stair case. It takes n steps to reach to the top.
Each time you can either climb 1 or 2 steps. In how many distinct ways can you climb to the top?
Note: Given n will be a positive integer.
Solution:
It is fibonacci number problem and it can be solved by either DP or recursion with memoization.
DP with O(1) space:
public class Solution {
public int climbStairs(int n) {
int f_zero = 1;
int f_one = 1;
while (n-- > 1) {
int temp = f_zero + f_one;
f_zero = f_one;
f_one = temp;
}
return f_one;
}
}
Time complexity is O(n) and space complexity is O(1).
83. Remove Duplicates from Sorted List
Given a sorted linked list, delete all duplicates such that each element appear only once.
For example,
Given 1->1->2, return 1->2.
Given 1->1->2->3->3, return 1->2->3.
Solution:
It is a variant of two pointers method.
/**
* Definition for singly-linked list.
* public class ListNode {
* int val;
* ListNode next;
* ListNode(int x) { val = x; }
* }
*/
public class Solution {
public ListNode deleteDuplicates(ListNode head) {
if (head == null) {
return null;
}
ListNode cur = head;
while (cur.next != null) {
if (cur.val == cur.next.val) {
cur.next = cur.next.next;
} else {
cur = cur.next;
}
}
return head;
}
}
88. Merge Sorted Array
Given two sorted integer arrays nums1 and nums2, merge nums2 into nums1 as one sorted array.
Note: You may assume that nums1 has enough space (size that is greater or equal to m + n) to hold additional elements from nums2. The number of elements initialized in nums1 and nums2 are m and n respectively.
Solution:
Two pointers method. To do the merge in place, we begin comparison from the end of arrays.
public class Solution {
public void merge(int[] nums1, int m, int[] nums2, int n) {
int i = m - 1;
int j = n - 1;
int end = m + n - 1;
while (i >= 0 && j >= 0) {
if (nums1[i] > nums2[j]) {
nums1[end--] = nums1[i--];
} else {
nums1[end--] = nums2[j--];
}
}
while (i >= 0) {
nums1[end--] = nums1[i--];
}
while (j >= 0) {
nums1[end--] = nums2[j--];
}
}
}
Time complexity is O(m+n) and space complexity is O(1).
100. Same Tree
Given two binary trees, write a function to check if they are equal or not.
Two binary trees are considered equal if they are structurally identical and the nodes have the same value.
Solution:
This is a good example of using recursion. Actually recursion is used a lot in tree problems because many tree concepts, including balanced tree and binary search tree, are defined recursively.
What is recursion? It is function calls itself, correct. It is breaking down a big problem into small ones, correct. How to implement recursion? You need clearify two things:
- base conditon, otherwise recursion can not stop.
- recursion rule. In this step, what are the operations in current call? What is the value passed from previous call? What is the value passed to next call?
In recursion, the space complexity is O(h) where h is the number of levels of calls in recursion, if each call takes O(1) space.
/**
* Definition for a binary tree node.
* public class TreeNode {
* int val;
* TreeNode left;
* TreeNode right;
* TreeNode(int x) { val = x; }
* }
*/
public class Solution {
public boolean isSameTree(TreeNode p, TreeNode q) {
if (p == null && q == null) {
return true;
} else if (p == null || q == null) {
return false;
} else if (p.val != q.val) {
return false;
}
return isSameTree(p.left, q.left) && isSameTree(p.right, q.right);
}
}
101. Symmetric Tree
Given a binary tree, check whether it is a mirror of itself (ie, symmetric around its center).
For example, this binary tree [1,2,2,3,4,4,3] is symmetric:
1
/ \
2 2
/ \ / \
3 4 4 3
But the following [1,2,2,null,3,null,3] is not:
1
/ \
2 2
\ \
3 3
Bonus points if you could solve it both recursively and iteratively.
Solution:
It is a variant of 100. Same Tree.
Method 1, use recursion and only modify solution of 100. Same Tree a little bit:
public class Solution {
public boolean isSymmetric(TreeNode root) {
if (root == null) {
return true;
}
return isSymmetric(root.left, root.right);
}
private boolean isSymmetric(TreeNode left, TreeNode right) {
if (left == null && right == null) {
return true;
} else if (left == null || right == null) {
return false;
} else if (left.val != right.val) {
return false;
}
return isSymmetric(left.left, right.right) && isSymmetric(left.right, right.left);
}
}
Method 2, iteratively:
104. Maximum Depth of Binary Tree
Given a binary tree, find its maximum depth.
The maximum depth is the number of nodes along the longest path from the root node down to the farthest leaf node.
Solution:
Method 1:
It can be solved easily by recursion. Essentially it is a DFS method.
public class Solution {
public int maxDepth(TreeNode root) {
if (root == null) {
return 0;
}
int left = maxDepth(root.left);
int right = maxDepth(root.right);
return Math.max(left, right) + 1;
}
}
Time complexity is O(n) and space complexity is O(n) or O(h) where h is the height of input tree.
Method 2:
Based on DFS, use a global_depth, then DFS the tree with current_depth + 1 when go down to next level of tree, and update global_depth when reach leaf node.
107. Binary Tree Level Order Traversal II
Given a binary tree, return the bottom-up level order traversal of its nodes' values. (ie, from left to right, level by level from leaf to root).
For example: Given binary tree [3,9,20,null,null,15,7],
3
/ \
9 20
/ \
15 7
return its bottom-up level order traversal as:
[
[15,7],
[9,20],
[3]
]
From debug message, if input is [], output is [].
Solution:
This is a level order traversal problem. The tricky thing here is to group elements by their levels.
/**
* Definition for a binary tree node.
* public class TreeNode {
* int val;
* TreeNode left;
* TreeNode right;
* TreeNode(int x) { val = x; }
* }
*/
public class Solution {
public List<List<Integer>> levelOrderBottom(TreeNode root) {
List<List<Integer>> sol = new ArrayList<>();
if (root == null) {
return sol;
}
Queue<TreeNode> queue = new LinkedList<>();
queue.offer(root);
while (!queue.isEmpty()) {
int size = queue.size();
List<Integer> level = new ArrayList<>();
while (size-- > 0) {
TreeNode temp = queue.poll();
level.add(temp.val);
if (temp.left != null) {
queue.offer(temp.left);
}
if (temp.right != null) {
queue.offer(temp.right);
}
}
sol.add(level);
}
Collections.reverse(sol);
return sol;
}
}
108. Convert Sorted Array to Binary Search Tree
Given an array where elements are sorted in ascending order, convert it to a height balanced BST.
Solution:
Use DFS, every time pick the middle of array as new root.
public class Solution {
public TreeNode sortedArrayToBST(int[] nums) {
if (nums == null) {
return null;
}
return buildTree(nums, 0, nums.length - 1);
}
private TreeNode buildTree(int[] nums, int left, int right) {
if (left > right) {
return null;
}
int mid = left + (right - left) / 2;
TreeNode root = new TreeNode(nums[mid]);
root.left = buildTree(nums, left, mid - 1);
root.right = buildTree(nums, mid + 1, right);
return root;
}
}
Time complexity is O(n) and space complexity is O(logn).
110. Balanced Binary Tree
Given a binary tree, determine if it is height-balanced.
For this problem, a height-balanced binary tree is defined as a binary tree in which the depth of the two subtrees of every node never differ by more than 1.
Solution:
If you know how to solve 104. Maximum Depth of Binary Tree, you can this problem.
public class Solution {
public boolean isBalanced(TreeNode root) {
if (root == null) {
return true;
}
return getHeight(root) != -1;
}
private int getHeight(TreeNode head) {
if (head == null) {
return 0;
}
int left = getHeight(head.left);
int right = getHeight(head.right);
if (left == -1 || right == -1 || Math.abs(left - right) > 1) {
return -1;
} else {
return Math.max(left, right) + 1;
}
}
}
Time complexity is O(n) and space complexity is O(n) or O(h) where h is the height of input tree.
111. Minimum Depth of Binary Tree
Given a binary tree, find its minimum depth.
The minimum depth is the number of nodes along the shortest path from the root node down to the nearest leaf node.
Solution:
Understand the definition of minimum depth first. I gave it a few attempts and from debug message I realized my initial understanding of minimum depth is wrong.
public class Solution {
public int minDepth(TreeNode root) {
if (root == null) {
return 0;
}
return getHeight(root);
}
private int getHeight(TreeNode root) {
if (root == null) {
return Integer.MAX_VALUE;
} else if (root.left == null && root.right == null) {
return 1;
}
int left = getHeight(root.left);
int right = getHeight(root.right);
return Math.min(left, right) + 1;
}
}
Time complexity is O(n) and space complexity is O(n) or O(h) where h is the height of input tree.
112. Path Sum
Given a binary tree and a sum, determine if the tree has a root-to-leaf path such that adding up all the values along the path equals the given sum.
For example: Given the below binary tree and sum = 22,
5
/ \
4 8
/ / \
11 13 4
/ \ \
7 2 1
return true, as there exist a root-to-leaf path 5->4->11->2 which sum is 22.
Solution:
public class Solution {
public boolean hasPathSum(TreeNode root, int sum) {
if (root == null) {
return false;
} else if (root.left == null && root.right == null) {
return sum == root.val;
}
return hasPathSum(root.left, sum - root.val) || hasPathSum(root.right, sum - root.val);
}
}
118. Pascal's Triangle
Given numRows, generate the first numRows of Pascal's triangle.
For example, given numRows = 5, Return
[
[1],
[1,1],
[1,2,1],
[1,3,3,1],
[1,4,6,4,1]
]
Solution:
public class Solution {
public List<List<Integer>> generate(int numRows) {
List<List<Integer>> sol = new ArrayList<>();
if (numRows <= 0) {
return sol;
}
List<Integer> first = new ArrayList<>();
first.add(1);
sol.add(first);
for (int i = 1; i < numRows; i++) {
List<Integer> level = new ArrayList<>();
List<Integer> pre = sol.get(i - 1);
for (int j = 0; j < i + 1; j++) {
if (j == 0) {
level.add(j, pre.get(j));
} else if (j == i) {
level.add(j, pre.get(j - 1));
} else {
level.add(j, pre.get(j - 1) + pre.get(j));
}
}
sol.add(level);
}
return sol;
}
}
119. Pascal's Triangle II
Given an index k, return the kth row of the Pascal's triangle.
For example, given k = 3,
Return [1,3,3,1].
Note: Could you optimize your algorithm to use only O(k) extra space?
Solution:
public class Solution {
public List<Integer> getRow(int rowIndex) {
List<Integer> sol = new ArrayList<>();
if (rowIndex < 0) {
return sol;
}
sol.add(1);
for (int i = 1; i <= rowIndex; i++) {
List<Integer> cur = new ArrayList<>(i + 1);
for (int j = 0; j < i + 1; j++) {
if (j == 0) {
cur.add(j, sol.get(j));
} else if (j == i) {
cur.add(j, sol.get(j - 1));
} else {
cur.add(j, sol.get(j - 1) + sol.get(j));
}
}
sol = cur;
}
return sol;
}
}
121. Best Time to Buy and Sell Stock
Say you have an array for which the ith element is the price of a given stock on day i.
If you were only permitted to complete at most one transaction (ie, buy one and sell one share of the stock), design an algorithm to find the maximum profit.
Example 1:
Input: [7, 1, 5, 3, 6, 4]
Output: 5
max. difference = 6-1 = 5 (not 7-1 = 6, as selling price needs to be larger than buying price)
Example 2:
Input: [7, 6, 4, 3, 1]
Output: 0
In this case, no transaction is done, i.e. max profit = 0.
Solution:
The physical meaning of M[i]: max profit when buy at minimum price among 0~ith days and sell at the ith day.
M[i] = 0, and update min_so_far; if input[i] < min_so_far
input[i] - min_so_far; otherwise
DP with optimized space complexity:
public class Solution {
public int maxProfit(int[] prices) {
if (prices == null || prices.length == 0) {
return 0;
}
int min_so_far = Integer.MAX_VALUE;
int profit = 0;
for (int i : prices) {
if (i < min_so_far) {
min_so_far = i;
} else {
profit = Math.max(i - min_so_far, profit);
}
}
return profit;
}
}
Time complexity is O(n) and space complexity is O(1).
122. Best Time to Buy and Sell Stock II
Say you have an array for which the ith element is the price of a given stock on day i.
Design an algorithm to find the maximum profit. You may complete as many transactions as you like (ie, buy one and sell one share of the stock multiple times). However, you may not engage in multiple transactions at the same time (ie, you must sell the stock before you buy again).
Solution:
Find out all profitable transactions:
public class Solution {
public int maxProfit(int[] prices) {
if (prices == null || prices.length == 0) {
return 0;
}
int profit = 0;
for (int i = 1; i < prices.length; i++) {
if (prices[i] - prices[i - 1] > 0) {
profit += prices[i] - prices[i - 1];
}
}
return profit;
}
}
125. Valid Palindrome
Given a string, determine if it is a palindrome, considering only alphanumeric characters and ignoring cases.
For example,
"A man, a plan, a canal: Panama" is a palindrome.
"race a car" is not a palindrome.
Note: Have you consider that the string might be empty? This is a good question to ask during an interview.
For the purpose of this problem, we define empty string as valid palindrome.
Solution:
Two pointers method:
public class Solution {
public boolean isPalindrome(String s) {
if (s == null || s.length() == 0) {
return true;
}
int left = 0;
int right = s.length() - 1;
while (left < right) {
while (left < s.length() && !isValid(s.charAt(left))) {
left++;
}
while (right >=0 && !isValid(s.charAt(right))) {
right--;
}
if ( left <= right && Character.toLowerCase(s.charAt(left)) != Character.toLowerCase(s.charAt(right))) {
return false;
} else {
left++;
right--;
}
}
return true;
}
private boolean isValid(char c) {
return Character.isLetter(c) || Character.isDigit(c);
}
}
136. Single Number
Given an array of integers, every element appears twice except for one. Find that single one.
Soluton:
public class Solution {
public int singleNumber(int[] nums) {
int sol = 0;
for (int i : nums) {
sol = sol^i;
}
return sol;
}
}
141. Linked List Cycle
Given a linked list, determine if it has a cycle in it.
Follow up: Can you solve it without using extra space?
Solution:
Slow-fast pointers method:
public class Solution {
public boolean hasCycle(ListNode head) {
if (head == null || head.next == null) {
return false;
}
ListNode slow = head;
ListNode fast = head;
while (fast != null && fast.next != null) {
slow = slow.next;
fast = fast.next.next;
if (slow == fast) {
return true;
}
}
return false;
}
}
155. Min Stack
Design a stack that supports push, pop, top, and retrieving the minimum element in constant time.
push(x) -- Push element x onto stack. pop() -- Removes the element on top of the stack. top() -- Get the top element. getMin() -- Retrieve the minimum element in the stack.
Example:
MinStack minStack = new MinStack();
minStack.push(-2);
minStack.push(0);
minStack.push(-3);
minStack.getMin(); --> Returns -3.
minStack.pop();
minStack.top(); --> Returns 0.
minStack.getMin(); --> Returns -2.
Solution:
Because stack only has three common APIs: push, pop and top. So when we are going to implement additional APIs, we need more than one stacks.
Here we are going to use two stacks: one is the main stack and the other one is implementing min function. The idea here is that when pushing a new element into the main stack, if it is the min value(including equal) so far, we store it into the minStack; when poping an element, we compare it with the minStack, if they are equal, also pop from the minStack.
public class MinStack {
// use interface Deque to represent stack.
// Don't use class Stack which is deprecated in Java.
private Deque<Integer> stack;
private Deque<Integer> minStack;
public MinStack() {
stack = new LinkedList<Integer>();
minStack = new LinkedList<Integer>();
}
public void push(int x) {
stack.offerFirst(x);
if (minStack.isEmpty() || x <= minStack.peekFirst()) {
minStack.offerFirst(x);
}
}
public Integer pop() {
// in LeetCode the return type is void, change it to Integer.
// check if empty, otherwise null.equals() will throw NPE.
if (stack.isEmpty()) {
return null;
}
Integer sol = stack.pollFirst();
if (minStack.peekFirst().equals(sol)) {
minStack.pollFirst();
}
return sol;
}
public Integer top() {
return stack.peekFirst();
}
public Integer getMin() {
return minStack.peekFirst();
}
}
What if there are many duplicate elements? Can we optimize the space used by the minStack? The solutions is that we store a (min, size) pair, where size records the size of the main stack, in the minStack. When poping, we compare the size of main stack with the size stored in the pair.
public class MinStack {
private Deque<Integer> stack;
private Deque<Pair> minStack;
public MinStack() {
stack = new LinkedList<Integer>();
minStack = new LinkedList<Pair>();
}
public void push(int x) {
stack.offerFirst(x);
if (minStack.isEmpty() || x < minStack.peekFirst().min) {
Pair pair = new Pair(x, stack.size());
minStack.offerFirst(pair);
}
}
public Integer pop() {
if (stack.isEmpty()) {
return null;
}
if (minStack.peekFirst().size == stack.size()) {
minStack.pollFirst();
}
Integer sol = stack.pollFirst();
return sol;
}
public Integer top() {
return stack.peekFirst();
}
public Integer getMin() {
return minStack.peekFirst().min;
}
}
class Pair {
int min;
int size;
public Pair(int min, int size) {
this.min = min;
this.size = size;
}
}
160. Intersection of Two Linked Lists
Write a program to find the node at which the intersection of two singly linked lists begins.
For example, the following two linked lists:
A: a1 → a2
↘
c1 → c2 → c3
↗
B: b1 → b2 → b3
begin to intersect at node c1.
Notes:
- If the two linked lists have no intersection at all, return null.
- The linked lists must retain their original structure after the function returns.
- You may assume there are no cycles anywhere in the entire linked structure.
- Your code should preferably run in O(n) time and use only O(1) memory.
Solution:
In LeetCode, the difficulty of this problem is easy, but I think it can be considered as medium.
Method 1:
By connecting the tail of Linked List A, which is c3 in example above, to the head of Linked List B, which is b1, then we can get a Linked List with circle.
A: a1 → a2 → c1 → c2 → c3
^ |
| arrow down
b3 <- b2 <- b1
Then the problem now is how to get the entrance of the circle in the Linked List? In this example, the solution should be c1.
Assume:
the distance between the head of Linked List and the entrance of circle is A,
the distance between the entrance of circle and the meeting node of slow/fast pointers is X,
the length of the Linked List is L,
the length of the circle is R, then R = L - A
and when slow and fast pointers meet, the steps the slow pointer walked is S, the steps the fast pointer walked is 2S.
We can derive some equations:
- S = A + X and 2S = S + nR, by considering slow/fast pointers meet,
- further A + X = nR = (n-1)R + R = (n-1)R + L - A,
- finally A = (n-1)R + L - A - X.
How to interpret A = (n-1)R + L - A - X? It means that if we put two pointers at the head of Linked List and the meeting node of slow/fast pointers, respectively, then move both pointers one step forward at the same time, then they will meet at the entrance of circle. For the pointer from the head of Linked List, it moves A steps and for the one starting from the meeting node of slow/fast pointers, it moves L - A - X steps.
So there are two steps for entrance of circle problem:
- Use slow-fast pointers method to get the meeting node.
- Put one pointer at the head, the other pointer at the meeting node from step 1, move both pointers one step forward each time and finally they will meet at the entrance of circle.
Method 2:
Because the lenght of two Linked Lists may not be the same, when iterating the two Linked Lists, we can manually connect the tail of one Linked List to the other's head and the iterations are following:
Linked List A: a1 a2 c1 c2 c3 b1 b2 b3 **c1** c2 c3
Linked List B: b1 b2 b3 c1 c2 c3 a1 a2 **c1** c2 c3
The answer is c1.
public class Solution {
public ListNode getIntersectionNode(ListNode headA, ListNode headB) {
if (headA == null || headB == null) {
return null;
}
ListNode curA = headA;
ListNode curB = headB;
while (curA != null && curB != null) {
/* check the heads here
can not put it before the while loop
because if so, for input: [2,3] and [3]
can not enter the while loop
*/
if (curA == curB) {
return curA;
}
curA = curA.next;
curB = curB.next;
/*
must check again here
otherwise if now curA is null and curB is null
can not exit the while loop
*/
if (curA == curB) {
return curA;
}
if (curA == null) {
curA = headB;
}
if (curB == null) {
curB = headA;
}
}
return null;
}
}
Myy first attemp in LeetCode did not pass because, like the comment said, I did not check curA == curB immediately after moving the two pointers one step forward.
167. Two Sum II - Input array is sorted
Given an array of integers that is already sorted in ascending order, find two numbers such that they add up to a specific target number.
The function twoSum should return indices of the two numbers such that they add up to the target, where index1 must be less than index2. Please note that your returned answers (both index1 and index2) are not zero-based.
You may assume that each input would have exactly one solution and you may not use the same element twice.
Input: numbers={2, 7, 11, 15}, target=9
Output: index1=1, index2=2
Solution:
The two sum problem in unsorted array(LeetCode problem #1) can be solved by HashMap and its solution is in this book: Chapter-Easy, Section-HashMap.
The key part of this problem is in sorted array. I use the two-pointers method where the two pointers are starting from the head and tail, respectively.
public class Solution {
public int[] twoSum(int[] numbers, int target) {
if (numbers == null) {
return null;
}
int left = 0;
int right = numbers.length - 1;
while (left <= right) {
if (numbers[left] + numbers[right] == target) {
return new int[] {left + 1, right + 1};
} else if (numbers[left] + numbers[right] < target) {
left++;
} else {
right--;
}
}
return null;
}
}
Time complexity is O(n) and space complexity is O(1).
Can the time complexity be further improved? I don't think so. Assume the input array is {1, 2, 3, ..., 8, 9, 10} and the target is 11, then there are 5 solution paris. Now increase one element of the input array by 1 and also increase the target to 12, then there is exactly one solution pair. To find the only solution pair, you need to iterate the whole array because any element of the array can be increased by one.
168. Excel Sheet Column Title
Given a positive integer, return its corresponding column title as appear in an Excel sheet.
For example:
1 -> A
2 -> B
3 -> C
...
26 -> Z
27 -> AA
28 -> AB
Solution:
public class Solution {
public String convertToTitle(int n) {
if (n == 0) {
return "";
}
return convertToTitle((n - 1) / 26) + (char)((n - 1) % 26 + 'A');
}
}
169. Majority Element
Given an array of size n, find the majority element. The majority element is the element that appears more than ⌊ n/2 ⌋ times.
You may assume that the array is non-empty and the majority element always exist in the array.
Solution:
There are multiple methods:
- sort the array first, solution is the element in the middle of the input array.
- iterate the input array and use HashMap to record elements and its frequency, if its frequency is bigger than n/2, then return it.
- Boyer–Moore majority vote algorithm(Code below)
- bit manipulation, not as good as Boyer-Moore algorithm, you can google it if interested.
Among the four methods above, I choose Boyer–Moore majority vote algorithm, whose time complexity is O(n) and space complexity is O(1).
public class Solution {
public int majorityElement(int[] nums) {
int result = 0;
int count = 0;
for (int num : nums) {
if (count == 0) {
result = num;
count = 1;
} else if (result == num) {
count++;
} else {
count--;
}
}
return result;
}
}
The Boyer-Moore algorithm can be easilly extend to other problems, for example, if the most frequent element in one array appears more than n/3 times, return it. We only need change above code a little bit: if result == num, count += 2.
171. Excel Sheet Column Number
Related to question Excel Sheet Column Title
Given a column title as appear in an Excel sheet, return its corresponding column number.
For example:
A -> 1
B -> 2
C -> 3
...
Z -> 26
AA -> 27
AB -> 28
Solution:
The solution is a reverse process to 168. Excel Sheet Column Title:
public class Solution {
public int titleToNumber(String s) {
if(s==null || s.length() == 0){
throw new IllegalArgumentException("Input is not valid!");
}
int result = 0;
int i = s.length()-1;
int t = 0;
while(i >= 0){
char curr = s.charAt(i);
result = result + (int) Math.pow(26, t) * (curr-'A'+1);
t++;
i--;
}
return result;
}
}
A good practice to write in recursion:
public class Solution {
public int titleToNumber(String s) {
if(s==null || s.length() == 0){
throw new IllegalArgumentException("Input is not valid!");
}
int result = 0;
return titleToNumber(s, s.length() - 1);
}
private int titleToNumber(String s, int i) {
if (i < 0) {
return 0;
}
return titleToNumber(s, i - 1) * 26 + (s.charAt(i) - 'A' + 1);
}
}
172. Factorial Trailing Zeroes
Given an integer n, return the number of trailing zeroes in n!.
Note: Your solution should be in logarithmic time complexity.
Solution:
It requires O(logn) time complexity. Honestly I did not get the O(logn) solution by myself. While considering the completeness of this book, I did some research online, please refer here.
The idea of a O(logn) solution is below:
For a number, the # of trailling zero depends on the # of 2s and 5s it contains, specifically, min(# of 2, # of 5). And for the number n!, # of 2s > # of 5s, for example, 5! contains one 5 and three 2. So we only need to find the # of 5s in n!. Additionally, we also need to consider some special numbers which contains multiple 5s, for example, 25, 125, etc. So the conclusion is:
# of trailing zeros of n! = int(n/5) + int(n/25) + int(n/125) + ....
public class Solution {
public int trailingZeroes(int n) {
int sum = 0;
while (n != 0) {
sum += n / 5;
n /= 5;
}
return sum;
}
}
Let's see a different implementation which can pass 500 of 502 test cases:
public class Solution {
public int trailingZeroes(int n) {
int sum = 0;
int x = 5;
while (n >= x) {
sum += n / x;
x = x * 5;;
}
return sum;
}
}
The faild test case is:
Input:
1808548329
Output:
452137078
Expected:
452137076
The reason is that when keeping timing 5, x can be 1220703125(=5^13), next time x shoule be 6103515625, while it is beyond the maximum int in Java which is 2,147,483,647. In comparison, the 1st implementaion uses division which can avoid overflow.
189. Rotate Array
Rotate an array of n elements to the right by k steps.
For example, with n = 7 and k = 3, the array [1,2,3,4,5,6,7] is rotated to [5,6,7,1,2,3,4].
Note: Try to come up as many solutions as you can, there are at least 3 different ways to solve this problem.
[show hint]
Hint: Could you do it in-place with O(1) extra space?
Solution:
This problem represents a series problems, how to transfer "I love coding" to "coding love I" ? The idea has two steps:
- reverse each word separately, got "I evol gnidoc";
- reveer the whole sentence, got "you love I";
public class Solution {
public void rotate(int[] nums, int k) {
if (nums == null) {
return;
}
k = k % nums.length;
reverse(nums, 0, nums.length - k -1);
reverse(nums, nums.length - k, nums.length - 1);
reverse(nums, 0, nums.length - 1);
}
private void reverse(int[] nums, int left, int right) {
while (left < right) {
swap(nums, left, right);
left++;
right--;
}
}
private void swap(int[] nums, int i, int j) {
int temp = nums[i];
nums[i] = nums[j];
nums[j] = temp;
}
}
190. Reverse Bits
Reverse bits of a given 32 bits unsigned integer.
For example, given input 43261596 (represented in binary as 00000010100101000001111010011100), return 964176192 (represented in binary as 00111001011110000010100101000000).
Follow up: If this function is called many times, how would you optimize it?
Solution:
In Java, int type has 32 bits.
Method 1:
iterative pick the left-most bit and insert it into the result.
public class Solution {
// you need treat n as an unsigned value
public int reverseBits(int n) {
int reversed = 0;
for (int i = 0; i < 32; i++) {
reversed = (reversed << 1) | (n & 1);
n = (n >> 1);
}
return reversed;
}
}
Method 2:
Similar to two pointers method: use left pointer and right pointer, swap(actually use xor to flip one bit) if different.
public class Solution {
// you need treat n as an unsigned value
public int reverseBits(int n) {
for (int i = 0; i < 16; i++) {
n = swapAPairOfBits(n, 32 - i - 1, i);
}
return n;
}
private int swapAPairOfBits(int n, int left, int right) {
int right_bit = (n >> right) & 1;
int left_bit = (n >> left) & 1;
// == has a higher priority than ^, so use ()
if ((right_bit ^ left_bit) == 1) {
n = n ^ ((1 << left) | (1 << right));
}
return n;
}
}
191. Number of 1 Bits
Write a function that takes an unsigned integer and returns the number of ’1' bits it has (also known as the Hamming weight).
For example, the 32-bit integer ’11' has binary representation 00000000000000000000000000001011, so the function should return 3.
Solution:
My first idea is simple:
...
while (n != 0) {
count += n & 1;
n = n >> 1;
}
return count;
But in LeetCode platform, it will exceed time limit for x is 10000000000000000000000000000000, because its time complexity is O(n) where n is the length of input's binary representation. Can it be faster? Let's start from a basic problem: determine whether a positive number x is a power of 2, i.e., x = 2n where n > 0. A naive method is to check if # of 1 bits is 1. A better solution is:
return ((x & x - 1) == 0 && x != 0);
Let' see how this one-line code works. For x = 8 whose bit representation is 0100, x - 1 is 0011, then x & x -1 is 0.
Now we can adopt the same strategy to the original problem.
public class Solution {
// you need to treat n as an unsigned value
public int hammingWeight(int n) {
if (n == 0) {
return 0;
}
int count = 1;
while ((n & (n - 1)) != 0) {
n &= n-1;
count++;
}
return count;
}
}
In the while loop, (n & (n - 1)) != 0 means that in the bit representation of n, the # of 1 bits is > 1. So after the while loop, there is one 1 bit in n's bit representation, that is why the inital count is 1.
The time complexity of this better solution is O(k) where k is # of 1 bits in input's binary representation.
198. House Robber
You are a professional robber planning to rob houses along a street. Each house has a certain amount of money stashed, the only constraint stopping you from robbing each of them is that adjacent houses have security system connected and it will automatically contact the police if two adjacent houses were broken into on the same night.
Given a list of non-negative integers representing the amount of money of each house, determine the maximum amount of money you can rob tonight without alerting the police.
Solution:
The physical meaning of M[i] is the max amount of money you can rob from the 0th house to the mth house.
The induction rule is:
M[i] = max(M[i - 1], M[i - 2] + input[i]);
The base case can be M[0] = input[0], M[1] = max(input[0], input[1]), but then you need to consider input.length == 1 in the base case. The base case in code below is M[0] = 0, M[1] = input[0].
public class Solution {
public int rob(int[] nums) {
if (nums == null || nums.length == 0) {
return 0;
}
int left = 0;
int right = nums[0];
for (int i = 1; i < nums.length; i++) {
int temp = Math.max(left + nums[i], right);
left = right;
right = temp;
}
return right;
}
}
Time complexity is O(n) and space complexity is O(1). The space complexity is optimized becasuse it only need to look back two elements in M[i] array, which are represented by left and right in the code.
202. Happy Number
Write an algorithm to determine if a number is "happy".
A happy number is a number defined by the following process: Starting with any positive integer, replace the number by the sum of the squares of its digits, and repeat the process until the number equals 1 (where it will stay), or it loops endlessly in a cycle which does not include 1. Those numbers for which this process ends in 1 are happy numbers.
Example: 19 is a happy number
12 + 92 = 82
82 + 22 = 68
62 + 82 = 100
12 + 02 + 02 = 1
Solution:
public class Solution {
public boolean isHappy(int n) {
if (n <= 0) {
return false;
}
HashSet<Integer> set = new HashSet<Integer>();
while (n != 1) {
if(set.contains(n)) {
return false;
} else {
set.add(n);
n = nextHappy(n);
}
}
return true;
}
private int nextHappy(int n) {
int result = 0;
while (n != 0) {
result += (n % 10) * (n % 10);
n /= 10;
}
return result;
}
}
203. Remove Linked List Elements
Remove all elements from a linked list of integers that have value val.
Example
Given: 1 --> 2 --> 6 --> 3 --> 4 --> 5 --> 6, val = 6
Return: 1 --> 2 --> 3 --> 4 --> 5
Solution:
Use dummy headnode to handle if remove the head of Linked List:
/**
* Definition for singly-linked list.
* public class ListNode {
* int val;
* ListNode next;
* ListNode(int x) { val = x; }
* }
*/
public class Solution {
public ListNode removeElements(ListNode head, int val) {
if (head == null) {
return null;
}
ListNode dummy = new ListNode(0);
dummy.next = head;
head = dummy;
while (head.next != null) {
if (head.next.val == val) {
head.next = head.next.next;
} else {
head = head.next;
}
}
return dummy.next;
}
}
204. Count Primes
Count the number of prime numbers less than a non-negative number, n.
Solution:
The naive method to chekc each number from 2 to n -1 will exceed time limit.
An efficient algorithm to find all prime numbers up to any given limit is Sieve of Eratosthenes.
In my opinion, it is not a good problem to test coding ability.
public class Solution {
public int countPrimes(int n) {
if (n < 3) {
return 0;
}
boolean[] primes = new boolean[n];
int count = n / 2;
for (int i = 3; i * i < n; i += 2) {
// the if statement is optional, but with its help the code is faster
if (primes[i]) {
continue;
}
for (int j = i * i; j < n; j += 2 * i) {
if (!primes[j]) {
count--;
primes[j] = true;
}
}
}
return count;
}
}
The solution above use the two refinements covered in the wikipedia page:
i * i < n- only consider odd numbers
The complexity analysis is in the wikipedia page.
205. Isomorphic Strings
Given two strings s and t, determine if they are isomorphic.
Two strings are isomorphic if the characters in s can be replaced to get t.
All occurrences of a character must be replaced with another character while preserving the order of characters. No two characters may map to the same character but a character may map to itself.
For example,
Given "egg", "add", return true.
Given "foo", "bar", return false.
Given "paper", "title", return true.
Note: You may assume both s and t have the same length.
Solution:
To check the one-to-one relationship between characters in two Strings, we use one HashpMap and one HashSet. The HaspMap stored the
public class Solution {
public boolean isIsomorphic(String s, String t) {
Map<Character, Character> map = new HashMap<>();
Set<Character> set = new HashSet<>();
for (int i = 0; i < s.length(); i++) {
char si = s.charAt(i);
char ti = t.charAt(i);
Character ch = map.get(si);
if (ch == null) {
if (set.contains(ti)) {
return false;
} else {
map.put(si, ti);
set.add(ti);
}
} else {
if (ch != ti) {
return false;
}
}
}
return true;
}
}
If use one HashMap, then you need to use the method map.containsValue() whihc is O(n).
206. Reverse Linked List
Reverse a singly linked list.
Hint: A linked list can be reversed either iteratively or recursively. Could you implement both?
Solution:
This is the most important fundamental problems in Linked List. Everybody should know how to do it iteratively and recursively.
Method 1, reverse iteratively:
/**
* Definition for singly-linked list.
* public class ListNode {
* int val;
* ListNode next;
* ListNode(int x) { val = x; }
* }
*/
public class Solution {
public ListNode reverseList(ListNode head) {
if (head == null) {
return head;
}
ListNode prev = null;
ListNode cur = head;
while (cur != null) {
ListNode next = cur.next;
cur.next = prev;
prev = cur;
cur = next;
}
return prev;
}
}
Mthod 2, reverse recursively:
/**
* Definition for singly-linked list.
* public class ListNode {
* int val;
* ListNode next;
* ListNode(int x) { val = x; }
* }
*/
public class Solution {
public ListNode reverseList(ListNode head) {
if (head == null || head.next == null) {
return head;
}
ListNode newHead = reverseList(head.next);
head.next.next = head;
head.next = null;
return newHead;
}
}
217. Contains Duplicate
Given an array of integers, find if the array contains any duplicates. Your function should return true if any value appears at least twice in the array, and it should return false if every element is distinct.
Solution:
public class Solution {
public boolean containsDuplicate(int[] nums) {
if(nums==null || nums.length==0) {
return false;
}
Set<Integer> set = new HashSet<Integer>();
for(int i: nums){
if(!set.add(i)){
return true;
}
}
return false;
}
}
The solution makes use of the return value of set.add() to be more efficient.
Time complexity is O(n) and space complexity is O(n).
219. Contains Duplicate II
Given an array of integers and an integer k, find out whether there are two distinct indices i and j in the array such that nums[i] = nums[j] and the absolute difference between i and j is at most k.
Solution:
Method 1, Use HashMap:
public class Solution {
public boolean containsNearbyDuplicate(int[] nums, int k) {
if (nums == null || nums.length == 0) {
return false;
}
Map<Integer, Integer> map = new HashMap<>();
for (int i = 0; i < nums.length; i++) {
Integer old = map.put(nums[i], i);
if (old != null && i - old <= k) {
return true;
}
}
return false;
}
}
Time complexity is O(n) and space complexity is O(n).
Method 2, use HashSet:
The size of the HashSet is always <=k.
public class Solution {
public boolean containsNearbyDuplicate(int[] nums, int k) {
if (nums == null || nums.length == 0) {
return false;
}
Set<Integer> set = new HashSet<Integer>();
for(int i = 0; i < nums.length; i++){
if(i > k) {
set.remove(nums[i - k - 1]);
}
if(!set.add(nums[i])) {
return true;
}
}
return false;
}
}
The space complexity is around the same becuase in Java, HashSet is implemented based on HashMap.
225. Implement Stack using Queues
Implement the following operations of a stack using queues.
- push(x) -- Push element x onto stack.
- pop() -- Removes the element on top of the stack.
- top() -- Get the top element.
- empty() -- Return whether the stack is empty.
Notes:
- You must use only standard operations of a queue -- which means only push to back, peek/pop from front, size, and is empty operations are valid.
- Depending on your language, queue may not be supported natively. You may simulate a queue by using a list or deque (double-ended queue), as long as you use only standard operations of a queue.
- You may assume that all operations are valid (for example, no pop or top operations will be called on an empty stack).
Solution:
Method 1, two queues, push O(1), pop/top O(n):
public class MyStack {
/** Initialize your data structure here. */
private Queue<Integer> queue1;
private Queue<Integer> queue2;
public MyStack() {
queue1 = new LinkedList<Integer>();
queue2 = new LinkedList<Integer>();
}
/** Push element x onto stack. */
public void push(int x) {
queue1.offer(x);
}
/** Removes the element on top of the stack and returns that element. */
public int pop() {
while (queue1.size() > 1) {
queue2.offer(queue1.poll());
}
Queue<Integer> tmp = queue1;
queue1 = queue2;
queue2 = tmp;
return queue2.poll();
}
/** Get the top element. */
public int top() {
while (queue1.size() > 1) {
queue2.offer(queue1.poll());
}
Integer top = queue1.peek();
queue2.offer(queue1.poll());
Queue<Integer> tmp = queue1;
queue1 = queue2;
queue2 = tmp;
return top;
}
/** Returns whether the stack is empty. */
public boolean empty() {
return queue1.isEmpty();
}
}
/**
* Your MyStack object will be instantiated and called as such:
* MyStack obj = new MyStack();
* obj.push(x);
* int param_2 = obj.pop();
* int param_3 = obj.top();
* boolean param_4 = obj.empty();
*/
Method 2, two queues, push O(n), pop/top O(1):
public class MyStack {
/** Initialize your data structure here. */
private Queue<Integer> queue1;
private Queue<Integer> queue2;
public MyStack() {
queue1 = new LinkedList<Integer>();
queue2 = new LinkedList<Integer>();
}
/** Push element x onto stack. */
public void push(int x) {
queue2.offer(x);
while (!queue1.isEmpty()) {
queue2.offer(queue1.poll());
}
Queue<Integer> tmp = queue1;
queue1 = queue2;
queue2 = tmp;
}
/** Removes the element on top of the stack and returns that element. */
public int pop() {
return queue1.poll();
}
/** Get the top element. */
public int top() {
return queue1.peek();
}
/** Returns whether the stack is empty. */
public boolean empty() {
return queue1.isEmpty();
}
}
Method 3, one queue, push O(1), pop/top O(n):
public class MyStack {
/** Initialize your data structure here. */
private Queue<Integer> queue;
public MyStack() {
queue = new LinkedList<Integer>();
}
/** Push element x onto stack. */
public void push(int x) {
queue.offer(x);
}
/** Removes the element on top of the stack and returns that element. */
public int pop() {
int size = queue.size();
while (size-- > 1) {
queue.offer(queue.poll());
}
return queue.poll();
}
/** Get the top element. */
public int top() {
int size = queue.size();
while (size-- > 1) {
queue.offer(queue.poll());
}
Integer top = queue.peek();
queue.offer(queue.poll());
return top;
}
/** Returns whether the stack is empty. */
public boolean empty() {
return queue.isEmpty();
}
}
226. Invert Binary Tree
Invert a binary tree.
4
/ \
2 7
/ \ / \
1 3 6 9
to
4
/ \
7 2
/ \ / \
9 6 3 1
Solution:
It can be solved easily by recursion.
/**
* Definition for a binary tree node.
* public class TreeNode {
* int val;
* TreeNode left;
* TreeNode right;
* TreeNode(int x) { val = x; }
* }
*/
public class Solution {
public TreeNode invertTree(TreeNode root) {
if (root == null) {
return root;
}
TreeNode tmp = root.left;
root.left = root.right;
root.right = tmp;
invertTree(root.left);
invertTree(root.right);
return root;
}
}
231. Power of Two
Given an integer, write a function to determine if it is a power of two.
Solution:
It is one step of the solution of 191. Number of 1 Bits.
public class Solution {
public boolean isPowerOfTwo(int n) {
if (n <= 0) {
return false;
}
return (n & n - 1) == 0;
}
}
232. Implement Queue using Stacks
Implement the following operations of a queue using stacks.
- push(x) -- Push element x to the back of queue.
- pop() -- Removes the element from in front of queue.
- peek() -- Get the front element.
- empty() -- Return whether the queue is empty.
Notes:
- You must use only standard operations of a stack -- which means only push to top, peek/pop from top, size, and is empty operations are valid.
- Depending on your language, stack may not be supported natively. You may simulate a stack by using a list or deque (double-ended queue), as long as you use only standard operations of a stack.
- You may assume that all operations are valid (for example, no pop or peek operations will be called on an empty queue).
Solution:
Two stacks, one for input, the other for output:
public class MyQueue {
/** Initialize your data structure here. */
private Deque<Integer> in;
private Deque<Integer> out;
private void move() {
while (!in.isEmpty()) {
out.offerFirst(in.pollFirst());
}
}
public MyQueue() {
in = new LinkedList<Integer>();
out = new LinkedList<Integer>();
}
/** Push element x to the back of queue. */
public void push(int x) {
in.offerFirst(x);
}
/** Removes the element from in front of queue and returns that element. */
public int pop() {
if (!out.isEmpty()) {
return out.pollFirst();
}
this.move();
return out.pollFirst();
}
/** Get the front element. */
public int peek() {
if (!out.isEmpty()) {
return out.peekFirst();
}
this.move();
return out.peekFirst();
}
/** Returns whether the queue is empty. */
public boolean empty() {
return in.isEmpty() && out.isEmpty();
}
}
The APIs for queue in Java are offer, poll, peek, etc. But in LeetCode solution template, they are push, pop, peek, etc.
Time complexity: push O(1), pop/top worst O(n), amortized O(1).
A follow up question: implement a deque by two stacks.
A follow up of the follow up question: in the deque implemented by two stacks, what is the time complexity for pop/top? If you are doing popFirst, popLast, popFirst, popLast, etc.
If operating a seriese popFirst, popLast, popFirst, popLast ..., the time complexity for popFirst/Last is O(n) because you need keep moving all elements from one stack to the other. Can we optimize it?
The solution is to use a 3rd stack. In the pop/top method, more specifically, in the move method, with the help of the 3rd stack, move 50% elements to each stack, so both stacks have the same size. Now the popFirst/Last has amortized O(1) time complexity.
234. Palindrome Linked List
Given a singly linked list, determine if it is a palindrome.
Follow up: Could you do it in O(n) time and O(1) space?
Solution:
- find middle ListNode,
- reverse the 2nd half of LinkedList,
- compare the 1st half and the 2nd half.
It is a good chance to practice the three basic problems.
/**
* Definition for singly-linked list.
* public class ListNode {
* int val;
* ListNode next;
* ListNode(int x) { val = x; }
* }
*/
public class Solution {
public boolean isPalindrome(ListNode head) {
if (head == null) {
return true;
}
ListNode middle = findMiddle(head);
ListNode secondHead = reverse(middle.next);
while (head != null && secondHead != null) {
if (head.val != secondHead.val) {
return false;
} else {
head = head.next;
secondHead = secondHead.next;
}
}
return secondHead == null;
}
// n1 -> n2 -> n3 ->n4, return n2
private ListNode findMiddle(ListNode head) {
ListNode slow = head;
ListNode fast = head.next;
while (fast != null && fast.next != null) {
slow = slow.next;
fast = fast.next.next;
}
return slow;
}
private ListNode reverse(ListNode head) {
ListNode prev = null;
while (head != null) {
ListNode next = head.next;
head.next = prev;
prev = head;
head = next;
}
return prev;
}
}
Time complexity is O(n) and space complexity is O(1). The original LinkedList is destroyed, if you don't like it, you can reverse the 2nd half back.
235. Lowest Common Ancestor of a Binary Search Tree
Given a binary search tree (BST), find the lowest common ancestor (LCA) of two given nodes in the BST.
According to the definition of LCA on Wikipedia: “The lowest common ancestor is defined between two nodes v and w as the lowest node in T that has both v and w as descendants (where we allow a node to be a descendant of itself).”
_______6______
/ \
___2__ ___8__
/ \ / \
0 _4 7 9
/ \
3 5
For example, the lowest common ancestor (LCA) of nodes 2 and 8 is 6. Another example is LCA of nodes 2 and 4 is 2, since a node can be a descendant of itself according to the LCA definition.
Solution:
This is an important problem about tree.
There are two cases:
- direct ancestor/descendant relationship, for example, node 2 and 4 whose LCA is 2,
- undirect ancestor/descendant relationship, for example, node 2 and 8 whose LCA is 6.
To find LCA of TreeNode p and q, it can be solved by recursion:
- base case: if root is null or p or q, return root
- recursive rule: call its left subtree and right substree to get the returned value, if both are not null, return root; if one of them is null, return that value; if both are null, return null.
How to understand it?
Case 1: when p and q are in direct ancestor/descendant relationship, for example, p is q's direct ancestor, when it meets p, it will return p and other brances will return null, when go back to previous recursion call, it has two returned value: p and null, it will keep returning p untill go back to the root.
Assume p is 2, q is 4, the returned value is shown in parenthese. Please keep in mind that nodes 0, 4, 3 and 5 are not visited.
_______6(2)_____
/ \
___2(2)__ ___8(null)__
/ \ / \
0 _4 7(null) 9(null)
/ \ / \ / \
3 5 (null) (null) (null) (null)
Case 2: assume p and q's LCA is k, the call meets p and q will return p and q, respectively, other brances which do not have p or q will return null, in the node K, it has two returned value p and q, then it will return k, and that k will be finally returned.
Assuem p is 2 and q is 8, and nodes 0, 4, 3, 5, 7, and 9 are not visited.
_______6(6)______
/ \
___2(2)__ ___8(8)__
/ \ / \
0 _4 7 9
/ \
3 5
/**
* Definition for a binary tree node.
* public class TreeNode {
* int val;
* TreeNode left;
* TreeNode right;
* TreeNode(int x) { val = x; }
* }
*/
public class Solution {
public TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) {
if (root == null || root == p || root == q) {
return root;
}
TreeNode left = lowestCommonAncestor(root.left, p, q);
TreeNode right = lowestCommonAncestor(root.right, p, q);
if (left != null && right != null) {
return root;
} else if (left != null) {
return left;
} else if (right != null) {
return right;
} else {
return null;
}
}
}
Time complexity is O(n) and space complexity is O(n) because the # of recursion levels can be n at worst case.
If the LCA of p and q is k, it means there are p and q in the tree. But if the LCA is p, then either q is in the subtree rooted at p or q does not exist. How can we tell from these two possibilities? The method is to iterate the subtree whose root is p to see if q exists or not. Because the original LCA solution does not touch the subtree rooted at p, so even doing this additional check the total time complexity is still O(n).
237. Delete Node in a Linked List
Write a function to delete a node (except the tail) in a singly linked list, given only access to that node.
Supposed the linked list is 1 -> 2 -> 3 -> 4 and you are given the third node with value 3, the linked list should become 1 -> 2 -> 4 after calling your function.
Solution:
Override the node to be deleted with its next node.
/**
* Definition for singly-linked list.
* public class ListNode {
* int val;
* ListNode next;
* ListNode(int x) { val = x; }
* }
*/
public class Solution {
public void deleteNode(ListNode node) {
node.val = node.next.val;
node.next = node.next.next;
}
}
242. Valid Anagram
Given two strings s and t, write a function to determine if t is an anagram of s.
For example, s = "anagram", t = "nagaram", return true. s = "rat", t = "car", return false.
Note: You may assume the string contains only lowercase alphabets.
Follow up: What if the inputs contain unicode characters? How would you adapt your solution to such case?
Solution:
public class Solution {
public boolean isAnagram(String s, String t) {
if (s.length() != t.length()) {
return false;
}
int[] count = new int[26];
for (int i = 0; i < s.length(); i++) {
count[s.charAt(i) - 'a']++;
}
for (int i = 0; i < t.length(); i++) {
count[t.charAt(i) - 'a']--;
if (count[t.charAt(i) - 'a'] < 0) {
return false;
}
}
return true;
}
}
If the strings have unicode, then use HashMap which works the same role as int array count in the original solution.
257. Binary Tree Paths
Given a binary tree, return all root-to-leaf paths.
For example, given the following binary tree:
1
/ \
2 3
\
5
All root-to-leaf paths are:
["1->2->5", "1->3"]
Solution:
DFS.
/**
* Definition for a binary tree node.
* public class TreeNode {
* int val;
* TreeNode left;
* TreeNode right;
* TreeNode(int x) { val = x; }
* }
*/
public class Solution {
public List<String> binaryTreePaths(TreeNode root) {
List<String> result = new ArrayList<>();
if (root == null) {
return result;
}
helper(root, String.valueOf(root.val), result);
return result;
}
private void helper(TreeNode root, String path, List<String> result) {
if (root.left == null && root.right == null) {
result.add(path);
return;
}
if (root.left != null) {
helper(root.left, path + "->" + String.valueOf(root.left.val), result);
}
if (root.right != null) {
helper(root.right, path + "->" + String.valueOf(root.right.val), result);
}
}
}
258. Add Digits
Given a non-negative integer num, repeatedly add all its digits until the result has only one digit.
For example:
Given num = 38, the process is like: 3 + 8 = 11, 1 + 1 = 2. Since 2 has only one digit, return it.
Follow up: Could you do it without any loop/recursion in O(1) runtime?
Solution:
public class Solution {
public int addDigits(int num) {
while(num > 9){
int res =0;
while(num > 0){
res += num % 10;
num /= 10;
}
num = res;
}
return num;
}
}
The O(1) solution from the internet:
public class Solution {
public int addDigits(int num) {
return num - 9 * ((num-1)/9);
}
}
263. Ugly Number
Write a program to check whether a given number is an ugly number.
Ugly numbers are positive numbers whose prime factors only include 2, 3, 5. For example, 6, 8 are ugly while 14 is not ugly since it includes another prime factor 7.
Note that 1 is typically treated as an ugly number.
Solution:
public class Solution {
public boolean isUgly(int num) {
if (num <= 0) return false;
while (num % 2 == 0) num /= 2;
while (num % 3 == 0) num /= 3;
while (num % 5 == 0) num /= 5;
return num == 1;
}
}
268. Missing Number
Given an array containing n distinct numbers taken from 0, 1, 2, ..., n, find the one that is missing from the array.
For example,
Given nums = [0, 1, 3] return 2.
Note: Your algorithm should run in linear runtime complexity. Could you implement it using only constant extra space complexity?
Solution:
There are at least three methods:
- HashSet, space O(n),
- get the sum from 0 to n if no number missing, it should be
n*(n+1)/2; then get the sum for the input array missing one number, calculate the difference of the two sums, might cause overflow if the sum is too big, - bit manipulation, use xor
public class Solution {
public int missingNumber(int[] nums) {
int result = 0;
for (int i = 0; i < nums.length; i++) {
result = result ^ (i + 1) ^ nums[i];
}
return result;
}
}
278. First Bad Version
You are a product manager and currently leading a team to develop a new product. Unfortunately, the latest version of your product fails the quality check. Since each version is developed based on the previous version, all the versions after a bad version are also bad.
Suppose you have n versions [1, 2, ..., n] and you want to find out the first bad one, which causes all the following ones to be bad.
You are given an API bool isBadVersion(version) which will return whether version is bad. Implement a function to find the first bad version. You should minimize the number of calls to the API.
Solution:
It is a binary search problem in a broader sense.
/* The isBadVersion API is defined in the parent class VersionControl.
boolean isBadVersion(int version); */
public class Solution extends VersionControl {
public int firstBadVersion(int n) {
int left = 1;
int right = n;
while (left < right - 1) {
int mid = left + (right - left) / 2;
if (isBadVersion(mid)) {
right = mid;
} else {
left = mid;
// or left = mid + 1;
}
}
if (isBadVersion(left)) {
return left;
} else {
return right;
}
}
}
283. Move Zeroes
Given an array nums, write a function to move all 0's to the end of it while maintaining the relative order of the non-zero elements.
For example, given nums = [0, 1, 0, 3, 12], after calling your function, nums should be [1, 3, 12, 0, 0].
Note:
- You must do this in-place without making a copy of the array.
- Minimize the total number of operations.
Solution:
To maintain the relative order of the non-zero elements, use two pointers moving from the head of the array.
public class Solution {
public void moveZeroes(int[] nums) {
int left = 0;
int right = 0;
while (right < nums.length) {
if (nums[right] != 0) {
swap(nums, left, right);
left++;
right++;
} else {
right++;
}
}
}
private void swap(int[] nums, int left, int right) {
int temp = nums[left];
nums[left] = nums[right];
nums[right] = temp;
}
}
290. Word Pattern
Given a pattern and a string str, find if str follows the same pattern.
Here follow means a full match, such that there is a bijection between a letter in pattern and a non-empty word in str.
Examples:
- pattern = "abba", str = "dog cat cat dog" should return true.
- pattern = "abba", str = "dog cat cat fish" should return false.
- pattern = "aaaa", str = "dog cat cat dog" should return false.
- pattern = "abba", str = "dog dog dog dog" should return false.
Notes: You may assume pattern contains only lowercase letters, and str contains lowercase letters separated by a single space.
Solution:
It is very similar to Problem 205. Isomorphic Strings.
public class Solution {
public boolean wordPattern(String pattern, String str) {
if (pattern == null && str == null) {
return true;
} else if (pattern == null || str == null) {
return false;
}
String[] words = str.split(" ");
if (words.length != pattern.length()) {
return false;
}
Map<Character, String> map= new HashMap<>();
Set<String> set = new HashSet<>();
for (int i = 0; i < words.length; i++) {
char pi = pattern.charAt(i);
String wi = words[i];
String st = map.get(pi);
if (st == null) {
if (set.contains(wi)) {
return false;
} else {
map.put(pi, wi);
set.add(wi);
}
} else {
if (!st.equals(wi)) {
return false;
}
}
}
return true;
}
}
292. Nim Game
You are playing the following Nim Game with your friend: There is a heap of stones on the table, each time one of you take turns to remove 1 to 3 stones. The one who removes the last stone will be the winner. You will take the first turn to remove the stones.
Both of you are very clever and have optimal strategies for the game. Write a function to determine whether you can win the game given the number of stones in the heap.
For example, if there are 4 stones in the heap, then you will never win the game: no matter 1, 2, or 3 stones you remove, the last stone will always be removed by your friend.
Solution:
public class Solution {
public boolean canWinNim(int n) {
return n % 4 != 0;
}
}
303. Range Sum Query - Immutable
Given an integer array nums, find the sum of the elements between indices i and j (i ≤ j), inclusive.
Example:
Given nums = [-2, 0, 3, -5, 2, -1]
sumRange(0, 2) -> 1
sumRange(2, 5) -> -1
sumRange(0, 5) -> -3
Note:
- You may assume that the array does not change.
- There are many calls to sumRange function.
Solution:
This is a prefix sum problem and it can be the 1st step or pre-processing in many DP problems.
public class NumArray {
private int[] prefixSum;
public NumArray(int[] nums) {
prefixSum = new int[nums.length];
int sum = 0;
for (int i = 0; i < nums.length; i++) {
sum += nums[i];
prefixSum[i] = sum;
}
}
public int sumRange(int i, int j) {
return i == 0 ? prefixSum[j] : prefixSum[j] - prefixSum[i - 1];
}
}
/**
* Your NumArray object will be instantiated and called as such:
* NumArray obj = new NumArray(nums);
* int param_1 = obj.sumRange(i,j);
*/
326. Power of Three
Given an integer, write a function to determine if it is a power of three.
Follow up: Could you do it without using any loop / recursion?
Solution:
It can be solved easily by iteration or recursion. Somebody posted an efficient solution in the LeetCode discussion forum:
public class Solution {
public boolean isPowerOfThree(int n) {
return (n > 0 && 1162261467 % n == 0);
// 1162261467 is 3^19, 3^20 is bigger than int
}
}
This solution works is because 3 is a prime number. For the power of 4, you need take a squre root first then it is a power of 2 problem.
342. Power of Four
Given an integer (signed 32 bits), write a function to check whether it is a power of 4.
Example:
Given num = 16, return true. Given num = 5, return false.
Follow up: Could you solve it without loops/recursion?
Solution:
In the discussion part of Problem 326. Power of Three, I said that for power of 4, take a squre root first, but somebody got a better solution:
public class Solution {
public boolean isPowerOfFour(int num) {
return num > 0 && ( num & (num - 1)) == 0 && (num & 0x55555555) != 0;
}
}
0x55555555 is to get rid of those power of 2 because the only '1' bit should be locate at the odd location, for example, 4 is 0000 0100, 16 is 0001 0000, and 64 is 0100 0000.
344. Reverse String
Write a function that takes a string as input and returns the string reversed.
Example:
Given s = "hello", return "olleh".
Solution:
public class Solution {
public String reverseString(String s) {
if (s == null) {
return null;
}
char[] ch = s.toCharArray();
int left = 0;
int right = ch.length - 1;
while (left < right) {
swap(ch, left, right);
left++;
right--;
}
return new String(ch);
}
private void swap(char[] ch, int left, int right) {
char temp = ch[left];
ch[left] = ch[right];
ch[right] = temp;
}
}
345. Reverse Vowels of a String
Write a function that takes a string as input and reverse only the vowels of a string.
Example 1:
Given s = "hello", return "holle".
Example 2:
Given s = "leetcode", return "leotcede".
Note: The vowels does not include the letter "y".
Solution:
Based on Problem 344. Reverse String.
public class Solution {
public String reverseVowels(String s) {
if (s == null) {
return null;
}
char[] ch = s.toCharArray();
int left = 0;
int right = ch.length - 1;
while (left < right) {
if (isVowel(ch[left]) && isVowel(ch[right])) {
swap(ch, left, right);
left++;
right--;
}
if (!isVowel(ch[left])) {
left++;
}
if (!isVowel(ch[right])){
right--;
}
}
return new String(ch);
}
private void swap(char[] ch, int left, int right) {
char temp = ch[left];
ch[left] = ch[right];
ch[right] = temp;
}
private boolean isVowel(char c) {
return c == 'a' || c == 'e' || c == 'i' || c == 'o' || c == 'u' || c == 'A' || c == 'E' || c == 'I' || c == 'O' || c == 'U';
}
}
An alternative way is to use a HashSet to check a char is a vowel or not.
349. Intersection of Two Arrays
Given two arrays, write a function to compute their intersection.
Example:
Given nums1 = [1, 2, 2, 1], nums2 = [2, 2], return [2].
Note:
- Each element in the result must be unique.
- The result can be in any order.
Solution:
There are at least three methods:
- sort the two arrays, use two pointers method,
- HashSet
- binary search, if one of the array is short, the other array is long
Method 1:
public class Solution {
public int[] intersection(int[] nums1, int[] nums2) {
if (nums1 == null || nums2 == null) {
return null;
}
Arrays.sort(nums1);
Arrays.sort(nums2);
int[] temp = new int[nums1.length];
int i = 0;
int j = 0;
int index = 0;
while (i < nums1.length && j < nums2.length) {
if (nums1[i] == nums2[j]) {
if (index == 0 || nums1[i] != temp[index - 1] ) {
temp[index++] = nums1[i];
}
i++;
j++;
} else if (nums1[i] < nums2[j]) {
i++;
} else {
j++;
}
}
int[] result = new int[index];
for (int k = 0; k < index; k++) {
result[k] = temp[k];
}
return result;
}
}
Space complexity is O(n). If no need to de-duplicate the result, then the array temp is not necessary and space complexity is O(1).
Method 2:
public class Solution {
public int[] intersection(int[] nums1, int[] nums2) {
if (nums1 == null || nums2 == null) {
return null;
}
if (nums2.length < nums1.length) {
int[] temp = nums1;
nums1 = nums2;
nums2 = temp;
}
Set<Integer> set = new HashSet<>();
for (int i = 0; i < nums1.length; i++) {
set.add(nums1[i]);
}
Set<Integer> resultSet = new HashSet<>();
for (int i = 0; i < nums2.length; i++) {
if (set.contains(nums2[i]) && !resultSet.contains(nums2[i])) {
resultSet.add(nums2[i]);
}
}
int[] result = new int[resultSet.size()];
int index = 0;
for (Integer num : resultSet) {
result[index++] = num;
}
return result;
}
}
Time complexity is O(m+n) where m and n is the size of two arrays, respectively. Space complexity is O(n) where is the size of the smaller array because at the beginning we store the smaller array into the HashSet.
If you don't know how to iterate over a Map/Set in Java, google it.
Method 3:
Sort the array nums1 first, then for each number in the array nums2 do a binary search in nums1.
When are we going to use this method?
If the array nums1 is sorted and very long, for example, 1 million, while the array nums2 is very short, for example, 10, then the binary search method is very useful because its time complexity is 10*log(1million). Considering the cost to sort an array, then this method is not significantly efficient for the original problem.
350. Intersection of Two Arrays II
Given two arrays, write a function to compute their intersection.
Example:
Given nums1 = [1, 2, 2, 1], nums2 = [2, 2], return [2, 2].
Note:
- Each element in the result should appear as many times as it shows in both arrays.
- The result can be in any order.
Follow up:
- What if the given array is already sorted? How would you optimize your algorithm?
- What if nums1's size is small compared to nums2's size? Which algorithm is better?
- What if elements of nums2 are stored on disk, and the memory is limited such that you cannot load all elements into the memory at once?
Solution:
Discussions are in the Problem 349. Intersection of Two Arrays.
371. Sum of Two Integers
Calculate the sum of two integers a and b, but you are not allowed to use the operator + and -.
Example:
Given a = 1 and b = 2, return 3.
Solution:
The sum of adding can be decomposed into two parts, for example, to calcuate 394 + 657:
- adding not considering carry, it is 941,
- carry, it is 011, then move one bit left, it is 0110.
The sum is 394 + 657 = 1051 = 941 + 0110.
Then how to get these two steps by bit manipulation?
- adding not considering carry: xor, because 0 ^ 0 = 0, 0 ^ 1 = 1, 1 ^ 0 = 1 and 1 ^ 1 = 0.
- carry: and(&) then << 1, because 0 & 0 = 0, 0 & 1 = 1, 1 & 0 = 1 and 1 & 1 = 1.
After we got the sum without carry and the carry, how to add them? iteratively or recursively apply this method until carry becomes zero, the answer is the sum.
public class Solution {
public int getSum(int a, int b) {
if (b == 0) {
return a;
}
int sum = a ^ b;
int carry = (a & b) << 1;
return getSum(sum, carry);
}
}
A follow up question: How to substract two numbers, for example, a - b? Two methods:
- a - b = a + (-b) so getSum(a, ~b + 1) works by Two's Complement,
- similar idea as getSum(), please refer here.
public int getSubtract(int a, int b) {
while (b != 0) {
int borrow = (~a) & b;
a = a ^ b;
b = borrow << 1;
}
return a;
}
367. Valid Perfect Square
Given a positive integer num, write a function which returns True if num is a perfect square else False.
Note: Do not use any built-in library function such as sqrt.
Example 1:
Input: 16
Returns: True
Example 2:
Input: 14
Returns: False
Solution:
Method 1, binary search:
public class Solution {
public boolean isPerfectSquare(int num) {
if (num < 1) {
return false;
} else if (num == 1) {
return true;
}
int left = 0;
int right = num;
while (left <= right) {
int mid = left + (right - left) / 2;
if (mid == num / mid && num % mid == 0) {
return true;
} else if (num / mid < mid) {
right = mid - 1;
} else {
left = mid + 1;
}
}
return false;
}
}
Time complexity is O(logn).
Method 2, iteration:
public class Solution {
public boolean isPerfectSquare(int num) {
if (num < 1) {
return false;
}
for (int i = 1; i <= num / i; i++) {
if (i * i == num) {
return true;
}
}
return false;
}
}
In the for loop, if it is for (int i = 1; i * i <= num; i++), it will fail on the test case where num = 2147483647 due to overflow.
Time complexity is O(sqrt(n)).
Method 3, pure math:
Perfect square is the sum of a consequent set of odd numbers, for example,
4 = 1 + 3
9 = 1 + 3 + 5
16 = 1 + 3 + 5 + 7
The proof is that, (n + 1)2 - n2 = 2 * n + 1, or just see the picture below,
public class Solution {
public boolean isPerfectSquare(int num) {
if (num < 1) {
return false;
}
int i = 1;
while (num > 0) {
num -= i;
i += 2;
}
return num == 0;
}
}
Time complexity is O(sqrt(n)).
Method 4, Newton's method, more specifically, Babylonian method:
public class Solution {
public boolean isPerfectSquare(int num) {
if (num < 1) {
return false;
}
long t = num;
while (t * t > num) {
t = (t + num / t) / 2;
}
return t * t == num;
}
}
Method 5:
Somebody post a O(1) solution, please refer here.
374. Guess Number Higher or Lower
We are playing the Guess Game. The game is as follows:
I pick a number from 1 to n. You have to guess which number I picked.
Every time you guess wrong, I'll tell you whether the number is higher or lower.
You call a pre-defined API guess(int num) which returns 3 possible results (-1, 1, or 0):
-1 : My number is lower
1 : My number is higher
0 : Congrats! You got it!
Example:
n = 10, I pick 6.
Return 6.
Solution:
The idea is Binary Search:
/* The guess API is defined in the parent class GuessGame.
@param num, your guess
@return -1 if my number is lower, 1 if my number is higher, otherwise return 0
int guess(int num); */
public class Solution extends GuessGame {
public int guessNumber(int n) {
int left = 0;
int right = n;
while (left <= right) {
int mid = left + (right - left) / 2;
int tmp = guess(mid);
if (tmp == 0) {
return mid;
} else if (tmp < 0) {
right = mid - 1;
} else {
left = mid + 1;
}
}
return left;
}
}
383. Random Note
Given an arbitrary ransom note string and another string containing letters from all the magazines, write a function that will return true if the ransom note can be constructed from the magazines ; otherwise, it will return false.
Each letter in the magazine string can only be used once in your ransom note.
Note: You may assume that both strings contain only lowercase letters.
canConstruct("a", "b") -> false
canConstruct("aa", "ab") -> false
canConstruct("aa", "aab") -> true
Solution:
public class Solution {
public boolean canConstruct(String ransomNote, String magazine) {
if (ransomNote == null && magazine == null) {
return true;
} else if (ransomNote == null || magazine == null) {
return false;
}
int[] cnt = new int[26];
for (int i = 0; i < magazine.length(); i++) {
cnt[magazine.charAt(i) - 97]++;
}
for (int i = 0; i < ransomNote.length(); i++) {
if (--cnt[ransomNote.charAt(i) - 97] < 0) {
return false;
}
}
return true;
}
}
387. First Unique Character in a String
Given a string, find the first non-repeating character in it and return it's index. If it doesn't exist, return -1.
Examples:
s = "leetcode"
return 0.
s = "loveleetcode",
return 2.
Solution:
public class Solution {
public int firstUniqChar(String s) {
if (s == null) {
return -1;
}
int[] count = new int[26];
for (int i = 0; i < s.length(); i++) {
count[s.charAt(i) - 97]++;
}
for (int i = 0; i < s.length(); i++) {
if (count[(s.charAt(i) - 97)] == 1) {
return i;
}
}
return -1;
}
}
389. Find the Difference
Given two strings s and t which consist of only lowercase letters.
String t is generated by random shuffling string s and then add one more letter at a random position.
Find the letter that was added in t.
Example:
Input:
s = "abcd"
t = "abcde"
Output:
e
Explanation:
'e' is the letter that was added.
Solution:
This is very similar to Problem 268. Missing Number, so all the three methods discussed in Problem 268 can be used here.
Use xor:
public class Solution {
public char findTheDifference(String s, String t) {
// assume inputs are valid to skip sanity check
char[] si = s.toCharArray();
char[] ti = t.toCharArray();
int result = 0;
for (char i : si) {
result ^= (int) i;
}
for (char i : ti) {
result ^= (int) i;
}
return (char) result;
}
}
The Fourth method based on assuming only lowercase letters:
public class Solution {
public char findTheDifference(String s, String t) {
// assume inputs are valid to skip sanity check
int[] count = new int[26];
for (int i = 0; i < t.length(); i++) {
count[t.charAt(i) - 97]++;
}
for (int i = 0; i < s.length(); i++) {
count[s.charAt(i) - 97]--;
}
for (int i = 0; i < 26; i++) {
if (count[i] == 1) {
return (char) (i + 97);
}
}
return (char) 0;
}
}
400. Nth Digit
Find the nth digit of the infinite integer sequence 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, ...
Note:
n is positive and will fit within the range of a 32-bit signed integer (n < 231).
Example 1:
Input:
3
Output:
3
Example 2:
Input:
11
Output:
0
Explanation:
The 11th digit of the sequence 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, ... is a 0, which is part of the number 10.
Solution:
There are 9*1 one-digit numbers, 90*2 two digits numbers, 900*3 three-digits numbers, so on so forth.
public class Solution {
public int findNthDigit(int n) {
int len = 1;
long count = 9;
int start = 1;
while (n > len * count) {
n -= len * count;
len += 1;
count *= 10;
start *= 10;
}
start += (n - 1) / len;
String s = Integer.toString(start);
return Character.getNumericValue(s.charAt((n - 1) % len));
}
}
In the while loop, it will check one-digit numbers, two-digit numbers, ... , and start is the 1st number in the corresponding k-digit numbers range. After the while loop, (n - 1) / len is the index of n in k-digit numbers range. start += (n - 1) / len is the number we want.
405. Convert a Number to Hexadecimal
Given an integer, write an algorithm to convert it to hexadecimal. For negative integer, two’s complement method is used.
Note:
- All letters in hexadecimal (a-f) must be in lowercase.
- The hexadecimal string must not contain extra leading 0s. If the number is zero, it is represented by a single zero character '0'; otherwise, the first character in the hexadecimal string will not be the zero character.
- The given number is guaranteed to fit within the range of a 32-bit signed integer.
- You must not use any method provided by the library which converts/formats the number to hex directly.
Example 1:
Input:
26
Output:
"1a"
Example 2:
Input:
-1
Output:
"ffffffff"
Solution:
In binary representation, every four digits represent a hexadecimal digit.
public class Solution {
public String toHex(int num) {
if(num == 0) {
return "0";
}
String ans = "";
int len = 0;
while(num != 0 && len < 8) {
int bit = num & 15;
if(bit < 10) {
ans = (char)('0' + bit) + ans;
}
else {
ans = (char)('a' + bit - 10) + ans;
}
num >>= 4;
len++;
}
return ans;
}
}
409. Longest Palindrome
Given a string which consists of lowercase or uppercase letters, find the length of the longest palindromes that can be built with those letters.
This is case sensitive, for example "Aa" is not considered a palindrome here.
Note:
Assume the length of given string will not exceed 1,010.
Example:
Input:
"abccccdd"
Output:
7
Explanation:
One longest palindrome that can be built is "dccaccd", whose length is 7.
Solution:
Because the ordering of input string can be disrupted, so we only need to count the number of letters who are showing even times. Finally check if there are letters showing odd times exist, answer plus one.
public class Solution {
public int longestPalindrome(String s) {
if(s==null || s.length()==0) {
return 0;
}
Set<Character> set = new HashSet<Character>();
int count = 0;
for(int i = 0; i < s.length(); i++) {
if(set.contains(s.charAt(i))) {
set.remove(s.charAt(i));
count++;
}else{
set.add(s.charAt(i));
}
}
if(!set.isEmpty()) {
return count*2+1;
}
return count*2;
}
}
412. Fizz Buzz
Write a program that outputs the string representation of numbers from 1 to n.
But for multiples of three it should output “Fizz” instead of the number and for the multiples of five output “Buzz”. For numbers which are multiples of both three and five output “FizzBuzz”.
Example:
n = 15,
Return:
[
"1",
"2",
"Fizz",
"4",
"Buzz",
"Fizz",
"7",
"8",
"Fizz",
"Buzz",
"11",
"Fizz",
"13",
"14",
"FizzBuzz"
]
Solution:
public class Solution {
public List<String> fizzBuzz(int n) {
List<String> results = new ArrayList<String>();
if (n <= 0) {
return results;
}
for (int i = 1; i <= n; i++) {
if (i % 15 == 0) {
results.add("FizzBuzz");
} else if (i % 5 == 0) {
results.add("Buzz");
} else if (i % 3 == 0) {
results.add("Fizz");
} else {
results.add(String.valueOf(i));
}
}
return results;
}
}
414. Third Maximum Number
Given a non-empty array of integers, return the third maximum number in this array. If it does not exist, return the maximum number. The time complexity must be in O(n).
Example 1:
Input: [3, 2, 1]
Output: 1
Explanation: The third maximum is 1.
Example 2:
Input: [1, 2]
Output: 2
Explanation: The third maximum does not exist, so the maximum (2) is returned instead.
Example 3:
Input: [2, 2, 3, 1]
Output: 1
Explanation: Note that the third maximum here means the third maximum distinct number.
Both numbers with value 2 are both considered as second maximum.
Solution:
public class Solution {
public int thirdMax(int[] nums) {
long max1 = Long.MIN_VALUE;
long max2 = Long.MIN_VALUE;
long max3 = Long.MIN_VALUE;
for (int n : nums) {
if (max1 < n) {
max3 = max2;
max2 = max1;
max1 = n;
} else if (max2 < n && n < max1) {
max3 = max2;
max2 = n;
} else if (max3 < n && n < max2) {
max3 = n;
}
}
return max3 == Long.MIN_VALUE ? (int) max1 : (int) max3;
}
}
415. Add Strings
Given two non-negative integers num1 and num2 represented as string, return the sum of num1 and num2.
Note:
- The length of both num1 and num2 is < 5100.
- Both num1 and num2 contains only digits 0-9.
- Both num1 and num2 does not contain any leading zero.
- You must not use any built-in BigInteger library or convert the inputs to integer directly.
Solution:
public class Solution {
public String addStrings(String num1, String num2) {
StringBuilder sb = new StringBuilder();
int carry = 0;
for( int i = num1.length() - 1, j = num2.length() - 1; i >= 0 || j >= 0 || carry == 1; i--, j--) {
int x = i < 0 ? 0 : num1.charAt(i) - '0';
int y = j < 0 ? 0 : num2.charAt(j) - '0';
sb.append((x + y + carry) % 10);
carry = (x + y + carry) / 10;
}
return sb.reverse().toString();
}
}
434. Number of Segments in a String
Count the number of segments in a string, where a segment is defined to be a contiguous sequence of non-space characters.
Please note that the string does not contain any non-printable characters.
Example:
Input: "Hello, my name is John"
Output: 5
Solution:
The 1st character in one word is non-space letter and its previous character must be space, and don't forget consider the 1st word where i == 0.
public class Solution {
public int countSegments(String s) {
if (s == null || s.length() == 0) {
return 0;
}
int result = 0;
for (int i = 0; i < s.length(); i++) {
if (s.charAt(i) != ' ' && (i == 0 || s.charAt(i - 1) == ' ')) {
result++;
}
}
return result;
}
}
437. Path Sum III
You are given a binary tree in which each node contains an integer value.
Find the number of paths that sum to a given value.
The path does not need to start or end at the root or a leaf, but it must go downwards (traveling only from parent nodes to child nodes).
The tree has no more than 1,000 nodes and the values are in the range -1,000,000 to 1,000,000.
Example:
root = [10,5,-3,3,2,null,11,3,-2,null,1], sum = 8
10
/ \
5 -3
/ \ \
3 2 11
/ \ \
3 -2 1
Return 3. The paths that sum to 8 are:
1. 5 -> 3
2. 5 -> 2 -> 1
3. -3 -> 11
Solution:
This is a recursion problem involved tree and HashMap. It requires a through understanding of recursion. I am surprised that this problem is categorized to "easy" in LeetCode.
A simple version of this problem: each node represents a number and find out whether existing a path that sums to a given number. Let's call it Problem A.
A further simplified problem: given an array, find out whether existing a subarray whose sum is a given number. Let's call it Problem B.
How to solve Problem B? The idea is to use a HashSet to store prefix sum. Iteratively scan each number in the array and calculate the current sum, then check if curSum - target exists in the HashSet, if so return true; otherwise add curSum to the HashSet. Maybe you can get the idea quickly from the code:
// input parameters: int[] nums, int target
Set<Integer> set = new HashSet<>();
curSum = 0;
for (int i : nums) {
curSum += i;
if (set.contains(curSum - target)) {
return true;
} else {
set.add(curSum);
}
}
return false;
Now you can see that, after nums[i] is visited, the HashSet stores prefix sums from 0th element to the 0th element, 1st element, 2nd element, ... , ith element. If curSum - target exists in the HashSet, it means there is one subarray ended at current element, whose sum is target. Time complexity is O(n) and space complexity is O(n).
Now let's go to Problem A. Because array is 1D data structure and tree is 1.5D data structure, so the idea to use a HashSet to store the prefix sum also works on Problem A. So the HashSet stores all the prefix sum corresponding to the current node, when visiting the node, calcuate the currrent sum then check if curSum - target exists in the HashSet. One thing worthes mention: if the node's value can be negative, when returning from a child node to its parent node, the HashSet needs to be updated as following:
- from the HashSet, remove the
curSumof the child, if it is added to the HashSet successfully when visiting the child node, - do nothing to the HashSet if the
curSumof the child can not add to the HashSet when visiting the child node(menas the numbercurSumalready exists).
If all nodes' values are positive, then just remove curSum when it goes back to the parent node. The key point here is that make sure the HashSet is always correctly updated when iterating the tree.
Now it is time for the original problem which requires the number of paths. Because nodes' values can be negative, it means that there might be multiple paths whose sum is the given value. So we need to use a HashMap whose key is the prefix sum and the value is the corresponding frequency.
/**
* Definition for a binary tree node.
* public class TreeNode {
* int val;
* TreeNode left;
* TreeNode right;
* TreeNode(int x) { val = x; }
* }
*/
public class Solution {
public int pathSum(TreeNode root, int sum) {
if (root == null) {
return 0;
}
Map<Integer, Integer> map = new HashMap<>();
// if sum == target, map.get(sum - target) return 1
map.put(0, 1);
return findPathSum(root, 0, sum, map);
}
private int findPathSum(TreeNode curr, int sum, int target, Map<Integer, Integer> map) {
if (curr == null) {
return 0;
}
// update the prefix sum by adding the current val
sum += curr.val;
// get the number of valid path, ended by the current node
int numPathToCurr = map.getOrDefault(sum - target, 0);
// update the map with the current sum, so the map is good to be passed to the next recursion
map.put(sum, map.getOrDefault(sum, 0) + 1);
// add the 3 parts discussed in 8. together
int res = numPathToCurr + findPathSum(curr.left, sum, target, map) + findPathSum(curr.right, sum, target, map);
// restore the map, as the recursion goes from the bottom to the top
map.put(sum, map.get(sum) - 1);
return res;
}
}
Time complexity is O(n) and space complexity is O(h) where h is the height of tree and in worst case it can be n.
438. Find All Anagrams in a String
Given a string s and a non-empty string p, find all the start indices of p's anagrams in s.
Strings consists of lowercase English letters only and the length of both strings s and p will not be larger than 20,100.
The order of output does not matter.
Example 1:
Input:
s: "cbaebabacd" p: "abc"
Output:
[0, 6]
Explanation:
The substring with start index = 0 is "cba", which is an anagram of "abc".
The substring with start index = 6 is "bac", which is an anagram of "abc".
Example 2:
Input:
s: "abab" p: "ab"
Output:
[0, 1, 2]
Explanation:
The substring with start index = 0 is "ab", which is an anagram of "ab".
The substring with start index = 1 is "ba", which is an anagram of "ab".
The substring with start index = 2 is "ab", which is an anagram of "ab".
Solution:
This is a typical fixed-width sliding window problem. The difficulty level should be "medium" rather than "easy".
To check whether the string segment in the sliding window is an anagram of the target string, we need a HashMap whose key is letter and value is frequency, to store the letters are not yet matched, and a counter which counts the number of letters needs to be matched. At the beginning, put the target string into the HashSet and counter is the length of the target string, because at that time no letter has been matched yet.
When the right boarder of window is moved forward to take a new letter, update the HashSet and if it is matched, counter--. When the left boarder of window is moved to dump a letter, also update the HashSet and counter. When counter is 0, it means the letters in the window is an anagram.
Because the string only contains lowercase letters so we can use an array which plays the same role as the HashMap in previous discussion.
public class Solution {
public List<Integer> findAnagrams(String s, String p) {
List<Integer> ans = new ArrayList<>();
if (s == null || p == null || s.length() == 0 || p.length() == 0 || s.length() < p.length()) {
return ans;
}
int[] map = new int[26];
for (int i = 0; i < p.length(); i++) {
map[p.charAt(i) - 'a']++;
}
int j = 0;
int needToMatch = p.length();
for (int i = 0; i < s.length(); i++) {
while (j < s.length() && j - i < p.length()) {
int count = map[s.charAt(j) - 'a'];
map[s.charAt(j) - 'a']--;
if (count > 0) {
needToMatch--;
}
j++;
}
if (needToMatch == 0) {
ans.add(i);
}
int count = map[s.charAt(i) - 'a'];
if (count >= 0) {
needToMatch++;
}
map[s.charAt(i) - 'a']++;
}
return ans;
}
}
441. Arranging Coins
You have a total of n coins that you want to form in a staircase shape, where every k-th row must have exactly k coins.
Given n, find the total number of full staircase rows that can be formed.
n is a non-negative integer and fits within the range of a 32-bit signed integer.
Example 1:
n = 5
The coins can form the following rows:
¤
¤ ¤
¤ ¤
Because the 3rd row is incomplete, we return 2.
Example 2:
n = 8
The coins can form the following rows:
¤
¤ ¤
¤ ¤ ¤
¤ ¤
Because the 4th row is incomplete, we return 3.
Solution:
Solve the equation: x * (x + 1) < 2 * n.
public class Solution {
public int arrangeCoins(int n) {
return (int) ((Math.sqrt(1 + 8.0 * n) - 1) / 2);
}
}
Note that 8.0 * n is important because it will make Java implicitly autoboxed the intermediate result into double data type. The code will not work if it is simply 8 * n.
447. Number of Boomerangs
Given n points in the plane that are all pairwise distinct, a "boomerang" is a tuple of points (i, j, k) such that the distance between i and j equals the distance between i and k (the order of the tuple matters).
Find the number of boomerangs. You may assume that n will be at most 500 and coordinates of points are all in the range [-10000, 10000] (inclusive).
Example:
Input:
[[0,0],[1,0],[2,0]]
Output:
2
Explanation:
The two boomerangs are [[1,0],[0,0],[2,0]] and [[1,0],[2,0],[0,0]]
Solution:
In the tuple (i, j, k), assuming the point i is fixed, and there are k points whose distances between themselves and the point i is the same, then there are k(k-1) boomerang tuples. And every points can be considered as the point i. To record the distance and the number of points who have the same distance, use HashMap whose key is distance, value is number of points.
public class Solution {
public int numberOfBoomerangs(int[][] points) {
if (points == null || points.length == 0 || points[0] == null || points[0].length == 0) {
return 0;
}
int result = 0;
for (int i = 0; i < points.length; i++) {
Map<Integer, Integer> map = new HashMap<>();
for (int j = 0; j < points.length; j++) {
if (i == j) {
continue;
}
int dis = getDis(points, i, j);
Integer tmp = map.get(dis);
if (tmp == null) {
map.put(dis, 1);
} else {
map.put(dis, tmp + 1);
}
}
for (int num : map.values()) {
result += num * (num - 1);
}
}
return result;
}
private int getDis(int[][] points, int i, int j) {
int x = points[i][0] - points[j][0];
int y = points[i][1] - points[j][1];
return x * x + y * y;
}
}
448. Find All Numbers Disappeared in an Array
Given an array of integers where 1 ≤ a[i] ≤ n (n = size of array), some elements appear twice and others appear once.
Find all the elements of [1, n] inclusive that do not appear in this array.
Could you do it without extra space and in O(n) runtime? You may assume the returned list does not count as extra space.
Example:
Input:
[4,3,2,7,8,2,3,1]
Output:
[5,6]
Solution:
Method 1:
Because it requires O(1) space, so the first idea I came up with is swap to put numbers at their right positions. The final state we want is that if number k appears once then its index is k - 1; if it appears more than once, then it also occupies other indexs whose corresponding numbers disappear. For example, the input array is
[7, 6, 5, 3, 3, 1, 4]
Its final state should be
[1, 5, 3, 4, 5, 6, 7]
If input[i] != i + 1, then swap input[i] with input[input[i] - 1]. Following this idea, we get
[4, 1, 3, 5, 5, 6, 7]
which is wrong. The reason is that after swap, number at index input[i] - 1 is correct, but number at index i is not correct yet. So we need keep swapping until either input[i] == i + 1 which means number at index i is correct, or input[input[i] - 1] == input[i] which means input[i] might not be at its right position, but its right position has been taken by the right number equals to input[i], in other words, number input[i] appears more than once.
Correctness proof: if swap, it can put one number into its right position without altering the numbers which have been put into their right positions previously. It is becuase the swap condition is nums[i] != i + 1 && nums[nums[i] - 1] != nums[i]. So ater the iteration, each element is either at its right position or occupies the indexs whose corresponding numbers doesn't show.
public class Solution {
public List<Integer> findDisappearedNumbers(int[] nums) {
List<Integer> result = new ArrayList<>();
if (nums == null || nums.length == 0) {
return result;
}
for (int i = 0; i < nums.length; i++) {
while (nums[i] != i + 1 && nums[nums[i] - 1] != nums[i]) {
swap(nums, i, nums[i] - 1);
}
}
for (int i = 0; i < nums.length; i++) {
if (nums[i] != i + 1) {
result.add(i + 1);
}
}
return result;
}
private void swap(int[] nums, int i, int j) {
int temp = nums[i];
nums[i] = nums[j];
nums[j] = temp;
}
}
Time complexity is O(n) although it has while loop inside the for loop. If you understand its correctness, you can get the time complexity. Space complexity is O(1).
Method 2:
When visit input[i], can we record its appearance? input[input[i] -1]++? Of course it is wrong. But we can do input[input[i] -1] += n where n is the size of input array to record the appearance. The reason is that
- the initial value at index
input[i] - 1can be found byinput[input[i] - 1] % n. - finally ecah element in the array wiil be x + k * n where x<=n is the initial value, and k will be the frequecny we want.
public class Solution {
public List<Integer> findDisappearedNumbers(int[] nums) {
List<Integer> result = new ArrayList<>();
if (nums == null || nums.length == 0) {
return result;
}
int size = nums.length;
for (int i = 0; i < size; i++) {
nums[(nums[i] - 1) % size] += size;
}
for (int i = 0; i < size; i++) {
if (nums[i] <= size) {
result.add(i + 1);
}
}
return result;
}
}
Method 3, from the internet:
To record the appearance of one number, set the number at its correct index to be negative value of the initial value, because by doing that the initial value can be tracd back.
public class Solution {
public List<Integer> findDisappearedNumbers(int[] nums) {
List<Integer> result = new ArrayList<>();
if (nums == null || nums.length == 0) {
return result;
}
int size = nums.length;
for (int i = 0; i < size; i++) {
int index = Math.abs(nums[i]) - 1;
if (nums[index] > 0) {
nums[index] = -nums[index];
}
}
for (int i = 0; i < size; i++) {
if (nums[i] > 0) {
result.add(i + 1);
}
}
return result;
}
}
Both method 2 and method 3 are using the array itself to record the appearance of numbers and guarantee the initial values can be traced back. Method 2 can return the frequency of each number appears, but it might cause overflow if x + k * n is very big.
453. Minimum Moves to Equal Array Elements
Given a non-empty integer array of size n, find the minimum number of moves required to make all array elements equal, where a move is incrementing n - 1 elements by 1.
Example:
Input:
[1,2,3]
Output:
3
Explanation:
Only three moves are needed (remember each move increments two elements):
[1,2,3] => [2,3,3] => [3,4,3] => [4,4,4]
Solution:
Incrementing n - 1 elements by 1 is equal to subtracting 1 from one element. To make all elements in the array equal, the best way to do is to make all elements in the array equal to the min element.
public class Solution {
public int minMoves(int[] nums) {
if (nums == null || nums.length == 0) {
throw new IllegalArgumentException("nums must be non-empty");
}
int sum = 0;
int min = Integer.MAX_VALUE;
for (int i = 0; i < nums.length; i++) {
sum += nums[i];
min = Math.min(min, nums[i]);
}
return sum - min * nums.length;
}
}
455. Assign Cookies
Assume you are an awesome parent and want to give your children some cookies. But, you should give each child at most one cookie. Each child i has a greed factor gi, which is the minimum size of a cookie that the child will be content with; and each cookie j has a size sj. If sj >= gi, we can assign the cookie j to the child i, and the child i will be content. Your goal is to maximize the number of your content children and output the maximum number.
Note: You may assume the greed factor is always positive. You cannot assign more than one cookie to one child.
Example 1:
Input: [1,2,3], [1,1]
Output: 1
Explanation: You have 3 children and 2 cookies. The greed factors of 3 children are 1, 2, 3.
And even though you have 2 cookies, since their size is both 1, you could only make the child whose greed factor is 1 content.
You need to output 1.
Example 2:
Input: [1,2], [1,2,3]
Output: 2
Explanation: You have 2 children and 3 cookies. The greed factors of 2 children are 1, 2.
You have 3 cookies and their sizes are big enough to gratify all of the children,
You need to output 2.
Solution:
For the smallest child, feed it with smallest cookie, if not match, use a larger cookie, otherwise use next larger cookie to feed next child.
public class Solution {
public int findContentChildren(int[] g, int[] s) {
if (g == null || s == null) {
throw new IllegalArgumentException("input not valid");
}
Arrays.sort(g);
Arrays.sort(s);
int j = 0;
for (int i = 0; i < s.length && j < g.length; i++) {
if (s[i] >= g[j]) {
j++;
}
}
return j;
}
}
459. Repeated Substring Pattern
Given a non-empty string check if it can be constructed by taking a substring of it and appending multiple copies of the substring together. You may assume the given string consists of lowercase English letters only and its length will not exceed 10000.
Example 1:
Input: "abab"
Output: True
Explanation: It's the substring "ab" twice.
Example 2:
Input: "aba"
Output: False
Example 3:
Input: "abcabcabcabc"
Output: True
Explanation: It's the substring "abc" four times. (And the substring "abcabc" twice.)
Solution:
461. Hamming Distance
The Hamming distance between two integers is the number of positions at which the corresponding bits are different.
Given two integers x and y, calculate the Hamming distance.
Note: 0 ≤ x, y < 231.
Example:
Input: x = 1, y = 4
Output: 2
Explanation:
1 (0 0 0 1)
4 (0 1 0 0)
↑ ↑
The above arrows point to positions where the corresponding bits are different.
Solution:
public class Solution {
public int hammingDistance(int x, int y) {
int xor = x ^ y;
int result = 0;
while (xor != 0) {
result += xor & 1;
xor = xor >> 1;
}
return result;
}
}