LeetCode Fizz Buzz 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:

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

---

从1到n生成数字字符串，但是如果某个数能整除15，则生成FizzBuzz；能整除5，则生成Buzz；能整除3则生成Fizz。 发现<string>中的to_string()很好用:-) 完整代码如下： [cpp] class Solution { public: vector<string> fizzBuzz(int n) { vector<string> ans; for (int i = 1; i <= n; i++) { if (i % 15 == 0)ans.push_back("FizzBuzz"); else if (i % 5 == 0)ans.push_back("Buzz"); else if (i % 3 == 0)ans.push_back("Fizz"); else ans.push_back(to_string(i)); } return ans; } }; [/cpp] 本代码提交AC，用时3MS。]]>

num1 and num2 represented as string, return the sum of num1 and num2. Note:

1. The length of both num1 and num2 is < 5100.
2. Both num1 and num2 contains only digits 0-9.
3. Both num1 and num2 does not contain any leading zero.
4. You must not use any built-in BigInteger library or convert the inputs to integer directly.

---

实现字符串加法，按照小学老师教的，从低到高一位一位加，注意保留进位。这题仔细一点，然后调试两次就差不多能AC了。 代码中需要注意运算符优先级，加法优先级高于三目运算符，所以三目运算符要加括号。 完整代码如下： [cpp] class Solution { public: string addStrings(string num1, string num2) { string ans = ""; int i = num1.size() – 1, j = num2.size() – 1; bool carry = false; while (i >= 0 || j >= 0) { int sum = 0; if (i < 0)sum = (num2[j] – ‘0’) + (carry ? 1 : 0); else if (j < 0)sum = (num1[i] – ‘0’) + (carry ? 1 : 0); else sum = (num1[i] – ‘0’) + (num2[j] – ‘0’) + (carry ? 1 : 0); //注意运算符优先级，要加括号 if (sum >= 10) { carry = true; sum -= 10; } else { carry = false; } char c = ‘0’ + sum; ans = c + ans; i–; j–; } if (carry)return ‘1’ + ans; else return ans; } }; [/cpp] 本代码提交AC，用时12MS。]]>

LeetCode Number of Segments in a String Count the number of segments in a string, where a segment is defined to be a contiguous sequence of non-space characters. Please note that the string does not contain any non-printable characters. Example:

Input: "Hello, my name is John"
Output: 5

---

统计一个字符串中segments的个数，每个segment被至少一个空格隔开，所以不能只单纯统计空格的个数。其实一个segment的特点是以非空格开头，并且前一个字符一定是空格；或者它是第一个segment，开头没有空格。 完整代码如下： [cpp] class Solution { public: int countSegments(string s) { if (s == "")return 0; int ans = 0; for (int i = 0; i < s.size(); i++) { if (s[i] != ‘ ‘) { if (i == 0 || (s[i – 1] == ‘ ‘))ans++; } } return ans; } }; [/cpp] 本代码提交AC，用时0MS。]]>

LeetCode Hamming Distance The Hamming distance between two integers is the number of positions at which the corresponding bits are different. Given two integers x and y, calculate the Hamming distance. Note: 0 ≤ x, y < 2³¹. Example:

Input: x = 1, y = 4
Output: 2
Explanation:
1   (0 0 0 1)
4   (0 1 0 0)
       ↑   ↑
The above arrows point to positions where the corresponding bits are different.

---

求两个整数的汉明距离，即两个整数的二进制串中不一样的位数。马上联想到之前LeetCode Number of 1 Bits求二进制中1的个数，这里是一样的，相当于求两个整数的二进制位，每次比较一下，如果不同，则汉明距离加1；当发现两个数已经相等时，汉明距离不可能再增加了。 完整代码如下： [cpp] class Solution { public: int hammingDistance(int x, int y) { int dist = 0; for (int i = 0; i < 32; i++) { if (x == y)break; if ((x & 1) != (y & 1))dist++; x >>= 1; y >>= 1; } return dist; } }; [/cpp] 本代码提交AC，用时0MS，击败55.12%，加了那个break效率会高很多。]]>

190. Reverse Bits

Reverse bits of a given 32 bits unsigned integer.

Example 1:

Input: 00000010100101000001111010011100
Output: 00111001011110000010100101000000
Explanation: The input binary string 00000010100101000001111010011100 represents the unsigned integer 43261596, so return 964176192 which its binary representation is 00111001011110000010100101000000.

Example 2:

Input: 11111111111111111111111111111101
Output: 10111111111111111111111111111111
Explanation: The input binary string 11111111111111111111111111111101 represents the unsigned integer 4294967293, so return 3221225471 which its binary representation is 10111111111111111111111111111111.

