leetcode biweekly contest 93

双周赛的前三题都是简单题目，最后一题比较难，思考了很长时间还是没有太好的思路。

6261. 数组中字符串的最大值

一个由字母和数字组成的字符串的值定义如下：

如果字符串只包含数字，那么值为该字符串在 10 进制下的所表示的数字。
否则，值为字符串的长度。

给你一个字符串数组 strs ，每个字符串都只由字母和数字组成，请你返回 strs 中字符串的 最大值 。

示例 1：

输入：strs = ["alic3","bob","3","4","00000"]
输出：5
解释：
- "alic3" 包含字母和数字，所以值为长度 5 。
- "bob" 只包含字母，所以值为长度 3 。
- "3" 只包含数字，所以值为 3 。
- "4" 只包含数字，所以值为 4 。
- "00000" 只包含数字，所以值为 0 。
所以最大的值为 5 ，是字符串 "alic3" 的值。

示例 2：

输入：strs = ["1","01","001","0001"]
输出：1
解释：
数组中所有字符串的值都是 1 ，所以我们返回 1 。

提示：

1 <= strs.length <= 100
1 <= strs[i].length <= 9
strs[i] 只包含小写英文字母和数字。

地址

https://leetcode.cn/contest/biweekly-contest-93/problems/maximum-value-of-a-string-in-an-array/

题意

直接遍历

思路

将每个字符串进行转换，如果只含有数字则进行转换，否则则不进行转换。
复杂度分析：

时间复杂度：$O(mn)$。
空间复杂度：$O(1)$。

代码

class Solution {
public:
    int maximumValue(vector<string>& strs) {
        int n = strs.size();
        int res = 0;
        for (int i = 0; i < n; i++) {
            bool isNum = true;
            for (auto c : strs[i]) {
                if (!isdigit(c)) {
                    isNum = false;
                    break;
                }
            }
            if (!isNum) {
                res = max(res, int(strs[i].size()));
            } else {
                res = max(res, stoi(strs[i]));
            }
        }
        return res;
    }
};

6262. 图中最大星和

给你一个 n 个点的无向图，节点从 0 到 n - 1 编号。给你一个长度为 n 下标从 0 开始的整数数组 vals ，其中 vals[i] 表示第 i 个节点的值。

同时给你一个二维整数数组 edges ，其中 edges[i] = [ai, bi] 表示节点 ai 和 bi 之间有一条双向边。

星图是给定图中的一个子图，它包含一个中心节点和 0 个或更多个邻居。换言之，星图是给定图中一个边的子集，且这些边都有一个公共节点。

下图分别展示了有 3 个和 4 个邻居的星图，蓝色节点为中心节点。

星和定义为星图中所有节点值的和。

给你一个整数 k ，请你返回至多包含 k 条边的星图中的 最大星和 。

示例 1：

输入：vals = [1,2,3,4,10,-10,-20], edges = [[0,1],[1,2],[1,3],[3,4],[3,5],[3,6]], k = 2
输出：16
解释：上图展示了输入示例。
最大星和对应的星图在上图中用蓝色标出。中心节点是 3 ，星图中还包含邻居 1 和 4 。
无法得到一个和大于 16 且边数不超过 2 的星图。

示例 2：

输入：vals = [-5], edges = [], k = 0
输出：-5
解释：只有一个星图，就是节点 0 自己。
所以我们返回 -5 。

提示：

n == vals.length
1 <= n <= 105
-104 <= vals[i] <= 104
0 <= edges.length <= min(n * (n - 1) / 2``, 105)
edges[i].length == 2
0 <= ai, bi <= n - 1
ai != bi
0 <= k <= n - 1

地址

https://leetcode.cn/contest/biweekly-contest-93/problems/maximum-star-sum-of-a-graph/

题意

排序

思路

我们将与每个节点 $x$ 相邻的节点按照其值的从大到小进行排序，我们每次最多取 $k$ 个最大的相邻节点即可，即求前 $k$ 项的前缀和最大值即可。
复杂度分析：

时间复杂度：$O(V \log E + V + E)$，其中 $V$ 为顶点的数目, $E$ 表示边的数目。
空间复杂度：$O(V + E)$，其中 $V$ 为顶点的数目, $E$ 表示边的数目。

代码

class Solution {
public:
    int maxStarSum(vector<int>& vals, vector<vector<int>>& edges, int k) {
        int n = vals.size();
        vector<vector<int>> graph(n);
        for (auto v : edges) {
            graph[v[0]].emplace_back(v[1]);
            graph[v[1]].emplace_back(v[0]);
        }
        for (int i = 0; i < n; i++) {
            sort(graph[i].begin(), graph[i].end(), [&](int a, int b) {
                return vals[a] > vals[b];
            });
        }
        int res = INT_MIN;
        for (int i = 0; i < n; i++) {
            int sum = vals[i];
            res = max(res, sum);
            for (int j = 0; j < graph[i].size() && j < k; j++) {
                sum += vals[graph[i][j]];
                res = max(res, sum);
            }
        }
        return res;
    }
};

6263. 青蛙过河 II

给你一个下标从 0 开始的整数数组 stones ，数组中的元素 严格递增 ，表示一条河中石头的位置。

一只青蛙一开始在第一块石头上，它想到达最后一块石头，然后回到第一块石头。同时每块石头至多到达 一次。

一次跳跃的长度是青蛙跳跃前和跳跃后所在两块石头之间的距离。

更正式的，如果青蛙从 stones[i] 跳到 stones[j] ，跳跃的长度为 |stones[i] - stones[j]| 。

一条路径的代价是这条路径里的 最大跳跃长度 。

请你返回这只青蛙的 最小代价 。

示例 1：

