解题思路

这道题需要检查密码是否满足安全规范，并计算最少的修改次数。主要规则：

  1. 长度在6-20个字符之间
  2. 必须包含小写字母、大写字母和数字
  3. 不能有连续3个相同字符

解题步骤：

  1. 统计密码中的字符类型（小写、大写、数字）
  2. 检查连续重复字符
  3. 根据不同情况计算最少修改次数：
    • 长度小于6时，需要添加字符
    • 长度大于20时，需要删除字符
    • 缺少必需字符类型时，需要添加或替换
    • 有连续重复字符时，需要修改或删除

代码

#include <iostream>
#include <string>
using namespace std;

int main() {
    string s;
    cin >> s;
    int len = s.size();
    int lower = 0, upper = 0, num = 0;
    int cnt = 0, rep = 0;
    int res = 0;
    
    // 检查字符类型和连续重复
    for(int i = 0; i < s.size(); ++i) {
        if(cnt > 0 && s[i] == s[i-1]) {
            ++cnt;
            if(cnt == 3) {
                ++res;
                if(len > 20) {
                    --len;
                    cnt = 2;
                } else {
                    cnt = 0;
                    ++rep;
                }
            }
        } else cnt = 1;

        if(islower(s[i])) lower = 1;
        else if(isupper(s[i])) upper = 1;
        else if(isdigit(s[i])) num = 1;
    }

    // 计算需要添加的字符类型数量
    int missing_types = 3 - lower - upper - num;
    if(rep >= missing_types) missing_types = 0;
    else missing_types -= rep;

    // 计算最终需要的修改次数
    if(len < 6) {
        res += max(6-len, missing_types);
    } else if(len > 20) {
        res += len - 20;  // 删除多余字符
        res += missing_types;  // 添加缺少的字符类型
    } else {
        res += missing_types;
    }
    
    cout << res << endl;
    return 0;
}

import java.util.Scanner;

public class Main {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        String s = sc.nextLine();
        int len = s.length();
        int lower = 0, upper = 0, num = 0;
        int cnt = 0, rep = 0;
        int res = 0;
        
        // 检查字符类型和连续重复
        for(int i = 0; i < s.length(); i++) {
            if(cnt > 0 && s.charAt(i) == s.charAt(i-1)) {
                ++cnt;
                if(cnt == 3) {
                    ++res;
                    if(len > 20) {
                        --len;
                        cnt = 2;
                    } else {
                        cnt = 0;
                        ++rep;
                    }
                }
            } else cnt = 1;

            char c = s.charAt(i);
            if(Character.isLowerCase(c)) lower = 1;
            else if(Character.isUpperCase(c)) upper = 1;
            else if(Character.isDigit(c)) num = 1;
        }

        int missing_types = 3 - lower - upper - num;
        if(rep >= missing_types) missing_types = 0;
        else missing_types -= rep;

        if(len < 6) {
            res += Math.max(6-len, missing_types);
        } else if(len > 20) {
            res += len - 20;
            res += missing_types;
        } else {
            res += missing_types;
        }
        
        System.out.println(res);
    }
}

def check_password(s: str) -> int:
    length = len(s)
    lower = upper = num = 0
    cnt = rep = res = 0
    
    # 检查字符类型和连续重复
    for i in range(len(s)):
        if cnt > 0 and s[i] == s[i-1]:
            cnt += 1
            if cnt == 3:
                res += 1
                if length > 20:
                    length -= 1
                    cnt = 2
                else:
                    cnt = 0
                    rep += 1
        else:
            cnt = 1
            
        if s[i].islower(): lower = 1
        elif s[i].isupper(): upper = 1
        elif s[i].isdigit(): num = 1
    
    missing_types = 3 - lower - upper - num
    if rep >= missing_types:
        missing_types = 0
    else:
        missing_types -= rep
    
    if length < 6:
        res += max(6-length, missing_types)
    elif length > 20:
        res += length - 20
        res += missing_types
    else:
        res += missing_types
        
    return res

s = input()
print(check_password(s))

算法及复杂度

  • 算法：贪心策略
  • 时间复杂度： - 其中 是字符串长度，需要遍历一次字符串
  • 空间复杂度： - 只使用了常数级别的额外空间