2021-04-24 Daily-Challenge
Today is Saturday, I gonna review the tasks I've done this week, and finish today's leetcode's April LeetCoding Challenge with cpp
.
LeetCode Review
K Closest Points to Origin
too easy to review
Count Items Matching a Rule
too easy to review
Decode Ways
already reviewed
Decode Ways II
const int MOD = 1e9 + 7;
auto speedup = []() {
std::ios::sync_with_stdio(false);
cin.tie(nullptr);
cout.tie(nullptr);
return nullptr;
}();
constexpr inline int mul(int a, int b) {
int result = 0;
while(b) {
if(b & 1) {
result += a;
result %= MOD;
}
b >>= 1;
a += a;
a %= MOD;
}
return result;
}
class Solution {
public:
int numDecodings(string s) {
int len = s.length();
vector<int> dp(len + 1);
dp[0] = 1;
for(int i = 0; i < len; ++i) {
char prev = i ? s[i - 1] : -1;
if(s[i] == '*') {
dp[i + 1] = mul(dp[i], 9);
if(prev == '1') {
dp[i + 1] += mul(dp[i - 1], 9);
dp[i + 1] %= MOD;
}
if(prev == '2') {
dp[i + 1] += mul(dp[i - 1], 6);
dp[i + 1] %= MOD;
}
if(prev == '*') {
dp[i + 1] += mul(dp[i - 1], 15);
dp[i + 1] %= MOD;
}
} else {
if(s[i] < '7' && (prev == '2' || prev == '*')) {
dp[i + 1] += dp[i - 1];
dp[i + 1] %= MOD;
}
if(prev == '1' || prev == '*') {
dp[i + 1] += dp[i - 1];
dp[i + 1] %= MOD;
}
if(s[i] != '0') {
dp[i + 1] += dp[i];
dp[i + 1] %= MOD;
}
}
if(!dp[i] && !dp[i + 1]) return 0;
// cout << dp[i + 1][10] << ' ';
}
// cout << endl;
return dp.back();
}
};
// Runtime: 20 ms, faster than 100.00% of C++ online submissions for Decode Ways II.
// Memory Usage: 16.9 MB, less than 59.65% of C++ online submissions for Decode Ways II.
long long is quicker, even larger
const int MOD = 1e9 + 7;
auto speedup = []() {
std::ios::sync_with_stdio(false);
cin.tie(nullptr);
cout.tie(nullptr);
return nullptr;
}();
class Solution {
public:
int numDecodings(string s) {
int len = s.length();
vector<long long> dp(len + 1);
dp[0] = 1;
for(int i = 0; i < len; ++i) {
char prev = i ? s[i - 1] : -1;
if(s[i] == '*') {
dp[i + 1] = dp[i] * 9;
if(prev == '1') dp[i + 1] += dp[i - 1] * 9;
if(prev == '2') dp[i + 1] += dp[i - 1] * 6;
if(prev == '*') dp[i + 1] += dp[i - 1] * 15;
} else {
if(s[i] < '7' && (prev == '2' || prev == '*')) dp[i + 1] += dp[i - 1];
if(prev == '1' || prev == '*') dp[i + 1] += dp[i - 1];
if(s[i] != '0') dp[i + 1] += dp[i];
}
dp[i + 1] %= MOD;
if(!dp[i] && !dp[i + 1]) return 0;
// cout << dp[i + 1][10] << ' ';
}
// cout << endl;
return dp.back();
}
};
// Runtime: 16 ms, faster than 100.00% of C++ online submissions for Decode Ways II.
// Memory Usage: 21.7 MB, less than 33.01% of C++ online submissions for Decode Ways II.
Human Traffic of Stadium
no need to review
Number of Lines To Write String
too easy to review
Binary Tree Preorder Traversal
no need to review
Binary Tree Inorder Traversal
no need to review
Binary Tree Postorder Traversal
no need to review
Longest Happy String
no need to review
Combination Sum
too easy to review
Combination Sum II
too easy to review
Combination Sum III
too easy to review
Combination Sum IV
too easy to review
N-ary Tree Preorder Traversal
too easy to rewrite with recursion or stack
Triangle
no need to review
Brick Wall
no need to review
Count Binary Substrings
too easy to review
April LeetCoding Challenge 24
Description
Critical Connections in a Network
There are n
servers numbered from 0
to n-1
connected by undirected server-to-server connections
forming a network where connections[i] = [a, b]
represents a connection between servers a
and b
. Any server can reach any other server directly or indirectly through the network.
A critical connection is a connection that, if removed, will make some server unable to reach some other server.
Return all critical connections in the network in any order.
Example 1:
Input: n = 4, connections = [[0,1],[1,2],[2,0],[1,3]]
Output: [[1,3]]
Explanation: [[3,1]] is also accepted.
Constraints:
1 <= n <= 10^5
n-1 <= connections.length <= 10^5
connections[i][0] != connections[i][1]
- There are no repeated connections.
Solution
learning tarjan algorithm
class Solution {
vector<vector<int>> neighbors;
vector<int> num;
vector<int> low;
int count = 0;
void init(int n, vector<vector<int>>& connections) {
num.resize(n);
low.resize(n);
neighbors.resize(n);
for(auto &edge : connections) {
neighbors[edge[0]].push_back(edge[1]);
neighbors[edge[1]].push_back(edge[0]);
}
}
void tarjan(int u, int father, vector<vector<int>> &answer) {
low[u] = num[u] = ++count;
for(auto child : neighbors[u]) {
if(child == father) continue;
if(!num[child]) {
tarjan(child, u, answer);
low[u] = min(low[u], low[child]);
if(low[child] > num[u]) {
answer.push_back({u, child});
}
} else if (num[child] < num[u]) {
low[u] = min(low[u], num[child]);
}
}
}
public:
vector<vector<int>> criticalConnections(int n, vector<vector<int>>& connections) {
init(n, connections);
vector<vector<int>> answer;
tarjan(0, 0, answer);
return answer;
}
};