Remove K Digits

Given a non-negative integer num represented as a string, remove k digits from the number so that the new number is the smallest possible.

Note:

• The length of num is less than 10002 and will be ≥ k.
• The given num does not contain any leading zero.

Example 1:

Input: num = "1432219", k = 3
Output: "1219"
Explanation: Remove the three digits 4, 3, and 2 to form the new number 1219 which is the smallest.

Example 2:

Input: num = "10200", k = 1
Output: "200"
Explanation: Remove the leading 1 and the number is 200. Note that the output must not contain leading zeroes.

Example 3:

Input: num = "10", k = 2
Output: "0"
Explanation: Remove all the digits from the number and it is left with nothing which is 0.

Analysis:
-- This is asking to remove K numbers from a number and result value should be smallest
-- to make a number smallest, make sure the next number moving up should be smaller than the one being removed.
--scan from left to right, keep removing the one bigger than its right neighbour
--after a number is removed, we need to compare its left neighbour and right neighbour
--if number is already in ascending order, we need to remove right most numbers-- right most non-zero numbers

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42

public class Solution { public String removeKdigits(String num, int k) { Objects.requireNonNull(num); if(k==0)return num; if(num.length()==1 && k==1)return "0"; int pre=0,cur=1; StringBuilder sb = new StringBuilder(num); //from left to right, delete character that is bigger than right neighbor while(k>0 && cur<sb.length()){ if(sb.charAt(cur)<sb.charAt(pre)){ sb.deleteCharAt(pre); if(pre>0){ //we now need to compare the left and right neighbors of the one being removed pre--; cur--; } k--; }else{ //moving forward if element in cur is greater than element at pre cursor pre=cur; cur++; } } //last pass might not remove enough characters int rightPosition = sb.length()-1; //then need to go through it from right to left and remove the right most non-zero one while(k>0 && rightPosition>=0){ if(sb.charAt(rightPosition)!='0'){ sb.deleteCharAt(rightPosition); k--; } rightPosition--; } //remove leading 0s while(sb.length()>0 && sb.charAt(0)=='0'){ sb.deleteCharAt(0); } return (sb.length()==0?"0":sb.toString()); } }

Insert Delete GetRandom O(1), with or without duplications

380. Insert Delete GetRandom O(1)

Design a data structure that supports all following operations in average O(1) time.

1. insert(val): Inserts an item val to the set if not already present.
2. remove(val): Removes an item val from the set if present.
3. getRandom: Returns a random element from current set of elements. Each element must have the same probability of being returned.

Example:

// Init an empty set.
RandomizedSet randomSet = new RandomizedSet();

// Inserts 1 to the set. Returns true as 1 was inserted successfully.
randomSet.insert(1);

// Returns false as 2 does not exist in the set.
randomSet.remove(2);

// Inserts 2 to the set, returns true. Set now contains [1,2].
randomSet.insert(2);

// getRandom should return either 1 or 2 randomly.
randomSet.getRandom();

// Removes 1 from the set, returns true. Set now contains [2].
randomSet.remove(1);

// 2 was already in the set, so return false.
randomSet.insert(2);

// Since 1 is the only number in the set, getRandom always return 1.
randomSet.getRandom();

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59

public class RandomizedSet { //key is the number, value is the index in arraylist //appending to list to achieve O(1) overall Map<Integer,Integer> numIndexMap = null; List<Integer> nums = null; /** Initialize your data structure here. */ public RandomizedSet() { numIndexMap = new HashMap<Integer,Integer>(); nums = new ArrayList<Integer>(); } /** Inserts a value to the set. Returns true if the set did not already contain the specified element. */ public boolean insert(int val) { if(numIndexMap.containsKey(val)){ return false; }else{ //index is 0 based, so we use its size before adding to list numIndexMap.put(val,nums.size()); nums.add(val); } return true; } /** Removes a value from the set. Returns true if the set contained the specified element. */ public boolean remove(int val) { if(!numIndexMap.containsKey(val)){ return false; }else{ int index = numIndexMap.remove(val);//this returns value of if(index<nums.size()-1){//not last element //move last element to the element to be removed //array set operation is O(1), remove tail is O(1) int lastVal = nums.get(nums.size()-1); nums.set(index,lastVal); numIndexMap.put(lastVal,index); } nums.remove(nums.size()-1); } return true; } /** Get a random element from the set. */ public int getRandom() { if(nums.size()==0)return -1; if(nums.size()==1)return nums.get(0); Random r = new Random(); int indexRandom = r.nextInt(nums.size()); return nums.get(indexRandom); } } /** * Your RandomizedSet object will be instantiated and called as such: * RandomizedSet obj = new RandomizedSet(); * boolean param_1 = obj.insert(val); * boolean param_2 = obj.remove(val); * int param_3 = obj.getRandom(); */

381. Insert Delete GetRandom O(1) - Duplicates allowed

https://leetcode.com/problems/insert-delete-getrandom-o1-duplicates-allowed/

Design a data structure that supports all following operations in average O(1) time.

Note: Duplicate elements are allowed.

1. insert(val): Inserts an item val to the collection.
2. remove(val): Removes an item val from the collection if present.
3. getRandom: Returns a random element from current collection of elements. The probability of each element being returned is linearly related to the number of same value the collection contains.

Example:

// Init an empty collection.
RandomizedCollection collection = new RandomizedCollection();

// Inserts 1 to the collection. Returns true as the collection did not contain 1.
collection.insert(1);

// Inserts another 1 to the collection. Returns false as the collection contained 1. Collection now contains [1,1].
collection.insert(1);

// Inserts 2 to the collection, returns true. Collection now contains [1,1,2].
collection.insert(2);

// getRandom should return 1 with the probability 2/3, and returns 2 with the probability 1/3.
collection.getRandom();

// Removes 1 from the collection, returns true. Collection now contains [1,2].
collection.remove(1);

// getRandom should return 1 and 2 both equally likely.
collection.getRandom();

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68

public class RandomizedCollection { Map<Integer, List<Integer>> numIndicesMap = new HashMap<Integer, List<Integer>>(); List<Integer> nums = new ArrayList<Integer>(); Random r = new Random(); /** Initialize your data structure here. */ public RandomizedCollection() { } /** Inserts a value to the collection. Returns true if the collection did not already contain the specified element. */ public boolean insert(int val) { if(numIndicesMap.containsKey(val)){ numIndicesMap.get(val).add(nums.size());//add a new index in numIndicesMap nums.add(val);//add new element to num list return false; }else{ List<Integer> indices = new ArrayList<Integer>(); indices.add(nums.size()); nums.add(val); numIndicesMap.put(val,indices); return true; } } /** Removes a value from the collection. Returns true if the collection contained the specified element. */ public boolean remove(int val) { if(numIndicesMap.containsKey(val)){ //remove it from numIndicesMap List<Integer> indices = numIndicesMap.get(val); int index = indices.remove(indices.size()-1);//remove last one. index in nums should be removed if(indices.size()==0){//indices list is empty, remove key from map numIndicesMap.remove(val); } //remove from nums int lastIndex = nums.size()-1; int lastElement = nums.get(lastIndex); if(index!=lastIndex){ //not last one nums.set(index,lastElement);//set last element to val's index //since lastElement is already in nums, it must have an index list in map List<Integer> indicesOfLastElement = numIndicesMap.get(lastElement); indicesOfLastElement.remove(new Integer(lastIndex));//remove last Index, //this has to be object instead of prime in order to remove correct element indicesOfLastElement.add(index);//add new index position for last element } nums.remove(nums.size()-1);//remove last element in list return true; } return false; } /** Get a random element from the collection. */ public int getRandom() { if(nums.size()==0)return -1; if(nums.size()==1)return nums.get(0); int randomInd = r.nextInt(nums.size());//n in nextInt is exclusive return nums.get(randomInd); } } /** * Your RandomizedCollection object will be instantiated and called as such: * RandomizedCollection obj = new RandomizedCollection(); * boolean param_1 = obj.insert(val); * boolean param_2 = obj.remove(val); * int param_3 = obj.getRandom(); */

388. Longest Absolute File Path

I really struggled to make the code concise and short, but could not. I guess sticking with an understandable solution will hopefully later leads to more concise code.

A mistake to come up a solution is to forget to add a clash into the absolute path.

Suppose we abstract our file system by a string in the following manner:

The string "dir\n\tsubdir1\n\tsubdir2\n\t\tfile.ext" represents:

dir
    subdir1
    subdir2
        file.ext

The directory dir contains an empty sub-directory subdir1 and a sub-directory subdir2 containing a file file.ext.

The string "dir\n\tsubdir1\n\t\tfile1.ext\n\t\tsubsubdir1\n\tsubdir2\n\t\tsubsubdir2\n\t\t\tfile2.ext" represents:

dir
    subdir1
        file1.ext
        subsubdir1
    subdir2
        subsubdir2
            file2.ext

The directory dir contains two sub-directories subdir1 and subdir2. subdir1 contains a file file1.ext and an empty second-level sub-directory subsubdir1. subdir2 contains a second-level sub-directory subsubdir2 containing a file file2.ext.

We are interested in finding the longest (number of characters) absolute path to a file within our file system. For example, in the second example above, the longest absolute path is"dir/subdir2/subsubdir2/file2.ext", and its length is 32 (not including the double quotes).

Given a string representing the file system in the above format, return the length of the longest absolute path to file in the abstracted file system. If there is no file in the system, return0.

Note:

• The name of a file contains at least a . and an extension.
• The name of a directory or sub-directory will not contain a ..

Time complexity required: O(n) where n is the size of the input string.

Notice that a/aa/aaa/file1.txt is not the longest file path, if there is another path aaaaaaaaaaaaaaaaaaaaa/sth.png.

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28

public class Solution { public int lengthLongestPath(String input) { //sequencially going through all the paths and files, //not care about the empty dirs because only file contribute to file path length String[] dirs = input.split("\n");//parse out each directory Stack<Integer> lvls= new Stack<Integer>(); int maxLen = 0; for(String s:dirs){ int lev = s.lastIndexOf("\t"); if(lev==-1){//this must be direct children in root dir lvls.clear(); lvls.push(s.length()+1);//every push is a path, and +1 for a slash } else{ //for subdirs or files //want to retreat back to parent level while(lvls.size()>lev+1)lvls.pop(); //lvl is -1, 0,1 etc, with 0 means first sublevel. because when its size is greater than lvl, //it will go further to reduce one, so lev+1 make sure it stops at parent level/lev after the further reduction lvls.push(lvls.peek()+s.length()-(lev+1)+1);//lev+1 is number if "\t" } if(s.contains(".")) maxLen = Math.max(maxLen, lvls.peek()-1);//file is not ended with a slash } return maxLen; } }

387. First Unique Character in a String

This is very similar to the second question I was asked in an Amazon interview back to 2014. Here's my solution for it.

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.

Note: You may assume the string contain only lowercase letters.

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27

public class Solution { public int firstUniqChar(String s) { if(s==null ||s.length()==0)return -1; if(s.length()==1)return 0; int[] positions = new int[26]; for(int i=0;i<26;i++){ positions[i]=Integer.MIN_VALUE; } //set repeated ones with -1 for(int i=0;i<s.length();i++){ int curCharIndex = s.charAt(i)-'a'; if(positions[curCharIndex]==Integer.MIN_VALUE){ positions[curCharIndex]=i; }else if(positions[curCharIndex]>=0){ positions[curCharIndex]=-1; } } for(int i=0;i<s.length();i++){ int curCharIndex = s.charAt(i)-'a'; if(positions[curCharIndex]>=0){ return positions[curCharIndex]; } } return -1; } }

Water and jug problem

You are given two jugs with capacities x and y litres. There is an infinite amount of water supply available. You need to determine whether it is possible to measure exactly z litres using these two jugs.
If z liters of water is measurable, you must have z liters of water contained within one or both buckets by the end.
Operations allowed:

• Fill any of the jugs completely with water.
• Empty any of the jugs.
• Pour water from one jug into another till the other jug is completely full or the first jug itself is empty.

Example 1: (From the famous "Die Hard" example)

Input: x = 3, y = 5, z = 4
Output: True

Example 2:

Input: x = 2, y = 6, z = 5
Output: False

Credits:
Special thanks to @vinod23 for adding this problem and creating all test cases

another key to understand this solution is the calculation of greatest common divisor.

1 2 3 4 5 6 7 8 9 10 11 12 13 14

public class Solution { public boolean canMeasureWater(int x, int y, int z) { /*//this code is for measuring and filling the z if(x==0&&y==0&&z!=0)return false; if(x==0&&y==0&&z==0)return true; return x + y == z || z % dieHard(x,y) == 0;*/ //this code is for a condition that what's left in x and y is z return x + y == z || (x+y)>=z&&z % dieHard(x,y) == 0; } //mx + ny = z private int dieHard(int a,int b){ return b==0? a: dieHard(b,a%b); } }

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

Note:Be careful about the overflow when multiple two integers

1 2 3 4 5 6 7 8 9 10 11 12 13

public class Solution { public boolean isPerfectSquare(int num) { int l=0,r=num/2+1;//for num=1, for num=4. it is a waste of calculation after the 4. //but as a general approach, this keeps code concise while(l<=r){ int m = l+(r-l)/2; long ans = (long)m*(long)m;//overflow if(ans==num)return true; if(ans>num)r=m-1; if(ans<num)l=m+1; } return false; } }

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.
Credits:
Special thanks to @jianchao.li.fighter for adding this problem and creating all test cases.

1 2 3 4 5 6 7 8 9 10 11

public class Solution { public boolean isUgly(int num) { if(num==0)return false; //divid as much as possible to each of 2, 3 and 5 and see if result is 1 //if result is nnot 1, then it is not ugly number while(num%2==0)num=num/2;//num must be multiple times of 2 while(num%3==0)num=num/3; while(num%5==0)num=num/5; return num==1; } }

Ugly Number 2
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.
Hint:

1. The naive approach is to call isUgly for every number until you reach the n^th one. Most numbers are not ugly. Try to focus your effort on generating only the ugly ones.
2. An ugly number must be multiplied by either 2, 3, or 5 from a smaller ugly number.
3. The key is how to maintain the order of the ugly numbers. Try a similar approach of merging from three sorted lists: L₁, L₂, and L₃.
4. Assume you have U_k, the k^th ugly number. Then U_k+1 must be Min(L₁ * 2, L₂ * 3, L₃ * 5).

Credits:
Special thanks to @jianchao.li.fighter for adding this problem and creating all test cases.

Lessons learned:
overflow:int to long when int multiply int. special case: n=1
key: priority queue and k sorted list merging.
key: repeated numbers should not be duplicated added. e.g. 6=2*3, 6 will be added twice if not checking.

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18

public class Solution { public int nthUglyNumber(int n) { if(n==1)return 1; PriorityQueue<Long> pq = new PriorityQueue<Long>(); pq.add(1l);//first ugly number is 1 int cnt=0; long minUgly=1; while(cnt<n){ minUgly= pq.poll();//access one ugly number cnt++;//so counter increase 1 if(!pq.contains(minUgly*2l))pq.add(minUgly*2l); if(!pq.contains(minUgly*3l))pq.add(minUgly*3l); if(!pq.contains(minUgly*5l))pq.add(minUgly*5l); } return (int)minUgly; } }

Super Ugly Numbers: this actually just need to change few lines of code in ugly number 2.

Write a program to find the n^th super ugly number. Super ugly numbers are positive numbers whose all prime factors are in the given prime list primes of size k. For example, [1, 2, 4, 7, 8, 13, 14, 16, 19, 26, 28, 32] is the sequence of the first 12 super ugly numbers given primes = [2, 7, 13, 19] of size 4.
Note:
(1) 1 is a super ugly number for any given primes.
(2) The given numbers in primes are in ascending order.
(3) 0 < k ≤ 100, 0 < n ≤ 10⁶, 0 < primes[i] < 1000.

Note: this implement is not optimized and runs timeout. putting here for demonstrate thought of solution.

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20

public class Solution { public int nthSuperUglyNumber(int n, int[] primes) { if(n==1)return 1; PriorityQueue<Long> pq = new PriorityQueue<Long>(); pq.add(1l);//first ugly number is 1 int cnt=0; long minUgly=1; while(cnt<n){ minUgly= pq.poll();//access one ugly number //System.out.println(minUgly); cnt++;//so counter increase 1 for(int p:primes){ if(!pq.contains(minUgly*p))pq.add(minUgly*p); } } return (int)minUgly; } }