阿里 2020-04-01笔试 第一题 （Python）
回忆下题目：给一个二进制串s，只由0和1组成。可以选择任意位置进行翻转，同时该位置的左边1位和右边1位也会跟着一起翻转。所谓翻转就是0变1，1变0。问能不能通过翻转使这个二进制串全部变成0？能的话输出最少的操作次数，不能的话输出“NO”。
（考试时没写出来，当时一直在想怎么用动态规划，最后10分钟突然想到应该用搜索，但是来不及写了，哭唧唧......）
-
翻转唯一性：每个位置要么不翻，要不只翻一次，不会有两次翻转操作选择了相同的位置（试想，同一个位置翻转2次相当于不翻，翻转3次相当于只翻一次）
-
顺序无关性：k次翻转后的结果与操作顺序无关
理解这两个性质之后，我们可以发现，如果字符长度为n，那最多可以被翻转n次，每个位置可以选择 翻 或者 不翻，所以即使遍历的话，也只有 2^n 种情况。
（由此可以想到：深度优先搜索，广度优先搜索， ...）
用一棵二叉树来表示我的解法：从第0层开始，往左表示翻转第0个位置，往右表示不翻转第0个位置，进入到下一层......依次，在第 i 层，往左表示翻转第 i 个位置，往右表示不翻转第 i 个位置......直到找到答案后停止；找不到则返回False。在搜索的过程中用count记录翻转次数。
翻转的时候巧用位运算：我们希望把1变成0，把0变成1，这时候可以和1做 “异或”运算：
-
0^1 = 1
-
1^1 = 0
代码如下：
import copy
def reverse(s_l, idx):
'''
和1取 异或 可实现取反： 0^1=1, 1^1=0
'''
s_l_copy = copy.deepcopy(s_l)
s_l_copy[idx] = s_l_copy[idx]^1
if idx > 0: #注意左边界
s_l_copy[idx-1] = s_l_copy[idx-1]^1
if idx < len(s_l_copy)-1: #注意右边界
s_l_copy[idx+1] = s_l_copy[idx+1]^1
return s_l_copy
def solution(s):
'''
两个重要性质：（1）顺序无关性 （2）翻转唯一性
每个位置只有两种可能性：1.不翻，2.翻且仅翻一次，
所以最多只能翻 n 次，其中 n=len(s)，
遍历的话也只有 2^n 种情况。
'''
s_l = [int(x) for x in s]
n = len(s_l)
if sum(s_l) == 0:
return 0
def recursion(cur_s_l, idx, count):
'''
cur_s_l: 当前字串的样子
idx: 翻转到第几位了，也就是现在在第几层了
count: 当前已经翻转了几次了
'''
#print(idx, '--'*(idx+1), cur_s_l, count) #打印出树的样子
if sum(cur_s_l) == 0:
return count
if idx == n:
return False
# 往左，表示在第idx位置进行翻转，idx往后挪一位，翻转次数count+1
# 往右，表示在第idx位置不进行翻转，idx往后挪一位，翻转次数count不变
return recursion(reverse(cur_s_l, idx), idx+1, count+1) or recursion(cur_s_l, idx+1, count)
return recursion(s_l, 0, 0)
print(solution('01')) #False
print(solution('011')) #1
print(solution('0111111')) #2
可惜笔试的时候并没有做出来，凉凉......😭😭😭
投递莉莉丝游戏等公司7个岗位 >