LeetCode 412. Fizz Buzz

Oct 29, 2016

题目描述:

Write a program that outputs the string representation of numbers from 1 to n.

But for multiples of three it should output “Fizz” instead of the number and for the multiples of five output “Buzz”. For numbers which are multiples of both three and five output “FizzBuzz”.

Example:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
n = 15,

Return:
[
    "1",
    "2",
    "Fizz",
    "4",
    "Buzz",
    "Fizz",
    "7",
    "8",
    "Fizz",
    "Buzz",
    "11",
    "Fizz",
    "13",
    "14",
    "FizzBuzz"
]

直接判断数字是不是3或5的倍数就可以了.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
class Solution {
public:
    vector<string> fizzBuzz(int n) {
        vector<string> ans;
        for(int i = 1; i <= n; i++){
            string s;
            if(i % 3 && i % 5){
                s = to_string(i);
            }
            else {
                if(i % 3 == 0){
                    s += "Fizz";
                }
                if(i % 5 == 0){
                    s += "Buzz";
                }
            }
            ans.push_back(s);
        }
        return ans;
    }
};

LeetCode 172. Factorial Trailing Zeroes

Oct 20, 2016

题目描述:

Given an integer n, return the number of trailing zeroes in n!.

**Note: **Your solution should be in logarithmic time complexity.

统计结果中因子5的个数.

1
2
3
4
5
6
7
8
9
10
11
class Solution {
public:
    int trailingZeroes(int n) {
        int ret = 0;
        while(n > 0){
            ret += n / 5; // 实际是计算比n小的最大的5的整数倍
            n /= 5; // 实际是计算比n小的最大的5的整数倍除以5
        }
        return ret;
    }
};

LeetCode 171. Excel Sheet Column Number

Oct 20, 2016

题目描述:

Related to question Excel Sheet Column Title

Given a column title as appear in an Excel sheet, return its corresponding column number.

For example:

1
2
3
4
5
6
7
A -> 1
B -> 2
C -> 3
...
Z -> 26
AA -> 27
AB -> 28

二十六进制的转换.

1
2
3
4
5
6
7
8
9
10
11
class Solution {
public:
    int titleToNumber(string s) {
        int ans = 0;
        for(int i = 0; i < s.length(); i++){
            ans *= 26;
            ans += s[i] - 'A' + 1;
        }
        return ans;
    }
};

LeetCode 169. Majority Element

Oct 17, 2016

题目描述:

Given an array of size n, find the majority element. The majority element is the element that appears more than ⌊ n/2 ⌋ times.

You may assume that the array is non-empty and the majority element always exist in the array.

这道题方法很多, 排序, 哈希表, 位运算等等都可以.

排序:

1
2
3
4
5
6
7
class Solution {
public:
    int majorityElement(vector<int> &nums) {
        sort(nums.begin(), nums.end());
        return nums[nums.size() / 2];
    }
};

位运算:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
class Solution {
public:
    int majorityElement(vector<int>& nums) {
        int n = nums.size();
        vector<int> bits(32);
        for(auto j : nums){
            for(int i = 0; i < 32; i++){
                if(j & (1 << i)) bits[i]++;
            }
        }
        int ans = 0;
        for(int i = 0; i < 32; i++){
            if(bits[i] > n / 2){
                ans |= (1 << i);
            }
        }
        return ans;
    }
};

哈希表:

1
2
3
4
5
6
7
8
9
10
11
12
class Solution {
public:
    int majorityElement(vector<int>& nums) {
        int n = nums.size() / 2;
        unordered_map<int, int> m;
        for(auto i : nums){
            if(++m[i] > n) return i;
        }
        
        return 0;
    }
};

还有一种O(n)的算法

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
class Solution {
public:
    int majorityElement(vector<int>& nums) {
        int n, cnt = 0;
        for(auto i : nums){
            if(cnt == 0){
                cnt++;
                n = i;
            }
            else if(n == i){
                cnt++;
            }
            else{
                cnt--;
            }
            
            if(cnt > nums.size() / 2) break;
        }
        return n;
    }
};

LeetCode 168. Excel Sheet Column Title

Oct 17, 2016

题目描述:

Given a positive integer, return its corresponding column title as appear in an Excel sheet.

For example:

1
2
3
4
5
6
7
1 -> A
2 -> B
3 -> C
...
26 -> Z
27 -> AA
28 -> AB

按照26进制来处理, 不过由于是从1而不是0开始的, 所以要对Z单独处理.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
class Solution {
public:
    string convertToTitle(int n) {
        string ret;
        while(n > 0){
            if(n % 26 == 0) {
                ret.push_back('Z');
                n = n / 26 - 1;
            }
            else {
                ret.push_back((n % 26) + 'A' - 1);
                n /= 26;
            }
        }
        reverse(ret.begin(), ret.end());
        return ret;
    }
};

LeetCode 167. Two Sum II - Input array is sorted

Oct 17, 2016

题目描述:

Given an array of integers that is already sorted in ascending order, find two numbers such that they add up to a specific target number.

