int sum[20020];
//先求前缀和再用hash表遍历
class Solution {
public:
int subarraySum(vector<int>& nums, int k) {
for(int i=0;i<nums.size();i++){
sum[i+1] = sum[i]+nums[i];
}
unordered_map<int,int> um;
int res = 0;
for(int i=0;i<=nums.size();i++){
if(um.count(sum[i]-k))
res += um[sum[i]-k];
um[sum[i]]++;
}
return res;
}
};
//把所有的0改成-1,然后就和上题一样去找和为1的连续数组,就是先求前缀和在用hash表遍历
int sums[50050];
class Solution {
public:
int findMaxLength(vector<int>& nums) {
int n = nums.size();
for(int i=0;i<n;i++)
if(!nums[i])
nums[i] = -1;
for(int i=0;i<n;i++){
sums[i+1] = sums[i] + nums[i];
}
unordered_map<int,int> um;
int res = 0;
for(int i=0;i<=n;i++){
if(um.count(sums[i])){
res = max(res,i-um[sums[i]]);
}
else
um[sums[i]] = i;
}
return res;
}
};
雪花雪花雪花
算出雪花旋转和翻转的最小表示,然后去这两个最小表示中的最小序列,再将其排序,二维数组的排序可以用一维数组索引替代,之后对比前两个如果相同,那么就说明雪花是相同的
#include<iostream>
#include<cstring>
#include<algorithm>
using namespace std;
const int N = 100010;
int s[N][6],idx[N];
bool cmp_min(int a[],int b[]){
for(int i=0;i<6;i++){
if(a[i]<b[i]) return true;
else if(a[i]>b[i]) return false;
}
return false;
}
bool cmp(int a,int b){
return cmp_min(s[a],s[b]);
}
void get_min(int snow[]){
static int b[12];
for(int i=0;i<12;i++) b[i] = snow[i%6];
int i = 0,j = 1,k;
while(i<6&&j<6){
for(k=0;k<6&&b[i+k]==b[j+k];k++);
if(b[i+k]>b[j+k]){
i = i + k+1;
if(i==j) i++;
}
else{
j = j + k + 1;
if(i==j) j++;
}
}
int res = min(i,j);
for(int i = 0;i<6;i++) snow[i] = b[res+ i];
}
int main(){
int n;
cin>> n;
int snow[6],isnow[6];
for(int i=0;i<n;i++){
for(int j=0,k=5;j<6,k>=0;j++,k--){
cin>>snow[j];
isnow[k] = snow[j];
}
get_min(snow);
get_min(isnow);
if(cmp_min(snow,isnow)) memcpy(s[i],snow,sizeof(snow));
else memcpy(s[i],isnow,sizeof(isnow));
idx[i] = i;
}
sort(idx,idx+n,cmp);
int flag = 0;
for(int i=1;i<n;i++){
if(!cmp_min(s[idx[i]],s[idx[i-1]])&&!cmp_min(s[idx[i-1]],s[idx[i]])){
flag = 1;
break;
}
}
if(flag) cout<<"Twin snowflakes found."<<endl;
else cout<<"No two snowflakes are alike."<<endl;
return 0;
}
网友评论