Leetcode 第 207 场周赛

本文主要是介绍Leetcode 第 207 场周赛，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

重新排列单词间的空格
给你一个字符串 text ，该字符串由若干被空格包围的单词组成。每个单词由一个或者多个小写英文字母组成，并且两个单词之间至少存在一个空格。题目测试用例保证 text 至少包含一个单词。

请你重新排列空格，使每对相邻单词之间的空格数目都相等，并尽可能最大化该数目。如果不能重新平均分配所有空格，请将多余的空格放置在字符串末尾，这也意味着返回的字符串应当与原 text 字符串的长度相等。

返回重新排列空格后的字符串。

思路：
因为不太懂字符串相关函数，所以没啥可以取巧的。
直接将所有单词先抽出来，把空格数量算出来，然后插入空格就好了

class Solution {
public:string reorderSpaces(string text) {int n = text.size();vector<string>vec;int cnt = 0;string now;for(int i = 0;i < n;i++) {if(text[i] == ' ') {cnt++;if(now.length() != 0) {vec.push_back(now);now.clear();}} else {now += text[i];}}if(text[n - 1] != ' ') vec.push_back(now);int num = vec.size();string ans;if(num == 1) {ans = vec[0];for(int i = 0;i < cnt;i++) ans = ans + ' ';return ans;}for(int i = 0;i < num;i++) {ans = ans + vec[i];if(i == num - 1) continue;for(int j = 0;j < cnt / (num - 1);j++) {ans = ans + ' ';}}for(int i = 0;i < cnt % (num - 1);i++) {ans += ' ';}return ans;}
};

拆分字符串使唯一子字符串的数目最大
给你一个字符串 s ，请你拆分该字符串，并返回拆分后唯一子字符串的最大数目。

字符串 s 拆分后可以得到若干非空子字符串，这些子字符串连接后应当能够还原为原字符串。但是拆分出来的每个子字符串都必须是唯一的。

注意：子字符串是字符串中的一个连续字符序列。

思路：
数据范围为16（逗你玩的感觉），直接递归枚举。
相当于字符之间有隔板，你选择放或者不放，所以复杂度是 $2^{n-1}$ 。

class Solution {
public:map<string,int>mp;int dfs(int id,string s) {if(id >= s.size()) return 0;string now;int num = 0;for(int i = id;i < s.size();i++) {now += s[i];if(!mp[now]) {mp[now] = 1;num = max(num,dfs(i + 1,s) + 1);mp[now] = 0;}}return num;}int maxUniqueSplit(string s) {return dfs(0,s);}
};

矩阵的最大非负积
给你一个大小为 rows x cols 的矩阵 grid 。最初，你位于左上角 (0, 0) ，每一步，你可以在矩阵中向右或向下移动。

在从左上角 (0, 0) 开始到右下角 (rows - 1, cols - 1) 结束的所有路径中，找出具有最大非负积的路径。路径的积是沿路径访问的单元格中所有整数的乘积。

返回最大非负积对 109 + 7 取余的结果。如果最大积为负数，则返回 -1 。

注意，取余是在得到最大积之后执行的。

思路：
要求最大非负数，那么可以想到定义 $f [i] [j] [0 / 1]$ ，代表从 $(i, j)$ 出发的最大乘积和最小乘积。直接记忆化搜索求解。

typedef long long ll;
const int mod = 1e9 + 7;
class Solution {
public:ll f[30][30][2]; //0最小，1最大int vis[30][30];void dfs(int i,int j,vector<vector<int>>& grid) {if(vis[i][j]) return;vis[i][j] = 1;int n = grid.size(),m = grid[0].size();ll mi = 2e18,mx = -2e18;if(i == n - 1 && j == m - 1) {f[i][j][0] = f[i][j][1] = grid[i][j];return;} if(j + 1 <= m - 1) {dfs(i,j + 1,grid);mi = min(mi,f[i][j + 1][0]);mx = max(mx,f[i][j + 1][1]);} if(i + 1 <= n - 1) {dfs(i + 1,j,grid);mi = min(mi,f[i + 1][j][0]);mx = max(mx,f[i + 1][j][1]);}if(grid[i][j] >= 0) {f[i][j][1] = mx * grid[i][j];f[i][j][0] = mi * grid[i][j];} else {f[i][j][1] = mi * grid[i][j];f[i][j][0] = mx * grid[i][j];}}int maxProductPath(vector<vector<int>>& grid) {dfs(0,0,grid);int n = grid.size(),m = grid[0].size();if(f[0][0][1] < 0) return -1;return f[0][0][1] % mod;}
};

