Exercises II

Easy: 2; Medium: 3; Hard: 1

Search Insert Position

原题链接：https://leetcode.com/problems/search-insert-position/

难度： easy

参考解法：

class Solution {
public:
    int searchInsert(vector<int>& nums, int target) {
        int i=0,site=0;
        while(i<nums.size()){
            if(nums[i]<target) site++;
            i++;
        }
        return site;
    }
};

Binary Search

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

First Bad Version

原题链接：https://leetcode.com/problems/first-bad-version/

难度：easy

参考解答：

Linear search 超时

class Solution {
public:
    int firstBadVersion(int n) {
        int i=0;
        while(i<n){
            if(isBadVersion(i)) break;
            i++;
        }
        return i;
    }
};

Binary search Accepted

class Solution {
public:
    int firstBadVersion(int n) {
        int min=1;
        int max=n;
        while(min<max){
            int mid=min+(max-min)/2;
            if(isBadVersion(mid)){max=mid;}
            else{min=mid+1;}
        }
        return min;
    }
};

Find First and Last Position of Element in Sorted Array

原题链接：https://leetcode.com/problems/find-first-and-last-position-of-element-in-sorted-array/

难度：medium

参考解答：

class Solution {
public:
    vector<int> searchRange(vector<int>& nums, int target) {
    int idx1 = lower_bound(nums, target);
    int idx2 = lower_bound(nums, target+1)-1;
    if (idx1 < nums.size() && nums[idx1] == target)
        return {idx1, idx2};
    else
        return {-1, -1};
    }
    
    int lower_bound(vector<int>& nums, int target) {
        int l = 0, r = nums.size()-1;
        while (l <= r) {
            int mid = (r-l)/2+l;
            if (nums[mid] < target)
                l = mid+1;
            else
                r = mid-1;
        }
        return l;
    }
};

Sum of Mutated Array Closest to Target

原题链接：https://leetcode.com/problems/sum-of-mutated-array-closest-to-target/

难度：medium

题意分析：给定一个数组arr和一个整数target。

给出一个数值value，使其满足在arr中比value大的值改成value之后，arr中数的总和最接近target。

这个value可以是不是数组中的数。

Input: arr = [4,9,3], target = 10

Output: 3

Explanation: When using 3 arr converts to [3, 3, 3] which sums 9 and that's the optimal answer.

Input: arr = [2,3,5], target = 10

Output: 5

Input: arr = [60864,25176,27249,21296,20204], target = 56803

Output: 11361

提示：ternary search/binary search

参考解法：

class Solution {
public:
    int findBestValue(vector<int>& A, int target) {
        sort(A.begin(), A.end());
        int n = A.size(), i = 0;
        while (i < n && target > A[i] * (n - i))
            target -= A[i++];
        return i == n ? A[n - 1] : int(round((target - 0.0001) / (n - i)));
    }
};

Round函数

Returns the integral value that is nearest to x, with halfway cases rounded away from zero.

Binary Search解法：

class Solution {
public:
    int findBestValue(vector<int>& arr, int target) {
        int l, r, mi, s=0, m=-1;
        for(int v:arr) s += v, m=max(m,v);
        
        if(s<=target) return m; // return the max value since we will keep all nums as is

        for(l=1,r=m;l<r;) {
            mi=(l+r)/2;
            s=0;
            for(int v:arr) s += (v>mi)?mi:v;
            if(s>=target) r=mi;
            else          l=mi+1;
        }
        // check if we are 1 step off the target 
        int s1=0,s2=0;
        for(int v:arr) s1 += (v>l)?(l):v, s2 += (v>l-1)?(l-1):v;
        
        return (abs(s2-target) <= abs(s1-target)) ? l-1 : l;
    }
};

Find Minimum in Rotated Sorted Array

原题链接：https://leetcode.com/problems/find-minimum-in-rotated-sorted-array/

难度：medium

参考解法：

class Solution {
public:
    int findMin(vector<int>& nums) {
        int res=INT_MAX;
        for(int n:nums) res=min(n,res);
        return res;
    }
};

Find Minimum in Rotated Sorted Array II

原题链接：https://leetcode.com/problems/find-minimum-in-rotated-sorted-array-ii/

难度：hard

参考解法：