LeetCode Find All Duplicates in an Array Given an array of integers, 1 ≤ a[i] ≤ n (n = size of array), some elements appear twice and others appear once. Find all the elements that appear twice in this array. Could you do it without extra space and in O(n) runtime? Example:

Input:
[4,3,2,7,8,2,3,1]
Output:
[2,3]

226. Invert Binary Tree 226. Invert Binary Tree LeetCode Invert Binary Tree Invert a binary tree.

     4
   /   \
  2     7
 / \   / \
1   3 6   9

to

     4
   /   \
  7     2
 / \   / \
9   6 3   1

Trivia: This problem was inspired by this original tweet by Max Howell:

Google: 90% of our engineers use the software you wrote (Homebrew), but you can’t invert a binary tree on a whiteboard so fuck off.

本题要把二叉树翻转，看题目中的例子，也就是交换树的左右子树，然后递归的交换就好了。简单题，完整代码如下：

class Solution {
public:
    void invert(TreeNode* root)
    {
        if (root == NULL)
            return;
        swap(root->left, root->right);
        invert(root->left);
        invert(root->right);
    }
    TreeNode* invertTree(TreeNode* root)
    {
        invert(root);
        return root;
    }
};

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

LeetCode Construct the Rectangle For a web developer, it is very important to know how to design a web page’s size. So, given a specific rectangular web page’s area, your job by now is to design a rectangular web page, whose length L and width W satisfy the following requirements:

1. The area of the rectangular web page you designed must equal to the given target area.
2. The width W should not be larger than the length L, which means L >= W.
3. The difference between length L and width W should be as small as possible.

Input: 4
Output: [2, 2]
Explanation: The target area is 4, and all the possible ways to construct it are [1,4], [2,2], [4,1].
But according to requirement 2, [1,4] is illegal; according to requirement 3,  [4,1] is not optimal compared to [2,2]. So the length L is 2, and the width W is 2.

1. The given area won’t exceed 10,000,000 and is a positive integer
2. The web page’s width and length you designed must be positive integers.

287. Find the Duplicate Number 287. Find the Duplicate Number

Given an array nums containing n + 1 integers where each integer is between 1 and n (inclusive), prove that at least one duplicate number must exist. Assume that there is only one duplicate number, find the duplicate one.

Example 1:

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

Example 2:

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

Note:

1. You must not modify the array (assume the array is read only).
2. You must use only constant, O(1) extra space.
3. Your runtime complexity should be less than O(n²).
4. There is only one duplicate number in the array, but it could be repeated more than once. 287. Find the Duplicate Number

一个长度为n+1的数组，包含1~n的数字，证明至少有一个数字重复，并找出这个重复数字。 证明好说，鸽巢原理。要求在线性时间复杂度和常数空间复杂度把这个重复的数字找出来就有难度了，而且不能修改原数组，难以用上LeetCode Find All Numbers Disappeared in an Array的技巧。 这题确实hard，看了看提示，以及网上的题解，现总结如下。 第一种解法是二分搜索。根据鸽巢原理，如果有n+1个[1,n]的数，则必有一个数重复了，把区间分成[1,m]和[m+1,n]，则重复的数字要么出现在[1,m]，要么出现在[m+1,n]，所以只需统计一下小于等于和大于m的数字的个数，数字多的那个区间肯定是存在重复数字的区间。然后在那个区间递归的找下去，直到找到重复数字。
完整代码如下：

class Solution {
public:
    int findDuplicate(vector<int>& nums)
    {
        int low = 1, high = nums.size() – 1;
        while (low < high) {
            int mid = (low + high) / 2, low_cnt = 0;
            for (int i = 0; i < nums.size(); ++i) {
                if (nums[i] <= mid)
                    ++low_cnt;
            }
            if (low_cnt > mid) {
                high = mid;
            }
            else {
                low = mid + 1;
            }
        }
        return low;
    }
};

本代码提交AC，用时9MS。
还有一种解法和LeetCode Linked List Cycle II很类似，如果存在重复数字，则使用下标递归访问的时候，会出现循环访问。首先通过快慢指针找到循环相遇点，然后慢指针回到原点，快慢指针按相同速度前进，直到遇到函数值相同时停止，这个相同的函数值即为重复数字。一些证明可以参考这个博客。
完整代码如下：

