当前位置:   article > 正文

LeetCode 316 周赛

leetcode 316

2446. 判断两个事件是否存在冲突

给你两个字符串数组 event1event2 ,表示发生在同一天的两个闭区间时间段事件,其中:

  • event1 = [startTime1, endTime1]
  • event2 = [startTime2, endTime2]

事件的时间为有效的 24 小时制且按 HH:MM 格式给出。

当两个事件存在某个非空的交集时(即,某些时刻是两个事件都包含的),则认为出现 冲突

如果两个事件之间存在冲突,返回 true ;否则,返回 false

示例

输入:event1 = ["01:15","02:00"], event2 = ["02:00","03:00"]
输出:true
解释:两个事件在 2:00 出现交集。
  • 1
  • 2
  • 3

思路

就是求两个区间是否相交。周赛当天我的做法是,将HH:MM的时间归一化为当天的第X分钟,于是某一时刻HH:MM就能用一个数字表示,于是就变成了简单的求两个区间是否相交的问题。

C++:

// C++
class Solution {
public:
    int parse(string& s) {
        int h = stoi(s.substr(0, 2));
        int m = stoi(s.substr(3));
        return h * 60 + m;
    }

    bool haveConflict(vector<string>& event1, vector<string>& event2) {
        int s1 = parse(event1[0]), e1 = parse(event1[1]);
        int s2 = parse(event2[0]), e2 = parse(event2[1]);
        return max(s1, s2) <= min(e1, e2);
    }
};
  • 1
  • 2
  • 3
  • 4
  • 5
  • 6
  • 7
  • 8
  • 9
  • 10
  • 11
  • 12
  • 13
  • 14
  • 15

Java:

// Java
class Solution {
    int parse(String s) {
        String[] ss = s.split(":");
        return 60 * Integer.parseInt(ss[0]) + Integer.parseInt(ss[1]);
    }
    public boolean haveConflict(String[] event1, String[] event2) {
        int s1 = parse(event1[0]), e1 = parse(event1[1]);
        int s2 = parse(event2[0]), e2 = parse(event2[1]);
        // [s1, e1]
        // [s2, e2]
        return Math.max(s1, s2) <= Math.min(e1, e2);
    }
}
  • 1
  • 2
  • 3
  • 4
  • 5
  • 6
  • 7
  • 8
  • 9
  • 10
  • 11
  • 12
  • 13
  • 14

其实也可以不用将字符串转化为数字进行比较。这道题目的数据格式,字符串的字典序大小关系,和对应的数字的大小关系是一致的。

// C++
class Solution {
public:
    bool haveConflict(vector<string>& event1, vector<string>& event2) {
        string s = max(event1[0], event2[0]);
        string e = min(event1[1], event2[1]);
        return s <= e;
    }
};
  • 1
  • 2
  • 3
  • 4
  • 5
  • 6
  • 7
  • 8
  • 9
// Java
class Solution {
	public boolean haveConflict(String[] event1, String[] event2) {
		String s = event1[0].compareTo(event2[0]) > 0 ? event1[0] : event2[0];
		String e = event1[1].compareTo(event2[1]) < 0 ? event1[1] : event2[1];
		return s.compareTo(e) <= 0;
	}
}
  • 1
  • 2
  • 3
  • 4
  • 5
  • 6
  • 7
  • 8

2447.最大公因数等于 K 的子数组数目

给你一个整数数组 nums 和一个整数 k ,请你统计并返回 nums 的子数组中元素的最大公因数等于 k 的子数组数目。

子数组 是数组中一个连续的非空序列。

数组的最大公因数 是能整除数组中所有元素的最大整数。

提示:

  • 1 <= nums.length <= 1000
  • 1 <= nums[i], k <= 10^9

示例

输入:nums = [9,3,1,2,6,3], k = 3
输出:4
解释:nums 的子数组中,以 3 作为最大公因数的子数组如下:

  • [9,3,1,2,6,3]
  • [9,3,1,2,6,3]
  • [9,3,1,2,6,3]
  • [9,3,1,2,6,3]

