返回信息流题目描述
The numberic keypad on your mobile phone looks like below:
1 2 3
4 5 6
7 8 9
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.
输入例子:
3
25
83
131
输出例子:
25
80
129
这题今天LZ用java在牛客网上做，但是发现总是报错：运行错误:请检查是否存在数组越界非法访问，野指针乱访问，空指针乱访问等情况。但是我在本地测试了一些例子，都是对的，不知道是什么原因造成的，望群里的大神们指导。如下为我的代码：
import java.util.HashMap;
import java.util.HashSet;
import java.util.Iterator;
import java.util.List;
import java.util.Map;
import java.util.Scanner;
import java.util.Set;
import java.util.TreeSet;
public class Main
{
public static void main(String[] args)
{
Map<Integer,Set<Integer>> hashMap = new HashMap<Integer,Set<Integer>>();
Set<Integer> s1 = new TreeSet<Integer>();
for(int i = 1; i < 10; i++)
s1.add(i);
s1.add(0);
hashMap.put(1, s1);
Set<Integer> s2 = new TreeSet<Integer>();
s2.add(2);
s2.add(3);
s2.add(5);
s2.add(6);
s2.add(8);
s2.add(9);
s2.add(0);
hashMap.put(2, s2);
Set<Integer> s3 = new TreeSet<Integer>();
s3.add(3);
s3.add(6);
s3.add(9);
hashMap.put(3, s3);
Set<Integer> s4 = new TreeSet<Integer>();
s4.add(4);
s4.add(5);
s4.add(6);
s4.add(7);
s4.add(8);
s4.add(9);
s4.add(0);
hashMap.put(4, s4);
Set<Integer> s5 = new TreeSet<Integer>();
s5.add(5);
s5.add(6);
s5.add(8);
s5.add(9);
s5.add(0);
hashMap.put(5, s5);
Set<Integer> s6 = new TreeSet<Integer>();
s6.add(6);
s6.add(9);
hashMap.put(6, s6);
Set<Integer> s7 = new TreeSet<Integer>();
s7.add(7);
s7.add(8);
s7.add(9);
s7.add(0);
hashMap.put(7, s7);
Set<Integer> s8 = new TreeSet<Integer>();
s8.add(8);
s8.add(9);
s8.add(0);
hashMap.put(8, s8);
Set<Integer> s9 = new TreeSet<Integer>();
s9.add(9);
hashMap.put(9, s9);
Set<Integer> s0 = new TreeSet<Integer>();
s0.add(0);
hashMap.put(0, s0);
Scanner in = new Scanner(System.in);
int t = in.nextInt();
while(t-- > 0)
{
int n = in.nextInt();
String str = n + "";
int length = str.length();
//System.out.println(length);
StringBuilder sb = new StringBuilder();
int i = 0;
for(i = 0; i < length; i++)
{
if(i == 0)
sb.append(str.charAt(i));
else
{
int tmp = str.charAt(i - 1) - '0';
int tm = str.charAt(i) - '0';
if(hashMap.get(tmp).contains(tm))
{
sb.append(str.charAt(i));
}
else
{
TreeSet treeSet = (TreeSet) hashMap.get(tmp);
Iterator it = treeSet.iterator();
int[] temp = new int[treeSet.size()];
int k = 0;
while(it.hasNext())
{
Integer j = (Integer)it.next();
temp[k] = j;
k++;
}
if(temp[0] > (str.charAt(i) - '0'))
{
sb.deleteCharAt(i - 1);
sb.append(str.charAt(i - 1) - '0' - 1);
int p = i;
for(p = i; p < length; p++)
sb.append(9);
System.out.println(sb.toString());
break;
}
else
{
for(k = 0; k < temp.length; k++)
{
if(temp[k] > (str.charAt(i) - '0'))
break;
}
if(temp[k - 1] == 0)
{
int p = i;
for(p = i; p < length; p++)
sb.append(0);
System.out.println(sb.toString());
break;
}
else
{
sb.append(temp[k - 1]);
//int p = i + 1;
for(int p = i + 1; p < length; p++)
sb.append(0);
System.out.println(sb.toString());
break;
}
}
}
}
}
if(i == length)
System.out.println(sb.toString());
}
}
}
此题在牛客网中的链接：http://www.nowcoder.com/practice/f46db1d185114716abbeaea1d58ffd62?tpId=49&tqId=29235&rp=1&ru=/ta/2016test&qru=/ta/2016test/question-ranking
这是一条镜像帖。来源：北邮人论坛 / acm-icpc / #89197同步于 2016/3/20
该镜像源已超过 30 天没有更新，可能在源站已被删除。
ACM_ICPC机器人发帖
Numberic keypad 微软去年校招在线测试题
sun111
2016/3/20镜像同步21 回复
订阅后，新回复会通过你的通知中心匿名送达。
9 条回复
对于直接上代码的人，我就直接回一份代码好了。
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <iostream>
#include <algorithm>
#include <vector>
using namespace std;
#define print(x) cout << x << endl
#define input(x) cin >> x
const int SIZE = 555;
struct Move {
int value;
int y;
int x;
};
int n;
char num[SIZE];
vector<int> ans;
const int keyboard[5][5] = {
{1, 2, 3},
{4, 5, 6},
{7, 8, 9},
{-1, 0, -1},
};
int get_y(int v) {
if (v == 0) {
return 3;
}
return (v - 1) / 3;
}
int get_x(int v) {
if (v == 0) {
return 1;
}
return (v - 1) % 3;
}
bool do_dfs(int ptr, int y, int x, bool flag) {
if (ptr == n) {
return true;
}
vector<Move> moves;
for (int i = 0; i < 4; i++) {
for (int j = 0; j < 3; j++) {
if (keyboard[i][j] == -1) {
continue;
}
if (i < y || j < x) {
continue;
}
Move m = {keyboard[i][j], i, j};
moves.push_back(m);
}
}
sort(moves.begin(), moves.end(), [](const Move& m1, const Move& m2) {
return m1.value > m2.value;
});
int v = num[ptr] - '0';
for (auto m: moves) {
if (m.value == -1) {
continue;
}
if (flag && m.value > v) {
continue;
}
ans.push_back(m.value);
bool ff = flag && (m.value == v);
if (do_dfs(ptr + 1, m.y, m.x, ff)) {
return true;
}
ans.pop_back();
}
return false;
}
void dfs() {
int v = num[0] - '0';
for (int i = v; i >= 0; i--) {
int y = get_y(i);
int x = get_x(i);
if (do_dfs(0, y, x, true)) {
break;
}
}
}
int main() {
freopen("input.txt", "r", stdin);
int T;
input(T);
while (T--) {
scanf("%s", num);
n = strlen(num);
ans.clear();
dfs();
int l = ans.size();
int ptr = 0;
while (ptr < l && ans[ptr] == 0) {
ptr++;
}
while (ptr < l) {
printf("%d", ans[ptr]);
ptr++;
}
puts("");
}
return 0;
}
【 在 Wizmann 的大作中提到: 】
: 对于直接上代码的人，我就直接回一份代码好了。
: [code=c]
: #include <cstdio>
: ...................
怎么把代码搞成这种格式啊。。。
哈哈，少年我欣赏你的魄力
【 在 Wizmann 的大作中提到: 】
: 对于直接上代码的人，我就直接回一份代码好了。
: [code=c]
: #include <cstdio>
: ...................
（≧?≦）
【 在 Lamperouge 的大作中提到: 】
: 活捉一只[ema0]
:
: 【 在 ayzmkk (ayzmkk) 的大作中提到: 】
: : 求认识～
:
前辈你好！我测试了你的代码，网站提示：
你的代码仅仅处理了一个测试用例，没有循环处理多个测试用例。
比如对于求解A+B的和的题目，需要按照以下代码来处理
正确代码：
#include <stdio.h>
int main() {
int a,b;
while(scanf("%d %d",&a, &b) != EOF)//注意while处理多个case
printf("%d
",a+b);
return 0;
}
错误代码:
#include <stdio.h>
int main() {
int a,b;
scanf("%d %d",&a, &b);//没有处理多个case
printf("%d
",a+b);
return 0;
}
【 在 Wizmann 的大作中提到: 】
: 对于直接上代码的人，我就直接回一份代码好了。
: [code=c]
: #include <cstdio>
: ...................