Numeric Keypad

Hello everyone , I meet you again , I'm your friend, Quan Jun .

Title Description

The numberic keypad on your mobile phone looks like below: 123 456 789 0 suppose you are holding your mobile phone with single hand. Your thumbpoints at digit 1. Each time you can 1)press the digit your thumbpointing at.2)moveyour thumb right,3)move your thumb down. Moving yourthumb left or up is not allowed. By using the numeric keypad under above constrains, you can producesome numbers like 177 or 480 while producing other numbers like 590 or52 is impossible. Given a number K, find out the maximum number less than or equal to Kthat can be produced.

Input description :

the first line contains an integer T, the number of testcases.
Each testcase occupies a single line with an integer K.

For 50%of the data ,1<=K<=999.
For 100% of the data, 1<=K<=10^500,t<=20.

Copy

Output description :

for each testcase output one line, the maximum number less than or equal to the corresponding K that can be produced.

Copy

Input example :

3
25
83
131

Copy

Output example :

25
80
129

Copy

Code demonstration ：

# -*- encoding: utf8 -*-
"""
 2 d list pad Indicates that the number corresponding to the current row value can be listed in the second dimension next time 
 One dimensional list last Indicates the number of available digits for the next key press of the current number -1, The convenient cycle is carried out -1

 Take an example to analyze ：
 Numbers ：131
 hold 1 Input ,
 from 3 Start looking for , Yes 3 In this case ：
 1)  find need, Then find the next character 
 2)  Can't find need, Then try to find the first one less than need Number of numbers , The next number selects the current maximum legal value , End and return 
 3)  Even less than need Can't find the number of , Like this example ： stay key=3 When , look for need=1, Can't find , This is the time ,
 Need to go back key=1 When ( Get rid of ret The last character , The empty string requires special treatment ), look for 1 The available array is smaller than 3 Small 
 Numbers ( Not directly -1, Because it may not be available ). The next number fills in the maximum legal value , End and return .
"""

# mapping table
pad = [[0],
		   [0, 1, 2, 3, 4, 5, 6, 7, 8, 9],
		   [0, 2, 3, 5, 6, 8, 9],
		   [3, 6, 9],
		   [0, 4, 5, 6, 7, 8, 9],
		   [0, 5, 6, 8, 9],
		   [6, 9],
		   [0, 7, 8, 9],
		   [0, 8, 9],
		   [9]]
last = [0, 9, 6, 2, 6, 4, 1, 3, 2, 0]

def find_min_number(num):
	"""
	find the minimum number
	"""
	ret = []
	input_str = str(num)
	input_length = len(input_str)
	ret.append(input_str[0])
	i = 1
	while i < input_length:
		need = int(input_str[i])
		key = int(ret[-1])
		j = last[key]
		# Situation 1)
		while j >= 0:
			if pad[key][j] == need:
				i += 1
				ret.append(str(pad[key][j]))
				break
			j -= 1 

		# Situation 2)
		if j < 0:
			j = last[key]
			while j >= 0:
				if pad[key][j] < need:
					ret.append(str(pad[key][j]))
					key = int(ret[-1])
					return ''.join(ret) + str(pad[key][last[key]])*(input_length-len(ret))
				j -= 1

		# Situation 3)
		if j < 0:
			need = key
			ret = ret[0:-1]
			if len(ret) == 0:
				ret.append(str(need-1))
				key = int(ret[-1])
				return ''.join(ret) + str(pad[key][last[key]])*(input_length-len(ret))

			key = int(ret[-1])
			j = last[key]
			while j >= 0:
				if pad[key][j] < need:
					ret.append(str(pad[key][j]))
					key = int(ret[-1])
					return ''.join(ret) + str(pad[key][last[key]])*(input_length-len(ret))
				j -= 1
	return ''.join(ret)

T = raw_input()
intT = int(T)

for i in range(intT):
	n = raw_input()
	num = int(n)
	print find_min_number(num)

Copy

Publisher ： Full stack programmer stack length , Reprint please indicate the source ：https://javaforall.cn/132495.html Link to the original text ：https://javaforall.cn