On the shoulders of giants.

weekly-contest-196

判断能否形成等差数列

给你一个数字数组 arr

如果一个数列中,任意相邻两项的差总等于同一个常数,那么这个数列就称为 等差数列

如果可以重新排列数组形成等差数列,请返回 true ;否则,返回 false

示例 1:

输入:arr = [3,5,1]
输出:true
解释:对数组重新排序得到 [1,3,5] 或者 [5,3,1] ,任意相邻两项的差分别为 2 或 -2 ,可以形成等差数列。

示例 2:

输入:arr = [1,2,4]
输出:false
解释:无法通过重新排序得到等差数列。

提示:

  • 2 <= arr.length <= 1000
  • -10^6 <= arr[i] <= 10^6
题解

从小到大排序后,求出公差然后遍历每个数对。

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

class Solution {
public:
    bool canMakeArithmeticProgression(vector<int>& arr) {
        sort(arr.begin(), arr.end());
        int d = arr[1] - arr[0];
        for(int i = 1; i < arr.size(); i++) {
            if(arr[i] - arr[i - 1] != d) return false;
        }
        return true;
    }
};

所有蚂蚁掉下来前的最后一刻

有一块木板,长度为 n单位 。一些蚂蚁在木板上移动,每只蚂蚁都以 每秒一个单位 的速度移动。其中,一部分蚂蚁向 移动,其他蚂蚁向 移动。

当两只向 不同 方向移动的蚂蚁在某个点相遇时,它们会同时改变移动方向并继续移动。假设更改方向不会花费任何额外时间。

而当蚂蚁在某一时刻 t 到达木板的一端时,它立即从木板上掉下来。

给你一个整数 n 和两个整数数组 left 以及 right 。两个数组分别标识向左或者向右移动的蚂蚁在 t = 0 时的位置。请你返回最后一只蚂蚁从木板上掉下来的时刻。

示例 1:

输入:n = 4, left = [4,3], right = [0,1]
输出:4
解释:如上图所示:
-下标 0 处的蚂蚁命名为 A 并向右移动。
-下标 1 处的蚂蚁命名为 B 并向右移动。
-下标 3 处的蚂蚁命名为 C 并向左移动。
-下标 4 处的蚂蚁命名为 D 并向左移动。
请注意,蚂蚁在木板上的最后时刻是 t = 4 秒,之后蚂蚁立即从木板上掉下来。(也就是说在 t = 4.0000000001 时,木板上没有蚂蚁)。

示例 2:

输入:n = 7, left = [], right = [0,1,2,3,4,5,6,7]
输出:7
解释:所有蚂蚁都向右移动,下标为 0 的蚂蚁需要 7 秒才能从木板上掉落。

示例 3:

输入:n = 7, left = [0,1,2,3,4,5,6,7], right = []
输出:7
解释:所有蚂蚁都向左移动,下标为 7 的蚂蚁需要 7 秒才能从木板上掉落。

示例 4:

输入:n = 9, left = [5], right = [4]
输出:5
解释:t = 1 秒时,两只蚂蚁将回到初始位置,但移动方向与之前相反。

示例 5:

输入:n = 6, left = [6], right = [0]
输出:6

提示:

  • 1 <= n <= 10^4
  • 0 <= left.length <= n + 1
  • 0 <= left[i] <= n
  • 0 <= right.length <= n + 1
  • 0 <= right[i] <= n
  • 1 <= left.length + right.length <= n + 1
  • leftright 中的所有值都是唯一的,并且每个值 只能出现在二者之一 中。
题解

两只蚂蚁相碰转向等效为两只蚂蚁彼此穿过对方,所以直接求最后一只蚂蚁到达相对侧的时间。

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

class Solution {
public:
    int getLastMoment(int n, vector<int>& left, vector<int>& right) {
        int result = 0;
        for(auto dis : left) {
            result = max(result, dis);
        }
        for(auto dis : right) {
            result = max(result, n - dis);
        }
        return result;
    }
};

统计全 1 子矩形

给你一个只包含 0 和 1 的 rows * columns 矩阵 mat ,请你返回有多少个 子矩形 的元素全部都是 1 。

示例 1:

输入:mat = [[1,0,1],
            [1,1,0],
            [1,1,0]]
