我有n个m位的字符串,每一位都是0或1,现在要求的是指少需要几位我能把他们分辨出来
比如说有2个,011和100,我只需要一位就能分辨出来了。再比如说有4个,111,110,101,011,我就需要3位才能分辨
n最多6,m最多100,求个思路啊
补充一下诶,我可以单独选其中的某几位来分辨的,比如0001和0000我只需要1位就可以分辨了不是4位
把n个字符串,建一棵字母树。树上的每个节点有两个儿子,一个是代表0节点,一个代表1节点,其实你可以把它当成是二叉树,然后建完树后,
遍历二叉树,找二叉树的最大深度,就是答案,时间复杂度为nm
将这些字符串装入字典树,你的问题转换为字典树的度树>1的最大深度。
111110和111111
就是
1-1-1-1-1-0/1
度数>1的最大深度是6
所以是6
你的意思是,假如两个字符串比较,怎么区分,就是看两个字符串里面最少连续几位不同,比如100111 和111111,要2位就行?
把n个字符串先转换为二进制,然后两两异或(找出它们之间不同的位数)。找到n个串中两两最多的不同的位数,就是你要找的最小的判断不同
字符串的位数。