LintCode领扣 题解丨阿里高频面试题:密码强度检查器-阿里云开发者社区

开发者社区> 算法编程> 正文

LintCode领扣 题解丨阿里高频面试题:密码强度检查器

简介: LintCode领扣 题解丨阿里高频面试题:密码强度检查器

当以下条件都满足时,一个密码被视为是强密码:

至少包含6个字符,但不超过20个字符。
至少包含一个小写字母,一个大写字母,和一个数字。
不能包含三个连续的重复字符("...aaa..."是弱密码,但"...aa...a..."是强密码,假设它们的其他条件都满足了)。
写一个函数strongPasswordChecker(s),它将一个字符串s作为输入,并且返回将其转换成强密码需要的最少改变次数。如果s已经是一个强密码了,返回0。

插入、删除或者替换任意一个字符都视为一次改变。

在线评测地址:https://www.lintcode.com/problem/strong-password-checker/?utm_source=sc-tc-sz0811

样例 1:

输入:"aaa123"
输出:1
解释:"aaa123"->"aaA123"
样例 2:

输入:"a"
输出:5
解释:"a"->"aa"->"aaA"->"aaA1"->"aaA12"->"aaA123"
【题解】

考点:

思维
题解:本题根据要求最小的改变次数,确定修改策略即可。

变为强密码需要解决三种问题:

长度小于6时需要插入字符,长度大于20时需要删除字符
缺失字符或数字,此时可以通过插入或者替换字符解决
出现三个及以上重复字符,利用置换解决该问题会更好,可以同时做到解决情况二和情况三。
接下来,按照长度进行讨论。

当长度小于6时,尽量采用插入操作,既可以增加长度也可以避免重复字符连续。
当长度大于等于6时,对于重复字符个数k大于等于3的情况,先将其删除到最近的(3m+2)个,那么如果k正好被3整除,那么我们直接变为k-1,如果k%3=1,那么变为k-2。这样做的好处是3m+2个重复字符可以用替换m个字符来去除重复,然后遍历一次,进行删除和替换,可以直接删除3m个,最少删除操作。
public class Solution {

/**
 * @param s: a string
 * @return: return an integer
 */
public int strongPasswordChecker(String s) {
    // write  your code here
    int res = 0, n = s.length(), lower = 1, upper = 1, digit = 1;
    int [] v = new int [n];
     for (int i = 0; i < n;) {        //遍历是否存在缺失字符种类
        if (s.charAt(i) >= 'a' && s.charAt(i) <= 'z') {
            lower = 0;
        }
        if (s.charAt(i) >= 'A' && s.charAt(i) <= 'Z') {
            upper = 0;
        }
        if (s.charAt(i) >= '0' && s.charAt(i) <= '9') {
            digit = 0;
        }
        int j = i;
        while (i < n && s.charAt(i) == s.charAt(j)) {
            ++i;
        }
        v[j] = i - j;    //标记j位置开始连续重复字符的数量
    }
    int missing = (lower + upper + digit);     //缺失的字符种类数
    if (n < 6) {
        int diff = 6 - n;                    //缺失的长度
        res += diff + Math.max(0, missing - diff);    //缺失长度加上missing - diff差值(因为增加的字符不一定补全字符种类,替换)
    } 
    else {
        int over = Math.max(n - 20, 0), left = 0;    //超出长度
        res += over;
        for (int k = 1; k < 3; ++k) {         //如果重复数量k%3==0,-1达到3m+2。如果k%3==1,-2达到3m+2
            for (int i = 0; i < n && over > 0; ++i) {
                if (v[i] < 3 || v[i] % 3 != (k - 1)) {
                    continue;
                }
                v[i] -= k;
                over -=k;            //删除字符
            }
        }
        for (int i = 0; i < n; ++i) {
            if (v[i] >= 3 && over > 0) {
                int need = v[i] - 2;        //通过-2得到3m
                v[i] -= over;
                over -= need;            //直接选择删除3m个
            }
            if (v[i] >= 3)  {        //如果v[i]>=3那么需要进行替换操作
                left += v[i] / 3;
            }
        }
        res += Math.max(missing, left);    //每次除以3即为替换的字符个数
    }
    return res;
    
}

}
更多题解参见九章算法官网:
https://www.jiuzhang.com/solution/strong-password-checker/?utm_source=sc-tc-sz0811

版权声明:本文内容由阿里云实名注册用户自发贡献,版权归原作者所有,阿里云开发者社区不拥有其著作权,亦不承担相应法律责任。具体规则请查看《阿里云开发者社区用户服务协议》和《阿里云开发者社区知识产权保护指引》。如果您发现本社区中有涉嫌抄袭的内容,填写侵权投诉表单进行举报,一经查实,本社区将立刻删除涉嫌侵权内容。

分享:
算法编程
使用钉钉扫一扫加入圈子
+ 订阅

开发者社区在线编程频道官方技术圈。包含算法资源更新,周赛动态,每日一题互动。

官方博客
链接