输出:13
解释:
6 个 1x1 的矩形。
有 2 个 1x2 的矩形。
有 3 个 2x1 的矩形。
有 1 个 2x2 的矩形。
有 1 个 3x1 的矩形。
矩形数目总共 = 6 + 2 + 3 + 1 + 1 = 13 。

示例 2:

输入:mat = [[0,1,1,0],
            [0,1,1,1],
            [1,1,1,0]]
输出:24
解释:8 个 1x1 的子矩形。
有 5 个 1x2 的子矩形。
有 2 个 1x3 的子矩形。
有 4 个 2x1 的子矩形。
有 2 个 2x2 的子矩形。
有 2 个 3x1 的子矩形。
有 1 个 3x2 的子矩形。
矩形数目总共 = 8 + 5 + 2 + 4 + 2 + 2 + 1 = 24

示例 3:

输入:mat = [[1,1,1,1,1,1]]
输出:21

示例 4:

输入:mat = [[1,0,1],[0,1,0],[1,0,1]]
输出:5

提示:

  • 1 <= rows <= 150
  • 1 <= columns <= 150
  • 0 <= mat[i][j] <= 1
题解

略带技巧的模拟,这里不多作介绍。

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

class Solution {
public:
    int numSubmat(vector<vector<int>>& mat) {
        int n = mat.size(), m = mat[0].size(), result = 0;
        for(int s = 0; s < n; s++) {
            for(int i = s; i < n; i++) {
                int total = 0;
                for(int j = 0; j < m; j++) {
                    total = (mat[i][j] ? total + 1 : 0);
                    result += total;
                }
            }
            for(int i = n - 1; s < i; i--) {
                for(int j = 0; j < m; j++) {
                    mat[i][j] = mat[i - 1][j] & mat[i][j];
                }
            }
        }
        return result;
    }
};

最多 K 次交换相邻数位后得到的最小整数

给你一个字符串 num 和一个整数 k 。其中,num 表示一个很大的整数,字符串中的每个字符依次对应整数上的各个 数位

你可以交换这个整数相邻数位的数字 最多 k 次。

请你返回你能得到的最小整数,并以字符串形式返回。

示例 1:

输入:num = "4321", k = 4
输出:"1342"
解释:4321 通过 4 次交换相邻数位得到最小整数的步骤如上图所示。

示例 2:

输入:num = "100", k = 1
输出:"010"
解释:输出可以包含前导 0 ,但输入保证不会有前导 0 。

示例 3:

输入:num = "36789", k = 1000
输出:"36789"
解释:不需要做任何交换。

示例 4:

输入:num = "22", k = 22
输出:"22"

示例 5:

输入:num = "9438957234785635408", k = 23
输出:"0345989723478563548"

提示:

  • 1 <= num.length <= 30000
  • num 只包含 数字 且不含有 前导 0 
  • 1 <= k <= 10^9
题解

从左到右遍历,对于每一个数,在这个数后面 k 位找到最小的数,然后相互交换到这个数。

没要实际移动每个交换的数,用树状数组记录之前有多少交换过就能算出最终的位置。

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

class Solution {
public:
    vector<int> bit;
    int n;
    int lowbit(int x) {
        return x & (-x);
    }
    void add(int x, int d) {
        for(int i = x; i <= n; i += lowbit(i)) bit[i] += d;
    }
    int ask(int x) {
        int sum = 0;
        for(int i = x; 0 < i; i -= lowbit(i)) sum += bit[i];
        return sum;
    }
    string minInteger(string num, int K) {
        this->n = num.length();
        bit = vector<int> (n + 1);
        vector<vector<int>> sta(10, vector<int> ());
        for(int i = 0; i < n; i++) {
            sta[num[i] - '0'].push_back(i + 1);
        }
        vector<int> top(10);
        string result = "";
        for(int i = 1; i <= n; i++) {
            for(int k = 0; k < 10; k++) {
                if(sta[k].size() <= top[k]) continue;
                int abs_x = sta[k][top[k]];
                int pos_x = abs_x - 1 - ask(abs_x);
                if(pos_x <= K) {
                    add(abs_x, 1);
                    top[k]++;
                    result += char('0' + k);
                    K -= pos_x;
                    break;
                }
            }
        }
        return result;
    }
};
Share

You may also like...

发表评论

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