leetcode 80 Remove Duplicates from Sorted Array II （有序数组去除重复元素）

Suppose an array sorted in ascending order is rotated at some pivot unknown to you beforehand. (i.e., 0 1 2 4 5 6 7 might become 4 5 6 7 0 1 2). Write a function to determine if a given target is in the array. The array may contain duplicates. 好像阿里一面的时候问过。。。 思路：肯定是二分。。。不过由于有重复元素。。。所以很恶心。。。

According to the Wikipedia’s article: “The Game of Life, also known simply as Life, is a cellular automaton devised by the British mathematician John Horton Conway in 1970.” Given a board with m by n cells, each cell has an initial state live (1) or dead (0). Each cell interacts with its eight neighbors (horizontal, vertical, diagonal) using the following four rules (taken from the above Wikipedia article): 1. Any live cell with fewer than two live neighbors dies, as if caused by under-population. 2. Any live cell with two or three live neighbors lives on to the next generation. 3. Any live cell with more than three live neighbors dies, as if by over-population.. 4. Any dead cell with exactly three live neighbors becomes a live cell, as if by reproduction. Write a function to compute the next state (after one update) of the board given its current state.

Given a collection of integers that might contain duplicates, nums, return all possible subsets. Note: The solution set must not contain duplicate subsets. For example, If nums = [1,2,2], a solution is: 1[ 2 [2], 3 [1], 4 [1,2,2], 5 [2,2], 6 [1,2], 7 [] 8] 思路： 复习（？）一下 枚举子集的三种写法 （还有种更飘逸的…先不写了orz 这道题我用位向量法A的。。

1/* *********************************************** 2Author :111qqz 3Created Time :2017年04月05日 星期三 16时49分57秒 4File Name :106.cpp 5************************************************ */ 6/** 7 * Definition for a binary tree node. 8 * struct TreeNode { 9 * int val; 10 * TreeNode *left; 11 * TreeNode *right; 12 * TreeNode(int x) : val(x), left(NULL), right(NULL) {} 13 * }; 14 */ 15class Solution { 16public: 17 TreeNode* buildTree(vector<int>& inorder, vector<int>& postorder) { 18 int siz = inorder.size(); 19 if (siz==0) return NULL; 20 int rt = postorder[siz-1]; 21 int pos = -1; 22 for ( int i = 0 ; i < siz; i++) 23 { 24 if (inorder[i]==rt) 25 { 26 pos = i ; 27 break; 28 } 29 } 30 TreeNode *head = new TreeNode(rt); 31 vector<int>in,post; 32 for ( int i = 0 ; i < pos ; i++) 33 { 34 in.push_back(inorder[i]); 35 post.push_back(postorder[i]); 36 } 37 head->left = buildTree(in,post); 38 in.clear(); 39 post.clear(); 40 for ( int i = pos + 1 ; i < siz ; i++) 41 { 42 in.push_back(inorder[i]); 43 post.push_back(postorder[i-1]); 44 } 45 head->right = buildTree(in,post); 46 return head; 47 } 48};

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. 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(n2)`. 4. There is only one duplicate number in the array, but it could be repeated more than once. 思路：O(n^2)的复杂度暴力即可，说个O(n)复杂度的解法。