20.密码验证合格程序

raylan.chen大约 3 分钟

假设输入为：021Abc9Abc1；

使用暴力解法时：

长度为 3 的子字符串为 021 时，

在其他子字符串中寻找可能相同的子字符串：Abc, bc9, c9A, 9Ab, Abc, bc1；

长度为 3 的子字符串为 21A 时，

在其他子字符串中寻找可能相同的子字符串：bc9, c9A, 9Ab, Abc, bc1；

长度为 3 的子字符串为 1Ab 时，

在其他子字符串中寻找可能相同的子字符串： c9A, 9Ab, Abc, bc1；

可以发现查找是否存在与某子字符串相同的子字符串时，例如 021, 21A 或 1Ab 时，其他字符组成的子字符串存在相同的部分，那么可以尝试使用一个 Set或 Map存储所有可能的子字符串，随后在判断是否存在两个相同的子字符串时，可以利用哈希表在时间复杂度为 O(1)下查找出结果；

使用Set可能会出现，输入为 021Abc1111，

长度为3的子字符串：021, 21A, 1Ab, Abc, bc1, c11, 「111, 111」，

1111存在复用的情况；

可以尝试使用Map避免出现此类情况，key：子字符串，value：子字符串索引。

import java.util.*;

public class Main {
    public static void main(String[] args) {
        Scanner in = new Scanner(System.in);
        // 长度 > 8
        // 大/小/数/其他 >=3
        // 不存在两个长度 > 3 的子串相等(Map 存储字串判断是否重复)
        List<String> res = new ArrayList<>();
        while (in.hasNext()) {
            char[] carr = in.nextLine().toCharArray();
            // 长度
            if (carr.length <= 8) {
                res.add("NG");
                continue;
            }
            boolean lower = false;
            boolean upper = false;
            boolean digit = false;
            boolean other = false;
            int kinds = 0;
            // 统计字符种数
            for (int i = 0; i < carr.length; i++) {
                if (Character.isLowerCase(carr[i])) {
                    if (!lower) kinds++;
                    lower = true;
                } else if (Character.isUpperCase(carr[i])) {
                    if (!upper) kinds++;
                    upper = true;
                } else if (Character.isDigit(carr[i])) {
                    if (!digit) kinds++;
                    digit = true;
                } else if (!Character.isWhitespace(carr[i])) {
                    if (!other) kinds++;
                    other = true;
                }
            }
            if (kinds < 3) {
                res.add("NG");
                continue;
            }
            // 子字符串检测，子字符串长度递增：3，4，...
            boolean sub = true;
            for (int i = 2; i < carr.length; i++) {
                Map<String, int[]> map = new HashMap<>();
                // 滑动窗口，长度为 i + 1
                if (sub) {
                    for (int j = 0, k = i; k < carr.length; j++, k++) {
                        String tmp = String.valueOf(carr, j, k - j + 1);
                        if (map.containsKey(tmp)) {
                            int[] val = map.get(tmp);
                            // 021Abc1111：021, 21A, 1Ab, Abc, bc1, c11, 「111, 111」
                            if (j > val[1] || k < val[0]) {
                                sub = false;
                                res.add("NG");
                                break;
                            }
                        } else {
                            map.put(tmp, new int[]{j, k});
                        }
                    }
                } else break;
            }
            if (sub) res.add("OK");
        }
        // 打印结果
        res.forEach(System.out::println);
    }
}

题解 | #密码验证合格程序#_牛客博客

参考以上优秀题解可知，代码还可进一步缩减为：

import java.util.*;

public class Main {
    public static void main(String[] args) {
        Scanner in = new Scanner(System.in);
        // 长度 > 8
        // 大/小/数/其他 >=3
        // 不存在两个长度 > 3 的子串相等(Map 存储字串判断是否重复)
        List<String> res = new ArrayList<>();
        while (in.hasNext()) {
            char[] carr = in.nextLine().toCharArray();
            // 长度
            if (carr.length <= 8) {
                res.add("NG");
                continue;
            }
            int lower = 0;
            int upper = 0;
            int digit = 0;
            int other = 0;
            // 统计字符种数
            for (int i = 0; i < carr.length; i++) {
                if (Character.isLowerCase(carr[i])) {
                    lower = 1;
                } else if (Character.isUpperCase(carr[i])) {
                    upper = 1;
                } else if (Character.isDigit(carr[i])) {
                    digit = 1;
                } else if (!Character.isWhitespace(carr[i])) {
                    other = 1;
                }
            }
            if (lower + upper + digit + other < 3) {
                res.add("NG");
                continue;
            }
            // 子字符串检测，子字符串长度递增：3，4，...
            boolean sub = true;
            for (int i = 2; i < carr.length; i++) {
                Map<String, int[]> map = new HashMap<>();
                // 滑动窗口，长度为 i + 1
                if (sub) {
                    for (int j = 0, k = i; k < carr.length; j++, k++) {
                        String tmp = String.valueOf(carr, j, k - j + 1);
                        if (map.containsKey(tmp)) {
                            int[] val = map.get(tmp);
                            // 021Abc1111：021, 21A, 1Ab, Abc, bc1, c11, 「111, 111」
                            if (j > val[1] || k < val[0]) {
                                sub = false;
                                res.add("NG");
                                break;
                            }
                        } else {
                            map.put(tmp, new int[]{j, k});
                        }
                    }
                } else break;
            }
            if (sub) res.add("OK");
        }
        // 打印结果
        res.forEach(System.out::println);
    }
}

20.密码验证合格程序

20.密码验证合格程序

参考链接

个人尝试