Evaluate Division

Equations are given in the format A / B = k, where A and B are variables represented as strings, and k is a real number (floating point number). Given some queries, return the answers. If the answer does not exist, return -1.0.
Example:
Given a / b = 2.0, b / c = 3.0.
queries are: a / c = ?, b / a = ?, a / e = ?, a / a = ?, x / x = ? .
return [6.0, 0.5, -1.0, 1.0, -1.0 ].
The input is: vector<pair<string, string>> equations, vector<double>& values, vector<pair<string, string>> queries , where equations.size() == values.size(), and the values are positive. This represents the equations. Return vector<double>.
According to the example above:

equations = [ ["a", "b"], ["b", "c"] ],
values = [2.0, 3.0],
queries = [ ["a", "c"], ["b", "a"], ["a", "e"], ["a", "a"], ["x", "x"] ]. 

The input is always valid. You may assume that evaluating the queries will result in no division by zero and there is no contradiction.

Analysis:

This is to find if two elements are connected. A typical graph practice.
After a path is found out, the answer to query is multiply of edges:
a/b=1,b/c=2,c/d=3, then a/d = a/b*b/c*c/d=6.0

class Edge{
    String from,to;
    double weight;
public Edge(String a,String b, double w){
    from = a;
    to = b;
    weight = w;
}
public String toString(){
    return from+"->"+to+":"+weight;
}
public int hashCode(){
    return toString().hashCode();
}    
public boolean equals(Object b){
    if(b instanceof Edge && toString().equals(b.toString())){
        return true;
    }
    return false;
}
}
class EdgeWeightedGraph{
    Map<String,Set<Edge>> adj = new HashMap<String,Set<Edge>>();
    
    public void addEdge(String a,String b, double weight){
        Edge one = new Edge(a,b,weight);
        Edge two = new Edge(b,a,1.0/weight);
        if(adj.containsKey(a)){
            adj.get(a).add(one);
        }else{
            Set<Edge> s = new HashSet<Edge>();
            s.add(one);
            adj.put(a,s);
        }
        if(adj.containsKey(b)){
            adj.get(b).add(two);
        }else{
            Set<Edge> s = new HashSet<Edge>();
            s.add(two);
            adj.put(b,s);
        }
    }
    public boolean contains(String a){
        return adj.containsKey(a);
    }
    public List<Edge> getPath(String a, String b){
        Set<Edge> visited = new HashSet<Edge>();
        List<Edge> path = new ArrayList<Edge>();
        path = dfsGetPath(a,b,path,visited);
        return path;
    }
    private List<Edge> dfsGetPath(String start,String end,List<Edge> path,Set<Edge> visited){
        if(start.equals(end)){
            //List<Edge> result = new ArrayList<Edge>();
            //result.addAll(path);
            return path;
        }
        if(adj.get(start)!=null){
            for(Edge e:adj.get(start)){
                if(visited.add(e)){
                    path.add(e);
                    List<Edge> r = dfsGetPath(e.to,end,path,visited);
                    if(r.size()>0){
                        return r;
                        //stop further processing
                    }
                    path.remove(e);//next loop starting from same path path
                }
            }
        }
        return new ArrayList<Edge>();
    }
}
public class Solution {
    public double[] calcEquation(String[][] equations, double[] values, String[][] queries) {
        //prepare
        double[] result = new double[queries.length];
        EdgeWeightedGraph g = new EdgeWeightedGraph();
        for(int i=0;i<values.length;i++){
            g.addEdge(equations[i][0],equations[i][1],values[i]);
        }
        for(int i=0;i<queries.length;i++){
            if(queries[i][0].equals(queries[i][1])&&g.contains(queries[i][0])){
                result[i]=1.0;
                continue;
            }
            List<Edge> r = g.getPath(queries[i][0],queries[i][1]);
            if(r.size()==0){
                result[i]=-1.0;
            }else{
                result[i]=1;
                for(Edge e:r){
                    result[i]*=e.weight;
                }
            }
        }
        return result;
    }
}

Frog Jump

