树|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;
}
};