配色设计网站推荐,运营网站赚钱,高端顺口公司名字,温州外贸网站制作文章目录 数据结构单链表栈表达式求值前缀表达式中缀表达式后缀表达式 队列单调栈单调队列KMPTrie并查集堆哈希表字符串哈希 数据结构
单链表
用数组模拟#xff08;静态链表#xff09;效率比定义Node类#xff08;动态链表#xff09;效率高些
使用数组模拟单链表静态链表效率比定义Node类动态链表效率高些
使用数组模拟单链表e [ ] 数组中存值ne [ ] 数组中存下个元素位置下标定义头指针head初始时指向-1定义idx表示用到了哪个下标
栈
定义数组 stk[ ] tt指向栈顶初始为-1插入时tt弹出时tt- - 查看栈是否为空只用看tt是否大于0即可栈顶元素即stk[tt]
表达式求值
前缀表达式
运算符位于操作数之前求值过程
从右向左读取表达式将遇到的数字压入栈中读到运算符是弹出栈顶操作数并进行计算
中缀表达式
常见的数学表达式运算符位于操作数之间
后缀表达式
也被称为逆波兰表达式运算符位于操作数之后后缀表达式不需要括号不存在优先级问题
求值过程与前缀表达式相同不过是从左向右读取
后缀表达式在计算机科学中有广泛的应用特别是在编译器设计、计算器实现和栈的应用中。它可以方便地用于计算复杂的算术表达式并且可以通过简单的迭代和栈操作来实现。可以将中缀表达式转换为后缀表达式使其更适合计算机程序中的求值过程。
队列
定义数组q[ ] hh为头下标初始为0tt为尾初始为-1尾部添加元素添加时q[tt] x头部删除删除hh即可
查看队列是否为空只用看hhtt如果是不为空不是就为空查看队头元素只用看q[hh]
单调栈
情景给一个序列找到一个数左边右边满足xx条件且离他最近的一个数
例如给一个序列找到每个数左边离他最近的且比他小的数不存在的话返回-1 暴力双层for循环一层逐个遍历一层从遍历的位置的前一个开始倒着遍历直到找到比他小的 单调栈思路 在读数据的同时维护一个栈如果栈不为空就比较栈顶元素和当前要加入的元素的大小如果大于或等于当前元素就将栈顶元素弹出直到新的栈顶元素比当前元素小就停止循环弹出栈顶元素如果此时栈不为空那么栈顶元素即答案栈为空答案为-1最后将当前元素入栈 这样维护的栈一定是单调的
单调队列
情景求滑动窗口中的最大值和最小值
例如给定一串数字有个大小为k的滑动窗口从左边移到右边求出每个位置的滑动窗口的最大值和最小值
普通队列维护一个队列当窗口向右走一步就将新的元素添加进队尾并删掉队头暴力求窗口中的最大和最小值即可单调队列 队列中存元素索引遍历整个数组先判断队头元素是否已经被移除窗口如果是将队头元素从队列中移除 获取窗口最小值判断队尾元素与当前元素大小若队尾元素大于当前元素删除队尾元素直到队尾元素小于当前元素再将当前元素添加到队尾然后判断当前遍历的元素是否达到窗口大小达到就输出队头窗口最小值即可 获取窗口最大值和上面一样只是判断队尾元素与当前元素大小相反
队尾添加元素添加的过程中保证目前的结果一定在队头队头取结果即可
KMP
习惯下标从1开始
对模板串处理对每个点预处理以某点为终点的后缀和前缀相等相等的长度最大为多少
next[ i ] j 以 i 为终点的后缀和从一开始的前缀相等而且后缀长度最长 记录的是最长公共前后缀长度
next[i] j;
p[1,j] p[i - j 1];Trie
用于高效存储查找字符串
模版 解释[0] [1] 3 表示根节点有个儿子 b 这个儿子在数组中的下标是3 [3] [4] 7 [3] 表示当前字符的下标[4] 表示当前字符有个儿子e下标为7 public class Main{final static int N 100010;static int[][]son new int[N][26]; //这里总共有26个字符static int[]cnt new int[N]; //以某个下标的字符为结尾的字符串个数static int idx 0; //表示下标自增来生成下标public static void insert(char[]str) {int p 0;for(int i 0;i str.length;i) {int u str[i] - a;if(son[p][u] 0) son[p][u] idx;p son[p][u];}cnt[p];}public static int query(char[]str) {int p 0;for(int i 0;i str.length;i) {int u str[i] - a;if(son[p][u] 0) return 0;p son[p][u];}return cnt[p];}
}并查集
用来快速处理 近乎O1
将两个集合合并询问两元素是否在一个集合当中 实现方式每个集合用一棵树来表示树根的编号就是整个集合的编号每个节点存储他的父节点p[x] 表示x的父节点 a1如何判断树根 p[x] x a2如何求x的集合编号while(p[x] ! x) x p[x] (一直向上找他的父节点直到找到了根) a3如何合并两集合把其中一个集合的集合编号等于另一棵树的集合编号 求集合编号时时间复杂度和树高是成正比的可能会出现树高过高问题需要优化 **优化**路径压缩 在从一个节点不断向上找到根节点时将走过的所有节点直接指向根节点 模版
public class Main{final static int N 100010;static int[]p new int[N];//找x的根节点 路径压缩static int find(int x) {if(x ! p[x]) p[x] find(p[x]);return p[x];}public static void main(String[]args) {Scanner sc new Scanner(System.in);int n sc.nextInt();for(int i 0;i n;i) p[i] i;//初始化int m sc.nextInt();for(int i 0;i m;i) {String l sc.next();int a sc.nextInt();int b sc.nextInt();if(M.equals(l)) p[find(a)] find(b);//合并两集合else {if(find(a) find(b)) System.out.println(Yes);else System.out.println(No);}}}
}有些题往往还需要维护别的变量
堆
完全二叉树最后一层节点从左到右依次排列
用数组存储堆
这里索引从1开始左儿子为 2x 右儿子为2x 1 父节点为 x / 2
以最小堆为例修改根节点元素需要将新的值下沉就让根元素和左右孩子比较与最小的那个交换一直到没法移了
上浮和父节点比较如果小于父节点和父节点交换位置
插入在heap[size] x再将这个数不断上浮
删除根节点 用堆的最后一个元素覆盖堆的根节点在将其不断下沉
删除任意一个元素heap[k] heap[size] ; size - - ; up(k) || down(k);
修改任意一个元素heap[k] x; down(k) || up(k);
将数组转化成堆
可以一个一个往堆里add复杂度为nlogn也可以从n/2 个元素开始倒着到1不断下沉操作
要修改第k个插入的元素还需要存个映射关系
第k个插入的元素的索引 ph[ ]索引为x的元素是第几个插入的 hp[ ]
交换堆中元素时也需要考虑到映射关系的改变
public static void heapSwap(int x,int y) {swap(ph,hp[x],hp[y]);swap(hp,x,y);swap(a,x,y);
}交换数组中的元素
public static void swap(int[]q,int a,int b) {int t q[a];q[a] q[b];q[b] t;
}哈希表
离散化是一种保序的hash方式只是其中一种
情景把0~10^9映射到 0 ~ 10^5 这些数
存储结构 开放寻址法拉链法 字符串哈希方式 a1hash函数一般怎么写 x mod 10^5取模的这个数尽可能是质数且离2整次幂尽可能远 a2处理冲突 开放寻址法拉链法将发生冲突的直接接在要插入的位置 在算法中对哈希表一般只有添加和查找两个操作
算法中对哈希表就算要删除往往不会真的删会再开一个数组对每个位置打一个标记标记一下被删除
拉链法
import java.util.Scanner;
import java.util.Arrays;
public class Main{final static int N 100003;static int[]h new int[N];//哈希表的槽static int[]e new int[N];//链表存值static int[]ne new int[N];//链表存下一个元素位置static int idx;//链表当前用到的索引static int hash(int x) {return (x%NN) % N;//计算hash值即该存入位置索引这样写目的是防止负数出现}//头插static void insert(int x) {int k hash(x);e[idx] x;ne[idx] h[k]; //h[k]就是每个链表的头指针h[k] idx;}static boolean find(int x) {int k hash(x);for(int i h[k];i ! -1;i ne[i]) {if(e[i] x) return true;}return false;}public static void main(String[]args) {Scanner sc new Scanner(System.in);Arrays.fill(h,-1);//相当于初始化每条链表头结点为-1int n sc.nextInt();for(int i 0;i n;i) {String l sc.next();int x sc.nextInt();if(l.equals(I)) insert(x);else {if(find(x)) System.out.println(Yes);else System.out.println(No);}}}
}开放寻址法 只用一个一维数组数组长度一般是题目要求的2~3倍经验值 添加 先用hash得到该存入的索引若该索引已有元素依次找下一个位置直到找到空的位置将元素插入 查找 用hash得到对应索引若对应索引元素不是要查找的元素依次往后找直到找到空的位置那么这个元素不存在 删除 先查找x然后对x打一个标记表示他被删除了 0x3f3f3f3f的十进制为1061109567和INT_MAX一个数量级即10^9 数量级而一般场合下的数据都是小于10^9的。 0x3f3f3f3f * 2 2122219134无穷大相加依然不会溢出。 public class Main{static final int nem 0x3f3f3f3f;//定义一个数据范围之外的数表示当前位置为空static final int N 200003;static int[]h new int[N];static int hash(int x) {return (x%NN) % N;}//核心//如果是添加返回的就是该添加的位置如果是查找返回位置要么就是这个元素的位置要么为空位置static int find(int x) {int k hash(x);while(h[k] ! nem h[k] ! x) {k;if(k N) k 0;}return k;}public static void main(String[]args) throws IOException{BufferedReader br new BufferedReader(new InputStreamReader(System.in));int n Integer.parseInt(br.readLine());Arrays.fill(h,nem);while(n -- 0) {String[]rr br.readLine().split( );int x Integer.parseInt(rr[1]);int we find(x);if(rr[0].equals(I)) {h[we] x;}else {if(h[we] x) System.out.println(Yes);else System.out.println(No);}}}
}字符串哈希
当我们需要快速判断两个字符串是否相等时可以使用
字符串前缀哈希法先预处理出字符串每个前缀的hash值 如何求字符串的hash值
p进制法 对于“ABCD”使用p进制表示可以表示成A * p^3 B * p^2 C * p^1 D * p^0mod Q其中将A映射成1B - - 2C - - 3D - - 4 结果可能比较大故给他模上一个Q使结果在 0 ~ Q - 1的范围内 不能映射成0如果A映射成0那么AA也是0AAA也是0……可以将他们映射成对应的ASII值当p取131或13331Q取2^64经验值在这种情况下我们可以不考虑冲突 我们可以利用预先求得的hash值可以根据公式求得所有子串的hash值。 例如 aabbaabb要求3 ~ 7L ~ R位置的子串和hash值即bbaab需要知道hash[2] (aa) 和 hash[7] (aabbaab)转化为p进制就是 11p和1122112p要求bbaab的hash值就是求22112p 可以将11p左移成1100000p即左移R - L 1位位运算理解即乘以 p^R - L 1 要求子串的hash值就可以表示为 hash[R] - hash[L - 1] * p^R - L 1 示例
public class Main{static final int N 100010;static int[]h new int[N];//预处理的前缀子串hash值static int[]p new int[N];//p[i]表示p的i次方将p的i次方预先算出来存到数组中static final int P 131;public static void main(String[]args) throws IOException {BufferedReader br new BufferedReader(new InputStreamReader(System.in));String[]ro1 br.readLine().split( );int n Integer.parseInt(ro1[0]);int m Integer.parseInt(ro1[1]);String s br.readLine();p[0] 1;for(int i 1;i n;i) {h[i] h[i - 1] * P s.charAt(i - 1);//求前缀子串hash值p[i] p[i - 1] * P;}while(m -- 0) {String[]ro2 br.readLine().split( );int l1 Integer.parseInt(ro2[0]);int r1 Integer.parseInt(ro2[1]);int l2 Integer.parseInt(ro2[2]);int r2 Integer.parseInt(ro2[3]);if(h[r1] - h[l1 - 1] * p[r1 - l1 1] h[r2] - h[l2 - 1] * p[r2 - l2 1]) System.out.println(Yes);else System.out.println(No);}}
}