A frog is crossing a river. The river is divided into x units and at each unit there may or may not exist a stone. The frog can jump on a stone, but it must not jump into the water.

Given a list of stones' positions (in units) in sorted ascending order, determine if the frog is able to cross the river by landing on the last stone. Initially, the frog is on the first stone and assume the first jump must be 1 unit.

If the frog's last jump was k units, then its next jump must be either k - 1, k, or k + 1 units. Note that the frog can only jump in the forward direction.

Note:

• The number of stones is ≥ 2 and is < 1,100.
• Each stone's position will be a non-negative integer < 231.
• The first stone's position is always 0.

Example 1:

[0,1,3,5,6,8,12,17]

There are a total of 8 stones.
The first stone at the 0th unit, second stone at the 1st unit,
third stone at the 3rd unit, and so on...
The last stone at the 17th unit.

Return true. The frog can jump to the last stone by jumping 
1 unit to the 2nd stone, then 2 units to the 3rd stone, then 
2 units to the 4th stone, then 3 units to the 6th stone, 
4 units to the 7th stone, and 5 units to the 8th stone.

Example 2:

[0,1,2,3,4,8,9,11]

Return false. There is no way to jump to the last stone as 
the gap between the 5th and 6th stone is too large.

Analysis

With possible movements defined as constrains/rules, and target is to find if something is reachable, a natural thought would be finding if there's a path between two nodes in a graph. So adjacency list is a good candidate data structure to use. Controversy to traditional use of adjacency list, which is built up to represent a graph before traverse it, this algorithm built it up on the fly and used it as a memoization mechanism to avoid duplicate computations.

The code is much more concise than my first version that does not have a good data structure in use.

https://discuss.leetcode.com/topic/59906/average-60ms-java-solution-idea-sharing-purpose-passed

https://discuss.leetcode.com/topic/59955/a-better-solution-based-on-my-first-version-35ms-vs-60ms

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

