gpt4 book ai didi

java - 对字符串执行的最小循环(向前或向后)移位以使其成为回文

转载 作者:行者123 更新时间:2023-12-01 11:13:08 25 4
gpt4 key购买 nike

以下是问题陈述和解决方案。两个测试用例对我来说失败了。帮我弄清楚。

如果一个字符串从两端读取相同的内容,则该字符串被称为回文字符串。给定一个字符串 S ,您可以执行循环移位。更正式地说,您可以从任何一端(头部或尾部)选取任何一个字符,并且可以将该字符附加到另一端。例如,如果字符串是 "abc" ,那么如果我们使用头部位置的字符进行移位,则字符串将变为 "bca" 。类似地,如果我们使用尾部的字符进行移位,则输入字符串将变为 "cab" 。您的任务是找出使给定字符串成为回文所需的最少移位次数。如果我们无法将字符串转换为回文然后打印 -1 .

输入格式: 第一行以 T 开头即测试用例的数量,然后 T每行后面都包含一个字符串 S .

输出格式: 如果每个字符串可以成为回文,则打印每个字符串的最小循环移位次数,否则 -1 .

限制: 1<=T<=100 , 1<=|S|<=300 , S将仅包含小写字母 ('a'-'z') .

示例输入和输出

输入

4
abbb
aaabb
aabb
abc

输出

-1
1
1
-1

说明:对于测试用例 2 (aaabb): 将尾部的字符移到头部,结果是“baaab”,这是一个回文。这是一个需要最少移位次数才能使给定字符串成为回文的操作。

对于测试用例 3 ( aabb ): 将给定字符串转换为回文的一种方法是将头部字符移至尾部,结果将是 "abba" ,这是一个回文。另一种方法是将尾部的字符移至头部,结果为 "baab" ,这也是一个回文。两者都只需要一个类次。

public class cyclic {

static boolean flag = false;

// fn to check if string is palindrome
static boolean ispal(String s) {
String reverse = "";
int length = s.length();
for (int i = length - 1; i >= 0; i--)
reverse = reverse + s.charAt(i);
reverse = reverse.trim();
if (s.equals(reverse)) {
flag = true;
return true;
} else {
return false;
}
}

// fn to perform front shift
static int frontshift(String str) {
int count = 0;
String element = "";
String s1[] = str.split("");
Deque<String> dequeA = new LinkedList<String>();
for (int i = 1; i < s1.length; i++) {
dequeA.add(s1[i]);
}
while (!ispal(str)) {
if (count <= str.length()) {
element = "";
String firstElement = dequeA.removeFirst();
dequeA.addLast(firstElement);
for (String object : dequeA) {
element = element + object;
}
str = element;
count++;
} else {
break;
}
}
return count;
}

// fn to perform backshift
static int backshift(String str) {
int count = 0;
String element = "";
String s1[] = str.split("");
Deque<String> dequeA = new LinkedList<String>();
for (int i = 1; i < s1.length; i++) {
dequeA.add(s1[i]);
}
while (!ispal(str)) {
if (count <= str.length()) {
element = "";
String firstElement = dequeA.removeLast();
dequeA.addFirst(firstElement);
for (String object : dequeA) {
element = element + object;
}
str = element;
count++;
} else {
break;
}
}
return count;
}

public static void main(String args[]) throws IOException {
BufferedReader br =
new BufferedReader(new InputStreamReader(System.in));
List<Integer> list = new ArrayList<Integer>();
int range = Integer.parseInt(br.readLine());
for (int i = 0; i < range; i++) {
String s = br.readLine();
int l1 = frontshift(s);
int l2 = backshift(s);
if (flag == true) {
if (l1 <= l2) {
list.add(l1);
} else {
list.add(l2);
}
} else {
list.add(-1);
}
flag = false;
}
for (Integer integer : list) {
System.out.println(integer);
}
}
}

最佳答案

我不是根据您的代码解决了您的任务:

import java.util.Scanner;

public class PalyndromeTest {
static boolean isPalyndrome(String s, int shift) {
int n = s.length();
if(shift < 0) shift+=n;
for(int pos = 0; pos < n/2; pos++) {
if(s.charAt((pos+shift)%n) != s.charAt((n-pos-1+shift)%n))
return false;
}
return true;
}

static int findShift(String s) {
for(int shift = 0; shift <= s.length()/2; shift++) {
if(isPalyndrome(s, shift) || isPalyndrome(s, -shift))
return shift;
}
return -1;
}

public static void main(String[] args) {
Scanner s = new Scanner(System.in);
int count = s.nextInt();
s.nextLine();
for(int i=0; i<count; i++) {
System.out.println(findShift(s.nextLine()));
}
}
}

首先,isPalyndrome 方法。它检查字符串是否是回文,并且也适用于正移或负移。请注意,例如,对于长度为 5 的字符串,shift = -1shift = 4 相同。我们不创建任何新字符串,只是使用 String.charAt 方法扫描现有字符串。我们使用%n余数运算符在到达字符串末尾时自动移回字符串开头。请注意,我们应该只检查字符串的一半。

第二,findShift 方法。它只是迭代从 0s.length()/2 的所有移位(不需要检查更大的移位,因为它们等于已经检查的负移位)。在每次迭代中,它都会检查正移和负移。

最后是 main 方法,它读取标准输入并为每个输入行调用 findShift 。它会立即输出结果,但如果您愿意,您可以将其收集到列表中并在最后输出。

关于java - 对字符串执行的最小循环(向前或向后)移位以使其成为回文,我们在Stack Overflow上找到一个类似的问题: https://stackoverflow.com/questions/32134536/

25 4 0
Copyright 2021 - 2024 cfsdn All Rights Reserved 蜀ICP备2022000587号
广告合作:1813099741@qq.com 6ren.com