LeetCode [313] Super Ugly Number

Ref
[1] https://leetcode.com/problems/super-ugly-number/

LeetCode [273] Integer to English Words

Convert a non-negative integer to its english words representation. Given input is guaranteed to be less than 231 - 1.

Example 1:

Input: 123
Output: "One Hundred Twenty Three"

Example 2:

Input: 12345
Output: "Twelve Thousand Three Hundred Forty Five"

Example 3:

Input: 1234567
Output: "One Million Two Hundred Thirty Four Thousand Five Hundred Sixty Seven"

Example 4:

Input: 1234567891
Output: "One Billion Two Hundred Thirty Four Million Five Hundred Sixty Seven Thousand Eight Hundred Ninety One"

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

class Solution { vector<string> lessThan20, tens, thousands; public: string numberToWords(int num) { if(num==0) return "Zero"; lessThan20 = vector<string>{"", "One", "Two", "Three", "Four", "Five", "Six", "Seven", "Eight", "Nine", "Ten", "Eleven", "Twelve", "Thirteen", "Fourteen", "Fifteen", "Sixteen", "Seventeen", "Eighteen", "Nineteen"}; tens = vector<string>{"", "Ten", "Twenty", "Thirty", "Forty", "Fifty", "Sixty", "Seventy", "Eighty", "Ninety"}; string ret = helper(num); string s; for(int i=0; i<ret.size(); ++i) { if((i>0 && ret[i]==' ' && ret[i-1]==' ') || (i==ret.size()-1 && ret[i]==' ')) continue; else s += ret[i]; } return s; } string helper(int num) { if(num < 20) return lessThan20[num]; else if(num<100){ return tens[num/10] + " " + helper(num%10); }else if(num<1000) { return lessThan20[num/100] + " " + "Hundred" + " " + helper(num%100); }else if(num<1000000) { return helper(num/1000) + " " + "Thousand" + " " + helper(num%1000); }else if(num<1000000000) { return helper(num/1000000) + " " + "Million" + " " + helper(num%1000000); }else { return helper(num/1000000000) + " " + "Billion" + " " + helper(num%1000000000); } } };

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

