深圳网站建设公司联,缤纷销客crm,wordpress外贸插件,浏览wap网站目录
手写哈希表
1、开放寻址法
2、拉链法
字符串前缀哈希表法
2058. 笨拙的手指 - 哈希表 秦九韶算法#xff08;进制转换#xff09; 枚举
秦九韶算法——将x进制数转化为十进制数 手写哈希表
活动 - AcWing
1、开放寻址法 设 h(x)k#xff0c;也就是 x 的哈希值…目录
手写哈希表
1、开放寻址法
2、拉链法
字符串前缀哈希表法
2058. 笨拙的手指 - 哈希表 秦九韶算法进制转换 枚举
秦九韶算法——将x进制数转化为十进制数 手写哈希表
活动 - AcWing
1、开放寻址法 设 h(x)k也就是 x 的哈希值为 k 如果在 hash[k]的位置已经有元素持续往后遍历直到找到 x询问或为空插入为止 注意开放寻址法一般会把数组开到数据范围的 2−3 倍能提高效率 import java.util.*;class Main
{static int N200003,nul0x3f3f3f3f; //质数static int[] hnew int[N];public static int find(int x){int k(x%NN)%N;while(h[k]!nulh[k]!x) //如果该坑位不为空且该坑位不为x如果x已经存过就不存了{k;if(kN) k0;}return k; //如果找到x则返回x所在的位置//如果没有找到x则返回x应该存放的位置}public static void main(String[] args){Scanner scnew Scanner(System.in);int nsc.nextInt();Arrays.fill(h,nul);while(n--0){String ssc.next();int xsc.nextInt();int kfind(x);if(s.equals(I)) h[k]x;else if(s.equals(Q)){if(h[k]!nul) System.out.println(Yes);else System.out.println(No);}}}
}2、拉链法 设 h(11)3h(23)3 这就是一种冲突 我们可以设一个数组h也就是哈希的结果 对于每一个结果k建立一个链表 把映射为 k 的所有数 x 都放在 h[k] 这个链表里 import java.util.*;class Main
{static int N100003; //质数static int[] hnew int[N],enew int[N],nenew int[N];static int idx;public static void insert(int x){int k(x%NN)%N; //N%N是为了让负数变成正数e[idx]x;ne[idx]h[k];h[k]idx;}public static boolean find(int x){int k(x%NN)%N;for(int ih[k];i!-1;ine[i])if(e[i]x) return true;return false;}public static void main(String[] args){Scanner scnew Scanner(System.in);int nsc.nextInt();Arrays.fill(h,-1);while(n--0){String ssc.next();int xsc.nextInt();if(s.equals(I)) insert(x);else if(s.equals(Q)){if(find(x)) System.out.println(Yes);else System.out.println(No);}}}
}字符串前缀哈希表法 把字符串变成一个p进制数字哈希值实现不同的字符串映射到不同的数字 对形如 的字符串采用字符的ascii 码乘上 P 的次方来计算哈希值 映射公式 注意 任意字符不可以映射成0否则会出现不同的字符串都映射成0的情况比如A,AA,AAA皆为0通过巧妙设置P (131 或 13331) , Q ()的值一般可以理解为不产生冲突 比较不同区间的子串是否相同就转化为对应的哈希值是否相同 求一个字符串的哈希值就相当于求前缀和求一个字符串的子串哈希值就相当于求部分和 字符串前缀和公式 h[i] h[i-1]*P s[i]; 区间和公式 区间和公式的理解: ABCDE 与 ABC 的前三个字符值是一样只差两位 乘上 把 ABC 变为 ABC00再用 ABCDE - ABC00 得到 DE 的哈希值 活动 - AcWing 题目 import java.util.*;class Main
{static int N100010;static long[] hnew long[N],pnew long[N];static int P131;public static void main(String[] args){Scanner scnew Scanner(System.in);int nsc.nextInt(),msc.nextInt();String s/sc.next();//下标从1开始p[0]1;for(int i1;in;i){p[i]p[i-1]*P;h[i]h[i-1]*Ps.charAt(i);}while(m--0){int l1sc.nextInt(),r1sc.nextInt();int l2sc.nextInt(),r2sc.nextInt();long h1h[r1]-h[l1-1]*p[r1-l11];long h2h[r2]-h[l2-1]*p[r2-l21];System.out.println(h1h2?Yes:No);}}
} 2058. 笨拙的手指 - 哈希表 秦九韶算法进制转换 枚举
2058. 笨拙的手指 - AcWing题库 题目 第一行给你一个N的二进制表示其中有一位是错误的 第二行给你一个N的三进制表示其中有一位是错误的 输出N的正确十进制值题目保证一定有唯一解 思路 枚举二进制数a的所有换1位的情况转化为十进制值存入哈希表 枚举三进制数b的所有换1位情况转化为十进制后在哈希表中查询是否存在 因为题目保证一定有唯一解所以两者交集即为答案 因此如果查询到则输出 秦九韶算法——将x进制数转化为十进制数 public static int get(String s,int x)
{int res0;for(int i0;is.length();i){char ts.charAt(i);resres*x t-0;}return res;
} import java.util.*;class Main
{static int N100010;public static int get(char[] s,int x)//将x进制数s转化为十进制数{//秦九韶算法int res0;for(int i0;is.length;i){resres*xs[i]-0;}return res;}public static void main(String[] args){Scanner scnew Scanner(System.in);char[] asc.next().toCharArray();char[] bsc.next().toCharArray();SetInteger stnew HashSet();for(int i0;ia.length;i){a[i]^1;st.add(get(a,2));a[i]^1;}for(int i0;ib.length;i){char tb[i];for(int j0;j3;j) //将这一位换成除了本身的其他数if(t-0!j){b[i](char)(j0);int tpget(b,3);if(st.contains(tp)){System.out.print(tp);return;}}b[i]t; //换完该位要恢复现场 继续换下一位}}
}
