彬子的Blog

HashMap JDK 7 中 HashMap 的数据结构是数组+链表。 JDK 8 中 HashMap 的数据结构是数组+链表+红黑树。 ​ 它在链表长度大于8且数组长度大于64时候会把链表转换成红黑树 HashMap 的初始容量是 16，随着元素的不断添加，HashMap 就需要进行扩容，阈值是capacity * loadFactor，capacity 为容量，loadFactor 为负载因子，默认为...

LeetCode 24. 两两交换链表中的节点 题目大意 给定一个单链表，需要将链表中的节点按顺序两两交换，并返回交换后新的链表头节点。禁止只交换节点的数值，必须真实地调整指针。当链表长度为奇数时，最后一个节点保持原状。 示例 输入：head = [1,2,3,4] 输出：[2,1,4,3] 当输入为 head = [1,2,3] 时，结果应为...

P1439 【模板】最长公共子序列 题意 给定 的两个排列 、，求它们的最长公共子序列（LCS）长度。 思路 经典做法是 动态规划，但对于 的数据会超时。利用“两个序列都是排列”的性质，可以将 LCS 转化为 LIS（最长上升子序列）： 建立哈希（或数组）mp[val] 记录值 val 在序列 中的位置； 遍历 ，将 $P_2[i]在 $P_1$ 中的位置mp[P2[i]]`...

蓝桥杯 2023 岛屿个数 题目描述 给定 组测试数据，每组数据是一张 的二值地图，字符 1 表示陆地，字符 0 表示海洋，地图之外视为海水。两个相邻的 1（上、下、左、右四个方向）属于同一个岛屿。若某个岛屿完全被另一个岛屿包围，则称其为子岛屿；统计时只需统计最外层岛屿的数量，子岛屿不计入答案。 输入格式 第一行一个整数 。 接下来每组数据： 第一行两个整数 ； 接下来 行，每行一个长度为 ...

蓝桥杯 2024 省赛 A：成绩统计 题目描述 有 位同学，按照进教室的顺序依次得到编号 ，第 位同学的成绩为 。小蓝依次查看同学成绩：当他看完前 位同学的成绩时，可以在这 个人中任意挑出 名同学，计算他们成绩的方差。请问至少需要查看多少位同学，才有可能找到一组方差严格小于阈值 的 人集合。如果始终无法满足条件，输出 。 方差 的定义为 输入格式 第一行：三个整数 。 第二行： 个整数...

【模板】单调栈（P5788） 题意 给定一个长度为 的序列 ，定义 为第 个元素之后第一个严格大于 的元素下标，不存在则为 。输出 。 思路 从右向左维护“严格递减”的单调栈： 栈中存储下标，且对应的值严格递减； 对于当前位置 ，不断弹出小于等于 的下标，剩余的栈顶即为第一个更大的位置； 若栈为空，则 ； 处理完后将 入栈继续向左。 时间复杂度...