367. Valid Perfect Square

Given a positive integer num, write a function which returns True if num is a perfect square else False.

Note: Do not use any built-in library function such as sqrt.

Example 1:

Input: 16
Returns: True

Example 2:

Input: 14
Returns: False

题目要求我们在不使用sqrt()的情况下对一个数是否是平方数进行判断，那么有了之前实现sqrt()的经验，我们应该能想到这道题是想考察二分查找了，思路很简单，代码如下:

/*use Binary-Search，0ms*/
class Solution {
public:
    bool isPerfectSquare(int num) {
        if(num==0)
            return false;
        long long int low=0,high=num,mid=0;
        while(low<=high){
            mid=low+((high-low)>>1);
            if(mid*mid<num)
                low=mid+1;
            else if(mid*mid>num)
                high=mid-1;
            else if(mid*mid==num)
                return true;
        }
        return false;
    }
};

牛顿迭代应该也能完成，思路见69. Sqrt(x)的代码。

35.Search Insert Position

Given a sorted array and a target value, return the index if the target is found. If not, return the index where it would be if it were inserted in order.

You may assume no duplicates in the array.

Here are few examples.

[1,3,5,6], 5 → 2
[1,3,5,6], 2 → 1
[1,3,5,6], 7 → 4
[1,3,5,6], 0 → 0

典型的Binary-Search，第一版思路是先用Binary-Search，如果没找到，再从最后出发向前遍历直到找到恰好比target大的元素并返回，代码如下:

/*solution1*/
class Solution {
public:
    int searchInsert(vector<int>& nums, int target) {
        if(nums.empty()||target<nums[0])
            return 0;
        int low=0,size=nums.size(),high=size-1,mid=0,i=0;
        while(low<=high){
            mid=low+(high-low)/2;
            if(nums[mid]==target)
                return mid;
            if(nums[mid]>target)
                high=mid-1;
            else
                low=mid+1;
        }
        // if not found,let varible i go back to find an exact position 
        for(i=size;i>=0&&nums[i-1]>target;i--);
        return i;
    }
};

之后又看了一些别人写的代码，发现最后一步向前查找是不必要的，因为Binary-Search的性质是如果最后找不到目标元素，则low指针指向恰好比target大的元素;high指针指向恰好比target小的元素，所以代码可以优化如下:

/*solution2*/
class Solution {
public:
    int searchInsert(vector<int>& nums, int target) {
        if(nums.empty()||target<nums[0])
            return 0;
        int low=0,size=nums.size(),high=size-1,mid=0,i=0;
        while(low<=high){
            mid=low+(high-low)/2;
            if(nums[mid]==target)
                return mid;
            if(nums[mid]>target)
                high=mid-1;
            else
                low=mid+1;
        }
        // if not found
        return low;
    }
};

33.Search in Rotated Sorted Array

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).

You are given a target value to search. If found in the array return its index, otherwise return -1.

You may assume no duplicate exists in the array.

这道题是典型的二分查找，由于没有重复元素，所以我们可以通过中间值和边缘值的大小关系来确定左右两半哪一半是有序的(或者说没有受到rotate的影响)，确定之后，我们可以通过判断target是否存在于这个有序区间，若存在于其中，则在该区间上进行二分查找即可;若不存在，则在另一区间上进行二分查找，简而言之:

1. 若A[mid]<A[high]，则右半边有序，若target存在于此区间,则将low调整到mid+1处;否则，将high调整到mid-1
2. 若A[mid]>=A[high]，则左半边有序，若target存在于此区间，则将high调到mid-1处;否则，将low调整到mid+1处
3. 若A[mid]==target，说明找到，返回

这个算法时间复杂度与Binary Search相同，O(lg n)

代码如下:

