liuchuo – 第156页 – 我不管，反正我最萌～

LeetCode 17. Letter Combinations of a Phone Number

Given a digit string, return all possible letter combinations that the number could represent.

A mapping of digit to letters (just like on the telephone buttons) is given below.

Input:Digit string “23”
Output: [“ad”, “ae”, “af”, “bd”, “be”, “bf”, “cd”, “ce”, “cf”].
Note:
Although the above answer is in lexicographical order, your answer could be in any order you want.

题目大意：给一个数字字符串，求可能出现的电话上的字母组合的所有情况～返回的次序可以不同～

分析：result为要返回的string数组，依次根据digits字符串的数字顺序从左到右遍历的顺序往里面添加字母，每一次都追加在原有result的后面，因为result会改变所以每次设立一个空string数组temp，然后temp根据result中原有的结果向后面继续添加拼接原+新的字符串，然后result = temp进行复制～如果digits不包含字符，应该返回空的result；否则因为要在原有result基础上拼接添加，所以先在result中push_back一个空串，以便后来的拼接字符串～

class Solution {
public:
    vector<string> letterCombinations(string digits) {
        vector<string> result;
        if(digits.length() == 0)
            return result;
        result.push_back("");
        vector<string> v = {"", "", "abc", "def", "ghi", "jkl", "mno", "pqrs", "tuv", "wxyz"};
        for(int i = 0; i < digits.size(); i++) {
            string s = v[digits[i] - '0'];
            vector<string> temp;
            for(int j = 0; j < s.length(); j++)
                for(int k = 0; k < result.size(); k++)
                    temp.push_back(result[k] + s[j]);
            result = temp;
        }
        return result;
    }
};

class Solution {

public:

vector<string> letterCombinations(string digits) {

vector<string> result;

if(digits.length() == 0)

return result;

result.push_back("");

vector<string> v = {"", "", "abc", "def", "ghi", "jkl", "mno", "pqrs", "tuv", "wxyz"};

for(int i = 0; i < digits.size(); i++) {

string s = v[digits[i] - '0'];

vector<string> temp;

for(int j = 0; j < s.length(); j++)

for(int k = 0; k < result.size(); k++)

temp.push_back(result[k] + s[j]);

result = temp;

}

return result;

}

};

LeetCode 179. Largest Number

Given a list of non negative integers, arrange them such that they form the largest number.

For example, given [3, 30, 34, 5, 9], the largest formed number is 9534330.

Note: The result may be very large, so you need to return a string instead of an integer.

题目大意：给一个非负整数数组，求怎样把他们连接起来构成的整数最大～

分析：先把他们转换成字符串数组arr，然后对arr进行排序，排序规则是return (a + b) > (b + a);即a+b拼接起来的字符串应该比b+a拼接起来的字符串大～然后将排序后的arr数组从头到尾连接起来～

class Solution {
public:
    string largestNumber(vector<int>& nums) {
        string result = "";
        vector<string> arr(nums.size());
        for(int i = 0; i < nums.size(); i++)
            arr[i] = to_string(nums[i]);
        auto cmp = [](string a, string b) {
            return (a + b) > (b + a);
        };
        sort(arr.begin(), arr.end(), cmp);
       for(int i = 0; i < arr.size(); i++)
            result += arr[i];
        return result[0] == '0' ? "0" : result;
    }
};

class Solution {

public:

string largestNumber(vector<int>& nums) {

string result = "";

vector<string> arr(nums.size());

for(int i = 0; i < nums.size(); i++)

arr[i] = to_string(nums[i]);

auto cmp = [](string a, string b) {

return (a + b) > (b + a);

};

sort(arr.begin(), arr.end(), cmp);

for(int i = 0; i < arr.size(); i++)

result += arr[i];

return result[0] == '0' ? "0" : result;

}

};

LeetCode 318. Maximum Product of Word Lengths

