LeetCode OJ – 第21页

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;

}

};

LeetCode 454. 4Sum II

Given four lists A, B, C, D of integer values, compute how many tuples (i, j, k, l) there are such that A[i] + B[j] + C[k] + D[l] is zero.

To make problem a bit easier, all A, B, C, D have same length of N where 0 ≤ N ≤ 500. All integers are in the range of -228 to 228 – 1 and the result is guaranteed to be at most 231 – 1.

Example:

Input:
A = [ 1, 2]
B = [-2,-1]
C = [-1, 2]
D = [ 0, 2]

Output:
2

Explanation:
The two tuples are:
1. (0, 0, 0, 1) -> A[0] + B[0] + C[0] + D[1] = 1 + (-2) + (-1) + 2 = 0
2. (1, 1, 0, 0) -> A[1] + B[1] + C[0] + D[0] = 2 + (-1) + (-1) + 0 = 0

题目大意：给四个长度相等的整型数组A、B、C、D，寻找i，j，k，l使得A[i] + B[j] + C[k] + D[l] = 0，求问有多少个这样的i，j，k，l组合～

分析：设立两个map，m1和m2，m1中存储A、B数组中的元素两两组合的和以及出现的次数，如m1[i] = j表示A、B两数组中各取一个元素相加的和为i的个数有j个～这样我们就能把A+B+C+D = 0的问题转化成A+B的和为sum，求C+D中有没有-sum可以满足相加等于0～如果m1[sum]的个数是cnt1，m2[0-sum]的个数是cnt2，那么就能构成cnt1*cnt2个组合～将所有满足条件的结果累加即可得到result的值～

class Solution {
public:
    int fourSumCount(vector<int>& A, vector<int>& B, vector<int>& C, vector<int>& D) {
        map<int, int> m1, m2;
        int result = 0, n = A.size();
        for(int i = 0; i < n; i++) {
            for(int j = 0; j < n; j++) {
                int t1 = A[i] + B[j];
                int t2 = C[i] + D[j];
                m1[t1]++;
                m2[t2]++;
            }
        }
        for(auto it = m1.begin(); it != m1.end(); it++)
            result += it->second * m2[0 - it->first];
        return result;
    }
};

class Solution {

public:

int fourSumCount(vector<int>& A, vector<int>& B, vector<int>& C, vector<int>& D) {

map<int, int> m1, m2;

int result = 0, n = A.size();

for(int i = 0; i < n; i++) {

for(int j = 0; j < n; j++) {

int t1 = A[i] + B[j];

int t2 = C[i] + D[j];

m1[t1]++;

m2[t2]++;

}

for(auto it = m1.begin(); it != m1.end(); it++)

result += it->second * m2[0 - it->first];

return result;

}

};