如何查看网站模板,服装 网站规划方案,软文广告营销,建设个人网页登陆网站持续更新
1.单调栈 它依旧是⼀个栈结构#xff0c;只不过⾥⾯存储的数据是递增或者递减的。 2. 单调栈解决的问题
*寻找当前元素左侧#xff0c;离它最近#xff0c;并且⽐它⼤的元素在哪#xff1b;
• 寻找当前元素左侧#xff0c;离它最近#xff0c;并且⽐它⼩的元素…持续更新···
1.单调栈 它依旧是⼀个栈结构只不过⾥⾯存储的数据是递增或者递减的。 2. 单调栈解决的问题
*寻找当前元素左侧离它最近并且⽐它⼤的元素在哪
• 寻找当前元素左侧离它最近并且⽐它⼩的元素在哪
• 寻找当前元素右侧离它最近并且⽐它⼤的元素在哪
• 寻找当前元素右侧离它最近并且⽐它⼩的元素在哪。 寻找当前元素左侧离它最近并且比它大的元素在哪 从左往右遍历元素构造⼀个单调递减的栈。插⼊当前位置的元素的时 • 如果栈为空则左侧不存在⽐当前元素⼤的元素 • 如果栈⾮空插⼊当前位置元素时的栈顶元素就是所找的元素。 注意因为我们要找的是最终结果的位置。因此栈⾥⾯存的是每个元素的下标。 2.单调队列 这⾥的队列和普通的队列不⼀样是⼀个双端队列 2. 单调队列解决的问题
⼀般⽤于解决滑动窗⼝内最⼤值最⼩值问题以及优化动态规划。 【题⽬描述】 有⼀个⻓为n 的序列a 以及⼀个⼤⼩为k 的窗⼝。现在这个从左边开始向右滑动每次滑动⼀ 个单位求出每次滑动后窗⼝中的最⼤值和最⼩值。 【输⼊描述】 输⼊⼀共有两⾏第⼀⾏有两个正整数 n , k 。 第⼆⾏ n 个整数表⽰序列 a 【输出描述】 输出共两⾏第⼀⾏为每次窗⼝滑动的最⼩值 第⼆⾏为每次窗⼝滑动的最⼤值 窗⼝内最⼤值 从左往右遍历元素维护⼀个单调递减的队列 • 当前元素进队之后注意维护队列内的元素在⼤⼩为 k 的窗⼝内 • 此时队头元素就是最⼤值。 3.并查集 在实现并查集的时我们⼀般让根节点⾃⼰指向⾃⼰ 在有些问题中我们需要维护若⼲个集合并且基于这些集合要频繁执⾏下⾯的操作 • 查询操作查找元素x 属于哪⼀个集合。⼀般会在每个集合中选取⼀个元素作为代表查询的是 这个集合中的代表元素 • 合并操作将元素 x所在的集合与元素 y所在的集合合并成⼀个集合注意合并的是元素所 在的集合不是这两个元素 • 判断操作判断元素 x 和 y 是否在同⼀个集合。 并查集Union Find是⼀种⽤于维护元素所属集合 的数据结构实现为⼀个森林其中每棵树表 ⽰⼀个集合树中的节点表⽰对应集合中的元素根节点来代表整个集合。 4.扩展域并查集 将每个元素拆分成多个域每个域代表⼀种状态或者关系。 通过维护这些域之间的关系来处理复杂的约束条件。 敌⼈朋友问题中我们会将 x 分成两个域朋友域 x 以及敌⼈域 y • x 和 y 是朋友正常处理把 x 和 y 合并成⼀个集合 • x 和y 是敌⼈那么 x和y 的敌⼈yn 就是朋友合并 x与yn y 和x 的敌⼈xn 就是朋友合并 y与xn 。 这样就可以利⽤两个域将所有的关系维护起来。 【问题食物链】 针对 x 扩展三个域同类域 x捕⻝域 x n被捕⻝域 x n n。 如果 x 和 y 是同类 • x 和 y 是同类 • x n 与 y n 是同类 • x n n 与 y n n 是同类 如果 x 捕⻝ y • x n 与 y 同类 • x 与 y n n 同类 • x n n 与 y n 同类 5.带权并查集 带权并查集在普通并查集的基础上为每个结点增加了⼀个权值。这个权值可以表⽰当前结点与⽗结点之间的关系、距离或其他信息注意由于我们有路径压缩操作所以最终这个权值表⽰的是当前结点相对于根结点的信息。有了这样⼀个权值就可以推断出集合中各个元素之间的相互关系。 【问题食物链】 把真话⾥⾯的相互关系⽤带权并查集维护起来权值表⽰当前节点相对于根节点的距离。那么对于集合中的任意两点 x 和 y • 如果 ( d [ y ] − d [ x ]) % 3 0 表⽰两者是同类关系 • 如果 ( d [ y ] − d [ x ]) % 3 1 表⽰两者是捕⻝关系 • 如果 ( d [ y ] − d [ x ]) % 3 2 表⽰两者是天敌关系。 find 操作 • 更新 d 数组按照最基础的距离更新的⽅式 d[x] d[x] d[fa[x]] union 操作 • 如果 x 和 y 是同类那么边权就是 0 • 如果 x 吃 y 那么边权就是 1 6.字符串哈希 定义⼀个把字符串映射到整数的函数 这就是字符串哈希。就是将⼀个字符串⽤⼀个整数表示。 单次计算⼀个字符串的哈希值复杂度是O ( N ) 。如果需要多次询问⼀个字符串的⼦串的哈希值每次重新计算效率⾮常低下。 ⼀般利⽤前缀和思想先预处理字符串中每个前缀的哈希值这样的话每次就能快速求出⼦串的哈希 了。 7.tree树 Trie 树⼜叫字典树或前缀树是⼀种能够快速插⼊和查询字符串的数据结构。它利⽤字符串的公共前缀将字符串组织成⼀棵树形结构从⽽⼤⼤提⾼了存储以及查找效率。 字典树作用
• 查询某个单词是否出现过并且出现⼏次
• 查询有多少个单词是以某个字符串为前缀
• 查询所有以某个前缀开头的单词这个作⽤可以⽤到输⼊法中输⼊拼⾳的时候可以提⽰可能
的单词
