LIKE CODING: Solution

Showing posts with label Solution. Show all posts

Sunday, August 30, 2015

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"

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);
        }
    }
};

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;
    }
}

Friday, August 28, 2015

LeetCode [271] Encode and Decode Strings

271. Encode and Decode Strings

Medium

Design an algorithm to encode a list of strings to a string. The encoded string is then sent over the network and is decoded back to the original list of strings.

Machine 1 (sender) has the function:

string encode(vector<string> strs) {
  // ... your code
  return encoded_string;
}

Machine 2 (receiver) has the function:

vector<string> decode(string s) {
  //... your code
  return strs;
}

So Machine 1 does:

string encoded_string = encode(strs);

and Machine 2 does:

vector<string> strs2 = decode(encoded_string);

strs2 in Machine 2 should be the same as strs in Machine 1.

Implement the encode and decode methods.

Note:

The string may contain any possible characters out of 256 valid ascii characters. Your algorithm should be generalized enough to work on any possible characters.
Do not use class member/global/static variables to store states. Your encode and decode algorithms should be stateless.
Do not rely on any library method such as eval or serialize methods. You should implement your own encode/decode algorithm.

//C++: 92ms
typedef unsigned char uchar;

class Codec {
public:

    // Encodes a list of strings to a single string.
    string encode(vector<string>& strs) {
        string ret;
        for(auto s:strs){
            int i = 0, len = s.size(), cnt;
            while(i<len){
                cnt = 1;
                uchar c = s[i++];
                while(i<len && (uchar)s[i]==c && cnt<254){
                    i++; cnt++;
                }
                ret += (uchar)cnt;
                ret += c;
            }
            ret += (uchar)255;
        }
        return ret;
    }

    // Decodes a single string to a list of strings.
    vector<string> decode(string s) {
        vector<string> ret;
        string cur;
        int i=0, len = s.size();
        while(i<len){
            uchar c = s[i++];
            if(c==(uchar)255){
                ret.push_back(cur);
                cur.clear();
            }else{
                int cnt = c;
                c = s[i++];
                for(int i=0; i<cnt; ++i) cur += c;
            }
        }
        return ret;
    }
};

public class Codec {
	// Encodes a list of strings to a single string.
    public String encode(List<String> strs) {
        StringBuilder sb = new StringBuilder();
        for(String s : strs) {
            sb.append(s.length()).append('/').append(s);
        }
        return sb.toString();
    }

    // Decodes a single string to a list of strings.
    public List<String> decode(String s) {
        List<String> ret = new ArrayList<String>();
        int i = 0;
        while(i < s.length()) {
            int slash = s.indexOf('/', i);
            int size = Integer.valueOf(s.substring(i, slash));
            i = slash + size + 1;
            ret.add(s.substring(slash + 1, i));
        }
        return ret;
    }
}

// Your Codec object will be instantiated and called as such:
// Codec codec = new Codec();
// codec.decode(codec.encode(strs));

Wednesday, August 26, 2015

LeetCode [270] Closest Binary Search Tree Value

270. Closest Binary Search Tree Value

Easy

Given the root of a binary search tree and a target value, return the value in the BST that is closest to the target.

Example 1:

Input: root = [4,2,5,1,3], target = 3.714286
Output: 4

Example 2:

Input: root = [1], target = 4.428571
Output: 1

Constraints:

The number of nodes in the tree is in the range [1, 104].
0 <= Node.val <= 109
-109 <= target <= 109

/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode() {}
 *     TreeNode(int val) { this.val = val; }
 *     TreeNode(int val, TreeNode left, TreeNode right) {
 *         this.val = val;
 *         this.left = left;
 *         this.right = right;
 *     }
 * }
 */
class Solution {
    int value = -1;
    public int closestValue(TreeNode root, double target) {
        helper(root, target);
        return value;
    }
    
    void helper(TreeNode node, double target){
        if(node==null) return;
        if(value == -1 || Math.abs(value-target)>Math.abs(node.val-target)){
            value = node.val;
        }
        if(target<node.val) helper(node.left, target);
        if(target>node.val) helper(node.right, target);
    }
}

Monday, August 24, 2015

LeetCode [269] Alien Dictionary

There is a new alien language which uses the latin alphabet. However, the order among letters are unknown to you. You receive a list of non-empty words from the dictionary, where words are sorted lexicographically by the rules of this new language. Derive the order of letters in this language.

Example 1:

Input:
[
  "wrt",
  "wrf",
  "er",
  "ett",
  "rftt"
]

Output: "wertf"

Example 2:

Input:
[
  "z",
  "x"
]

Output: "zx"

Example 3:

Input:
[
  "z",
  "x",
  "z"
] 

Output: "" 

Explanation: The order is invalid, so return "".

Note:

You may assume all letters are in lowercase.
You may assume that if a is a prefix of b, then a must appear before b in the given dictionary.
If the order is invalid, return an empty string.
There may be multiple valid order of letters, return any one of them is fine.

