Weekly Contest 169

5295. Find N Unique Integers Sum up to Zero

class Solution {
public:
    vector<int> sumZero(int n) {
        vector<int> ret;
        if(n == 1) return {0};
        if(n == 0) return {0};
        int flag = n%2==0 ? 1 : 0;
        if(flag == 1){
            for(int i=0; i<n; i+=2){
                ret.push_back(i+1);
                ret.push_back((i+1)*(-1));
            }
        }else {
            int t = n-3;
            int i=0;
            for(; i<t; i+=2){
                ret.push_back(i+1);
                ret.push_back((i+1)*(-1));
            }
            ret.push_back(i+2);
            ret.push_back(i+3);
            ret.push_back((2*i+5)*(-1));
        }
        return ret;
    }
};

5296. All Elements in Two Binary Search Trees

/**
 * 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:
    void inorder(TreeNode* root, vector<int>& con){
        if(!root) return;
        if(root->left) inorder(root->left, con);
        con.push_back(root->val);
        if(root->right) inorder(root->right, con);
    }
    vector<int> getAllElements(TreeNode* root1, TreeNode* root2) {
        vector<int> r1;
        vector<int> r2;
        inorder(root1, r1);
        inorder(root2, r2);
        int i=0;
        int j=0;
        vector<int> ret;
        while(i<r1.size() && j<r2.size()){
            if(r1[i] < r2[j]) ret.push_back(r1[i++]);
            else ret.push_back(r2[j++]);
        }
        while(i<r1.size()) ret.push_back(r1[i++]);
        while(j<r2.size()) ret.push_back(r2[j++]);
        return ret;
    }
};

5297. Jump Game III

class Solution {
public:
    bool dfs(vector<int>& arr, int start, vector<int>& visited){
        if(arr.size() == 1 && start >=0 && start < arr.size()) return arr[0]==0;
        if(start < 0 || start >= arr.size() || visited[start] == 1) return false;
        if(arr[start] == 0) return true;
        visited[start] = 1;
        return dfs(arr, start-arr[start], visited)||dfs(arr, start+arr[start], visited);
    }
    bool canReach(vector<int>& arr, int start) {
        vector<int> visited(arr.size(), 0);
        return dfs(arr, start, visited);
    }
};

5298. Verbal Arithmetic Puzzle

class Solution {
    vector<vector<char>> lefts;
    vector<char> rights;
    unordered_map<char, int> map;
    unordered_set<int> used;
    bool check(int level, int idx, int sum) {
		// last check
        if (level >= rights.size()) {
			// check left length is larger than right
            if (level < lefts.size()) {
                return false;
            }
			// check leading zeros
            for (char ch : lefts.back()) {
                if (map[ch] == 0) {
                    return false;
                }
            }
            if (map[rights.back()] == 0) {
                return false;
            }
            return sum == 0;
        }
        //check equality at the end of each level, level < rights.size();
        if (level >= lefts.size() || idx >= lefts[level].size()) {
            char ch = rights[level];
            bool add = false;
            if (map.find(ch) == map.end()) {
				// try map right character
                if (used.count(sum % 10) > 0) {
                    return false;
                } else {
                    used.insert(sum % 10);
                    map[ch] = sum % 10;
                    add = true;
                }
            } else if (map[ch] != sum % 10) {
                return false;
            }
            if (check(level + 1, 0, sum / 10)) {
                return true;
            } else {
                if (add) {
					// reset mapping
                    used.erase(sum % 10);
                    map.erase(ch);
                }
                return false;
            }
        }
        char ch = lefts[level][idx];
        if (map.find(ch) != map.end()) {
			// this left character is already mapped
            return check(level, idx + 1, sum + map[ch]);
        }
        for (int i = 0; i <= 9; i++) {
			// enumerate to map left character
            if (used.count(i) > 0) {
                continue;
            }
            map[ch] = i;
            used.insert(i);
            if (check(level, idx + 1, sum + i)) {
                return true;
            }
            map.erase(ch);
            used.erase(i);
        }
        return false;
    }
public:
    bool isSolvable(vector<string>& words, string result) {
        int levels = 0;
        for (const string &str : words) {
            levels = max(levels, (int)str.length());
        }
        for (int level = 0; level < levels; level++) {
            lefts.emplace_back();
            for (const string &str : words) {
                if (level < str.length()) {
                    lefts[level].push_back(str[str.length() - level - 1]);
                }
            }
        }
        for (int i = result.length() - 1; i >= 0; i--) {
            rights.push_back(result[i]);
        }
        return check(0, 0, 0);
    }
};