[Swift]LeetCode420.强密码检验器|StrongPasswordChecker

OStack程序员社区-中国程序员成长平台 › 门户 › 编程› 移动开发›Swift 教程

原作者: [db:作者] 来自: [db:来源] 收藏邀请

★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★
➤微信公众号：为敢（WeiGanTechnologies）
➤博客园地址：山青咏芝（https://www.cnblogs.com/strengthen/）
➤GitHub地址：https://github.com/strengthen/LeetCode
➤原文地址：https://www.cnblogs.com/strengthen/p/10333099.html
➤如果链接不是山青咏芝的博客园地址，则可能是爬取作者的文章。
➤原文已修改更新！强烈建议点击原文地址阅读！支持作者！支持原创！
★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★

热烈欢迎，请直接点击！！！

进入博主App Store主页，下载使用各个作品！！！

注：博主将坚持每月上线一个新app！！！

A password is considered strong if below conditions are all met:

It has at least 6 characters and at most 20 characters.
It must contain at least one lowercase letter, at least one uppercase letter, and at least one digit.
It must NOT contain three repeating characters in a row ("...aaa..." is weak, but "...aa...a..." is strong, assuming other conditions are met).

Write a function strongPasswordChecker(s), that takes a string s as input, and return the MINIMUM change required to make s a strong password. If s is already strong, return 0.

Insertion, deletion or replace of any one character are all considered as one change.

一个强密码应满足以下所有条件：

由至少6个，至多20个字符组成。
至少包含一个小写字母，一个大写字母，和一个数字。
同一字符不能连续出现三次 (比如 "...aaa..." 是不允许的, 但是 "...aa...a..." 是可以的)。

编写函数 strongPasswordChecker(s)，s 代表输入字符串，如果 s 已经符合强密码条件，则返回0；否则返回要将 s 修改为满足强密码条件的字符串所需要进行修改的最小步数。

插入、删除、替换任一字符都算作一次修改。

Runtime: 4 ms

Memory Usage: 19.5 MB

 1 class Solution {
 2     func strongPasswordChecker(_ s: String) -> Int {
 3         var digitNum = 0
 4         var upperNum = 0
 5         var lowerNum = 0
 6 
 7         var repeatArr = Array<Int>()
 8         var lastChar = 0
 9         var repeatnum = 1
10         for c in s.unicodeScalars{
11             let num = c.value
12             if num >= 48 && num < 58{
13                 digitNum += 1
14             }
15             if num >= 65 && num < 91{
16                 upperNum += 1
17             }
18             if num >= 97 && num < 123{
19                 lowerNum += 1
20             }
21             if num == lastChar{
22                 repeatnum += 1
23             }else{
24                 if repeatnum >= 3{
25                     repeatArr.append(repeatnum)
26                 }
27                 repeatnum = 1
28             }
29             lastChar = Int(num)
30         }
31         if repeatnum >= 3{
32             repeatArr.append(repeatnum)
33         }
34         //补全三种字符需要的步骤 （插入，替换）
35         var step1 = 0
36         step1 += digitNum == 0 ? 1:0
37         step1 += upperNum == 0 ? 1:0
38         step1 += lowerNum == 0 ? 1:0
39 
40         //插入
41         if s.count < 6{
42             //不满6位 与 种类不齐都可以通过 插入同时结局 所以 取大值
43             return max(step1,6-s.count)
44         }
45         //大于6位只进行替换 和 删除，两者互斥 所以求和
46         else{
47             //至少需要的删除操作
48             let deleteStep = (s.count - 20) > 0 ? s.count - 20 : 0
49             var deleteStepTemp = deleteStep
50             for i in 0...2{
51                 if deleteStepTemp < (i+1){
52                     break
53                 }
54                 for index in 0..<repeatArr.count{
55                     if deleteStepTemp < (i+1){
56                         break
57                     }
58                     let num = repeatArr[index]
59                     if num % 3 == i && num >= 3{
60                         repeatArr[index] = num - i - 1
61                         deleteStepTemp -= (i + 1)
62                     }
63                 }
64             }
65             //需要通过替换消除3连的部署（每n个数相连 需要替换n/3个）
66             var changeStep = 0
67             for i in 0..<repeatArr.count{
68                 let num = repeatArr[i]
69                 changeStep += num/3
70             }
71             //消除3连的替换changeStep步数 和 step1步数 可以同事满足 所以取大值
72             var res = max(changeStep,step1)
73             //总步数 = 必须删除的步数 + 需要替换的步数
74             res = deleteStep + res
75             return res
76         }
77     }
78 }

Runtime: 8 ms

Memory Usage: 19.5 MB

 1 class Solution {
 2     func strongPasswordChecker(_ s: String) -> Int {
 3         var requiredChar:Int = GetRequiredChar(s)
 4         if s.count < 6
 5         {
 6             return max(requiredChar, 6 - s.count)
 7         }
 8         var replace:Int = 0
 9         var oned:Int = 0
10         var twod:Int = 0
11 
12         var i:Int = 0
13         var arrS:[Character] = Array(s)
14         while(i < s.count)
15         {
16             var len:Int = 1
17             while(i + len < s.count && arrS[i + len] == arrS[i + len - 1])
18             {
19                 len += 1
20             }
21             if len >= 3
22             {
23                 replace += len / 3
24                 if len % 3 == 0 {oned += 1}
25                 if len % 3 == 1 {twod += 2}
26             }
27             i += len
28         }
29         if s.count <= 20
30         {
31             return max(requiredChar, replace)
32         }
33         var deleteCount:Int = s.count - 20
34         replace -= min(deleteCount, oned)
35         replace -= min(max(deleteCount - oned, 0), twod) / 2
36         replace -= max(deleteCount - oned - twod, 0) / 3
37         return deleteCount + max(requiredChar, replace)
38     }
39 
40     func GetRequiredChar(_ s:String) -> Int
41     {
42         var lowercase:Int = 1
43         var uppercase:Int = 1
44         var digit:Int = 1
45         for c in s
46         {
47             if c >= "a" && c <= "z" {lowercase = 0}
48             else if c >= "A" && c <= "Z" {uppercase = 0}
49             else if c >= "0" && c <= "9" {digit = 0}
50         }
51         return lowercase + uppercase + digit
52     }
53 }