题解 | 密码验证合格程序

密码验证合格程序

https://www.nowcoder.com/practice/184edec193864f0985ad2684fbc86841

使用哈希表,时间复杂度O(n)

思路:

  1. 条件一判断长度即可
  2. 条件二针对四种情况使用四个变量分别标记,遍历完进行判断
  3. 条件三使用哈希表保存子串和对应的起始下标,具体的:
  • 如果哈希表不存在子串,说明不存在重复,直接保存
  • 如果哈希表存在子串
  1. 如果当前子串起始下标大于等于之前子串起始下标+3,说明是独立子串重复了,不符合条件
  2. 否则说明子串虽然重复但是非独立,是符合条件的(这里不需要更新起始下标)

import java.util.*;

public class Main {
    public static void main(String[] args) {
        Scanner in = new Scanner(System.in);
        while (in.hasNextLine()) {
            String s = in.nextLine();
            if (isValid(s)) {
                System.out.println("OK");
            } else {
                System.out.println("NG");
            }
        }
    }

    private static boolean isValid(String s) {
        if (s.length() <= 8) {
            return false;
        }
        Map<String, Integer> map = new HashMap<>();
        int a = 0;
        int b = 0;
        int c = 0;
        int d = 0;
        for (int i = 0; i < s.length(); i++) {
            char ch = s.charAt(i);
            if (ch >= 'A' && ch <= 'Z') {
                a = 1;
            } else if (ch >= 'a' && ch <= 'z') {
                b = 1;
            } else if (ch >= '0' && ch <= '9') {
                c = 1;
            } else {
                d = 1;
            }
            if (i + 3 <= s.length()) {
                String t = s.substring(i, i + 3);
                if (!map.containsKey(t)) {
                    map.put(t, i);
                } else if (i >= map.get(t) + 3) {
                    return false;
                }
            }
        }
        return a + b + c + d >= 3;
    }
}
#密码验证合格程序#
全部评论

相关推荐

被加薪的哈里很优秀:应该继续招人,不会给你留岗位的
点赞 评论 收藏
分享
球Offer上岸👑:可能是大环境太差了 太卷了 学历也很重要 hc也不是很多 所以很难
点赞 评论 收藏
分享
评论
点赞
收藏
分享

创作者周榜

更多
牛客网
牛客网在线编程
牛客网题解
牛客企业服务