实现一个算法,确定一个字符串 s 的所有字符是否全都不同。
示例 1:
输入: s = “leetcode”
输出: false
示例 2:
输入: s = “abc”
输出: true
限制:
0 <= len(s) <= 100
如果你不使用额外的数据结构,会很加分。
题意:给一个字符串,让我们判断是否没有重复的字符。
数组求解
思路一(数组):我们使用一个长度为125位的数组来分别代表a-z,A-Z出现的个数,统计后遍历一遍如果相同位置的值大于1就说明有重复的字符。
代码:
//数组求解 class Solution { public boolean isUnique(String astr) { // 如果字符串长度超过了52(大小写加一起总共52),肯定是有重复的啊,直接return false if(astr.length()>52) return false; //定义一个数组,来存放a-z,A-Z的个数 //97+26=123 int [] a = new int[125]; //初始化一下 for (int i = 0; i < 125; i++) { a[i]=0; } //遍历一遍,统计个数 for (int i = 0; i < astr.length(); i++) { int k=0; k=astr.charAt(i); a[k]++; } //a[i]>1就代表同一个字符出现了两次,return false for (int i = 0; i < 125; i++) { if(a[i]>1) return false; } return true; } }
位运算求解
思路二(位运算):使用一个long类型的数字,long类型是64位,大写字母’A’的ASCII码是65,小写字母’z’的ASCII码是122,两者相差58(122-65+1=58,加1是因为这里要包含大写字母’A’),是小于64的,所以足够了,用每一位存储每一个字符,比如右边第1位存储大写字符’A’,右边第2位存储大写字符’B’……,以此类推。然后再遍历字符串中的字符,先判断对应的位置是否是1,如果是1,就表示已经存在了,直接返回false,如果对应的位置不是1,说明这个字符还没出现过,然后把对应的位置置为1。
代码:
//位运算求解 class Solution { public boolean isUnique(String astr) { long bits =0 ; int len = astr.length(); for (int i = 0; i < len; i++) { int move = astr.charAt(i)-'A'; // 0010&0010=0010 ,!=0就是 bits的某个位置存在的字符和当前这个相同了,就代表有重复的 if((bits&(1L<<move))!=0){ //有重复的,直接返回false return false; }else{ //标记当前位置有字符 bits |= (1L<<move); } } return true; } }
双层循环求解
思路三(双层循环):双层循环遍历下,碰到相同的就return false即可。
代码:
//双层循环求解 class Solution { public boolean isUnique(String astr) { for (int i = 0; i < astr.length(); i++) { for (int j = i+1; j < astr.length(); j++) { //存在相同的字符 if(astr.charAt(i)==astr.charAt(j)) return false; } } return true; } }
测试代码
完整代码(含测试过程):
package com.Keafmd.day0104; /** * Keafmd * * @ClassName: IsUnique * @Description: 判定字符是否唯一 * @author: 牛哄哄的柯南 * @date: 2021-01-04 21:21 */ public class IsUnique { public static void main(String[] args) { Solution0104 solution = new Solution0104(); String s1="abc"; String s2="leetcode"; String s3="Aabc"; boolean result = solution.isUnique(s3); System.out.println(result); int a= 0|2; //2 int b= 2&2; //2 //System.out.println(a); //System.out.println(b); } } //数组求解 class Solution0104 { public boolean isUnique(String astr) { // 如果字符串长度超过了52(大小写加一起总共52),肯定是有重复的啊,直接return false if(astr.length()>52) return false; //定义一个数组,来存放a-z,A-Z的个数 //97+26=123 int [] a = new int[125]; //初始化一下 for (int i = 0; i < 125; i++) { a[i]=0; } //遍历一遍,统计个数 for (int i = 0; i < astr.length(); i++) { int k=0; k=astr.charAt(i); a[k]++; } //a[i]>1就代表同一个字符出现了两次,return false for (int i = 0; i < 125; i++) { if(a[i]>1) return false; } return true; } } //位运算求解 class Solution01041 { public boolean isUnique(String astr) { long bits =0 ; int len = astr.length(); for (int i = 0; i < len; i++) { int move = astr.charAt(i)-'A'; // 0010&0010=0010 ,!=0就是 bits的某个位置存在的字符和当前这个相同了,就代表有重复的 if((bits&(1L<<move))!=0){ //有重复的,直接返回false return false; }else{ //标记当前位置有字符 bits |= (1L<<move); } } return true; } } //双层循环求解 class Solution01042 { public boolean isUnique(String astr) { for (int i = 0; i < astr.length(); i++) { for (int j = i+1; j < astr.length(); j++) { //存在相同的字符 if(astr.charAt(i)==astr.charAt(j)) return false; } } return true; } }