LeetCode第 26 场双周赛

LeetCode第 26 场双周赛

LeetCode第 26 场双周赛题解。

连续字符(双指针)

给你一个字符串 s ,字符串的「能量」定义为:只包含一种字符的最长非空子字符串的长度。

请你返回字符串的能量。

示例 1:

输入:s = “leetcode”
输出:2
解释:子字符串 “ee” 长度为 2 ,只包含字符 ‘e’ 。

示例 2:

输入:s = “abbcccddddeeeeedcba”
输出:5
解释:子字符串 “eeeee” 长度为 5 ,只包含字符 ‘e’ 。

提示:

  • 1 <= s.length <= 500
  • s 只包含小写英文字母。

思路

双指针裸题。

代码

连续字符
1
2
3
4
5
6
7
8
9
10
11
12
13
14
class Solution {
public:
int maxPower(string s) {
int res=0;
for(int i=0;i<s.size();i++){
int t=0;
int j=i+1;
while(j<s.size()&&s[j]==s[j-1]) j++;
res=max(res,j-i);
i=j-1;
}
return res;
}
};

最简分数 (辗转相除法)

给你一个整数 n ,请你返回所有 0 到 1 之间(不包括 0 和 1)满足分母小于等于 n最简分数 。分数可以以任意顺序返回。

示例 1:

输入:n = 2
输出:[“1/2”]
解释:“1/2” 是唯一一个分母小于等于 2 的最简分数。

示例 2:

输入:n = 3
输出:[“1/2”,”1/3”,”2/3”]

示例 3:

输入:n = 4
输出:[“1/2”,”1/3”,”1/4”,”2/3”,”3/4”]
解释:“2/4” 不是最简分数,因为它可以化简为 “1/2” 。

示例 4:

输入:n = 1
输出:[]

思路

直接先从2 ~ n枚举分母,再从2 ~ i-1枚举分子,找出分子分母没有公因数的组合即可。

代码

最简分数
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
class Solution {
public:
int gcd(int a,int b){
return b==0?a:gcd(b,a%b);
}
vector<string> simplifiedFractions(int n) {
vector<string> res;
for(int i=2;i<=n;i++){
string t="1/"+to_string(i);
res.push_back(t);
for(int j=2;j<i;j++){
//判断两个数是否有公因子
if(gcd(i,j)==1){
t=to_string(j)+"/"+to_string(i);
res.push_back(t);
}
}
}
return res;
}
};

统计二叉树中好节点的数目 (DFS)

给你一棵根为 root 的二叉树,请你返回二叉树中好节点的数目。

「好节点」X 定义为:从根到该节点 X 所经过的节点中,没有任何节点的值大于 X 的值。

示例 1:

1
2
3
4
5
6
7
输入:root = [3,1,4,3,null,1,5]
输出:4
解释:图中蓝色节点为好节点。
根节点 (3) 永远是个好节点。
节点 4 -> (3,4) 是路径中的最大值。
节点 5 -> (3,4,5) 是路径中的最大值。
节点 3 -> (3,1,3) 是路径中的最大值。

提示:

  • 二叉树中节点数目范围是 [1, 10^5]
  • 每个节点权值的范围是 [-10^4, 10^4]

思路

一开始看到这道题我有点慌,因为我不太熟悉用这种链表指针的方式动态的建图,但是后来仔细看了下题之后发现这其实是一个dfs我们只用遍历一遍整棵树即可,然后在dfs的过程中记录下遍历到当前结点时的最大值即可,如果当前节点value比最大值大那么答案就+1,然后再把这个最大值和自己的值取个max传递给自己的孩子结点。

代码

统计二叉树中好节点的数目
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
/**
* 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 ans=0;

void dfs(TreeNode* u,int cur){
if(u==NULL) return;
if(u->val >= cur)
ans++;
int t=max(u->val,cur);
dfs(u->left,t);
dfs(u->right,t);
}

int goodNodes(TreeNode* root) {
dfs(root,root->val);//注意由于结点的val可能为负数,所以不能初始化为0
return ans;
}
};

数位成本和为目标值的最大数字 (完全背包)

给你一个整数数组 cost 和一个整数 target 。请你返回满足如下规则可以得到的 最大 整数:

  • 给当前结果添加一个数位(i + 1)的成本为 cost[i]cost 数组下标从 0 开始)。
  • 总成本必须恰好等于 target
  • 添加的数位中没有数字 0 。

由于答案可能会很大,请你以字符串形式返回。

如果按照上述要求无法得到任何整数,请你返回 “0” 。
示例 1:

输入:cost = [4,3,2,5,6,7,2,5,5], target = 9
输出:“7772”
解释:添加数位 ‘7’ 的成本为 2 ,添加数位 ‘2’ 的成本为 3 。所以 “7772” 的代价为 2*3+ 3*1 = 9 。 “997” 也是满足要求的数字,但 “7772” 是较大的数字。
数字 成本
1 -> 4
2 -> 3
3 -> 2
4 -> 5
5 -> 6
6 -> 7
7 -> 2
8 -> 5
9 -> 5

示例 2:

输入:cost = [7,6,5,5,5,6,8,7,8], target = 12
输出:“85”
解释:添加数位 ‘8’ 的成本是 7 ,添加数位 ‘5’ 的成本是 5 。”85” 的成本为 7 + 5 = 12 。

示例 3:

输入:cost = [2,4,6,2,4,6,4,4,4], target = 5
输出:“0”
解释:总成本是 target 的条件下,无法生成任何整数。

示例 4:

输入:cost = [6,10,15,40,40,40,40,40,40], target = 47
输出:“32211”

提示:

  • cost.length == 9
  • 1 <= cost[i] <= 5000
  • 1 <= target <= 5000

思路

这题仔细读题不难发现这是一道完全背包的题目,但是比较反常的是它的位数太大了!因此在数值的判断以及初始化的时候我们要格外的小心。

由于这里是求的是”恰好”情况下的最大值,所以在初始化的时候我们要把f[0]初始化为0,把其他的初始化为-∞;f[0]代表着target=0的情况,在这种情况下显然能凑出的值只有0。

代码

数位成本和为目标值的最大数字
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
class Solution {
public:
const static int N=5010;
string f[N];

//判断a是否比b大
bool cmp(string a,string b){
if(a.size()!=b.size()) return a.size()>b.size();
for(int i=0;i<a.size();i++){
if(a[i]!=b[i]) return a[i]>b[i];
}
return true;
}

string largestNumber(vector<int>& cost, int target) {
//由于这里是"恰好"要用完target,因此只有f[0]是可达的其他的状态标记为不可达
for(int i=1;i<N;i++) f[i]="-";

for(int i=0;i<cost.size();i++){
for(int j=cost[i];j<=target;j++){
           //标记为"-"可以理解为-∞
               if(f[j-cost[i]]=="-") continue;
string t=to_string(i+1)+f[j-cost[i]];
if(cmp(t,f[j])) f[j]=t;
}
}



return f[target]=="-"?"0":f[target];
}
};

评论