讨论/题目交流/🏆 第 169 场力扣周赛/
🏆 第 169 场力扣周赛

欢迎小伙伴们在这里交流分享你的参赛心得以及体验。【前往竞赛

image.png

3 分 - 和为零的N个唯一整数
4 分 - 两棵二叉搜索树中的所有元素
5 分 - 跳跃游戏 III
7 分 - 口算难题

展开讨论

弱鸡我又来写题解了。

今天上线晚了。 接近11点半才来, 导致最后一道题12:08才交, 活该掉分。

题解先。
T1: 和为零的N个唯一整数
构造题。 第一和第二个样例给了不同的构造方式。
我分别给出两种。

  1. 正数为1, 2, 3 ... ,n - 1 为等差数列, 负数为 Σi=1n1\Sigma_{i = 1}^{n - 1}. 注意特判 n == 1的情况;
  2. 分奇数偶数讨论。 奇数中间含0, 剩下每两个数一组互为相反数。 偶数的情况就不要0.

T2: 两棵二叉搜索树中的所有元素
解法一: 非常简单但可以AC。 把两棵树所有点遍历, 然后排序。 时间复杂度 O((n+m)log(n+m))O((n+m)log(n+m))
解法二: 将两棵树中序遍历, 然后就变合并两个有序数组。 时间复杂度 O((n+m))O((n+m))
显然两个都可以过。 某些数据结构的常数不亚于一个log(逃)

T3: 跳跃游戏 III
简单BFS即可。 从初始点开始, 每次遍历最多两个节点。 直到遍历完看是否存在一个点0且在BFS过程中访问到即可。

T4: 口算难题
典型的回溯算法。 理论上时间复杂度为O(10!k)O(10! * k), 其中kk 为每次计算的常数因子, 约等于Σwordsi+result\Sigma |words_i| + |result|. 注意两点。

  1. 首位不能为0
  2. 找到结果后立刻退出回溯
  3. (Optional) 注意回溯顺序。

代码贴上, 2800ms险过(虽然12点多才交)。

class Solution {
public:
    
    int isFirst[26], value[26];
    int letters[26], used[26];
    
    int vis[10];
    
    int wordsToValue(string &words){
        int len = words.length();
        
        int ans = 0;
        for(int i = 0; i < len; i++){
            int cid = words[i] - 'A';
            
            ans = ans * 10 + value[cid];
        }
        
        return ans;
    }
    
    void run(int i, vector<string>& words, string &result, int &ok){
        if(i > letters[0]){
            int sum = 0;
            for(int i = 0; i < words.size(); i++){
                int cur = 0;
                sum += wordsToValue(words[i]);
            }
            
            
            
            int cons = wordsToValue(result);
            
            if(sum == cons) ok = 1;
            
            //printf("%d %d\n",sum, cons);
            
            return;
        }
        
        if(ok)return;
        
        else{
            int cid = letters[i];
            for(int j = 0; j < 10; j++){
                
                if(!vis[j]){
                    if(!isFirst[cid] || (j > 0 && isFirst[cid])){
                        value[cid] = j;
                        vis[j] = 1;
                        run(i+1, words, result, ok);
                        if(ok) break;
                        vis[j] = 0;
                    }
                }
            }
        }
        
        
    }
    
    bool isSolvable(vector<string>& words, string result) {
        int n = words.size();
        int ok = 0;
        
        for(int i = 0; i < n; i++){
            int len = words[i].length();
            for(int j = 0; j < len; j++){
                int cid = words[i][j] - 'A';
                
                if(j == 0){
                    isFirst[cid] = 1;
                }
                
                if(!used[cid]){
                    letters[++letters[0]] = cid;
                    used[cid] = 1;
                }
            }
        }
        
        int len = result.length();
        for(int j = 0; j < len; j++){
                int cid = result[j] - 'A';
                
                if(j == 0){
                    isFirst[cid] = 1;
                }
                
                if(!used[cid]){
                    letters[++letters[0]] = cid;
                    used[cid] = 1;
                }
            }
        
        printf("%d\n", letters[0]);
        
        run(1, words, result, ok);
        
        return ok == 1;
    }
};

感谢各位批评指正。 如果有更优的算法欢迎讨论。

展开全部 17 讨论