演算法作業02

第1題

$O(n^3)$ ,

$c=4$ ,

$n_0=2$

第2題

$O(n^2)$ ,

$c=30$ ,

$n_0=3$

第3題：數列被轉置

1. 解題思路

先用二分搜找最大值座標，再用二分搜找target

2. 程式碼

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

3. 測試輸出輸入的畫面截圖

4. 花費時間

20分鐘

5. 完成程度

完全自己解出

第4題：數字可能重複，回傳範圍

1. 解題思路

先把nums大小為0的解決，
再找到第一個大於等於target的座標，
再判斷是否為target的值，如果不是就是[-1,-1]
再找到第一個大於target的座標。

2. 程式碼

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

3. 測試輸出輸入的畫面截圖

4. 花費時間

15分鐘

5. 完成程度

完全自己解出

第5題：猜數字遊戲

1. 解題思路

分成三種情況二分搜
-1:縮右界
1:縮左界
0:回傳答案

2. 程式碼

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

3. 測試輸出輸入的畫面截圖

4. 花費時間

5分鐘

5. 完成程度

完全自己解出

第6題：找出正數或負數的數量較大者

1. 解題思路

第一個二分搜：找出第一個大於0的
第二個二分搜：找出第一個大於等於0的
然後就能算了

2. 程式碼

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

3. 測試輸出輸入的畫面截圖

4. 花費時間

21分鐘

5. 完成程度

完全自己解出

第7題：心得

已填