LeetCode Biweekly Contest 91 Tutorial
Q2
Tutorial
An easy dp problem, for dp[i], means how many good string of length i.
Init dp[zero] = 1, dp[one] = 1 (if one == zero, then dp[one] = 2);
So dp[i] = dp[i - zero] + dp[i - one]. After calculate all dp, sum up dp[low] to dp[high].
Accepted Code
class Solution {
public:
long long dp[100005];
int countGoodStrings(int low, int high, int zero, int one) {
memset(dp, 0, sizeof(dp));
dp[zero]++;
dp[one]++;
for(int i = min(zero, one); i <= high; ++i){
if(i > zero) dp[i] += dp[i - zero];
if(i > one) dp[i] += dp[i - one];
dp[i] %= 1000000007;
}
long long ans = 0;
for(int i = low; i <= high; ++i){
ans += dp[i];
ans %= 1000000007;
}
return ans;
}
};
Q3
Tutorial
First, from root 0, bfs all tree to find where bob is. Storage the parent node of every node.
Secondly, from Bob Node, Stroage the time that bob will visit from bob node to root.
Last, from node 0, calculate alice’s maximum income to all leaf.
Accepted Code
class Solution {
public:
int bobVisTime[100005];
vector<int> to[100005];
int dp[100005];
map<int, int> par;
int res;
int mostProfitablePath(vector<vector<int>>& edges, int bob, vector<int>& amount) {
memset(bobVisTime, 0x3f3f3f3f, sizeof(bobVisTime));
memset(dp, 0, sizeof(dp));
res = INT_MIN;
for(auto i : edges){
int a = i[0], b = i[1];
to[a].push_back(b);
to[b].push_back(a);
}
fillBobVisTime(bob);
dfs(0, 0, -1, 0, amount);
return res;
}
void dfs(int a, int t, int p, int ans, const vector<int> &amount){
//printf("a = %d, t = %d, ans = %d, bobVisTime = %d\n", a, t, ans, bobVisTime[a]);
if(t == bobVisTime[a]){ //同时到达
ans += amount[a] / 2;
}
else if(bobVisTime[a] > t){ //alice先到
ans += amount[a];
}
else{ // bob先到
ans += 0;
}
for(int i : to[a]){
if(i != p) dfs(i, t + 1, a, ans, amount);
}
if(to[a].size() == 1 && a != 0){ //leaf
//printf("a = %d\n", a);
res = max(res, ans);
}
return;
}
void fillBobVisTime(int b){
queue<pair<int, int>> q;
q.push({0, 0});
while(!q.empty()){
pair<int, int> t = q.front();
q.pop();
for(int i : to[t.first]){
if(bobVisTime[i] != 0x3f3f3f3f) continue;
bobVisTime[i] = t.second + 1;
par[i] = t.first;
q.push({i, t.second + 1});
}
}
memset(bobVisTime, 0x3f3f3f3f, sizeof(bobVisTime));
int cnt = 0;
while(b != 0){
bobVisTime[b] = cnt++;
b = par[b];
}
bobVisTime[0] = cnt;
return;
}
};
Q4
Tutorial
We define an array sumL of length 1e4. sumL[11] mean the length of all string: “1”, “2”, “3”, …… , “10”, “11”.
So if there is an valid answer, we conbine all the splited string into one string, the length of the string is: message.length + sumL[b] + b * string_of_b.length + b * 3.
If we don’t ignore the last part, make all part’s length equal to limit. The check will be very easy: limit * b == message.length + sumL[b] + b * string_of_b.length + b * 3. If we could find some b(from 1 to 1e4) satisfied this equation, make it to be the answer. But now, we can except the last part of message, whose length can be at most limit. So we just change the equation to be an inequality: limit * b - message.length + sumL[b] + b * string_of_b.length + b * 3 < limit. If we could find a b satisfied this inequality, we find the answer.
Accepted Code
class Solution {
public:
int sumL[10005];
vector<string> splitMessage(string message, int limit) {
memset(sumL, 0, sizeof(sumL));
for(int i = 1; i <= 10000; ++i){
sumL[i] = sumL[i - 1] + tos(i).size();
}
for(int i = 1; i <= 10000; ++i){
if(check(i, limit, message.size())){
return del(i, message, limit);
}
}
return {};
}
inline vector<string> del(int b, string message, int limit){
vector<string> res;
int idx = 0;
string bs = tos(b);
int blen = bs.size();
for(int i = 1; i <= b; ++i){
string tres = "";
string as = tos(i);
int les = limit - 3 - blen - as.size();
tres = message.substr(idx, les) + "<" + as + "/" + bs + ">";
idx += les;
res.push_back(tres);
}
return res;
}
inline bool check(int b, int limit, int mL){
if(limit * b - (mL + b * 3 + b * tos(b).size() + sumL[b]) < limit){
return true;
}
return false;
}
inline string tos(int n){
string res = "";
while(n){
res += char(n % 10 + '0');
n /= 10;
}
reverse(res.begin(), res.end());
return res;
}
};