Day 128, #256 #265 #267 #273 Paint House, Paint House II, Palindrome Permutation II, Integer to English Words

Paint House

There are a row of n houses, each house can be painted with one of the three colors: red, blue or green. The cost of painting each house with a certain color is different. You have to paint all the houses such that no two adjacent houses have the same color.

The cost of painting each house with a certain color is represented by a n x 3 cost matrix. For example, costs[0][0] is the cost of painting house 0 with color red;costs[1][2] is the cost of painting house 1 with color green, and so on... Find the minimum cost to paint all houses.

Note:
All costs are positive integers.

-----------------------------------------
方程式：
递归：超时，可加memoization

class Solution {
public:
    int helper(vector<vector<int>>& costs, int index,int pre) {
        if (index == costs.size()) return 0;
        int min1 = INT_MAX,min2 = INT_MAX,min3 = INT_MAX;
        if (pre != 0) {
            min1 = costs[index][0] + helper(costs,index + 1,0);
        }
        if (pre != 1) {
            min2 = costs[index][1] + helper(costs,index + 1,1);
        }
        if (pre != 2) {
            min3 = costs[index][2] + helper(costs,index + 1,2);
        }
        
        return min(min(min2,min1),min3);
    }

    int minCost(vector<vector<int>>& costs) {
        return helper(costs,0,-1);
    }
};

DP:
3个array，dp[k][i] = 为在第i个房子涂k的颜色所需要的总花费
dp[0][i] = costs[i][0] + min(dp[1][i - 1],dp[2][i - 1]);
其他2个颜色类同

以下方法已经做过空间优化

class Solution {
public:
    int minCost(vector<vector<int>>& costs) {
        int n = costs.size();
        if (n == 0) return 0;
        int dp0 = costs[0][0];
        int dp1 = costs[0][1];
        int dp2 = costs[0][2];
        
        for (int i = 1; i < n; i++) {
            int t0 = dp0, t1 = dp1, t2 = dp2;
            dp0 = costs[i][0] + min(t1,t2);
            dp1 = costs[i][1] + min(t2,t0);
            dp2 = costs[i][2] + min(t1,t0);
        }

        return min(min(dp0,dp1),dp2);
    }
};

Paint House II

There are a row of n houses, each house can be painted with one of the k colors. The cost of painting each house with a certain color is different. You have to paint all the houses such that no two adjacent houses have the same color.

The cost of painting each house with a certain color is represented by a n x k cost matrix. For example, costs[0][0] is the cost of painting house 0 with color 0; costs[1][2] is the cost of painting house 1 with color 2, and so on... Find the minimum cost to paint all houses.

Note:
All costs are positive integers.

Follow up:
Could you solve it in O(nk) runtime?

------------------------------------------
2个variable保存上一次涂房子的最小的2个值，first是值，second是颜色

class Solution {
public:
    int minCostII(vector>& costs) {
        int n = costs.size();
        if (n == 0) return 0;
        int k = costs[0].size();
        vector dp = costs[0];
        int minCost = INT_MAX;
        
        for (int i = 1; i < n; i++) {
            // pair of cost - color
            pair min1 = make_pair(INT_MAX,-1);
            pair min2 = make_pair(INT_MAX,-1);
            // find the smallest two values from previous painting job
            for (int j = 0; j < k; j++) {
                if (dp[j] < min1.first) {
                    min2 = min1;
                    min1.first = dp[j];
                    min1.second = j;
                }else if (dp[j] < min2.first) {
                    min2.first = dp[j];
                    min2.second = j;
                }
            }
            
            for (int j = 0; j < k; j++) {
                if (j == min1.second) {
                    dp[j] = costs[i][j] + min2.first;
                }else {
                    dp[j] = costs[i][j] + min1.first;
                }
            }
        }
    
        for (int i = 0; i < k; i++) {
            minCost = min(minCost,dp[i]);
        }
        
        return minCost;
    }
};

Palindrome Permutation II
 Given a string s, return all the palindromic permutations (without duplicates) of it. Return an empty list if no palindromic permutation could be form.
For example:
Given s = "aabb", return ["abba", "baab"].
Given s = "abc", return [].
Hint:

1. If a palindromic permutation exists, we just need to generate the first half of the string.
2. To generate all distinct permutations of a (half of) string, use a similar approach from: Permutations II or Next Permutation.

------------------------------
#1 检测所给string是否可生成pal, 跟I一样
#2 典型permutation

class Solution {
public:
    vector<int> collect(string s,string &single) {
        vector<int> count(256,0);
        for (int i = 0; i < s.length(); i++) {
            count[s[i]]++;
        }
        
        for (int i = 0; i < 256; i++) {
            if (count[i] % 2 == 1) {
                if (single == "") {
                    single += i;
                }else {
                    vector<int> t;
                    return t;
                }
            }
        }
        
        return count;
    }

    void rec(vector<string> &rt,vector<int> &count,string s,int total,string single) {
        if (total == 0) {
            string t = s;
            reverse(t.begin(),t.end());
            rt.push_back(s + single + t);
            return;
        }
        
        for (int i = 0; i < 256; i++) {
            if (count[i] < 2) continue;
            string t = s;
            t += i;
            count[i] -= 2;
            rec(rt,count,t,total - 1,single);
            count[i] += 2;
        }
    }

