力扣第 395 场周赛

OJ加加

A

给你两个长度相等的数组 nums1 和 nums2。

数组 nums1 中的每个元素都与变量 x 所表示的整数相加。如果 x 为负数，则表现为元素值的减少。

在与 x 相加后，nums1 和 nums2 相等 。当两个数组中包含相同的整数，并且这些整数出现的频次相同时，两个数组 相等 。

返回整数 x 。

示例 1:

输入：nums1 = [2,6,4], nums2 = [9,7,5]

输出：3

解释：

与 3 相加后，nums1 和 nums2 相等。

示例 2:

输入：nums1 = [10], nums2 = [5]

输出：-5

解释：

与 -5 相加后，nums1 和 nums2 相等。

示例 3:

输入：nums1 = [1,1,1,1], nums2 = [1,1,1,1]

输出：0

解释：

与 0 相加后，nums1 和 nums2 相等。

提示：

  • 1 <= nums1.length == nums2.length <= 100
  • 0 <= nums1[i], nums2[i] <= 1000
  • 测试用例以这样的方式生成：存在一个整数 x，使得 nums1 中的每个元素都与 x 相加后，nums1 与 nums2 相等。

排序减去就行

1
2
3
4
5
6
7
8
class Solution {
public:
    int addedInteger(vector<int>& nums1, vector<int>& nums2) {
        sort(nums1.begin(),nums1.end());
        sort(nums2.begin(),nums2.end());
        return nums2[0]-nums1[0];
    }
};

B

给你两个整数数组 nums1 和 nums2。

从 nums1 中移除两个元素，并且所有其他元素都与变量 x 所表示的整数相加。如果 x 为负数，则表现为元素值的减少。

执行上述操作后，nums1 和 nums2 相等 。当两个数组中包含相同的整数，并且这些整数出现的频次相同时，两个数组 相等 。

返回能够实现数组相等的 最小 整数 x 。

示例 1:

输入：nums1 = [4,20,16,12,8], nums2 = [14,18,10]

输出：-2

解释：

移除 nums1 中下标为 [0,4] 的两个元素，并且每个元素与 -2 相加后，nums1 变为 [18,14,10] ，与 nums2 相等。

示例 2:

输入：nums1 = [3,5,5,3], nums2 = [7,7]

输出：2

解释：

移除 nums1 中下标为 [0,3] 的两个元素，并且每个元素与 2 相加后，nums1 变为 [7,7] ，与 nums2 相等。

提示：

  • 3 <= nums1.length <= 200
  • nums2.length == nums1.length - 2
  • 0 <= nums1[i], nums2[i] <= 1000
  • 测试用例以这样的方式生成：存在一个整数 x，nums1 中的每个元素都与 x 相加后，再移除两个元素，nums1 可以与 nums2 相等。

时空都是第一？

  • image-20240428141735489
  • 选择用map去判断，枚举-1000到1000，其实很简单
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
45
46
47
48
class Solution {
public:
    int minimumAddedInteger(vector<int>& nums1, vector<int>& nums2) 
    {
        map<int,int>m;
        for(auto x:nums2)
        {
            m[x]++;
        }
        for(int i=-1000;i<=1000;i++)
        {
            bool flag=0;
            map<int,int>mp;
            for(auto x:nums1)
            {
                x+=i;
                mp[x]++;
            }
            //计算一下两个map数组之间
            int cnt=0;
            for(auto &[x,y]:m)
            {
                if(!mp[x])
                {
                    flag=1;
                    break;
                }
                if(mp[x]-m[x]<0||mp[x]-m[x]>2)
                {
                    flag=1;
                    break;
                }
                cnt+=mp[x]-m[x];
            }
            if(cnt<=2&&!flag)
            {
            return i;    
            }
            for(auto x:nums1)
            {
                x-=i;
            }
        }
        return 2;
        
        
    }
};

C

给你两个整数 n 和 x 。你需要构造一个长度为 n 的 正整数 数组 nums ，对于所有 0 <= i < n - 1 ，满足 nums[i + 1] 大于 nums[i] ，并且数组 nums 中所有元素的按位 AND 运算结果为 x 。

返回 nums[n - 1] 可能的 最小 值。

示例 1：

输入：n = 3, x = 4

输出：6

解释：

数组 nums 可以是 [4,5,6] ，最后一个元素为 6 。

示例 2：

输入：n = 2, x = 7

输出：15

解释：

数组 nums 可以是 [7,15] ，最后一个元素为 15 。

提示：

  • \(1 <= n, x <= 10^8\)

有点思维，但其实不多

如果n是4，算去X自己要减去1之外

就剩3，然后意味着有2个1要填，自然是从低到高填就行啦~

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
using ll=long long;
class Solution 
{
public:
long long minEnd(int n, int x) {
    	int i,j;
        ll res=x;
        n--;
        for(i=0,j=0;i<=30;i++,j++)
        {
        	while((res>>j)&1) j++;
        	if(!((n>>i)&1)) continue;
        	res|=(1LL<<j);
		}
        return res;
    }
};
//应该是直接往没有1的数字里面填就可以了
//但是有多少个数字要填就又是一个问题了

D

本场最难？

直接进行二分那个答案，因为答案只有那一个吗

check函数其实很好写就是滑动窗口思想，就去滑就行了

不多赘述

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
#include "bits/stdc++.h"
#define rep(i, a, n) for (auto i = a; i <= (n); ++i)
#define all(a) a.begin(), a.end()
#define sz(a) (int)(a).size()
using namespace std;

using ll = long long;
class Solution {
public:
	int medianOfUniquenessArray(vector<int>& as) {
		int n = sz(as);
		vector<int> cnt;
		auto check = [&](int x) -> bool {
			int MAXN = *max_element(all(as));
			cnt.assign(MAXN + 1, 0);
			int diff = 0;
			int r = 0;
			ll res = 0;
			rep(i, 0, n - 1) 
            {
				while (r < n && diff <= x) {
					int v = as[r++];
					if (cnt[v]++ == 0) diff++;
				}
				if (diff > x) res += r - i - 1;
				else res += r - i;
				int v = as[i];
				if(--cnt[v] == 0) diff--;
			}
			ll tot = 1ll * (n + 1) * n / 2;
			return res >= (tot + 1) / 2;
		};
		int l = 0, r = n;
		while (l < r) 
        {
			int mid = (l + r) >> 1;
			if (check(mid)) r = mid;
			else l = mid + 1;
		}
		return r;
	}
};