class Solution {
public:
    int findDuplicate(vector<int>& nums)
    {
        int slow = 0, fast = 0;
        while (true) {
            slow = nums[slow];
            fast = nums[nums[fast]];
            if (slow == fast)
                break;
        }
        slow = 0;
        while (true) {
            slow = nums[slow];
            fast = nums[fast];
            if (slow == fast)
                return slow;
        }
    }
};

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

二刷。对二分搜索的解读。假设数组没有重复数字，比如[1,2,3,4,5,6,7]，则对于任意一个数x，<=x的数的个数和x是相等的，比如<=1的数有1个，<=2的数有2个etc…如果出现重复数字，假设比中点小，则<=m的数的个数要大于m。所以代码中每次比较是low_cnt和m比较。

l、r、while(l<=r)都是标准的二分搜索框架。最后返回r+1，想象一直low_cnt>m，知道不满足while循环，则最后一个满足的就是r+1。

class Solution {
public:
	int findDuplicate(vector<int>& nums) {
		int n = nums.size();
		int l = 1, r = n - 1;
		while (l <= r) {
			int m = l + (r - l) / 2;
			int low_cnt = 0;
			for (int i = 0; i < n; ++i) {
				if (nums[i] <= m)++low_cnt;
			}
			if (low_cnt > m)r = m - 1;
			else l = m + 1;
		}
		return r + 1;
	}
};

LeetCode Find All Numbers Disappeared in an Array Given an array of integers where 1 ≤ a[i] ≤ n (n = size of array), some elements appear twice and others appear once. Find all the elements of [1, n] inclusive that do not appear in this array. Could you do it without extra space and in O(n) runtime? You may assume the returned list does not count as extra space. Example:

Input:
[4,3,2,7,8,2,3,1]
Output:
[5,6]

292. Nim Game

You are playing the following Nim Game with your friend: There is a heap of stones on the table, each time one of you take turns to remove 1 to 3 stones. The one who removes the last stone will be the winner. You will take the first turn to remove the stones.

Both of you are very clever and have optimal strategies for the game. Write a function to determine whether you can win the game given the number of stones in the heap.

Example:

Input: 4 Output: false  Explanation: If there are 4 stones in the heap, then you will never win the game;              No matter 1, 2, or 3 stones you remove, the last stone will always be               removed by your friend. 292. Nim Game 

博弈论的题。两个人轮流拿石头，一次可以拿1~3个，拿掉最后一个石头的人获胜。规定我先拿，问如果石头数为n时，我是否可以取胜。 看Hint，找规律。

• 如果n∈[1,3]，则我第一次拿就可以把所有石头拿走，所以我肯定可以获胜。
• 如果n=4，则无论我第一次拿多少个，因为我最多可以拿3个，所以剩下的石头数转换为了n∈[1,3]的情况，也就是变成了对手肯定能获胜的情况。
• 如果n∈[5,7]，则我为了获胜，可以想方设法让我第一次拿了之后，剩余4个石头，这样相当于对手遇到n=4的情况，于是转换为我可以获胜的情况。
• 如果n=8，则无论第一次拿多少个，剩余的石头个数都转换为了n∈[5,7]的情况，也就变成了对手必胜的情况。
• …

观察以上的分析，发现当n是4的倍数时，我必输；否则我必胜。代码就很好写了：

class Solution {
public:
    bool canWinNim(int n) { return n % 4 != 0; }
};

本代码提交AC，用时0MS。
类似博弈论的题，一定要在纸上写几个例子出来，然后仔细找规律。

LeetCode Island Perimeter You are given a map in form of a two-dimensional integer grid where 1 represents land and 0 represents water. Grid cells are connected horizontally/vertically (not diagonally). The grid is completely surrounded by water, and there is exactly one island (i.e., one or more connected land cells). The island doesn’t have “lakes” (water inside that isn’t connected to the water around the island). One cell is a square with side length 1. The grid is rectangular, width and height don’t exceed 100. Determine the perimeter of the island. Example:

[[0,1,0,0],
 [1,1,1,0],
 [0,1,0,0],
 [1,1,0,0]]
Answer: 16
Explanation: The perimeter is the 16 yellow stripes in the image below:

LeetCode Max Consecutive Ones Given a binary array, find the maximum number of consecutive 1s in this array. Example 1:

Input: [1,1,0,1,1,1]
Output: 3
Explanation: The first two digits or the last three digits are consecutive 1s.
    The maximum number of consecutive 1s is 3.

• The input array will only contain 0 and 1.
• The length of input array is a positive integer and will not exceed 10,000