Subsets

78. Subsets

Example:

Input: nums = [1,2,3]
Output:
[
  [3],
  [1],
  [2],
  [1,2,3],
  [1,3],
  [2,3],
  [1,2],
  []
]

Solution 1: think from previous result

Say we already have the subsets of [1,2], now we add 3 .
The only thing we need to do is add 3 to every previous result.
That's it.

def subsets(self, nums):
    ret = [[]]
    for num in nums:
        if not ret:
            ret.append(num)
        else:
            length = len(ret)
            for i in xrange(length):
                ret.append(ret[i][:])
                ret[-1].append(num)
    return ret

Solution 2: DFS

For each number, it could form a subset with it's subsequence.
for nothing: []
for 1: [1], [1,2],[1,2,3]
for 2: [2], [2,3]
for 3: [3]

class Solution(object):
    def subsets (self, nums):
        res = []
        self.dfs(nums, 0, [], res)
        return res
    
    def dfs(self, nums, index, path, res):
        res.append(path)
        for i in xrange(index, len(nums)):
            self.dfs(nums, i+1, path+[nums[i]], res)

90. Subsets II 

Input could contains duplicates
Example: [1,2,2], [5,5,5]
Sort the list first, nums[i] == nums[i-1] if nums[i] has duplicates

for [1,2] subsets [], [1], [2], [1,2]
next we add another 2, we only need to add it to [2] and [1,2] 
which is the start point of previous 2.

for[5,5] subsets [], [5], [5,5]
next we add 5, we only need to add it to [5,5] 
which is the start point of previous 5.
def subsetsWithDup(self, nums):       
    ret = [[]]
    nums.sort()
    lastIdx = 0

    for k, num in enumerate(nums):
        length = len(ret)
        idx = 0
        if k != 0 and nums[k] == nums[k-1]:
            idx = lastIdx
        lastIdx = len(ret)
        for i in xrange(idx, length):
            ret.append(ret[i][:])
            ret[-1].append(num)
    return ret

440. K-th Smallest in Lexicographical Order

Given integers n and k, find the lexicographically k-th smallest integer in the range from 1 to n.

Note: 1 ≤ k ≤ n ≤ 109.

Example:

Input:
n: 13   k: 2

Output:
10

Explanation:
The lexicographical order is [1, 10, 11, 12, 13, 2, 3, 4, 5, 6, 7, 8, 9], so the second smallest number is 10.

It's a complete (not full) denary tree. The BFS result is normal order and the DFS result is lexicographical order.
No need to run DFS because there isand all other children are full.

 public class Solution {  
   public int findKthNumber(int n, int k) {  
     String prefix = "";  
     while(k != 0){  
       //find each digit for nth number from most significant to least significant  
       //each digit range from 0 to 9  
       int i = 0;   
       for(;i <= 9; i++){  
         //we count numbers in the same tree, when count is bigger than n for the first time  
         //we found the digit   
         int count = countPrefix(n,prefix+i);  
         if(count < k){  
           k -= count;  
         }else{  
           break;  
         }  
       }  
       prefix = prefix + i;  
       k--;  
     }  
     return Integer.valueOf(prefix);  
   }  
   public int countPrefix(int n, String prefix){  
     long a = Long.valueOf(prefix);  
     if(a == 0||a>n) return 0;  
     long b = a + 1;  
     int count = 1;//a   
     a*=10;b*=10;// next level  
     while(a <= n){  
       count += Math.min(n+1,b) - a;  
       a*=10;b*=10;// next level    
     }  
     return count;  
   }  
 }  

439. Ternary Expression Parser

Given a string representing arbitrarily nested ternary expressions, calculate the result of the expression. You can always assume that the given expression is valid and only consists of digits 0-9, ?, :, T and F (T and F represent True and False respectively).

Note:

1. The length of the given string is ≤ 10000.
2. Each number will contain only one digit.
3. The conditional expressions group right-to-left (as usual in most languages).
4. The condition will always be either T or F. That is, the condition will never be a digit.
5. The result of the expression will always evaluate to either a digit 0-9, T or F.

Example 1:

Input: "T?2:3"

Output: "2"

Explanation: If true, then result is 2; otherwise result is 3.

Example 2:

Input: "F?1:T?4:5"

Output: "4"

Explanation: The conditional expressions group right-to-left. Using parenthesis, it is read/evaluated as:

             "(F ? 1 : (T ? 4 : 5))"                   "(F ? 1 : (T ? 4 : 5))"
          -> "(F ? 1 : 4)"                 or       -> "(T ? 4 : 5)"
          -> "4"                                    -> "4"

Example 3:

Input: "T?T?F:5:3"

Output: "F"

Explanation: The conditional expressions group right-to-left. Using parenthesis, it is read/evaluated as:

             "(T ? (T ? F : 5) : 3)"                   "(T ? (T ? F : 5) : 3)"
          -> "(T ? F : 3)"                 or       -> "(T ? F : 5)"
          -> "F"                                    -> "F"

