题解 | 密码验证合格程序
密码验证合格程序
https://www.nowcoder.com/practice/184edec193864f0985ad2684fbc86841
使用哈希表,时间复杂度O(n)
思路:
- 条件一判断长度即可
- 条件二针对四种情况使用四个变量分别标记,遍历完进行判断
- 条件三使用哈希表保存子串和对应的起始下标,具体的:
- 如果哈希表不存在子串,说明不存在重复,直接保存
- 如果哈希表存在子串
- 如果当前子串起始下标大于等于之前子串起始下标+3,说明是独立子串重复了,不符合条件
- 否则说明子串虽然重复但是非独立,是符合条件的(这里不需要更新起始下标)
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; } }#密码验证合格程序#