LeetCode Weekly Contest 132

Problem list:

• Divisor Game
• Maximum Difference Between Node and Ancestor
• Longest Arithmetic Sequence
• Recover a Tree From Preorder Traversal

1025. Divisor Game

Problem

Alice and Bob take turns playing a game, with Alice starting first.

Initially, there is a number N on the chalkboard. On each player's turn, that player makes a move consisting of:

• Choosing any x with 0 < x < N and N % x == 0.
• Replacing the number N on the chalkboard with N - x.

Also, if a player cannot make a move, they lose the game.

Return True if and only if Alice wins the game, assuming both players play optimally.

Example 1:

Input: 2
Output: true
Explanation: Alice chooses 1, and Bob has no more moves.

Example 2:

Input: 3
Output: false
Explanation: Alice chooses 1, Bob chooses 1, and Alice has no more moves.

Note:

1. 1 <= N <= 1000

https://leetcode.com/contest/weekly-contest-132/problems/divisor-game/

Solution

The first though was "dynamic programming"...

class Solution {
public:
    bool divisorGame(int N) {
        vector<bool> v(N + 1);
        for (int i = 0; i < N; i++) {
            if (!v[i]) {
                for (int j = 1; i + j <= N && j < i + j; j++)
                    if ((i + j) % j == 0)
                        v[i + j] = 1;
            }
        }
        return v[N];
    }
};

Is this an easy one? Yes… Then I found that we just need to check if the given number is even or not.

class Solution {
public:
    bool divisorGame(int N) {
        return N % 2 == 0;
    }
};

Proof:

Firstly, we can prove that the one who gets input 3 will lose the game.

Consider if N is odd, Alice can only have an odd x, which makes N-x even for Bob. Bob choose whatever an odd number to give another odd number to Alice. Keep going like this, Alice will finally be given a 3, she then loses the game.

Consider if N is even, she can play this trick to win the game.

1026. Maximum Difference Between Node and Ancestor

Problem

Given the root of a binary tree, find the maximum value V for which there exists different nodes A and B where V = |A.val - B.val| and A is an ancestor of B.

(A node A is an ancestor of B if either: any child of A is equal to B, or any child of A is an ancestor of B.)

Example 1:

img

Input: [8,3,10,1,6,null,14,null,null,4,7,13]
Output: 7
Explanation: 
We have various ancestor-node differences, some of which are given below :
|8 - 3| = 5
|3 - 7| = 4
|8 - 1| = 7
|10 - 13| = 3
Among all possible differences, the maximum value of 7 is obtained by |8 - 1| = 7.

Note:

1. The number of nodes in the tree is between 2 and 5000.
2. Each node will have value between 0 and 100000.

https://leetcode.com/contest/weekly-contest-132/problems/maximum-difference-between-node-and-ancestor/

Solution

My first try used two nested recursions.

/**
 * 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:
    int V = -1;
    int maxAncestorDiff(TreeNode* root) {
        getMaxV(root);
        return V;
    }
    void getMaxV(TreeNode* node) {
        if (node != NULL) {
            int val = node->val;
            calcMaxV(val, node->left);
            calcMaxV(val, node->right);
            getMaxV(node->left);
            getMaxV(node->right);
        }
    }
    void calcMaxV(int val, TreeNode* node) {
        if (node != NULL) {
            int v = abs(node->val - val);
            if (v > V) {
                V = v;
            }
            calcMaxV(val, node->left);
            calcMaxV(val, node->right);
        }
    }
};

Actually one depth-first search is enough (by keeping the max and min value):

/**
 * 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:
  int V = -1;
  int maxAncestorDiff(TreeNode* root) {
    dfs(root, root->val, root->val);
    return V;
  }
  void dfs(TreeNode *node, int mn, int mx) {
    if (node != NULL) {
      mn = min(mn, node->val);
      mx = max(mx, node->val);
      V = max(V, max(mx - node->val, node->val - mn));
      f(node->left, mn, mx);
      f(node->right, mn, mx)
    }
  }
};

1027. Longest Arithmetic Sequence

Problem

Given an array A of integers, return the length of the longest arithmetic subsequence in A.

Recall that a subsequence of A is a list A[i_1], A[i_2], ..., A[i_k] with 0 <= i_1 < i_2 < ... < i_k <= A.length - 1, and that a sequence B is arithmetic if B[i+1] - B[i] are all the same value (for 0 <= i < B.length - 1).

Example 1:

Input: [3,6,9,12]
Output: 4
Explanation: 
The whole array is an arithmetic sequence with steps of length = 3.

Example 2:

Input: [9,4,7,2,10]
Output: 3
Explanation: 
The longest arithmetic subsequence is [4,7,10].

Example 3:

Input: [20,1,15,3,10,5,8]
Output: 4
Explanation: 
The longest arithmetic subsequence is [20,15,10,5].

Note:

1. 2 <= A.length <= 2000
2. 0 <= A[i] <= 10000

https://leetcode.com/contest/weekly-contest-132/problems/longest-arithmetic-sequence/

Solution

The idea is to keep track of two numbers as the first two elements in the sequence using two nested for loop, and then use another for loop interating from the next number to check how many numbers match this sequence:

class Solution {
public:
    int longestArithSeqLength(vector<int>& A) {
        int longest = 0;
        for (int i = 0; i < A.size(); i++) {
            for (int j = i + 1; j < A.size(); j++) {
                int diff = A[j] - A[i];
                int matched = 2;
                for (int k = j + 1; k < A.size(); k++) {
                    if (A[k] - A[i] == diff * matched) {
                        matched++;
                    }
                }
                longest = max(longest, matched);
            }
        }
        return longest;
    }
};

1028. Recover a Tree From Preorder Traversal

Problem

We run a preorder depth first search on the root of a binary tree.

At each node in this traversal, we output D dashes (where D is the depth of this node), then we output the value of this node. (If the depth of a node is D, the depth of its immediate child is D+1. The depth of the root node is 0.)

If a node has only one child, that child is guaranteed to be the left child.

Given the output S of this traversal, recover the tree and return its root.

Example 1:

Input: "1-2--3--4-5--6--7"
Output: [1,2,5,3,4,6,7]

Example 2:

Input: "1-2--3---4-5--6---7"
Output: [1,2,5,3,null,6,null,4,null,7]

Example 3:

img

Input: "1-401--349---90--88"
Output: [1,401,null,349,88,90]

Note:

• The number of nodes in the original tree is between 1 and 1000.` `
• Each node will have a value between 1 and 10^9.

https://leetcode.com/contest/weekly-contest-132/problems/recover-a-tree-from-preorder-traversal/

Solution

I didn't attempt to do this one. Found this optimal solution in comments:

/**
 * 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* recoverFromPreorder(string S) {
        stack<TreeNode*> s;
        int i = 0;
        while (i < S.size()) {
            int value = 0, level = 0;
            while (i < S.size() && S[i] == '-') {
                ++level;
                ++i;
            }
            while (i < S.size() && S[i] != '-') {
                value = value * 10 + S[i] - '0';
                ++i;
            }
            while (s.size() > level) {
                s.pop();
            }
            auto node = new TreeNode(value);
            if (!s.empty() && !s.top()->left) {
                s.top()->left = node;
            } else if (!s.empty()) {
                s.top()->right = node;
            }
            s.push(node);
        }
        TreeNode* ret;
        while (!s.empty()) {
            ret = s.top();
            s.pop();
        }
        return ret;
    }
};