LeetCode Total Hamming Distance The Hamming distance between two integers is the number of positions at which the corresponding bits are different. Now your job is to find the total Hamming distance between all pairs of the given numbers. Example:

Input: 4, 14, 2
Output: 6
Explanation: In binary representation, the 4 is 0100, 14 is 1110, and 2 is 0010 (just
showing the four bits relevant in this case). So the answer will be:
HammingDistance(4, 14) + HammingDistance(4, 2) + HammingDistance(14, 2) = 2 + 2 + 2 = 6.

1. Elements of the given array are in the range of 0 to 10^9
2. Length of the array will not exceed 10^4.

• 4:  0100
• 14:1110
• 2:  0010

LeetCode Sum of Left Leaves Find the sum of all left leaves in a given binary tree. Example:

    3
   / \
  9  20
    /  \
   15   7
There are two left leaves in the binary tree, with values 9 and 15 respectively. Return 24.

LeetCode Add Two Numbers II You are given two non-empty linked lists representing two non-negative integers. The most significant digit comes first and each of their nodes contain a single digit. Add the two numbers and return it as a linked list. You may assume the two numbers do not contain any leading zero, except the number 0 itself. Follow up: What if you cannot modify the input lists? In other words, reversing the lists is not allowed. Example:

Input: (7 -> 2 -> 4 -> 3) + (5 -> 6 -> 4)
Output: 7 -> 8 -> 0 -> 7

LeetCode Assign Cookies Assume you are an awesome parent and want to give your children some cookies. But, you should give each child at most one cookie. Each child i has a greed factor g_i, which is the minimum size of a cookie that the child will be content with; and each cookie j has a size s_j. If s_j >= g_i, we can assign the cookie j to the child i, and the child i will be content. Your goal is to maximize the number of your content children and output the maximum number. Note: You may assume the greed factor is always positive. You cannot assign more than one cookie to one child. Example 1:

Input: [1,2,3], [1,1]
Output: 1
Explanation: You have 3 children and 2 cookies. The greed factors of 3 children are 1, 2, 3.
And even though you have 2 cookies, since their size is both 1, you could only make the child whose greed factor is 1 content.
You need to output 1.

Input: [1,2], [1,2,3]
Output: 2
Explanation: You have 2 children and 3 cookies. The greed factors of 2 children are 1, 2.
You have 3 cookies and their sizes are big enough to gratify all of the children,
You need to output 2.

LeetCode Magical String A magical string S consists of only ‘1’ and ‘2’ and obeys the following rules: The string S is magical because concatenating the number of contiguous occurrences of characters ‘1’ and ‘2’ generates the string Sitself. The first few elements of string S is the following: S = “1221121221221121122……” If we group the consecutive ‘1’s and ‘2’s in S, it will be: 1 22 11 2 1 22 1 22 11 2 11 22 …… and the occurrences of ‘1’s or ‘2’s in each group are: 1 2 2 1 1 2 1 2 2 1 2 2 …… You can see that the occurrence sequence above is the S itself. Given an integer N as input, return the number of ‘1’s in the first N number in the magical string S. Note: N will not exceed 100,000. Example 1:

Input: 6
Output: 3
Explanation: The first 6 elements of magical string S is "12211" and it contains three 1's, so return 3.

167. Two Sum II – Input array is sorted

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.

Note:

• Your returned answers (both index1 and index2) are not zero-based.
• You may assume that each input would have exactly one solution and you may not use the same element twice.

Example:

Input: numbers = [2,7,11,15], target = 9
Output: [1,2]
Explanation: The sum of 2 and 7 is 9. Therefore index1 = 1, index2 = 2.

本题要在一个已排序数组中找两个数，使得这两个数的和等于一个目标target。这应该是LeetCode Two Sum的简化版吧，因为之前那个题有一种解法就是先对数组排序，然后首尾指针夹逼，现在这个题都排好序了，那还有什么好说的呢，直接借用之前的方法。 完整代码如下：

class Solution {
public:
    vector<int> twoSum(vector<int>& numbers, int target)
    {
        int i = 0, j = numbers.size() – 1;
        while (numbers[i] + numbers[j] != target) {
            if (numbers[i] + numbers[j] > target)
                –j;
            else
                ++i;
        }
        return vector<int>({ i + 1, j + 1 });
    }
};

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

260. Single Number III 260. Single Number III

Given an array of numbers nums, in which exactly two elements appear only once and all the other elements appear exactly twice. Find the two elements that appear only once.

Example:

Input:  [1,2,1,3,2,5]
Output: [3,5]

Note:

1. The order of the result is not important. So in the above example, [5, 3] is also correct.
2. Your algorithm should run in linear runtime complexity. Could you implement it using only constant space complexity? 260. Single Number III