    vector<string> generatePalindromes(string s) {
        vector<string> rt;
        string single = "";
        vector<int> count = collect(s,single);
        if (count.size() == 0) return rt;
        rec(rt,count,"",s.length() / 2,single);
        return rt;
    }
};

Java

class Solution {
    public List<String> generatePalindromes(String s) {
        List<String> rt = new ArrayList<>();
        int[] map = new int[128];
        int odd = 0;
        
        for (int i = 0; i < s.length(); i++) {
            map[s.charAt(i)] += 1;
            if (map[s.charAt(i)] % 2 == 1) odd++;
            else odd--;
        }
        
        if (odd > 1) return rt;
        
        String mid = "";
        for (int i = 0; i < 128; i++) {
            if (map[i] % 2 == 1) mid += (char)i;
        }

        perm(rt, "", s.length() / 2, mid, map);
        
        return rt;
    }
    
    private void perm(List<String> rt, String curS, int total, String mid, int[] map) {
        if (total == 0) {
            rt.add(curS + mid + new StringBuilder(curS).reverse().toString());
            return;
        }
        
        for (int i = 0; i < 128; i++) {
            if (map[i] < 2) continue;
            map[i] -= 2;
            perm(rt, curS + (char)i, total - 1, mid, map);
            map[i] += 2;
        }
    }
}

Integer to English Words

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

For example,

123 -> "One Hundred Twenty Three"
12345 -> "Twelve Thousand Three Hundred Forty Five"
1234567 -> "One Million Two Hundred Thirty Four Thousand Five Hundred Sixty Seven"

Hint:

1. Did you see a pattern in dividing the number into chunk of words? For example, 123 and 123000.
2. Group the number by thousands (3 digits). You can write a helper function that takes a number less than 1000 and convert just that chunk to words.
3. There are many edge cases. What are some good test cases? Does your code work with input such as 0? Or 1000010? (middle chunk is zero and should not be printed out)

----------------------------------------------------------------
注意空格

class Solution {
public:
    string translate(vector<string> &ones,vector<string> &oneTens,vector<string> &tens,vector<string> &ends,int nums,string end) {
        string rt = "";
        if (nums >= 100) {
            rt += ones[nums / 100 - 1] + " Hundred";
            nums %= 100;
        }
        
        if (nums >= 10) {
            if (rt != "") rt += " ";
            if (nums <= 19) {
                rt += oneTens[nums % 10];
                return rt + end;
            }
            rt += tens[nums / 10 - 2];
            nums %= 10;
        }
        
        if (nums >= 1) {
            if (rt != "") rt += " ";
            rt += ones[nums - 1];
        }
        
        return rt + end;
    }


    string numberToWords(int num) {
        if (num == 0) return "Zero";
        vector<string> ones = {"One","Two","Three","Four","Five","Six","Seven","Eight","Nine"};
        vector<string> oneTens = {"Ten","Eleven","Twelve","Thirteen","Fourteen","Fifteen","Sixteen","Seventeen","Eighteen","Nineteen"};
        vector<string> tens = {"Twenty","Thirty","Forty","Fifty","Sixty","Seventy","Eighty","Ninety"};
        vector<string> ends = {" Billion"," Million"," Thousand",""};
        
        string rt = "";
        int temp = 0, endI = 0,bill = 1000000000;
        while (num > 0) {
            if (num / bill > 0) {
                if (rt != "") rt += " ";
                rt += translate(ones,oneTens,tens,ends,num / bill,ends[endI]);
            }
            num %= bill;
            bill /= 1000;
            endI++;
        }
        return rt;
    }
};

In Java
注意空格

class Solution {
    private String[] units = {""," Thousand"," Million"," Billion"};
    private String[] singleDigits = {"One","Two","Three","Four","Five","Six","Seven","Eight","Nine"};
    private String[] doubleDigitsTenth = {"Ten","Eleven","Twelve","Thirteen","Fourteen","Fifteen","Sixteen","Seventeen","Eighteen","Nineteen"};
    private String[] doubleDigits = {"Twenty","Thirty","Forty","Fifty","Sixty","Seventy","Eighty","Ninety"};
    
    public String numberToWords(int num) {
        if (num == 0) return "Zero";
        String rt = "";
        for (int i = 0; i < 4; i++) {
            String cur = toWords((num % 1000), units[i]);
            if (!rt.isEmpty() && !cur.isEmpty()) rt = " " + rt;
            rt = cur + rt;
            num /= 1000; 
        }
        
        return rt;
    }
    
    private String toWords(int num, String unit) {
        String s = "";
        if (num == 0) return s;
        
        if (num >= 100) {
            s += singleDigits[num / 100 - 1] + " Hundred";
            num %= 100;
        }
        if (num > 9 && num < 20) {
            if (!s.isEmpty()) s += " ";
            s += doubleDigitsTenth[num % 10];
        } else {
            if (num > 19) {
                if (!s.isEmpty()) s += " ";
                s += doubleDigits[num / 10 - 2];
                num %= 10;
            }
            if (num != 0) {
                if (!s.isEmpty()) s += " ";
                s += singleDigits[num - 1];
            }
        }
        
        return s + unit;
    }
}