class Solution {public: string digitSum(string s, int k) { while (s.length() > k) { string t; for (int i = 0; i < s.length(); i += k) { int sum = 0; for (int j = i; j < i + k && j < s.length(); j++) { sum += s[j] - '0'; } t += to_string(sum); } s = t; } return s; }};
2. Minimum Rounds to Complete All Tasks
Take a hash-map to count the frequency of each number.
Greedy, given a frequency x of some task:
If x mod 3 = 0, then take 3-tasks x / 3 times.
If x mod 3 = 1,
If x = 1, then not possible,
Otherwise, then take 3-tasks x / 3 - 1 times and 2-tasks twice.
If x mod 3 = 2, then take 3-tasks x / 3 times and 2-tasks once.
Time complexity: O(n).
● ● ●c++
class Solution {public: int minimumRounds(vector<int>& tasks) { unordered_map<int, int> cnt; for (auto &t : tasks) { cnt[t]++; } int ans = 0; for (auto &pair : cnt) { int x = pair.second; if (x == 1) { return -1; } if (x % 3 == 0) { ans += x / 3; } if (x % 3 == 1) { ans += (x / 3 - 1) + 2; } if (x % 3 == 2) { ans += x / 3 + 1; } } return ans; }};
3. Maximum Trailing Zeros in a Cornered Path
Given a number x, we can factorize x into the number of 2 (c2) and the number of 5 (c5). And we know the number of tailing zeros is min(c2, c5).
Based on that, we can perform 2-d preffix sum from 4 different directions.
Time complexity: O(nm)
● ● ●c++
const vector<pair<int, int>> kDir = { { -1, 0 }, { +1, 0 }, { 0, -1 }, { 0, +1 }};class Solution {private: int n, m; vector<vector<int>> f2; vector<vector<int>> f5; vector<vector<vector<int>>> sf2; vector<vector<vector<int>>> sf5; int getsf2(int d, int x, int y) { if (x < 0 || x >= n || y < 0 || y >= m) { return 0; } if (sf2[d][x][y] == -1) { sf2[d][x][y] = f2[x][y] + getsf2(d, x + kDir[d].first, y + kDir[d].second); } return sf2[d][x][y]; } int getsf5(int d, int x, int y) { if (x < 0 || x >= n || y < 0 || y >= m) { return 0; } if (sf5[d][x][y] == -1) { sf5[d][x][y] = f5[x][y] + getsf5(d, x + kDir[d].first, y + kDir[d].second); } return sf5[d][x][y]; }public: int maxTrailingZeros(vector<vector<int>>& grid) { n = grid.size(), m = grid.front().size(); f2 = vector<vector<int>>(n, vector<int>(m, 0)); f5 = vector<vector<int>>(n, vector<int>(m, 0)); for (int i = 0; i < n; i++) { for (int j = 0; j < m; j++) { while (grid[i][j] >= 2 && grid[i][j] % 2 == 0) { f2[i][j]++; grid[i][j] /= 2; } while (grid[i][j] >= 5 && grid[i][j] % 5 == 0) { f5[i][j]++; grid[i][j] /= 5; } } } sf2 = vector<vector<vector<int>>>(4, vector<vector<int>>(n, vector<int>(m, -1))); sf5 = vector<vector<vector<int>>>(4, vector<vector<int>>(n, vector<int>(m, -1))); int ans = 0; for (int x = 0; x < n; x++) { for (int y = 0; y < m; y++) { for (int d1 = 0; d1 < 4; d1++) { for (int d2 = d1 + 1; d2 < 4; d2++) { int c2 = getsf2(d1, x, y) + getsf2(d2, x, y) - f2[x][y]; int c5 = getsf5(d1, x, y) + getsf5(d2, x, y) - f5[x][y]; ans = max(ans, min(c2, c5)); } } } } return ans; }};
4. Longest Path With Different Adjacent Characters
Remove the edges where two connecting nodes have same character.
Then we can do a DFS to find the longest path within this undirected acyclic graph.
Time complexity: O(n).
● ● ●c++
class Solution {private: vector<vector<int>> edges_; vector<bool> v_; int ans = 0; int dfs(int x) { v_[x] = true; int m1 = 0, m2 = 0; for (auto &y : edges_[x]) { if (!v_[y]) { int tmp = dfs(y); if (tmp > m1) { m2 = m1; m1 = tmp; } else if (tmp > m2) { m2 = tmp; } } } ans = max(ans, m1 + m2 + 1); return 1 + m1; }public: int longestPath(vector<int>& parent, string s) { int n = parent.size(); edges_ = vector<vector<int>>(n); for (int i = 0; i < n; i++) { if (parent[i] == -1) { continue; } int x = i, y = parent[i]; if (s[x] != s[y]) { edges_[x].push_back(y); edges_[y].push_back(x); } } v_ = vector<bool>(n, false); for (int i = 0; i < n; i++) { if (!v_[i]) { dfs(i); } } return ans; }};