思路

一个子数组中所有元素的最大公因数等于k,含义是:这个子数组中的全部元素,都是k的倍数,并且这些数的最大公约数是k。周赛当天我的想法是,既然都是k的倍数,那我把全部数都先除以个k,那么满足条件的子数组,一定满足如下的性质:

  • 子数组中所有元素都不为0
  • 子数组中全部数的最大公约数是1

其实这个是否把所有数都除以k,没什么太大区别,如果不除以k的话,子数组需要满足如下性质

  • 子数组中所有元素都是k的倍数
  • 子数组中全部数的最大公约数是k

此时看了眼这道题的数据范围,n只有1000,那么暴力枚举全部子数组,需要10^6,而每次判断子数组是否满足条件,只需要求个gcd,而gcd的时间复杂度大概在 O ( l o g n ) O(logn) O(logn)级别,那么是不会超时的。并且,我们在枚举子数组的过程中,如果中间遇到了某个元素使得上述2个条件不能满足,则可以提前退出该轮循环,因为子数组要求必须连续,所以暴力法是可以做的。

暴力法的时间复杂度为 O ( n × ( n + l o g U ) ) O(n×(n+logU)) O(n×(n+logU)),外层循环是n,内层循环是求n个数的最大公约数。注意求n个数的最大公约数的时间复杂度为 O ( n + l o g U ) O(n + logU) O(n+logU),U是n个数中的最大值。注意并不是 O ( n l o g U ) O(nlogU) O(nlogU)。(至于为什么还没搞清楚)

C++:

// C++ 8ms 还挺快
class Solution {
public:
    int gcd(int a, int b) {
        return !b ? a : gcd(b, a % b);
    }

    int subarrayGCD(vector<int>& nums, int k) {
        int n = nums.size(), ans = 0;
        // 枚举全部的子数组
        for (int i = 0; i < n; i++) {
            // 枚举所有左端点为i的子数组
            if (nums[i] % k != 0) continue; // 如果第一个位置都不是k的倍数, 直接跳过, 其实这一行也可以不写
            int g = 0;
            for (int j = i; j < n; j++) {
                if (nums[j] % k != 0) break; // 从这里断掉了, 后面的不用枚举了,因为子数组必须连续
                g = gcd(nums[j], g); // 更新一下[i, j]所有数的最大公约数
                if (g == k) ans++; // 找到一个满足条件的子数组
            }
        }
        return ans;
    }
};
  • 1
  • 2
  • 3
  • 4
  • 5
  • 6
  • 7
  • 8
  • 9
  • 10
  • 11
  • 12
  • 13
  • 14
  • 15
  • 16
  • 17
  • 18
  • 19
  • 20
  • 21
  • 22
  • 23

2448. 使数组相等的最小开销

给你两个下标从 0 开始的数组 numscost ,分别包含 n 整数。

你可以执行下面操作 任意 次:

  • nums任意 元素增加或者减小 1

对第 i 个元素执行一次操作的开销是 cost[i]

请你返回使 nums 中所有元素 相等最少 总开销。

提示:

  • n == nums.length == cost.length
  • 1 <= n <= 10^5
  • 1 <= nums[i], cost[i] <= 10^6

示例

输入:nums = [1,3,5,2], cost = [2,3,1,14]
输出:8
解释:我们可以执行以下操作使所有元素变为 2 :
- 增加第 0 个元素 1 次,开销为 2 。
- 减小第 1 个元素 1 次,开销为 3 。
- 减小第 2 个元素 3 次,开销为 1 + 1 + 1 = 3 。
总开销为 2 + 3 + 3 = 8 。
这是最小开销。
  • 1
  • 2
  • 3
  • 4
  • 5
  • 6
  • 7
  • 8

思路

中位数贪心/枚举

