FB onsite 挂经 非典型coding

翻滚吧豆子 发表于 2017-5-20 13:24
给的提示非常有意义，比如 sum = A + A'
A'是A去掉任意一位。那么可以看成是两部分相加：
sum = (A1 +  ...

why not divide by 11,110,1100,11000,....

leonxxx 发表于 2017-5-20 13:38
why not divide by 11,110,1100,11000,....

能给出你具体的方法吗？

翻滚吧豆子 发表于 2017-5-20 13:45
能给出你具体的方法吗？

it has multiple answers.

say 43763+4363=48126;
44063+4063
43813+4313

my thoughts is

divided 11; see if it can abcd+abc;
divided 110; see if can abcd+abd
divided by 1100, see if can abcd+acd;
etc.

leonxxx 发表于 2017-5-20 14:15
it has multiple answers.

say 43763+4363=48126;

嗯嗯，我觉得可行，和我的想法基本一样。要想想怎么处理
abcd+acd 而cd+cd进位的情况

dlf1601 发表于 2017-5-20 13:30
再请教一下，第一题copy on write class是考thread safe吗？
是不是这样就行了？。。

- -我觉得你这个有点不对劲。。。。
java的string都是不能修改的，所以按这么每次write，即便你不费这功夫，他也是会new 一个对象

这道题我猜测肯定要上StringBuffer或者StringBuilder或者char[]

翻滚吧豆子 发表于 2017-5-20 16:07
- -我觉得你这个有点不对劲。。。。
java的string都是不能修改的，所以按这么每次write，即便你不费这功 ...

用char[] buffer在write的时候也是先copy一份出来再在copy的那份上write吧， 把a指向新的obj, b还是指向老的obj

dlf1601 发表于 2017-5-21 03:52
用char[] buffer在write的时候也是先copy一份出来再在copy的那份上write吧， 把a指向新的obj, b还是指向 ...

但是你要记住有多少个reference啊。
如果对string a只有一个引用，然后这时候要修改，那我直接就在原地改了，不用复制

n2是n1少一位digit，输入s=n1 + n2, 求(n1, n2)的可能解

123456
   ^
   e
^^^ ^^
h   t

e为去掉的digit
h为前缀
t为后缀

s = 2 * t + (11 * h + e) * 10^r
= 2 * t + e * 10^r + h * 11 * 10^r

注意2 * t < 10^r, 0 <= e <= 9

尝试不同的r
h = s / (11 * 10^r)
e * 10^r + 2 * t = s % (11 * 10 ^ r)
e = (s % (11 * 10 ^ r)) / 10 ^ r
t = ((s % (11 * 10 ^ r)) % 10 ^ r) / 2

复杂度log(s)

1. def findn1n2(s):
   
2.     if s < 10: return [(s, 0)]
   
3.     rec = set()
   
4.     r = 0
   
5.     while s / (11 * 10 ** r):
   
6.         h = s / (11 * 10 ** r)
   
7.         m = s % (11 * 10 ** r)
   
8.         e = m / (10 ** r)
   
9.         t = (m % (10 ** r)) / 2
   
10.         n1 = h * 10 ** (r + 1) + e * 10 ** r + t
    
11.         n2 = h * 10 ** r + t
    
12.         rec.add((n1, n2))
    
13.         r += 1
    
14.     return list(rec)
    
15. 
    
16. print findn1n2(2) #[(2, 0)]
    
17. print findn1n2(39) #[(36, 3)]
    
18. print findn1n2(1246) #[(1133, 113), (1123, 123)]

复制代码

liliphy 发表于 2017-5-21 06:49
n2是n1少一位digit，输入s=n1 + n2, 求(n1, n2)的可能解

123456

兄弟你这个挺好，貌似就是有个case没考虑，低位相加有可能进位的
比如
输入1346，应该输出
1224, 122
1223, 123
1218,     128
1173,     173
但你这个只输出了
[(1223, 123), (1224, 122)]

翻滚吧豆子 发表于 2017-5-21 07:04
兄弟你这个挺好，貌似就是有个case没考虑，低位相加有可能进位的
比如
输入1346，应该输出

说的没错，我重新考虑了一下

1. def findn1n2(s):
   
2.     if s < 10: return [(s, 0)]
   
3.     rec = set()
   
4.     base = 1
   
5.     while s / (11 * base):
   
6.         h = s / (11 * base)
   
7.         m = s % (11 * base)
   
8.         e = 0
   
9.         while e * base <= m:
   
10.             if (m - e * base) % 2 == 0 and (m - e * base) / 2 < base:
    
11.             t = (m - e * base) / 2
    
12.             n1 = h * 10 * base + e * base + t
    
13.             n2 = h * base + t
    
14.             rec.add((n1, n2))
    
15.         e += 1
    
16.     base *= 10
    
17.     return list(rec)
    
18. 
    
19. print findn1n2(2) #[(2, 0)]
    
20. print findn1n2(39) #[(36, 3)]
    
21. print findn1n2(1246) #[(1073, 173), (1133, 113), (1123, 123), (1128, 118)]
    
22. print findn1n2(1346) #[(1218, 128), (1173, 173), (1224, 122), (1223, 123)]
    

复制代码