Given a string array words, find the maximum value of length(word[i]) * length(word[j]) where the two words do not share common letters. You may assume that each word will contain only lower case letters. If no such two words exist, return 0.

Example 1:
Given [“abcw”, “baz”, “foo”, “bar”, “xtfn”, “abcdef”]
Return 16
The two words can be “abcw”, “xtfn”.

Example 2:
Given [“a”, “ab”, “abc”, “d”, “cd”, “bcd”, “abcd”]
Return 4
The two words can be “ab”, “cd”.

Example 3:
Given [“a”, “aa”, “aaa”, “aaaa”]
Return 0
No such pair of words.

题目大意：给一个string数组，每一个string都是一个单词，只包含小写字母，求问没有相同字母的两个单词的长度乘积最大值是多少～如果不存在这样的两个单词，返回0～

分析：其实只需要知道每个单词包含哪些字母就可以了～反正一共只有26个字母，而整型长度是32位，这样就可以用一个int的32位来体现一个字母有哪些字母～比如说一个单词包含字母b，那么b – a = 1，就把从右往左的第1位置为1～等到把一个单词的所有字母相应位都置为1后，这个整型的值与另一个单词的整型值做“&”运算就可以得知他俩有没有相同的字符了～因为如果做“&”运算后的结果是0，表示没有二进制中的一位同时是1，表示这两个单词是没有相同字符的～这样就能很快判断出最大的长度乘积了～

class Solution {
public:
    int maxProduct(vector<string>& words) {
        vector<int> v(words.size());
        int result = 0;
        for(int i = 0; i < words.size(); i++)
            for(int j = 0; j < words[i].length(); j++)
                v[i] = v[i] | 1 << (words[i][j] - 'a');
        for(int i = 0; i < words.size(); i++)
            for(int j = i + 1; j < words.size(); j++)
                if((v[i] & v[j]) == 0)
                    result = max(result, (int)(words[i].length() * words[j].length()));
        return result;
    }
};

class Solution {

public:

int maxProduct(vector<string>& words) {

vector<int> v(words.size());

int result = 0;

for(int i = 0; i < words.size(); i++)

for(int j = 0; j < words[i].length(); j++)

v[i] = v[i] | 1 << (words[i][j] - 'a');

for(int i = 0; i < words.size(); i++)

for(int j = i + 1; j < words.size(); j++)

if((v[i] & v[j]) == 0)

result = max(result, (int)(words[i].length() * words[j].length()));

return result;

}

};

LeetCode 482. License Key Formatting

Now you are given a string S, which represents a software license key which we would like to format. The string S is composed of alphanumerical characters and dashes. The dashes split the alphanumerical characters within the string into groups. (i.e. if there are M dashes, the string is split into M+1 groups). The dashes in the given string are possibly misplaced.

We want each group of characters to be of length K (except for possibly the first group, which could be shorter, but still must contain at least one character). To satisfy this requirement, we will reinsert dashes. Additionally, all the lower case letters in the string must be converted to upper case.

So, you are given a non-empty string S, representing a license key to format, and an integer K. And you need to return the license key formatted according to the description above.

Example 1:
Input: S = “2-4A0r7-4k”, K = 4

Output: “24A0-R74K”

Explanation: The string S has been split into two parts, each part has 4 characters.
Example 2:
Input: S = “2-4A0r7-4k”, K = 3

Output: “24-A0R-74K”

Explanation: The string S has been split into three parts, each part has 3 characters except the first part as it could be shorter as said above.
Note:
The length of string S will not exceed 12,000, and K is a positive integer.
String S consists only of alphanumerical characters (a-z and/or A-Z and/or 0-9) and dashes(-).
String S is non-empty.

题目大意：将序列号重置格式，首先去掉原先有的“-”，然后所有字母必须大写，而且要重新将每K位加一个“-”，如果序列号不能被K整除，则字符串开头允许小于K位～

