Algorithm
1、基础算法
2、数据结构
2.1 并查集
2.1.1 好路径的数目
-
题目：
给你一棵 n 个节点的树（连通无向无环的图），节点编号从 0 到 n - 1 且恰好有 n - 1 条边。 给你一个长度为 n 下标从 0 开始的整数数组 vals ，分别表示每个节点的值。同时给你一个二维整数数组 edges ，其中 edges[i] = [ai, bi] 表示节点 ai 和 bi 之间有一条 无向 边。 一条 好路径 需要满足以下条件： 开始节点和结束节点的值 相同 。 开始节点和结束节点中间的所有节点值都 小于等于 开始节点的值（也就是说开始节点的值应该是路径上所有节点的最大值）。 请你返回不同好路径的数目。 注意，一条路径和它反向的路径算作 同一 路径。比方说， 0 -> 1 与 1 -> 0 视为同一条路径。单个节点也视为一条合法路径。 -------------------------------------------------------- 示例1: 输入：vals = [1,3,2,1,3], edges = [[0,1],[0,2],[2,3],[2,4]] 输出：6 解释：总共有 5 条单个节点的好路径。 还有 1 条好路径：1 -> 0 -> 2 -> 4 。 （反方向的路径 4 -> 2 -> 0 -> 1 视为跟 1 -> 0 -> 2 -> 4 一样的路径） 注意 0 -> 2 -> 3 不是一条好路径，因为 vals[2] > vals[0] 。 -
解法：
class f: # 并查集数据结构，可依照需要修改 def __init__(self, val, x): self.val = val self.dic = {x: 1} class Solution: def myFind(self, arr, x): if arr[x].val != x: arr[x].val = self.myFind(arr, arr[x].val) return arr[x].val def numberOfGoodPaths(self, vals: List[int], edges: List[List[int]]) -> int: n = len(vals) # 取所有的单个节点值 res = n # 按照每个节点的值进行排序 arr = [] for i in range(n): arr.append((vals[i], i)) arr.sort() # 处理每个节点相关联的路径（可用二维数组代替） dic = {} for pair in edges: if pair[0] not in dic.keys(): dic[pair[0]] = [] dic[pair[0]].append(pair[1]) if pair[1] not in dic.keys(): dic[pair[1]] = [] dic[pair[1]].append(pair[0]) # 初始化并查集 arrFind = [] for i in range(n): arrFind.append(f(i, vals[i])) # 开始处理 for i in range(n): tar = arr[i][0] node = arr[i][1] if dic.get(node, -1) == -1: continue for j in dic[node]: if vals[node] >= vals[j]: px = self.myFind(arrFind, node) py = self.myFind(arrFind, j) if px != py: res += arrFind[px].dic.get(tar) * arrFind[py].dic.get(tar, 0) # 并查集的union操作，先对元素值进行操作 arrFind[px].dic[tar] += arrFind[py].dic.get(tar, 0) # 合并两个连通块并设置其中一个根指向另一个根 arrFind[py].val = px return res
2.2 线段树
2.2.1 最长递增子序列 II
-
原题链接：https://leetcode.cn/problems/longest-increasing-subsequence-ii/
-
题目：
给你一个整数数组 nums 和一个整数 k 。 找到 nums 中满足以下要求的最长子序列： `子序列 严格递增` `子序列中相邻元素的差值 不超过 k 。` 请你返回满足上述要求的 `最长子序列` 的长度。 子序列 是从一个数组中删除部分元素后，剩余元素不改变顺序得到的数组。 -------------------------------------------------------- 示例： 输入：nums = [4,2,1,4,3,4,5,8,15], k = 3 输出：5 解释： 满足要求的最长子序列是 [1,3,4,5,8] 。 子序列长度为 5 ，所以我们返回 5 。 注意子序列 [1,3,4,5,8,15] 不满足要求，因为 15 - 8 = 7 大于 3 。 -
解法：
2.3 字典树
3、搜索与图论
4、数学知识
5、动态规划
5.1 状态压缩动态规划
5.1.1 划分为k个相等的子集
-
原题链接：https://leetcode.cn/problems/partition-to-k-equal-sum-subsets/
-
题目：
给定一个整数数组 nums 和一个正整数 k，找出是否有可能把这个数组分成 k 个非空子集，其总和都相等。 --------------------------------------------------------------------------------- 示例 1： 输入： nums = [4, 3, 2, 3, 5, 2, 1], k = 4 输出： True 说明： 有可能将其分成 4 个子集（5），（1,4），（2,3），（2,3）等于总和。 -
解法：
5.1.2 旋转数字
-
题目：
我们称一个数 X 为好数, 如果它的每位数字逐个地被旋转 180 度后，我们仍可以得到一个有效的，且和 X 不同的数。要求每位数字都要被旋转。 如果一个数的每位数字被旋转以后仍然还是一个数字， 则这个数是有效的。0, 1, 和 8 被旋转后仍然是它们自己；2 和 5 可以互相旋转成对方（在这种情况下，它们以不同的方向旋转，换句话说，2 和 5 互为镜像）；6 和 9 同理，除了这些以外其他的数字旋转以后都不再是有效的数字。 现在我们有一个正整数 N, 计算从 1 到 N 中有多少个数 X 是好数？ -------------------------------------------------------------------------------------- 示例1: 输入: 10 输出: 4 解释: 在[1, 10]中有四个好数： 2, 5, 6, 9。 注意 1 和 10 不是好数, 因为他们在旋转之后不变。 -
解法：