qidao123.com技术社区-IT企服评测·应用市场

标题: 力扣（2405题）子字符串的最优划分 [打印本页]

作者: 温锦文欧普厨电及净水器总代理 时间: 2025-4-28 18:18
标题: 力扣（2405题）子字符串的最优划分
该题有俩个难点，一个是怎么确定子串里有没有重复的字符，另一个难点是怎么划分字符串并进行子串数目的计数
这里用到滑动窗口技巧和哈希表
利用哈希表来纪录字串中的字符，就可以在O(1)的时间复杂度下确定子串中有没有重复；再利用滑动窗口来划分字符串，如果新加入窗口的字符与子串中有重复的，那么就进行一次划分，并让计数加一
比方：字符串“abacada”，让我们来划分字符串的话，那么子串就是“ab”，“ac”，“ad”，
“a”这五个子串。下面就来具体实现，创建一个哈希表来储存字符int hash[128]（字符范例实际是整数范例），初始化计数NumOfsubstring为零，初始化left和right指针为零（left和right之间的部门就是窗口，也是字符串的字串），创建一个循环（循环条件就是right < s.size()，大部门滑动窗口的循环条件险些都是这个），right每向右移动，便将新字符加入窗口。在循环内里最告急的事情就是考虑清楚什么情况下要移动左窗口，在这道题中，如果新加入窗口的字符与子串中有重复，那么就让left = right（这就相当于进行了一次划分），并将哈希表清空归零，然后让NumOfsubstring计数加一。不停重复这个过程，直至循环结束，最后返回NumOfsubstring+1。
具体代码如下：
class Solution {
public:
int partitionString(string s) {
int hash[128];
memset(hash, 0, sizeof(hash));
int NumOfsubsting = 0;
for(int left = 0, right = 0; right < s.size(); right++){
if(hash[ s[right] ]){
left = right;
NumOfsubsting++;
memset(hash, 0, sizeof(hash));
}
hash[ s[right] ]++;
}
return NumOfsubsting+1;
}
};
下面带各人过一遍代码。还是拿“abacada”举例，进入循环，hash['a']为零，以是不执行if语句，hash['a']加一，right加一，第一遍循环结束；right为1小于s.size()成立，进入循环，hash['b']为零，hash['b']加一，right加一，第二遍循环结束；right小于s.size()成立，进入循环，hash['a']为一，执行if语句，left = right（这里就相当于是进行了一次划分），NumOfsubstring计数加一，将哈希表清空归零，hash['a']加一（留意此时的hash['a']即是一）。重复上述过程的划分就可以确定有多少个子串了，但是要留意最后一次划分时因为会直接跳出主循环，NumOfsubstring不会进行加一操作，以是要在最后的返回中让NumOfsubstring加一（如果没有这个加一操作，NumOfsubstring的值会比精确的子串数小一）

免责声明：如果侵犯了您的权益，请联系站长，我们会及时删除侵权内容，谢谢合作！更多信息从访问主页：qidao123.com:ToB企服之家，中国第一个企服评测及商务社交产业平台。

欢迎光临 qidao123.com技术社区-IT企服评测·应用市场 (https://dis.qidao123.com/)