分析：
1.将“-”去除，且用toupper将所有字符变成大些形式，存储在新的字符串temp里面；
2.先处理首部，如果len % K不等于0，就先将前面len%K个字母放入result字符串中；
3.每K位增加一个“-”，注意：如果一开始index == 0，即len能够被K整除，前面没有多余的，则不需要增加那个多余的第一个“-”～～

class Solution {
public:
    string licenseKeyFormatting(string S, int K) {
        string result = "", temp = "";
        for(int i = 0; i < S.length(); i++) {
            if(S[i] != '-')
                temp += toupper(S[i]);
        }
        int len = temp.length(), index = 0;
        while(index < len % K)
            result += temp[index++];
        for(int i = 0; i < len - len % K; i++) {
            if(i % K == 0 && index != 0)
                result += '-';
            result += temp[index++];
        }
        return result;
    }
};

class Solution {

public:

string licenseKeyFormatting(string S, int K) {

string result = "", temp = "";

for(int i = 0; i < S.length(); i++) {

if(S[i] != '-')

temp += toupper(S[i]);

}

int len = temp.length(), index = 0;

while(index < len % K)

result += temp[index++];

for(int i = 0; i < len - len % K; i++) {

if(i % K == 0 && index != 0)

result += '-';

result += temp[index++];

}

return result;

}

};

LeetCode 12. Integer to Roman

Given an integer, convert it to a roman numeral.

Input is guaranteed to be within the range from 1 to 3999.

题目大意：将一个整数转化为罗马数字表示法～

分析：根据罗马数字的表示方法，我们直到罗马字符有”M”, “CM”, “D”, “CD”, “C”, “XC”, “L”, “XL”, “X”, “IX”, “V”, “IV”, “I”这几种，分别对应1000, 900, 500, 400, 100, 90, 50, 40, 10, 9, 5, 4, 1。如果在这些数字之间的，比如3，那就重复3次写1：III。所以只需要按照罗马数字表示的从大到小顺序，当num比a[i]大的时候，cnt = num / a[i],就将b[i]连接在result字符串后面cnt次。每一次循环将num取余a[i]，直到num<=0为止～

class Solution {
public:
    string intToRoman(int num) {
        string result = "";
        int a[] = {1000, 900, 500, 400, 100, 90, 50, 40, 10, 9, 5, 4, 1};
        string b[] = {"M", "CM", "D", "CD", "C", "XC", "L", "XL", "X", "IX", "V", "IV", "I"};
        int index = 0, cnt;
        while(num > 0) {
            cnt = num / a[index];
            while(cnt--)
                result += b[index];
            num = num % a[index];
            index++;
        }
        return result;
    }
};

class Solution {

public:

string intToRoman(int num) {

string result = "";

int a[] = {1000, 900, 500, 400, 100, 90, 50, 40, 10, 9, 5, 4, 1};

string b[] = {"M", "CM", "D", "CD", "C", "XC", "L", "XL", "X", "IX", "V", "IV", "I"};

int index = 0, cnt;

while(num > 0) {

cnt = num / a[index];

while(cnt--)

result += b[index];

num = num % a[index];

index++;

}

return result;

}

};

LeetCode 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:
Input contains only lowercase English letters.
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.
Input length is less than 50,000.
Example 1:
Input: “owoztneoer”
Output: “012”

Example 2:
Input: “fviefuro”
Output: “45”

题目大意：给一个非空字符串，是一些数字的单词打乱后的顺序，求还原这些数字是哪些以及多少个，按照数字增序排列～

分析：先把0～9这10个数字的字母写出来，就可以知道z、x、w、g、u可以唯一确定0、6、2、8、4的个数，然后按照06284的拼写在别的字母中减去他们的拼写，接下来可以发现按照s、r、o、f、e这样的顺序分别筛出7、3、1、5、9的个数即可～（还有更简洁的代码写法，这样写是为了清晰思路）