从右往左看，这个表达式我们可以试着看一看。
每次计算都是以‘?’ 为标志，当我们碰到'?'的时候，我们计算local result，并不需要区分trueStack VS. falseStack 因为我们碰到?的时候只需要看最近的三个点就可以了。即使是
?():() 这样的表达式，因为我们已经算过local的结果，因此还是比较最近的三个点。

 public String parseTernary(String expression) {  
     // why only judge on ?  
     // we look from right to left, think how we do it when we compute  
     // we ignore things except '?', when we meet '?', we look at nearby three elements  
     // event through ?():(), this situation, we've already calculated result for things inside()  
     // use stack to preserve previous solutions  
     Stack<Character> stack = new Stack<>();  
     for(int i = expression.length()-1; i>=0; i--){  
       if(expression.charAt(i) == '?'){  
         char t = stack.pop();  
         stack.pop();  
         char f = stack.pop();  
         if(expression.charAt(i-1) == 'F'){  
           stack.push(f);  
         }else {  
           stack.push(t);  
         }  
         i--;  
       }else{  
         stack.push(expression.charAt(i));  
       }  
     }  
     return stack.pop()+"";  
   }  

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

解法：

这个题a/b, b/c, so we know a/c 因此是一个graph问题

edge case：

a/b thus we also know b/a 因此是一个undirected graph

a/b, a/c 所以图结构为：

Map<String,Map<String,Double>>

<a,<b,v1>,<c,v2>>, <b,<a, v1>>,<c,<a, v2>>

  Map<String,Map<String,Double>> dividendToDivisor = new HashMap<>();  
   public boolean notFound = true;  
   public double[] calcEquation(String[][] equations, double[] values, String[][] queries) {  
     for(int i = 0; i < equations.length; i++){  
       String[] eq = equations[i];  
       dividendToDivisor.putIfAbsent(eq[0],new HashMap<>());  
       dividendToDivisor.get(eq[0]).put(eq[1],values[i]);  
       dividendToDivisor.putIfAbsent(eq[1],new HashMap<>());  
       dividendToDivisor.get(eq[1]).put(eq[0],1/values[i]);  
     }  
     double[] ans = new double[queries.length];  
     for(int i = 0; i < queries.length; i++){  
       String[] q = queries[i];  
       notFound = true;  
       ans[i] = find(q[0],q[1],new HashSet<>());  
     }  
     return ans;    
   }  
   public double find(String x, String y,Set<String> visited){  
     // System.out.println(x+" "+y+(visited.contains(x)||!dividendToDivisor.containsKey(x)));  
     if(visited.contains(x) || !dividendToDivisor.containsKey(x)) return -1;  
     if(x.equals(y)) {notFound = false; return 1.0;}  
     visited.add(x);  
     for(Map.Entry<String, Double> entry: dividendToDivisor.get(x).entrySet()) {  
       String next = entry.getKey();  
       double ans = find(next,y,visited);  
       if(!notFound)   
         return dividendToDivisor.get(x).get(next)*ans;  
     }  
     visited.remove(x);  
     return -1;  
   }  

Counting Groups

1.题意：
输入2D matrix(n*n),每个cell为0或1，如果|i1-i2|+|j1-j2|=1 and both value =1那么是一个group里边的。
再给你一个group size list, 每个元素是group size大小，返回一个相应的list，每个元素是对应group size 的group 数

2.算法：
首先|i1-i2|+|j1-j2|=1 这个条件是(i,j)的上下左右满足，其次要value都是1

对value是1的点进行dfs，用一个visited hash 来避免重复

用map sizeToCount 记录group size 和这个size的group数量

 public static void group(int[][] matrix){   
       int n = matrix.length;  
    Map<Integer,Integer> visited = new HashMap<>();   
    for(int i = 0; i < n; i++){   
       for(int j = 0; j < n; j++){   
         dfs(matrix,visited,i,j);   
       }   
    }   
  }   
 public static int dfs(int[][]matrix,Map<Integer,Integer>visited,int i, int j){   
       int n = matrix.length;  
    if(i<0||j<0||i>=n||j>=n) return 0;   
    if(matrix[i][j] == 0 || !visited.containsKey(i*n+j)) return 0;   
    int ans = 1;   
    visited.put(i*n+j,0);   
    ans += dfs(matrix,visited,i-1,j);   
    ans += dfs(matrix,visited,i,j-1);   
    ans += dfs(matrix,visited,i+1,j);   
    ans += dfs(matrix,visited,i,j+1);   
    visited.put(i*n+j,ans);   
    sizeToCount.putIfAbsent(ans,0);  
    sizeToCount.put(ans,sizeToCount.get(ans)+1);  
    return ans;   
  }