# 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

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

# 35.Search Insert Position

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

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

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

# 33.Search in Rotated Sorted Array

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.

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，说明找到，返回

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]

1. hash-table
2. two pointers

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

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

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

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

/*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.牛顿迭代法

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