树|regex正则
lc2047
可以三解，复习了:模拟 状态机 正则
正则+istringstream处理
这才是真正的代码😭
正则表达式 (([a-z]+-)?[a-z]+)?[!,.]? 的结构和匹配逻辑是：
- 核心部分 ([a-z]+-)?[a-z]+ ：匹配“纯小写字母”（如 abc ）或“小写字母+连字符+小写字母”（如 abc-def ，连字符前后至少1个字母）；
- 外层 (...)？ ：让核心部分可选（但结合实际场景，通常是必填，避免空串）；
- 末尾 [!,.]? ：匹配0或1个句末标点（ ! / , / . ）。
整体用于匹配合法单词：允许“纯字母”“字母-连字符-字母”，且可带1个句末标点。
#include <regex>
class Solution {
public:
int countValidWords(string sentence) {
regex r1("(([a-z]+-)?[a-z]+)?[!,.]?");
//定义匹配pattern
istringstream iss(sentence);
int ans=0;
string word;
while(iss>>word){
if(regex_match(word,r1)){
ans++;
}
}
return ans;
}
};
判断句子中每个单词是否合法（合法是“纯字母”“字母-字母”或这两类加句末标点），统计合法单词数
状态机 优雅的转移设计
-1:错误
0:空格
1:字母
2:字母+链接符
3:字母+链接符+字母
4:结尾状态注意的梳理 可以画图枚举 画画就出来啦
class Solution {
public:
int countValidWords(string sentence)
{
int state=0,res=0;
sentence+=' ';
for(auto& c:sentence){
if(c==' '){
if(state==1||state==3||state==4)res++;
state=0; //重置
}
else if('a'<=c&&c<='z'){
if(state==0||state==2)state++;
else if(state==1||state==3)continue;
else state=-1;
}
else if(c=='-'){
if(state==1)state=2;
else state=-1;
}
else if(c=='.'||c==','||c=='!'){
if(state==0||state==1||state==3)
state=4;
else state=-1;
}
else state=-1;
}
return res;
}
};
lc1422
注意 覆盖所有分割点
class Solution {
//左0右1
public:
int maxScore(string s)
{
int n=s.size();
vector<int> p(n+1);
for(int i=1;i<=n;i++)
p[i]=p[i-1]+(s[i-1]-'0');
int ret=0;
for(int i=1;i<n;i++)
{
int f=i-p[i];
int b=p[n]-p[i];
ret=max(ret,f+b);
}
return ret;
}
};
lc563
int dfs
class Solution
{
public:
int findTilt(TreeNode* root)
{
int ret=0;
auto dfs=[&](this auto&& dfs,TreeNode* node)->int
{
if(!node) return 0;
int l=dfs(node->left);
int r=dfs(node->right);
ret+=abs(l-r);
return l+r+node->val;
};
dfs(root);
return ret;
}
};