LeetcodeBWk26

写在前面

这次双周赛还是比较简单的

在摸鱼了很久以后,某网友突然问我双周赛,让我想起来已经有快半年没做的双周赛

在比赛开始一半做,还好这次比较简单,在最后一分钟做完了

第 26 场双周赛

题目

A. 连续字符

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

请你返回字符串的能量。

示例 1:

1
2
3
输入:s = "leetcode"
输出:2
解释:子字符串 "ee" 长度为 2 ,只包含字符 'e' 。

示例 2:

1
2
3
输入:s = "abbcccddddeeeeedcba"
输出:5
解释:子字符串 "eeeee" 长度为 5 ,只包含字符 'e' 。

示例 3:

1
2
输入:s = "triplepillooooow"
输出:5

示例 4:

1
2
输入:s = "hooraaaaaaaaaaay"
输出:11

示例 5:

1
2
输入:s = "tourist"
输出:1

提示:

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

直接用一个计数器模拟计数即可

1
2
3
4
5
6
7
8
9
10
11
12
13
class Solution {
public int maxPower(String s) {
int ans=1;
int cur=1;
char []str=s.toCharArray();
for(int i=1;i<str.length;i++){
if(str[i-1]==str[i]) cur++;
else cur=1;
ans=Math.max(ans,cur);
}
return ans;
}
}

B. 最简分数

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

示例 1:

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

示例 2:

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

示例 3:

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

示例 4:

1
2
输入:n = 1
输出:[]

提示:

  • 1 <= n <= 100

枚举一下,gcd=1说明是最简分数

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
class Solution {
int gcd(int a,int b){
return b==0? a: gcd(b,a%b);
}
public List<String> simplifiedFractions(int n) {
List<String> ans=new ArrayList();
for(int i=1;i<=n;i++){
for(int j=1;j<i;j++){
int d=gcd(i,j);
if(d!=1) continue;
ans.add(Integer.toString(j)+"/"+Integer.toString(i));
}
}
return ans;
}
}

C. 统计二叉树中好节点的数目

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

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

示例 1:

img

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) 是路径中的最大值。

示例 2:

img

1
2
3
输入:root = [3,3,null,4,2]
输出:3
解释:节点 2 -> (3, 3, 2) 不是好节点,因为 "3" 比它大。

示例 3:

1
2
3
输入:root = [1]
输出:1
解释:根节点是好节点。

提示:

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

我们使用DFS,考虑进入某个节点的时候的值是val(实际上就是最大值),然后我们判断一下cur.val 和val 的关系,然后更新答案,用新的val去继续DFS即可

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
class Solution {
int ans=0;
void DFS(TreeNode cur,int val){
if(cur==null) return ;
if(cur.val >= val) ans++;
val=Math.max(cur.val,val);
DFS(cur.left,val);
DFS(cur.right,val);
}
public int goodNodes(TreeNode root) {
ans=0;
DFS(root,-100000);
return ans;
}
}

D. 数位成本和为目标值的最大数字

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

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

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

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

示例 1:

1
2
3
4
5
6
7
8
9
10
11
12
13
输入: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:

1
2
3
输入:cost = [7,6,5,5,5,6,8,7,8], target = 12
输出:"85"
解释:添加数位 '8' 的成本是 7 ,添加数位 '5' 的成本是 5 。"85" 的成本为 7 + 5 = 12 。

示例 3:

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

示例 4:

1
2
输入:cost = [6,10,15,40,40,40,40,40,40], target = 47
输出:"32211"

提示:

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

要数值最大,由于不含0,所以我们先必须要让位数最多,这个是一个背包计数问题,我们同时需要记录答案,如果有cost相同的数值,我们直接选大的,然后应该优先放大的

在背包计数的时候,同时也要注意要优先选大的数的值

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
33
34
35
36
37
38
class Solution {
public:
int dp[5000+10];
int jp[5000+10];

int arr[5000+10];
string largestNumber(vector<int>& cost, int target) {
memset(arr,0,sizeof(0));
memset(dp,0,sizeof(dp));
memset(jp,0,sizeof(jp));
int n=target;
for(int i=1;i<=n;i++){
for(int j=0;j<9;j++){
int p=cost[j];
if(i-p<0) continue;
if(i-p!=0 && dp[i-p]==0) continue;
if(dp[i-p]+1>=dp[i]) {
dp[i]=dp[i-p]+1;
jp[i]=p;
}
}
}
string ans(dp[n],'0');
if(dp[n]==0) return "0";
while(n){
arr[jp[n]]++;
n-=jp[n];
}
int index=0;
for(int i=8;i>=0;i--){
while(arr[cost[i]]){
arr[cost[i]]--;
ans[index++]=('1'+i);
}
}
return ans;
}
};

总结

这次题目比较简单,就是最后一题犯了太多的sb错误,导致写了非常之久