###### tags: `Weekly Contest`
# Weekly Contest 132

## [1025. Divisor Game](https://leetcode.com/problems/divisor-game/) (<font color=#00B8A3>Easy</font>)

限制 :

<ul>
<li><code>1 <= n <= 1000</code></li>
</ul>
### Solution

#### 時間複雜度: $O(N)$

#### 空間複雜度: $O(1)$

程式碼:

class Solution {
public:
    bool divisorGame(int n) {
        bool isAlice = false;
        while (true) {
            int temp = n;
            for (int i = 1; i < n; i++) {
                if (temp % i == 0) {
                    temp = temp - i;
                    isAlice = !isAlice;
                    break;
                }
            }
            if (n == temp)
                return isAlice;
            else 
                n = temp;
        }
    }
};

## [1026. Maximum Difference Between Node and Ancestor](https://leetcode.com/problems/maximum-difference-between-node-and-ancestor/) (<font color=#FFC011>Medium</font>)

限制 :
<ul>
<li><code>The number of nodes in the tree is in the range [2, 5000].</code></li>
<li><code>0 <= Node.val <= 10⁵</code></li>
</ul>

### Solution

#### 時間複雜度: $O(log(N))$

#### 空間複雜度: $O(log(N))$

程式碼:

class Solution {
public:
    int findValue(TreeNode* root, int maxNum, int minNum) {
        maxNum = max(maxNum, root->val);
        minNum = min(minNum, root->val);
        int result = maxNum - minNum;
        if(root->left == nullptr && root->right == nullptr) {
            return result;    
        }
        int leftValue = INT_MIN;
        int rightValue = INT_MIN;
        if(root->left ) 
            leftValue = findValue(root->left, maxNum, minNum);
        if(root->right ) 
            rightValue = findValue(root->right, maxNum, minNum);
        result = max(result, leftValue);
        result = max(result, rightValue);
        return result;

    }
    int maxAncestorDiff(TreeNode* root) {
        return findValue(root, INT_MIN, INT_MAX);
    }
};

## [1027. Longest Arithmetic Subsequence](https://leetcode.com/problems/longest-arithmetic-subsequence/)(<font color=#FFC011>Medium</font>)

限制 :

<ul>
<li><code>2 <= nums.length <= 1000</code></li>
<li><code>0 <= nums[i] <= 500</code></li>
</ul>

### Solution
這題要找的是找到最長的 subsequence ，符合等差數列。
由於這題的長度不長，所以直接暴力解就好。

#### 時間複雜度: $O(N^3)$

#### 空間複雜度: $O(1)$

程式碼:

class Solution {
public:
    int longestArithSeqLength(vector<int>& nums) {
        int maxLen = 0;
        for (int i = 0; i < nums.size(); i++) {
            for (int j = i + 1; j < nums.size(); j++) {
                int d = nums[j] - nums[i];
                int l = 2;
                int nowNum = nums[j];
                for (int k = j + 1; k < nums.size(); k++) {
                    if (nums[k] == nowNum + d) {
                        nowNum = nums[k];
                        l++;
                    }
                }
                maxLen = max(maxLen, l);
            }
        }
        return maxLen;
    }
};

## [1028. Recover a Tree From Preorder Traversal](https://leetcode.com/problems/recover-a-tree-from-preorder-traversal)(<font color=#FF375F>Hard</font>)

限制 :

<ul>
<li><code>The number of nodes in the original tree is in the range [1, 1000].
</code></li>
<li><code>1 <= Node.val <= 10⁹
</code></li>
</ul>

### Solution
- 參考至[這個影片](https://youtu.be/QRSDXF8ZrmE?si=CBDneq_KTffy_tKG)
- 這題是要從一個含有紀錄的字串，轉換回一顆 binary tree。字串內容分別有"-"和阿拉伯數字，"-"代表的是後面阿拉伯數字所在的level，阿拉伯數字則代表這個 node 的數值。
- 在這裡由於題目所使用的是DFS，traversal 的順序是 中->左->右節點。我們要用這個特性來建立一個 stack ，方便我們替node找到合適的位置
- 演算法的過程：對每一個的"-X"的一串數字做處理，重新回復成數字和層數，再利用 stack 找到自己的父節點，駔後再存放進去。
#### 時間複雜度: $O(n)$

#### 空間複雜度: $O(n)$

程式碼:

class Solution {
public:
    // 利用 stk 把樹的其中一部份記起來
    // 因為下一個數字與前面數字有子樹的關係，而且左子樹一定先。所以 stk
    // 可以很方便 traversal。 注意因為是 DFS，所以這方法才可以用。
    TreeNode* recoverFromPreorder(string traversal) {
        vector<TreeNode*> stk;
        for (int i = 0, level, val; i < traversal.size();) {
            for (level = 0; traversal[i] == '-'; i++) {
                level++;
            }
            for (val = 0; i < traversal.size() && traversal[i] != '-'; i++) {
                val = val * 10 + traversal[i] - '0';
            }

            TreeNode* node = new TreeNode(val);
            // 找到和上面數字的父 node
            while (stk.size() > level)
                stk.pop_back();
            if (stk.size() > 0)
                if (stk.back()->left == nullptr)
                    stk.back()->left = node;
                else
                    stk.back()->right = node;
            stk.push_back(node);
        }
        return stk[0];
    }
};