有个算法题，有没有人能提出好点算法

badyun

题目是一段数字只包含0，1，2

其中2代表0或者1

随机输入这样的一串数字，把其中的2替换成0或者1，要求输出所有可能的结果

比如

输入：121，返回101和111

输入：122，返回100，101，111，110

需要用算法实现输入任意长度的012，返回所有的可能

摸鱼怪

不懂，感谢楼主的cb

平淡最真

先计算2的个数，记录位置。然后总的可能性就是000...000-111...111   这不就是2进制吗     从小往大一个一个写出来。然后把原本的0和1插回去

badyun

平淡最真 发表于 2021-10-31 19:01
先计算2的个数，记录位置。然后总的可能性就是000...000-111...111   这不就是2进制吗     从小往大一个一 ...

要求性能尽可能高。我自己的算法用了三个循环，感觉还能优化

wihn

用两个位来表示0~2，逢三进一，依次输出
0000,0001,0010,0100..........
用二进制的两位模拟三进制
行不行？

wihn

wihn 发表于 2021-10-31 19:27
用两个位来表示0~2，逢三进一，依次输出
0000,0001,0010,0100..........
用二进制的两位模拟三进制

需要一个大循环，每次需要取余运算

搜索曾经的回忆

典型dfs递归算法吧

hate

ruby递归，性能，一般吧

[Ruby] 纯文本查看 复制代码

str = "0211112"

def concat(char, chars)
    if chars.size == 0
        return char == '2' ? ['0', '1'] : [char]
    end

    if char == '2'
        return concat('0', chars) + concat('1', chars)
    end
    
    concat(chars[0], chars[1..-1]).map do |str|
        char + str
    end
end

puts concat(str.chars[0], str.chars[1..-1])

kesai

好久不写不太会了，O(∩_∩)O哈哈~，都不知道对不对了，哎，老了

[Python] 纯文本查看 复制代码

s='122'
res=[]
for c in s:
    if not res:
        res=[c] if c!='2' else ['0','1']
    else:
        res=list(map(lambda x:x+c,res)) if c!='2' else list(map(lambda x:x+'0',res))+list(map(lambda x:x+'1',res))
print(res)

往事随风不苦涩

kesai 发表于 2021-10-31 20:28
好久不写不太会了，O(∩_∩)O哈哈~，都不知道对不对了，哎，老了
[mw_shl_code=python,true]s='122'
res= ...

可不可以试试构建二叉树，逢2就分叉，然后遍历由根节点到所有叶子节点的路径。