512周赛-①Q1-贪心②Q2-双指针③Q3-组合数学#

第 512 场周赛 - 力扣（LeetCode）

Q1-贪心#

题目#

给你两个非负整数 n 和 s。

返回满足下述条件的最大整数：

最多有 n 位数字。
其各位数字之和等于 s 。

如果不存在这样的整数，则返回 -1。

贪心#

① 字符串

最多填n个9，若s > 9n则无解

如果s = 0，则答案为0

否则，整数的十进制长度可以为n，从高到低填，如果s ≤ 9则这一位填s，其余为填0；如果s > 9，这一位填9，s-=9

1
class Solution {
2
public:
3
    int largestInteger(int n, int s) {
4
        if(s > 9*n){
5
            return -1;
6
        }
7
        if(s == 0){
8
            return 0;
9
        }
10
        string ans(n,'0');
11
        for(int i = 0;i<n;i++){
12
            if(s <= 9){
13
                ans[i] += s;
14
                break;
15
            }
16
            ans[i] = '9';
17
            s -= 9;
18
        }
19
        return stoi(ans);
20
    }
21
};

② 数学

填 s//9个9

如果s%9>0，填s%9

最后填0

1
class Solution {
2
public:
3
    int largestInteger(int n, int s) {
4
        if(s > 9*n){
5
            return -1;
6
        }
7
        if(s == 0){
8
            return 0;
9
        }
10
        int ans = (int) pow(10,s/9) - 1;
11
        if(s % 9){
12
            ans = ans*10 + s%9;
13
            n--;
14
        }
15
        return ans * (int) pow(10,n - s/9);
16
    }
17
};

Q2-双指针#

题目#

给你两个二维整数数组 series1 和 series2。

两个序列中的每个元素都表示为 [timestamp, value]，其中：

timestamp 是表示时间的整数。
value 是表示该时间点对应值的整数。

每个数组都按照 timestamp 的 严格递增 顺序排列。

若某个序列中某个时间戳缺失，且该序列中存在更晚的时间戳，则将该缺失时间戳的值设为下一个更晚时间戳对应的值。否则，该时间点的值视为 0。

聚合序列 通过以下方式构造：对于两个序列中出现过的每个时间戳，将两个序列在该时间戳对应的值相加。

返回聚合后的序列，格式为二维整数数组 [timestamp, summedValue]，并按照 timestamp 严格递增 排序。

如果一个数组中的每个元素都严格大于前一个元素，则称该数组为严格递增 。

示例 1：

输入： series1 = [[1,3],[4,1]], series2 = [[2,2],[5,2]]

输出： [[1,5],[2,3],[4,3],[5,2]]

解释：

时间戳	`series1`	`series2`	`summedValue`
1	3	2	5
2	1	2	3
4	1	2	3
5	0	2	2

因此，聚合后的序列为 [[1, 5], [2, 3], [4, 3], [5, 2]]。

双指针#

由于数组 series1和 series2已经分别按照时间戳升序排序，因此在遍历两个数组的过程中，可以定位到聚合序列中的当前时间戳并计算当前时间戳对应的值。

使用 i和 j分别表示数组 series1和 series2的下标，初始时 i=j=0。当两个数组中至少有一个数组没有遍历结束时，执行如下操作。如果两个数组都没有遍历结束，则取 series1[i] 和 series2[j] 这两组元素，两组元素的时间戳的较小值作为聚合序列中的当前时间戳，两组元素的值之和作为聚合序列中的当前时间戳对应的值。

计算聚合序列中的当前时间戳与对应的值之后，将较小时间戳对应的序列数组中的下标值增加 1，如果两个时间戳相等则两个数组中的下标值都增加 1。

如果只有一个数组没有遍历结束，则根据该数组的当前元素计算聚合序列中的当前时间戳与对应的值。

1
class Solution:
2
    def aggregateTimeSeries(self, series1: list[list[int]], series2: list[list[int]]) -> list[list[int]]:
3
        ans = []
4
        n,m = len(series1),len(series2)
5
        i = j = 0
6
        while i < n and j < m:
7
            t1,t2 = series1[i][0],series2[j][0]
8
            s = series1[i][1] + series2[j][1]
9
            if t1 < t2:
10
                ans.append([t1,s])
11
                i += 1
12
            elif t1 > t2:
13
                ans.append([t2,s])
14
                j += 1
15
            else:
16
                ans.append([t1,s])
17
                i += 1
18
                j += 1
19
        ans += series1[i:]
20
        ans += series2[j:]
21
        return ans