The function twoSum should return indices of the two numbers such that they add up to the target, where index1 must be less than index2. Please note that your returned answers (both index1 and index2) are not zero-based.

You may assume that each input would have exactly one solution.

Input: numbers={2, 7, 11, 15}, target=9 Output: index1=1, index2=2

输入数据是有序的反而更简单了, 两个指针从两端开始向中间移动就可以了.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
class Solution {
public:
    vector<int> twoSum(vector<int>& numbers, int target) {
        int l = 0, r = numbers.size() - 1;
        vector<int> ans(2);
        while(true){
            if(numbers[l] + numbers[r] > target){
                r--;
            }
            else if(numbers[l] + numbers[r] < target){
                l++;
            }
            else{
                ans[0] = l + 1;
                ans[1] = r + 1;
                break;
            }
        }
        return ans;
    }
};

LeetCode 424. Longest Repeating Character Replacement

Oct 16, 2016

题目描述:

Given a string that consists of only uppercase English letters, you can replace any letter in the string with another letter at most k times. Find the length of a longest substring containing all repeating letters you can get after performing the above operations.

Note: Both the string’s length and k will not exceed 104.

Example 1:

1
2
3
4
5
6
7
8
9
Input:
s = "ABAB", k = 2

Output:
4

Explanation:
Replace the two 'A's with two 'B's or vice versa.

Example 2:

1
2
3
4
5
6
7
8
9
Input:
s = "AABABBA", k = 1

Output:
4

Explanation:
Replace the one 'A' in the middle with 'B' and form "AABBBBA".
The substring "BBBB" has the longest repeating letters, which is 4.

这道题我采用双指针的方法. p指向最长连续重复字符的结尾, q指向开头. 首先看一个例子: 字符串"ABBBAAABBAAB", k=2, 先查找A. 用r记录已经替换了多少个字母.

1
2
ABBBAAABBAAB
p=0, q=0, r=0

一开始p和q都指向开头, 第一个字符为A, 因此不用替换, 此时长度为1.

1
2
ABBBAAABBAAB
p=1, q=0, r=1

第二个字符需要替换, r变为1, 此时长度为2.

1
2
ABBBAAABBAAB
p=2, q=0, r=2

第三个字符也要替换, r变为2, 长度为3.

1
2
ABBBAAABBAAB
p=3, q=2, r=2

第四个字符仍然需要替换, 但是所有的替换次数已经用完, 因此q要向前移, 直到跳过第一个不是A的字符.

1
2
ABBBAAABBAAB
p=4, q=2, r=2

第五个字符不需要替换, q不变

1
2
3
4
5
6
7
8
ABBBAAABBAAB
p=5, q=2, r=2

ABBBAAABBAAB
p=6, q=2, r=2

ABBBAAABBAAB
p=7, q=3, r=2

p=7的时候, 又指向了B, 此时q也指向B, 因此只要q前移一格.

1
2
3
4
5
6
7
8
9
10
11
ABBBAAABBAAB
p=8, q=4, r=2

ABBBAAABBAAB
p=9, q=4, r=2

ABBBAAABBAAB
p=10, q=4, r=2

ABBBAAABBAAB
p=11, q=8, r=2

最后一个字符不是A, 因此q要前移, 先跳过三个A, 再继续跳过一个B以腾出一个替换次数.

最长连续重复字符的长度为max(p-q+1), 而因为输入只有26个大写字母, 因此对每一个出现的字母计算一次最长长度就可以得到总的最长长度.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
class Solution {
public:
    int characterReplacement(string s, int k) {
        int maxLen = 0;
        vector<bool> letters(26, false);
        for(auto c : s){
            letters[c - 'A'] = true;
        }
        for(int i = 0; i < 26; i++){
            if(!letters[i]) continue;
            int p, q = 0, r = 0;
            for(p = 0; p < s.length(); p++){
                if(s[p] == i + 'A'){
                    maxLen = max(maxLen, p - q + 1);
                }
                else{
                    if(r < k){
                        maxLen = max(maxLen, p - q + 1);
                        r++;
                    }
                    else{
                        while(s[q] == i + 'A') q++;
                        q++;
                        maxLen = max(maxLen, p - q + 1);
                    }
                }
            }
        }
        return maxLen;
    }
};

LeetCode 423. Reconstruct Original Digits from English

Oct 16, 2016

题目描述:

Given a non-empty string containing an out-of-order English representation of digits 0-9, output the digits in ascending order.

Note:

  1. Input contains only lowercase English letters.
  2. 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.
  3. Input length is less than 50,000.

Example 1:

1
2
3
4
Input: "owoztneoer"

Output: "012"

Example 2:

1
2
3
Input: "fviefuro"

Output: "45"

这道题关键在于找出所有的数字, 至于顺序问题采用排序或者先用数组保存最后再拼接都可以.

