# 50. Pow(x, n)

Implement pow(x, n).

1. 当n>0时，不断让x相乘即可，注意你的结果最好使用long long int,以防溢出
2. n==0时，若x不为0，返回1即可
3. n<0时，让x的倒数不断相乘

/*solution1 20ms*/
class Solution {
public:
double myPow(double x, int n) {
if(x&&!n)
return 1;
double res=1,flag=0;
if(x==-1.0)
return n&1==0||n==INT_MIN? 1:-1;
if(n<0){
if(n==INT_MIN&&x!=1)/*When n==INT_MIN,if you use abs() ,
will cause overflow,for the abstract of INT_MIN is larger than INT_MAX for 1*/
return 0;
for(int i=0;i<abs(n);i++){
flag=res;
res=res*(1/x);
if(res==flag)/*flag is used to prevent from time limit exceed，
for n may be very large, when res is going to be zero,
the iteration will be useless*/
return res;
}
}
else{
for(int i=0;i<n;i++){
flag=res;
res=res*x;
if(res==flag)
return res;
}
}
return res;
}
};


class Solution {
private:
double power(double x,int n){
if(x&&!n)
return 1;
double res=power(x,n/2);
if(n%2==0)
return res*res;
else
return res*res*x;
}

public:
double myPow(double x, int n) {
if(n<0)
return 1/power(x,-n);
else
return power(x,n);
}
};


# 374. Guess Number Higher or Lower

We are playing the Guess Game. The game is as follows:

I pick a number from 1 to n. You have to guess which number I picked.

Every time you guess wrong, I’ll tell you whether the number is higher or lower.

You call a pre-defined API guess(int num) which returns 3 possible results (-1, 1, or 0):

-1 : My number is lower
1 : My number is higher
0 : Congrats! You got it!


Example:

n = 10, I pick 6.

Return 6.


My number is lower中的My到底是作为解题人的“我”提供的数据小了呢？还是题目作为游戏发起人的”我”提供的数字小了？

// Forward declaration of guess API.
// @param num, your guess
// @return -1 if my number is lower, 1 if my number is higher, otherwise return 0
int guess(int num);

class Solution {
public:
int guessNumber(int n) {
long long int low=1,high=n,mid=0;
while(low<=high){
mid=low+((high-low)>>1);
if(guess(mid)==0)
return mid;
else if(guess(mid)==1)
low=mid+1;
else
high=mid-1;
}
return -1;
}
};


# 81.Search in Rotated Sorted Array II

81.Search in Rotated Sorted Array II

Follow up for “Search in Rotated Sorted Array”: What if duplicates are allowed?

Would this affect the run-time complexity? How and why?

Write a function to determine if a given target is in the array.

class Solution {
public:
bool search(vector<int>& nums, int target) {
int size=nums.size(),low=0,high=size-1,mid=0;
while(low<=high){
mid=low+(high-low)/2;
if(target==nums[mid])
return true;
if(nums[mid]<nums[high]){
if(target>nums[mid]&&target<=nums[high])
low=mid+1;
else
high=mid-1;
}
else if(nums[mid]>nums[high]){
if(target>=nums[low]&&target<nums[mid])
high=mid-1;
else
low=mid+1;
}
else
high--;
}
return false;
}
};


# 349. Intersection of Two Arrays

Given two arrays, write a function to compute their intersection.

Example: Given nums1 = [1, 2, 2, 1], nums2 = [2, 2], return [2].

Note: Each element in the result must be unique. The result can be in any order.

class Solution {
public:
vector<int> intersection(vector<int>& nums1, vector<int>& nums2) {
unordered_set<int> hash(nums1.begin(),nums1.end());
vector<int> res;
int k=0;
for(int i=0;i<nums2.size();i++){
if(hash.count(nums2[i])){
res.push_back(nums2[i]);
hash.erase(nums2[i]);
}
}
return res;
}
};


# 350.Intersection of Two Arrays II

Given two arrays, write a function to compute their intersection.

Example: Given nums1 = [1, 2, 2, 1], nums2 = [2, 2], return [2, 2].

Note: Each element in the result should appear as many times as it shows in both arrays.

The result can be in any order.

Follow up:

What if the given array is already sorted? How would you optimize your algorithm?

What if nums1’s size is small compared to nums2’s size? Which algorithm is better?

What if elements of nums2 are stored on disk, and the memory is limited such that you cannot load all elements into the memory at once?

[1 2 3 3]
[1 2 3 3 4 5]


class Solution {
public:
vector<int> intersect(vector<int>& nums1, vector<int>& nums2) {
unordered_map<int,int> hash;
vector<int> res;
for(int i=0;i<nums1.size();i++)
hash[nums1[i]]++;
for(int i=0;i<nums2.size();i++){
if(hash.find(nums2[i])!=hash.end()&&--hash[nums2[i]]>=0)
res.push_back(nums2[i]);
}
return res;
}
};


# 154.Find Minimum in Rotated Sorted Array II

154.Find Minimum in Rotated Sorted Array II

Follow up for “Find Minimum in Rotated Sorted Array”: What if duplicates are allowed?

Would this affect the run-time complexity? How and why?

Suppose a sorted array 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).

Find the minimum element.

The array may contain duplicates.

Find Minimum in Rotated Sorted Array I算法的平均时间复杂度为O(log n），而在Find Minimum in Rotated Sorted Array II中，由于有重复元素的存在，那么会对时间复杂度造成影响，在最坏的情况下，比如整个数组由同一个元素组成时，这个算法就不得不一直对high的值进行调整，所以最坏的情况下时间复杂度为O(n）

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