Skip to content

Commit eb5aadd

Browse files
liuyuboboboliuyubobobo
committed
0420 solved.
1 parent afc2ace commit eb5aadd

File tree

3 files changed

+145
-1
lines changed

3 files changed

+145
-1
lines changed

‎0001-0500/0420-Strong-Password-Checker/cpp-0420/CMakeLists.txt

Lines changed: 6 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,6 @@
1+
cmake_minimum_required(VERSION 3.21)
2+
project(cpp_0420)
3+
4+
set(CMAKE_CXX_STANDARD 14)
5+
6+
add_executable(cpp_0420 main.cpp)

‎0001-0500/0420-Strong-Password-Checker/cpp-0420/main.cpp

Lines changed: 138 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,138 @@
1+
/// Source : https://leetcode.com/problems/strong-password-checker/
2+
/// Author : liuyubobobo
3+
/// Time : 2022-04-30
4+
5+
#include <iostream>
6+
#include <vector>
7+
#include <queue>
8+
#include <cassert>
9+
#include <algorithm>
10+
11+
using namespace std;
12+
13+
14+
/// Ad-Hoc
15+
/// Time Complexity: O(|s|)
16+
/// Space Compelxity: O(|s|)
17+
class Solution {
18+
public:
19+
int strongPasswordChecker(string s) {
20+
21+
int lower = 0, upper = 0, digit = 0, other = 0;
22+
for(char c: s){
23+
if(islower(c)) lower ++;
24+
else if(isupper(c)) upper ++;
25+
else if(isdigit(c)) digit ++;
26+
else other ++;
27+
}
28+
29+
priority_queue<int> pq;
30+
for(int start = 0, i = 1; i <= s.size(); i ++)
31+
if(i == s.size() || s[start] != s[i]){
32+
if(i - start >= 3) pq.push(i - start);
33+
start = i;
34+
}
35+
36+
int need_change = !lower + !upper + !digit;
37+
int len = s.size();
38+
if(len < 6){
39+
int res = 0;
40+
while(!pq.empty() && need_change){
41+
assert(pq.top() / 3 == 1);
42+
res ++;
43+
pq.pop(); need_change --;
44+
len ++;
45+
}
46+
47+
res += pq.size(); len += pq.size();
48+
res += need_change; len += need_change;
49+
res += max(6 - len, 0);
50+
return res;
51+
}
52+
53+
if(len <= 20){
54+
return for20(pq, need_change);
55+
}
56+
57+
// len > 20
58+
vector<int> v;
59+
while(!pq.empty()) v.push_back(pq.top()), pq.pop();
60+
sort(v.begin(), v.end(), [](int a, int b){
61+
return a % 3 < b % 3;
62+
});
63+
64+
int res = 0;
65+
for(int i = 0; i < v.size() && len > 20; i ++){
66+
if(v[i] % 3 == 0){
67+
len --; v[i] --; res ++;
68+
}
69+
else if(v[i] % 3 == 1){
70+
len --; v[i] --; res ++;
71+
if(len <= 20) break;
72+
len --; v[i] --; res ++;
73+
}
74+
}
75+
76+
for(int i = 0; i < v.size() && len > 20; i ++){
77+
while(v[i] > 5 && len > 20){
78+
int t = min(len - 20, 3);
79+
v[i] -= t; len -= t; res += t;
80+
}
81+
}
82+
83+
if(len == 20){
84+
for(int e: v) pq.push(e);
85+
return res + for20(pq, need_change);
86+
}
87+
88+
for(int i = 0; i < v.size() && len > 20; i ++){
89+
int t = min(len - 20, v[i] - 2);
90+
v[i] -= t; len -= t; res += t;
91+
}
92+
93+
if(len == 20){
94+
for(int e: v) pq.push(e);
95+
return res + for20(pq, need_change);
96+
}
97+
98+
return max(len - 20, 0) + res + need_change;
99+
}
100+
101+
private:
102+
int for20(priority_queue<int>& pq, int need_change){
103+
int res = 0;
104+
while(!pq.empty() && need_change){
105+
int cur = pq.top(); pq.pop();
106+
res ++, need_change --;
107+
cur -= 3;
108+
if(cur >= 3) pq.push(cur);
109+
}
110+
111+
if(need_change) res += need_change;
112+
else{
113+
while(!pq.empty()){
114+
int cur = pq.top(); pq.pop();
115+
res += cur / 3;
116+
}
117+
}
118+
return res;
119+
}
120+
};
121+
122+
123+
int main() {
124+
125+
cout << Solution().strongPasswordChecker("a") << '\n';
126+
// 5
127+
128+
cout << Solution().strongPasswordChecker("aA1") << '\n';
129+
// 3
130+
131+
cout << Solution().strongPasswordChecker("1337C0d3") << '\n';
132+
// 0
133+
134+
cout << Solution().strongPasswordChecker("ABABABABABABABABABAB1") << '\n';
135+
// 2
136+
137+
return 0;
138+
}

‎readme.md

Lines changed: 1 addition & 1 deletion
Original file line numberDiff line numberDiff line change
@@ -450,7 +450,7 @@ email: [liuyubobobo@gmail.com](mailto:liuyubobobo@gmail.com)
450450
| 417 | [Pacific Atlantic Water Flow](https://leetcode.com/problems/pacific-atlantic-water-flow/description/) | [无] | | [Java](0001-0500/0417-Pacific-Atlantic-Water-Flow/java-0417/src/) | |
451451
| | | | | | |
452452
| 419 | [Battleships in a Board](https://leetcode.com/problems/battleships-in-a-board/) | [无] | [C++](0001-0500/0419-Battleships-in-a-Board/cpp-0419/) | | |
453-
| | | | | | |
453+
| 420 | [Strong Password Checker](https://leetcode.com/problems/strong-password-checker/) | [无] | [C++](0001-0500/0420-Strong-Password-Checker/cpp-0420/) | | |
454454
| 421 | [Maximum XOR of Two Numbers in an Array](https://leetcode.com/problems/maximum-xor-of-two-numbers-in-an-array/) | [solution](https://leetcode.com/problems/maximum-xor-of-two-numbers-in-an-array/solution/) | [C++](0001-0500/0421-Maximum-XOR-of-Two-Numbers-in-an-Array/cpp-0421/) | | |
455455
| | | | | | |
456456
| 423 | [Reconstruct Original Digits from English](https://leetcode.com/problems/reconstruct-original-digits-from-english/) | [solution](https://leetcode.com/problems/reconstruct-original-digits-from-english/solution/) | [C++](0001-0500/0423-Reconstruct-Original-Digits-from-English/cpp-0423/) | | |

0 commit comments

Comments
 (0)