On the shoulders of giants.

weekly-contest-169

和为零的N个唯一整数

给你一个整数 n,请你返回 任意 一个由 n 个 各不相同 的整数组成的数组,并且这 n 个数相加和为 0

示例 1:

输入:n = 5
输出:[-7,-1,1,3,4]
解释:这些数组也是正确的 [-5,-1,1,2,3],[-3,-1,2,-2,4]。

示例 2:

输入:n = 3
输出:[-1,0,1]

示例 3:

输入:n = 1
输出:[0]

提示:

  • 1 <= n <= 1000
题解

分析对称性即可,具体看代码。

时间复杂度:\(O(n\log n)\)

class Solution {
public:
    vector<int> sumZero(int n) {
        vector<int> result;
        
        if(n & 1) result.push_back(0);
        
        for(int i = 1; i <= n / 2; i++) {
            result.push_back(i);
            result.push_back(-i);
        }
        
        sort(result.begin(), result.end());
        
        return result;
    }
};

两棵二叉搜索树中的所有元素

给你 root1root2 这两棵二叉搜索树。

请你返回一个列表,其中包含 两棵树 中的所有整数并按 升序 排序。.

示例 1:

输入:root1 = [2,1,4], root2 = [1,0,3]
输出:[0,1,1,2,3,4]

示例 2:

输入:root1 = [0,-10,10], root2 = [5,1,7,0,2]
输出:[-10,0,0,1,2,5,7,10]

示例 3:

输入:root1 = [], root2 = [5,1,7,0,2]
输出:[0,1,2,5,7]

示例 4:

输入:root1 = [0,-10,10], root2 = []
输出:[-10,0,10]

示例 5:

输入:root1 = [1,null,8], root2 = [8,1]
输出:[1,1,8,8]

提示:

  • 每棵树最多有 5000 个节点。
  • 每个节点的值在 [-10^5, 10^5] 之间。
题解

暴力做法,遍历两颗树,取出所有元素后排序。

时间复杂度:\(O(n\log n)\)

