# 演算法作業 HW07
## 第一題
## 第二題
## 第三題
## 第四題
### 螢幕通過畫面
### 程式碼

/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode(int x) : val(x), next(NULL) {}
 * };
 */
class Solution {
public:
    ListNode* sortList(ListNode* head) {
        if (!head || !head->next) {
            return head;
        }
        ListNode* slow = head;
        ListNode* fast = head->next;
        while (fast && fast->next) {
            slow = slow->next;
            fast = fast->next->next;
        }
        ListNode* mid = slow->next;
        slow->next = nullptr;
        ListNode* left = sortList(head);
        ListNode* right = sortList(mid);
        return merge(left, right);
    }
    
    ListNode* merge(ListNode* left, ListNode* right) {
        ListNode* dummy = new ListNode(0);
        ListNode* cur = dummy;
        while (left && right) {
            if (left->val < right->val) {
                cur->next = left;
                left = left->next;
            } else {
                cur->next = right;
                right = right->next;
            }
            cur = cur->next;
        }
        cur->next = left ? left : right;
        ListNode* res = dummy->next;
        delete dummy;
        return res;
    }
};

### 解題思路
如果為空或是只有一個節點，則直接回傳。
然後利用快慢指針找到中點，將鏈表一分為二，對左右兩個鏈表進行merge sort，最後合併兩個鏈表。
### 花費時間
約半天，其中花費大量時間去複習物件導向...
### 自己完成的比例
半數由自己完成，但最後還是沒辦法解出
## 第五題
### 螢幕通過畫面
### 程式碼

/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode(int x) : val(x), left(NULL), right(NULL) {}
 * };
 */
class Solution {
public:
    TreeNode* sortedArrayToBST(vector<int>& nums) {
        return buildBST(nums, 0, nums.size() - 1);
    }
    
    TreeNode* buildBST(vector<int>& nums, int left, int right) {
        if (left > right) {
            return nullptr;
        }
        int mid = left + (right - left) / 2;
        TreeNode* root = new TreeNode(nums[mid]);
        root->left = buildBST(nums, left, mid - 1);
        root->right = buildBST(nums, mid + 1, right);
        return root;
    }
};

### 解題思路
透過二分法建立一顆平衡的二元搜尋樹，對於有序陣列，中間元素可以作為根節點，左半部分遞歸構建左子樹，右半部分遞歸構建右子樹。

buildBST（） 函數用於遞歸構建平衡二叉搜索樹，當左右指標相遇時遞歸結束，返回 nullptr，否則計算中間元素的位置，創建根節點，遞歸構建左子樹和右子樹，最後返回根節點。
### 花費時間
一小時左右
### 自己完成的比例
全部由自己完成
## 第六題
### 螢幕通過畫面
### 程式碼

class Solution {
public:
    vector<int> beautifulArray(int n) {
        vector<int> res = {1};
        while (res.size() < n) {
            vector<int> temp;
            for (int i : res) {
                if (2 * i - 1 <= n) {
                    temp.push_back(2 * i - 1);
                }
            }
            for (int i : res) {
                if (2 * i <= n) {
                    temp.push_back(2 * i);
                }
            }
            res = temp;
        }
        return res;
    }
};

### 解題思路
將美麗陣列分成兩部分，分別是奇數部分和偶數部分，然後將奇數部分和偶數部分分別構建成美麗數位，最後將兩部分合併。
### 花費時間
約半小時
### 自己完成的比例
ChatGPT教我
## 心得
這次不管是教學影片的觀念部分，或是程式題部分，難度均有所提升，花費了比較多的時間去複習以前學過的觀念，還有吸收現階段的觀念