第一題
解法:模擬
- 時間復雜度 O(N)
- 空間復雜度 O(N)
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[i][0] << endl;
if (i == bs.size() - 1) {
}else {
if (ie >= bs[i + 1][0]) {
ret += (double)(bs[i + 1][0] - bs[i][0]) * bs[i + 1][1] / 100;
}else {
ret += ((double)ie - bs[i][0]) * bs[i + 1][1] / 100;
break;
}
}
// cout << ret << endl;
}
return ret;
}
};
第二題
解法:線性 DP
? dist[i] 表示 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[i]) {
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[i].size(); ++ j) {
int x = grid[i][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[i] << endl;
ret = min(ret, dist[i] + 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) {
// 所有零食都分完了，計算小朋友獲得的最大餅干數(shù)
int t = tot[0];
for (int i = 1; i < K; i++) t = max(t, tot[i]);
// 所有結(jié)果里取最小
ans = min(ans, t);
return;
}
for (int i = 0; i < K; i++) {
// 枚舉第 d 包零食分給第 i 個小朋友
tot[i] += A[d];
dfs(d + 1);
// 撤銷修改
tot[i] -= 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）
著作權(quán)歸作者所有。商業(yè)轉(zhuǎn)載請聯(lián)系作者獲得授權(quán)，非商業(yè)轉(zhuǎn)載請注明出處。
解法2：二分 + 回溯
?二分最大不公上限，回溯是否有滿足此上限的分配方案
- 剪枝 1：優(yōu)先分配餅干包數(shù)最多的
?對餅干從大到小排序 - 剪枝 2:第一個零食包不管給哪個小朋友，所開啟的回溯樹都一樣，所以首個餅干包只要給第一個小朋友就行了，這樣的回溯樹只有一個根節(jié)點（一個回溯樹），否則有k個回溯樹。
- 剪枝 3：如果當前小朋友沒有分配餅干或分配包數(shù)達到上限則無需進行下一個朋友分配（具體見代碼）
- 時間復雜度 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[i] == bk[i - 1]) continue;
bk[i] += cs[u];
if (bk[i] <= m && check(cs, bk, u + 1, m)) {
bk[i] -= cs[u];
return true;
}
bk[i] -= cs[u];
// 剪枝 3
if (bk[i] == 0 || bk[i] + cs[u] == 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：狀態(tài)壓縮 DP
? dp[i][j] 為前 i 個朋友分配情況為 j 時的最小不公值， 答案為 dp[k][(1 << n) - 1];有 dp[i][j] = min(dp[i][j], max(dp[i][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[i] += cs[j];
}
}
}
for (int i = 0; i < 1 << n; ++ i) {
dp[0][i] = sum[i];
}
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 狀態(tài)的子集
dp[i][j] = min(dp[i][j], max(dp[i - 1][j - x], sum[x]));
}
}
}
/*
for (int x = j; x; x = (x - 1) & j) 這樣可以枚舉狀態(tài)j的每一個子集
比如 j = 3 (011) 這個循環(huán)就可以枚舉 011, 010, 001這三個狀態(tài)（用x表示）
（進入循環(huán) x = 011,第一次 x = 010 & 011 = 010,第二次 x = 001 & 011 = 001)
比如 j = 4 (100) 這個循環(huán)只能枚舉 100這個狀態(tài)， x = (011) & (100)就會使x為0，從而退出循環(huán)。
max(dp[i - 1][j - x], sum[x])，就表示在
給第 i 個朋友 分配 狀態(tài)為 x 的餅干包數(shù)
與
給前 i - 1朋友分配 狀態(tài)為 j -x 的餅干的個人最小包數(shù)中 取最大值。
j - x 可以算 狀態(tài) x 在 j 下的 “補集”。比如 j 為 （110），x 為（010）時，j - x =（110 - 010 = 100）
枚舉所有狀態(tài)，取可能達到的個人最大包數(shù)的最小值，就可以求出滿足題意的結(jié)果。
最后返回 dp[k - 1][(1<< n) - 1] 表示給k個朋友分配狀態(tài)為 “111...1”的餅干，個人最大包數(shù)的最小值。
*/
return dp[k - 1][(1 << n) - 1];
}
};
第四題
解法：枚舉
?按去除首字母后的字符串進行分組
cnt[i][j] 表示首字符不包含 i 字符且包含 j 字符的分組數(shù)目
若兩個組能交換必然 一個有 j 無 i(cnt[i][j]) ，一個 有 i 無 j（cnt[j][i]）
則 答案為所有 cnt[i][j] + cnt[j][i] 的和
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[i][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[i][j];
// cout << cnt[i][j] << endl;
}
}
}
}
}
return ret;
}
};
