首页 > 试题广场 > 确定字符互异
[编程题]确定字符互异
  • 热度指数:88817 时间限制:C/C++ 3秒,其他语言6秒 空间限制:C/C++ 32M,其他语言64M
  • 算法知识视频讲解

请实现一个算法,确定一个字符串的所有字符是否全都不同。这里我们要求不允许使用额外的存储结构。

给定一个string iniString,请返回一个bool值,True代表所有字符全都不同,False代表存在相同的字符。保证字符串中的字符为ASCII字符。字符串的长度小于等于3000。

测试样例:
"aeiou"
返回:True
"BarackObama"
返回:False
推荐
public boolean checkDifferent(String iniString) {   
return !iniString.matches(".*(.)(.*\\1).*");
}

编辑于 2016-02-24 11:33:12 回复(85)
看到多数人的答案,我觉得似乎有些不妥。
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)Parition 基于快速排序的partition,可以边排序边找重复 ,也即是每次partition之后,判断中间key元素与两边元素是否相同,相同则返回false,不同再进行下一轮partition.时间复杂度也是O(nlongn),但要比排序速度快。

综上,其实此题若改为长度为N的整形数组,不用额外空间 ,这题目就Perfect!下面贴出基于partition的代码。
class Different {   
bool quick_check(string &str,int low,int high){
        int first = low,last = high;
        char key = str[first];
        if (low>=high)
            return true;
        while(first<last){
            while(first <last && str[last] >= key)
                last--;            
            str[first] = str[last];
            while(first<last && str[first] <= key)
                first++;
            str[last] = str[first];
        }
        str[first] = key;
        if (first>low && str[first] == str[first-1])
            return false;
        if (first<high && str[first] == str[first+1])
            return false;
        return quick_check(str,low,first-1) && quick_check(str,first+1,high);
    }
public:
    bool checkDifferent(string iniString) {
        // write code here
        return quick_check(iniString,0,iniString.size()-1);
    }
};
编辑于 2016-08-09 19:20:47 回复(15)
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 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)
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头像 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)
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)
# -*- 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)
不定义任何存储结构,只需要两个循环变量:
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)
跟一楼的大佬比我就是个渣渣啊。。。
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)
//这道题理解起来并不是很难
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思路:
1. 对字符串中的每一个字母计数,出现大于1就返回False。
2. set()去重,比较长度是否变化。
3. 依次取字母,看该字母是否在切片后(切掉包括该字母之前的所有字母)的字符串中
发表于 2017-06-05 11:14:03 回复(1)
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)
利用异或的特性很好弄
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)
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)
    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)
//题目要求不用存储结构 那我就什么存储结构也没用
//依次比较 如果发现相同的 就返回false
import java.util.*;
public class Different {
    public boolean checkDifferent(String iniString) {
        int len=iniString.length();
        for(int i=0;i<len-1;i++){
            for(int j=i+1;j<len;j++){
                if(iniString.charAt(i)==iniString.charAt(j)){
                   return false; 
                }
            }
        }
        return true;
    }
}

编辑于 2017-06-06 10:33:22 回复(3)