演算法作業07

第1題: 2-D Maxima Finding Problem

這個題目與解法，與第2章介紹的2-D Ranking Finding Problem相似。請比較此兩個問題與其解法，有何相同與相異之處。

相同之處：

一樣是切分成左右邊、也是切成一個一個再合併。

相異之處：

• 主要是合併方式
  • 2-D Maxima Finding 是把左邊比右邊的最大值小的直接砍掉，右邊不會受到影響。
  • 2-D Ranking Finding 是幫右邊加上左邊的值，左邊不會被修改到。

若將此問題，由2-D延伸到3-D，請你嘗試設計出一個解法。

想法1

我一開始想的是先把點按照某一軸離散化給出順序，
這樣有一個軸已經固定了，就轉換成2-D的問題了。

當然這是需要排序的

$O(NlogN)$
整體還是

$O(NlogN)$
所以我想說應該可行

想法2

另一個想法是一樣用合併的，

合併上就是由兩邊一個一個去比對，但目前只想到

$O(N^2)$
有點糟糕

第一步是合併綠色紅色
第二步是合併藍色橘色
第三步是合併綠紅跟藍橘
這樣可以變成一個完整的一整塊

想法1複雜度比較好一點，但我好想找到D&C解

第2題: Closest Pair Problem

請說明Closest Pair Problem，每回合的合併過程？(可參考PPT13頁)

左半部

$(x=L-d\to L)\mathrm{的}\mathrm{每}\mathrm{一}\mathrm{個}\mathrm{點}，\mathrm{跟}\mathrm{右}\mathrm{半}\mathrm{部}\mathrm{在}\mathrm{那}\mathrm{個}\mathrm{長}\mathrm{方}\mathrm{形}$(x=L\to L+d,y=y_p-d \to y_p-d)$裡面的做比較，
如果找到比

$d$小的

$d^{\prime }$就去做更新

第3題: Convex Hull Problem

請說明Convex Hull Problem，

(1)為何不直接用sort來得到polygon，而要採用merge？

把角度取出來sort之後時間會是

$O(NlogN)$，太久了，
但如果原本就是有順序的節點，直接merge，

$O(N)$(應該)就可以了

(2)請說明如何將polygon，修改成convex hull？

一個一個檢查，如果形成角度超過180度，就把它刪除

第4題: 將linked list的數列排序

解題思路

就是很簡單的把值取出來排序再丟回去
用merge的話，比較討厭的就是長度的部分跟ListNode要做一次開一次
有點麻煩，考慮到時間問題我就選擇實作簡單的方法，以後再補merge

程式碼

/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode() : val(0), next(nullptr) {}
 *     ListNode(int x) : val(x), next(nullptr) {}
 *     ListNode(int x, ListNode *next) : val(x), next(next) {}
 * };
 */
class Solution {
public:
    ListNode* sortList(ListNode* head) {
        ListNode* ans= new ListNode();
        ListNode* p=new ListNode();
        p->next=ans;
        vector<int> v;
        while(head!=NULL)
        {
            v.push_back(head->val);
            head=head->next;
        }
        sort(v.begin(),v.end());
        for(int i=0;i<v.size();i++)
        {
            ans->next=new ListNode(v[i],NULL);
            ans=ans->next;
        }
        return p->next->next;
    }
};

測試輸出輸入的畫面截圖

花費時間

15分鐘

完成程度

完全自己解出

第5題: 將排序好的數列轉為二元搜尋樹

解題思路

簡單的切半遞迴
分成三種情況

1. nums.size()>=2，代表可以再切，所以把中間的節點放好之後就可以切成左右子樹
2. nums.size()==1，代表已經到尾端了，並且把剩下的那個數字放進節點
3. nums.size()==0，代表已經到尾端了，而且因為沒東西，所以回傳NULL

不過這是我第一次在leetcode寫遞迴，讚喔

程式碼

/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode() : val(0), left(nullptr), right(nullptr) {}
 *     TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
 *     TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
 * };
 */
class Solution {
public:

    TreeNode* sortedArrayToBST(vector<int>& nums) {
        cout<<endl;
        TreeNode* ans=new TreeNode();
        if(nums.size()==1)
        {
            ans->val=nums[0];
            return ans;
        }
        else if(nums.size()==0)
        {
            return NULL;
        }
        ans->val=nums[nums.size()/2];
        vector<int> l(nums.begin(),nums.begin()+nums.size()/2);
        vector<int> r(nums.begin()+nums.size()/2+1,nums.end());
        ans->left=sortedArrayToBST(l);
        ans->right=sortedArrayToBST(r);
        return ans;
    }
};

測試輸出輸入的畫面截圖

花費時間

15分鐘

完成程度

完全自己解出

第6題： 美麗數列

解題思路

我想了一小時還是出不來
上面是我想的過程的圖，很明顯我的方向錯了
所以我直接問同學大概怎麼寫

結果同學說用奇數偶數生成的方法
我就：「歐歐歐歐歐歐歐歐歐」
%%% 就出來ㄌ

作法1
從1開始
把陣列

$a$的每個值

$a_i$取出來加入

$2\times a_i-1$(這邊是奇數)存到tmp
把陣列

$a$的每個值

$a_i$取出來

$2\times a_i$(這邊是偶數)存到tmp
tmp就會是奇數在前偶數在後，而且長度是

$a$的兩倍
再把a設成tmp
再把

$a_i>n$的處理掉就可以了

$O(NlogN)$

作法2
王于桐大電神aka王卷桐提出用遞迴切左右邊
也是

$O(NlogN)$
間單來說就是把它會撞到中間那個值的部分通通丟到一側
這樣就可以避免被撞到

註：撞到是指a[i]+a[j]==a[k]*2

小想法:
因為作法2可以分左右
照理來說會按照二進位獲得左右移的方向
所以也許有公式解可以解掉這題
能夠把時間複雜度變成O(N)
也許而已，還沒想到

程式碼1

class Solution {
public:
    vector<int> beautifulArray(int n) {
        vector<int> a={1};
        int i;
        while(a.size()<n)
        {
            vector<int> tmp;
            for(i=0;i<a.size();i++) if((a[i]<<1)-1<=n) tmp.push_back((a[i]<<1)-1);
            for(i=0;i<a.size();i++) if((a[i]<<1)<=n) tmp.push_back((a[i]<<1));
            a=tmp;
        }
        return a;
    }
};

程式碼2

class Solution {
public:
    void d(vector<int> &a,int l,int r)
    {
        if(l==r)
        {
            return;
        }
        vector<int> tmp(r-l+1,0);
        int x=(r-l)>>1,i,j;
        for(i=l,j=0;i<=r;i+=2,j++)
        {
            tmp[j]=a[i];
        }
        for(i=l+1,j=((r-l)>>1)+1;i<=r;i+=2,j++)
        {
            tmp[j]=a[i];
        }
        for(i=l,j=0;i<=r;i++,j++)
        {
            a[i]=tmp[j];
        }
        d(a,l,((r-l)>>1)+l);
        d(a,(((r-l)>>1)+1)+l,r);
    }
    vector<int> beautifulArray(int n) {
        vector<int> a;
        for(int i=1;i<=n;i++)
        {
            a.push_back(i);
        }
        d(a,0,n-1);
        return a;
    }
};

測試輸出輸入的畫面截圖

花費時間

60+7+30

完成程度

詢問同學/討論後，了解後解出

心得

已填