PAT（甲级）1078 Hashing (25point(s))

阳光穿透心脏的1/2处 2024-05-08 05:59 84阅读 0赞

##### 题目 #####

[题目链接][Link 1]

##### 思路 #####

先判断原题hash位置有没有被占用，如果被占用，就进行二次平方探查；

##### 代码 #####

#include <iostream>
    #include <string>
    #include <cstring>
    #include <vector>
    #include <algorithm>
    using namespace std;
    const int maxn = 1e4 + 10;
    bool flag[maxn];
    
    bool isPrime(int a){
        
         if(a <= 1) return false;
         for(int i = 2; i * i <= a; i ++){
        
              if(a % i == 0) return false;
         }
         return true;
    }
    
    int main()
    {
        
         memset(flag, false, sizeof(flag));//初始化
         int s, n, t;
         scanf("%d%d", &s, &n);
         while(isPrime(s) == false) s ++;
         for(int i = 0; i < n; i ++){
        
              scanf("%d", &t);
              if(flag[t % s] == false) printf("%d", t % s), flag[t % s] = true;
              else{
        
                   //如果找不到进行平方探查
                   int step;
                   for(step = 1; step < s; step ++){
        
                        int idx = (t + step * step) % s;
                        if(flag[idx] == false){
        
                             flag[idx] = true;
                             printf("%d", idx);
                             break;
                        }
                   }
                   //如果大于size，说明放不下；
                   if(step >= s) printf("-");
              }
              if(i != n - 1) printf(" ");
         }
         system("pause");
         return 0;
    }

[Link 1]: https://pintia.cn/problem-sets/994805342720868352/problems/994805389634158592

发表评论取消回复

表情：

评论列表（有 0 条评论，84人围观）

还没有评论，来说两句吧...

相关阅读

相关 PAT 甲级 1129 Recommendation System (25 point(s)) set自动排序

题目题目链接思路题目大意：给一个人的选座记录，根据用户以往选择座位的次数来为推荐k个座位，按照选择的次数从大往小推荐，如果次数一样则按id从小到大排序做法：定义一个结构体...

不念不忘少年蓝@/ 2024年05月08日 06:14/ 0 赞/ 82 阅读

相关 PAT（甲级）1118 Birds in Forest (25point(s))

题目题目链接思路题目大意：在同一张照片里的鸟属于一个树，所以用并查集就可以做了；至于鸟的数量，可以通过set去重存储；代码#include <iostream&gt...

迈不过友情╰/ 2024年05月08日 06:02/ 0 赞/ 73 阅读

相关 PAT（甲级）1021 Deepest Root (25point(s))

题目题目链接思路题目大意：给一张图，这个图有点特殊，没有环且边数等于节点数-1，即是一棵树；每个节点都可能是根节点，要求是输出那些作为根节点时树的深度最大的节点；首先要判...

桃扇骨/ 2024年05月08日 06:01/ 0 赞/ 85 阅读

相关 PAT（甲级）1047 Student List for Course (25point(s))

题目题目链接思路题目大意：给出每个人所选的科目，要求按科目输出选择的人有哪些；先来分析一下，我们肯定需要为每个科目开一个数组，存储有哪些人选择了这个科目，但有个问题，名字...

港控/mmm°/ 2024年05月08日 06:00/ 0 赞/ 86 阅读

相关 PAT（甲级）1024 Palindromic Number (25point(s))

题目题目链接思路题目大意：判断一个字符串是不是回文串，如果不是可以翻转后相加在判断是不是回文串；本质是大数相加问题，大数相加需要先把数字翻转一下，将个位数字放到数组的第0...

悠悠/ 2024年05月08日 06:00/ 0 赞/ 84 阅读

相关 PAT（甲级）1078 Hashing (25point(s))

题目题目链接思路先判断原题hash位置有没有被占用，如果被占用，就进行二次平方探查；代码#include <iostream>#include <str...

阳光穿透心脏的1/2处/ 2024年05月08日 05:59/ 0 赞/ 85 阅读

相关 PAT（甲级）1101 Quick Sort (25point(s))

题目题目链接思路题目大意：判断一个数字是否大于他左边的任何数字且小于他右边的任何数字；先把每个数字左边的最大值和右边的最小值统计出来，分别用left 和 right 数组...

﹏ヽ暗。殇╰゛Y/ 2024年05月08日 05:53/ 0 赞/ 74 阅读

相关 PAT甲级1078 hashing

题目大意：利用除留余数法建hashtable，然后利用平方探查法缓解hash值冲突问题，然后要你输出每个输入的值在hashtable中的下标位置，如果不存在的话输出 -

深碍√TFBOYSˉ_/ 2023年07月24日 13:13/ 0 赞/ 17 阅读

相关 Python实现Pat 1078. Hashing (25)

Pat 1078. Hashing (25) The task of this problem is simple: insert a sequence of disti

男娘i/ 2022年06月05日 06:56/ 0 赞/ 198 阅读

相关 1078. Hashing (25)

The task of this problem is simple: insert a sequence of distinct positive integers into

红太狼/ 2022年05月29日 13:25/ 0 赞/ 124 阅读