我正在进行《破解编码访谈》一书中的练习,我试图确定字符串中是否有重复的字符。我正在使用ArrayList数据结构。我的方法的返回类型为Boolean,如果存在重复,则返回true;如果没有重复的字符,则返回false。我添加了第三条return语句,以便程序可以编译,但始终返回false。
import java.util.*;
public class QuestionOneCrackingCode {
public static void main(String[] args) {
String s = "abcdefga";
ArrayList<String> c = new ArrayList<String>();
c.add(s);
System.out.print(check(c));
}
public static boolean check(ArrayList<String> g) {
for (int i = 0; i < g.size(); i++) {
for (int j = i + 1; j < g.size(); j++) {
if (g.get(i) == g.get(j)) {
return true;
} else {
return false;
}
}
}
return false;
}
}
您没有将字符串分成字符,而是创建了一个包含字符串的单元素列表。无需对算法做大的改动,就可以这样:
public static void main(String[] args) {
String s = "abcdefga";
System.out.print(check(s));
}
public static boolean check(CharSequence g) {
for (int i = 0; i < g.length(); i++) {
for (int j = i + 1; j < g.length(); j++) {
if (g.charAt(i) == g.charAt(j)) {
return true;
}
}
}
return false;
}
请注意,第一个return false;
也是不正确的,因为它将阻止算法继续通过第一个比较。
顺便说一句,are比较字符串时,应使用.equals()
而不是==
。
您的解决方案比较列表中的字符串引用。列表本身仅包含一个字符串。
尝试以下操作:
// check one string for duplicate chars
public static boolean check(String checkString)
{
// result flag
boolean foundDuplicate = false;
// get string length
int stringLength = checkString.length();
// create a set for all found characters (max size is number
// of characters in the string to check
Set<Character> characters = new HashSet<>(stringLength);
// loop all characters in string
for (int i = 0; i < stringLength; i++)
{
// construct a object (may be use internal JDK cache)
Character c = Character.valueOf(checkString.charAt(i));
// check if character is already found
if (characters.contains(c))
{
// yes, set result to TRUE
foundDuplicate = true;
// break the loop
break;
}
else
{
// not found, add char to set
characters.add(c);
}
}
return foundDuplicate;
}
这受字符串长度和堆大小的限制。但是我认为所有UTF-8字符都可以放入堆中。
@@ Maarten Bodewes,您是对的。该检查可以简化为:
// add character to set and check result
if (!characters.add(c))
{
// returned false: character already exists
foundDuplicate = true;
// break the loop
break;
}
// no else necessary
这是我的代码版本的结果。
abcdefga true
abcdefgh false
abcdefdh true
我修改了check参数以采用单个String。不需要字符串列表。
在检查方法中,一旦一对字符匹配,您可以退出。您必须先测试整个字符串,然后才能说没有匹配的字符。
第一个for循环可以停在倒数第二个字符处。第二个for循环将获取最后一个字符。
因为我正在比较char值,所以我使用==。如果我在比较String值,则将使用.equals方法。
这里是代码。
package com.ggl.testing;
public class QuestionOneCrackingCode {
public static void main(String[] args) {
String s = "abcdefga";
System.out.println(s + " " + check(s));
s = "abcdefgh";
System.out.println(s + " " + check(s));
s = "abcdefdh";
System.out.println(s + " " + check(s));
}
public static boolean check(String s) {
for (int i = 0; i < (s.length() - 1); i++) {
for (int j = i + 1; j < s.length(); j++) {
if (s.charAt(i) == s.charAt(j)) {
return true;
}
}
}
return false;
}
}
我的参与:
public static void main(String[] args) {
System.out.println(check("abcdefga")); // true
System.out.println(check("noduplicate")); // false
System.out.println(check("withduplicate")); // true
System.out.println(check("abcdefghijklmnopqrstuvwxyz")); // false
System.out.println(check("abcdefghijklmnopqrstuvwxyzz")); // true
}
/**@brief Check if a String contains duplicated characters.
* Strong expectation for the string: The String must only contains
* lowercase alpha characters (ie. in [a-z])
* @returns true if a char is present more than once */
public static boolean check(String str) {
int presentChars = 0; // will store the table of already found characters
int l = str.length();
for (int i = 0; i < l; ++i) {
char c = str.charAt(i);
int offset = c - 'a'; // a=0, b=1, ... z=25
int mask = 1 << offset;
if ((presentChars& mask) != 0) { // Oh! Char already tagged as found
return true; // No need to process further, bye!
}
presentChars|= mask; // Tag the current char as present
}
return false; // No duplicate
}
}
我使用此代码的目标是最大程度地减少复杂性。在最坏的情况下,该算法位于O(N)中。另外,该函数的内存占用非常低:即使我为了提高可读性而使用更多int
,实际上仅需要一个presentChars
=)
此代码的缺点:输入的字符串有很大的先决条件。我已经在评论中对此进行了详细说明,但它仅适用于[a-z]范围内的字符。
希望对您有所帮助!
在Java 8中,您可以这样操作:
public static boolean check(CharSequence checkString)
{
return checkString.length() != checkString.chars().distinct().count();
}
即如果字符串中不同字符的数量与字符总数不同,则说明存在重复。这不一定是最有效的方法,但是它是简洁的。
public static boolean check(String g) {
for (int i = 0; i < g.length(); i++) {
for (int j = i + 1; j < g.length(); j++) {
if (g.charAt(i) == (g.charAt(j))) {
return true;
}
}
}
return false;
}
[我使用一个表格来计算一个字符重复多少次,如果一个字符出现多次,然后返回true,则最坏情况下的代码为O(n)
public static void main(String[] args) {
String test ="abdefghijklmnoPQRSTUVWXYZa";
System.out.println(isThereAnyCharacterRepeated(test));
}
public static boolean isThereAnyCharacterRepeated(String str){
int repeatedCharacters[] = new int[255];
for(int i=0;i<str.length();i++){
int index=(int)str.charAt(i);
repeatedTable[index]++;
if(repeatedTable[index]>1)return true;
}
return false;
}