石神
2023/03/08阅读：19主题：全栈蓝
【leetcode周赛】第一期
第一期
本文只是节选公众号的中的一篇，我的公众号每日都会更新，欢迎参观 公众号算法每日一更
leetcode第332场周赛
6354. 找出数组的串联值
❝力扣链接：https://leetcode.cn/problems/find-the-array-concatenation-value/
题目描述：
给你一个下标从 「0」 开始的整数数组
nums。现定义两个数字的 「串联」 是由这两个数值串联起来形成的新数字。
例如， 15和49的串联是1549。
nums的 「串联值」 最初等于0。执行下述操作直到nums变为空：
如果 nums中存在不止一个数字，分别选中nums中的第一个元素和最后一个元素，将二者串联得到的值加到nums的 「串联值」 上，然后从nums中删除第一个和最后一个元素。如果仅存在一个元素，则将该元素的值加到 nums的串联值上，然后删除这个元素。返回执行完所有操作后
nums的串联值。「示例 1：」
输入：nums = [7,52,2,4]
输出：596
解释：在执行任一步操作前，nums 为 [7,52,2,4] ，串联值为 0 。
- 在第一步操作中：
我们选中第一个元素 7 和最后一个元素 4 。
二者的串联是 74 ，将其加到串联值上，所以串联值等于 74 。
接着我们从 nums 中移除这两个元素，所以 nums 变为 [52,2] 。
- 在第二步操作中：
我们选中第一个元素 52 和最后一个元素 2 。
二者的串联是 522 ，将其加到串联值上，所以串联值等于 596 。
接着我们从 nums 中移除这两个元素，所以 nums 变为空。
由于串联值等于 596 ，所以答案就是 596 。「示例 2：」
输入：nums = [5,14,13,8,12]
输出：673
解释：在执行任一步操作前，nums 为 [5,14,13,8,12] ，串联值为 0 。
- 在第一步操作中：
我们选中第一个元素 5 和最后一个元素 12 。
二者的串联是 512 ，将其加到串联值上，所以串联值等于 512 。
接着我们从 nums 中移除这两个元素，所以 nums 变为 [14,13,8] 。
- 在第二步操作中：
我们选中第一个元素 14 和最后一个元素 8 。
二者的串联是 148 ，将其加到串联值上，所以串联值等于 660 。
接着我们从 nums 中移除这两个元素，所以 nums 变为 [13] 。
- 在第三步操作中：
nums 只有一个元素，所以我们选中 13 并将其加到串联值上，所以串联值等于 673 。
接着我们从 nums 中移除这个元素，所以 nums 变为空。
由于串联值等于 673 ，所以答案就是 673 。「提示：」
❞
1 <= nums.length <= 10001 <= nums[i] <= 104
-
比赛解法：双指针模拟
long long findTheArrayConcVal(int* nums, int numsSize){
long long ret = 0;
if(numsSize % 2 == 1) ret = nums[numsSize / 2];
for(int i = 0; i < numsSize/2; i++){
long long left = nums[i];
int right = nums[numsSize - i - 1];
int tmp = right;
while(tmp > 0){
left *= 10;
tmp /= 10;
}
ret += left + right;
}
return ret;
}
-
大佬解法：同
小想法
❝双指针，快慢指针，二叉法……这些思想/思路都是要映在脑子里的。
❞
6355. 统计公平数对的数目
❝力扣链接：https://leetcode.cn/problems/count-the-number-of-fair-pairs/
题目描述：
给你一个下标从 「0」 开始、长度为
n的整数数组nums，和两个整数lower和upper，返回 「公平数对的数目」 。如果
(i, j)数对满足以下情况，则认为它是一个 「公平数对」 ：
0 <= i < j < n，且lower <= nums[i] + nums[j] <= upper「示例 1：」
输入：nums = [0,1,7,4,4,5], lower = 3, upper = 6
输出：6
解释：共计 6 个公平数对：(0,3)、(0,4)、(0,5)、(1,3)、(1,4) 和 (1,5) 。「示例 2：」
输入：nums = [1,7,9,2,5], lower = 11, upper = 11
输出：1
解释：只有单个公平数对：(2,3) 。「提示：」
❞
1 <= nums.length <= 105nums.length == n-109 <= nums[i] <= 109-109 <= lower <= upper <= 109
-
比赛解法：快排+双指针
int cmp(const void *a, const void *b)
{
return *(int*)a - *(int*)b; //由小到大排序
}
long long countFairPairs(int* nums, int numsSize, int lower, int upper){
long long ret = 0;
qsort(nums, numsSize, sizeof(int), cmp);
int right = numsSize - 1;
for(int left = 0; left < right; left++){
while(nums[left] + nums[right] > upper && left < right)
right--;
while(nums[left] + nums[right] >= lower && left < right){
right--;
ret++;
}
right = numsSize - 1;
}
return ret;
}
-
大佬解法
# 快排+二分
class Solution:
def countFairPairs(self, nums: List[int], lower: int, upper: int) -> int:
from sortedcontainers import SortedList
li = SortedList()
ans = 0
for i in nums:
ans += li.bisect_right(upper - i) - li.bisect_left(lower - i)
li.add(i)
return ans
// 快排+模拟
int cmp(const void* a, const void* b){
return *(int*)a - *(int*)b;
}
// O(n)
long long count(int* nums, int numsSize, int upper){
if(numsSize <= 1)
return 0;
int left = 0, right = numsSize - 1;
long long res = 0;
while(left < right){
while(nums[left] + nums[right] > upper && left < right)
right--;
if(left >= right)
return res;
else{
res += right - left;
left++;
}
}
return res;
}
long long countFairPairs(int* nums, int numsSize, int lower, int upper){
qsort(nums, numsSize, sizeof(int), cmp);
if(numsSize <= 1)
return 0;
// 求出小于等于upper的个数
long long res1 = count(nums, numsSize, upper);
// 求出小于等于lower - 1的个数
long long res2 = count(nums, numsSize, lower - 1);
return res1 - res2;
}
小想法
❝当时打算快排+二分，但是二分没啥把握，不如快排+双指针。自以为时间复杂度已经降到
O(nlogn)了，但是对于一组完全相同的数据，显然还是O(n^2)，只能说学艺不精！快排+模拟也非常巧妙！主要是算两回，而我老想着一次搞定，太妙了！！！
❞
6356. 自字符串异或查询
❝力扣链接：https://leetcode.cn/problems/substring-xor-queries/
给你一个 「二进制字符串」
s和一个整数数组queries，其中queries[i] = [firsti, secondi]。对于第
i个查询，找到s的 「最短子字符串」 ，它对应的 「十进制」值val与firsti「按位异或」 得到secondi，换言之，val ^ firsti == secondi。第
i个查询的答案是子字符串[lefti, righti]的两个端点（下标从 「0」 开始），如果不存在这样的子字符串，则答案为[-1, -1]。如果有多个答案，请你选择lefti最小的一个。请你返回一个数组
ans，其中ans[i] = [lefti, righti]是第i个查询的答案。「子字符串」 是一个字符串中一段连续非空的字符序列。
「示例 1：」
输入：s = "101101", queries = [[0,5],[1,2]]
输出：[[0,2],[2,3]]
解释：第一个查询，端点为 [0,2] 的子字符串为 "101" ，对应十进制数字 5 ，且 5 ^ 0 = 5 ，所以第一个查询的答案为 [0,2]。第二个查询中，端点为 [2,3] 的子字符串为 "11" ，对应十进制数字 3 ，且 3 ^ 1 = 2 。所以第二个查询的答案为 [2,3] 。「示例 2：」
输入：s = "0101", queries = [[12,8]]
输出：[[-1,-1]]
解释：这个例子中，没有符合查询的答案，所以返回 [-1,-1] 。「示例 3：」
输入：s = "1", queries = [[4,5]]
输出：[[0,0]]
解释：这个例子中，端点为 [0,0] 的子字符串对应的十进制值为 1 ，且 1 ^ 4 = 5 。所以答案为 [0,0] 。「提示：」
❞
1 <= s.length <= 104s[i]要么是'0'，要么是'1'。1 <= queries.length <= 1050 <= firsti, secondi <= 109
-
大佬解法：字典树
❝
根据异或性质可知val ^ firsti == secondi ---> val = firsti ^ secondi;
❞
/**
* Return an array of arrays of size *returnSize.
* The sizes of the arrays are returned as *returnColumnSizes array.
* Note: Both returned array and *columnSizes array must be malloced, assume caller calls free().
*/
#define N 500010
struct pos {
int start;
int end;
};
int trie[N][2], id;
struct pos pos[N];
// 字典树的插入
void insert(char *s, int postion, int len)
{
int p = 0;
for (int i = postion; i < postion + len; i++) {
int u = s[i] - '0';
if (!trie[p][u]) {
trie[p][u] = ++id;
pos[id].start = postion;
pos[id].end = i;
}
p = trie[p][u];
}
}
// 字典树的查询
int query(char *s)
{
int p = 0;
for (int i = 0; s[i]; i++) {
int u = s[i] - '0';
if (!trie[p][u])
return 0;
p = trie[p][u];
}
return p;
}
int** substringXorQueries(char * s, int** queries, int queriesSize, int* queriesColSize, int* returnSize, int** returnColumnSizes){
int len = strlen(s);
int i, j, k, res;
char t[32];
memset(trie, 0, sizeof(trie));
int ** ans = malloc(queriesSize * sizeof(int *));
*returnColumnSizes = malloc(queriesSize * sizeof(int));
*returnSize = 0, pos[0].start = -1, pos[0].end = -1, id = 0;
// 建立字典树s
for (i = 0; i < lens; i++)
// 库函数fmin，返回最小值
insert(s, i, fmin(len - i, 30));
for (i = 0; i < queriesSize; i++) {
/* 若val ^ firsti == secondi
则firsti ^ secondi == val
*/
int v = queries[i][0] ^ queries[i][1];
k = 0;
do {
t[k++] = v % 2 + '0';
v >>= 1;
} while (v);
t[k] = '\0';
// 交换t[j]和t[k]
for (j = 0, k = k - 1; j < k; j++, k--) {
t[j] ^= t[k];
t[k] ^= t[j];
t[j] ^= t[k];
}
(*returnColumnSizes)[*returnSize] = 2;
res = query(t);
ans[*returnSize] = malloc(2 * sizeof(int));
ans[*returnSize][0] = pos[res].start;
ans[(*returnSize)++][1] = pos[res].end;
}
return ans;
}
❝这题我没时间做😢，现在再看，有时间也做不出来，
学这个题真是狂掉san值下次再碰到这类就pass
❞
字典树
❝Trie树，即字典树，是一种树形结构，是一种哈希树的变种。利用字符串的公共前缀来减少查询时间，最大限度地减少无谓的字符串比较。
❞
应用
-
1、维护字符串集合（即「字典」）。 -
2、向字符串集合中插入字符串（即「建树」）。 -
3、查询字符串集合中是否有某个字符串（即「查询」）。 -
4、统计字符串在集合中出现的个数（即「统计」）。 -
5、将字符串集合按字典序排序（即「字典序排序」）。 -
6、求集合内两个字符串的LCP（Longest Common Prefix，最长公共前缀）（即「求最长公共前缀」）。
又是一个空间换时间。
基本性质
-
根节点不包含字符，除根节点外每一个节点都只包含一个字符。 -
从根节点到某一节点，路径上经过的字符连接起来，为该节点对应的字符串。 -
每个节点的所有子节点包含的字符都不相同。
查询时间复杂度是O(n)，n是字符串的长度。
插入
struct node
{
int nxt[27];
}trie[maxn];
int insert(char s[],int id)
{
int now=0;
int len=strlen(s);
for(int i=0;i<len;i++)
{
int ch=s[i]-'a'+1;
if(!trie[now].nxt[ch])
{
trie[now].nxt[ch]=tot;
tot++;
}
now=trie[now].nxt[ch];
}
end[now]=id;
}
删除
bool search(char s[])
{
int len=strlen(s);
int now=0;
for(int i=0;i<len;i++)
{
int ch=s[i]-'a'+1;
if(!trie[now].nxt[ch])
return 0;
}
return end[now];
}
6357. 最小得分子序列
这是个hard，作为一题选手，我放了，等到成为两题选手再学
贴个官方链接，感兴趣的可以学下：https://leetcode.cn/circle/discuss/ayE0iI/
acwing第90场周赛
4806. 首字母大写
❝acwing链接：https://www.acwing.com/problem/content/4809/
题目描述：
给定一个由大小写字母构成的单词。
如果单词的首字母为小写字母，则请你将该首字母转换为对应大写字母。
如果单词的首字母为大写字母，则不做任何变化。
输出最终的单词。
输入格式
一个由大小写字母构成的非空字符串，表示给定单词。
输出格式
输出最终的单词。
数据范围
前 33 个测试点满足，输入单词长度范围 [1,10][1,10]。 所有测试点满足，输入单词长度范围 [1,1000][1,1000]。
输入样例1：
ApPLe输出样例1：
ApPLe输入样例2：
konjac输出样例2：
❞Konjac
-
比赛解法：直接模拟
#include<stdio.h>
void cap(char* str){
if(str[0] >= 'a' && str[0] <= 'z')
str[0] -= 'a' - 'A';
}
int main(){
char str[1000];
scanf("%s", str);
cap(str);
printf("%s", str);
return 0;
}
-
大佬解法：同上
#include <stdio.h>
#include <cstring.h>
#include <algorithm>
using namesapce std;
int main(){
string str;
cin >> str;
// 小写转大写函数
str[0] = toupper(str[0]);
cout << str << endl;
return 0;
}
4807. 找数字
❝acwing链接：https://www.acwing.com/problem/content/4810/
题目描述：
给定一个正整数 m 和一个非负整数 s。
请你找到长度为 m 且各位数字之和为 s 的最小和最大「非负」整数。
要求所求非负整数不得包含前导零。
输入格式
共一行，两个整数 m,s。
输出格式
在一行内输出满足条件的最小和最大「非负」整数。
如果无解，则输出
-1 -1。数据范围
前 66 个测试点满足 1≤m≤3。 所有测试点满足 1≤m≤100，0≤s≤900。
输入样例1：
2 15输出样例1：
69 96输入样例2：
3 0输出样例2：
❞-1 -1
-
比赛解法：快排+遍历
❝
快排+二分遍历可能不会超时，不过当时二分没把握
❞
#include<stdio.h>
void maxAndMin(int* max, int* min, int len, int target){
*max = -1, *min = -1;
int tmp = len;
int length = 1;
while(tmp--)
length *= 10;
int sum = 0;
// 找最小值
for(int i = 1; i < length; i++){
int tmp = i;
while(tmp > 0){
sum += tmp % 10;
tmp /= 10;
}
if(sum == target){
*min = i;
break;
}
sum = 0;
}
// 找最大值
for(int i = length - 1; i >= 1; i--){
int tmp = i;
while(tmp > 0){
sum += tmp % 10;
tmp /= 10;
}
if(sum == target){
*max = i;
break;
}
sum = 0;
}
}
int main(){
int max = -1;
int min = -1;
int len, target;
scanf("%d%d", &len, &target);
maxAndMin(&max, &min, len, target);
printf("%d %d", min, max);
return 0;
}
-
大佬解法：字符串实现对位存储+按位赋值
#include <iostream>
#include <cstring>
#include <algorithm>
using namespace std;
int main(){
int m, s;
cin >> m >> s;
// 无解的情况
if (s > m * 9 || !s && m > 1)
puts("-1 -1");
else{
// a，b赋初值为空格
string a(m, ' '), b(m, ' ');
int sum = s;
/*最小值：从低位向高位填数，每次填数越大越好
min(9, s - 1)*/
for (int i = m - 1; i ; i--){
int t = min(9, sum - 1);
a[i] = t + '0';
sum -= t;
}
// 把留下的1填入最高位
a[0] = sum + '0';
sum = s;
/*最大值：从高位向低位填数，每次填数越大越好
min(9, s)*/
for (int i = 0; i < m; i++){
int t = min(9, sum);
b[i] = t + '0';
sum -= t;
}
cout << a << ' ' << b << endl;
}
return 0;
}
小想法
❝比赛的时候第二题没做出来，后来补的暴力解，最后还是超时了。
本题重点：
❞
碰到对整数的位进行操作的题，借助字符串/字符数组 在理解题目之后用数学思维解题，最后再写代码
4808. 构造字符串
❝原题链接：https://www.acwing.com/problem/content/4811/
题解链接：https://www.acwing.com/activity/content/problem/content/8012/
作为一题选手，表示放过~
❞
由于时间有点久远，因而对题目剖析不深，之后会越做越好的👌
作者介绍