java - PALIN- 下一个回文 - 一个 SPOJ 问题
问题描述
我为 Ridit 开了一个帐户,Ridit 是在 SPOJ 学习 Java 的 7 岁学生之一。我给他的第一个任务是 PALIN - The Next Palindrome。这是这个问题的链接- PALIN- The next Palindrome- SPOJ在我向他解释之后,他能够解决大部分问题,除了删除前导零,我做到了。以下是他对问题的解决方案 -
import java.util.Scanner;
public class Main {
public static void main(String[] args) {
// TODO Auto-generated method stub
try {
Scanner in = new Scanner(System.in);
int t = Integer.parseInt(in.nextLine());
String[] numbersInString = new String[t];
for (int i = 0; i <t; i++) {
String str = in.nextLine();
numbersInString[i] = removeLeadingZeros(str);
}
for (int i = 0 ; i<t; i++) {
int K = Integer.parseInt(numbersInString[i]);
int answer = findTheNextPalindrome(K);
System.out.println(answer);
}
}catch(Exception e) {
return;
}
}
static boolean isPalindrome(int x) {
String str = Integer.toString(x);
int length = str.length();
StringBuffer strBuff = new StringBuffer();
for(int i = length - 1;i>=0;i--) {
char ch = str.charAt(i);
strBuff.append(ch);
}
String str1 = strBuff.toString();
if(str.equals(str1)) {
return true;
}
return false;
}
static int findTheNextPalindrome(int K) {
for(int i = K+1;i<9999999; i++) {
if(isPalindrome(i) == true) {
return i;
}
}
return -1;
}
static String removeLeadingZeros(String str) {
String retString = str;
if(str.charAt(0) != '0') {
return retString;
}
return removeLeadingZeros(str.substring(1));
}
}
它在他的计算机上的 Eclipse 中给出了正确的答案,但在 SPOJ 中却失败了。如果有人帮助这个小男孩第一次提交,那肯定会让他非常高兴。我找不到此解决方案的任何问题...提前谢谢您...
解决方案
这可能会有所帮助
import java.io.IOException;
import java.util.Scanner;
public class ThenNextPallindrom2 {
public static void main(String[] args) throws IOException {
// TODO Auto-generated method stub
int t = 0;
Scanner sc = new Scanner(System.in);
if(sc.hasNextInt()) {
t = sc.nextInt();
}
sc.nextLine();
int[] arr, arr2;
while(t > 0) {
t--;
String s = sc.nextLine();
arr = getStringToNumArray(s);
if(all9(arr)) {
arr2 = new int[arr.length + 1];
arr2[0] = 1;
for(int i=0;i<arr.length;i++) {
arr2[i+1] = 0;
}
arr2[arr2.length -1] = 1;
arr = arr2;
} else{
int mid = arr.length/ 2;
int left = mid-1;
int right = arr.length % 2 == 1 ? mid + 1 : mid;
boolean left_small = false;
while(left >= 0 && arr[left] == arr[right]) {
left--;
right++;
}
if(left < 0 || arr[left] < arr[right]) left_small = true;
if(!left_small) {
while(left >= 0) {
arr[right++] = arr[left--];
}
} else {
mid = arr.length/ 2;
left = mid-1;
int carry = 1;
if(arr.length % 2 == 0) {
right = mid;
} else {
arr[mid] += carry;
carry = arr[mid]/10;
arr[mid] %= 10;
right = mid + 1;
}
while(left >= 0) {
arr[left] += carry;
carry = arr[left] / 10;
arr[left] %= 10;
arr[right++] = arr[left--];
}
}
}
printArray(arr);
}
}
public static boolean all9(int[] arr) {
for(int i=0;i<arr.length;i++) {
if(arr[i] != 9)return false;
}
return true;
}
public static void printArray(int[] arr) {
for(int i=0;i<arr.length;i++) {
System.out.print(arr[i]);
}
System.out.println();
}
public static int[] getStringToNumArray(String s) {
int[] arr = new int[s.length()];
for(int i=0; i<s.length();i++) {
arr[i] = Integer.parseInt(String.valueOf(s.charAt(i)));
}
return arr;
}
}
推荐阅读
- python - 如何使用 python(最好是 BS4)从 Google 图片(或 bing)中找到图片的 url?
- javascript - 如何在反应中从firebase cloud firestore获取数据
- amazon-web-services - 注册 ECS Fargate 实例时 NLB 健康检查随机失败
- sql - 创建滚动期间
- python - 如何将连接的值连接到python中的新值
- f# - 在 F# 中,如何将 null 写入 Nullable
班员? - java - 单击事件时跳转到集合中的下一个项目
- azure-devops - .NET Core SDK 5.0.100 的 Nuget 还原失败
- pine-script - Change chart background daily
- wordpress - 网站更新后自动刷新页面