319. Bulb Switcher

There are n bulbs that are initially off. You first turn on all the bulbs. Then, you turn off every second bulb. On the third round, you toggle every third bulb (turning on if it's off or turning off if it's on). For the ith round, you toggle every i bulb. For the nth round, you only toggle the last bulb. Find how many bulbs are on after n rounds.

Example:

Given n = 3. 

At first, the three bulbs are [off, off, off].
After first round, the three bulbs are [on, on, on].
After second round, the three bulbs are [on, off, on].
After third round, the three bulbs are [on, off, off]. 

So you should return 1, because there is only one bulb is on

int bulbSwitch(int n) {
    return sqrt(n);
}

A bulb ends up on iff it is switched an odd number of times.

Call them bulb 1 to bulb n. Bulb i is switched in round d if and only if d divides i. So bulb i ends up on if and only if it has an odd number of divisors.

Divisors come in pairs, like i=12 has divisors 1 and 12, 2 and 6, and 3 and 4. Except when i is a square, like 36 has divisors 1 and 36, 2 and 18, 3 and 12, 4 and 9, and double divisor 6. So bulb i ends up on if and only if i is a square.

So just count the square numbers.

Let R = int(sqrt(n)). That's the root of the largest square in the range [1,n]. And 1 is the smallest root. So you have the roots from 1 to R, that's R roots. Which correspond to the R squares. So int(sqrt(n)) is the answer. (C++ does the conversion to int automatically, because of the specified return type).

423. Reconstruct Original Digits from English

Given a non-empty string containing an out-of-order English representation of digits 0-9, output the digits in ascending order.

Note:

1. Input contains only lowercase English letters.
2. Input is guaranteed to be valid and can be transformed to its original digits. That means invalid inputs such as "abc" or "zerone" are not permitted.
3. Input length is less than 50,000.

Example 1:

Input: "owoztneoer"

Output: "012"

Example 2:

Input: "fviefuro"

Output: "45"

只有10个数字的string， 因此可以穷举。
看到有一些数字有特殊独有的character

发现分三步就可以完成
1: zero， two，six，eight，four   除掉string s中的这些后可以做第二步
2. one，three，five, seven
3. nine，ten

因此需要1个size为3 的step map list存每个step map<Character,Integer>
除掉这步中算过的character 就从count map中删掉

   public String originalDigits(String s) {  
     List<Map<Character,Integer>> stepsMap = new ArrayList<>();      
     Map<Character,String> dict = new HashMap<>();   
     Map<Character,Integer> step1 = new HashMap<>();   
     step1.put('z',0);dict.put('z',"zero");  
     step1.put('w',2);dict.put('w',"two");  
     step1.put('u',4);dict.put('u',"four");  
     step1.put('x',6);dict.put('x',"ix");  
     step1.put('g',8);dict.put('g',"eight");  
     Map<Character,Integer> step2 = new HashMap<>();   
     step2.put('o',1);dict.put('o',"one");  
     step2.put('h',3);dict.put('h',"three");  
     step2.put('f',5);dict.put('f',"five");  
     Map<Character,Integer> step3 = new HashMap<>();   
     step3.put('v',7);dict.put('v',"seven");  
     step2.put('i',9);dict.put('i',"nine");  
     stepsMap.add(step1);stepsMap.add(step2);stepsMap.add(step3);  
     Map<Character,Integer> count = new HashMap<>();   
     for(int i = 0; i< s.length();i++){  
       char c = s.charAt(i);  
       count.putIfAbsent(c,0);  
       count.put(c,count.get(c)+1);  
     }  
     int[] digits = new int[10];  
     //3 steps  
     for(int i = 0; i < stepsMap.size(); i++){  
       Map<Character,Integer> step = stepsMap.get(i);  
       for(char c : step.keySet()){  
         if(count.containsKey(c)){  
           int occur = count.get(c);  
           digits[step.get(c)] = occur;  
           String str = dict.get(c);  
           for(int j = 0; j < str.length();j++){  
             char d = str.charAt(j);  
             count.put(d,count.get(d)-occur);  
             if(count.get(d) == 0)  
               count.remove(d);  
           }  
         }  
       }  
     }  
     StringBuilder sb = new StringBuilder();  
     for(int i = 0; i < 10; i++){  
       while(digits[i]-- >0)  
         sb.append(""+i);  
     }  
     return sb.toString();  
   }  

O(n) 1pass
按照计算顺序，统计相对特殊字符（10个）的出现次数
计算完上一步的特殊字符，例如知道0出现了两次，那么0 这个数字在cout 'o' 也出现了两次，从o的count中减去2

public String originalDigits(String s) {
    int[] count = new int[10];
    for (int i = 0; i < s.length(); i++){
        char c = s.charAt(i);
        if (c == 'z') count[0]++;
        if (c == 'w') count[2]++;
        if (c == 'x') count[6]++;
        if (c == 's') count[7]++; //7-6
        if (c == 'g') count[8]++;
        if (c == 'u') count[4]++; 
        if (c == 'f') count[5]++; //5-4
        if (c == 'h') count[3]++; //3-8
        if (c == 'i') count[9]++; //9-8-5-6
        if (c == 'o') count[1]++; //1-0-2-4
    }
    count[7] -= count[6];
    count[5] -= count[4];
    count[3] -= count[8];
    count[9] = count[9] - count[8] - count[5] - count[6];
    count[1] = count[1] - count[0] - count[2] - count[4];
    StringBuilder sb = new StringBuilder();
    for (int i = 0; i <= 9; i++){
        for (int j = 0; j < count[i]; j++){
            sb.append(i);
        }
    }
    return sb.toString();
}