LeetCode -- 第 392 场周赛

链接 : 

竞赛 - 力扣 (LeetCode)

3105. 最长的严格递增或递减子数组

. - 力扣（LeetCode）

用两个分组循环(本质就是双指针)，分别求出最长的递增和递减子数组的长度，然后取max ;

class Solution {
public:
    int longestMonotonicSubarray(vector<int>& nums) {
        int ans = 1 ;
        int n = nums.size() ;
        for(int i=0;i<n;i++){
            int j = i + 1 ;
            while(j<n && nums[j]>nums[j-1]) j++ ;
            ans = max(ans , j - i) ;
            i = j - 1 ;
        }
        for(int i=0;i<n;i++){
            int j = i + 1 ;
            while(j<n && nums[j]<nums[j-1]) j++ ;
            ans = max(ans , j - i) ;
            i = j - 1 ;
        }
        return ans ;
    }
};

 3106. 满足距离约束且字典序最小的字符串

. - 力扣（LeetCode）

模拟即可，详细请看代码 : 

class Solution {
public:
    
    string getSmallestString(string s, int k) {
        int n = s.size()  ;
        string ans = "" ;
        vector<char> a(n) ;
        int idx = 0 ;
        bool tag = true ;
        for(int i=0;i<n;i++){
            int d = min(s[i]-'a','a'-s[i]+26) ;
            if(d<=k) a[i] = 'a' , k -= d ;
            else{
                int z = k ;
                a[i] = s[i] - k ;
                idx = i ;
                tag = false ;
                break ;
            }
        }
        if(!tag)
        for(int t=idx+1;t<n;t++){
            a[t] = s[t] ;
        }
        for(int i=0;i<n;i++){
            ans.push_back(a[i]) ;
        }
        return ans ;
    }
};

3107. 使数组中位数等于 K 的最少操作数

. - 力扣（LeetCode）

也是模拟，赛时代码写的很繁琐 : 

typedef long long LL ;
class Solution {
public:
    long long minOperationsToMakeMedianK(vector<int>& nums, int k) {
        long long ans = 2e18 ;
        int n = nums.size() ;
        if(n==1){
            return abs(nums[0]-k);
        }
        sort(nums.begin(),nums.end()) ;
        if(n&1){//奇数
            // 前面不用管
            int t = n / 2 ;
            int x = nums[t] ;
            if(x==k){
                return 0 ;
            }else if(x>k){
                // 全部减小到k以下
                long long res = x - k ;
                for(int i=0;i<t;i++){
                    if(nums[i]>k){
                        res += nums[i]-k ;
                    }
                }
                ans = min(ans,res) ;
            }else{//x < k
                long long res = k - x ;
                for(int i=t+1;i<n;i++){
                    if(nums[i]<k) res += k - nums[i] ;
                }
                ans = min(ans,res) ;
            }
        }else{
            int x=n/2-1,y = n/2 ;
            long long z = nums[y] ;
            LL f = 1LL * k ;
            if(z==f){
                return 0LL ;
            }else if(z>f){
                // 前面不用管
                LL res = 0 ;
                for(int i=0;i<=y;i++){
                    if(nums[i]>f) res += nums[i] - f ;
                }
                ans = min(ans,res) ;
            }else{
                LL res = 0 ;
                for(int i=y;i<n;i++){
                    if(nums[i]<f) res += f - nums[i] ;
                }
                ans = min(res,ans) ;
            }
        }
        return ans ;
    }
};

3108 . 权图里旅途的最小代价

联通块问题 ，首先对于每一个查询:
如果两个值在同一个连通块内 ， 那么ans = 连通块中所有变的的与值和;

不在，直接返回-1，如果是同一个点的话，直接返回0；

class Solution {
public:
    vector<vector<pair<int,int>>> g ;
    vector<int> cc_and ;// 存放每个连通块的and和
    vector<int> ids ;// 存放每个结点到连通块号的映射

    int dfs(int x){
        ids[x] = cc_and.size() ;// 记录每个点所在连通块编号
        int and_ = -1 ; // -1 & x = x 
        for(auto &[y,w] : g[x]){
            and_ &= w ;
            if(ids[y] < 0){ // 没有访问过
                and_ &= dfs(y) ;
            }
        }
        return and_ ;
    }

    vector<int> minimumCost(int n, vector<vector<int>>& edges, vector<vector<int>>& query) {
        // and越多，值只会越小
        // s和t在同一连通块 : 连通块and和
        // 不在 : -1
        
        // 建图 : 
        g.resize(n) ;
        for(auto& e : edges){
            int x = e[0] , y = e[1] ,w = e[2] ;
            g[x].emplace_back(y,w) ;
            g[y].emplace_back(x,w) ; 
        }

        ids.resize(n,-1) ;
        for(int i=0;i<n;i++){
            if(ids[i]<0){//没有访问过
                cc_and.push_back(dfs(i)) ;
            }
        }

        vector<int> ans ;
        ans.reserve(query.size()) ;// 预分配空间
        for(auto &q : query){
            int s = q[0] , t = q[1] ;
            ans.push_back(s==t?0:ids[s]!=ids[t]?-1:cc_and[ids[s]]) ;
        }
        return ans ;
    }
};