01.01. 判定字符是否唯一

1、题目

实现一个算法，确定一个字符串 s 的所有字符是否全都不同。

2、初步作答

2.1 思路（错误）

作为从C转过来的 java 选手，做题目第一时间想到的是利用两重 for 循环判断字符串是否相同。

2.2 做法（错误）

使用 for 循环遍历字符串S（这里把字符串当成了数组去操作，实操太少，自己太笨），再嵌套一层 for 循环遍历S，遍历过程中如果遇到相同字符，就返回 false ；循环结束，如果全部遍历结束没有返回 false ，那么就返回 true 。

2.3 代码（错误）

错误解法

class Solution {
    public boolean isUnique(String astr) {
        if(astr == null){
            return true;
        }
        for(int i = 0;i < s.length;i++){
            for(int j = i+1;j < s.length;j++){
                if(astr[i] == astr[j]){
                    return false;
                }
            }
        }
        return true;
    }
}

• 这里是错误思路的解法，当然就是错误解法啦。

2.4 思考

刷题经历太少导致学过的数据结构算法不知道该怎么使用，只会简单的循环结构叠加（弊端显现啊，属于是）。同时，字符串不是数组，这简直就是语文当英语看，从头错到尾。

3、题目解析

3.1 思路说明

理解到自己的错误就去推翻之前的错误重新再来，那在这里我们还需要多考虑几种情况。

• 字符串是否为空，空字符串所有字符肯定全部不相同，直接返回 true；

• 字符串中字符的范围是什么？

  • 1.如果是26个英文字母，就有两种情况需要讨论

    • (1) 只能是小写或大写字母

      • ① 字符串长度大于26直接返回 false；
      • ② 字符串长度小于26时，定义一个大小为26的全0数组。遍历字符串，以'a'=0~'z'=26或'A'=0~'Z'=26 为数组下标，每个字符出现一次相应的数组位加1，如果数组中出现大于1的数时，返回false；如果遍历结束之后，数组所有元素都是0或1，则返回 true。
      • 备注：这里使用两步判断是为了节省运算时间和空间消耗，如果字符串长度大于26，就不用开辟一个数组空间，同时节省了判断的时间消耗。

    • (2) 大小写字母都可以

      • ① 字符串长度大于52直接返回 false；
      • ② 字符串长度小于52时，定义一个大小为52的全0数组。遍历字符串，以'a'=0~'z'=26并且'A'=27~'Z'=52 为数组下标，每个字符出现一次相应的数组位加1，如果数组中出现大于1的数时，返回false；如果遍历结束之后，数组所有元素都是0或1，则返回 true。

  • 2.如果是ASCII码，那么总共范围就是128

  • 3.如果是Unicode，没有字符要求，那么就老老实实排序再判断

• 本题也可以直接使用字符串索引查询的方法来判断 ( S.charAt() )

• 题目说明不使用额外的数据结构算法，那么这道题最本质的还是使用位运算（不太会位运算，敲，这就去学习一下）

3.2 代码

3.2.1 使用HashMap

class Solution {
    public boolean isUnique(String astr) {
        if(astr == null){
            return true;
        }
      Map<Character,Integer> map = new HashMap<>();
        for(int i = 0; i< astr.length();i++){
            if(map.containsKey(astr.charAt(i))){
                return false;
            }
            map.put(astr.charAt(i),i);
        }
        return true;
    }
}

3.2.2 使用位运算

class Solution {
    public boolean isUnique(String astr) {
     	int mark = 0;
        for (int i = 0; i < astr.length() ; i++) {
            //移动距离
            int move = (int)astr.charAt(i) - 'a';
           	if ((mark & (1 << move) )!=0){
               	return false;
           	}else {
               	mark |=(1 << move);
           	}
        }
        return true;
}

3.3.3 使用索引比较的方法（初步思路优化）

class Solution {
    public boolean isUnique(String astr) {
        if(astr == null){
            return true;
        }
        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;
    }
}

---

01.02. 判定是否互为字符重排

1、题目

给定两个字符串 s1 和 s2，请编写一个程序，确定其中一个字符串的字符重新排列后，能否变成另一个字符串。

2、初步作答

2.1 思路

一个字符串重新排列，仅是字符顺序变化，字符串长度不变，s1 和 s2 长度应一致。排列过程中要记录字符串中字符是否已经使用，使用过的字符不可二次使用。最终，所有字符全部使用，则字符串重排成功。

2.2 做法

• s2 如果由 s1 重新排列，那么两个字符串长度一定相同。所以，如果字符串长度不同，直接返回false；
• 新建一个数组，记录字符串中字符使用情况；
• 我们这里使用 for 循环遍历 s1 中每一个字符，如果字符排列使用，则相应下标数组加 1 ；
• 比较数组之和与字符串长度是否匹配，匹配则返回 true，反之返回 false；

2.3 代码

class Solution {
    public boolean CheckPermutation(String s1, String s2) {
        if(s1.length() != s2.length()){
            return false;
        }
        int[] num = new int[s1.length()];
        for(int i = 0;i < s1.length();i++){
            for(int j = 0;j < s2.length();j++){
                if(num[j] == 1){
                    continue;
                }
                if(s1.charAt(i) == s2.charAt(j)){
                    num[j] = 1;
                    break;
                }
            }
        }
        int sum = 0;
        for(int m = 0;m < s1.length();m++){
            sum += num[m];
        }
        if(sum == s1.length()){
            return true;
        }else{
            return false;
        }
    }
}

代码运行情况
执行用时：0 ms, 在所有 Java 提交中击败了100.00%的用户
内存消耗：39.1 MB, 在所有 Java 提交中击败了5.27%的用户
通过测试用例：23 / 23

2.4 思考

这里定义了一个数组，导致内存消耗偏大。所以代码优化上，应着重考虑降低内存消耗。

3、题目解析

3.1 字符数组排序比较

class Solution {
    public boolean CheckPermutation(String s1, String s2) {
        char[] s1char = s1.toCharArray();
        Arrays.sort(s1char);
        char[] s2char = s2.toCharArray();
        Arrays.sort(s2char);
        return new String(s1char).equals(new String(s2char));
    }
}

3.2 哈希算法

class Solution {
    public boolean CheckPermutation(String s1, String s2) {
        int len1 = s1.length(), len2 = s2.length();
        if (len1 != len2)
            return false;
        HashMap<Character, Integer> dic = new HashMap<>();
        for (int i = 0; i < len1; i++) {
            dic.put(s1.charAt(i) , dic.getOrDefault(s1.charAt(i), 0) + 1);
        }
        for (int i = 0; i < len2; i++) {
            dic.put(s2.charAt(i) , dic.getOrDefault(s2.charAt(i), 0) - 1);
        }
        for (int val : dic.values()) {
            if (val != 0)
                return false;
        }
        return true;
    }
}

• 几种方法在内存消耗上都有缺陷，如果有更好的算法，可以告诉我，谢谢