树状数组

一、什么是树状数组

树状数组，其英文是 Binary Indexed Tree（简称 BIT），也称为 二叉索引树/二叉下标树。

• 树状数组虽然名称后缀是数组，但实际上是一棵由数组实现的树

最基本的树状数组支持 2 种操作：

• 单点修改：更新数组 nums 中任意单个元素值
• 区间查询：求数组 nums 中任意区间的元素和

并查集

一、什么是并查集？

并查集是一种简单的集合表示。

它支持以下 3 种操作：

• Initial(S)：将集合 S 中的所有元素初始化为一个个单元素集合
• Union(S, Root1, Root2)：把集合 S 中的子集合 Root2 并入子集合 Root1 中
• Find(S, x)：查找集合 S 中单元素 x 所在的子集合，并返回子集合的名字

排序算法的选择

一、算法汇总

希尔排序

一、什么是希尔排序？

• 希尔排序是一种基于插入排序进行了优化后的排序算法
• 希尔排序比普通插入排序更适用于大规模数组排序

二、为什么要用希尔排序？

散列表

一、什么是散列表？

1.1 定义

散列表（Hash Table），也称为哈希表，其定义如下：

• 散列表是一种能够根据关键字，直接访问到值的数据结构
• 散列表建立了关键字和存储地址之间的一种直接映射关系

其中，关键字称为 Key，对应的值称为 Value。

因此散列表也可以说是：

264. 丑数2

一、题目描述

给你一个整数 n ，请你找出并返回第 n 个 丑数 。

丑数 就是只包含质因数 2、3 和/或 5 的正整数。

输入：n = 10
输出：12
解释：[1, 2, 3, 4, 5, 6, 8, 9, 10, 12] 是由前 10 个丑数组成的序列。

854. 相似度为 K 的字符串

一、题目描述

对于某些非负整数 k ，如果交换 s1 中两个字母的位置恰好 k 次，能够使结果字符串等于 s2 ，则认为字符串 s1 和 s2 的 相似度为 k 。

给你两个字母异位词 s1 和 s2 ，返回 s1 和 s2 的相似度 k 的最小值。

输入：s1 = “ab”, s2 = “ba”
输出：1

698. 划分为k个相等的子集

一、题目描述

给定一个整数数组 nums 和一个正整数 k，找出是否有可能把这个数组分成 k 个非空子集，其总和都相等。

提示：

• 1 <= k <= len(nums) <= 16
• 0 < nums[i] < 10000
• 每个元素的频率在 [1,4] 范围内

跳表

一、什么是跳表？

跳表，又叫做跳跃表、跳跃列表。

• 是一种对有序链式线性表的优化
• 在原始链表的基础上添加了多级索引链表
• 分为多层，从下往上分别是原始链表、一级索引、二级索引…
• 搜索时从上往下，实现了类似“二分查找”的功能

922. 按奇偶排序数组 II

一、题目描述

给定一个非负整数数组A， A 中一半整数是奇数，一半整数是偶数。

对数组进行排序，以便：

• 当A[i] 为奇数时，i也是奇数；
• 当A[i]为偶数时，i 也是偶数。

你可以返回任何满足上述条件的数组作为答案。