8.2 状态机|贪心|dfs_dp
lc140 单词拆分
class Solution {
unordered_set<string> set;
vector<string> ret;
string s;
int n = 0;
public:
vector<string> wordBreak(string s, vector<string>& wordDict) {
this->s = s;
n = s.size();
for (auto& w : wordDict)
set.insert(w);
dfs(0, "");
return ret;
}
void dfs(int pos, string path) {
if (pos == n) {
if (!path.empty() && path.back() == ' ') {
path.pop_back();
}
ret.push_back(path);
return;
}
for (int i = pos; i < n; ++i) {
string tmp = s.substr(pos, i - pos + 1);
if (set.count(tmp)) {
string newPath = path;
if (!newPath.empty()) {
newPath += " ";
}
newPath += tmp;
dfs(i + 1, newPath);
}
}
}
};
逻辑优化
class Solution {
public:
vector<string> wordBreak(string s, vector<string>& wordDict) {
unordered_map<string,vector<string> > m;
return helper(m,wordDict,s);
}
vector<string> helper(unordered_map<string,vector<string> >& m,vector<string>& wordDict,string s){
if(m.count(s)) return m[s];
if(s.empty()) return {""};
vector<string> res;
for(auto word:wordDict){
if(s.substr(0,word.size())!=word) continue;
vector<string> tmp=helper(m,wordDict,s.substr(word.size()));
for(auto itm:tmp){
res.push_back(word+(itm.empty()?"":" "+itm));
}
}
m[s]=res;
return res;
}
};
进一步，dp
i j双指针 扫描固定切割
一个指针找到 可切割位置，就存该点为true
dp 存状态 cache，假设每一步为切割点的状态
class Solution {
public:
bool wordBreak(string s, vector<string>& wordDict)
{
int n=s.size();
s=' '+s;//解决 下表映射
vector<bool> dp(n+1,false);
dp[0]=true; //多开一个空间 初始化
//! 这个 地方一定要初始化为true
unordered_map<string,int> hash;
for(auto& str:wordDict)
hash[str]++;
for(int i=1;i<=n;i++)
{
for(int j=1;j<=i;j++)
{
string tmp=s.substr(j,i-j+1);
if(dp[j-1]==true
&& hash.count(tmp))
dp[i]=true;
}
}
//双指针 扫描固定切割
// 一个指针找到 可切割位置，就存该点为true
//dp 存状态
return dp[n];
}
};
lcr138
#include <unordered_map>
#include <string>
using namespace std;
class Solution {
public:
bool validNumber(string s) {
unordered_map<char, int> states[9] = {
{{' ',0}, {'s',1}, {'d',2}, {'.',4}},
{{'d',2}, {'.',4}},
{{'d',2}, {'.',3}, {'e',5}, {' ',8}},
{{'d',3}, {'e',5}, {' ',8}},
{{'d',3}},
{{'s',6}, {'d',7}},
{{'d',7}},
{{'d',7}, {' ',8}},
{{' ',8}}
};
int p = 0;
for (char c : s) {
char t;
if (c >= '0' && c <= '9') t = 'd';
else if (c == '+' || c == '-') t = 's';
else if (c == 'e' || c == 'E') t = 'e';
else if (c == '.' || c == ' ') t = c;
else t = '?';
if (states[p].find(t) == states[p].end()) return false;
p = states[p][t];
}
return p == 2 || p == 3 || p == 7 || p == 8;
}
};
判断一个字符串是不是合法的数字（比如"123"、"-123.45"、"3.14e5"都是合法的）。
核心思路是状态机：
1. 把字符串的每个字符转换成统一的类型（比如所有数字都算'd'，正负号算's'）
2. 定义好"状态转移规则"：比如初始状态下遇到数字就进入"数字状态"，遇到符号就进入"符号状态"
3. 从初始状态开始，逐个字符检查，按照规则跳转状态
4. 最后看最终停在的状态是不是"合法结束状态"（比如数字后面、小数点后有数字、指数后有数字等状态）
就像坐公交车：
每个站（状态）只能换乘特定的车（字符类型）去下一个站
只要有一次坐错车就到不了终点，最后到了终点站才算成功。
lc2561.
hash统计diff预处理
交换上的贪心：
sort后，考虑直接交换和通过最小元素中转两种
ret += min({need1[i], need2[i], 2 * min_val});
class Solution {
public:
long long minCost(vector<int>& basket1, vector<int>& basket2) {
// 统计元素差异（用哈希表精准计算需要交换的元素）
unordered_map<int, int> diff;
for (int x : basket1) diff[x]++;
for (int x : basket2) diff[x]--;
vector<int> need1, need2;
int min_val = INT_MAX; // 用于中转交换的最小元素
for (auto& [k, v] : diff)
{
min_val = min(min_val, k); // 记录全局最小值
if (v % 2 != 0) return -1; // 无法平衡的情况
int cnt = abs(v) / 2;
if (v > 0) while (cnt--) need1.push_back(k);
else while (cnt--) need2.push_back(k);
}
// 交换逻辑：考虑直接交换和通过最小元素中转两种方式
sort(need1.begin(), need1.end());
sort(need2.rbegin(), need2.rend());
long long ret = 0;
for (int i = 0; i < need1.size(); i++) {
ret += min({need1[i], need2[i], 2 * min_val});
}
return ret;
}
};
lc748
int target[26] = {0};
int curr[26] = {0};
if (curr[i] < target[i]）
valid = false;
class Solution {
public:
string shortestCompletingWord(string licensePlate, vector<string>& words) {
int target[26] = {0};
for (auto& l : licensePlate)
{
if (isalpha(l)) {
target[tolower(l) - 'a']++; // 直接统计小写字母频次
}
}
string ret;
int minLen = INT_MAX;
for (auto& w : words) {
int curr[26] = {0};
// 统计当前单词中每个字母的出现次数
for (auto c : w) {
curr[tolower(c) - 'a']++;
}
// 检查当前单词是否包含所有必要字母且数量足够
bool valid = true;
for (int i = 0; i < 26; i++) {
if (curr[i] < target[i])
{
valid = false;
break;
}
}
// 更新结果：优先选更短的，长度相同则选字典序小的
if (valid) {
if (w.size() < minLen)
{
minLen = w.size();
ret = w;
}
}
}
return ret;
}
};