[编程题]确定字符互异

热度指数：92178 时间限制：C/C++ 3秒，其他语言6秒空间限制：C/C++ 32M，其他语言64M
算法知识视频讲解

给定一个字符串string iniString，请返回一个bool值,True代表字符串的所有字符全都不同，False代表存在相同的字符。保证字符串中的字符为ASCII字符且不允许使用额外的存储结构，字符串的长度小于等于3000。

测试样例：

"aeiou"

返回：True

"BarackObama"

返回：False

算法知识视频讲解

推荐

Bug祥

public boolean checkDifferent(String iniString) {   
return !iniString.matches(".*(.)(.*\\1).*");
}

编辑于 2016-02-24 11:33:12 回复(86)

C/C++

小刀初试

--------------2021年02月20日10:58:48 更新修复BUG---------

1)在划分递归退出条件中`if (low>=high) return true;`这里不应该如此武断，应该再判断相邻元素的异同；

2)每次划分结束后`if (first>low...; if (first<high...`，应该判断相邻元素，而不是仅判断当前划分范围的相邻。

以上可以合并判断。

-----------------------以下为原贴，代码已修改-----------------------

看到多数人的答案，我觉得似乎有些不妥。

1）哈希法 首先char类型判断重复，用hash数组最方便，只需要256个bool类型即可，O(n)的时间（其实只要判断前257个就行了O(1)，抽屉原理），但是题目要求不能使用额外的存储结构，那么这个方法KO掉。
2）遍历那么只能用两层for循环遍历，时间复杂度为O(n*n)，但是根据抽屉原理，没必要遍历到N，只需要遍历到前257就够了，如果N<257就遍历到N，所以时间复杂度其实为O(1)!!!
3）排序既然题目要求不能使用额外空间，而参数列表没有const或引用，那么就可以对字符串排序，然后再判断，需要O（nlogn)排序，然后再遍历一遍O(n)。其实也没必要全都排序，只需前257个，同抽屉原理。

4）划分基于快速排序的partition，可以边排序边找重复 ，也即是每次partition之后，判断中间key元素与两边元素是否相同，相同则返回false，不同再进行下一轮partition.时间复杂度也是O(nlogn)，但要比排序速度快。

补充划分的实质：即将待划分元素集合按照选择的key划分为两部分：不大于key部分，和不小于key部分。因此，在每趟划分结束后，其选择的key必然是完全排序后的最终位置！亦即任何一个元素都会作为某一次划分的key（除非有重复元素），这就是为什么能使用划分解此题的原因。

综上，其实此题若改为长度为N的整形数组，不用额外空间 ，这题目就Perfect！下面贴出基于partition的代码。代码已做修改，并适配支持随机访问的容器，包括最原始的数组类型。

class Different {
    template<typename T>
    bool quick_check(T &arr, int size, int begin, int end) {
        int i = begin, j = end-1;
        auto key = arr[i];
        while (i < j) {
            while (i<j && arr[j]>=key) j--;
            arr[i] = arr[j];
            while (i<j && arr[i]<=key) i++;
            arr[j] = arr[i];
        }
        arr[i] = key;
        if (i && arr[i]==arr[i-1]) return false;
        if (i+1<size && arr[i]==arr[i+1]) return false;
        if (begin >= end-1) return true;
        return quick_check(arr, size, begin, i) && quick_check(arr, size, i+1, end);
    }
public:
    bool checkDifferent(string &iniString) {
        // write code here
        return quick_check(iniString, iniString.size(), 0, iniString.size());
    }
};

编辑于 2021-02-20 11:10:57 回复(19)

Pisces

import java.util.*;

public class Different {
  public boolean checkDifferent(String str) {
        //使用异或,因为让支持ASCII所以判断下长度，长度超了，肯定重复
       if(str.length()>256)return false;
        for (int i = 0;i<str.length();i++) {
            for (int j = i+1;j<str.length();j++) {
                if ((str.charAt(i)^str.charAt(j))==0)
                    return false;
            }
        }
        return true;
    }

    
}

编辑于 2016-04-09 21:25:09 回复(10)

Python

华科平凡

python solution:

# -*- coding:utf-8 -*-
class Different:
    def checkDifferent(self, iniString):
        # write code here
        return len(iniString)==len(set(iniString))

发表于 2017-10-01 20:07:54 回复(5)

