50. Pow(x, n)

Implement pow(x, n).

根据经验,题干越简单的题目,坑越多。

题目要求我们实现一个计算pow()函数,这个函数是用来计算乘方的。题目中没有给出n的范围,我们姑且按照实数范围对其进行考虑。

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

于是第一版代码在经过修改之后通过了,因为是数值计算题,会涉及很多的corner case,代码中有很多if语句来对边界条件进行判断,代码如下:

/*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;
    }
};

正是由于一大堆的条件判断,这个算法很慢。因此,在参考了讨论区之后,我发现了用二分法解决这个问题。

要求x^n,可以求x^(n/2)*x^(n/2),于是,我们就有了用二分法解决问题的思路,代码如下:

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.

这道题就是一道简单的二分查找,本身是没有什么难度的,但是却被这道题卡了很久,原因是它提供的API的说明实在是充满了歧义。

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

第一次提交是按照第一种方式理解的,结果出现了错误,让我感到很不可思议,因为仔细检查过后发现二分查找算法本身应该是没有问题的,后来我尝试互换了中间值大于目标值和中间值小于目标值 两种情况下对low,high指针的处理,获得了Accept。

所以,由此可见,提供准确而无歧义的API文档是多么重要。

代码如下:

// 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

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.

这是上面那道题的后续题目,这次出现了重复元素,不过出现了重复元素,主要思路没有变化,还是通过寻找有序区间并判断target是否存在于这个区间来调整low,high两个指针的位置。

但是这次有重复元素了,所以A[mid]和A[high]的大小关系并不能成为我们判断左半边还是右半边有序的条件了,比如给出数组{1,2,3,3,3,3,3},旋转之后可能是{3,3,3,3,3,1,2}或者{3,1,2,3,3,3,3},这样,我们仅凭中间值和边缘值的大小关系是不能判断出哪边有序的,所以解决方案是如果中间值和边缘值相等,则high–然后判断中间值和新的边缘值的关系。

注意这里移动high指针会造成算法时间复杂度的变化,最坏的情况就是整个数组都由一个数字组成,那就要移动到low=high为止,也就是算法时间复杂度从O(lg n)变成了O(n)

代码如下:

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.

要求返回两个元素的相同部分,因为不需要考虑重复元素的问题,所以没什么难度,用hash-table可以很快解决问题,代码如下:

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]

要求返回[1,2,3,3]

依然采用hash算法,只不过要记录每个元素在nums1数组中出现的次数,代码如下;

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;
    }
};

下面考虑follow up:

如果是给出两个排好序的数组,那么从头往后扫一遍对比元素值就可以解决了。

剩下两个容我再想想…………

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系列的第二题,和这个系列的第一题的思路相近,就是寻找在rotate之后依然有序的部分,但是这次有可能会出现nums[mid]==nums[high]的情况,之前处理过Search in Rotated Sorted Array II问题,当出现这种情况时,应该对high的值-1,然后继续判断。

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];
    }
};