解决这个问题的想法是去经历这个问题string，在模拟过程中判断判断条件，判断条件如下；
1.只有小写字母、连字符和/或标点符(不含数字)。
2.至多一个 连字符 '-' 。如果存在，小写字母应该存在于字符的两侧（"a-b" 但是 "-ab" 和 "ab-" 不是有效单词)。
3.至多一个 标点符号。如有，标点符号应位于 token 的 末尾 。
解决代码
class Solution { public: int countValidWords(string s) { int n = s.size(), res = 0; for (int i = 0; i < n; i ){ if (isalpha(s[i]) || s[i] == '.' || s[i] == '!' || s[i] == ',') { int num = 0; while(i < n && s[i] != ' '){ if (s[i] == '-' && i < n-1 && isalpha(s[i 1])) num ; else if((s[i] == '-' && i < n-1 && !isalpha(s[i 1])) || ((s[i] == '.' || s[i] == '!isalpha(s[i 1])) || ((s[i] == '.' || s[i] == '!' || s[i] == ',') && (i < n-1 && s[i 1] != ' ')) || isdigit(s[i])) num = 2; i ; } i --; if (num <= 1) res ; } else if(s[i] != ' '){ while(i < n && s[i] != ' ') i ; i --; } } return res; } }; |
读完问题后，首先要注意问题的数据范围n <= 1e6; 有了这个条件，你可以考虑枚举一切n 1 - 1e7.本范围内满足条件的最小值；本问题要求满足条件的单个位置的数字数等于数字本身，严格大于给出的数字数n；
为什么是1e7呢？因为这个问题要求严格大于n，n能够取到1e6.因此，操作时可以向上取1e7.会有严格大于n的值。
解决代码
const int N = 10, M = 1e7; class Solution { public: int snt[N]; int nextBeautifulNumber(int n) { for (int i = n 1; i <= M; i ){ memset(snt, 0, sizeof snt); int k = i; while(k > 0) { snt[k % 10] ; k /= 10; } bool flag = false; for (int j = 0; j <= 9; j ){ if (snt[j] > 0 && j != snt[j]) { flag = true; break; } &bsp; } if (!flag) return i; } return -1; } }; |
该题题意：给出的是一个二叉树，想要得到的是删除某个节点的分支，所产生的新的分支的乘积的最大值的个数；所以此题可以采用dfs+回溯来解决该问题，在回溯的过程中返回分支所产生的节点，然后求其乘积，得到最大值，同时并记录其个数。解释如下：
对于此案例，若是采用dfs+回溯的方法对于节点2来看；在回溯的过程中2节点的两个子节点3 ，1分别回溯到节点2的节点个数为n1，n2，但对于节点2而言还得计算其父节点部分所产生的个数为p， 整个二叉树的节点个数为n；已知子节点的回溯值n1, n2,如何求出父节点p的值呢？由上图可知：
p = n – n1 – n2
有了此公式对于该问题也就很好解决了。
解决代码
class Solution { public: int root, n, res; unordered_map<int, vector<int>> mp; typedef long long LL; LL kk; int dfs(int p){ LL maxv = 1; int nums = 1; for (int v: mp[p]) { int k = dfs(v); maxv = (LL)maxv * k; nums += k; } if(p != root) maxv = (LL)maxv * (n-nums); if (maxv > kk) { res = 1; kk = maxv; } else if (maxv == kk) { res ++; } return nums; } int countHighestScoreNodes(vector<int>& ps) { n = ps.size(); for (int i = 0; i < n; i ++){ if (ps[i] == -1) root = i; else { mp[ps[i]].push_back(i); } } dfs(root); return res; } }; |
该题的题意：完成某一个课程前，必须先完成在它之前的先修课，那么此题就完全符合拓扑结构，故此可以采用拓扑图去解决该问题。如果要进行该点操作，必须首先完成其所有入度点的操作，因为完成每一个该点入度的时间不一样，所以我们取时间最晚的入度为执行该点的起始执行时间(因为最晚的入度时间点必定其他入度已经全部执行完成)；写出拓扑图+数组记录每一个点的起始时间就可解决该问题。
解决代码
const int N = 50010; class Solution { public: int n, r[N], dist[N]; vector<int> rlx[N]; void topu(vector<int> time){ queue<int> qu; int n = time.size(); for (int i = 1; i <= n; i ++){ if (r[i] == 0) { qu.push(i); dist[i] = time[i-1]; } } while(qu.size()){ int v = qu.front(); qu.pop(); for (int x: rlx[v]){ r[x] --; dist[x] = max(dist[x], dist[v] + time[x-1]); if (r[x] == 0) qu.push(x); } } } int minimumTime(int n, vector<vector<int>>& rx, vector<int>& time) { n = time.size(); for (int i = 0; i < rx.size(); i ++){ int a = rx[i][0], b = rx[i][1]; r[b] ++; rlx[a].push_back(b); } topu(time); int res = 0; for (int i = 1; i <= n; i ++) res = max(res, dist[i]); return res; } }; |
本博客是力扣264场周赛的题解，如果存在不懂的地方可以在评论区提出，这里会耐心解答！关注公众号：算法与编程之美，我们会不断的更新力扣周赛题解，codeforces题解等比赛题解。
实习编辑：衡辉
稿件来源：深度学习与文旅应用实验室（DLETA）