- 15.Python 常见的序列_python中属于序列的有
- 2Binutils工具集 解析
- 3一键部署 Llama3 8B/70B！最高仅占1.07GB存储；COCONut上线，字节跳动推出的首个大规模全景图像分割数据集_ollama3
- 4选择不再困难：Rust Web框架Actix、Rocket与Warp深度对比_rust actix
- 5drf 获取域名+端口_如何注册域名（+简单提示可免费获取）
- 6Postman的新手教学，一学就会！_postman使用教程
- 7工作流使用_flowable关联业务表单
- 8性能测试常见的测试指标_性能中的rt
- 9大数据最全Python编程 圣诞树教程 （附代码）程序员的浪漫_python圣诞树(2)，手把手教你写_圣诞树程序代码
- 10Python数据库操作【一】—— Sqlite_python sqlite
2022-03-14每日刷题打卡
赞
踩
2022-03-14每日刷题打卡
代码源——每日一题
网格判断 - 题目 - Daimayuan Online Judge
您将获得一个 n×n 的网格，网格中每个正方形的颜色为黑色或白色。如果满足以下所有条件，则网格是正确的：
- 每行的黑色方块数与白色方块数相同。
- 每列的黑色正方形数与白色方块数相同。
- 没有行或列具有 3 个以上相同颜色的连续正方形。
给定网格，确定它是否正确。
输入格式
第一行一个数字 n（2≤n≤24)， 并且数字 n 是偶数。
接下来 n 行，每行包含一个长度为n的由字符B和W组成的字符串，代表网格正方形的颜色。
输出格式
如果网格正确，请打印数字 1 在一行上。否则，请打印数字 0 在一行上。
样例输入
4
WBBW
WBWB
BWWB
BWBW
- 1
- 2
- 3
- 4
- 5
样例输出
1
- 1
这题可以直接计数做，我这里使用前缀和节省点细节操作。先选一个要记录的颜色，我这里选择的是‘W’，然后遍历数组计算前缀和，遇到当前格子为‘W’时前缀和++。当遍历到的位置大于3时，我们就可以回头看之前的位置了，如果当前位置的前缀和减去往前数第三个位置的前缀和的差值等于3时，说明这中间连着的都是’W’，不满足情况直接输出0。如果差值为0，说明这段路上都没有‘W’，都是’B‘，这也是不符合条件的，输出0。我们先一行行的遍历，如果没有异样，那我们就再一列列来。如果也没有问题那就输出1。
#include<iostream> using namespace std; #include<vector> #include<algorithm> #include<math.h> #include<set> #include<numeric> #include<string> #include<string.h> #include<map> #include<unordered_map> #include<stack> #include<list> #include<queue> #pragma GCC optimize(1) #pragma GCC optimize(2) #pragma GCC optimize(3,"Ofast","inline") typedef long long ll; typedef pair<int, int>PII; int main() { ios_base::sync_with_stdio(false); cin.tie(nullptr); cout.tie(nullptr); int n; cin >> n; vector<int>s(n + 1); vector<vector<char>>v(n + 1, vector<char>(n + 1)); string str; for (int i = 1; i <= n; i++) { cin >> str; for (int j = 1; j <= n; j++) { v[i][j] = str[j - 1]; s[j] = s[j - 1]; if (str[j - 1] == 'W')s[j] += 1; if (j >= 4&&(s[j]==s[j-3]||s[j]-s[j-3]==3)) { cout << 0 << endl; return 0; } } if (s[n] != n / 2) { cout << 0 << endl; return 0; } } for (int i = 1; i <= n; i++) { for (int j = 1; j <= n; j++) { s[j] = s[j - 1]; if (v[j][i] == 'W')s[j] += 1; if (j >= 4 && (s[j] == s[j - 3] || s[j] - s[j - 3] == 3)) { cout << 0 << endl; return 0; } } if (s[n] != n / 2) { cout << 0 << endl; return 0; } } cout << 1 << endl; return 0; }
- 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
- 49
- 50
- 51
- 52
- 53
- 54
- 55
- 56
- 57
- 58
- 59
- 60
- 61
- 62
- 63
- 64
- 65
- 66
- 67
- 68
- 69
- 70
- 71
- 72
- 73
- 74
力扣——每日一题
599. 两个列表的最小索引总和
假设 Andy 和 Doris 想在晚餐时选择一家餐厅，并且他们都有一个表示最喜爱餐厅的列表，每个餐厅的名字用字符串表示。
你需要帮助他们用最少的索引和找出他们共同喜爱的餐厅。 如果答案不止一个，则输出所有答案并且不考虑顺序。 你可以假设答案总是存在。
示例 1:
输入: list1 = [“Shogun”, “Tapioca Express”, “Burger King”, “KFC”]，list2 = [“Piatti”, “The Grill at Torrey Pines”, “Hungry Hunter Steakhouse”, “Shogun”]
输出: [“Shogun”]
解释: 他们唯一共同喜爱的餐厅是“Shogun”。
一个哈希表先遍历list1，记录list1的每个元素和对应的下标。再遍历list2，如果list2的元素在哈希表中出现过，就计算它们的下标和，然后用另一个哈希表来记录下标和和字符串，同时记录下当前出现过的最小下标和。当计算出的下标和大于记录的最小下标和时，直接放弃这家餐馆，去找下一个餐馆。最后根据第二个哈希表和我们记录的最小下标返回存储的所有字符串。
class Solution { public: vector<string> findRestaurant(vector<string>& list1, vector<string>& list2) { map<int, vector<string>>mymap; map<string, int>pos; int n = list1.size(), m = list2.size(), res = 1e9; for (int i = 0; i < n; i++) { pos[list1[i]] = i + 1; } for (int i = 0; i < m; i++) { int num = pos[list2[i]]; if(num != 0&&num+i>res)continue; if (num != 0) { mymap[i +num].push_back(list2[i]); res = min(res, i + num); } } return mymap[res]; } };
- 1
- 2
- 3
- 4
- 5
- 6
- 7
- 8
- 9
- 10
- 11
- 12
- 13
- 14
- 15
- 16
- 17
- 18
- 19
- 20
- 21
- 22
- 23
- 24
41. 缺失的第一个正数
给你一个未排序的整数数组 nums ，请你找出其中没有出现的最小的正整数。
请你实现时间复杂度为 O(n) 并且只使用常数级别额外空间的解决方案。
示例 1：
输入：nums = [1,2,0]
输出：3
这题学到个神奇的东西——原地哈希。想要找没有出现的最小正整数且时间复杂度控制在O(n)，那就用哈希表先遍历一遍数组，把出现过的正整数都记录下来，然后再遍历一遍哈希表来找到最小出现过的正整数。这样的解法时间复杂度和空间复杂度都是O(n)，时间符合了但空间并不符和，空间复杂度O(1)使得我们不可能做出哈希表，但我们可以用题目给的数组当成哈希表。思路如下，我们遍历数组，每遍历到一个正整数num，就把下标为num-1的位置打上标记，最后只要遍历一遍数组，看哪个位置没有标记，第一个没有标记的位置下标+1就是缺失的第一个正数。
class Solution { public: int firstMissingPositive(vector<int>& nums) { int n=nums.size(); for(auto&i:nums) { if(i<=0)i=n+1; } for(int i=0;i<n;i++) { int num=abs(nums[i]); if(num<=n) nums[num-1]=-1*abs(nums[num - 1]); } for(int i=0;i<n;i++) { if(nums[i]>0) return i+1; } return n+1; } };
- 1
- 2
- 3
- 4
- 5
- 6
- 7
- 8
- 9
- 10
- 11
- 12
- 13
- 14
- 15
- 16
- 17
- 18
- 19
- 20
- 21
- 22
CodeForces
Problem - 1648B - Codeforces
You are given an array a of n positive integers numbered from 11 to n. Let’s call an array integral if for any two, not necessarily different, numbers xx and y from this array, x≥y, the number ⌊xy⌋(x divided by y with rounding down) is also in this array.
You are guaranteed that all numbers in a do not exceed cc. Your task is to check whether this array is integral.
Input
The input consists of multiple test cases. The first line contains a single integer tt (1≤t≤1041≤t≤104) — the number of test cases. Description of the test cases follows.
The first line of each test case contains two integers n and cc (1≤n≤1061≤n≤106, 1≤c≤1061≤c≤106) — the size of a and the limit for the numbers in the array.
The second line of each test case contains nn integers a1, a2, …, an (1≤ai≤c) — the array a.
Let N be the sum of n over all test cases and C be the sum of c over all test cases. It is guaranteed that N≤10^6 and C≤10^6
Output
For each test case print Yes if the array is integral and No otherwise.
Examples
input
4
3 5
1 2 5
4 10
1 3 3 7
1 2
2
1 1
1
- 1
- 2
- 3
- 4
- 5
- 6
- 7
- 8
- 9
output
Yes
No
No
Yes
- 1
- 2
- 3
- 4
input
1
1 1000000
1000000
- 1
- 2
- 3
output
No
- 1
Note
In the first test case it is easy to see that the array is integral:
- ⌊11⌋=1, a1=1, this number occurs in the arry
- ⌊22⌋=1
- ⌊55⌋=1
- ⌊21⌋=2, a2=2, this number occurs in the array
- ⌊51⌋=5, a3=5, this number occurs in the array
- ⌊52⌋=2, a2=2, this number occurs in the array
Thus, the condition is met and the array is integral.
In the second test case it is enough to see that
⌊73⌋=⌊213⌋=2, this number is not in a, that’s why it is not integral.
In the third test case ⌊22⌋=1, but there is only 2 in the array, that’s why it is not integral.
题目是说，给你一个数组和一个数c，这个数组里的数最大不会大过c，然后对于这个数组，如果任意两个数x和y（x>=y，且这两个数可以是同一个数），数组里都有x/y（取下限），那这个数组就很nb，现在让你判断这个数组牛不牛逼。
暴力解法就是哈希表记录所有数的出现情况，然后两重for枚举所有可能的x与y，再判断哈希表里是否有结果，一旦出现没有就输出NO。
但这解法的时间复杂度为n^2，在这题数据面前妥妥TLE，此时我们就要想办法去优化它了。
首先我们知道，在这里因为我们取得除数结果取下限，所以对于一个数x来说在范围[x* k,x*k+k-1]内，它的除数结果都是k，那么我们可以反过来枚举除数结果k：1~y，同时用哈希表记录数组（题目给的数组，并不是那个x *k的范围）出现的所有数，只要范围内有数，且除数结果也出现在数组里那就符合情况了，反之，如果范围内有数，但除数结果不在数组里，那就不符合。如果范围内没有数，那我们直接去找下一个范围即可。当k *x大于c时结束枚举（因为最大不能大过c）。
那么我们怎么知道这个范围内有没有数呢？这里我们可以用前缀和的方式，和一般的前缀和数组不太一样，这里我们前缀和记录的是数在区间里的记录情况，举个例子，比如数组是1 3 5 ，那么我们先开一个长度为c+1的前缀和数组，然后给前缀和数组的对应下标的数+1（初始都是0），这样就是s[1]=1,s[3]=1,s[5]=1，然后用普通求前缀和的方式：s[i]+=s[i-1]即可，这样结果就是s[0]~s[5]:0 1 1 2 2 3。这个前缀和数组就说明了，小于等于3的范围里的数有s[3]个，小于等于5的范围里的数有s[5]个，大于2小于等于5的数有s[5]-s[2]=2个，这样我们就可以很直观的知道哪个区间里有没有数了，再根据我们之前的方法，就可以很快的得出结果了，时间复杂度为nlogn。
#include<iostream> using namespace std; #include<vector> #include<algorithm> #include<math.h> #include<set> #include<numeric> #include<string> #include<string.h> #include<map> #include<unordered_map> #include<stack> #include<list> #include<queue> #pragma GCC optimize(1) #pragma GCC optimize(2) #pragma GCC optimize(3,"Ofast","inline") typedef long long ll; typedef pair<int, int>PII; int main() { ios_base::sync_with_stdio(false); cin.tie(nullptr); cout.tie(nullptr); int t = 0; cin >> t; while (t--) { int n, c; cin >> n >> c; vector<int>s(c + 1); map<int, int>mymap; for (int i = 1; i <= n; i++) { int num; cin >> num; mymap[num]++; } for (int i = 1; i <= c; i++) { s[i] = s[i - 1] + mymap[i]; } bool flag = true; for (int i = 1; i <= c; i++) { if (mymap[i] == 0)continue; for (int j = 1; j * i <= c; j++) { int r = min(c, i * j + i - 1); if (s[r] - s[j * i - 1] > 0) { if (mymap[j] == 0) { cout << "NO" << endl; flag = false; break; } } } if (!flag)break; } if (flag)cout << "YES" << endl; } }
- 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
- 49
- 50
- 51
- 52
- 53
- 54
- 55
- 56
- 57
- 58
- 59
- 60
- 61
- 62
- 63
- 64
- 65
- 66
- 67
