Secretary to Mystic Studio [Mystic Studio]
The algorithm sent yesterday did not take into account one situation, for example, after adding one, the situation of repeated numbers appeared again. After correction, the algorithm was sent again today.
For example, if YOU put in 99, then B should be 101 because 100 has two consecutive equal zeros.
The worst way to do this is to add 1 and keep adding 1 until you find something that doesn’t repeat.
Interview: If this is an interview question, check with the interviewer to see if the number A ranges, such as decimals and negative numbers, etc. So we’re going to make it positive here.
Optimization idea:
If there is no repetition of the input number itself, increment 1; If there are duplicates, for example 11100234, and if we want to find the smallest number that is not repeated more than 11100234, the first two-digit number that is repeated is 11, then if we want 11 to be repeated more than 11100234, we should add 1 to the second digit to 12100234. And then to keep the number as small as possible, I’m going to zero all the numbers after the 2, which is 12,000 million; And then you start at 2 and you start at 0 and you start at 0 and you start at 01; So it’s 12010101. Note here: if the change is followed by a round, it needs to be processed again, such as 199, after the first processing becomes 200,200 is still repeated, it needs to be processed again.
# -*- coding: utf-8 -*-
Enter A number A and find the smallest number B that is greater than A and that does not have two consecutive equal numbers. For example, if you type 99, then B should be 101 because 100 has two consecutive equivalent zeros: The worst way Add 1 plus 1 until found so far have not repeat number Optimization of the train of thought If the input is after 1099 plus 1 into 1100, so not to repeat the number of his next if have add 1 efficiency will be low, this is the point can be optimized If this problem in the interview, with the interviewer to confirm good, the scope of the number of A Whether there are decimals or whether there are negative numbers, and so on. So here we're going to make it positive. """
def get_data(num):
If num=4, return 10000 args: the number of zeros needed.
data = 1
while num > 0:
data = data * 10
num = num - 1
return data
def get_tail(num, data):
Args :num = 345 args:num = 345 args:num =3
list_data = []
Num = 0
head = get_data(num)
Get the last bits by erasing them
need_data = data % head
return need_data
def judge(data):
Args :data number args:data number
i = 1
while i < len(data):
# check if two numbers are equal
if string_num[i- 1] == string_num[i]:
return True
i = i + 1
return False
if __name__ == "__main__":
# Number entered
num = 1099
num = num + 1
# number to string, to determine if there are equal numbers
string_num = str(num)
i = 1
flag = 0
while True:
if(judge(string_num)==False) :break
while i < len(string_num):
# check if two numbers are equal
if string_num[i- 1] == string_num[i]:
# if there is a duplicate digit, add 1 to the smallest digit and 0 to the next digit
new_len = len(string_num) - i - 1
num = num + get_data(new_len)
tail = get_tail(new_len, num)
# is set to 0 by subtracting the following number of digits from num
num = num - tail
string_num = str(num)
flag = 1
# set 0 and look for the next few digits to find the minimum number that does not repeat
i = i + 1
# if flag=0 proves that there are no duplicates, then exit
if flag == 0:
num = num + 1
string_num = str(num)
# if flag=0 and the last bit is computed
if flag == 1 and i >=len(string_num):
# check if there is a repeat, if there is no recalculation, stop
if(judge(string_num)):
i = 0
flag = 0
continue
else:
break
print string_num
Copy the code1099 output is: 1201; 99 output is: 101; 9 The output is: 10; 1098 output is: 1201
For more algorithm content, please pay attention to the subscription number “Vernacular algorithm:
Python algorithms and data structures — maximizing the sum of all subarrays
Turn the search tree into a bidirectional list
Excellent algorithm tutorial recommended