On the shoulders of giants.

biweekly-contest-22

两个数组间的距离值

给你两个整数数组 arr1 , arr2 和一个整数 d ,请你返回两个数组之间的 距离值 。

距离值」定义为符合此描述的元素数目:对于元素 arr1[i] ,不存在任何元素 arr2[j] 满足 |arr1[i]-arr2[j]| <= d

示例 1:

输入:arr1 = [4,5,8], arr2 = [10,9,1,8], d = 2
输出:2
解释:
对于 arr1[0]=4 我们有:
|4-10|=6 > d=2 
|4-9|=5 > d=2 
|4-1|=3 > d=2 
|4-8|=4 > d=2 
对于 arr1[1]=5 我们有:
|5-10|=5 > d=2 
|5-9|=4 > d=2 
|5-1|=4 > d=2 
|5-8|=3 > d=2
对于 arr1[2]=8 我们有:
|8-10|=2 <= d=2
|8-9|=1 <= d=2
|8-1|=7 > d=2
|8-8|=0 <= d=2

示例 2:

输入:arr1 = [1,4,2,3], arr2 = [-4,-3,6,10,20,30], d = 3
输出:2

示例 3:

输入:arr1 = [2,1,100,3], arr2 = [-5,-2,10,-3,7], d = 6
输出:1

提示:

  • 1 <= arr1.length, arr2.length <= 500
  • -10^3 <= arr1[i], arr2[j] <= 10^3
  • 0 <= d <= 100
题解

直接遍历即可。

时间复杂度:\(O(nm)\)

class Solution {
public:
    int findTheDistanceValue(vector<int>& arr1, vector<int>& arr2, int d) {
        int result = 0;
        for(auto num1 : arr1) {
            int tot = 0;
            for(auto num2 : arr2) {
                tot += (abs(num1 - num2) <= d);
            }
            result += (tot == 0);
        }
        return result;
    }
};

安排电影院座位

如上图所示,电影院的观影厅中有 n 行座位,行编号从 1 到 n ,且每一行内总共有 10 个座位,列编号从 1 到 10 。

给你数组 reservedSeats ,包含所有已经被预约了的座位。比如说,researvedSeats[i]=[3,8] ,它表示第 3 行第 8 个座位被预约了。

请你返回 最多能安排多少个 4 人家庭 。4 人家庭要占据 同一行内连续 的 4 个座位。隔着过道的座位(比方说 [3,3] 和 [3,4])不是连续的座位,但是如果你可以将 4 人家庭拆成过道两边各坐 2 人,这样子是允许的。

示例 1:

输入:n = 3, reservedSeats = [[1,2],[1,3],[1,8],[2,6],[3,1],[3,10]]
输出:4
解释:上图所示是最优的安排方案,总共可以安排 4 个家庭。蓝色的叉表示被预约的座位,橙色的连续座位表示一个 4 人家庭。

示例 2:

输入:n = 2, reservedSeats = [[2,1],[1,8],[2,6]]
输出:2

示例 3:

输入:n = 4, reservedSeats = [[4,3],[1,4],[4,6],[1,7]]
输出:4

提示:

  • 1 <= n <= 10^9
  • 1 <= reservedSeats.length <= min(10*n, 10^4)
  • reservedSeats[i].length == 2
  • 1 <= reservedSeats[i][0] <= n
  • 1 <= reservedSeats[i][1] <= 10
  • 所有 reservedSeats[i] 都是互不相同的。
题解

模拟每一行,计算每一行的个数。

时间复杂度:\(O(n)\)

class Solution {
public:
    int maxNumberOfFamilies(int n, vector<vector<int>>& reservedSeats) {
        int result = 0, m = 10, row = 1, t = reservedSeats.size();
        sort(reservedSeats.begin(), reservedSeats.end());
        result += (reservedSeats[0][0] - 1) * (int)(m / 4);
        result += (reservedSeats[0][1] - 1) / 4;
        for(int i = 1; i < t; i++) {
            int u = reservedSeats[i - 1][0], d = reservedSeats[i][0];
            int l = reservedSeats[i - 1][1], r = reservedSeats[i][1];
            if(u != d) {
                result += (m - l) / 4;
                result += (d - u - 1) * (int)(m / 4);
                result += (r - 1) / 4;
            } else {
                result += (r - l + 1) / 4;
            }
            row = d;
            cout << d << " , " << r << " : " << result << endl;
        }
        result += (m - reservedSeats[t - 1][1]) / 4;
        result += (n - row) * (int)(m / 4);
        return result;
    }
};

将整数按权重排序

我们将整数 x 的 权重 定义为按照下述规则将 x 变成 1 所需要的步数:

  • 如果 x 是偶数,那么 x = x / 2
  • 如果 x 是奇数,那么 x = 3 * x + 1

比方说,x=3 的权重为 7 。因为 3 需要 7 步变成 1 (3 –> 10 –> 5 –> 16 –> 8 –> 4 –> 2 –> 1)。

