首页 > 试题广场 >

Numeric Keypad

[编程题]Numeric Keypad

热度指数：7833 时间限制：C/C++ 1秒，其他语言2秒空间限制：C/C++ 32M，其他语言64M
算法知识视频讲解

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 thumb points at digit 1. Each time you can 1)press the digit your thumb pointing at.2)moveyour thumb right,3)move your thumb down. Moving your thumb left or up is not allowed.
By using the numeric keypad under above constrains, you can produce some numbers like 177 or 480 while producing other numbers like 590 or 52 is impossible.
Given a number K, find out the maximum number less than or equal to K that can be produced.

输入描述:

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.

输出描述:

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

示例1

输入

输出

25
80
129

算法知识视频讲解

Python

离疏

x = [10]*10
x[0]=[0]
x[1]=[1,2,3,4,5,6,7,8,9,0]
x[2]=[2,3,5,6,8,9,0]
x[3]=[3,6,9]
x[4]=[4,5,6,7,8,9,0]
x[5]=[5,6,8,9,0]
x[6]=[6,9]
x[7]=[7,8,9,0]
x[8]=[8,9,0]
x[9]=[9]

T=int(input())
for t in range(T):
    K=list(input())
    for i in range(len(K)-1):
        while int(K[len(K)-1-i]) not in x[int(K[len(K)-2-i])]:#从低位往高位遍历
            if K[len(K)-i-1] == '0':#低位等于0且不在高位的下一步中
                K[len(K)-i-2] = str(int(K[len(K)-i-2])-1)#高位数字-1
                K[len(K)-i-1] = '9'#低位为9
            else:#低位不为0
                K[len(K)-i-1] = str(int(K[len(K)-1-i]) -1)#低位-1
            if len(K)-i < len(K):#当低位不是最后一位时
                for j in range(len(K)-i,len(K)):#要么这一位减了1,要么前一位减了1
                    K[j] = '9'#后面全部的变成 9才能最接近给的数字
        if K[len(K)-i-1] =='0' :#低位在高位的下一步中且低位为0
            if len(K)-i < len(K):#不是最后一位
                for j in range(len(K)-i,len(K)):#0后面只能是0
                    K[j] = '0'
    print(''.join(K))

发表于 2018-09-30 17:02:20 回复(0)

Python

大鹌鹑

当按下一个键时，下一个键的范围就受限了，我们可以找出键盘上的每个键的下一个键的范围。

keyboard = [['0'], ['9', '8', '7', '6', '5', '4', '3', '2', '1', '0'], ['9', '8', '6', '5', '3', '2', '0'],
            ['9', '6', '3'], ['9', '8', '7', '6', '5', '4', '0'], ['9', '8', '6', '5', '0'], ['9', '6'],
            ['9', '8', '7', '0'], ['9', '8', '0'], ['9']]


def find_max(target, cur):
    if len(target) <= len(cur):
        return cur
    for n in keyboard[int(cur[-1])]:
        if (cur + n <= target[:len(cur) + 1]):
            re = find_max(target, cur + n)
            if re is not None:
                return re
    return None


cnt = input()
in_args = []
for _ in xrange(0, cnt):
    num = input()
    in_args.append(str(num))

for num in in_args:
    for i in xrange(int(num[0]), -1, -1):
        result = find_max(num, str(i))
        if result is not None:
            print result
            break

发表于 2016-08-08 09:05:23 回复(0)