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.
[编程题]Numeric Keypad
- 热度指数：7833 时间限制：C/C++ 1秒，其他语言2秒 空间限制：C/C++ 32M，其他语言64M
- 算法知识视频讲解
输入描述:
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
输入
3 25 83 131
输出
25 80 129
import java.util.Scanner;
public class Main{
public static String[] dp={ "0", "0123456789", "0235689", "369","0456789", "05689", "69", "0789", "089", "9" };
public static void main(String[] args){
Scanner input = new Scanner(System.in);
int t = input.nextInt();
input.nextLine();
while(t-->0){
String result="",s=input.nextLine();
boolean flag=false;
int i=0;
for(;i<s.length()-1;i++){
if(judge(s.charAt(i),s.charAt(i+1))){
result+=s.charAt(i);
}else{
flag=true;
break;
}
}
if(flag){
while(i>=0&&less(s.charAt(i),s.charAt(i+1)).equals("")){
//System.out.println("work");
if(i==0){
result=String.valueOf(((int)s.charAt(i)-48-1));
while(i++<s.length()-1){
int l=dp[(int)result.charAt(0)-48].length();
result+=dp[(int)result.charAt(0)-48].charAt(l-1);
}
break;
}
i--;
result=result.substring(0,result.length()-1);
}
if(i<s.length()){
String p=less(s.charAt(i),s.charAt(i+1));
result+=s.charAt(i++);
result+=p;
while(i++<s.length()-1){
int l=dp[Integer.parseInt(p)].length();
result+=dp[Integer.parseInt(p)].charAt(l-1);
}
}
}else{
result+=s.substring(s.length()-1, s.length());
}
System.out.println(result);
}
}
public static boolean judge(char a,char b){
if(dp[(int)a-48].contains(String.valueOf(b))) return true;
else return false;
}
public static String less(char a,char b){
int index=-1;
int temp=(int)b-48;
while(index<0&&temp>=0){
index=dp[(int)a-48].indexOf(String.valueOf(--temp));
}
if(index<0)
return "";
else
return String.valueOf(dp[(int)a-48].charAt(index));
}
}
发表于 2018-08-23 11:17:32
回复(1)
思路大致是：判断输入的数字是否合理，不合理的话就减1，继续判断，一旦合理，就输出！
import java.util.Scanner;
public class Main{
private static final int [][]boost=new int[][]{
{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}
};//合理的输入
public void main(String []args){
Scanner in=new Scanner(System.in);
int T=in.nextInt();//总输入个数
while(T>0){
int next=in.nextInt();
while(isMin(new String(String.valueOf(next)))==false){
next--;
}//每次判断读入的数是否合理，不合理-1
System.out.println(next);
T--;
}
}
public boolean isMin(String s){
boolean min=true;
char[] str=s.toCharArray();
for(int i=0;i<s.length()-1;i++){
int row=str[i]-'0';
for(int j=0;j<boost[row].length;j++){
if(str[i+1]-'0'==boost[row][j]){
min=true;
break;
}
else
min=false;
}
}
return min;
}
}
按照给的例子我输出是成功的，不知道为啥提交不成功呢？说没有通过所有测试，
希望大神们帮忙瞅一眼，感激不尽！
发表于 2017-08-03 10:46:31
回复(1)
//参考了某大神的答案，但是有点啰嗦，很零碎
import java.util.*;
import java.util.*;
public class Main {
public static void main(String[] args) {
Scanner s = new Scanner(System.in);
int n = s.nextInt();
String[] str = new String[n];
s.nextLine();
for(int i=0; i<n; i++)
str[i] = s.nextLine();
for(int i=0; i<n; i++) {
String data = str[i];
char[] num = data.toCharArray();
for(int j=0; j<data.length()-1; j++) {
//不合适的那个结点
while(!reach(num[j], num[j+1])) {
num[j+1]--;
if(num[j+1]<'0') {
num[j]--;
if(j==0)
num[j+1] = '9';
else
j--;
}
for(int k=j+2; k<data.length(); k++)
num[k] = '9';
}
}
for(int i2=0; i2<data.length(); i2++)
System.out.print(num[i2]);
System.out.println();
}
}
public static boolean reach(char first, char next) {
int row1=0, row2=0, col1=0, col2=0;
if(first=='0') {
first = '9'+'2';
}
if(next=='0')
next = '9'+'2';
row1 = (first-1-'0')/3;
col1 = (first+2-'0')%3;
row2 = (next-1-'0')/3;
col2 = (next+2-'0')%3;
if(row1<=row2 && col1<=col2)
return true;
return false;
}
}
发表于 2017-04-05 11:34:23
回复(0)
import java.util.Arrays;
import java.util.Scanner;
public class Main {
public static void main(String[] args) {
Scanner scan = new Scanner(System.in);
int count = scan.nextInt();
scan.nextLine();
String[] array = new String[count];
for (int i = 0; i < count; i++) {
array[i] = scan.nextLine();
}
int[] niubi = { 00, 10, 11, 12, 13, 14, 15, 16, 17, 18, 19, 20, 22, 23, 25, 26, 28, 29, 33, 36, 39, 40, 44, 45,
46, 47, 48, 49, 50, 55, 56, 58, 59, 66, 69, 70, 77, 78, 79, 80, 88, 89, 99 };
for (String arrayi : array) {
char[] num = arrayi.toCharArray();
for (int i = 0; i < num.length - 1;) {
char a = num[i];
char b = num[i + 1];
int tem = Integer.parseInt(("" + a + b));
if (Arrays.binarySearch(niubi, tem) >= 0) {
// System.out.println("okkkkkkkkk"+tem);
i++;
} else {
// System.out.println("***kkkkk"+tem);
int wtf = 0;
for (int *** : niubi) {
if (*** <= tem) {
wtf = ***;
} else {
break;
}
}
num[i] = (char) (wtf / 10 + 48);
num[i + 1] = (char) (wtf % 10 + 48);
for (int **** = i + 2; **** < num.length; ****++) {
if (num[i] == '0')
num[****] = '0';
else
num[****] = '9';
}
i = (i - 1) >= 0 ? i - 1 : 0;
}
}
System.out.println(String.valueOf(num));
}
};
}
编辑于 2016-11-19 22:34:52
回复(0)
不知道是不是非要这么麻烦。。
import java.util.*;
public class Main{
static char[][] pad={
{'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'}
};
public static void main(String[] args){
Scanner sc=new Scanner(System.in);
int t,i,j,r,cur;//cur表示当前停留的按键位置， 其余是循环变量
Stack<Integer> precur=new Stack<Integer>();//存之前相等时的cur值
String k;
StringBuffer res =new StringBuffer();
t=sc.nextInt();
while(t-->0){
k=sc.next();
cur=1;
res=new StringBuffer();
for(i=0;i<k.length();){
if(res.length()>i){//结果长度已经大于i，表示是回溯过程
for(r=0;r<pad[cur].length;r++){//取比当前位置小的下一个数，
if(pad[cur][r]<Integer.valueOf(res.charAt(i))){
res.setCharAt(i,pad[cur][r]);
break;
}
}
if(r==pad[cur].length){//取不到更小的数，继续回溯
if(!precur.isEmpty()){
cur=precur.pop();
i--;
continue;
}
}
else{
i++;
cur=pad[cur][r]-'0';
break;
}
}
else{//向下一位比较
j=0;
while(j<pad[cur].length&&pad[cur][j]>k.charAt(i)){//取第一个不大于给定值的数
j++;
}
if(j==pad[cur].length){//如果想等，继续比较下一个
if(!precur.isEmpty()){
cur=precur.pop();
i--;
continue;
}
}
if(pad[cur][j]==k.charAt(i)){//取不到则回溯
precur.push(cur);
res.append(pad[cur][j]);
cur=k.charAt(i)-'0';
i++;
continue;
}
else{//取到的数小于给定值，则直接跳出循环，将其余值都取能取的最大值。
res.append(pad[cur][j]);
cur=pad[cur][j]-'0';
i++;
break;
}
}
}
for(;i<k.length();i++){//将其余值都取能取的最大值。
if(res.length()>i)
res.setCharAt(i, pad[cur][0]);
else
res.append(pad[cur][0]);
cur=pad[cur][0]-'0';
}
System.out.println(res);
}
sc.close();
}
}
发表于 2016-09-14 16:21:52
回复(0)
历尽千幸万苦终于通过了，一开始由于没有考虑到范围k的范围只是用整型来保存数据，结果一度提示说数组越界，不过在调通之后还是幸福感满满，方法比较啰嗦，可是为了纪念这次通过我一定要把代码贴出来！！！思路：首先根据范围用String存储，然后对于string再由高位对地位处理判断后面出现数字的合法性，如果当前数字不合理：（1）在其合法数组找相较于当前数字次小的数字；（2）如果不存在，那么需要将前面一个数字改为下一个数字的次小合法值（3）该值为最高位那么减一再处理；可以用栈来处理但是没有再修改了直接用了动态数组。import java.util.ArrayList; import java.util.Scanner; public class Main { public static void main(String[] args) { // TODO Auto-generated method stub Scanner in =new Scanner(System.in); int n=Integer.parseInt(in.nextLine()); int[][] istrue={{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[] k=new int[n]; while(n>0){ String k=in.nextLine(); ismaxnumber(k,istrue); n--; } } public static void ismaxnumber(String k,int[][] istrue){ char[] chark=k.toCharArray(); int[] a=new int[chark.length]; for(int i=0;i<chark.length;i++){ a[i]=Integer.parseInt(Character.toString(chark[i])); } ArrayList<Integer> b=new ArrayList(); int current=0; int notcontained=0; //System.out.println(a.length); b.add(a[0]); for(int i=0;i<a.length-1;i++){ current=i+1; if(iscontained(istrue[a[i]],a[i+1])) b.add(a[i+1]); else{ notcontained=1; break;} } //a从0到length为从高位到低位，curren存储当前不满足位置首先从curren-1一个位置判断是否存在比其小的数，如果有后面都为其最大值，反之没有那么则再返回到上上个位置判断 if(notcontained==1){ //System.out.println(a[current]+" current"); if(ismaxofarray(istrue[a[current-1]],a[current])!=-1){ b.add(ismaxofarray(istrue[a[current-1]],a[current])); for(int i=current;current<a.length-1;current++){ b.add(istrue[b.get(i)][istrue[b.get(i)].length-1]); } } else{//即最小值都要小于下一个值，那么光标退回上一个未知，将原有的位置上返回可行解的前一个值 if(current>=2){ if(isnextmaxofarray(istrue[a[current-2]],b.get(current-1))!=-1){ b.set(current-1,isnextmaxofarray(istrue[a[current-2]],b.get(current-1))); for(int i=current-1;i<a.length-1;i++){ b.add(istrue[b.get(i)][istrue[b.get(i)].length-1]); } } else{ b.remove(current-1); b.set(current-2,b.get(current-2)-1); for(int i=current-2;i<a.length-1;i++){ b.add(istrue[b.get(i)][istrue[b.get(i)].length-1]); } } } else{ b.set(current-1,b.get(current-1)-1); for(int i=current-1;i<a.length-1;i++){ b.add(istrue[b.get(i)][istrue[b.get(i)].length-1]); } } } } for(int i=0;i<=b.size()-1;i++) System.out.print(b.get(i)); System.out.println(); } public static boolean iscontained(int[] a,int b){ int c=0; for(int i=0;i<a.length;i++){ if(a[i]==b){ c=1; break; } } if(c==1) return true; else return false; } public static int ismaxofarray(int[] a,int b){ int c=-1; for(int i=a.length-1;i>=0;i--){ if(a[i]<=b){ c=a[i]; break; } } return c; } public static int isnextmaxofarray(int[] a,int b){ int c=-1; for(int i=a.length-1;i>=0;i--){ if(a[i]<b){ c=a[i]; break; } } return c; } }
发表于 2016-08-29 14:36:04
回复(0)
问题信息
难度：
6条回答
49收藏
13287浏览
通过挑战的用户
查看代码-
2023-02-18 16:55:56 -
2022-09-03 14:50:14 -
2022-08-29 08:37:20 -
2022-08-26 22:19:37 -
2022-08-25 14:40:12
相关试题
-
扫描二维码，关注牛客网
- 意见反馈
-
下载牛客APP，随时随地刷题
扫一扫，把题目装进口袋
- 求职之前，先上牛客
-
扫描二维码，进入QQ群
扫描二维码，关注牛客公众号
- 公司地址：北京市朝阳区北苑路北美国际商务中心K1座一层-北京牛客科技有限公司
- 联系方式：010-60728802 投诉举报电话：010-57596212（朝阳人力社保局）
- 牛客科技© All rights reserved admin@nowcoder.com
- 京ICP备14055008号-4 增值电信业务经营许可证 营业执照 人力资源服务许可证
-
京公网安备
11010502036488号