1
class Solution {
2
public:
3
    vector<vector<int>> aggregateTimeSeries(vector<vector<int>>& series1, vector<vector<int>>& series2) {
4
        vector<vector<int>> ans;
5
        int n = series1.size();
6
        int m = series2.size();
7
        int i = 0;
8
        int j = 0;
9
        while(i < n && j < m){
10
            int t1 = series1[i][0],t2 = series2[j][0];
11
            int sum = series1[i][1] + series2[j][1];
12
            if(t1 < t2){
13
                ans.push_back({t1,sum});
14
                i++;
15
            }
16
            else if(t1 > t2){
17
                ans.push_back({t2,sum});
18
                j++;
19
            }
20
            else{
21
                ans.push_back({t1,sum});
22
                i++;
23
                j++;
24
            }
25
        }
26
        ans.insert(ans.end(),series1.begin() + i,series1.end());
27
        ans.insert(ans.end(),series2.begin() + j,series2.end());
28
        return ans;
29
    }
30
};

Q3-组合数学#

题目#

给你两个正整数 n 和 k。

一个有效序列 是一个由 k 个正整数组成的序列，满足以下条件：

序列中所有整数的和等于 n。
序列中所有整数的乘积是偶数。

返回有效序列的数量。由于答案可能很大，请将其对 109 + 7 取余后返回。

如果两个序列在任何下标处不同，则认为它们是不同的序列。例如，[1, 1, 2] 和 [1, 2, 1] 被认为是不同的序列。

组合数学#

乘积为偶数 ⟺ 序列中至少有一个偶数。

因为：奇数 × 奇数 = 奇数，任何数 × 偶数 = 偶数。

乘积为偶数的序列数 = 所有序列数 - 全为奇数的序列数

将 n 个相同的球排成一行，分成 k 份，每份至少 1 个。

在 n 个球之间的 (n-1) 个空隙中，选择 (k-1) 个位置插入隔板。

\text{总数} = C_{n-1}^{k-1}

举例：n=5, k=3

1
球：● ● ● ● ●
2
空隙： ↑ ↑ ↑ ↑
3
选择 2 个空隙插入隔板
4

5
选位置 1 和 3：
6
● | ● ● | ● ● → [1, 2, 2]
7

8
选位置 1 和 2：
9
● | ● | ● ● ● → [1, 1, 3]
10

11
选位置 2 和 4：
12
● ● | ● ● | ● → [2, 2, 1]
13

14
...共 C(4,2) = 6 种

任意奇数可写成： $2a + 1$ （其中 $a \ge 0$ ）。

设序列为 $[2a_1+1, 2a_2+1, \dots, 2a_k+1]$ 。

\sum_{i=1}^{k}(2a_i+1)=n\\2\sum_{i=1}^{k}a_i+k=n\\2\sum_{i=1}^{k}a_i=n-k\\\sum_{i=1}^{k}a_i=\frac{n-k}{2}

$n - k$ 必须是偶数，否则无解。

设 $m = \frac{n - k}{2}$ ，则 $m$ 必须是非负整数。

将 m 个相同的球分给 k 个人，每人可以得 0 个（因为 $a_i \ge 0$ ）。

将 m 个球和 k-1 个隔板一起排列，总位置数 = m + k - 1，选择 k-1 个位置放隔板。

\text{全奇数序列数} = C_{m+k-1}^{k-1}

举例：n=5, k=3

$m = \frac{5-3}{2} = 1$
将 1 个球分给 3 人：C(1+3-1, 2) = C(3, 2) = 3

三种分法（a₁, a₂, a₃）：

a₁	a₂	a₃	原序列
1	0	0	\[3, 1, 1]
0	1	0	\[1, 3, 1]
0	0	1	\[1, 1, 3]

1
class Solution:
2
    def countValidSequences(self, n: int, k: int) -> int:
3
        MOD = 10**9 +7
4
        tot = comb(n-1,k-1)
5
        if (n - k)%2 == 0:
6
            m = (n - k)//2
7
            odd = comb(m + k - 1,k-1)
8
        else:
9
            odd = 0
10
        return (tot - odd)%MOD

音乐

音乐

512周赛-①Q1-贪心②Q2-双指针③Q3-组合数学#

Q1-贪心#

题目#

贪心#

Q2-双指针#

题目#

双指针#

Q3-组合数学#

题目#

组合数学#

文章分享

音乐

目录

音乐

音乐

[算法训练] 512周赛-①Q1-贪心②Q2-双指针③Q3-组合数学

512周赛-①Q1-贪心②Q2-双指针③Q3-组合数学#

Q1-贪心#

题目#

贪心#

Q2-双指针#

题目#

双指针#

Q3-组合数学#

题目#

组合数学#

文章分享

音乐

目录