You are a product manager and currently leading a team to develop a new product. Unfortunately, the latest version of your product fails the quality check. Since each version is developed based on the previous version, all the versions after a bad version are also bad.

Suppose you have n versions [1, 2, …, n] and you want to find out the first bad one, which causes all the following ones to be bad.

You are given an API bool isBadVersion(version) which will return whether version is bad. Implement a function to find the first bad version. You should minimize the number of calls to the API.

// Forward declaration of isBadVersion API.

class Solution {
public:
int low=0,high=n-1,mid=0;
while(low<=high){
mid=low+(high-low)/2;
high=mid-1;
else
low=mid+1;
}
return low;
}
};


# 268.Missing Number

Given an array containing n distinct numbers taken from 0, 1, 2, …, n, find the one that is missing from the array.

For example, Given nums = [0, 1, 3] return 2.

Note: Your algorithm should run in linear runtime complexity. Could you implement it using only constant extra space complexity?

1. 等差数列求和
2. 位操作中的异或操作
3. 排序后二分查找

/*solution1 32ms accumulate the sequence from 0 to n,
not a good algorithm，when the test case is large，maybe overflow.
*/
class Solution {
public:
int missingNumber(vector<int>& nums) {
return ((nums.size()*(nums.size()+1))>>1)-accumulate(nums.begin(),nums.end(),0);/*parameter 0 is initial value*/
}
};


1. 让序列0~n中每一个元素先进行异或,得x
2. 让数组中每一个元素进行异或，得y
3. 返回x异或y的值

/*solution2 use bit manipulation and the property of XOR 36ms*/
class Solution {
public:
int missingNumber(vector<int>& nums) {
int x=0,y=0,i=0;
for(i=0;i<=nums.size();i++)
x^=i;
for(i=0;i<nums.size();i++)
y^=nums[i];
return x^y;
}
};


/*solution3 one-pass,with bit manipulation 38ms*/
class Solution {
public:
int missingNumber(vector<int>& nums) {
int x=nums.size(),y=0,i=0;
for(i=0;i<nums.size();i++)
x=x^i^nums[i];
return x;
}
};


# 240.Search a 2D Matrix II

240.Search a 2D Matrix II

Write an efficient algorithm that searches for a value in an m x n matrix. This matrix has the following properties:

• Integers in each row are sorted in ascending from left to right.
• Integers in each column are sorted in ascending from top to bottom.

For example,

Consider the following matrix:

[
[1,   4,  7, 11, 15],
[2,   5,  8, 12, 19],
[3,   6,  9, 16, 22],
[10, 13, 14, 17, 24],
[18, 21, 23, 26, 30]
]


Given target = 5, return true.

Given target = 20, return false.

/*solution1 264ms*/
class Solution {
public:
bool searchMatrix(vector<vector<int>>& matrix, int target) {
if(matrix.empty()||matrix[0].empty())
return false;
int row=0,col=matrix[0].size()-1,size=matrix.size();
while(row<size&&col>=0){
if(matrix[row][col]==target)
return true;
else if(matrix[row][col]>target)
col--;
else if(matrix[row][col]<target)
row++;
}
return false;
}
};


/*solution2 164ms*/
class Solution {
public:
bool searchMatrix(vector<vector<int>>& matrix, int target) {
int row = matrix.size();
int col = matrix[0].size();
int i = row-1,j =0;
while(i>=0&&j<col){
if(target>matrix[i][j])
j++;
else if(target<matrix[i][j])
i--;
else
return true;
}
return false;
}
};


# 238.Product of Array Except Self

238.Product of Array Except Self

Given an array of n integers where n > 1, nums, return an array output such that output[i] is equal to the product of all the elements of nums except nums[i].

Solve it without division and in O(n).

For example, given [1,2,3,4], return [24,12,8,6].

Follow up: Could you solve it with constant space complexity? (Note: The output array does not count as extra space for the purpose of space complexity analysis.)

• 既然要算出某一元素以外其他元素的乘积，那么我们可以先算出所有元素的乘积，最后再除以不需要的元素即可

• 对于[0,1]这样的只有两个元素且其中一个元素的值为0的数组，我们发现只要交换一下两个元素然后返回即可。

• 对于长度大于2的数组，又要再分两种情况：
1. 长度大于2且只含有一个0，例如[9 0 3]这样的数组，我们发现只需要把0所在的位置赋值为其他元素的乘积，而其他位置依然为0，返回即可。
2. 长度大于2但含有不止一个0，例如[9 0 0 3]这样的数组，我们容易证明对于这样的数组，要返回的数组的所有元素应该都为0。

Corner case讨论完毕，下面我们看代码:

/*solution1 60ms*/
class Solution {
public:
vector<int> productExceptSelf(vector<int>& nums) {
int i=0,res=1,count=0,zero_pos=0;
vector<int> output(nums.size(),0);
for(i=0;i<nums.size();i++)
res=res*nums[i];
if(!res){
if(nums.size()==2){
swap(nums[0],nums[1]);
return nums;
}
else if(nums.size()>2){
res=1;
/*计算除0以外所有元素的乘积，并记录0的个数和位置*/
for(i=0;i<nums.size();i++){
if(nums[i]==0){
count++;
zero_pos=i;
continue;
}
res=res*nums[i];
}
if(count==1){
output[zero_pos]=res;
return output;
}
if(count>1)
return output;
}
}
for(i=0;i<nums.size();i++)
output[i]=res/nums[i];
return output;
}
};


/*solution2 60ms*/
class Solution {
public:
vector<int> productExceptSelf(vector<int>& nums) {
vector<int> arr1(nums.size(),1);
vector<int> arr2(nums.size(),1);
for(int i=1;i<arr1.size();i++)
arr1[i]=arr1[i-1]*nums[i-1];
for(int i=arr2.size()-2;i>=0;i--)
arr2[i]=arr2[i+1]*nums[i+1];
for(int i=0;i<arr1.size();i++)
arr1[i]=arr1[i]*arr2[i];
return arr1;
}
};


/*solution3 60ms*/
class Solution {
public:
vector<int> productExceptSelf(vector<int>& nums) {
vector<int> arr1(nums.size(),1);
int tmp=1;
for(int i=1;i<arr1.size();i++)
arr1[i]=arr1[i-1]*nums[i-1];
for(int i=nums.size()-1;i>=0;i--){
arr1[i]=arr1[i]*tmp;
tmp=tmp*nums[i];
}
return arr1;
}
};


# 136. Single Number

Given an array of integers, every element appears twice except for one. Find that single one.

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

/*use bit manipulation 20ms,no extra place*/
class Solution {
public:
int singleNumber(vector<int>& nums) {
int i=0,single=0;
for(i=0;i<nums.size();i++)
single^=nums[i];
return single;
}
};


class Solution {
public:
int singleNumber(vector<int>& nums) {
unordered_map<int,int> hash;
int i=0,single;
for(i=0;i<nums.size();i++){
if(hash.find(nums[i])==hash.end())
hash[nums[i]]=i;
else
hash.erase(nums[i]);
}
unordered_map<int,int>::iterator it=hash.begin();
return (*it).first;
}
};