力扣 297 场周赛
第一题
解法:模仿
class Solution {public: double calculateTax(vector<vector<int>>& bs, int ie) { double ret = 0; bs.push_back({0, 0}); sort(bs.begin(), bs.end(), [](vector<int>& a, vector<int>& b) { return a[0] < b[0]; }); for (int i = 0; i < bs.size(); ++ i) { // cout << ie << " " << bs[i + 1][0] << " " << bs[0] << endl; if (i == bs.size() - 1) { }else { if (ie >= bs[i + 1][0]) { ret += (double)(bs[i + 1][0] - bs[0]) * bs[i + 1][1] / 100; }else { ret += ((double)ie - bs[0]) * bs[i + 1][1] / 100; break; } } // cout << ret << endl; } return ret; }};第二题
解法:线性 DP
dist 体现 i 这个点到最底层的间隔
- 时间复杂度 O(N * M ^ 2)
- 空间复杂度 O(N)
class Solution { public: unordered_map<int, int> row; int dist[3000]; int n, m; int minPathCost(vector<vector<int>>& grid, vector<vector<int>>& mt) { vector<int> one, last; for (int i = 0; i < grid.size(); ++ i) { for (int& j : grid) { row[j] = i; if (i == 0) one.push_back(j); if (i == grid.size() - 1) last.push_back(j); } } memset(dist, 0x3f, sizeof dist); for (int& x : last) dist[x] = 0; int n = grid.size(); for (int i = n - 2; i >= 0; -- i) { for (int j = 0; j < grid.size(); ++ j) { int x = grid[j]; for (int k = 0; k < grid[i + 1].size(); ++ k) { int v = grid[i + 1][k]; dist[x] = min(dist[x], v + mt[x][k] + dist[v]); // dist[x] += dist[v]; } } } int ret = 1e9; // cout << dist[0] << " " << dist[4] << endl; for (int& i : one) { // cout << i << " " << dist << endl; ret = min(ret, dist + i); } return ret; }};第三题
解法 1： 回溯
搜索每包零食分给每个朋侪, 每包零食有 K 种选择；
- 时间复杂度 O(N ^ k)
- 空间复杂度 O(N)
class Solution { int n, K, ans; vector<int> A, tot; void dfs(int d) { if (d == n) { // 全部零食都分完了，盘算小朋侪得到的最大饼干数 int t = tot[0]; for (int i = 1; i < K; i++) t = max(t, tot); // 全部结果里取最小 ans = min(ans, t); return; } for (int i = 0; i < K; i++) { // 枚举第 d 包零食分给第 i 个小朋侪 tot += A[d]; dfs(d + 1); // 打消修改 tot -= A[d]; } }public: int distributeCookies(vector<int>& cookies, int k) { n = cookies.size(); K = k; A = cookies; tot.resize(K, 0); ans = 1e9; dfs(0); return ans; }};作者：TsReaper链接：https://leetcode.cn/circle/discuss/4GGKMb/view/OxXY76/泉源：力扣（LeetCode）著作权归作者全部。商业转载请接洽作者得到授权，非商业转载请注明出处。解法2：二分 + 回溯
二分最大不公上限，回溯是否有满意此上限的分配方案
- 剪枝 1：优先分配饼干包数最多的
对饼干从大到小排序
- 剪枝 2:第一个零食包不管给哪个小朋侪，所开启的回溯树都一样，所以首个饼干包只要给第一个小朋侪就行了，如许的回溯树只有一个根节点（一个回溯树），否则有k个回溯树。
- 剪枝 3：假如当前小朋侪没有分配饼干或分配包数到达上限则无需举行下一个朋侪分配（详细见代码）
参考
- 时间复杂度 O(N * log N)
- 空间复杂度 O(N)
class Solution {public: bool check(vector<int>& cs, vector<int>& bk, int u, int m) { if (u == cs.size()) return true; for (int i = 0; i < bk.size(); ++ i) { // 剪枝 2 if (i && bk == bk[i - 1]) continue; bk += cs; if (bk <= m && check(cs, bk, u + 1, m)) { bk -= cs; return true; } bk -= cs; // 剪枝 3 if (bk == 0 || bk + cs == m) break; } return false; } int distributeCookies(vector<int>& cs, int k) { // 剪枝 1 sort(cs.begin(), cs.end(), [](int& a, int& b){ return a > b; }); int sum = 0; for (int& x : cs) sum += x; int l = 1, r = sum; vector<int> bk(k); while (l < r) { int mid = l + r >> 1; if (check(cs, bk, 0, mid)) { r = mid; }else l = mid + 1; } return l; }};解法3：状态压缩 DP
dp[j] 为前 i 个朋侪分配环境为 j 时的最小不公值， 答案为 dp[k][(1 << n) - 1];有 dp[j] = min(dp[j], max(dp[j - x], sum[x]));
此中 j 为二进制体现饼干分配环境比如 1010，体现分配了第零个饼干和第二个饼干
sum[x] 体现分配环境为 x 的累加和比如 1010 体现 cookies[0] + cookies[2];
class Solution {public: int distributeCookies(vector<int>& cs, int k) { int n = cs.size(); vector<vector<int> > dp(k, vector<int>(1 << n, 1e8)); vector<int> sum(1 << n); for (int i = 0; i < 1 << n; ++ i) { for (int j = 0; j < n; ++ j) { if (i >> j & 1) { sum += cs[j]; } } } for (int i = 0; i < 1 << n; ++ i) { dp[0] = sum; } for (int i = 1; i < k; ++ i) { for (int j = 0; j < 1 << n; ++ j) { for (int x = j; x; x = (x - 1) & j) { // 枚举 j 状态的子集 dp[j] = min(dp[j], max(dp[i - 1][j - x], sum[x])); } } } /*for (int x = j; x; x = (x - 1) & j) 如许可以枚举状态j的每一个子集比如 j = 3 (011) 这个循环就可以枚举 011, 010, 001这三个状态（用x体现）（进入循环 x = 011,第一次 x = 010 & 011 = 010,第二次 x = 001 & 011 = 001)比如 j = 4 (100) 这个循环只能枚举 100这个状态， x = (011) & (100)就会使x为0，从而退出循环。max(dp[i - 1][j - x], sum[x])，就体如今 给第 i 个朋侪 分配 状态为 x 的饼干包数 与给前 i - 1朋侪分配 状态为 j -x 的饼干的个人最小包数中 取最大值。j - x 可以算 状态 x 在 j 下的 “补集”。比如 j 为 （110），x 为（010）时，j - x =（110 - 010 = 100）枚举全部状态，取大概到达的个人最大包数的最小值，就可以求出满意题意的结果。末了返回 dp[k - 1][(1<< n) - 1] 体现给k个朋侪分配状态为 “111...1”的饼干，个人最大包数的最小值。 */ return dp[k - 1][(1 << n) - 1]; }};第四题
解法：枚举
按去除首字母后的字符串举行分组
cnt[j] 体现首字符不包罗 i 字符且包罗 j 字符的分组数目
若两个组能互换一定 一个有 j 无 i(cnt[j]) ，一个 有 i 无 j（cnt[j]）
则 答案为全部 cnt[j] + cnt[j] 的和
class Solution {public: long long distinctNames(vector<string>& is) { unordered_map<string, int> mp; for (string s : is) { mp[s.substr(1)] |= 1 << (s[0] - 'a'); } int cnt[26][26]; memset(cnt, 0, sizeof cnt); long long ret = 0; for (auto& [_, mask] : mp) { for (int i = 0; i < 26; ++ i) { if ((mask >> i & 1) == 0) { for (int j = 0; j < 26; ++ j) { if (mask >> j & 1) { ++ cnt[j]; } } } } } for (auto& [_, mask] : mp) { for (int i = 0; i < 26; ++ i) { if (mask >> i & 1) { for (int j = 0; j < 26; ++ j) { if ((mask >> j & 1) == 0) { ret += cnt[j]; // cout << cnt[j] << endl; } } } } } return ret; }}; |
