LeetCode 第 392 场周赛个人题解

class Solution {
public:
    int longestMonotonicSubarray(vector<int>& nums) {
        int ret = 1, pre = -1, cur = 0;
        for(auto x : nums){
            if(x > pre)
                cur++;
            else
                ret = max(ret, cur), cur = 1;
            pre = x;
        }
        ret = max(ret, cur);
        pre = 1e9, cur = 0;
        for(auto x : nums){
            if(x < pre)
                cur++;
            else
                ret = max(ret, cur), cur = 1;
            
            pre = x;
        }
        ret = max(ret, cur);
        return ret;
    }
};

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

原题链接

满足距离约束且字典序最小的字符串 - 力扣 (LeetCode) 竞赛

思路分析

贪心

求字典序最小，那么我们可以初始目标字符串为全部都是'a'

然后计算此时的距离tot

然后倒序遍历进行修正，不断减少tot，当tot <= k我们退出循环即可

时间复杂度O(n)

AC代码

class Solution:
    def getSmallestString(self, s: str, k: int) -> str:
        n = len(s)
        ret = []
        tot = sum(min(ord(x) - ord('a'), ord('a') + 26 - ord(x)) for x in s)
        i = n - 1
        while tot > k:
            dif = min(ord(s[i]) - ord('a'), ord('a') + 26 - ord(s[i]))
            cost = min(dif, tot - k)
            ret += chr(ord(s[i]) - dif + cost)
            tot -= cost
            i -= 1
        ret += ['a'] * (i + 1)
        return "".join(ret[::-1])

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

原题链接

使数组中位数等于 K 的最少操作数 - 力扣 (LeetCode) 竞赛

思路分析

我们对原数组预排序

我们先确定中位数位置mid

然后mid左边要小于等于k，右边要大于等于k

操作数就是左边大于k的数字与k的差的和以及右边小于k的数字与k的差的和

然后对于偶数长度进行mid特判，取元素大的那个位置为mid，然后代价要加上abs(nums[mid] - k)

时间复杂度O(nlogn)

AC代码

class Solution:
    def minOperationsToMakeMedianK(self, nums: List[int], k: int) -> int:
        n = len(nums)
        nums.sort()
        mid = n // 2
        if n & 1:
            return abs(nums[mid] - k) + sum(x - k for x in nums[0:mid] if x > k) + sum(k - x for x in nums[mid + 1::] if x < k)
        if nums[mid - 1] > nums[mid]:
            mid -= 1
        return abs(nums[mid] - k) + sum(x - k for x in nums[0:max(0, mid)] if x > k) + sum(k - x for x in nums[mid + 1::] if x < k)

100244. 带权图里旅途的最小代价

原题链接

带权图里旅途的最小代价 - 力扣 (LeetCode) 竞赛

思路分析

并查集

条件反射敲了一遍dijkstra然后敲完想了下根本用不到

因为题目说了，一趟旅途可能访问同一条边或者同一个节点多次。

那么对于处于同一个连通块内任意两个节点的最小代价显然就是所有边权的与值

由于是无向图，我们用并查集处理连通块，然后计算每个连通块内所有边的与值即可

然后比较坑的一点是：题目没有说起点终点相同结果为0，所以注意不要搞成1<<31 - 1了

对于查询我们先特判相同起点终点，然后查询是否在一个连通块内即可

时间复杂度O(m + q)，m为边数，q为查询数目

AC代码

class Solution {
public:
int andsum[100005];
int p[100005];
    int findp(int x){
        return p[x] < 0 ? x : p[x] = findp(p[x]);
    }
    void merge(int x, int y){
        int px = findp(x), py = findp(y);
        if(px == py) return;
        if(p[px] > p[py]) swap(px, py);
        p[px] += p[py], p[py] = px;
    }
    vector<int> minimumCost(int n, vector<vector<int>>& edges, vector<vector<int>>& query) {
        memset(andsum, -1, sizeof andsum);
        memset(p, -1, sizeof p);
        for(auto& e : edges) merge(e[0], e[1]);
        for(auto& e : edges) 
            if(andsum[findp(e[0])] == -1)
                andsum[findp(e[0])] = e[2];
            else
                andsum[findp(e[0])] &= e[2];
        vector<int> ret;
        for(auto& q : query)
            if(q[0] == q[1])
                ret.emplace_back(0);
            else if(findp(q[0]) != findp(q[1]))
                ret.emplace_back(-1);
            else
                ret.emplace_back(andsum[findp(q[0])]);
        return ret;
    }
};

原文地址:https://blog.csdn.net/EQUINOX1/article/details/137458279 本文来自互联网用户投稿，该文观点仅代表作者本人，不代表本站立场。本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。如若转载，请注明出处：https://www.suanlizi.com/kf/1777314955759063040.html 如若内容造成侵权/违法违规/事实不符，请联系《酸梨子》网邮箱：1419361763@qq.com进行投诉反馈，一经查实，立即删除！

阅读全部