输入：stones = [0,2,5,6,7]
输出：5
解释：上图展示了一条最优路径。
这条路径的代价是 5 ，是这条路径中的最大跳跃长度。
无法得到一条代价小于 5 的路径，我们返回 5 。

示例 2：

输入：stones = [0,3,9]
输出：9
解释：
青蛙可以直接跳到最后一块石头，然后跳回第一块石头。
在这条路径中，每次跳跃长度都是 9 。所以路径代价是 max(9, 9) = 9 。
这是可行路径中的最小代价。

提示：

2 <= stones.length <= 105
0 <= stones[i] <= 109
stones[0] == 0
stones 中的元素严格递增。

地址

https://leetcode.cn/contest/biweekly-contest-93/problems/frog-jump-ii/

题意

贪心算法

思路

最优算法肯定为隔一个元素跳，要么去的时候每次跳的步骤为 $[0,2,4,\cdots]$，要么回的时候每次跳的步骤则为 $[0,1,3,\cdots]$，题目等价于有两只青蛙从 $0$ 开始起跳，且二者没有共同落地地点都到达终点时的二者的最小跳的距离。
复杂度分析

时间复杂度：时间复杂度为 $O(n)$，$n$ 表示数组的长度。
空间复杂度：时间复杂度为 $O(1)$。

代码

class Solution {
public:
    int maxJump(vector<int>& stones) {
        int n = stones.size();
        int res = 0;
        for (int i = 0; i < n; i += 2) {
            res = max(res, stones[min(i + 2, n - 1)] - stones[i]);
        }
        for (int i = 1; i < n; i += 2) {
            res = max(res, stones[min(i + 2, n - 1)] - stones[i]);
        }
        return res;
    }
};

6264. 让数组不相等的最小总代价

给你两个下标从 0 开始的整数数组 nums1 和 nums2 ，两者长度都为 n 。

每次操作中，你可以选择交换 nums1 中任意两个下标处的值。操作的开销为两个下标的和。

你的目标是对于所有的 0 <= i <= n - 1 ，都满足 nums1[i] != nums2[i] ，你可以进行 任意次 操作，请你返回达到这个目标的最小总代价。

请你返回让 nums1 和 nums2 满足上述条件的 最小总代价 ，如果无法达成目标，返回 -1 。

示例 1：

输入：nums1 = [1,2,3,4,5], nums2 = [1,2,3,4,5]
输出：10
解释：
实现目标的其中一种方法为：
- 交换下标为 0 和 3 的两个值，代价为 0 + 3 = 3 。现在 nums1 = [4,2,3,1,5] 。
- 交换下标为 1 和 2 的两个值，代价为 1 + 2 = 3 。现在 nums1 = [4,3,2,1,5] 。
- 交换下标为 0 和 4 的两个值，代价为 0 + 4 = 4 。现在 nums1 = [5,3,2,1,4] 。
最后，对于每个下标 i ，都有 nums1[i] != nums2[i] 。总代价为 10 。
还有别的交换值的方法，但是无法得到代价和小于 10 的方案。

示例 2：

输入：nums1 = [2,2,2,1,3], nums2 = [1,2,2,3,3]
输出：10
解释：
实现目标的一种方法为：
- 交换下标为 2 和 3 的两个值，代价为 2 + 3 = 5 。现在 nums1 = [2,2,1,2,3] 。
- 交换下标为 1 和 4 的两个值，代价为 1 + 4 = 5 。现在 nums1 = [2,3,1,2,2] 。
总代价为 10 ，是所有方案中的最小代价。

示例 3：

输入：nums1 = [1,2,2], nums2 = [1,2,2]
输出：-1
解释：
不管怎么操作，都无法满足题目要求。
所以返回 -1 。

提示：

n == nums1.length == nums2.length
1 <= n <= 105
1 <= nums1[i], nums2[i] <= n

地址

https://leetcode.cn/contest/biweekly-contest-93/problems/minimum-total-cost-to-make-arrays-unequal/

题意

数学问题

思路

看了一个非常的好的解题思路，本质还是数论的问题：题解
复杂度分析：

时间复杂度：$O(n)$，其中 $n$ 表示数组的元素。
空间复杂度：$O(n)$，其中 $n$ 表示数组的元素。

代码

class Solution {
public:
    long long minimumTotalCost(vector<int>& nums1, vector<int>& nums2) {
        int n = nums1.size();
        vector<int> sameIndex;
        for (int i = 0; i < n; i++) {
            if (nums1[i] == nums2[i]) {
                sameIndex.push_back(i);
            }
        }
        unordered_map<int, int> freq;
        int maxVal = -1;
        int maxFreq = 0;
        for (auto index : sameIndex) {
            freq[nums1[index]]++;
            if (freq[nums1[index]] > maxFreq) {
                maxFreq = freq[nums1[index]];
                maxVal = nums1[index];
            }
        }
        if (maxFreq * 2 <= sameIndex.size()) {
            return accumulate(sameIndex.begin(), sameIndex.end(), 0LL);
        }
        for (int i = 0; i < n; i++) {
            if (nums1[i] == nums2[i]) continue;
            if (nums1[i] != maxVal && nums2[i] != maxVal) {
                sameIndex.push_back(i);
            }
            if (maxFreq * 2 <= sameIndex.size()) {
                break;
            }
        }
        if (maxFreq * 2 <= sameIndex.size()) {
            return accumulate(sameIndex.begin(), sameIndex.end(), 0LL);
        }
        return -1;
    }
};

欢迎关注和打赏，感谢支持！

关注我的博客: http://whistle-wind.com/
关注我的知乎：https://www.zhihu.com/people/da-hua-niu
关注我的微信公众号: 公务程序猿

Tags: 力扣周赛题解

← leetcode contest 323 leetcode contest 324 →

扫描二维码，分享此文章