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

First Smallest Number After Self

1.给一个int[]nums,返回int[] ans, ans[i]是i右边第一个小于等于nums[i]的数字，如果不存在，ans[i]=0

2.算法：
用一个stack维护单调递减
每个元素只出栈1次因此是线性

维护stack／queue思想的一道题： Sliding Window Maximum

 public static int[] firstRightSmallEqual(int[] nums){  
           Stack<Integer> stack = new Stack<>();  
           int[] ans = new int[nums.length];  
           for(int i = nums.length-1;i>=0; i--){  
                while(!stack.empty() && nums[stack.peek()] > nums[i]){  
                     stack.pop();  
                }  
                if(!stack.empty()) ans[i] = nums[stack.peek()];  
                stack.push(i);  
           }  
           return ans;  
      }  

Smallest Number After Self

1.给一个int[]nums,返回int[] ans, ans[i]是i右边小于等于nums[i]的最大数，如果不存在，ans[i]=0

2.算法：
建立一个bst，找predecessor

      public static int[] biggestSmallerAfterSelf(int[] nums){  
           TreeSet<Integer> root = new TreeSet<>();  
           int[] ans = new int[nums.length];  
           for(int i = nums.length-1; i>=0; i--){  
                Integer pred = root.floor(nums[i]);  
                if(pred!=null){  
                     ans[i] = pred;  
                }  
                root.add(nums[i]);  
           }  
           return ans;  
      }  

Metals hackRank

Mr. Octopus has recently shut down his factory and want to sell off his metal rods to a local businessman.

In order to maximize profit, he should sell the metal of same size and shape. If he sells  metal rods of length , he receives N x L x metal_price. The remaining smaller metal rods will be thrown away. To cut the metal rods, he needs to pay cost_per_cut for every cut.

What is the maximum amount of money Mr. Octopus can make?

Input Format 
First line of input contains cost_per_cut 
Second line of input contains metal_price 
Third line contains L, the number of rods Mr. Octopus has, followed by L integers in each line representing length of each rod.

Output Format 
Print the result corresponding to the testcase.

Constraints 
1 <= metal_price, cost_per_cut <= 1000 
1 <= L <= 50 
Each element of lenghts will lie in range [1, 10000].

Sample Input#00

1
10
3
26
103
59

Sample Output#00

1770

Explanation Here cuts are pretty cheap. So we can make large number of cuts to reduce the amount of wood wasted. Most optimal lengths of rods will be . So we will cut  pieces of length  from  rod, and throw peice of length  from it. Similarly we will cut  pieces of length  from  rod and throw away a piece of length . From  rod, we will cut  pieces of length  and throw a piece of length . So in total we have  pieces of length and we have made  cuts also. So total profit is 

Sample Input#01

100
10
3
26
103
59

Sample Output#01

1230

Explanation Here we will throw smallest rod entirely and cut the pieces of length 51 from both left. So profit is 

Brute Force

  public static int maxProfit(int cost, int price, List<Integer> rods){  
     int upper = 0;  
     for(int rod: rods){  
       upper = Math.max(rod,upper);  
     }  
     int max = 0;  
     for(int cutLen = 1; cutLen <= upper; cutLen++){  
       max = Math.max(max,profit(cost,price,cutLen,rods));  
     }  
     System.out.println(max);  
     return max;  
   }  
   public static int profit(int cost, int price, int cutLen, List<Integer> rods){  
     int sum = 0;  
     for(int rod: rods){  
       //cut each rod  
       if(rod < cutLen){  
         continue;  
       }  
       int cutCount = rod%cutLen == 0? rod/cutLen-1 : rod/cutLen;  
       int count = rod/cutLen;  
       sum += Math.max(0,price*cutLen*count - cutCount*cost);  
     }  
     return sum;  
   }  

Royal Name

1. 题意：

给你一个list of string，每个string 是由一个firstName 以及一个Roman 数字构成。

eg. Louis X， Louis VIII

Roman数字是1-50 I, V, X, L

返回sorted list : Louis VIII, Louis X

2.算法：

这个题是一个sort 题。 要用一个Comparator实例

 public void sortedRoyalName(String[] names){  
   Arrays.sort(names, (a,b)->{  
     String[] name1 = a.split("//s");  
     String[] name2 = b.split("//s");  
     if(name1[0].equals(name2[0])){  
       return Integer.comare(romanToInt(name1[1]),romanToInt(name1[1]));   
     }  
     return name1[0].compareTo(name2[0]);  
   });  
 }  
 public int romanToInt(String s) {  
      int ans = 0;  
     HashMap<String,Integer> RomanToIntMap = new HashMap<>();  
     RomanToIntMap.put("I",1);  
     RomanToIntMap.put("V",5);  
     RomanToIntMap.put("X",10);  
     RomanToIntMap.put("L",50);  
     RomanToIntMap.put("C",100);  
     RomanToIntMap.put("C",100);  
     RomanToIntMap.put("D",500);  
     RomanToIntMap.put("M",1000);  
     int i = 0;  
     while(i < s.length()){  
       if(i!= s.length()-1 && RomanToIntMap.get(s.substring(i,i+1)) < RomanToIntMap.get(s.substring(i+1,i+2))){  
         ans += RomanToIntMap.get(s.substring(i+1,i+2)) - RomanToIntMap.get(s.substring(i,i+1)) ;  
         i+=2;  
         continue;  
       }  
       ans += RomanToIntMap.get(s.substring(i,i+1));  
       i++;  
     }  
     return ans;  
   }  

数列 Reduction

1. 题意：

给一个数列 eg. [1,2,3]，nums[i]+nums[j] 然后把这个数字放回array，这次操作的cost就是nums[i]+nums[j]，[3,3]。重复步骤，直到array里边只有1个数字。这个步骤要循环n-1次。因为每次数量减1。

求minimum cost 3+6 = 9

2. 算法：

想要最小cost，那么每次选的nums[i] 和 nums[j]应该是这个array里边的最小值。因为如果加了一个值，那么这个值在某个时刻还要再加不知道几遍。因此越小越好。

易错点：先sort array，按照从小数开始加，每次加前一个sum
对于[1,2,2,2,2,3] 而言最小是 [1,2,2,2,2,3]  -> [2,2,2,3,3] ->[2,3,3,4] ->[3,4,5]->[5,7]->[12]
minSum = 3+ 4+5+7+12
如果按照错误算法是[1,2,2,2,2,3]  -> [3,2,2,2,3] -> [5,2,2,3]->[7,2,3]->[9,3]->[12]
minSum = 3+5+7+9+12

 public int reductionCost(int[] nums){  
   if(nums.length <= 1) return 0;  
   int sum = 0;  
   PriorityQueue<Integer> pq = new PriorityQueue<>();  
   for(int num : nums){  
     pq.add(num);  
   }  
   while(pq.size()>1){  
     int x = pq.poll();  
     int y = pq.poll();  
     sum += x+y;  
     pq.offer(x+y);  
   }  
   return sum;  
 }