1.1 5388. 重新格式化字符串(1417. Reformat The String)
string 字符串 The 重新 格式化 1.1
2023-06-13 09:13:21 时间
0. 前言
- 本周休息不太好,早上醒来,比赛都快结束了,混混沉沉做完所有题,以后还是不能熬夜
- 中文版地址:https://leetcode-cn.com/contest/weekly-contest-185/
- 英文版地址:https://leetcode.com/contest/weekly-contest-185/
1. 题解
1.1 5388. 重新格式化字符串(1417. Reformat The String)
- 中文版题目描述:https://leetcode-cn.com/problems/reformat-the-string/
- 英文版题目描述:hhttps://leetcode.com/problems/reformat-the-string/
- 思路:签到题
- 将字符串分成两组一组字符一组数字,轮流加入新字符串
- 可以思考一下这个题不用辅助数组怎么做
- 代码如下:
class Solution {
public:
bool isNumber(char ch) {
return ch >= '0' && ch <= '9';
}
string reformat(string s) {
char mark = s[0];
int len = s.length(), i = 0, j = len - 1;
while (i < j) {
while (i < j && (isNumber(mark) != isNumber(s[j]))) j--;
while (i < j && (isNumber(mark) == isNumber(s[i]))) i++;
swap(s[i], s[j]);
}
if (abs(len - i - 1 - i - 1) > 1) return "";
// cout << i+1 << " " << len - i -1 << endl;
string ans = "";
if (len - i - 1 > i + 1) {
ans += s[len-1];
for (int p = 0 ; p <= i ; p++) {
ans += s[p];
ans += s[p+i+1];
}
} else if (len - i - 1 < i + 1) {
for (int p = 0 ; p < i ; p++) {
ans += s[p];
ans += s[p+i+1];
}
ans += s[i];
} else {
for (int p = 0 ; p <= i ; p++) {
ans += s[p];
ans += s[p+i+1];
}
}
return ans;
}
};
1.2 5389. 点菜展示表(1418. Display Table of Food Orders in a Restaurant)
- 中文版题目描述:https://leetcode-cn.com/problems/display-table-of-food-orders-in-a-restaurant/
- 英文版题目描述:https://leetcode.com/problems/display-table-of-food-orders-in-a-restaurant/
- 思路:数据结构
- 一个 map 或者 set 存所有菜的名称
- 一个二维 map 存每个桌子需要相应菜的数量
- 由于桌号按照升序排序,将桌号按照数字的方式存在 map 中
- 代码如下:
class Solution {
public:
vector<vector<string>> displayTable(vector<vector<string>>& orders) {
sort(orders.begin(), orders.end(), [](vector<string>& a, vector<string>& b) {
return a[1] < b[1];
});
map<int, map<string, int>> tables;
map<string, bool> foods;
for (auto o : orders) {
for (int i = 2 ; i < o.size() ; i++) {
int table = atoi(o[1].c_str());
if (tables.find(table) == tables.end()) {
tables[table] = map<string, int>();
}
if (tables[table].find(o[i]) == tables[table].end()) {
tables[table][o[i]] = 0;
}
tables[table][o[i]]++;
foods[o[i]] = true;
// cout << o[i] << endl;
}
}
// cout << tables.size() << endl;
vector<vector<string>> ans = vector<vector<string>>(tables.size()+1, vector<string>());
ans[0].push_back("Table");
for (auto it : foods) {
ans[0].push_back(it.first);
}
int i = 1;
for (auto it : tables) {
ans[i++].push_back(to_string(it.first));
for (auto food : foods) {
if (it.second.find(food.first) == it.second.end()) {
it.second[food.first] = 0;
}
ans[i-1].push_back(to_string(it.second[food.first]));
}
}
return ans;
}
};
1.3 5390. 数青蛙(1419. Minimum Number of Frogs Croaking)
- 中文版题目描述:https://leetcode-cn.com/problems/minimum-number-of-frogs-croaking/
- 英文版题目描述:https://leetcode.com/problems/minimum-number-of-frogs-croaking/
- 思路:统计 'c'、'r'、'o'、'a'、'k' 各自的数目
- 要找到一个完整的 "croak" 才算找到合理的娃叫
- 当遇到 'c' 我们就要找下一个 'r';当遇到 'r' 就要找下一个 'o';当遇到 'o' 就要找下一个 'a';当遇到 'a' 就要找下一个 'k';当遇到 'k' 就要找下一个 'c'
- 反过来推,遇到一个 'c' 时,前面只有存在一个 'k',说明是来自某一只已存在青蛙的叫声,否则需要新增一只青蛙
- 遇到一个 'r' 就找前面的 'c';遇到一个 'o' 就找前面的 'r';遇到一个 'a' 就找前面的 'o';遇到一个 'r' 就找前面的 'a'
- 即维护一个数量关系 c >= r >= o >= a >= k 的关系,若打破,则说明不会存在这种情况
- 代码如下:
class Solution {
public:
int minNumberOfFrogs(string croakOfFrogs) {
unordered_map<char, int> cnt;
cnt['c'] = cnt['r'] = cnt['o'] = cnt['a'] = cnt['k'];
int len = croakOfFrogs.length(), ans = 0;
for (int i = 0 ; i < len ; i++) {
char cur = croakOfFrogs[i];
cnt[cur]++;
if (cur == 'c') {
if (cnt['k']) cnt['k']--;
else ans++;
} else if (cur == 'r') {
cnt['c']--;
} else if (cur == 'o') {
cnt['r']--;
} else if (cur == 'a') {
cnt['o']--;
} else if (cur == 'k') {
cnt['a']--;
}
if (cnt['a'] < 0 || cnt['r'] < 0 || cnt['o'] < 0 || cnt['a'] < 0) break;
}
if (cnt['a'] != 0 || cnt['r'] != 0 || cnt['o'] != 0 || cnt['a'] != 0) return -1;
return ans;
}
};
1.4 5391. 生成数组(1420. Build Array Where You Can Find The Maximum Exactly K Comparisons)
- 中文版题目描述:https://leetcode-cn.com/problems/build-array-where-you-can-find-the-maximum-exactly-k-comparisons/
- 英文版题目描述:https://leetcode.com/problems/build-array-where-you-can-find-the-maximum-exactly-k-comparisons/
- 思路:动态规划
- dp[i][j][l] 表示长度为 i,最大值为 j,最大值首次出现在 l 位置的所有情况
- 更新 i+1 长度的情况时,若第 i+1 位的值 r 大于 j,则 dp[i+1][r][l+1] += dp[i][j][l];否则 dp[i+1][j][l] += dp[i][j][l]
- 初始化 i = 1 的情况,dp[1][i][1] = 1
- 最终答案为 sum(dp[n][i][k])
- 代码如下:
class Solution {
public:
int numOfArrays(int n, int m, int k) {
long long mod = (long long)1000000007;
vector<vector<vector<long long>>> dp = vector<vector<vector<long long>>>(n+1, vector<vector<long long>>(m+1, vector<long long>(k+2, (long long)0)));
for (int i = 1 ; i <= m ; i++) {
dp[1][i][1] = (long long)1;
}
for (int i = 1 ; i < n ; i++) {
for (int j = 1 ; j <= m ; j++) {
for (int l = 1 ; l <= k ; l++) {
for (int r = 1 ; r <= m ; r++) {
if (r > j) {
dp[i+1][r][l+1] += dp[i][j][l];
dp[i+1][r][l+1] %= mod;
} else {
dp[i+1][j][l] += dp[i][j][l];
dp[i+1][j][l] %= mod;
}
}
}
}
}
long long ans = (long long)0;
for (int i = 1 ; i <= m ; i++) {
ans += dp[n][i][k];
ans %= mod;
}
return (int)ans;
}
};
2. 小结
- 第四题最初陷入试图用组合数学的误区,耽误了好长时间,后来参考其他同学的才解决
3. 参考文献
相关文章
- java中字符串String格式转化成json格式[通俗易懂]
- 把字符串转换成float类型_c++如何将string类型转换成int类型
- Swift4 String截取字符串
- String字符串操作之截取
- Java截取String字符串的几种方法
- SqlBulkCopy – The given value of type String from the data source cannot be converted to type
- 深入理解C++11_c++ string char
- java中map转string_字符串转list集合
- integer转换为string_go 字符串转int
- java解析字符串_java string 转jsonobject
- 【C++ 语言】C++字符串 ( string 类 | 创建方法 | 控制台输出 | 字符串操作 | 栈内存字符串对象 | string* )
- ORA-26747: The one-to-many transformation function string encountered the following error: string ORACLE 报错 故障修复 远程处理
- ORA-28074: The “string” field of the redaction parameters is not valid. ORACLE 报错 故障修复 远程处理
- ORA-28077: The attribute specified (string) exceeds the maximum length. ORACLE 报错 故障修复 远程处理
- ORA-31691: The worker received message number string from the MCP, which is invalid. ORACLE 报错 故障修复 远程处理
- ORA-41104: The database: string is the Cluster Director. ORACLE 报错 故障修复 远程处理
- ORA-48411: The trace files exceeds the maximum number [string] ORACLE 报错 故障修复 远程处理
- ORA-48487: The internal predicate string exceeds the maximum length [string] ORACLE 报错 故障修复 远程处理
- ORA-48490: The field number exceeds the maximum number [string] ORACLE 报错 故障修复 远程处理
- ORA-48491: The program name is too long, exceeds the maximum length [string] ORACLE 报错 故障修复 远程处理
- ORA-48499: The value of the keyword “string” exceeds the maximum length string ORACLE 报错 故障修复 远程处理
- ORA-48928: The predicate exceeds the max limit string ORACLE 报错 故障修复 远程处理
- ORA-48929: The trace record size exceeded the max size that can be read [string] ORACLE 报错 故障修复 远程处理
- ORA-55567: The _highthreshold_undoretention value should be at least string based on the current undo retention settings. ORACLE 报错 故障修复 远程处理
- ORA-55569: The UNDO_RETENTION parameter value should be atmost string, the _highthreshold_undoretention setting. ORACLE 报错 故障修复 远程处理
- ORA-13703: The snapshot pair [string, string] for database_id string and instance_id string are not found in the current repository. ORACLE 报错 故障修复 远程处理
- Java String字符串补0或空格详解编程语言
- JS时间和字符串的相互转换 Date+String详解编程语言
- vue attribute中使用字符串模板 template string详解编程语言
- 学习Oracle中的STRING_TO_TABLE函数(oracle字符串分割函数)
- 关于JS字符串函数String.replace()
- 浅析string类字符串和C风格字符串之间的区别
- c字符串,string对象,字符串字面值的区别详解