阿里4.1笔试第一题
因为小弟也要参加笔试了,所以搜罗了一下最近的笔试题。
看到一题挺有意思的,也写个解法
问题:
题目:给一串二进制字符串如00011001,希望把他改为全为0,如果更改某个字符,那么他两边的字符也要更改,例如把第二位的0换成1,那么就变成了11111001.
如果无法变为全0,那么返回NO
想法:
找规律,最左边一位一定是1.这个关键,如果是1的话,那么左2位,就有2种选择,{翻,不翻}或者{不翻,翻},不妨假设为{翻,不翻}
循环每一位,由于该位是0还是1已知,左两位情况已知,那么后一位翻不翻就知道了。
这样循环到最后一位,按同样的方法,如果发现矛盾了,那么将前面所有位反号,就可以啦
另外,只有一种情况无解,即“10”。
input_str = "111111" n = len(input_str) op = [0 for i in range(n)] # 假设为{翻,不翻} op[0] = 0 op[1] = 1 for i in range(1, n): # 1, ..., n-1 # 循环,推导出下一步是啥 if i != n-1: op[i+1] = (int(input_str[i])-(op[i]+op[i-1])) % 2 # 最后一步单独判断 if i == n-1: # 看是不是match if (int(input_str[i])-(op[i]+op[i-1])) % 2 == 0: break # 如果不match else: # 前n-1位反号 for j in range(0, n-1): if op[j] == 0: op[j] = 1 elif op[j] == 1: op[j] = 0 # 填最后一位 op[i] = (int(input_str[i])-op[i-1]) % 2 # 打完收工 print(op)