LeetCode智加科技专场——第207场周赛题解

昨天下午战队赛，第一次在女票面前比赛差点爆零，哎，太丢人了，必须得奋发图强了呀

目录

T1.重新排列单词间的空格

T2.拆分字符串是唯一字符串的数目最大

T3.矩阵的最大非负积

T4.连通两组带你的最小成本

T1.重新排列单词间的空格

不多说了，WA两次才AC，caole

class Solution {
public:string reorderSpaces(string text) {int blankNum = 0;int wordNum = 0;vector<string> v;string ans;for (auto elem : text) {if (elem == ' ')blankNum++;}if (blankNum == 0) {return text;}for (int i = 0; i < text.size(); i++) {if (text[i] != ' ') {int j = i;string temp;while (j < text.size() && text[j] != ' ') {temp.push_back(text[j]);j++;}v.push_back(temp);i = j;}}ans += v[0];if (v.size() == 1) {int i = text.size() - ans.size();while (i--) {ans.push_back(' ');}return ans;}int num = blankNum / (v.size() - 1);for (int i = 1; i < v.size(); i++) {for (int j = 0; j < num; j++) {ans.push_back(' ');}ans += v[i];}if (ans.size() < text.size()) {int i = text.size() - ans.size();while (i--) {ans.push_back(' ');}}return ans;}
};

后来看大佬用join写，我只能说，Py牛逼！！

T2.拆分字符串是唯一字符串的数目最大

不可重复回溯模板题，可参见：https://xduwq.blog.csdn.net/article/details/105666096

class Solution {
public:int ans = 0;unordered_set<string> m;int maxUniqueSplit(string s) {dfs(s, 0);return ans;}// dfs不可重复回溯模板void dfs(string& s, int index) {if (index == s.size()) {ans = max(ans, (int)m.size());return;}string temp;for (int i = index; i < s.size(); i++) {temp += s[i];// 先去重if (m.find(temp) == m.end()) {m.insert(temp);dfs(s, i + 1);m.erase(temp);}}}
};

T3.矩阵的最大非负积

这个经典DP启发：

class Solution {
public:int uniquePaths(int m, int n) {int dp[m][n];// for(int i = 0; i<m; i++) {dp[i][0] = 1;}for(int j = 0; j<n; j++) {dp[0][j] = 1;}// for(int i = 1; i<m; i++) {for(int j = 1; j<n; j++) {dp[i][j] = dp[i-1][j] + dp[i][j-1];}}return dp[m-1][n-1];}
};

这个类似的矩阵DP题有很多，算是一种模板吧

但是这里有负数的存在，所以处理起来比上面那种模板来讲比较困难。可以维护两个DP数组，一个记录当前的最大值，一个记录当期的最小值（因为最小值可能在下一个步骤当中乘以一个负数就变成了最大值，最大值在下一个步骤当中乘以一个负数就变成最小值了），后面的步骤同理。

typedef long long ll;
class Solution {
public:int maxProductPath(vector<vector<int>>& grid) {// DP模板题ll r = grid.size();ll l = grid[0].size();// 分别保存最大值和最小值，到时候根据正负情况再进行判断ll dp_min[r][l], dp_max[r][l];// 初始化首行和首列dp_min[0][0] = dp_max[0][0] = grid[0][0];for (ll i = 1; i < r; i++)dp_min[i][0] = dp_max[i][0] = dp_min[i-1][0] * grid[i][0];for (ll j = 1; j < l; j++)dp_min[0][j] = dp_max[0][j] = dp_min[0][j-1] * grid[0][j];// 核心DPfor (ll i = 1; i < r; i++) {for (ll j = 1; j < l; j++) {if (grid[i][j] == 0)dp_min[i][j] = dp_max[i][j] = 0;else if(grid[i][j] > 0) {dp_min[i][j] = min(dp_min[i-1][j], dp_min[i][j-1]) * grid[i][j];dp_max[i][j] = max(dp_max[i-1][j], dp_max[i][j-1]) * grid[i][j];} else {dp_min[i][j] = max(dp_max[i-1][j], dp_max[i][j-1]) * grid[i][j];dp_max[i][j] = min(dp_min[i-1][j], dp_min[i][j-1]) * grid[i][j];}}}if (dp_max[r-1][l-1] < 0)return -1;return dp_max[r-1][l-1] % 1000000007;}
};

T4.连通两组带你的最小成本

不说了，我菜炸了，日常放弃，看大佬题解，溜了

class Solution {
public:int size1, size2;int connectTwoGroups(vector<vector<int>>& cost) {size1 = cost.size();size2 = cost[0].size();int total = 1 << (size1 + size2);vector<int> dp(total, 0x3f3f3f3f);return dfs(cost, dp, 0, 0);}int dfs(vector<vector<int>>& cost, vector<int> &dp, int state, int index) {if (index >= size1 + size2) {return 0;}if (dp[state] != 0x3f3f3f3f) {return dp[state];}int result = 0x3f3f3f3f;// 给左边点连线if (index < size1) {for (int i = 0; i < size2; i++) {int nextState = state | (1 << index) | (1 << (size1 + i));result = std::min(result, cost[index][i] + dfs(cost, dp, nextState, index + 1));}// 给右边点连线} else {if ((state & (1 << index)) != 0) {return dp[state] = dfs(cost, dp, state, index + 1);}for (int i = 0; i < size1; i++) {int nextState = (state | (1 << i) | (1 << index));result = std::min(result, cost[i][index - size1] + dfs(cost, dp, nextState, index + 1));}}return dp[state] = result;}
};