给定一个01串（仅由‘ 0’或‘1’组成的字符串），现在想把这个数字串排序成“非递减”有序序列，请问至少需要多少次交换（任意两个位置交换）？

　　输入描述:

　　输入数据第一行是一个正整数T（T<=100），表示有T组测试数据；

　　接下来的T行，每行给出01串。

　　数据保证：

　　50%的字符串长度在[1,100 ]

　　95%的字符串长度在[1,10000]

　　100%的字符串长度在[1,1000000]

　　输出描述:

　　对于每组测试数据，请输出排成“非递减有序序列”的最小交换次数。

　　每组输出占一行。

　　输入例子:

　　3

　　01

　　10

　　110

　　输出例子:

　　0

　　1

　　1

　　请通过评论说出你的解答。如果有必要，请介绍一下解题思路。在评论中分享解题思路可以让其他人了解你的想法。你的解答帮助了其他人，其他人的解答也将帮助到你。期待大家参与 ^_^

关注「算法爱好者」

看更多名企笔试题与解题讨论

↓↓↓