给你三个整数 lo, hi 和 k 。你的任务是将区间 [lo, hi] 之间的整数按照它们的权重 升序排序 ,如果大于等于 2 个整数有 相同 的权重,那么按照数字自身的数值 升序排序 。

请你返回区间 [lo, hi] 之间的整数按权重排序后的第 k 个数。

注意,题目保证对于任意整数 x (lo <= x <= hi) ,它变成 1 所需要的步数是一个 32 位有符号整数。

示例 1:

输入:lo = 12, hi = 15, k = 2
输出:13
解释:12 的权重为 9(12 --> 6 --> 3 --> 10 --> 5 --> 16 --> 8 --> 4 --> 2 --> 1)
13 的权重为 9
14 的权重为 17
15 的权重为 17
区间内的数按权重排序以后的结果为 [12,13,14,15] 。对于 k = 2 ,答案是第二个整数也就是 13 。
注意,12 和 13 有相同的权重,所以我们按照它们本身升序排序。14 和 15 同理。

示例 2:

输入:lo = 1, hi = 1, k = 1
输出:1

示例 3:

输入:lo = 7, hi = 11, k = 4
输出:7
解释:区间内整数 [7, 8, 9, 10, 11] 对应的权重为 [16, 3, 19, 6, 14] 。
按权重排序后得到的结果为 [8, 10, 11, 7, 9] 。
排序后数组中第 4 个数字为 7 。

示例 4:

输入:lo = 10, hi = 20, k = 5
输出:13

示例 5:

输入:lo = 1, hi = 1000, k = 777
输出:570

提示:

  • 1 <= lo <= hi <= 1000
  • 1 <= k <= hi - lo + 1
题解

对每个数进行处理,然后以次数为第一关键字,数字为第二关键字排序。

时间复杂度:\(O(n \log m) \)

class Solution {
public:
    int getKth(int lo, int hi, int k) {
        vector<pair<int, int>> num;
        for(int x = lo; x <= hi; x++) {
            int total = 0, val = x;
            while(val != 1) {
                total++;
                val = (val & 1 ? 3 * val + 1 : val / 2);
            }
            num.push_back(make_pair(total, x));
        }
        sort(num.begin(), num.end());
        return num[k - 1].second;
    }
};

3n 块披萨

给你一个披萨,它由 3n 块不同大小的部分组成,现在你和你的朋友们需要按照如下规则来分披萨:

  • 你挑选 任意 一块披萨。
  • Alice 将会挑选你所选择的披萨逆时针方向的下一块披萨。
  • Bob 将会挑选你所选择的披萨顺时针方向的下一块披萨。
  • 重复上述过程直到没有披萨剩下。

每一块披萨的大小按顺时针方向由循环数组 slices 表示。

请你返回你可以获得的披萨大小总和的最大值。

示例 1:

输入:slices = [1,2,3,4,5,6]
输出:10
解释:选择大小为 4 的披萨,Alice 和 Bob 分别挑选大小为 3 和 5 的披萨。然后你选择大小为 6 的披萨,Alice 和 Bob 分别挑选大小为 2 和 1 的披萨。你获得的披萨总大小为 4 + 6 = 10 。

示例 2:

输入:slices = [8,9,8,6,1,1]
输出:16
解释:两轮都选大小为 8 的披萨。如果你选择大小为 9 的披萨,你的朋友们就会选择大小为 8 的披萨,这种情况下你的总和不是最大的。

示例 3:

输入:slices = [4,1,2,5,8,3,1,9,7]
输出:21

示例 4:

输入:slices = [3,1,2]
输出:3

提示:

  • 1 <= slices.length <= 500
  • slices.length % 3 == 0
  • 1 <= slices[i] <= 1000
题解

该问题可以转换成求选择不连续的数之和最大问题(把问题不断缩小可以证明)。

动态规划,设 \(dp_{x,y}\) 表示前 x 个数选了 y 个数的最大和。

转移方程:\(dp_{x,y}=\max (dp_{x-2,y-1}+slices[x],dp_{x-1,y})\)

分别对应选与不选。环的处理也就是选第一个和最后一个不能兼得,所以分别舍去第一、倒一的数,跑两边算法。

时间复杂度:\(O(n^2)\)

class Solution {
public:
    int solve(vector<int>& slices, int l, int r, int m) {
        int result = 0, n = r - l + 1;
        vector<vector<int>> dp(n + 1, vector<int> (m + 1));
        dp[l][1] = slices[l];
        dp[l + 1][1] = max(slices[l], slices[l + 1]);
        for(int i = l + 2; i <= r; i++) {
            for(int j = 1; j <= m; j++) {
                dp[i][j] = max(dp[i - 2][j - 1] + slices[i], dp[i - 1][j]);
            }
        }
        return dp[r][m];
    }
    int maxSizeSlices(vector<int>& slices) {
        int n = slices.size(), m = n / 3;
        int ans1 = solve(slices, 0, n - 2, m);
        int ans2 = solve(slices, 1, n - 1, m);
        return max(ans1, ans2);
    }
};
Share

You may also like...

发表评论

电子邮件地址不会被公开。 必填项已用*标注