class Solution {
    Map<Character, Set<Character>> links = new HashMap<>();
    public String alienOrder(String[] words) {
        int i = 0;
        boolean cont = true;

        while(cont)
        {
            String prefix0 = "";
            char pChar = '.';
            cont = false;
            for(String w : words)
            {
                if(w.length() < i) continue; //"er**", if i = 3 skip
                String prefix = w.substring(0, i);
                if(w.length() >= i+1)
                {
                    cont = true;
                    char c =  w.charAt(i);
                    if(!links.containsKey(c)) links.put(c, new HashSet<>());
                    if(prefix.equals(prefix0) && pChar!='.' && pChar != c)
                        links.get(pChar).add(c);
                    pChar = c;
                }else{//w.length() == i
                    // for case "abc","ab"
                    if(prefix.equals(prefix0) && pChar != '.') return "";
                }
                prefix0 = prefix;
            }
            i++;
        }

        Set<Character> visited = new HashSet<Character>();
        Set<Character> path = new HashSet<Character>();
        List<Character> seq = new ArrayList<Character>();

        for(Map.Entry e : links.entrySet())
        {
            char node = (char) e.getKey();
            if(!visited.contains(node))
            {
                path.add(node);
                if(hasCycle(visited, path, seq, node)) return "";
                path.remove(node);
            }
        }

        Collections.reverse(seq);
        return seq.stream().map(Object::toString).collect(Collectors.joining(""));
    }

    boolean hasCycle(Set<Character> visited, Set<Character> path, List<Character> seq, char c)
    {
        visited.add(c);
        for(char next : links.get(c))
        {
            if(path.contains(next)) return true;
            if(visited.contains(next)) continue;
            path.add(next);
            if(links.containsKey(next) && hasCycle(visited, path, seq, next)) return true;
            path.remove(next);
        }
        seq.add(c);
        return false;
    }
}

class Solution {
    Map<Character, Set<Character>> links = new HashMap<>();
    public String alienOrder(String[] words) {
        int len = words.length;
        int j = 0;
        boolean cont = true;

        while(cont){
            String prefix0 = "";
            char ch0 = '.';
            cont = false;
            for(int i=0; i<len; ++i){
                String w = words[i];
                String prefix = words[i].substring(0, Math.min(w.length(), j)); 
                
                if(j>=w.length()){
                    if(prefix.equals(prefix0) && ch0!='.') return "";
                    prefix0 = prefix;
                    ch0 = '.';
                }else{
                    cont = true;
                    char ch = words[i].charAt(j);
                    if(!links.containsKey(ch)) links.put(ch, new HashSet<>());
                    if(prefix.equals(prefix0) && ch0!=ch && ch0!='.'){
                        links.get(ch0).add(ch);
                    }
                    prefix0 = prefix;
                    ch0 = ch;
                }
            }
            j++;
        }

        Set<Character> path = new HashSet<>();
        Set<Character> visited = new HashSet<>();
        List<Character> list = new ArrayList<>();

        for(char node : links.keySet()){
            if(visited.contains(node)) continue;
            path.add(node);
            if(hasCycle(path, visited, list, node)) return "";
            path.remove(node);
        }

        String ret = "";
        for(char c : list) ret += c;
        return ret;
    }

    boolean hasCycle(Set<Character> path, Set<Character> visited, List<Character> list, char node){
        visited.add(node);
        for(char nxt : links.get(node)){
            if(path.contains(nxt)) return true;
            if(visited.contains(nxt)) continue;
            path.add(nxt);
            if(hasCycle(path, visited, list, nxt)) return true;
            path.remove(nxt);
        }
        list.add(0, node);
        return false;
    }
}

LeetCode [268] Missing Number

Given an array containing n distinct numbers taken from 0, 1, 2, ..., n, find the one that is missing from the array.

Example 1:

Input: [3,0,1]
Output: 2

Example 2:

Input: [9,6,4,2,3,5,7,0,1]
Output: 8

Note:
Your algorithm should run in linear runtime complexity. Could you implement it using only constant extra space complexity?

class Solution {
public:
    int missingNumber(vector<int>& nums) {
        int ret = 0;
        for(auto n:nums) ret ^= n;
        for(int i=1; i<=nums.size(); ++i) ret ^= i;
        return ret;
    }
};

class Solution {
public:
    int missingNumber(vector<int>& nums) {
        int n = 0, m = INT_MIN;//n = xor of all existing numbers, m is the maximum
        for(auto i:nums){
            n ^= i;
            m = max(m, i);
        }
        if(m!=nums.size()) return nums.size();

        int m1 = m, w = 0;//w is #digits in m. eg., m=1010 w = 4
        while(m1){
            w++;
            m1 >>= 1;
        }

        int ret = 0;
        for(int i=w; i>0; --i){
            int t = pow(2,i-1), k = 0;
            //k=1 if the count of 1s on i-th digit of all numbers (including the missing number)
            if(i==1)
                k = ((m+1)/2%2);
            else if(m%(t*2)>=t)
                k = (m%t+1)%2;
            int p = (n&t)>>(i-1);//i-th digit of n
            ret |= ((k^p)*t);
        }
        return ret;
    }
};

class Solution {
public:
    int missingNumber(vector<int>& nums) {
        int miss = 0;
        for(int i=0; i<nums.size(); ++i){
            miss ^= ((i+1)^nums[i]);
        }
        return miss;
    }
};

class Solution {
public:
    int missingNumber(vector<int>& nums) {
        int n = nums.size();
        int sum_miss = accumulate(nums.begin(), nums.end(), 0);
        int sum_all = (1+n)*n/2;
        return sum_all - sum_miss;
    }
};

class Solution{
public:
    int getDupSum(vector<int> nums){
        int n = nums.size()-1;
        return accumulate(nums.begin(), nums.end(), 0)-(1+n)*n/2;
    }
    int getDupBit(vector<int> nums){
        int ret = 0, n = nums.size()-1;
        for(int i=0; i<n; ++i){
            ret ^= ((i+1)^(nums[i]));
        }
        return ret^nums[n];
    }
};

//Java
class Solution {
    public int missingNumber(int[] nums) {
        int s = 0;
        for(int v:nums) s+=v;
        int n = nums.length;
        return n*(n+1)/2-s;
    }
}