连通两组点的最小成本
给你两组点，其中第一组中有 size1 个点，第二组中有 size2 个点，且 size1 >= size2 。

任意两点间的连接成本 cost 由大小为 size1 x size2 矩阵给出，其中 cost[i][j] 是第一组中的点 i 和第二组中的点 j 的连接成本。如果两个组中的每个点都与另一组中的一个或多个点连接，则称这两组点是连通的。换言之，第一组中的每个点必须至少与第二组中的一个点连接，且第二组中的每个点必须至少与第一组中的一个点连接。

返回连通两组点所需的最小成本。

思路：
挺有难度的一道题，没想出来（哭）。参考

一开始看成了二分图最小带权匹配，但是每个点可以有多个出边，所以这样不行。但是题解里面有大佬处理后可以用KM算法，这个可以自行学习。

题意可以转换为一个矩形，选择一些点使得每行每列都有点，且权值和最小。然后因为数据范围小，考虑状压或者搜索。

可以定义 $f [i] [j]$ 代表选到第 $i$ 行，且第 $i$ 行状态为 $j$ 的权值和。
这样最终状态就是 $f [n - 1] [1 < < m - 1]$ 。不过这样有一个问题，我如何保证每行一定有选的数呢？

答案是，只需要在转移的时候，将之前的状态和当前的状态起点都设置为1就好了。
（一个小点，但就是没想到）。

		for(int i = 0;i < n;i++) {for(int j = 1;j < (1 << m);j++) { //当前这一行选择的列if(i == 0) {dp[i][j] = Cost[i][j];continue;}for(int k = 1;k < (1 << m);k++) { //之前选择的列dp[i][j | k] = min(dp[i][j | k],dp[i - 1][k] + Cost[i][j]);}}}

不过这样写的话，最后会超时。因为我们已经知道了之前选择列的情况，我们首先要满足这一行一定要选东西，其次希望，选择的列尽量是之前没有选择过的。

所以可以这样转移：

	for(int i = 0;i < n;i++) {for(int j = 1;j < (1 << m);j++) { //之前所有选择的列if(i == 0) {dp[i][j] = Cost[i][j];continue;}for(int k = 0;k < m;k++) {//选择一个数的状态dp[i][j | (1 << k)] = min(dp[i][j | (1 << k)],dp[i - 1][j] + Cost[i][1 << k]);}int state = (1 << n) - 1 - j;for(int k = state;k;k = (k - 1) & state) { //选择所有没有选择过的列状态的子集dp[i][j | k] = min(dp[i][j | k],dp[i - 1][j] + Cost[i][k]);}}}

最终代码

#pragma GCC optimize(2)
class Solution {
public:int dp[13][1 << 13],Cost[13][1 << 13];int connectTwoGroups(vector<vector<int>>& cost) {int n = cost.size(),m = cost[0].size();for(int i = 0;i < n;i++) {for(int j = 0;j < (1 << m);j++) {int now = 0;for(int k = 0;k < m;k++) {if(j & (1 << k)) {now += cost[i][k];}}Cost[i][j] = now;}}memset(dp,0x3f,sizeof(dp));for(int i = 0;i < n;i++) {for(int j = 1;j < (1 << m);j++) { //之前所有选择的列if(i == 0) {dp[i][j] = Cost[i][j];continue;}for(int k = 0;k < m;k++) {dp[i][j | (1 << k)] = min(dp[i][j | (1 << k)],dp[i - 1][j] + Cost[i][1 << k]);}int state = (1 << n) - 1 - j;for(int k = state;k;k = (k - 1) & state) {dp[i][j | k] = min(dp[i][j | k],dp[i - 1][j] + Cost[i][k]);}}}return dp[n - 1][(1 << m) - 1];}
};