Code – 第155页

LeetCode 166. Fraction to Recurring Decimal

Given two integers representing the numerator and denominator of a fraction, return the fraction in string format.

If the fractional part is repeating, enclose the repeating part in parentheses.

For example,

Given numerator = 1, denominator = 2, return “0.5”.
Given numerator = 2, denominator = 1, return “2”.
Given numerator = 2, denominator = 3, return “0.(6)”.
Hint:

No scary math, just apply elementary math knowledge. Still remember how to perform a long division?
Try a long division on 4/9, the repeating part is obvious. Now try 4/333. Do you see a pattern?
Be wary of edge cases! List out as many test cases as you can think of and test your code thoroughly.

题目大意：给定两个整型数分子和分母，以小数的形式返回它们的结果，当有循环小数时，将循环的部分用括号括起来～

分析：先忽略符号，为了防止溢出，转换为long型的a和b，以绝对值形式求a/b的结果：a/b的结果是结果的整数部分，如果余数r = a % b不等于0，说明还有小数部分～
用map标记余数r应该在string result的哪个位置，如果map[r]不为0说明出现过，那么就在m[r]（出现的位置）的前面添加一个(，在result结尾添加一个)，表示这部分会循环～

注意点：1.如果除数等于0，直接返回0，为了避免出现返回-0的情况～2.如果(numerator < 0) ^ (denominator < 0)等于1，说明他们一正一负，结果是负数，所以要在result的第一位添加一个“-”。3.如果一开始的r不等于0，说明有小数部分，则在计算小数部分之前添加一个”.”

class Solution {
public:
    string fractionToDecimal(int numerator, int denominator) {
        if(numerator == 0) return "0";
        string result = "";
        if(((numerator < 0) ^ (denominator < 0)) == 1)
            result += '-';
        long a = abs((long)numerator), b = abs((long)denominator);
        result += to_string(a / b);
        long r = a % b;
        if(r != 0) result += '.';
        map<int, int> m;
        while(r != 0) {
            if(m[r] != 0) {
                result.insert(m[r], 1, '(');
                result += ')';
                break;
            }
            m[r] = result.size();
            r = r * 10;
            result += to_string(r / b);
            r = r % b;
        }
        return result;
        
    }
};

class Solution {

public:

string fractionToDecimal(int numerator, int denominator) {

if(numerator == 0) return "0";

string result = "";

if(((numerator < 0) ^ (denominator < 0)) == 1)

result += '-';

long a = abs((long)numerator), b = abs((long)denominator);

result += to_string(a / b);

long r = a % b;

if(r != 0) result += '.';

map<int, int> m;

while(r != 0) {

if(m[r] != 0) {

result.insert(m[r], 1, '(');

result += ')';

break;

}

m[r] = result.size();

r = r * 10;

result += to_string(r / b);

r = r % b;

}

return result;

}

};

LeetCode 29. Divide Two Integers

Divide two integers without using multiplication, division and mod operator.

If it is overflow, return MAX_INT.

题目大意：不用乘法、除法、取余操作，将两个数相除，如果它溢出了，返回MAX_INT～

分析：我用了减法和log函数。。就是e的(loga-logb)次方等于e的log(a/b) = a/b。。。。这应该不算投机取巧吧？。。。～

class Solution {
public:
    int divide(int dividend, int divisor) {
        if(divisor == 0 || dividend == INT_MIN && divisor == -1) return INT_MAX;
        int sign = ((dividend >> 31) ^ (divisor >> 31)) == 0 ? 1 : -1;
        long a = abs((long)dividend);
        long b = abs((long)divisor);
        double c = exp(log(a) - log(b)) + 0.0000000001;
        return (int)(sign * c);
    }
};

class Solution {

public:

int divide(int dividend, int divisor) {

if(divisor == 0 || dividend == INT_MIN && divisor == -1) return INT_MAX;

int sign = ((dividend >> 31) ^ (divisor >> 31)) == 0 ? 1 : -1;

long a = abs((long)dividend);

long b = abs((long)divisor);

double c = exp(log(a) - log(b)) + 0.0000000001;

return (int)(sign * c);

}

};

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;

}

};