【每天一道算法题】Numeric Keypad

题目描述

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.

输入例子:

输出例子:

25
80
129

剑指offer公司真题部分，微软的题目。

根据题意，可以知道的是，按下某个键后，这个键左方及上方的键不能再用了。例如按下了[5]:

所以我们可以得到一张表，以表示按下某个键后还剩下的合法按键：

一个数组表示key，也就是当前被查的字符。

一个数组last表示，当前被查字符的可用数字的个数。例如1是9，0是0，9是0。

例如来一个131.

把1输入进去。

从3开始查。need=3；

会有以下三种情况：

　　找到need。。如果找到，那么查找下一个字符，也就是1.

　　找不到need。。我试着找第一个小于need的数。那么后面的所以数位则填充当前最大的合法值，结束，返回；

　　连小于need的数我都找不到。。就像这个例子，我在key=3的时候，找need=1。我根本找不到，这个时候，需要回到key=1的时候（需要pop，遇到字符串为空的情况需要特殊处理），找1的可用数组里，比need稍微小一点的（不能直接找need-1，因为need-1可能不在可用数组里。），那么后面的所以数位则填充当前最大的合法值，结束，返回。

#include <iostream>
#include <vector>
#include <string>
#include <queue>
using namespace std;
int pad[10][10] = {
    { 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 }

};
int last[] = { 0,9,6,2,6,4,1,3,2,0 };

string maxnum(string& s1) {
    string s2;
    s2.push_back(s1[0]);
    int len = s1.length();
    for (int i = 1; i < len; ) {
        int need = s1[i] - '0';
        int key = s2.back() - '0';
        int j = 0;
        for (j = last[key]; j >= 0; j--)
        {
            if (pad[key][j] == need) {
                i++;
                s2.push_back(pad[key][j] + '0');
                break;
            }
        }

        if (j < 0) {
            for (j = last[key]; j >= 0; j--)
            {
                if (pad[key][j] < need) {
                    s2.push_back(pad[key][j] + '0');
                    key = s2.back() - '0';
                    for (int j = s2.size(); j < len; j++)
                        s2.push_back(pad[key][last[key]] + '0');
                    return s2;
                }
            }
        }

        if (j < 0) {
            need = key;
            s2.pop_back();
            if (s2.size() == 0) {
                s2.push_back(need - 1 + '0');
                key = s2.back() - '0';
                for (int j = s2.size(); j < len; j++)
                    s2.push_back(pad[key][last[key]] + '0');
                return s2;
            }

            key = s2.back()-'0';
            for (j = last[key]; j >= 0; j--)
            {
                if (pad[key][j] < need) {
                    s2.push_back(pad[key][j] + '0');
                    key = s2.back() - '0';
                    for (int j = s2.size(); j < len; j++)
                        s2.push_back(pad[key][last[key]]+'0');
                    return s2;
                }
            }
        }

    }
    return s2;
}

int main() {
    int num;
    cin >> num;
    vector<string> vec(num,"");
    for (int i = 0; i < num; i++)
        cin >> vec[i];
    for (int i = 0; i < num; i++)
        cout << maxnum(vec[i]) << endl;
    return 0;
}