Code – 第156页

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;

}

};

LeetCode 18. 4Sum

Given an array S of n integers, are there elements a, b, c, and d in S such that a + b + c + d = target? Find all unique quadruplets in the array which gives the sum of target.

Note: The solution set must not contain duplicate quadruplets.

For example, given array S = [1, 0, -1, 0, -2, 2], and target = 0.

A solution set is:
[
[-1, 0, 0, 1],
[-2, -1, 1, 2],
[-2, 0, 0, 2]
]

题目大意：给一个整型数组，求abcd序列，使得a+b+c+d=target，返回所有不重复的abcd序列结果集合～

分析：对整型数组进行排序，先用i和j确定了前两个元素，然后用begin和end分别从j+1和最后一个元素n-1开始查找，根据sum的值移动begin和end指针，如果sum==target，就将结果放入结果集中；如果sum>target，将end向前移动一个，如果sum<target，就讲begin向后移动一个……为了避免重复，当i、j、begin、end和它们的前一个元素相同的时候，就跳过当前元素，直接移动到下一个～

class Solution {
public:
    vector<vector<int>> fourSum(vector<int>& nums, int target) {
       vector<vector<int>> result;
       int n = nums.size();
       if(n < 4) return result;
       sort(nums.begin(), nums.end());
       vector<int> temp(4);
       for(int i = 0; i < n - 3; i++) {
            if(i != 0 && nums[i] == nums[i-1]) continue;
           for(int j = i + 1; j < n - 2; j++) {
               if(j != i + 1 && nums[j] == nums[j-1]) continue;
               int begin = j + 1, end = n - 1;
               while(begin < end) {
                   int sum = nums[i] + nums[j] + nums[begin] + nums[end];
                   if(sum == target) {
                       temp[0] = nums[i];
                       temp[1] = nums[j];
                       temp[2] = nums[begin];
                       temp[3] = nums[end];
                       result.push_back(temp);
                       begin++;
                       end--;
                       while(begin < end && nums[begin] == nums[begin-1]) begin++;
                       while(begin < end && nums[end] == nums[end+1]) end--;
                   } else if(sum > target) {
                       end--;
                   } else {
                       begin++;
                   }
               }
           }
       }
       return result;
    }
};

