演算法導論第二次上課

第一題
第1題: 
O(n^3) , c=4 ,n0=1
第2題: 
O(n^2) , c=3 ,n0=-0.5

第3題：數列被轉置

#include <algorithm>
#include <vector>
#include <map>
class Solution {
public:
    int search(vector<int>& nums, int target) {
        map <int , int > lookfor;
        for(int i =0; i<nums.size(); i++)
            lookfor[nums[i]] = i;
        
    sort(nums.begin(),nums.end());
        int left = 0;
        int right = nums.size()-1;
        int mid;
        while(left<= right)
        {
            mid=(left+right)/2;
            if(nums[mid] < target)
                left = mid +1;
            else if(nums[mid] > target)
                right = mid -1;
            else
                return lookfor[nums[mid]];
        }
    return -1;
    }
};

花費時間:20分鐘 感謝我們最帥的班代教我 YA
第4題：數字可能重複，回傳範圍

    class Solution {
public:
    vector<int> searchRange(vector<int>& nums, int target) {
        if(nums.size()==0)
            return {-1, -1};
        int ll=0;
        int lr = nums.size()-1;
        int lm;
    while (ll <= lr)        
    { lm = (ll+lr)/2;
        if(nums[lm]== target)
            break;
        else if (nums[lm] > target)
            lr = lm - 1;
        else 
            ll = lm +1;
       
     }
        lr = ll = lm;
        if(nums[lm] == target)
        {
        while(ll>=0&&target==nums[ll])//runtime error在這我不懂 順序對調就對了= =
            ll--;
        while(lr<nums.size()&&target==nums[lr])
            lr++;
             return {ll+1,lr-1};
        }
      return {-1,-1};
    }
};

花費時間:1個小時 一直runtime error 把while的條件對調就對了
第5題: 猜數字遊戲

class Solution {
public:
    int guessNumber(long long int n) {//解決測資太大使用long long int
        long long int left = 0;
        long long int right = n;
        long long int target = n/2;
        while(left<=right)//使用上週教的binary search
        {
            target =(left+right)/2;
        if(guess(target)==-1)
            right = target-1;
        else if(guess(target)==1)
            left = target +1;
        else if(guess(target == 0))
            return target;
        }
        return 0;
    }
};

花費時間:15分鐘

心得
---
第6題 :

今天學的複雜度在資料結構中就有提到 有些東西都快忘光了
作業相當有趣 至少坐起來沒有像以前大一的時候這麼崩潰了 應該是自己有在進步吧!