树状数组

一、什么是树状数组

树状数组，其英文是 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。

因此散列表也可以说是：

跳表

一、什么是跳表？

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

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

922. 按奇偶排序数组 II

一、题目描述

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

对数组进行排序，以便：

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

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

905. 按奇偶排序数组

一、题目描述

给定一个非负整数数组 A，返回一个数组，在该数组中， A 的所有偶数元素之后跟着所有奇数元素。

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

896. 单调数列

一、题目描述

如果数组是单调递增或单调递减的，那么它是单调的。

• 如果对于所有 i <= j，A[i] <= A[j]，那么数组 A 是单调递增的。
• 如果对于所有 i <= j，A[i]> = A[j]，那么数组 A 是单调递减的。

当给定的数组 A是单调数组时返回 true，否则返回 false。

746. 使用最小花费爬楼梯

一、题目描述

数组的每个下标作为一个阶梯，第 i 个阶梯对应着一个非负数的体力花费值cost[i]（下标从 0 开始）。

每当你爬上一个阶梯你都要花费对应的体力值，一旦支付了相应的体力值，你就可以选择向上爬一个阶梯或者爬两个阶梯。

请你找出达到楼层顶部的最低花费。在开始时，你可以选择从下标为 0 或 1 的元素作为初始阶梯。