可以先把nums的所有数字从小到大排个序,因为我们操作的最终结果,是使所有数都相等,不妨设最终的这个数为x,那么所有的数最后都要变成x。我们来考虑x的取值。假设nums从小到大排好序后是:[1,2,3,5,9,11,20],绘制一个折线图如下

我们考虑最终的x是否一定能取到nums中的某个值。假设x不是nums中的某个值。假设x = 8,将每个元素大小到x的距离设为di,每个元素操作一次的代价为ci

< x的元素共有4个,大于x的元素有3个。

小于x的元素全部变为x的总代价是:d1 * c1 + d2 * c2 + d3 * c3 + d4 * c4

大于x的元素全部变为x的总代价是:d5 * c5 + d6 * c6 + d7 * c7

我们尝试把x变小,让他与相邻最近的nums[4]相等,设x与下面的nums[4]的距离为d,那么看看将x变小为nums[4]时,对总的代价会有什么变化。

首先对于左侧小于x的元素,因为距离变得近了,其总代价会变少,变少了这么多:d * (c1 + c2 + c3 + c4)

对于右侧大于x的元素,其总代价会变多,变多了这么多:d * (c5 + c6 + c7)

我们设c1 + c2 + c3 + c4 = leftc5 + c6 + c7 = right

那么代价的变化是:d * right - d * left = ▲

rightleft之间肯定有个大小关系,若right > left,则代价的变化 ▲ > 0;若right = left,则▲ = 0;若right < left,则▲ < 0

容易得知这样的结论,若x取到两个数中间时,总代价最少,那么有

  • right > left,我们一定能将x往上移,使得总代价变得更小
  • right < left,我们一定能将x往下移,使得总代价变得更小
  • right = left,则我们将x往上移,往下移,总代价都保持不变

所以,最终使得总代价最小的方案,所取的x,一定能够取到nums中的某个值。

我们只需要求解x取到哪个值即可。

我们先随便将x设为排好序的nums中的某个位置的数,然后我们考虑把x往左挪一个位置,或者往右挪一个位置,观察一下总的开销的变化情况。设x所在的下标为i,即,x = nums[i],则x左侧,即所有下标位于区间[0, i - 1]的数的操作开销为:

leftCost = (nums[0] - x) * cost[0] + (nums[1] - x) * cost[1] + ... + (nums[i - 1] - x) * cost[ i - 1]

简化一下,我们将nums[k]x之间的距离用d[k]表示,则

leftCost = d[0] * cost[0] + d[1] * cost[1] + ... + d[i - 1] * cost[i - 1]

同理,x右侧,即所有下标位于区间[i + 1, n - 1]的数的操作开销为

rightCost = d[i + 1] * cost[i + 1] + ... + d[n - 1] * cost[n - 1]

我们考虑将x往左挪一个位置,即取x = nums[i - 1],来看一下左右两侧的开销变化。

由于我们对nums按照从小到大排了序,则x左侧的元素都是小于x的。当把x往左挪一个位置,则左侧所有点离最终x的距离,变小了,变小的幅度是 nums[i] - nums[i - 1],右侧所有点离最终x的距离,变大了,变大的幅度也是nums[i] - nums[i - 1],我们设

d = nums[i] - nums[i - 1]

则左侧全部元素,减小的开销为:d * (cost[0] + cost[1] + ... + cost[i - 1])

右侧全部元素,增大的开销为:d * (cost[i] + cost[i + 1] + cost[i + 1] + ... + cost[n - 1])

