Python思考练习题1_GOOGLE面试题（已公开答案）

大头目

玩法申明（借鉴每日一题）：

1. 楼主看情况提供答案（有可能是自己做不出，但觉得很好的题目）
2. 请大家先独立思考，再参考其他鱼油的解答，这样才有助于自己编程水平的提高。开始阶段是看不到其他人的回帖的，等答题完成，过几天后取消限制。
3. 鼓励大家积极答题，但楼主囊肿羞涩大部分情况无法奖励大家，除非遇到楼主非常想知道答案的题目或者代码写得很好且有说明注释的答案。
4. 纯属娱乐，大家如果希望知道题目出处的可以私聊我，互相推荐好书，交流看书心得。

题目：
由一组字母组成的等式：WWWDOT - GOOGLE = DOTCOM
每个字母可以用数字0~9代替
每组字母开头不等于0
所有字母对应的数字都是唯一的，也就是W=1的话，其他字母就不能=1

求出替换后的数字能够满足等式，据说这是GOOGLE公司的面试题，但从无考证。

附加要求：
算法时间越短越好

grf1973

l=0
for w in range(2,10):
        for g in range(1,w):
                for d in [w-g,w-g-1]:
                        for t in range(1,10):
                                if t!=w and t!=g and t!=d:
                                        for e in range(t):   #t>e
                                                m=t-e
                                                c=d-g if d>g else 10+d-g
                                                for o in [t+1,t-1]:
                                                        res=[l,w,g,d,t,e,m,c,o]
                                                        if len(set(res))==9:
                                                                if eval('%d%d%d%d%d%d-%d%d%d%d%d%d' %(w,w,w,d,o,t,g,o,o,g,l,e))==eval('%d%d%d%d%d%d'%(d,o,t,c,o,m)):
                                                                        print('%d%d%d%d%d%d-%d%d%d%d%d%d=%d%d%d%d%d%d' %(w,w,w,d,o,t,g,o,o,g,l,e,d,o,t,c,o,m))

结果有两个
777589-188103=589486
777589-188106=589483
[Finished in 0.1s]

RIXO

想了俩小时，猝

塔利班

from itertools import permutations
for each in permutations(range(10),9):
    w,d,o,t,g,l,e,c,m=each
    if w<3 or not g or not d or w<=g:
        continue
    else:
        A=w*111000+d*100+o*10+t
        B=g*100100+o*11000+l*10+e
        C=d*100000+o*10010+t*1000+c*100+m
        if A==B+C:
            print(A,B,C)
            break

大头目

塔利班 发表于 2018-9-29 16:36

答案不止一个

大头目

给上我又臭又长的答案，新手比较容易看懂

import time
t1 = time.clock()
for w in range(3,10):
        for g in range(1,10):
                if g == w:
                        pass
                else:
                        for d in range(1,10):
                                if d == g or d == w:
                                        pass
                                else:
                                        for o in range(0,10):
                                                if o == d or o == g or o == w:
                                                        pass
                                                else:
                                                        for t in range(0,10):
                                                                if t == o or t == d or t == g or t == w:
                                                                        pass
                                                                else:
                                                                        for l in range(0,10):
                                                                                if l == t or l == o or l == d or l == g or l == w:
                                                                                        pass
                                                                                else:
                                                                                        for e in range(0,10):
                                                                                                if e == l or e == t or e == o or e == d or e == g or e == w:
                                                                                                        pass
                                                                                                else:
                                                                                                        for c in range(0,10):
                                                                                                                if c == e or c == l or c == t or c == o or c == d or c == g or c == w:
                                                                                                                        pass
                                                                                                                else:
                                                                                                                        for m in range(0,10):
                                                                                                                                if m == c or m == e or m == l or m == t or m == o or m == d or m == g or m == w:
                                                                                                                                        pass
                                                                                                                                else:
                                                                                                                                        x = w * 100000 + w * 10000 + w * 1000 + d * 100 + o * 10 + t
                                                                                                                                        y = g * 100000 + o * 10000 + o * 1000 + g * 100 + l * 10 + e
                                                                                                                                        z = d * 100000 + o * 10000 + t * 1000 + c * 100 + o * 10 + m

                                                                                                                                        if x - y == z:
                                                                                                                                                print(x,'-',y,'=',z)
t2 = time.clock()
print(t2-t1)

大头目

grf1973 发表于 2018-9-28 16:59
l=0
for w in range(2,10):
        for g in range(1,w):

逻辑看不懂，腻害，不过答案是对的！

塔利班

大头目 发表于 2018-9-30 14:26
答案不止一个

嗯，那就把break去掉就好了
我以为都是唯一的，答案也是唯一的

grf1973

大头目 发表于 2018-9-30 14:29
逻辑看不懂，腻害，不过答案是对的！

就是枚举+剪枝啦。比如w肯定大于1，O-L=O-->L=0,[O,T]=[W-O,W-O]-->abs(O-T)=1,W-G=D-->D=W-G or W-G-1等等等等

grf1973

4楼代码加一点小的剪枝，可以快很多
from itertools import permutations
for each in permutations(range(1,10),8):
    w,d,o,t,g,e,c,m=each
    if w<3 or w<=g:
        continue
    else:
        A=w*111000+d*100+o*10+t
        B=g*100100+o*11000+e
        C=d*100000+o*10010+t*1000+c*100+m
        if A==B+C:
            print("%d-%d=%d" %(A,B,C))

grf1973

显然L=0，T>E，M=T-E，据此还可以剪枝，速度又提高一倍。

from itertools import permutations
for each in permutations(range(1,10),7):
    w,d,o,t,g,e,c=each
    if w<3 or w<=g or t<=e:
        continue
    else:
            m=t-e
            if m in each:
                    continue
            A=w*111000+d*100+o*10+t
            B=g*100100+o*11000+e
            C=d*100000+o*10010+t*1000+c*100+m
            if A==B+C:
                print("%d-%d=%d" %(A,B,C))

翩跹叶惊鸿

grf1973 发表于 2018-9-28 16:59
l=0
for w in range(2,10):
        for g in range(1,w):

for o in [t+1,t-1]:

请问为什么 o 只能等于 t+1 或 t-1 ？

grf1973

翩跹叶惊鸿 发表于 2018-9-30 23:06
for o in [t+1,t-1]:

请问为什么 o 只能等于 t+1 或 t-1 ？

因为公式里有两个相同的W-O，一个结果是O，一个结果是T。简单枚举一下就可以知道abs(o-t)=1，所以o=t+1或者o=t-1