Folders and files
| Name | Name | Last commit date | ||
|---|---|---|---|---|
先接个雨水吧
#【数学题】超级回文数
- 转 BigInt，从 1 - 100000 构造偶数回文 + 构造奇数回文，再判断平方数是否是回文数，结果转成字符串
- 最后结果升序排列
#【DFS】计算岛屿最大面积
- 定义 dfs 函数
- 越界判断/递归终止条件：i < 0 || i >= grid.length || j < 0 || j >= grid[0].length || grid[i][j] == 0，返回 0
- 走过的标记为 0
- 遍历上下左右四个方向，累加结果
- 遍历 grid，更新最大面积
#【DFS】二叉树的最大路径和
- maxSum = 0 初始化
- DFS，后序遍历
- 遍历到 null 节点，返回 0
- 计算当前节点的内部最大路径和（经过左右子树的最大和）
- 更新全局的最大路径和 maxSum
- 返回当前节点对其父节点能够贡献的最大路径和（只能选择左子树或右子树中的一个），如果小于 0 则返回 0
- 最终返回 maxSum，即二叉树中的最大路径和
#【双指针】最多能完成排序的块
双指针 sum1, sum2，对排序后的数组和原数组同时按顺序分别累加，两者只要相等一次，就视为找到一个块，最后返回 count
#【双指针】无重复字符的最长子串
- 滑动窗口，left = 0, right = 1 指针，right 指针遍历字符串，left 指针收缩窗口
- 当前窗口子串包含下一位字符，left 右移，不包含则 right 右移
- 返回窗口最大长度 max = Math.max(max, right - left)
#【哈希表】按位与为零的三元组
用哈希表 map 存储所有二元组按位与的结果与出现次数，再枚举数组 nums 与 map 所有的键，如果二者位与结果为 0 就累计其次数
#【DP】最长有效括号
- dp 定义：记录以坐标 i 结尾的最长有效括号子串长度
- 状态转移方程 dp[i] = 2 + dp[i-1] + dp[i - dp[i-1] -2] 【最小单元 ()(()) 】
- 注意判断 i - dp[i-1] -1 以及 i - dp[i-1] -2 是否越界，越界则表示不存在，直接为 0
#【DP】最长递增子序列
- 动态规划，dp[i] 表示以 nums[i] 结尾的最长递增子序列的长度
- 初始化 dp 数组，dp[i] = 1，result = 1；默认最长为 1
- 遍历 nums，对于每个 nums[i]，遍历 nums[0] - nums[i-1]，如果 nums[j] < nums[i]，则 dp[i] = max(dp[i], dp[j] + 1)
- result = max(result, dp[i])
- 返回 result
#【DP 二维】不相交的线 （最长公共子序列）
- 动态规划，dp[i][j] 表示 nums1 前 i 个元素和 nums2 前 j 个元素的最长公共子序列长度
- 初始化 dp 数组，dp[i][j] = 0，长度为 num1 + 1, num2 + 1
- 两层遍历
- 遍历条件 i = 1, i < num1.length, ++i，j = 1, j < num2.length, ++j
- 如果 nums1[i - 1] == nums2[j - 1]，则 dp[i][j] = dp[i-1][j-1] + 1
- 否则 dp[i][j] = Math.max(dp[i-1][j], dp[i][j-1]) （可能从左边或者上边转移过来）
- 返回 dp[num1.length][num2.length]
#【并查集】按公因数计算最大组件大小
迷之并查集
- 初始化并查集：unionfind 对象用于存储每个数或因子的根节点。
- 遍历数组 A：对每个数 num，计算它的所有因子，并将 num 与这些因子“合并”到同一个集合中。
- 合并操作：union 函数负责将 num 及其因子连在一起。并查集的 find 函数用来查找元素所属的根节点，并带有路径压缩优化。
- 统计最大连通分量：遍历数组 A，通过 find 找到每个数所属的连通分量的根节点，记录该连通分量的大小，并找出最大的连通分量。
/**
* @param {number[]} A
* @return {number}
*/
var largestComponentSize = function(A) {
// unionfind 用来记录每个数和因子的连通关系
const unionfind = {};
// 对数组 A 中的每个数进行因子分解，并将它与其因子加入同一个集合
for (const num of A) {
// 对当前数 num 进行因子分解，i 代表因子
for (let i = 2; i <= Math.sqrt(num); i++) {
// 如果 i 是 num 的因子，说明 num 可以被 i 整除
if (num % i === 0) {
// 将 num 的两个因子 i 和 num / i 以及 num 本身加入同一个集合
union(i, num / i, num);
}
}
}
// count 用于统计每个连通分量中的元素个数
const count = {};
let res = 0;
// 遍历数组 A，找到每个数所在的连通分量的根节点，并统计每个分量的大小
for (const num of A) {
const p = find(num); // 找到 num 所在连通分量的根节点
if (!count[p]) {
count[p] = 0;
}
count[p] += 1; // 统计该连通分量的大小
res = Math.max(res, count[p]); // 更新最大连通分量的大小
}
return res; // 返回最大连通分量的大小
// find 函数用于查找元素 i 所在集合的根节点（带路径压缩）
function find(i) {
// 如果 i 不在 unionfind 中，初始化它的根为自己
if (unionfind[i] === undefined) {
return (unionfind[i] = i);
}
// 如果 i 不是根节点，递归查找它的根，并路径压缩
return unionfind[i] === i ? i : (unionfind[i] = find(unionfind[i]));
}
// union 函数将 x, y, z 三个元素合并到同一个集合
function union(x, y, z) {
x = find(x); // 找到 x 的根节点
y = find(y); // 找到 y 的根节点
z = find(z); // 找到 z 的根节点
// 将 x 和 y 的根节点指向 z，将它们合并
unionfind[x] = unionfind[y] = z;
}
};#【单调栈】拼接最大数
迷之单调栈，先接个雨水吧
#【链表】按格式合并两个链表
迷之合并
#【位运算】解码异或后的排列
迷之位运算
/**
* @param {number[]} encoded
* @return {number[]}
*/
var decode = function(encoded) {
const x = Array.from({length: encoded.length + 1}, (v, k) => k + 1).reduce((acc, cur) => acc ^ cur);
const perm = [x, ...new Array(encoded.length)];
encoded.forEach((v, i) => i % 2 !== 0 && (perm[0] ^= v));
for (let i = 1; i < perm.length; i++) {
perm[i] = perm[i - 1] ^ encoded[i - 1];
}
return perm;
};#【状态压缩】最长超赞子字符串 迷之超赞
var longestAwesome = function (s) {
let prefixSum = 0;
let map = new Map();
let res = 1;
map.set(0, -1);
for (let i = 0; i < s.length; i++) {
prefixSum = prefixSum ^ (1 << s[i]);
// 考虑中间计算为偶数部分
if (map.has(prefixSum)) {
res = Math.max(res, i - map.get(prefixSum));
} else {
map.set(prefixSum, i);
}
// 考虑中间为奇数部分
for (let j = 0; j < 10; j++) {
let next = prefixSum ^ (1 << j);
if (map.has(next)) {
res = Math.max(res, i - map.get(next));
}
}
}
return res;
};