连续字符
?
给出一个字符串，要在字符串中找到最长的一段包含相同字符的子串的长度，这个字符串有很多段，每一段都是相同的字符，在其中找到最长的一段，示例1：leetcode，返回最长的子串长度为 2
如果用循环的方式，枚举每一段的起点，枚举每一段的终点，再求长度，时间复杂度为 O( n^2 )
双指针算法：枚举的时候一段一段来枚举，每次字母只会扫描一遍，每次会枚举到一个字母，第一个指针枚举每一段的开头，第二个指针每次从开头往后枚举，枚举到这一段的结尾：只要第二个指针对应的字母和第一个指针相同，第二个指针就一直往后走，最终第二个指针就会走到和第 i 个字母相同的这段字母的下一个位置，得出从 i ~ j -1 这一段就是连续相同的一段字母，求出长度，求完后 i 跳到 j 的位置. . . 时间复杂度为 O( n )
class Solution {
public:
int maxPower(string s) {
//定义答案
int res = 0;
//第一个指针从前往后走
for(int i = 0;i < s.size();) {
//第二个指针每次从 i 的后面开始走
int j = i + 1;
//1.第二个指针没有走到结尾 2.第二个指针的字符等于第一个指针的字符 第二个指针就往后走
while(j < s.size() && s[i] == s[j]) j ++;
//当前字符为 i ~ j - 1,长度为 j - i
//更新答案
res = max(res,j - i);
//让 i 跳到 j 的位置
i = j;
}
return res;
}
};最简分数
?
?
?
给出一个整数 n，返回所有大于 0 小于 1 的并且满足分母小于等于 n 的最简分数?
示例1：当 n 等于 2 时，只有一个分数 1 / 2
把所有满足要求的分数枚举出来，对于一个分数而言，枚举分子和分母
由于 0 ＜ a / b ＜ 1，所以一定是正数
分子 a 的范围：1? ≤? a ＜ b
分母 b 的范围：1? ≤? b? ≤? n
两层循环枚举 a、b 即可
要求输出最简分数：a、b的最大公因数等于 1→ 用欧几里得算法求最大公因数，判断是不是 1 即可
先枚举分母再枚举分子，两重循环，对于每一对 a、b 用欧几里得算法求最大公因数是不是 1，就满足条件
时间复杂度为 O( n^2 × logn )
class Solution {
public:
//辗转相除法求最大公因数
int gcd(int a,int b) {
return b ? gcd(b,a % b) : a;
}
vector<string> simplifiedFractions(int n) {
//定义答案
vector<string> res;
//枚举分子、分母
//分母
for(int i = 1;i <= n;i++ )
//分子
for(int j = 1;j < i;j++ )
//分子和分母的最大公因数是 1
if(gcd(i,j) == 1)
//注意格式
res.push_back(to_string(j) + '/' + to_string(i));
return res;
}
};统计二叉树中好节点的数目
?
?
?
看从根节点到当前点 X 的路径上的所有节点最大值是不是大于当前点的权值
二叉树的遍历，dfs 加一个参数 maxv ，用于记录从根节点到目标点之前的最大值，比较最大值和目标点的权值，如果最大值大于目标点的权值，目标点就不是好节点，否则就是好节点，函数返回好节点的数量
递归图解：力扣1448. 统计二叉树中好节点的数目讲解_青鱼29的博客-CSDN博客
/**
* Definition for a binary tree node.
* struct TreeNode {
* int val;
* TreeNode *left;
* TreeNode *right;
* TreeNode() : val(0), left(nullptr), right(nullptr) {}
* TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
* TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
* };
*/
class Solution {
public:
int goodNodes(TreeNode* root) {
//第二个参数取 int 的最小值 不会大于任何一点的权值
return dfs(root,INT_MIN);
}
//当前点 从根节点走到当前点之前的最大值
int dfs(TreeNode* root,int maxv) {
//如果树为空,一个节点都没有,好节点为0
if(!root) return 0;
//看当前点是不是好节点
//如果当前点是好节点,res 为 1,如果不是好节点,res 为 0
int res = maxv <= root->val;
//需要往下走,走之前,要更新最大值maxv-> 需要经过当前点
maxv = max(maxv,root->val);
//当前点(根节点)的好节点数量 + 左子树的好节点数量 + 右子树的好节点数量
return res + dfs(root->left,maxv) + dfs(root->right,maxv);
}
};数位成本和为目标值的最大数字
?
?
?
