tags: Weekly Contest

Weekly Contest 132

1025. Divisor Game (Easy)

限制 :

• 1 <= n <= 1000

時間複雜度:

$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 (Medium)

限制 :

• The number of nodes in the tree is in the range [2, 5000].
• 0 <= Node.val <= 105

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(Medium)

限制 :

• 2 <= nums.length <= 1000
• 0 <= nums[i] <= 500

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(Hard)

限制 :

• The number of nodes in the original tree is in the range [1, 1000].
• 1 <= Node.val <= 109

Solution

• 參考至這個影片
• 這題是要從一個含有紀錄的字串，轉換回一顆 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];
    }
};