先遍历一次输入字符串, 记录每个字母的出现次数, 然后用贪心法逐个找出每个单词的出现次数, 只要组成这个单词的所有字母的剩余个数都不为0, 那么就可以组成这个单词. 但是如果采用0-9的顺序来依次搜索单词的话, one这个单词中的o, n和e可能都不是one中的, 可能是从其他单词中"拿来的", 这就会导致结果错误. 所以要以特定的顺序来遍历0-9. 如果一个单词中有"独特的"字母, 也就是只在这个单词中出现的字母, 那么它就不可能从其他的单词中"拿来"组成这个单词的所有字母, zero中的z, two中的w, four中的u, six中的x, eight中的g都是唯一的, 因此要把它们放在前面来搜索, 在剩下的单词中继续寻找"唯一的"字母. 这样就可以得到一个0-9的序列, 比如0246875319, 按照这个顺序来搜索单词就可以得到正确答案.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
class Solution {
    vector<string> digits = {"zero", "two", "four", "six", "eight", "seven", "five", "three", "one", "nine"};
    string digitStr = "0246875319";
public:
    string originalDigits(string s) {
        vector<int> letters(26, 0);
        for(auto c : s){
            letters[c - 'a']++;
        }
        vector<string> ansVector(10);
        for(int i = 0; i < digits.size(); i++){
            while(true){
                bool cont = true;
                for(int j = 0 ; j < digits[i].length(); j++){
                    if(letters[digits[i][j] - 'a'] == 0){
                        cont = false;
                        break;
                    }
                }
                if(!cont) break;
                for(int j = 0 ; j < digits[i].length(); j++){
                    letters[digits[i][j] - 'a']--;
                }
                ansVector[digitStr[i] - '0'].push_back(digitStr[i]);
            }
        }
        string ans;
        for(auto i : ansVector){
            ans += i;
        }
        return ans;
    }
};

LeetCode 166. Fraction to Recurring Decimal

Oct 13, 2016

题目描述:

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)”.

模拟手算除法, 难度不大但是非常繁琐.

对于循环小数使用一个hash表来保存出现过的余数的值和它所得的结果在结果字符串中的位置, 当出现重复的余数时就可以确定是循环小数.

还要注意int型的溢出问题.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
class Solution {
public:
	string fractionToDecimal(int numerator, int denominator) {
		if (numerator == 0) return string("0");
		bool sign = (numerator ^ denominator) & 0x80000000;
		unordered_map<long long, int> remainders;
		long long lldenominator = denominator;
		long long llnumerator = numerator;
		lldenominator = abs(lldenominator);
		llnumerator = abs(llnumerator);
		string dStr = to_string(lldenominator), nStr = to_string(llnumerator);
		int nLen = nStr.length(), dLen = dStr.length();
		long long tmpn = nStr[0] - '0';
		int ni = 1;
		
		bool hasDot = false;
		string ans;

		while (true) {
			int a = tmpn / lldenominator;
			if(!(a == 0 && !hasDot)) ans.push_back(a + '0');
			else if (a == 0 && !ans.empty()) ans.push_back('0');
			tmpn = tmpn % lldenominator;
			if (!tmpn && ni == nLen) break;
			tmpn *= 10;
			if (ni == nLen && !hasDot) {
				if (ans.empty()) ans += "0.";
				else ans += ".";
				hasDot = true;
			}

			if (ni < nLen) {
				tmpn += nStr[ni++] - '0';
			}
			if (!hasDot) continue;
			if (remainders.count(tmpn)) break;
			else remainders[tmpn] = ans.size();
		}
		if (tmpn) {
			int index = remainders[tmpn];
			ans.insert(ans.begin() + index, '(');
			ans.push_back(')');
		}
		if (sign) ans = "-" + ans;
		return ans;
	}
};

LeetCode 165. Compare Version Numbers

Oct 13, 2016

题目描述:

Compare two version numbers version1 and version2. If version1 > version2 return 1, if version1 < version2 return -1, otherwise return 0.

You may assume that the version strings are non-empty and contain only digits and the . character. The . character does not represent a decimal point and is used to separate number sequences. For instance, 2.5 is not “two and a half” or “half way to version three”, it is the fifth second-level revision of the second first-level revision.

Here is an example of version numbers ordering:

1
0.1 < 1.1 < 1.2 < 13.37

使用.把字符串分割为数组, 然后再依次比较大小.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
class Solution {
public:
    int compareVersion(string version1, string version2) {
        vector<int> v1 = versionVector(version1), v2 = versionVector(version2);
        for(int i = 0; i < v1.size() && i < v2.size(); i++){
            if(v1[i] > v2[i]) return 1;
            else if(v1[i] < v2[i]) return -1;
        }
        if(v1.size() > v2.size()){
            for(int i = v2.size(); i < v1.size(); i++){
                if(v1[i] != 0) return 1;
            }
        }
        else if(v1.size() < v2.size()){
            for(int i = v1.size(); i < v2.size(); i++){
                if(v2[i] != 0) return -1;
            }
        }
        return 0;
    }
    
    vector<int> versionVector(string &s){
        vector<int> version;
        int pos = 0, next = 0;
        while(next = s.find('.', pos)){
            version.push_back(stoi(s.substr(pos, next - pos)));
            if(next == string::npos) break;
            pos = next + 1;
        }
        return version;
    }
};