01/04 07:59

1. 大餐计数之哈希O(1)

# 一、5642. 大餐计数之哈希O(1)

1 <= deliciousness.length <= 105
0 <= deliciousness[i] <= 220

# 二、 程序

## 1，会超时的哦

struct arrays
{

int value;
int count;
}arrays;

struct hashmap
{

struct arrays* table;
long long used;
long long size;

}hashmap;

bool Surplus(long long value)
{

int count = 0;

while (value>0 && count == 0)
{

if (value&1)
{

++count;
}
value = value>>1;
}
if (value>0)
{

return false;
}
return count == 1;
}

int countPairs1(int* deliciousness, int deliciousnessSize)
{

struct hashmap *map_ptr = malloc(sizeof(struct hashmap));
map_ptr->size = deliciousnessSize;
map_ptr->used = 0;

map_ptr->table = malloc(sizeof(struct arrays) * deliciousnessSize);

for (int i = 0; i < deliciousnessSize; ++i)
{

map_ptr->table[i].count = 0;
bool find = false;
int index = -1;
for (int j = 0; j < map_ptr->used; ++j)
{

if (map_ptr->table[j].value == deliciousness[i])
{

++map_ptr->table[j].count;
find = true;
break;
}
else if (map_ptr->table[j].value> deliciousness[i])
{

index = j;
++map_ptr->used;
for (int w = map_ptr->used ; w >j; --w)
{

map_ptr->table[w].value = map_ptr->table[w-1].value;
map_ptr->table[w].count = map_ptr->table[w-1].count;
}

break;
}
}
if (!find)
{

if (index != -1)
{

map_ptr->table[index].count = 1;
map_ptr->table[index].value = deliciousness[i];
}
else
{

map_ptr->table[map_ptr->used].count = 1;
map_ptr->table[map_ptr->used].value = deliciousness[i];
++map_ptr->used;
}

}
}
int count = 0;
for (int i = 0;i < map_ptr->used; ++i)
{

for (int j = i; j <  map_ptr->used; ++j)
{

if (i !=j)
{

if (Surplus(map_ptr->table[i].value + map_ptr->table[j].value))
{

count += map_ptr->table[i].count * map_ptr->table[j].count;
}
}
else if (map_ptr->table[i].count>1)
{

if (Surplus(map_ptr->table[i].value + map_ptr->table[j].value))
{

count += ((map_ptr->table[i].count-1) * map_ptr->table[i].count) /2; //等差数列
}
}
}
}
if(map_ptr)
{

if(map_ptr->table)
{

free(map_ptr->table);
}
free(map_ptr);
}
long M = 1000000007;
return count%M;
}


## 2，利用目标2的幂技巧

### ③，科学计数法

#### 1.什么是 1 e 9 1e9 1e9

1 e 9 = 1 ∗ 1 0 9 = 1000000000 ； 1e9 = 1*10^9 = 1000000000； 1e9=1109=1000000000

e表示10，e后面的数字表示次方，e的多少次方。

#### 2.C++中的 1 e 9 1e9 1e9

int n u m 1 = 1 e 9 ; { num1 = 1e9;} num1=1e9;
int n u m 1 = 1 e 10 ; {num1 = 1e10;} num1=1e10;

num1 = 1 000 000 000；
num2 = 1 410 065 408；

C/C++中int类型是32位的，范围是-2147483648 到 2147483647。
int占用4个字节，也就是32位，除了第一位代表符号，剩下的31位可用。

10 0101 0100 0000 1011 1110 0100 0000 0000前两位出现数据溢出问题。

int countPairs(int* deliciousness, int deliciousnessSize)
{

const int M = 1e9 + 7;
int hash[3000000]={

0}; //2的陪数 的差距保存哈希表
long long ans = 0;
for(int i = 0;i < deliciousnessSize; ++i)
{

//刚刚好是2的倍数
ans += hash[deliciousness[i]];
//距离 2的幂的距离统计个数 --》 这边为什么是22呢是因为2^21是最大值
for(int j = 0; j < 22; j++)
{

if(((1<<j)-deliciousness[i])>=0)
{

hash[(1<<j)-deliciousness[i]]++;
}
}
}
return ans % M;
}



0
0 收藏

0 评论
0 收藏
0