微软第三题没写完,求问这种算法对不对?
最后一题想出了算法没写完,菜是原罪。
有没有AC的大佬帮我看看算法对不对。
--------------------------------
用四位数举例 "abcd" + "dcba" ,四个数位分别是(a+d),(b+c),(c+b),(d+a)。
第一种情况:若(d+a)没有进位,首尾字符应该一致。如果一致,去掉首尾字符继续判断。
第二种情况:若(d+a)有进位,首字符一定是'1'。(如果首尾都是'1'不一定有进位,要考虑两种。比如 5906 + 6095 = 12001 有进位,1090 + 0901 = 1991 无进位。)
有进位的情况,用12001举例。
最末位是1,也就是(a+d) = 11, 12001 - 11000 => 01001, 去掉最高位是"1001",1001 - 11 => 990,去掉末位是"99",然后继续判断"99"。
如果首尾不同而且首位不是'1',一定不满足。
每次可以去掉两个字符,执行到最后字符串长度是0或1。是0的话满足要求;是1的话判断数字的奇偶性,偶数满足要求。
-------------------------
有大佬提醒了另外一种情况,感谢。补充在这里。
首位比末位多1的情况:
比如 580+085 = 665