Friday, September 29, 2017
Thursday, September 28, 2017
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
You may assume
pattern contains only lowercase letters, and str contains lowercase letters separated by a single space.
Solution:
There are multiple ways to solve this problem. But the idea is basically the same.
I will post the most concise one that I saw in the discussion section.
public boolean wordPattern(String pattern, String str) {
String[] words=str.split(" ");
HashMap map=new HashMap();
if(words.length!=pattern.length()) return false;
for(Integer i=0;i<words.length;i++){
if(map.put(words[i],i)!=map.put(pattern.charAt(i),i)) return false;
}
return true;
}
292. Nim Game
ou 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
Case 1. If there are 4 stones, no matter how many stones you remove, the last one will be removed by your friend.
Case 2: But if there are 5 stones, you can remove 1, then your friend is going to remove first for the remaining 4, which you can always remove the last one. Similarly for 6 and 7, you can always remove some stones to only leave 4 stones.
Case 3: But if there are 8 stones, and your friend is smart will always leave 4 stones and let you remove first and it becomes case 1
So we find that if n%4==0 which means you will lose the game for sure, otherwise you will be winner.
public boolean canWinNim(int n) {
return n%4!=0;
}
284. Peeking Iterator
Given an Iterator class interface with methods:
next() and hasNext(), design and implement a PeekingIterator that support the peek() operation -- it essentially peek() at the element that will be returned by the next call to next().
Here is an example. Assume that the iterator is initialized to the beginning of the list:
[1, 2, 3].
Call
next() gets you 1, the first element in the list.
Now you call
peek() and it returns 2, the next element. Calling next() after that still return 2.
You call
next() the final time and it returns 3, the last element. Calling hasNext() after that should return false.
Follow up: How would you extend your design to be generic and work with all types, not just integer?
Solution:
Use a variable to track the peek element which is the next element. So if peekElement is not null, means it has been peeked, so we just return the peekElement, if it is null, we assign peekElement=iterator.next(). The problem now is when we call next(), we need to check peekElement first, if it is null, means the next element is cached in the peekElement, we return peekElement and set peekElement to null. To check if the iterator hasNext(), we have to check if there is a cached peekElement and if the iterator hasNext().
// Java Iterator interface reference:
// https://docs.oracle.com/javase/8/docs/api/java/util/Iterator.html
class PeekingIterator implements Iterator<Integer> {
Integer peekElement;
Iterator<Integer> myIterator;
public PeekingIterator(Iterator<Integer> iterator) {
// initialize any member here.
peekElement=null;
myIterator=iterator;
}
// Returns the next element in the iteration without advancing the iterator.
public Integer peek() {
if(peekElement==null) peekElement=myIterator.next();
return peekElement;
}
// hasNext() and next() should behave the same as in the Iterator interface.
// Override them if needed.
@Override
public Integer next() {
if(peekElement!=null){
Integer temp=peekElement;
peekElement=null;
return temp;
}
else return myIterator.next();
}
@Override
public boolean hasNext() {
return myIterator.hasNext() || peekElement!=null;
}
}
Wednesday, September 27, 2017
282. Expression Add Operators
Given a string that contains only digits
0-9 and a target value, return all possibilities to add binary operators (not unary) +, -, or *between the digits so they evaluate to the target value.
Examples:
"123", 6 -> ["1+2+3", "1*2*3"] "232", 8 -> ["2*3+2", "2+3*2"] "105", 5 -> ["1*0+5","10-5"] "00", 0 -> ["0+0", "0-0", "0*0"] "3456237490", 9191 -> []
Solution:
Recursively add operator and check the result till so far.
The difficult point is add "*", I use sum to keep track the summation before we add multiply and use number to track the product.
If we are going to try "+", we can assign the sum=sum+nextNumber, and number=1, because '+' and '-' have lower priority than '*'. But if we are going to try '*', we have to keep previous sum and keep calculating product.
Also we need to take care of 0. If current number is 0, we break the iteration, and directly try next recursion, because '00','01'...is not a valid number.
Recursively add operator and check the result till so far.
The difficult point is add "*", I use sum to keep track the summation before we add multiply and use number to track the product.
If we are going to try "+", we can assign the sum=sum+nextNumber, and number=1, because '+' and '-' have lower priority than '*'. But if we are going to try '*', we have to keep previous sum and keep calculating product.
Also we need to take care of 0. If current number is 0, we break the iteration, and directly try next recursion, because '00','01'...is not a valid number.
public List<String> addOperators(String num, int target) {
List<String> res=new ArrayList<String>();
helper(num,0,0,1,target,"",res);
return res;
}
public void helper(String num, int ind, long sum, long number, int target,String item,List<String> res){
if(ind==num.length()){
if(sum==target) res.add(item);
return;
}
for(int i=ind+1;i<=num.length();i++){
long temp=Long.parseLong(num.substring(ind,i));
long nextNumber= temp*number;
if(i==num.length()){
helper(num,i,sum+nextNumber,0,target,item+temp,res);
}
else{
helper(num,i,sum+nextNumber,1,target,item+temp+"+",res);
helper(num,i,sum+nextNumber,-1,target,item+temp+"-",res);
helper(num,i,sum,nextNumber,target,item+temp+"*",res);
}
if(num.charAt(ind)=='0') break;
}
}
Tuesday, September 26, 2017
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:
Use a variable to keep track the count of non-zero element and move them to the right position which is indexed at their count, and set all other positions to 0.
public void moveZeroes(int[] nums) {
int ind=0;
for(int i=0;i<nums.length;i++){
if(nums[i]!=0){
if(i!=ind){
nums[ind]=nums[i];
nums[i]=0;
}
ind++;
}
}
}
275. H-Index II
Follow up for H-Index: What if the
Solution: we can use the linear solution I used in
citations array is sorted in ascending order? Could you optimize your algorithm?Solution: we can use the linear solution I used in
274. H-Index
Or we can use a better binary search.
The same idea as we do the linear search.
length-m is the target we try to figure it out.
If current paper has the same citations (citations[m]) as the amount of paper that has at least current citations ( length-m), it means H-index is citations[m] because any larger h (index to right) will lead to less paper.
If length-m > current paper's citations, we should search right half because, length-m is too large that we can't find lenth-m of paper that have at least length-m citations. Because the most (length-m)th paper has citations of citations[m] which is less than length-m.
else if length-m < current paper's citations, we should search left half, because although it satisfy the requirement but it is not the optimal answer.
public int hIndex(int[] citations) {
int n=citations.length;
int l=0;
int r=n-1;
while(l<=r){
int m=(r-l)/2+l;
if(n-m==citations[m]) return n-m;
else if(n-m<citations[m]) r=m-1;
else l=m+1;
}
return n-l;
}
Monday, September 25, 2017
273. Integer to English Words
Convert a non-negative integer to its english words representation. Given input is guaranteed to be less than 231 - 1.
For example,
123 -> "One Hundred Twenty Three" 12345 -> "Twelve Thousand Three Hundred Forty Five" 1234567 -> "One Million Two Hundred Thirty Four Thousand Five Hundred Sixty Seven"
Solution:
The method is very straightforward, nothing special.
Couple tips:
1. Compose the string for every 3 digits.
2. Add white space to the end of returned string for <=3 digit number, so we should be able to concatenate with thousands without manually adding whitespace before thousands. Any unwanted whtiespaces that are at the end will be trimmed before return.
The method is very straightforward, nothing special.
Couple tips:
1. Compose the string for every 3 digits.
2. Add white space to the end of returned string for <=3 digit number, so we should be able to concatenate with thousands without manually adding whitespace before thousands. Any unwanted whtiespaces that are at the end will be trimmed before return.
private final String[] LESS_THAN_20 = {"", "One", "Two", "Three", "Four", "Five", "Six", "Seven", "Eight", "Nine", "Ten", "Eleven", "Twelve", "Thirteen", "Fourteen", "Fifteen", "Sixteen", "Seventeen", "Eighteen", "Nineteen"};
private final String[] TENS = {"", "Ten", "Twenty", "Thirty", "Forty", "Fifty", "Sixty", "Seventy", "Eighty", "Ninety"};
private final String[] THOUSANDS = {"", "Thousand", "Million", "Billion"};
public String numberToWords(int num) {
if(num==0) return "Zero";
int i=0;
String res="";
while(num!=0){
if(num%1000!=0){
res=helper(num%1000)+THOUSANDS[i]+" "+res;
}
num=num/1000;
i++;
}
return res.trim();
}
public String helper(int num){
if(num==0) return "";
if(num>=100) return LESS_THAN_20[num/100]+" Hundred "+helper(num%100);
if(num>=20) return TENS[num/10]+" "+helper(num%10);
else return LESS_THAN_20[num]+" ";
}
Sunday, September 24, 2017
287. Find the Duplicate Number
Given an array nums containing n + 1 integers where each integer is between 1 and n (inclusive), prove that at least one duplicate number must exist. Assume that there is only one duplicate number, find the duplicate one.
Note:
- You must not modify the array (assume the array is read only).
- You must use only constant, O(1) extra space.
- Your runtime complexity should be less than
O(n2). - There is only one duplicate number in the array, but it could be repeated more than once.
Solution:
Since nums array contains 1 to n, nums[0] must between 1 and n. Assume there is no duplicate in this array, nums[nums[0]] must !=nums[0] and any subsequent nums[x] must be a distinct number from 1 to n.
However there must exist at least one duplicate because, n+1 > length(1 to n) .
So when we keep nums(n)=nums[nums(n-1)], we will fall into a cycle because there must exsit a distinct index m and n to make nums[m]==nums[n] which is the duplicate number we are trying to find here.
So the whole problem becomes a cycle detecting problem.
And we know there is a great algorithm that can find the entry point of the cycle:
142. Linked List Cycle II Leetcode Java
Similarly here, we use the same technique, walker and runner to find the entry point.
Time complexity: O(n)
Time complexity: O(n)
public int findDuplicate(int[] nums) {
int walker=nums[0];
int runner=nums[0];
do{
walker=nums[walker];
runner=nums[nums[runner]];
}while(walker!=runner);
walker=nums[0];
while(walker!=runner){
walker=nums[walker];
runner=nums[runner];
}
return walker;
}
Another O(nlg(n)) solution:
Normal binary search usually search the index while target is the element of the array. But this one is opposite and we search number itself.
We set initial l=1 and r=n,
Eg.n=6, so the array may be 1,2,3,4,5,6 + a duplicate number
m is 3, so if duplicate is <=3, which means if we count all the element that is <=3, the count must > 3
if duplicate is >3, the count must <=3.
So according the count, we can either cut the left half or right half.
While counting takes O(n), so the total time complexity is O(nlgn).
public int findDuplicate(int[] nums) {
int l=1;
int r=nums.length-1;
while(l<r){
int m=(r-l)/2+l;
int count=0;
for(int i=0;i<nums.length;i++){
if(nums[i]<=m) count++;
}
if(count>m) r=m;
else l=m+1;
}
return l;
}
279. Perfect Squares
Given a positive integer n, find the least number of perfect square numbers (for example,
1, 4, 9, 16, ...) which sum to n.
For example, given n =
12, return 3 because 12 = 4 + 4 + 4; given n = 13, return 2 because 13 = 4 + 9.
Solution:
Bottom-up DP.
dp[n]=Math.min(dp[n-1]+1,dp[n-4]+1,dp[n-9]+1.....)
There is a very fast and decent Mathematics solution using
Legendre's three-square theorem
Please see the discussion tab in the Leetcode.
public int numSquares(int n) {
int[] dp=new int[n+1];
for(int i=1;i<=n;i++){
int j=1;
dp[i]=i;
while(i>=j*j){
dp[i]=Math.min(dp[i],dp[i-j*j]+1);
j++;
}
}
return dp[n];
}
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:
Binary search:
If version m is not a bad version, so the first bad version must be after m, so l =m+1; else if version m is a bad version, the first bad version must be m or before m. so r=m;
public int firstBadVersion(int n) {
int l=1;
int r=n;
while(l<r){
int m=(r-l)/2+l;
if(isBadVersion(m)) r=m;
else l=m+1;
}
return l;
}
274. H-Index
Given an array of citations (each citation is a non-negative integer) of a researcher, write a function to compute the researcher's h-index.
According to the definition of h-index on Wikipedia: "A scientist has index h if h of his/her N papers have at least h citations each, and the other N − h papers have no more than h citations each."
For example, given
citations = [3, 0, 6, 1, 5], which means the researcher has 5 papers in total and each of them had received 3, 0, 6, 1, 5 citations respectively. Since the researcher has 3 papers with at least 3 citations each and the remaining two with no more than 3 citations each, his h-index is 3.
Note: If there are several possible values for
h, the maximum one is taken as the h-index.
Solution:
1. Sort the citations, check from highest to lowest and see if current citation is greater than visited papers, continue if the statement is true.
public int hIndex(int[] citations) {
Arrays.sort(citations);
int res=0;
for(int i=citations.length-1;i>=0;i--){
if(citations[i]<res+1) break;
else res++;
}
return res;
}
2. O(n) solution
DP.
For example, [3, 0,6,1,5], the total amount of paper is 5, so the maximum possible h-index is 5. We use an array h to keep track the count of papers that has the citations as the current index. For any paper that has citations greater than 5, we increment h[5].
So the h will look like this[1,1,0,1,0,2] , we have 2 paper that has citations>=5, 5 is not our h index, we have 2+0 papers that has citations >=4, 4 is not h index, we have 2+0+1=3 papers that has citations>=3, so 3 is our h-index.
public int hIndex(int[] citations) {
int n=citations.length;
int[] h=new int[n+1];
for(int i=0;i<citations.length;i++){
if(citations[i]>n) h[n]++;
else h[citations[i]]++;
}
int sum=0;
for(int i=n;i>=0;i--){
sum+=h[i];
if(sum>=i) return i;
}
return 0;
}
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 =
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?
Your algorithm should run in linear runtime complexity. Could you implement it using only constant extra space complexity?
Solution:
Missing element= 0+1+2+...+n- (Sum(nums[]);
public int missingNumber(int[] nums) {
int sum=0;
for(int i=0;i<nums.length;i++){
sum=sum+i+1-nums[i];
}
return sum;
}
264. Ugly Number II
Write a program to find the
n-th ugly number.
Ugly numbers are positive numbers whose prime factors only include
2, 3, 5. For example, 1, 2, 3, 4, 5, 6, 8, 9, 10, 12 is the sequence of the first 10 ugly numbers.
Note that
1 is typically treated as an ugly number, and n does not exceed 1690.
Solution:
Bottom-up dp.
All the ugly numbers should be product of an ugly number and 2 or 3 or 5.
We use an array to track all the ugly numbers we calculated so far and use three pointers to track which ugly number is the next ugly number that we are going to use to build nth ugly number for 2,3,and 5 respectively.
For example when we get ugly number 10, which is 2 * 5, the next ugly number for factor 2 that is possible to build an ugly number next to 10 is 6, and next ugly number that for factor 3 is 4 since 9 is build by 3 * 3, so next is 4 for factor 3. The next ugly number for factor five becomes 3, because 10 is 2*5, so the pointer moves to 3. We compare all 3 candidates, 2*6, 3*4, 5*3 and get the minimum which is 12, and increment the pointers respectively.
public int nthUglyNumber(int n) {
int[] res=new int[n];
res[0]=1;
int a,b,c;
a=b=c=0;
for(int i=1;i<n;i++){
res[i]=Math.min(2*res[a],Math.min(3*res[b],5*res[c]));
if(res[i]%2==0) a++;
if(res[i]%3==0) b++;
if(res[i]%5==0) c++;
}
return res[n-1];
}
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:
Recursive,
Base case: num==1 which is ugly number.
If num can be divided by 2, 3 ,5 recursively check num/2 or num/3 or num/5.
public boolean isUgly(int num) {
if(num<=0) return false;
if(num==1) return true;
if(num%2==0) return isUgly(num/2);
if(num%3==0) return isUgly(num/3);
if(num%5==0) return isUgly(num/5);
return false;
}
Iterative: same idea:
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;
}
260. Single Number III
Given an array of numbers
nums, in which exactly two elements appear only once and all the other elements appear exactly twice. Find the two elements that appear only once.
For example:
Given
nums = [1, 2, 1, 3, 2, 5], return [3, 5].
Note:
- The order of the result is not important. So in the above example,
[5, 3]is also correct. - Your algorithm should run in linear runtime complexity. Could you implement it using only constant space complexity?
Solution:
Previous similar problem: 136: single number and 137 single number II
As we know we can use bit operator xor to get rid of all elements that appeared twice.
Similarly here, we xor all the numbers in the array and let's assume the two elements that we want to get is a and b, so xor all elements in nums will give us x= (a ^b) , x must be a non-zero integer,because they are different, so there must be at least one digit 1 in x's binary format.We can use ~(x-1) & x to get to get the least digit of 1. Eg. 110100 -1 = 110011, ~110011 = 001100, 001100 & 110100= 100. Because x= y+ 2^n and x-1 = y+2^n-1
^y & y=0, 2^n & (~(2^n-1))=2^n. So ~(x-1) & x= 2^n which is the least position of digit 1.So in this digit position, a and b have different digits. Either a has 0 and b has 1 or a has 1 and b has 0.
With this information, we can split the whole nums array to 2 parts, All the numbers that have 0 at this position and all the numbers that have 1 at this position. We know these two group of numbers are just simply some elements that appear exactly two elements and one element appears only once. So we xor these two group of numbers separately , we can get our results.
public int[] singleNumber(int[] nums) {
int a=nums[0];
for(int i=1;i<nums.length;i++){
a=a^nums[i];
}
a=(~(a-1))&a;
int[] res=new int[2];
for(int i=0;i<nums.length;i++){
if((nums[i]&a)==0) res[0]=res[0]^nums[i];
else res[1]=res[1]^nums[i];
}
return res;
}
236. Lowest Common Ancestor of a Binary Tree
Given a binary tree, find the lowest common ancestor (LCA) of two given nodes in the tree.
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).”
_______3______
/ \
___5__ ___1__
/ \ / \
6 _2 0 8
/ \
7 4
For example, the lowest common ancestor (LCA) of nodes
5 and 1 is 3. Another example is LCA of nodes 5 and 4 is 5, since a node can be a descendant of itself according to the LCA definition.
Solution:
This problem is the extension of
235. Lowest Common Ancestor of a Binary Search Tree
This one is a genera tree, which doesn't allow us to use value to determine a node's parent.
But we can use recursion to get lowest common ancestor.
For base case, if root==null || root == p || root == q, return root.
Then we recursively use the function to get left child's lowest common ancestor for p and q. Let's define it as leftCommon. Similarly we can get rightCommon.
Obviously if leftCommon is null we return rightCommon, and if rightCommon is null we return leftCommon.
For example, p is node 6 while q is node 7. LeftCommon should be 5, while rightCommon is null.
The other situation is both leftCommon and rightCommon are not null, which means leftCommon is p while rightCommon is q or vice versa. In this case we should return root. Eg p=6, q =8. leftCommon is 6 and rightCommon is 8, so we return 3.
public TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) {
if(root==null || root==p || root==q) return root;
TreeNode leftCommon=lowestCommonAncestor(root.left,p,q);
TreeNode rightCommon=lowestCommonAncestor(root.right,p,q);
if(leftCommon==null) return rightCommon;
if(rightCommon==null) return leftCommon;
return root;
}
Subscribe to:
Posts (Atom)