class Solution { Map<Integer, String> map = new HashMap<>(); public String numberToWords(int num) { map.put(0, "Zero"); map.put(1, "One"); map.put(2, "Two"); map.put(3, "Three"); map.put(4, "Four"); map.put(5, "Five"); map.put(6, "Six"); map.put(7, "Seven"); map.put(8, "Eight"); map.put(9, "Nine"); map.put(10, "Ten"); map.put(11, "Eleven"); map.put(12, "Twelve"); map.put(13, "Thirteen"); map.put(14, "Fourteen"); map.put(15, "Fifteen"); map.put(16, "Sixteen"); map.put(17, "Seventeen"); map.put(18, "Eighteen"); map.put(19, "Nineteen"); map.put(20, "Twenty"); map.put(30, "Thirty"); map.put(40, "Forty"); map.put(50, "Fifty"); map.put(60, "Sixty"); map.put(70, "Seventy"); map.put(80, "Eighty"); map.put(90, "Ninety"); map.put(100, "Hundred"); map.put(1000, "Thousand"); map.put(1000000, "Million"); map.put(1000000000, "Billion"); return helper(num); } String toString(int gra, int num){ int cnt = num/gra; String s = helper(cnt) + " " + map.get(gra) ; int r = num%gra; if(r>0) s += " " + helper(r); return s; } String helper(int num){ String s = ""; if(num<=20) return map.get(num); else if(num<100){//(20, 100) int r = num%10; s = map.get(num-r); if(r>0) s += " " + helper(r); return s; }else if(num<1000){//[10 , 1000) s = toString(100, num); }else if(num<1000000){//[1000, 1000000) s = toString(1000, num); }else if(num<1000000000){//[1000000, 1000000000) s = toString(1000000, num); }else{//[1000000000, s = toString(1000000000, num); } return s; } }

LeetCode [263] Ugly Number

Ref
[1] https://leetcode.com/problems/ugly-number/
OJ
[2] http://www.geeksforgeeks.org/ugly-numbers/

LeetCode [258] Add Digits

===================================
0  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  ...
===================================
Ref
[1] https://leetcode.com/problems/add-digits/
[2] https://leetcode.com/discuss/52122/accepted-time-space-line-solution-with-detail-explanations
OJ

MJ [2]

Questions: Similar to LeetCode Permutation Sequence [1] except the numbers in nums are not unique. In Test, there are 4 numbers whose permutations are in increasing order, find the sequence number (1-based) of one of its permutation in the sequence. Eg., if nums=[2 1 2 3] it should return 4; if nums=[3 1 2 2] it should return 10.

Test:
 1 2 2 3---1
 1 2 3 2---2
 1 3 2 2---3
 2 1 2 3---4
 2 1 3 2---5
 2 2 1 3---6
 2 2 3 1---7
 2 3 1 2---8
 2 3 2 1---9
 3 1 2 2---10
 3 2 1 2---11
 3 2 2 1---12

============ =====================


Ref
[1] https://leetcode.com/problems/permutation-sequence/
[2] http://www.mitbbs.com/article_t/JobHunting/33021689.html
[3] http://www.mitbbs.com/article_t1/JobHunting/32952623_0_1.html
Zenefits MJ, replace numbers with chars.

LeetCode [248] Strobogrammatic Number III

248. Strobogrammatic Number III

Hard

A strobogrammatic number is a number that looks the same when rotated 180 degrees (looked at upside down).

Write a function to count the total strobogrammatic numbers that exist in the range of low <= num <= high.

Example:

Input: low = "50", high = "100"
Output: 3 
Explanation: 69, 88, and 96 are three strobogrammatic numbers.

Note:
Because the range might be a large number, the low and high numbers are represented as string.

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

class Solution { public int strobogrammaticInRange(String low, String high) { int ret = 0; for(int i = low.length(); i<=high.length(); ++i){ List<String> list = compose(i, i); for(String s : list){ if(Long.parseLong(s)>=Long.parseLong(low) && Long.parseLong(s)<=Long.parseLong(high)) ret++; } } return ret; } List<String> compose(int n, int N){ List<String> list = new ArrayList<>(); if(n==0){ list.add(""); }else if(n==1){ list.addAll(Arrays.asList("0", "1", "8")); }else{ List<String> tmp = compose(n-2, N); for(String s : tmp){ list.addAll(Arrays.asList("1"+s+"1","8"+s+"8","6"+s+"9","9"+s+"6")); if(n<N) list.add("0"+s+"0"); } } return list; } }

LeetCode [247] Strobogrammatic Number II

247. Strobogrammatic Number II

Medium

A strobogrammatic number is a number that looks the same when rotated 180 degrees (looked at upside down).

Find all strobogrammatic numbers that are of length = n.

Example:

Input:  n = 2
Output: ["11","69","88","96"]

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

class Solution { public List<String> findStrobogrammatic(int n) { return helper(n, n); } List<String> helper(int n, int N){ List<String> list = new ArrayList<>(); if(n==0){ list.add(""); }else if(n==1){ list.addAll(Arrays.asList("0","1", "8")); }else{ List<String> tmp = helper(n-2, N); for(String s : tmp){ list.addAll(Arrays.asList("1"+s+"1", "8"+s+"8", "6"+s+"9", "9"+s+"6")); if(n<N) list.add("0"+s+"0"); } } return list; } }

LeetCode [246] Strobogrammatic Number

246. Strobogrammatic Number

Easy

A strobogrammatic number is a number that looks the same when rotated 180 degrees (looked at upside down).

Write a function to determine if a number is strobogrammatic. The number is represented as a string.

 

Example 1:

Input: num = "69"
Output: true

Example 2:

Input: num = "88"
Output: true

Example 3:

Input: num = "962"
Output: false

Example 4:

Input: num = "1"
Output: true

//Java
class Solution {
    Map<Character, Character> map = new HashMap<>();
    public boolean isStrobogrammatic(String num) {
        map.put('0', '0');
        map.put('1', '1');
        map.put('6', '9');
        map.put('8', '8');
        map.put('9', '6');

        StringBuilder ret = new StringBuilder();
        for(int i=num.length()-1; i>=0; --i){
            char c = num.charAt(i);
            if(!map.containsKey(c)) return false;
            ret.append(map.get(c));
        }

        return ret.toString().equals(num.toString());
    }
}

//C++
//C++: 0ms
class Solution {
public:
    bool isStrobogrammatic(string num) {
        int n = num.size(), l = 0, r = n-1;
        while(l<=r){
            if(num[l]==num[r] && num[l]!='0' && num[l]!='1' && num[l]!='8') return false;
            if(num[l]!=num[r] && !((num[l]=='6'&&num[r]=='9')||(num[l]=='9'&&num[r]=='6'))) return false;
            l++;
            r--;
        }
        return true;
    }
};

LeetCode [233] Number of Digit One

Note:

• There's one 1 on 1-th digit for every 10 numbers;
• There's ten 1s on 10-th digit for every 100 number;
• There's one hundred 1s on 100-th digit for every 1000 number;
• ......
• line 8 computes the number of 1s on w/10-th digit and denoted it by c
• 
  
• If the input n=14, for example, when computing the number of 1s on 10-th digit, c would be evaluated to 0. However, there are 5 numbers with 1 on 10-th digit (10,11,12,13,14). I use extra at line 10 to handle such case.

  0    1    2     3     4     5     6     7    8    9    one 1 on 1-th digit for every 10 numbers
10  11  12   13   14   15   16   17  18  19    ten 1s on 10-th digit for every 100 numbers 
..............

90  91  92   93   94   95   96   97  98  99
.............
100 101            .....                        109   one hundred 1s on 100-th digit for every 1000 numbers 
.............
190 191            .....                        199

Ref
[1] https://leetcode.com/problems/number-of-digit-one/
OJ

LeetCode [172] Factorial Trailing Zeroes

Note:

• method1: #5 = #trailing zeros
•                ...5...10...15...20...25...30...125...625
• #5              1     1     1     1    2     1      3       4       

 
Ref
[1] https://oj.leetcode.com/problems/factorial-trailing-zeroes/
OJ
[2] https://oj.leetcode.com/discuss/20691/my-explanation-of-the-log-n-solution
method1

LeetCode [171] Excel Sheet Column Number

 171. Excel Sheet Column Number

Easy

Given a column title as appear in an Excel sheet, return its corresponding column number.

For example:

    A -> 1
    B -> 2
    C -> 3
    ...
    Z -> 26
    AA -> 27
    AB -> 28 
    ...

Example 1:

Input: "A"
Output: 1

Example 2:

Input: "AB"
Output: 28

Example 3:

Input: "ZY"
Output: 701

 

Constraints:

• 1 <= s.length <= 7
• s consists only of uppercase English letters.
• s is between "A" and "FXSHRXW".

1 2 3 4 5 6 7 8 9 10 11

class Solution { public: int titleToNumber(string s) { int res = 0; int n = s.size(); for(int i=0; i<n; ++i){ res = res*26+(s[i]-'A'+1); } return res; } };

1 2 3 4 5 6 7 8 9 10

class Solution { public int titleToNumber(String s) { int x = 0; for(char c : s.toCharArray()){ int k = c - 'A'; x = x*26+k+1; } return x; } }