LeetCode第 26 场双周赛
LeetCode8 分钟 读完 (大约 1169 个字)  0次访问

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];
    }
};
#

喜欢这篇文章？打赏一下作者吧

评论

最新文章

×