问答

我竟然连题目都看不懂,这算法难吗?

作者:admin 2021-07-19 我要评论

给你一个方程,左边用?words?表示,右边用?result 表示。 你需要根据以下规则检查方程是否可解: 每个字符都会被解码成一位数字(0 - 9)。 每对不同的字符必须...

在说正事之前,我要推荐一个福利:你还在原价购买阿里云、腾讯云、华为云服务器吗?那太亏啦!来这里,新购、升级、续费都打折,能够为您省60%的钱呢!2核4G企业级云服务器低至69元/年,点击进去看看吧>>>)

给你一个方程,左边用?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

###

就是让你尝试分配不同数字到等式中出现的字符上以使得等式成立,例如第一个例子:

   SEND |    9567
+  MORE | +  1085
------- | -------
= MONEY | = 10652

如果找到了分配方式,则返回 true,否则返回 false.


这道题我想不出来用编程的方法解决,只能用解数独一样的方法去看了:

仅针对 SEND + MORE = MONEY 这个例子:

// 四种情况
// 1. S、M 处于 [0, 5] 所以不会产生进位;
// 2. S、M 处于 (5, 9] 所以会产生进位;
// 3. S、M 本身相加不会进位,但可能因为 E + O > 10 导致进位.
// 4. S、M 本身相加已经进位,又由于 E + O > 10 导致结果加一,所以取它们本身相加的值时需要退回 1.

S + M = O | 10 + O | O - 1 | 10 + O - 1

// 又由题面可知,S + M = MO,显然只能对应情况 3,4
// 无论哪种情况,显然 M 都为 1. 

S + 1 = 10 + O | 10 + O - 1

// 化简可得

S = 9 + O | 8 + O => S - O = 9 | 8

// 注意题意:所有字母都会分配唯一的数字,且落在 [0, 9] 内,1 已经被分配给了 M,所以此处不可能出现 S - O = 8 的情况 (10 - 2 或 9 - 1). 因此 S - O = 9,即 9 - 0 = 9.

// 所以,M = 1, S = 9, O = 0
// 此时 9END + 10RE = 10NEY.
// 即 E + 0 = N | N - 1,但 E 不可能等于 N,所以 E = N - 1 即 N - E = 1.
// 可能的情况有:8 - 7, 7 - 6, 6 - 5, 5 - 4, 4 - 3
// 又由于 N + R = E | 10 + E | E - 1 | 10 + E -1
// 所以代入 N - E = 1 后可得

// N + R = N - 1 | 10 + N - 1 | N - 1 - 1 | 10 + N - 1 - 1
// 分别化简可得
// R = -1 ×
// R = 9 ×
// R = -2 ×
// R = 8 √

// 所以,M = 1, S = 9, O = 0, R = 8
// 此时 9END + 108E = 10NEY

// 由于 N + 8 = 10 + E - 1, 所以 D + E = 10 + Y.
// 由已求得条件可知 Y 必等于 2(剩余数字没有能组合出 13 的情况),那么 D + E = 12,可能的组合有:
// * 7 + 5 = 12
// * 5 + 7 = 12

//再因为 N - E = 1 可能的组合有:
// * 7 - 6
// * 6 - 5

// 显然 E 只能取 5,那么 N 即为 6,D 即为 7
// 所以可得 M = 1, S = 9, O = 0, R = 8, E = 5, N = 6, D = 7, Y = 2

上面这串东西我也不知道怎么写成代码,仅供参考.

###

因为数字只允许0-9,所以左右字母加起来不会超过10个,
最简单的算法就是10重循环,如下:

int used[10] = { -1 }
for (i0=0;i0<10;i0++)
{
    used[0] = i0;
    for (i1=0;i1<10;i1++)
    {
        if (used 里面已经有了 i1)
            continue;
        used[1] = i1;
        for (i2=0;i2<10;i2++)
        {
            if (used 里面已经有了 i2)
                continue;
            used[2] = i2;
            ...
                for (i9=0;i9<10;i9++)
                {
                    if (used 里面已经有了 i9)
                        continue;
                    if (字母替换的等式成立)
                        return 字母替换组合
                }
         }
    }
}

这是不考虑效率,最简单粗暴的实现。

版权声明:本文转载自网络,遵循 CC 4.0 BY-SA 版权协议,转载请附上原文出处链接和本声明。本站转载出于传播更多优秀技术知识之目的,如有侵权请联系QQ/微信:153890879删除

相关文章
  • 我竟然连题目都看不懂,这算法难吗?

    我竟然连题目都看不懂,这算法难吗?

  • 关于 async await的问题

    关于 async await的问题

  • antd Table排序问题

    antd Table排序问题

  • eslint 如何检查指定文件夹下的.js,.vu

    eslint 如何检查指定文件夹下的.js,.vu

腾讯云代理商
海外云服务器