class Solution {

public:

vector<vector<int>> fourSum(vector<int>& nums, int target) {

vector<vector<int>> result;

int n = nums.size();

if(n < 4) return result;

sort(nums.begin(), nums.end());

vector<int> temp(4);

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

if(i != 0 && nums[i] == nums[i-1]) continue;

for(int j = i + 1; j < n - 2; j++) {

if(j != i + 1 && nums[j] == nums[j-1]) continue;

int begin = j + 1, end = n - 1;

while(begin < end) {

int sum = nums[i] + nums[j] + nums[begin] + nums[end];

if(sum == target) {

temp[0] = nums[i];

temp[1] = nums[j];

temp[2] = nums[begin];

temp[3] = nums[end];

result.push_back(temp);

begin++;

end--;

while(begin < end && nums[begin] == nums[begin-1]) begin++;

while(begin < end && nums[end] == nums[end+1]) end--;

} else if(sum > target) {

end--;

} else {

begin++;

}

return result;

}

};

LeetCode 16. 3Sum Closest

Given an array S of n integers, find three integers in S such that the sum is closest to a given number, target. Return the sum of the three integers. You may assume that each input would have exactly one solution.

For example, given array S = {-1 2 1 -4}, and target = 1.

The sum that is closest to the target is 2. (-1 + 2 + 1 = 2).

题目大意：给定一个整型数组，在数组中找xyz，使x+y+z最接近target，返回最接近的x+y+z的值～

分析：对nums排序，先确定第一个数为nums[i], 使begin = i + 1，end = n – 1,如果当前sum == target，就令begin++，end–，指针分别向前向后移动一个，如果sum比较大，就令end往前一个；如果sum比较小，就令begin往后一个～每次根据sum更新result的值，result设置为long型，避免一开始是INT最大值、加了负数后溢出～

class Solution {
public:
    int threeSumClosest(vector<int>& nums, int target) {
        long result = INT_MAX;
        int n = nums.size();
        sort(nums.begin(), nums.end());
        for(int i = 0; i < n; i++) {
            int begin = i + 1, end = n - 1;
            while(begin < end) {
                int sum = nums[i] + nums[begin] + nums[end];
                if(sum == target) {
                    begin++;
                    end--;
                } else if(sum > target) {
                    end--;
                } else {
                    begin++;
                }
                if(abs(sum - target) < abs(result - target))
                    result = sum;
            }
        }
        return (int)result;
    }
};

class Solution {

public:

int threeSumClosest(vector<int>& nums, int target) {

long result = INT_MAX;

int n = nums.size();

sort(nums.begin(), nums.end());

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

int begin = i + 1, end = n - 1;

while(begin < end) {

int sum = nums[i] + nums[begin] + nums[end];

if(sum == target) {

begin++;

end--;

} else if(sum > target) {

end--;

} else {

begin++;

}

if(abs(sum - target) < abs(result - target))

result = sum;

}

return (int)result;

}

};

LeetCode 15. 3Sum

Given an array S of n integers, are there elements a, b, c in S such that a + b + c = 0? Find all unique triplets in the array which gives the sum of zero.

Note: The solution set must not contain duplicate triplets.

For example, given array S = [-1, 0, 1, 2, -1, -4],

A solution set is:
[
[-1, 0, 1],
[-1, -1, 2]
]

题目大意：给一个整数数组，从中选三个元素abc，使a + b + c = 0，返回所有满足条件的abc集合，结果集合中的结果不能有重复～

分析：将sum数组排序，先确定nums[i]为第一个元素，为了避免重复，如果nums[i]和刚刚的nums[i-1]相同就跳过continue，然后begin指向i+1，end指向n-1，判断此时的sum是否等于0，如果等于0就将结果放入result数组中，且begin++，end – -，为了避免重复，如果begin++后的元素依旧和刚才的元素相同，继续begin++，end同理～如果sum>0就将end – -，如果sum<0就将begin++，最后返回result结果集～～

class Solution {
public:
    vector<vector<int>> threeSum(vector<int>& nums) {
        vector<vector<int>> result;
        int n = nums.size();
        if(n < 3) return result;
        sort(nums.begin(), nums.end());
        vector<int> temp(3);
        for(int i = 0; i < n; i++) {
            if(nums[i] > 0) break;
            if(i > 0 && nums[i] == nums[i-1]) continue;
            int begin = i + 1, end = n - 1;
            while(begin < end) {
                int sum = nums[i] + nums[begin] + nums[end];
                if(sum == 0) {
                    temp[0] = nums[i]; 
                    temp[1] = nums[begin]; 
                    temp[2] = nums[end];
                    result.push_back(temp);
                    begin++; 
                    end--;
                    while(begin < end && nums[begin] == nums[begin - 1]) begin++;
                    while(begin < end && nums[end] == nums[end + 1]) end--;
                } else if(sum > 0) {
                    end--;
                } else {
                    begin++;
                }
            }
        }
        return result;
    }
};

class Solution {

public:

vector<vector<int>> threeSum(vector<int>& nums) {

vector<vector<int>> result;

int n = nums.size();

if(n < 3) return result;

sort(nums.begin(), nums.end());

vector<int> temp(3);

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

if(nums[i] > 0) break;

if(i > 0 && nums[i] == nums[i-1]) continue;

int begin = i + 1, end = n - 1;

while(begin < end) {

int sum = nums[i] + nums[begin] + nums[end];

if(sum == 0) {

temp[0] = nums[i];

temp[1] = nums[begin];

temp[2] = nums[end];

result.push_back(temp);

begin++;

end--;

while(begin < end && nums[begin] == nums[begin - 1]) begin++;

while(begin < end && nums[end] == nums[end + 1]) end--;

} else if(sum > 0) {

end--;

} else {

begin++;

}

return result;

}

};