class Solution {
public:
    int 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 mid;
            if(nums[mid]<nums[high]){
                if(target>nums[mid]&&target<=nums[high])
                    low=mid+1;
                else
                    high=mid-1;
            }
            else{
                if(target>=nums[low]&&target<nums[mid])
                    high=mid-1;
                else
                    low=mid+1;
            }
        }
        return -1;
    }
};

167. Two Sum II - Input array is sorted

Given an array of integers that is already sorted in ascending order, find two numbers such that they add up to a specific target number.

The function twoSum should return indices of the two numbers such that they add up to the target, where index1 must be less than index2. Please note that your returned answers (both index1 and index2) are not zero-based.

You may assume that each input would have exactly one solution.

Input: numbers=[2, 7, 11, 15], target=9

Output: [1,2]

之前介绍过Two Sum系列问题的解法，这道题只是多出了一个数组已经排好序的条件，所以之前的思路可以继续使用：

1. hash-table
2. two pointers

第一种方法使用hash Table，确定一个数，然后在数组中寻找target与该数的差值即可，代码如下:

/*solution 1 ,use hash-table 8ms*/
class Solution {
public:
    vector<int> twoSum(vector<int>& numbers, int target) {
        if(numbers.empty())
            return {};
        unordered_map<int,int> hash;
        vector<int> res(2,0);
        for(int i=0;i<numbers.size();i++){
            int tmp=target-numbers[i];
            if(hash.find(tmp)!=hash.end()){
                res[0]=hash[tmp]+1;
                res[1]=i+1;
            }
            else
                hash[numbers[i]]=i;
        }
        return res;
    }
};

第二种方法使用双指针，一个指首部一个指尾部，若两个被指向的值的和大于target，则右指针左移，否则左指针右移，代码如下:

/*solution2 two pointers 8ms*/
class Solution {
public:
    vector<int> twoSum(vector<int>& numbers, int target) {
    	int left = 0, right = numbers.size() - 1;
    	vector<int> res;
    	while(left < right){
        	long long val = numbers[left] + numbers[right];
        	if(val == target){
            	res.push_back(left + 1);
            	res.push_back(right + 1);
            	return res; 
        	}
			else if(val < target)
            	left++;
        	else
            	right--;
    	}
    	return res;
	}
};

69. Sqrt(x)

Implement int sqrt(int x).

Compute and return the square root of x.

要求设计一个计算算数平方根的函数，那么我们只需要在0~x的范围内查找，寻找到符合root*root==x的元素，返回即可。

思路比较简单，具体实现有两种方式:

1. 二分查找法
2. 牛顿迭代法

第一种方法比较容易想到，但考虑到这个题要求返回值为int类型，所以我们的循环条件不能是简单的root*root==x,而需要仔细加以考虑，对下面一个序列进行分析:

9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25
3  3  3  3  3  3  3  4  4  4  4  4  4  4  4  4  5

综上我们可以知道当if(x>=root*root&&x<(root+1)*(root+1))时，便应该return (int)root;,具体请见代码，如下:

/*solution1 use binary-search 8ms*/
class Solution {
public:
    int mySqrt(int x) {
        if(x<0)
            return -1;
        int low=0,high=x;
        double root=0;
        while(low<=high){
            root=low+(high-low)/2;
            if(x>=root*root&&x<(root+1)*(root+1))
                return (int)root;
            if(root*root<x)
                low=root+1;
            else
                high=root-1;
        }
        return -1;
    }
};

2.牛顿迭代法

首先看方法的说明:

数学推导很简单，最终得到的递推公式是:

我们用一个last变量记录上一次迭代的结果，res记录每次迭代的新结果，当last和res相等时，则说明精度已经达到我们的要求，返回即可，代码如下:

*solution 2 use Newton's method*/
class Solution {
public:
    int mySqrt(int x) {
        if(x<0)
            return -1;
        if(x==0)
            return 0;
        double last=0,res=1;
        while(res!=last){
            last=res;
            res=(res+x/res)/2;
        }
        return (int)res;
    }
};