周星星_

太奇葩了！！！

我发现一个样例包含转义字符的：

D-5H0F6T%Z?QM9,\72:[A8X! ;YJ#

其中\72刚好是字符:

按照题目要求，不能转义，返回True是正确的。

这里大部分回答都没有处理转义的情况，所以在本地必然返回False

要么这个样例是错误的，不应该出现这类情况。要么牛客的样例测试有bug

比如下面的代码，在牛客都可以通过，

但是在本地无法通过这个转义样例！！

c++版

class Different {
public:
    bool checkDifferent(string iniString) {
        int a[256] = {0};
        for(int i = 0; i < iniString.size(); i ++)
        {
            //cout<<i<<" "<<(int)(iniString[i])<<endl;//无法通过转义的样例
            int x = iniString[i];
            a[x] ++;
            if(a[x] > 1) return false;
        }
        return true;
    }
};

python版

# -*- coding:utf-8 -*-
class Different:
    def checkDifferent(self, iniString):
        for i in range(len(iniString)):
            for j in range(i+1,len(iniString)):
                if iniString[i]==iniString[j]:
                    return False
        return True

发表于 2016-07-18 15:15:22 回复(12)

Prokias

class Different {
public:
    bool checkDifferent(string iniString) {
        // write code here
        sort(iniString.begin(), iniString.end());
        if(unique(iniString.begin(), iniString.end()) == iniString.end()) return true;
        else return false;
    }
};

很少贴代码出来，这题习惯性的看了讨论区，没有看到比较好的，贴出来和大家一起探讨。

发表于 2015-07-25 20:02:38 回复(20)

Ron

import java.util.*;

public class Different {
    public boolean checkDifferent(String iniString) {
        // write code here
    	boolean[] charset = new boolean[65536];
    	for(int i = 0;i < iniString.length(); i++){
    		int val = iniString.charAt(i);
    		if(charset[val]){
    			return false;
    		}
    		charset[val] = true;
    	}
    	return true;
    }
}

编辑于 2016-04-18 15:43:21 回复(20)

晓宇大美女~

import java.util.*;

public class Different {
    public boolean checkDifferent(String iniString) {
        int iniLength = iniString.length();
        char[] charArray = iniString.toCharArray();
        TreeSet<Character> after = new TreeSet<Character>();
        for(int i = 0;i<charArray.length;i++){
        	after.add(charArray[i]);
        }
        int afterLength = after.size();
        if(afterLength==iniLength)
        	return true;
        return false;
    }
}

发表于 2016-07-19 22:16:57 回复(8)

C++牛起来吧

class Different {

public:

bool checkDifferent(string iniString) {

for (auto &i : iniString) //i为iniString中字符的引用，不占内存

{

for (auto &j : iniString) //j为 iniString中字符的引用，不占内存

{

if ((i == j)&&(&i != &j)) //i和j相同，i和j地址不同，表示有重复，返回false

{

return false;

}

}//不存在相同的字符，返回ture

return true;

}

};

发表于 2015-12-04 15:18:55 回复(1)

九城城主

思路：ASIIC字符值是0 ~ 255，因此可以建立一个大小为256的int型数组a[256]，用来记录每个字符对应的出现的次数。将a[256]各元素初始化为0。

对字符串的处理如下：

1）如果字符串长度大于256，则必然有重复的字符出现，返回false；

2）如果字符串长度小于256，则对每个元素从i = 0 ~ iniString.length() - 1进行遍历，将字符initString[i]转化为int值x，然后对应的计数a[x] ++，如果a[x]的值超过1，则有此元素重复出现，返回false。

遍历完成退出，返回true。

代码如下所示：

class Different {
public:
    bool checkDifferent(string iniString) {
        // write code here
        int a[256] = {0};
        int len = iniString.length(), i;
        if(len > 256)
            return false;
        for(i = 0; i < len; i ++)
            {
            int x = iniString[i];
            a[x] ++;
            if(a[x] > 1)
                return false;
        }
        return true;
    }
};

编辑于 2016-02-24 11:28:00 回复(22)

Python

谭锅锅

# -*- coding:utf-8 -*-

class Different:

def checkDifferent(self, iniString):

# write code here

if len(iniString) == len(set(iniString)):

return True

else:

return False

python就这样写就可以了额，set会去重，如果有重复的长度就不一样了，否则，就是没重复的哈

发表于 2016-12-01 21:21:10 回复(3)

喜欢国企不想奋斗的废物

class Different {

public:

bool checkDifferent(string iniString)

{

bool flag[128] = {false};

for (auto it = iniString.cbegin(); it != iniString.cend(); ++it)

{

if (!flag[*it])

flag[*it] = true;

else

return false;

}

return true;

}

};

发表于 2015-09-07 10:38:46 回复(0)

cap_liu

利用异或的特性很好弄
public boolean checkDifferent(String iniString) {
        // write code here
        char temp=iniString.charAt(0);
		int i=0;
		for(i=1;i<iniString.length();i++){
			if((temp^iniString.charAt(i))==0)
				return false;
		}
		return true;
    }

发表于 2015-09-15 15:13:18 回复(14)

C/C++

konishi

不定义任何存储结构，只需要两个循环变量：

class Different {
public:
    bool checkDifferent(string iniString) {
        // write code here
        for(size_t i = 0; i < iniString.size(); i++)
        {
            for(size_t j = 0; j < iniString.size(); j++)
            {
                if((iniString[i] == iniString[j]) && (i != j))
                    return false;
            }
        }
        return true;
    }
};

发表于 2019-10-23 17:31:06 回复(0)

Slotherver

跟一楼的大佬比我就是个渣渣啊。。。

import java.util.*;

public class Different {
public boolean checkDifferent(String iniString) {
char[] string = iniString.toCharArray();
for(int i = 0; i < string.length; i++){
int tmp = string[i];
for(int j = i + 1; j < string.length; j++)
if( tmp == string[j])
return false;
}
return true;
}
}

发表于 2018-03-20 17:51:38 回复(1)

Java

༺既༒合༻

//这道题理解起来并不是很难
public static boolean checkDifferent(String iniString) {
            //先将字符串转换成字符数组
		char[] str = iniString.toCharArray();
            //定义跳出二层循环条件
		boolean find = false;
		for (int i = 0; i < str.length && !find; i++) {
			for (int j = i+1; j < str.length; j++) {
                                //当发现相同字符时，修改条件，直接跳出二层循环
				if (str[i] == str[j]) {
					find = true;
					break;
				}
			}
		}
                //返回查找结果
		return !find;
	}

编辑于 2018-02-13 23:37:50 回复(1)

Python

jay3zhang

python思路：

1. 对字符串中的每一个字母计数，出现大于1就返回False。

2. set()去重，比较长度是否变化。

3. 依次取字母，看该字母是否在切片后(切掉包括该字母之前的所有字母)的字符串中

发表于 2017-06-05 11:14:03 回复(1)

rs勿忘初心

先用sort()函数排序，对于字符串如sort(str.begin(),str.end());然后遍历字符串，相邻直接进行比较。

class Different {
public:
    bool checkDifferent(string iniString) {
        // write code here       
        sort(iniString.begin(),iniString.end());
        for(int i=0;i<iniString.size();i++)
          {         
              if(iniString[i]==iniString[i-1])
              return false;
          }
        return true;
    }
};

发表于 2017-04-28 20:29:21 回复(0)

Java

江南消夏

import java.util.*;

public class Different {
    public boolean checkDifferent(String iniString) {
        
        for (int i=0; i<iniString.length(); i++)
            for (int j=i+1; j<iniString.length(); j++){
            if (iniString.charAt(i) == iniString.charAt(j))
                return false;
        }
        
        return true;
        // write code here
    }
}

发表于 2016-12-30 10:52:48 回复(0)

crazychen

importjava.util.*;
 
publicclassDifferent {
    public boolean checkDifferent(String iniString) {
        int[] flag =new int[1000];
        for(inti=0;i<iniString.length();i++){
            charc = iniString.charAt(i);
            if(flag[c]>0)return false;
            else flag[c] =1;
        }
        return true;
    }
}

发表于 2015-07-12 12:02:04 回复(7)

ChenYou

    bool checkDifferent(string iniString) {
        // write code here
        char f = iniString[0];
        for(int i = 1; i < iniString.length(); i++) 
            if(f == iniString[i]) return false;
        return true;
    }

这样的也能过？测试用例是不是太弱了。。。

发表于 2015-12-02 22:23:32 回复(5)