Note:

• Note that in some languages such as Java, there is no unsigned integer type. In this case, both input and output will be given as signed integer type and should not affect your implementation, as the internal binary representation of the integer is the same whether it is signed or unsigned.
• In Java, the compiler represents the signed integers using 2’s complement notation. Therefore, in Example 2 above the input represents the signed integer -3 and the output represents the signed integer -1073741825.

Follow up:

If this function is called many times, how would you optimize it?

---

本题要把一个无符号32位整数的二进制位翻转，因为之前刚刷过LeetCode Number of 1 Bits可以快速统计uint32中二进制1的个数，所以很快联想到解法。一个32次的循环，依次获取到原数字的每一个二进制位，然后和结果取或，结果依次左移。
完整代码如下：

class Solution {
public:
    uint32_t reverseBits(uint32_t n)
    {
        uint32_t ans = 0;
        for (int i = 0; i < 31; i++) {
            ans |= (n & 1);
            ans <<= 1;
            n >>= 1;
        }
        return ans | (n & 1);
    }
};

本代码提交AC，用时3MS。

有意思的是Follow up，说如果这个函数会被多次调用，该怎样优化。都提到会被多次调用了，那肯定是把之前计算过的结果保存起来，下次查询的时候直接调用。但是一个32位的数，一共有2^32种情况，多次调用遇到同一个数的概率有点低，如果把之前的结果当成一个缓存，则缓存命中的概率有点低。如果只是缓存4bit的结果，只有2^4=16种情况，命中的概率就大大提高了。 这个解法就是直接缓存了4bit的翻转结果，放到tb数组中。每次取出原数字的4bit，然后直接查tb表，得到4bit的翻转结果，和ret取或，这样for循环只执行了8次。不错。

char tb[16] = { 0, 8, 4, 12, 2, 10, 6, 14, 1, 9, 5, 13, 3, 11, 7, 15 };
uint32_t reverseBits(uint32_t n)
{
    int curr = 0;
    uint32_t ret = 0;
    uint32_t msk = 0xF;
    for (int i = 0; i < 8; i++) {
        ret = ret << 4;
        curr = msk & n;
        ret |= tb[curr];
        n = n >> 4;
    }
    return ret;
}

还有一种解法借鉴了归并排序的思路，假设要对一个8bit的数组归并排序，先要不断一分为二，在归并的时候，在最底层对每1bit-1bit的对归并排序，倒数第二层对每2bit-2bit的对归并排序，如此往上归并。

      01101001
    /         \
   0110      1001
  /   \     /   \
 01   10   10   01
 /\   /\   /\   /\
0 1  1 0  1 0  0 1

逆序也可以借鉴归并的思路，如下，首先最底层对每相邻的1bit-1bit交换位置，然后倒数第二层，对每相邻的2bit-2bit交换位置，如此往上交换，得到序列10010110，正好是上图中01101001的逆序。

      10010110
    /         \
   0110      1001
  /   \     /   \
 10   01   01   10
 /\   /\   /\   /\
0 1  1 0  1 0  0 1

这个思路的代码如下，没有了for循环，只需执行20次位运算，代码中用8bit的字符串模拟了执行的情况。

class Solution {
public:
    uint32_t reverseBits(uint32_t x)
    {
        // x = ABCDEFGH
        x = ((x & 0x55555555) << 1) | ((x & 0xAAAAAAAA) >> 1); // x = B0D0F0H0 | 0A0C0E0G = BADCFEHG
        x = ((x & 0x33333333) << 2) | ((x & 0xCCCCCCCC) >> 2); // x = DC00HG00 | 00BA00FE = DCBAHGFE
        x = ((x & 0x0F0F0F0F) << 4) | ((x & 0xF0F0F0F0) >> 4); // x = HGFE0000 | 0000DCBA = HGFEDCBA
        x = ((x & 0x00FF00FF) << 8) | ((x & 0xFF00FF00) >> 8); // …
        x = ((x & 0x0000FFFF) << 16) | ((x & 0xFFFF0000) >> 16);
        return x;
    }
};

上面的16进制数字中:
0x55555555 = 0101 0101 0101 0101 0101 0101 0101 0101
0xAAAAAAAA = 1010 1010 1010 1010 1010 1010 1010 1010
0x33333333 = 0011 0011 0011 0011 0011 0011 0011 0011
0xCCCCCCCC = 1100 1100 1100 1100 1100 1100 1100 1100
本代码提交AC，用时也是3MS。