leetcode 154周赛

墨蓝 2023-08-17 15:44 103阅读 0赞

# 链接：[https://leetcode-cn.com/contest/weekly-contest-154][https_leetcode-cn.com_contest_weekly-contest-154] #

> 给你一个字符串 text，你需要使用 text 中的字母来拼凑尽可能多的单词 "balloon"（气球）。  
> 字符串 text 中的每个字母最多只能被使用一次。请你返回最多可以拼凑出多少个单词 "balloon"。

思路：用哈希表存储b,a,l,o,n,存在的次数，然后取最小值o,l 需要特殊处理。

class Solution {
    public:
        int maxNumberOfBalloons(string text) {
            unordered_map<int,int> hash;
            for(int i=0;i<text.size();++i){
                int j=text[i]-'a';
                hash[j]++;
            }
            int b=hash['b'-'a'];
            int a=hash['a'-'a'];
            int l=hash['l'-'a'];
            int o=hash['o'-'a'];
            int n=hash['n'-'a'];
            l/=2;
            o/=2;
            int ans=1e9;
            ans=min(ans,a);
            
            ans=min(ans,b);
            
            ans=min(ans,l);
            
            ans=min(ans,o);
           
            ans=min(ans,n);
            return ans;
        }
    };

> 给出一个字符串 s（仅含有小写英文字母和括号）。  
> 请你按照从括号内到外的顺序，逐层反转每对匹配括号中的字符串，并返回最终的结果。  
> 注意，您的结果中 不应 包含任何括号。

思路：  
1.括号问题，要用到栈(括号的匹配情况是一定的  
2.可以用string模拟栈  
3.每次将(压入栈  
4.如果遇到）就出栈，直到遇到(  
5.然后将翻转过的字符串再压入栈，一次翻转完成  
6.重复以上操作

class Solution {
    public:
        string reverseParentheses(string s) {
            string res;
            for(int i=0;i<s.size();++i){
                if(s[i]==')'){
                    string t;
                    while(res.back()!='('){
                        t+=res.back();
                        res.pop_back();
                    }
                    res.pop_back();
                    res+=t;
                }
                else{
                    res+=s[i];
                }
            }
            return res;
        }
    };

> 给你一个整数数组 arr 和一个整数 k。  
> 首先，我们要对该数组进行修改，即把原数组 arr 重复 k 次。  
> 举个例子，如果 arr = \[1, 2\] 且 k = 3，那么修改后的数组就是 \[1, 2, 1, 2, 1, 2\]。  
> 然后，请你返回修改后的数组中的最大的子数组之和。  
> 注意，子数组长度可以是 0，在这种情况下它的总和也是 0。  
> 由于 结果可能会很大，所以需要 模（mod） 10^9 + 7 后再返回。

思路：  
1.若使用一般方法，将arr重复k次的结果重新构成一个数组，然后求最大连续子序列，这样的复杂度不容乐观(10^9  
2.另外这里的最大值（10^14）是不会超过long long (10^18)的  
3.我们可以直到答案只有以下三种情况  
4.就是只在一个arr里取答案  
5.在两个arr里取答案(最大前缀+最大后缀)  
6.在多个arr里面取答案(最大前缀+最大后缀+中间的区间和)  
7.对于6来说，他能更新答案的话arr区间和必须大于零，所以只有加k-2个和不加的两种情况。  
8.最大后缀可以用 区间和-最小前缀  
9.对于4 ，其实就是最大连续子序列和，但是这里我们可以不直接求，而是用一段的前缀和减去前一段的最小前缀和，这是等价的。

class Solution {
    public:
        int kConcatenationMaxSum(vector<int>& arr, int k) {
            long long ans=0;
            int mod=1e9+7;
            int n=arr.size();
            vector<long long> sum(n+1);
            vector<long long> minr(n+1),maxr(n+1);
            sum[0]=arr[0];
            minr[0]=min(0,arr[0]);
            maxr[0]=max(0,arr[0]);
            ans=max(ans,sum[0]-minr[0]);
            for(int i=1;i<n;++i){
                sum[i]=sum[i-1]+arr[i];
                minr[i]=min(minr[i-1],sum[i]);
                maxr[i]=max(maxr[i-1],sum[i]);
                ans=max(ans,sum[i]-minr[i]);
            }
            if(k>=2){
                ans=max(ans,max(maxr[n-1]+sum[n-1]-minr[n-1],maxr[n-1]+sum[n-1]-minr[n-1]+(k-2)*sum[n-1]));
            }
            return (int)(ans%mod);
        }
    };

> 力扣数据中心有 n 台服务器，分别按从 0 到 n-1 的方式进行了编号。  
> 它们之间以「服务器到服务器」点对点的形式相互连接组成了一个内部集群，其中连接 connections 是无向的。  
> 从形式上讲，connections\[i\] = \[a, b\] 表示服务器 a 和 b 之间形成连接。任何服务器都可以直接或者间接地通过网络到达任何其他服务器。  
> 「关键连接」是在该集群中的重要连接，也就是说，假如我们将它移除，便会导致某些服务器无法访问其他服务器。  
> 请你以任意顺序返回该集群内的所有 「关键连接」。

思路：tarjan求桥模板题(网上也有很多讲解，可以搜索一下

class Solution {
    public:
        vector<vector<int>> res;//答案
        vector<vector<int>> g;//存图
        vector<int> low,dfn;//tarjan
        int cot;
        void targan(int x,int p)
        {
            low[x]=dfn[x]=++cot;
            for(auto y:g[x]){
                if(!dfn[y]){
                    targan(y,x);
                    low[x]=min(low[x],low[y]);
                    if(low[y]>dfn[x]){
                        res.push_back({x,y});
                    }
                }
                else{
                    if(y==p)continue;
                    else{
                        low[x]=min(low[x],dfn[y]);
                    }
                }
            }
        }
        vector<vector<int>> criticalConnections(int n, vector<vector<int>>& connections) {
            g=vector<vector<int>>(n);
            low=dfn=vector<int>(n);
            for(auto t:connections){
                g[t[0]].push_back(t[1]);
                g[t[1]].push_back(t[0]);
            }
            for(int i=0;i<n;++i){
                if(!dfn[i]){
                    targan(i,-1);
                }
            }
            return res;
        }
    };

转载于:https://www.cnblogs.com/clear-love/p/11522539.html

[https_leetcode-cn.com_contest_weekly-contest-154]: https://leetcode-cn.com/contest/weekly-contest-154