public class Solution { public boolean canCross(int[] stones) { Objects.requireNonNull(stones); if(stones.length==1)return true;//one stone means the one to the other side if(stones.length==2) return (stones[1]==1?true:false); //this is an adjacency list. and our target is to figure out //if there's a path to a node following certain restrictions //Controversy to traditional use of adjacency list, this list is built up on the fly Map<Integer, Set<Integer>> validMovements = new HashMap<Integer, Set<Integer>>(); for(int i:stones){ validMovements.put(i, new HashSet<Integer>()); } validMovements.get(0).add(1); return dfs(validMovements,1,1,stones[stones.length-1]); } private boolean dfs(Map<Integer, Set<Integer>> validPositions, int curPosition, int lastJumpUnits, int endPosition){ boolean reachable = false; for(int i=-1;i<=1;i++){ int nextPosition = curPosition + lastJumpUnits+i; if(nextPosition==endPosition){ return true; } //lastJumpUnits+i=0, not jumping, will make infinite loop so to avoid it if(lastJumpUnits+i>0 && validPositions.containsKey(nextPosition) && !validPositions.get(nextPosition).contains(lastJumpUnits+i)){ //we go here only when nextPosition is valid and nextPosition's movement has not been done //validPositions.get(nextPosition).add(lastJumpUnits+i); reachable = dfs(validPositions,nextPosition,lastJumpUnits+i,endPosition); if(reachable)break; } } validPositions.get(curPosition).add(lastJumpUnits); return reachable; } }

Longest Common Subsequence LCS -- Again

When I see this again, I admired people coming up this solution again. Posting it here to learn it again.

Given two strings, when trying to find out LCS,  we split things into three cases, first two cases are when first characters do not match:
Case 1: We don't use the first character of the first string.
Case 2: We don't use the first character of the second string.
Case 3: We match up the first character of each string.
The third case is obviously only possible if the first characters match.
Once we have decided which of these options we are going to use, we have reduced the problem to one of a smaller size: we want to find the LCS of the remaining strings, which are suffixes of the original strings.
The terminating condition for the DP occurs when one of the strings is empty - in that case, the length of the LCS is 0.

This results in the following code:

// lcs is an array of dimensions [M+1][N+1]
// s is first string of length M
// t is second string of length N
//lcs[i][j] means LCS is comparing the two strings with s starts from position i and t starts from j

for (int i=M; i>=0; i--){  // using the ith character onwards of first string
    for (int j=N; j>=0; j--) {   // using the jth character onwards of second string
        if (i==M || j==N) lcs[i][j]=0;   // empty string
        else {
            lcs[i][j] = max(lcs[i+1][j],lcs[i][j+1]);   // first two cases
            if (s[i]==t[j]) lcs[i][j] = max(lcs[i][j], lcs[i+1][j+1] + 1);   // third case
        }
    }
}


This code runs in O(MN) time.  lcs[0][0] will hold the length of the longest common subsequence of both strings.

Static Class in Java

There is no top level static class.

You can only create static nested class in Java. And it is treated as a top-level class.

Since it's a static member of enclosing class, it can access all static members in enclosing class.

Defined like this:

public class OuterClass{
public static class StaticNestedClass{
//variable
//method
}

public class InnerClass{
//access even private members of OuterClass

}
}

Name of Inner class was given to non-static class of OuterClass.

Local class is the one defined inside method.

Anonymous class is the one created from interface.

Instantiate static nested class. Each instance is itself a single instance. Do not be fulled by static keyword here. static here means this is a static member of OuterClass, when using it, it is treated as top-level class.

OutClass.StaticNestedClass snc1 = new OutClass.StaticNestedClass();
OutClass.StaticNestedClass snc2 = new OutClass.StaticNestedClass();

Inner class has to be instantiated from instance of OuterClass.

OuterClass oc = new OuterClass();
OuterClass.InnerClass ocic = oc.new OuterClass.InnerClass();

Instantiate anonymous class

Interface Service {
//some code
}

Service s = new Service(){
//code to implement inteface methods
}

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(); */

Revisit the LCS

Taken from codechief.

The standard LCS problem

Given two strings, when trying to find out LCS,  we split things into three cases:

Case 1: We don't use the first character of the first string.

Case 2: We don't use the first character of the second string.

Case 3: We match up the first character of each string.

The third case is obviously only possible if the first characters match.

Once we have decided which of these options we are going to use, we have reduced the problem to one of a smaller size: we want to find the LCS of the remaining strings, which are suffixes of the original strings.

The terminating condition for the DP occurs when one of the strings is empty - in that case, the length of the LCS is 0.

This results in the following code:

[code]

// lcs is an array of dimensions [M+1][N+1]

// s is first string of length M

// t is second string of length N

//lcs[i][j] means LCS is comparing the two strings from position i and j

for (int i=M; i>=0; i--)  // using the ith character onwards of first string

for (int j=N; j>=0; j--) {   // using the jth character onwards of second string

    if (i==M || j==N) lcs[i][j]=0;   // empty string

    else {

        lcs[i][j] = max(lcs[i+1][j],lcs[i][j+1]);   // first two cases

        

        if (s[i]==t[j]) lcs[i][j] = max(lcs[i][j], lcs[i+1][j+1] + 1);   // third case

    }

}

[/code]

This code runs in O(MN) time.  lcs[0][0] will hold the length of the longest common subsequence of both strings. 

Ransom Note

Ransom 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.

1 2 3

canConstruct("a", "b") -> false canConstruct("aa", "ab") -> false canConstruct("aa", "aab") -> true

Original url：leetcode Ransom Note

Analysis:

This is to count the number of characters in magazine and characters in ransom note. use haspmap or array. since note contains only lowercase letters, array is enought.

This is also a method to tell if a set is a subset of another set.

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

public class Solution { public boolean canConstruct(String ransomNote, String magazine) { int[] cnt = new int[26]; //collect statistics of characters in magzine for (int i = 0; i < magazine.length(); i++){ cnt[magazine.charAt(i) - 97]++; } //consume the statistics by examing the ransom note for (int i = 0; i < ransomNote.length(); i++){ if (--cnt[ransomNote.charAt(i) - 97] < 0){ return false; } } return true; } }