class Solution {
public:
    string originalDigits(string s) {
        map<char, int> m;
        int cnt[10] = {0}, temp;
        for(int i = 0; i < s.length(); i++)
            m[s[i]]++;
        temp = m['z'];
        cnt[0] = temp;
        m['z'] -= temp;
        m['e'] -= temp;
        m['r'] -= temp;
        m['o'] -= temp;
        temp = m['x'];
        cnt[6] = temp;
        m['s'] -= temp;
        m['i'] -= temp;
        m['x'] -= temp;
        temp = m['w'];
        cnt[2] = temp;
        m['t'] -= temp;
        m['w'] -= temp;
        m['o'] -= temp;
        temp = m['g'];
        cnt[8] = temp;
        m['e'] -= temp;
        m['i'] -= temp;
        m['g'] -= temp;
        m['h'] -= temp;
        m['t'] -= temp;
        temp = m['u'];
        cnt[4] = temp;
        m['f'] -= temp;
        m['o'] -= temp;
        m['u'] -= temp;
        m['r'] -= temp;
        temp = m['s'];
        cnt[7] = temp;
        m['s'] -= temp;
        m['e'] -= temp;
        m['v'] -= temp;
        m['e'] -= temp;
        m['n'] -= temp;
        temp = m['r'];
        cnt[3] = temp;
        m['t'] -= temp;
        m['h'] -= temp;
        m['r'] -= temp;
        m['e'] -= temp;
        m['e'] -= temp;
        temp = m['o'];
        cnt[1] = temp;
        m['o'] -= temp;
        m['n'] -= temp;
        m['e'] -= temp;
        temp = m['f'];
        cnt[5] = temp;
        m['f'] -= temp;
        m['i'] -= temp;
        m['v'] -= temp;
        m['e'] -= temp;
        temp = m['e'];
        cnt[9] = temp;
        m['n'] -= temp;
        m['i'] -= temp;
        m['n'] -= temp;
        m['e'] -= temp;
        string result = "";
        for(int i = 0; i <= 9; i++)
            for(int j = 0; j < cnt[i]; j++)
                result += to_string(i);
        return result;
    }
};

class Solution {

public:

string originalDigits(string s) {

map<char, int> m;

int cnt[10] = {0}, temp;

for(int i = 0; i < s.length(); i++)

m[s[i]]++;

temp = m['z'];

cnt[0] = temp;

m['z'] -= temp;

m['e'] -= temp;

m['r'] -= temp;

m['o'] -= temp;

temp = m['x'];

cnt[6] = temp;

m['s'] -= temp;

m['i'] -= temp;

m['x'] -= temp;

temp = m['w'];

cnt[2] = temp;

m['t'] -= temp;

m['w'] -= temp;

m['o'] -= temp;

temp = m['g'];

cnt[8] = temp;

m['e'] -= temp;

m['i'] -= temp;

m['g'] -= temp;

m['h'] -= temp;

m['t'] -= temp;

temp = m['u'];

cnt[4] = temp;

m['f'] -= temp;

m['o'] -= temp;

m['u'] -= temp;

m['r'] -= temp;

temp = m['s'];

cnt[7] = temp;

m['s'] -= temp;

m['e'] -= temp;

m['v'] -= temp;

m['e'] -= temp;

m['n'] -= temp;

temp = m['r'];

cnt[3] = temp;

m['t'] -= temp;

m['h'] -= temp;

m['r'] -= temp;

m['e'] -= temp;

temp = m['o'];

cnt[1] = temp;

m['o'] -= temp;

m['n'] -= temp;

m['e'] -= temp;

temp = m['f'];

cnt[5] = temp;

m['f'] -= temp;

m['i'] -= temp;

m['v'] -= temp;

m['e'] -= temp;

temp = m['e'];

cnt[9] = temp;

m['n'] -= temp;

m['i'] -= temp;

m['n'] -= temp;

m['e'] -= temp;

string result = "";

for(int i = 0; i <= 9; i++)

for(int j = 0; j < cnt[i]; j++)

result += to_string(i);

return result;

}

};