所以,若左侧的 ∑ k = 0 k = i − 1 c o s t k \sum_{k=0}^{k=i-1}cost_k k=0k=i1costk 若小于右侧的 ∑ k = i k = n − 1 c o s t k \sum_{k=i}^{k=n-1}cost_k k=ik=n1costk,说明把x从位置i变到i - 1,减小的开销小于增加的开销,总开销是增大的。所以此时不能将x的位置往左移动,只能往右移动。同理,若左侧的 ∑ k = 0 k = i − 1 c o s t k \sum_{k=0}^{k=i-1}cost_k k=0k=i1costk 大于右侧的 ∑ k = i k = n − 1 c o s t k \sum_{k=i}^{k=n-1}cost_k k=ik=n1costk,那么x的位置应当往左移动。我们可以根据这个性质,找到一个位置,使得其往左或往右移动都不能使得总开销变得更小,那么这个位置就是最终的x的位置。我们可以直接从第0个位置开始累加,当累加的cost刚好超过总数的一半,则停止。或者对cost数组计算一个前缀和,用二分查找来找x的位置。

确定x的位置后,再遍历一次依次累加各个元素的代价即可。

C++:

// C++
typedef long long LL;
class Solution {
public:

    void quick_sort(vector<int>& n, vector<int>& c, int l, int r) {
        if (l >= r) return ;
        int x = n[l + r >>1], i = l - 1, j = r + 1;
        while (i < j) {
            do i++; while (n[i] < x);
            do j--; while (n[j] > x);
            if (i < j) {
                swap(n[i], n[j]);
                swap(c[i], c[j]);
            }
        }
        quick_sort(n, c, l, j);
        quick_sort(n, c, j + 1, r);
    }

    LL minCost(vector<int>& nums, vector<int>& cost) {
        int n = nums.size();
        // 按照nums从小到大排序
        quick_sort(nums, cost, 0, n - 1);
        vector<LL> s(n + 1);
        // 求一个cost的前缀和
        for (int i = 0; i < n; i++) s[i + 1] = s[i] + cost[i];
        // 二分中位数的位置
        int l = 1, r = n;
        while (l < r) {
            int mid = l + r >> 1;
            // 找到第一个左侧 >= 右侧的位置
            if (s[mid] >= s[n] - s[mid]) r = mid;
            else l = mid + 1;
        }
        //l是最终的位置
        int x = nums[l - 1];
        LL ans = 0;
        for (int i = 0; i < n; i++) {
            ans += (LL) abs(nums[i] - x) * cost[i];
        }
        return ans;
    }
};
  • 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
  • 33
  • 34
  • 35
  • 36
  • 37
  • 38
  • 39
  • 40
  • 41
  • 42
  • 43
  • 44

或者通过枚举也可以找到答案,首先,我们上面证明了,使得总开销最小的值x,一定是能取到nums中的某个数。那么我们还是先按照nums从小到大排序,然后先设x = nums[0],计算出一个总开销出来。然后置x = nums[1],计算变化的开销量,再置x = nums[2]计算变化的开销量,一直枚举到最后,每次对计算出来的总开销取一个min即可。

// C++
typedef long long LL;
typedef pair<int, int> PII;
class Solution {
public:
    LL minCost(vector<int>& nums, vector<int>& cost) {
        int n = nums.size();
        // nums和cost合在一起排序, 按照nums从小到大
        vector<PII> v(n);
        for (int i = 0; i < n; i++) v[i] = {nums[i], cost[i]};
        sort(v.begin(), v.end());

        // 计算前缀和, 并计算x = nums[0]时的总开销
        LL cur = 0;
        vector<LL> s(n + 1);
        for (int i = 0; i < n; i++) {
            s[i + 1] = s[i] + v[i].second;
            cur += (LL) abs(v[i].first - v[0].first) * v[i].second;
        }

        // 依次计算 x = nums[i]时的总开销, 并更新ans
        LL ans = cur;
        for (int i = 1; i < n; i++) {
            int d = v[i].first - v[i - 1].first;
            // 左侧开销变大, 右侧变小
            LL l = s[i] * d, r = (s[n] - s[i]) * d;
            cur += l - r;
            ans = min(ans, cur);
        }
        return ans;
    }
};
  • 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

2449. 使数组相似的最少操作次数

给你两个正整数数组 numstarget ,两个数组长度相等。

