方法一:蛮力法 最容易想到的方法就是对这个给定的数加1,然后判断这个数是不是“不重复数”,如果不是,则继续加1,直到找到“不重复数”为止。显然这种方法的效率非常低下。
方法二:从右到左的贪心法 例如给定数字11099,首先对这个数字加1,变为11000,接着从右向左找出第一对重复的数字00,对这个数字加1,变为11001,继续从右向左找出下一对重复的数00,将其加1,同时把这一位往后的数字变为0101…串(当某个数字自增后,只有把后面的数字变成0101…,才是最小的不重复数字),这个数字变为11010,接着采用同样的方法,11010->12010就可以得到满足条件的数。
需要特别注意的是当对第i个数进行加1操作后可能会导致第i个数与第i+1个数相等,因此,需要处理这种特殊情况,下图以99020为例介绍处理方法。
(1)把数字加1并转换为字符串。
(2)从右到左找到第一组重复的数99(数组下标为i=2),然后把99加1,变为100,然后把后面的字符变为0101…串,得到100010。
(3)由于执行(2)后对下标为2的值进行了修改,导致它与下标为i=3的值相同,因此,需要对i自增变为i=3,接着从i=3开始从右向左找出下一组重复的数字00,对00加1变为01,后面的字符变为0101…串,得到100101。
(4)由于下标为i=3与i+1=4的值不同,因此,可以从i-1=2的位置开始从右向左找出下一组重复的数字00,对其加1就可以得到满足条件的最小的“不重复数”。
根据这个思路给出实现方法如下:
1)对给定的数加1。
2)循环执行如下操作:对给定的数从右向左找出第一对重复的数(下标为i),对这个数字加1,然后把这个数字后面的数变为0101…得到新的数。如果操作结束后下标为i的值等于下标为i+1的值,则对i进行自增,否则对i进行白减;然后从下标为i开始从右向左重复执行步骤2),直到这个数是“不重复数”为止。
实现代码如下:
package main
import(
"strcony"
"fmt"
)
//处理数字相加的进位
func carry(num[]rune, pos int){
for; pos>0; pos--{
if num[pos]>'9'{
num[pos]='0'
num[pos-1]++
}
}
}
//获取大于n的最小不重复数
func findMinNonDupNum1(n int)int{
count:=0//用来记录循环次数
mRune:=[]rune(strconv.Itoa(n+1))
ch:=make([]rune, len(mRune)+2)
ch[0]='0'
ch[len(ch)-1]='0'
fori:=0; i<len(mRune); i++{
ch[i+1]=mRune[i]
}
ll:=len(ch)
i:=ll-2//从右向左遍历
for i>0{
count++
if ch[i-1]==ch[i]{
ch[i]++//末尾数字加1
carry(ch, i)//处理进位
//把下标为i后面的字符串变为0101…串
forj:=i+1; j<ll; j++{
if (j-i)%2==1{
ch[j]='0'
}else{
ch[j]='1'
}
}
//第i位加1全,可能会与第i+1位相等,i++用来处理这种情况
i++
}else{
i--
}
}
fmt.Println("循环次数为:", count)
result,_:=strconv.Atoi(string(ch))
return result
}
func main(){
fmt.Println("从右到左的贪心法")
fmt.Println(findMinNonDupNum1(23345))
fmt.Println(findMinNonDupNum1(1101010))
fmt.Println(findMinNonDupNum1(99010))
fmt.Println(findMinNonDupNum1(8989))
}
程序的运行结果为
循环次数为:7
23401
循环次数为:11
1201010
循环次数为:13
101010
循环次数为:10
9010
方法三:从左到右的贪心法 与方法二类似,只不过是从左到右开始遍历,如果碰到重复的数字,则把其加1,后面的数字变成0101…串。实现代码如下:
package main
import (
"strconv"
"fmt"
)
//处理数字相加的进位
func carry(hum []rune, pos int){
for; pos>0; pos-- {
if num[pos]>'9' {
num[pos]='0'
num[pos-1]++
}
}
}
func findMinNonDupNum2(n int)int{
count:=0//用来记录循环次数
mRune:=[]rune(strconv.Itoa(n+ 1))
ch:=make([]rune, len(mRune)+2)
ch[0]='0'
ch[len(ch)-1]='0'
fori:=0; i<len(mRune); i++ {
ch[i+l]=mRune[i]
}
ll:=len(ch)
i:=2//从左向右遍历
for i<ll {
count++
if ch[i-1]==ch[i] {
ch[i]++//末尾数字加1
carry(ch, i)//处理进位
//把下标为i后面的字符串变为0101…串
forj:=i+1; j<ll; j++{
if (j-i)%2==1 {
ch[j]='0'
}else{
ch[j]='1'
}
}
}else{
i++
}
}
fmt.Println("循环次数为:", count)
result,_:=strconv.Atoi(string(ch))
return result
}
func main(){
fmt.Println("从左到右的贪心法")
fmt.Println(findMinNonDupNum2(23345))
fmt.Println(findMinNonDupNum2(1101010))
fmt.Println(findMinNonDupNum2(99010))
fmt.Println(findMinNonDupNum2(8989))
}
显然,方法三循环的次数少于方法二,因此,方法三的性能要优于方法二。