LeetCode 每日一题「判定字符是否唯一」

我是陈皮，一个在互联网 Coding 的 ITer，微信搜索「陈皮的JavaLib」第一时间阅读最新文章，回复【资料】，即可获得我精心整理的技术资料，电子书籍，一线大厂面试资料和优秀简历模板。

题目

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

示例1：

输入： s = "leetcode"
输出：false

示例2：

输入：s = "abc"
输出：true

限制

0 <= len(s) <= 100
如果你不使用额外的数据结构，会很加分。

题目来源：LeetCode

解法一

判断一个字符串中所有字符是否唯一，最简单的暴力求解就是两两对比是否相同，即双重循环，但是算法复杂度为 O(n^2)，性能也是最低的。如果字符串的长度是比较小的话，此算法也是勉强可以使用的。

package com.chenpi;

/**

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

 * @Author Mr.nobody

 * @Date 2021/4/18

 * @Version 1.0

 */

public class StrIsUnique {

    public boolean isUnique(String astr) {

        // 字符串为null或者为空，自然没有字符重复，即唯一

        if (null == astr || 0 == astr.length()) {

            return true;

        }

        // 双重循环，两两对比

        for (int i = 0; i < astr.length() - 1; i++) {

            for (int j = i + 1; j < astr.length(); j++) {

                if (astr.charAt(i) == astr.charAt(j)) {

                    return false;

                }

            }

        }

        return true;

    }

    public static void main(String[] args) {

        String astr = "leetcode";

        StrIsUnique strIsUnique = new StrIsUnique();

        System.out.println(strIsUnique.isUnique(astr));

    }

}

解法二

既然是判断唯一性，那我们可以遍历每一个字符，然后通过某种规则将它们放入指定位置，因为相同字符肯定会被放到相同的位置，我们只需要判断放入此位置之前是否有字符放入过，如果有，就代表有重复的字符。借助散列表这种数据结构就能达到这种效果。

package com.chenpi;

import java.util.HashMap;

import java.util.Map;

/**

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

 * @Author Mr.nobody

 * @Date 2021/4/18

 * @Version 1.0

 */

public class StrIsUnique {

    public boolean isUnique(String astr) {

        // 字符串为null或者为空，自然没有字符重复，即唯一

        if (null == astr || 0 == astr.length()) {

            return true;

        }

        Map<Character, Integer> map = new HashMap<>(astr.length() + 1);

        // 遍历每一个字符，从map中判断是否存在相同的字符

        for (int i = 0; i < astr.length(); i++) {

            // 存在相同的字符

            if (null != map.get(astr.charAt(i)) && map.get(astr.charAt(i)) == 1) {

                return false;

            }

            // 在map中不存在此字符，放入map中

            map.put(astr.charAt(i), 1);

        }

        return true;

    }

    public static void main(String[] args) {

        String astr = "陈皮的JavaLib";

        StrIsUnique strIsUnique = new StrIsUnique();

        System.out.println(strIsUnique.isUnique01(astr));

    }

}

解法三

如果我们不再借助其他数据结构，如何解法呢？因为要求唯一性，肯定要有字符比较的。解法二我们借助了散列表这种数据结构，结果内存消耗方面只击败了27.28%的用户。

假设字符串中的字符是26个小写字母，解法二是将每一个字符放入散列表中，如果散列表中每一个位置都没有重复的字符，则唯一性。那我们可以将每一个字符映射到一个二进制数组中，通过与运算，如果相同位置都为1，则结果为1，则代表有重复字符。

借助一个初始值为0的int变量mark，二进制形式为0000...0000，遍历每一个字符，计算字符与a字符的距离move_bit，然后使用左移运算符1 << move_bit创建对应下标为1，其余下标为0的数num。将num与mark做与运算，如果结果不为0，则代表有重复字符。如果结果为0，则代表这个字符之前没出现过，将num和mark通过或运算的结果赋值给mark，即在mark中将此字符的对应下标的值设为1。

package com.chenpi;

import java.util.HashMap;

import java.util.Map;

import java.util.function.BinaryOperator;

/**

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

 * @Author Mr.nobody

 * @Date 2021/4/18

 * @Version 1.0

 */

public class StrIsUnique {

    public boolean isUnique02(String astr) {

        // 字符串为null或者为空，自然没有字符重复，即唯一

        if (null == astr || 0 == astr.length()) {

            return true;

        }

        int mark = 0;

        int num = 0;

        // 遍历每一个字符

        for (int i = 0; i < astr.length(); i++) {

            num = 1 << (astr.charAt(i) - 'a');

            // 通过与运算判断对应下标是否都为1，即是否有相同字符

            if ((mark & num) != 0) {

                return false;

            }

            // 在map中将对应下标置为1

            mark |= num;

        }

        return true;

    }

    public static void main(String[] args) {

        String astr = "javalib";

        StrIsUnique strIsUnique = new StrIsUnique();

        System.out.println(strIsUnique.isUnique02(astr));

    }

}

上一题与下一题

上一题：LeetCode 每日一题「实现 strStr()」

下一题：LeetCode 每日一题「判定是否互为字符重排」

巴特西

LeetCode 每日一题「判定字符是否唯一」

题目

解法一

解法二

解法三

上一题与下一题

最新文章

热门文章