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

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

image.png

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

展开讨论

来贴一个 5298. 口算难题 的题解

因为字母解码的过程中,数字与字母满足一一映射的关系,所以可能的映射关系最多只有 10!10! 种。如果给定一个字母-数字的映射关系,能 O(1)O(1) 检查是否满足题目中的方程,那么问题就解决了。

为了能够 O(1)O(1) 检查,考虑预处理每个字母对方程左式与右式的贡献,设方程左式等于 leftleft,右式等于 rightright
用题目的第一个样例 words = ["SEND","MORE"], result = "MONEY" 来举例。
我们知道 :

left=(1000S+100E+10N+D)+(1000M+100O+10R+E)right=10000M+1000O+100N+10E+Y\begin{aligned} left &= (1000\cdot S +100\cdot E + 10\cdot N + D) + (1000\cdot M +100\cdot O + 10\cdot R + E) \\ right &= 10000\cdot M + 1000\cdot O +100\cdot N + 10\cdot E + Y \end{aligned}

如果从字母贡献的角度来看,可以得到另一种等价的计算方法:

left=1000S+101E+10N+1D+1000M+100O+10R+0Yright=0S+10E+100N+0D+10000M+1000O+0R+1Y\begin{aligned} left &= 1000\cdot S +101\cdot E + 10\cdot N + 1\cdot D + 1000\cdot M +100\cdot O + 10\cdot R + 0\cdot Y \\ right &= 0\cdot S +10\cdot E + 100\cdot N + 0\cdot D + 10000\cdot M +1000\cdot O + 0\cdot R + 1\cdot Y \end{aligned}

如果我们可以预处理出每一个字母对于 left,rightleft, right 的贡献权值,那么一旦确定了一个字母对应的数值,就可以计算出它对于 left,rightleft, right 的贡献并加入其中。当确定完所有数字对应的数值之后,left,rightleft, right 也能随之确定了,就能直接 O(1)O(1) 检查了。

所以,先预处理出上段所介绍的贡献权值,然后使用一个 DFS 枚举字母与数字的对应关系,DFS 的过程中维护 left,rightleft, right 的值并在终点检查。

class Solution {
public:
    bool canZero[26];
    int left[15], right[15], numc;
    map<char, int> toIndex;
    bool vis[15];
    
    void calcWeight(const string &s, int arr[]){
        int n = s.length(), w = 1;
        for (int i = n - 1; i >= 0; i--){
            arr[toIndex[s[i]]] += w;
            w *= 10;
        }
    }
    
    bool dfs(int cur, int n, int l, int r){
        if (cur > n){
            // if (l == r) printf("%d\n", l);
            return l == r;
        }
        
        for (int i = 0; i <= 9; i++){
            if (canZero[cur] == false && i == 0) continue;
            if (vis[i]) continue;
            vis[i] = true;
            bool flag = dfs(cur + 1, n, l + i * left[cur], r + i * right[cur]);
            if (flag) return true;
            vis[i] = false;
        }
        return false;
    }
    
    bool isSolvable(vector<string>& words, string result) {
        numc = 0; toIndex.clear();
        for (auto w: words) for (auto c: w){
            if (toIndex[c] == 0) toIndex[c] = ++numc;
        }
        for (auto c: result){
            if (toIndex[c] == 0) toIndex[c] = ++numc;
        }
        
        for (int i = 0; i < 26; i++) canZero[i] = true;
        canZero[toIndex[result[0]]] = false;
        for (auto w: words) canZero[toIndex[w[0]]] = false;
        
        memset(left, 0, sizeof(left));
        memset(right, 0, sizeof(right));
        calcWeight(result, right);
        for (auto w: words) calcWeight(w, left);
        
        memset(vis, false, sizeof(vis));
        return dfs(1, numc, 0, 0);
    }
};
5
展开全部 17 讨论