请实现一个算法，确定一个字符串的所有字符是否全都不同。这里我们要求不允许使用额外的存储结构。
第一次，自己实现：
public class T1_1 {
// 请实现一个算法，确定一个字符串的所有字符是否全都不同。这里我们要求不允许使用额外的存储结构。
// 给定一个string iniString，请返回一个bool值,True代表所有字符全都不同，False代表存在相同的字符。保证字符串中的字符为ASCII字符。字符串的长度小于等于3000。
// 测试样例：
// "aeiou"
// 返回：True
//"BarackObama"
// 返回：False
public boolean checkDifferent(String iniString) {
// write code here
for(int i=0;i<iniString.length()-1;i++){
for(int j=i+1;j<iniString.length()-1;j++){
if(iniString.substring(i,i+1).equals(iniString.substring(j,j+1))){
return false;
}
}
}
return true;
}
public static void main(String[] args){
System.out.println(new T1_1().checkDifferent("BarackObama"));
}
}
第二次 牛人解法
public boolean checkDifferent(String iniString) {
return !iniString.matches(".*(.)(.*\\1).*");
}
通过搜索String.maches()的用法后，发现了正则表达式的规则总结：
image.png
这是这个正则的解释
image.png
但是我迷惑的是 反向引用明明是 \1 为什么 在代码中是 \1 呢
后来找到解答：
image.png
好吧- - ！
第三次 跟着大神写代码：
大神的提示：
image.png
当然前提是 “保证字符串中的字符为ASCII字符。字符串的长度小于等于3000”
那我就跟着大神写代码：
1.哈希法：
import java.util.HashMap;
public class T1_1 {
// 请实现一个算法，确定一个字符串的所有字符是否全都不同。这里我们要求不允许使用额外的存储结构。
// 给定一个string iniString，请返回一个bool值,True代表所有字符全都不同，False代表存在相同的字符。保证字符串中的字符为ASCII字符。字符串的长度小于等于3000。
// 测试样例：
// "aeiou"
// 返回：True
//"BarackObama"
// 返回：False
public boolean checkDifferent(String iniString) {
HashMap<Character,Boolean> myMap=new HashMap<>(256);
char[] myChar=iniString.toCharArray();
for(char tmp:myChar){
if(myMap.get(tmp) == null){
myMap.put(tmp,true);
}else{
return false;
}
}
return true;
}
public static void main(String[] args) {
System.out.println("重复："+new T1_1().checkDifferent("BarackObama"));
System.out.println("不重复："+new T1_1().checkDifferent("aeiou"));
}
}
2.遍历 略
3.排序
import static java.util.Arrays.sort;
public class T1_1 {
// 请实现一个算法，确定一个字符串的所有字符是否全都不同。这里我们要求不允许使用额外的存储结构。
// 给定一个string iniString，请返回一个bool值,True代表所有字符全都不同，False代表存在相同的字符。保证字符串中的字符为ASCII字符。字符串的长度小于等于3000。
// 测试样例：
// "aeiou"
// 返回：True
//"BarackObama"
// 返回：False
public boolean checkDifferent(String iniString) {
char[] chars=iniString.toCharArray();
sort(chars);
for(int i=0;i<chars.length-1;i++){
if(chars[i] == chars[i+1]){
return false;
}
}
return true;
}
public static void main(String[] args) {
System.out.println("重复："+new T1_1().checkDifferent("BarackObama"));
System.out.println("不重复："+new T1_1().checkDifferent("aeiou"));
}
}
- (不想做)
另一个大神的思路
image.png
public class T1_1 {
// 请实现一个算法，确定一个字符串的所有字符是否全都不同。这里我们要求不允许使用额外的存储结构。
// 给定一个string iniString，请返回一个bool值,True代表所有字符全都不同，False代表存在相同的字符。保证字符串中的字符为ASCII字符。字符串的长度小于等于3000。
// 测试样例：
// "aeiou"
// 返回：True
//"BarackObama"
// 返回：False
public boolean checkDifferent(String iniString) {
int[] ints=new int[256];
for(int i=0;i<ints.length;i++){
ints[i]=0;
}
for(int i=0;i<iniString.length();i++){
int counter=iniString.charAt(i);
if(ints[counter]>1){
return false;
}else{
ints[counter]++;
}
}
return true;
}
public static void main(String[] args) {
System.out.println("重复："+new T1_1().checkDifferent("BarackObama"));
System.out.println("不重复："+new T1_1().checkDifferent("aeiou"));
}
}
others:
import java.util.TreeSet;
public class T1_1 {
// 请实现一个算法，确定一个字符串的所有字符是否全都不同。这里我们要求不允许使用额外的存储结构。
// 给定一个string iniString，请返回一个bool值,True代表所有字符全都不同，False代表存在相同的字符。保证字符串中的字符为ASCII字符。字符串的长度小于等于3000。
// 测试样例：
// "aeiou"
// 返回：True
//"BarackObama"
// 返回：False
public boolean checkDifferent(String iniString) {
TreeSet<Character> tree=new TreeSet<>();
for(int i=0;i<iniString.length();i++){
tree.add(iniString.charAt(i));
}
return tree.size()==iniString.length()?true:false;
}
public static void main(String[] args) {
System.out.println("重复："+new T1_1().checkDifferent("BarackObama"));
System.out.println("不重复："+new T1_1().checkDifferent("aeiou"));
}
}
以上大神思路参考链接：
https://www.nowcoder.com/questionTerminal/9618c2a9e8a14c3e82954ee14168f592
以上我没有写出大于255直接return false的情况。
T1_1 Done !
