algorithm-hashmap
哈希大法
前缀和+哈希表
前缀和+哈希表前往这里
遍历过程维护集合大小
在遍历的过程中,我们可以通过前后双指针(滑动窗口),动态维护一个哈希表,来确保当前窗口的元素集合大小不超过某个值k,如下代码所示
12345678910111213for (int i = 0, j = 0; i < n; i++) { // 前后双指针+哈希表记录集合大小 for (; j < n && map.size() <= k; j++) { if (map.size() == k && map.get(nums[j]) == null) break; // 超过则退出循环 map.merge(nums[j], 1, Integer::sum); } res += j - i; if (map.get(nums[i]) == 1) { map.remove(nums[i]); } else { ma ...
note-java-stream
Stream
创建Stream
从数组创建
123Integer[] arr = {1, 3, 2, 5, 4};Stream<Integer> arrStream = Arrays.stream(arr);// Stream<Integer> arrStream = Stream.of(arr);
从集合创建
12List<Integer> list = Arrays.asList(arr);Stream<Integer> listStream = list.stream();
生成器Stream::generate和迭代器Stream::iterate
123456// 随机数生成器,输出5个随机数Stream<Double> generate = Stream.generate(Math::random);generate.limit(5).forEach((a)-> System.out.println("a = " + a));// 自然数迭代器,输出0、1、2、 ...
note-redis
《Redis设计与实现》:笔记
指令
Redis指令参考:Redis Order
结构
对象9
type:对象的类型
REDIS_STRING,字符串对象
REDIS_LIST,列表对象
REDIS_HASH,哈希对象
REDIS_SET,集合对象
REDIS_ZSET,有序集合对象
数据类型
汇总一个类型对应的多种编码
REDIS_STRING,字符串对象
REDIS_ENCODING_INT
要求字符串对象保存的是整数值, 并且这个整数值可以用 long 类型来表示
ptr属性里面(将 void* 转换成 long ), 并将字符串对象的编码设置为 int
通过 APPEND 命令, 向一个保存整数值的字符串对象追加了一个字符串值,对象的编码就会从int变成raw
REDIS_ENCODING_RAW
字符串对象保存的是一个字符串值,且长度大于 39 字节
ptr指针指向一个SDS对象(sdshdr)
REDIS_ENCODING_EMBSTR
字符串对象保存的是一个字符串值,且长度小于等于 39 字节
和raw一样,ptr指针指向一个SDS对象,但它的 ...
algorithm-series-hash-hash
二重哈希
第一个哈希的value被当作key放入第二个哈希
最高频率的 ID
你需要在一个集合里动态记录 ID 的出现频率。给你两个长度都为 n 的整数数组 nums 和 freq ,nums 中每一个元素表示一个 ID ,对应的 freq 中的元素表示这个 ID 在集合中此次操作后需要增加或者减少的数目。
**增加 ID 的数目:**如果 freq[i] 是正数,那么 freq[i] 个 ID 为 nums[i] 的元素在第 i 步操作后会添加到集合中。
**减少 ID 的数目:**如果 freq[i] 是负数,那么 -freq[i] 个 ID 为 nums[i] 的元素在第 i 步操作后会从集合中删除。
请你返回一个长度为 n 的数组 ans ,其中 ans[i] 表示第 i 步操作后出现频率最高的 ID 数目 ,如果在某次操作后集合为空,那么 ans[i] 为 0 。
示例 1:
**输入:**nums = [2,3,2,1], freq = [3,2,-3,1]
输出:[3,3,2,2]
解释:
第 0 步操作后,有 3 个 ID 为 2 的元素,所以 ans[0] = 3 ...
tips-misc
Markdown
段内换行
在一行的结尾插入两个或以上的空格
链接地址
链接和文字分开,例如google,baidu
1234[google],[baidu][google]:https://www.google.com[baidu]:https://www.baidu.com
网址链接
用<>包围,例如1234@qq.com(GFM拓展语法可以自动识别,不需要用<>)
1<1234@qq.com>
表情符号
:smile:: :smile:
:laughing:: :laughing:
表格
左对齐
居中对齐
右对齐
01
hello
a
02
world
b
1234| 左对齐 | 居中对齐 | 右对齐 || :--- | :--: | ---: || 01 | hello | a || 02 | world | b |
任务列表
[x] 已完成
[ ] 未完成
12- [x] 已完成- [ ] 未完成
锚点
Markdown
段内换行
链接地址
网址链接
表情符号
表格
任务列表
锚点
拓展
MySql
...
algorithm-tree-lca
最近公共祖先
描述
问题就是寻找树上两个节点的最近公共祖先节点
边权重均等查询
此题难度超过2500
现有一棵由 n 个节点组成的无向树,节点按从 0 到 n - 1 编号。给你一个整数 n 和一个长度为 n - 1 的二维整数数组 edges ,其中 edges[i] = [ui, vi, wi] 表示树中存在一条位于节点 ui 和节点 vi 之间、权重为 wi 的边。
另给你一个长度为 m 的二维整数数组 queries ,其中 queries[i] = [ai, bi] 。对于每条查询,请你找出使从 ai 到 bi 路径上每条边的权重相等所需的 最小操作次数 。在一次操作中,你可以选择树上的任意一条边,并将其权重更改为任意值。
注意:
查询之间 相互独立 的,这意味着每条新的查询时,树都会回到 初始状态 。
从 ai 到 bi的路径是一个由 不同 节点组成的序列,从节点 ai 开始,到节点 bi 结束,且序列中相邻的两个节点在树中共享一条边。
返回一个长度为 m 的数组 answer ,其中 answer[i] 是第 i 条查询的答案。
示例 1:
1234567输 ...
algorithm-cycling-pattern
循环节
循环节:指在序列中出现的一种重复的、周期性的模式。这个模式可以是一组连续的元素,也可以是整个序列的重复。
周期性特征:序列中的循环节反映了序列的周期性特征,即序列中的某一段会以某种方式重复出现。
寻找循环节的方法
快慢指针法:用两个指针,一个每次走一步,另一个每次走两步。如果存在循环节,两个指针最终会相遇。
哈希表法:使用哈希表记录每次遍历的状态,如果发现某个状态已经出现过,说明存在循环节。
统计重复个数
定义 str = [s, n] 表示 str 由 n 个字符串 s 连接构成。
例如,str == ["abc", 3] =="abcabcabc" 。
如果可以从 s2 中删除某些字符使其变为 s1,则称字符串 s1 可以从字符串 s2 获得。
例如,根据定义,s1 = "abc" 可以从 s2 = "ab***dbe***c" 获得,仅需要删除加粗且用斜体标识的字符。
现在给你两个字符串 s1 和 s2 和两个整数 n1 和 n2 。由此构造得到两个字符串,其中 str1 = ...
algorithm-difference-array
差分数组
一维的不多说了
二维差分数组
假设对于原矩阵,给一个左上角grid[l][u],右下角grid[r][d]的子矩阵的元素都添加一
那么对于差分数组diff[][]来说,相当于:
123456// 是否要+1取决于需求,都可以// l r u d分别表示左右上下diff[l][u]++; // 添加左上角到结束的矩阵(差分的特点就是,+1相当于加到了结束,联想一维的情况)diff[r+1][u]--; // 删除右上角到结束的矩阵diff[l][d+1]--; // 删除左下角到结束的矩阵diff[r+1][d+1]++; // 添加右下角到结束的矩阵(因为两次删除了重复的区域,所以要加回来)
比如:
123456789101112131415161718192021// 原矩阵0 0 0 0 0 00 0 0 0 0 00 0 0 0 0 00 0 0 0 0 00 0 0 0 0 00 0 0 0 0 0// 给一个左上角`grid[1][1]`,右下角`grid[3][3]`的子矩阵的元素都添加0 0 0 0 0 00 1 1 1 0 00 1 1 1 0 00 ...
algorithm-presum
前缀和
前缀和是一种数组变换方法,通过将数组中每个元素替换为从数组起始位置到当前位置的所有元素之和。这样,计算任意区间的和变得非常高效,只需一次前缀和计算即可,而不需要多次重复计算。
123int[] nums;int n = nums.length, sum[] = new int[n+1];sum[i+1] = sum[i] + nums[i];
需要用sum[0]表示空数组的和
l到r的区间和表示为 sum[r+1] - sum[l]
例如,nums[0]到nums[5]的区间和表示为 sum[6] - sum[0]
二维前缀和
定义sum[i+1][j+1]表示左上角grid[0][0],右下角grid[i][j]的子矩阵元素和
123456int[][] sum = new int[m + 1][n + 1];for (int i = 0; i < m; i++) { for (int j = 0; j < n; j++) { sum[i + 1][j + 1] = sum[i + 1][j] + sum[i][j + 1] ...
algorithm-monotonic-stack
单调栈
单调栈(Monotonic Stack)是一种特殊的栈,它首先是一个栈,其次栈中的所有元素单调递增或者单调递减。 单调栈在算法中的应用在于它能够在一次扫描即O(n)的复杂度之内找到数组中每一个元素的前上界(单增栈)或者前下界(单减栈)
主要用于在遍历过程中,需要保存上界或者下界的题目
美丽塔 II
给你一个长度为 n 下标从 0 开始的整数数组 maxHeights 。
你的任务是在坐标轴上建 n 座塔。第 i 座塔的下标为 i ,高度为 heights[i] 。
如果以下条件满足,我们称这些塔是 美丽 的:
1 <= heights[i] <= maxHeights[i]
heights 是一个 山脉 数组。
如果存在下标 i 满足以下条件,那么我们称数组 heights 是一个 山脉 数组:
对于所有 0 < j <= i ,都有 heights[j - 1] <= heights[j]
对于所有 i <= k < n - 1 ,都有 heights[k + 1] <= heights[k]
请你返回满足 美丽塔 要 ...