本题是LeetCode Single Number的升级版，即数组中有两个只出现一次的数，其他的数都出现了两次，现在要把这两个只出现一次的数找出来。
直接用LeetCode Single Number异或的方法是不行的，因为虽然出现两次的数异或等于0了，但是有两个只出现一次的数a和b，得到的结果是它们的异或a^b。
如果有办法把数组中的数分成两堆，a和b在不同的堆里，并且每堆除了a或b，其他数也都恰好出现了两次，即如果3出现两次，则两个3要么都在a堆中，要么都在b堆中。这样我们就可以对两个堆分别异或，找到每堆中只出现一次的数a和b。
那么根据a^b的结果能否把数分成两堆呢，答案是可以的。异或的规则是相同为0，不同为1。既然a和b分别只出现了1次，那么a和b肯定是不同的两个数，所以他们的异或结果的二进制中肯定有一位是1，记这一位为x，那么a和b在x位的二进制肯定是不一样的，这就找到了a和b的区别。
所以我们可以把数组中的所有数按x位为0或1分成两堆，这样就达到了开头的目的，然后利用LeetCode Single Number的方法，在两堆进行异或，最终就能找到a和b了。完整代码如下：

class Solution {
public:
    vector<int> singleNumber(vector<int>& nums)
    {
        int flag = 0;
        for (int i = 0; i < nums.size(); ++i) {
            flag ^= nums[i];
        }
        int mask = 1;
        for (int i = 0; i < 32; ++i) {
            if ((flag & mask) != 0)
                break;
            mask <<= 1;
        }
        vector<int> ans(2, 0);
        for (int i = 0; i < nums.size(); ++i) {
            if (nums[i] & mask) {
                ans[0] ^= nums[i];
            }
            else {
                ans[1] ^= nums[i];
            }
        }
        return ans;
    }
};

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

二刷。相同思路，很简洁的代码，对于n，直接n&(-n)就能得到其最后一位1的位置，请看面试笔试宝典第三版P97，代码如下：

class Solution {
public:
	vector<int> singleNumber(vector<int>& nums) {
		int c = 0, n = nums.size();
		for (int i = 0; i < n; ++i) {
			c ^= nums[i];
		}
		c = c & (-c); // 得到c最后一个1
		int a = 0, b = 0;
		for (int i = 0; i < n; ++i) {
			if ((nums[i] & c) == 0) { // 注意加括号，位运算优先级低于==
				a ^= nums[i];
			}
			else {
				b ^= nums[i];
			}
		}
		return { a,b };
	}
};

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

137. Single Number II

Given a non-empty array of integers, every element appears three times except for one, which appears exactly once. Find that single one.

Note:

Your algorithm should have a linear runtime complexity. Could you implement it without using extra memory?

Example 1:

Input: [2,2,3,2]
Output: 3

Example 2:

Input: [0,1,0,1,0,1,99]
Output: 99

数组中有出现3次的数，但是也有一个出现1次的数，现在要把这个只出现1次的数找出来。要求是线性时间复杂度和常数空间复杂度。 相比于LeetCode Single Number有难度。网上看到一个很不错的题解，分析得很详细。 初级解法是，把数组中每个数字的对应二进制位加起来，因为3个相同的数对应二进制位加起来之后模3一定等于0，比如5的二进制为101，三个101加起来就是303，每一位模3就是000。所以如果混入了一个只出现一次的数，这样取模之后，剩余位为1的就是我们要找的数的二进制形式。 这种解法需要一个32位的数组，用来统计所有数每一位出现1的次数之和，所以空间复杂度是O(32)=O(1)。时间复杂度的话，相当于O(32n)=O(n)，是线性的。完整代码如下：

class Solution {
public:
    int singleNumber(vector<int>& nums)
    {
        int bit_len = sizeof(int) * 8;
        vector<int> bit(bit_len, 0);
        for (int i = 0; i < bit_len; ++i) {
            for (int j = 0; j < nums.size(); ++j) {
                bit[i] += (nums[j] & 1);
                nums[j] >>= 1;
            }
        }
        int ans = 0;
        for (int i = 0; i < bit_len; ++i) {
            int r = bit[i] % 3;
            ans |= (r << i);
        }
        return ans;
    }
};

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

高级解法是，使用三个int的每一位表示所有数每一位出现1次数之和的情况，one对应位为1表示这一位出现了1次1，two对应位为1表示这一位出现了2次1，three对应位为1表示这一位出现了3次1。但是one,two,three对应位不可能都同时为1。

通过分析对应位的关系（请看原博客），发现one,two,three可以快速通过位运算计算得到。完整代码如下：

class Solution {
public:
    int singleNumber(vector<int>& nums)
    {
        int one = 0, two = 0, three = 0;
        for (int i = 0; i < nums.size(); ++i) {
            two |= (one & nums[i]);
            one ^= nums[i];
            three = one & two;
            one -= three;
            two -= three;
        }
        return one;
    }
};

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

初级解法还是好理解一些，会不会是一个通用的解法呢，比如数组中出现1次和出现4次（甚至k次）的数混在一起，都可以通过模k求解呢？