在一次操作中,你可以选择两个 不同 的下标 ij ,其中 0 <= i, j < nums.length ,并且:

  • nums[i] = nums[i] + 2
  • nums[j] = nums[j] - 2

如果两个数组中每个元素出现的频率相等,我们称两个数组是 相似 的。

请你返回将 nums 变得与 target 相似的最少操作次数。测试数据保证 nums 一定能变得与 target 相似。

提示:

  • n == nums.length == target.length
  • 1 <= n <= 10^5
  • 1 <= nums[i], target[i] <= 10^6
  • nums 一定可以变得与 target 相似。

示例

输入:nums = [8,12,6], target = [2,14,10]
输出:2
解释:可以用两步操作将 nums 变得与 target 相似:
- 选择 i = 0 和 j = 2 ,nums = [10,12,4] 。
- 选择 i = 1 和 j = 2 ,nums = [10,14,2] 。
2 次操作是最少需要的操作次数。
  • 1
  • 2
  • 3
  • 4
  • 5
  • 6

思路

贪心

每次能把一个元素+2,另一个元素-2。由此可知,经过数次操作后,偶数还是偶数,奇数还是奇数。元素的奇偶性不会改变。我们可以先把全部元素按照奇偶性分成两组。(扩展,如果题目变形成+3和-3,同理,所有模3余0的数,经过数次操作后,模3还是余0,模3余1的同理,所以可以根据模3的余数,将元素分为3类:x mod 3 = 0,x mod 3 = 1,x mod 3 = 2,对于+k -k,就是分为k - 1组)。

由于题目保证nums一定能变得与target相似,那么我们来考虑下如何转换能使得操作次数最小。

我们对numstarget中的数先按奇偶性进行分组,nums分为o_oddo_eventarget分为t_oddt_even

o_oddt_odd从小到大排个序。

由于无论如何操作,奇数都只能变成奇数。所以o_odd中每个数,经过操作后,需要变成t_odd中的每个数。排完序后,我们观察能够发现,把o_odd的每个位置挨个变成t_odd每个位置的数,能够使得操作次数最少。

于是很简单的,我们可以依次统计每个位置的数的差,然后除以2,就是这个位置上的数需要操作的次数。我们对奇偶两组数分别统计完成后,得到的总的统计次数,再除以个2,就是最终答案。

至于该贪心策略的正确性,这里略过。

// C++
class Solution {
public:
    long long makeSimilar(vector<int>& nums, vector<int>& target) {
        // 先分组
        vector<int> o_odd, o_even;
        vector<int> t_odd, t_even;
        for (int& i : nums) {
            if (i % 2) o_odd.push_back(i);
            else o_even.push_back(i);
        }
        for (int& i : target) {
            if (i % 2) t_odd.push_back(i);
            else t_even.push_back(i);
        }
        // 排序
        sort(o_odd.begin(), o_odd.end());
        sort(o_even.begin(), o_even.end());
        sort(t_odd.begin(), t_odd.end());
        sort(t_even.begin(), t_even.end());

        long long ans = 0;
        for (int i = 0; i < o_odd.size(); i++) ans += abs(o_odd[i] - t_odd[i]) / 2;
        for (int i = 0; i < o_even.size(); i++) ans += abs(o_even[i] - t_even[i]) / 2;
        return ans / 2;
        
    }
};
  • 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

总结

本周周赛太拉跨,只做出了2题。T3一直坐牢到比赛结束。当时看了下T3和T4都是hard,心理也生出了些许畏惧。

今天重做时,发现T4也并不难。可惜!

T1模拟;T2暴力枚举GCD;T3贪心,T4贪心

声明:本文内容由网友自发贡献,不代表【wpsshop博客】立场,版权归原作者所有,本站不承担相应法律责任。如您发现有侵权的内容,请联系我们。转载请注明出处:https://www.wpsshop.cn/w/小小林熬夜学编程/article/detail/732824
推荐阅读
相关标签
  

闽ICP备14008679号