/**
 * 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:
    vector<int> result;
    
    void dfs(TreeNode* root) {
        if(root == NULL) return;
        result.push_back(root->val);
        dfs(root->left);
        dfs(root->right);
    }
    
    vector<int> getAllElements(TreeNode* root1, TreeNode* root2) {
        dfs(root1);
        dfs(root2);
        
        sort(result.begin(), result.end());
        
        return result;
    }
};

跳跃游戏 III

这里有一个非负整数数组 arr,你最开始位于该数组的起始下标 start 处。当你位于下标 i 处时,你可以跳到 i + arr[i] 或者 i - arr[i]

请你判断自己是否能够跳到对应元素值为 0 的 任意 下标处。

注意,不管是什么情况下,你都无法跳到数组之外。

示例 1:

输入:arr = [4,2,3,0,3,1,2], start = 5
输出:true
解释:
到达值为 0 的下标 3 有以下可能方案: 
下标 5 -> 下标 4 -> 下标 1 -> 下标 3 
下标 5 -> 下标 6 -> 下标 4 -> 下标 1 -> 下标 3 

示例 2:

输入:arr = [4,2,3,0,3,1,2], start = 0
输出:true 
解释:
到达值为 0 的下标 3 有以下可能方案: 
下标 0 -> 下标 4 -> 下标 1 -> 下标 3

示例 3:

输入:arr = [3,0,2,1,2], start = 2
输出:false
解释:无法到达值为 0 的下标 1 处。 

提示:

  • 1 <= arr.length <= 5 * 10^4
  • 0 <= arr[i] < arr.length
  • 0 <= start < arr.length
题解

BFS:每次走到没有走过且能到达的位置,判断该位置下值是否为零。

时间复杂度:\(O(n)\)

class Solution {
public:
    bool canReach(vector<int>& arr, int start) {
        int n = arr.size(), p = start;
        vector<bool> vis(n);
        queue<int> q;
        
        vis[p] = true;
        q.push(p);
        
        while(!q.empty()) {
            int x = q.front(); q.pop();
            if(arr[x] == 0) return true;
            for(int i = -1; i <= 1; i += 2) {
                int dx = x + i * arr[x];
                if(dx < 0 || n <= dx || vis[dx]) continue;
                vis[dx] = true;
                q.push(dx);
            }
        }
        
        return false;
    }
};

口算难题

给你一个方程,左边用 words 表示,右边用 result 表示。

你需要根据以下规则检查方程是否可解:

  • 每个字符都会被解码成一位数字(0 – 9)。
  • 每对不同的字符必须映射到不同的数字。
  • 每个 words[i]result 都会被解码成一个没有前导零的数字。
  • 左侧数字之和(words)等于右侧数字(result)。 

如果方程可解,返回 True,否则返回 False

示例 1:

输入:words = ["SEND","MORE"], result = "MONEY"
输出:true
解释:映射 'S'-> 9, 'E'->5, 'N'->6, 'D'->7, 'M'->1, 'O'->0, 'R'->8, 'Y'->'2'
所以 "SEND" + "MORE" = "MONEY" ,  9567 + 1085 = 10652

示例 2:

输入:words = ["SIX","SEVEN","SEVEN"], result = "TWENTY"
输出:true
解释:映射 'S'-> 6, 'I'->5, 'X'->0, 'E'->8, 'V'->7, 'N'->2, 'T'->1, 'W'->'3', 'Y'->4
所以 "SIX" + "SEVEN" + "SEVEN" = "TWENTY" ,  650 + 68782 + 68782 = 138214

示例 3:

输入:words = ["THIS","IS","TOO"], result = "FUNNY"
输出:true

示例 4:

输入:words = ["LEET","CODE"], result = "POINT"
输出:false

提示:

  • 2 <= words.length <= 5
  • 1 <= words[i].length, results.length <= 7
  • words[i], result 只含有大写英文字母
  • 表达式中使用的不同字符数最大为 10
题解

每一位计算(从低位到高位),即每一位枚举映射,合法后再进行算下一位(注意进位和首位不能为零)。

时间复杂度:\(O(mn!)\) ,\(n\) 为单词个数,\(m=\max \left |word \right |\)

class Solution {
public:
    static const int N = 10, M = 26;
    vector<string> words;
    vector<int> num;
    vector<int> stata[N];
    vector<bool> vis;
    int lim, n;
    int check(int p, int x) {
        int sum = 0, ans = -1;
        for(int i = 0; i < n - 1; i++) {
            int j = (int)words[i].length() - 1 - p;
            if(0 <= j) sum += num[words[i][j] - 'A'];
        }
        int j = (int)words[n - 1].length() - 1 - p;
        if(0 <= j) ans = num[words[n - 1][j] - 'A'];
        return (sum + x) % 10 == ans ? (sum + x) / 10 : -1;
    }
    bool search(int p, int x, int dep) {
        if(p == lim) return true;
        if(stata[p].size() == dep) {
            int num = check(p, x);
            return num == -1 ? false : search(p + 1, num, 0);
        }
        for(int i = 0; i < 10; i++) {
            if(vis[i]) continue;
            bool flag = false;
            if(i == 0) {
                for(auto word : words) { // 首位不能为零,只有一个数字的除外。
                    if(word.length() == 1) continue;
                    int id = word[0] - 'A';
                    if(stata[p][dep] == id) flag = true;
                }
            }
            if(flag) continue;
            num[stata[p][dep]] = i;
            vis[i] = true;
            if(search(p, x, dep + 1)) return true;
            vis[i] = false;
        }
        return false;
    }
    bool isSolvable(vector<string>& words, string result) {
        words.push_back(result);
        this->words.assign(words.begin(), words.end());
        n = words.size();
        for(int i = 0; i < 7; i++) stata[i].clear();
        num.resize(M);
        vis.resize(M, 0);
        for(int i = 0; i < 7; i++) {
            for(auto word : words) {
                if((int)word.length() - 1 - i < 0) continue;
                int id = word[word.length() - 1 - i] - 'A';
                if(vis[id]) continue;
                stata[i].push_back(id);
                vis[id] = true;
            }
        }
        lim = 0;
        for(auto word : words) lim = max(lim, (int)word.length());
        for(int i = 0; i < M; i++) vis[i] = 0;
        return search(0, 0, 0);
    }
};
Share

You may also like...

发表评论

电子邮件地址不会被公开。 必填项已用*标注