首页 > 试题广场 > 确定字符互异
[编程题]确定字符互异
  • 热度指数:92178 时间限制: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 回复(86)
--------------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)
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)
利用异或的特性很好弄
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)
不定义任何存储结构,只需要两个循环变量:
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)
    先用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)
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)
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)