力扣 297 场周赛

第一题

解法:模拟

• 时间复杂度 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) {
            // 所有零食都分完了，计算小朋友获得的最大饼干数
            int t = tot[0];
            for (int i = 1; i < K; i++) t = max(t, tot[i]);
            // 所有结果里取最小
            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）
著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。

解法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[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：状态压缩 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 状态的子集
                    dp[i][j] = min(dp[i][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[i][j] 表示首字符不包含 i 字符且包含 j 字符的分组数目
若两个组能交换必然 一个有 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;
    }
};