Estom的博客

n个骰子的点数 生成幂集的循环方法。完全一致，也是动态规划问题。 1 n个骰子的点数问题描述 把n个骰子扔在地上，所有骰子朝上一面的点数之和为s。输入n，打印出s的所有可能的值出现的概率。你需要用一个浮点数数组返回答案，其中第 i 个元素代表这 n 个骰子所能掷出的点数集合中第 i 小的那个的概率。 示例 1: 123456输入: 1输出: [0.16667,0.16667,0.16667,0.16667,0.16667,0.16667]示例 2:输入: 2输出: [0.02778,0.05556,0.08333,0.11111,0.13889,0.16667,0.13889,0.11111,0.08333,0.05556,0.02778] 问题分析策略选择算法设计 使用动态规划解决问题一般分为三步： 确定状态变量 确定状态转移方程 边界处理 表示状态 分析问题的状态时，不要分析整体，只分析最后一个阶段即可！因为动态规划问题都是划分为多个阶段的，各个阶段的状态表示都是一样，而我们的最终答案在就是在最后一个阶段。 通过题目我们知道一共投掷 n 枚骰子，那最后一个阶...

1 进位计数数制 2进制—-字面量0b 8进制—-字面量0 10进制—无 16进制0x-字面量0x 数制转化 r进制数转化成十进制$$I = a_{n-1}\times r^{n-1} + \cdots + a_0 \times r^0$$ 十进制整数转化r进制数——除r取余法$$\frac Ir=\frac{a_{n-1}\times r^{n-1}+ \cdots + a_0 \times r^0}{r} + \frac {a_0 \times r^0}{r}$$ 十进制小数转化r进制数——乘r取整法$$f = a_{-1} \times r^{-1} + a_{-(m-1)} \times r^{-(m-1)} + a_{-m} \times r^{-(m-1)}$$ 为什么十进制相对其他进制来说特殊，因为我们在计算的时候，加减乘除，全部都使用十进制的法则，所以十进制计算表达起来更简单。 2 数值编码 $2^{n-1}$表示最高位是1 $2^n$表示最高位的溢出位为1 原码$$(X)_y=\left{ \begin{a...

1 队列的最大值问题描述 请定义一个队列并实现函数 max_value 得到队列里的最大值，要求函数max_value、push_back 和 pop_front 的均摊时间复杂度都是O(1)。 若队列为空，pop_front 和 max_value 需要返回 -1 示例 1： 1234输入: ["MaxQueue","push_back","push_back","max_value","pop_front","max_value"][[],[1],[2],[],[],[]]输出: [null,null,null,2,1,2] 链接 问题分析策略选择 数据结构：单调队列 算法思想：后入的较大值，会把之前的较大值排除。但是后入的次大值，不会将之前的最大值排出队列。所以维护两个队列，一个用来删除元素，一个用来找到最大值（单调队列） 算法设计 本算法基于问题的一个重要性质：当一个元素进入队列的时候，它前面所有比它小的元素就不会再对答案产生影响。 举个...

数组离散化1 问题描述 离散化一个序列的前提是我们只关心这个序列里面元素的相对大小，而不关心绝对大小（即只关心元素在序列中的排名）；离散化的目的是让原来分布零散的值聚集到一起，减少空间浪费。那么如何获得元素排名呢，我们可以对原序列排序后去重，对于每一个$a_i$通过二分查找的方式计算排名作为离散化之后的值。当然这里也可以不去重，不影响排名。 数组本质上是一种有序的映射。i—-A—->x 即(A[i]=x)的映射。有时候为了建立值的数量与坐标i的反向映射，但此时值x的范围是离散化的。需要建立离散数组。一个的额外的映射数组，完成反向映射x—-B—->i。 2 离散数组——数组实现方法 使用数组B作为离散数组的映射。B的下标i能够反映原来数组中各个元素的大小顺序。但不是原来数组中各个元素的值。 建立离散数组的时间复杂度为O(nlog n)需要对原数组进行快速排序。 代码实现 12345678910vector<int> nums;//表示原来的数组vector<int> tmp = nums;//对离散数组进行排序sort(tmp.b...

单调栈 用来解决局部顺序问题 柱形图问题多使用单调栈。 下边是对柱形图问题的总结。 视野总和：利用了栈内元素的数量计算问题。 柱形图中的最大矩形：利用的是出栈序列。这组序列构成了可能的最大矩形。 盛最多水的容器：利用了反向贪心思想。 接雨水问题：单调栈解法也是利用了出栈序列。这个序列的左右边界能够形成一个容器。双指针解法利用了反向贪心思想。 接雨水问题2 其它类型的单调栈 求最大区间：利用的出栈的序列。表示一个可能的最大值区间。 132模式：利用了其有序性。 1 视野总和问题描述 有n个人站队，所有的人全部向右看，个子高的可以看到个子低的发型，给出每个人的身高，问所有人能看到其他人发现总和是多少。 123输入：4 3 7 1输出：2解释：个子为4的可以看到个子为3的发型，个子为7可以看到个子为1的身高，所以1+1=2 问题分析 问题分类: 思路：观察题之后，我们发现实际上题目转化为找当前数字向右查找的第一个大于他的数字之间有多少个数字，然后将每个结果累计就是答案，但是这里时间复杂度为O(N^2)，所以我们使用单调栈来解决这个问题。 策略选择 数据结构：单调栈 算...

字典树Trie 参考资料 字典树trie 数据结构算法10 1 Trie定义 Trie，又称前缀树或字典树，是一种有序树，用于保存关联数组，其中的键通常是字符串。与二叉查找树不同，键不是直接保存在节点中，而是由节点在树中的位置决定。一个节点的所有子孙都有相同的前缀，也就是这个节点对应的字符串，而根节点对应空字符串。一般情况下，不是所有的节点都有对应的值，只有叶子节点和部分内部节点所对应的键才有相关的值。 字典树设计的核心思想是空间换时间，所以数据结构本身比较消耗空间。但它利用了字符串的**共同前缀（Common Prefix）**作为存储依据，以此来节省存储空间，并加速搜索时间。Trie 的字符串搜索时间复杂度为 O(m)，m为最长的字符串的长度，其查询性能与集合中的字符串的数量无关。其在搜索字符串时表现出的高效，使得特别适用于构建文本搜索和词频统计等应用。 2 Trie 的性质 根节点（Root）不包含字符，除根节点外的每一个节点都仅包含一个字符； 从根节点到某一节点路径上所经过的字符连接起来，即为该节点对应的字符串； 任意节点的所有子节点所包含的字符都不相同； ...

线性区间操作区间操作分类 修改区间值，询问元素值。（差分数组） 修改元素值，访问区间值。（树状数组和线段树） 修改元素值，查询最大最小值。（线段树） 1 数组中的逆序对问题描述在数组中的两个数字，如果前面一个数字大于后面的数字，则这两个数字组成一个逆序对。输入一个数组，求出这个数组中的逆序对的总数。 问题分析策略选择 数据结构：线性数组、树状数组 算法思想：用树状数组解决逆序数问题，也是一个经典的做法。树状数组是一种实现了高效查询「前缀和」与「单点更新」操作的数据结构， 算法设计具体的做法是： 先离散化，将所有的数组元素映射到 0、1、2、3… ，这是为了节约树状数组的空间； 从后向前扫描，边统计边往树状数组里面添加元素，这个过程是「动态的」，需要动手计算才能明白思想。 我们可以看出它第i−1 位的前缀和表示「有多少个数比 i 小」。那么我们可以从后往前遍历序列a，记当前遍历到的元素为 $a_i$，我们把$a_i$对应的桶的值自增 1，把 i - 1位置的前缀和加入到答案中算贡献。 我们显然可以用数组来实现这个桶，可问题是如果$a_i$中有很大的元素，比如 10^9我...

单调栈定义 单调栈中存放的数据应该是有序的，所以单调栈也分为单调递增栈和单调递减栈 单调递增栈：单调递增栈就是从栈底到栈顶数据是从小到大 单调递减栈：单调递减栈就是从栈底到栈顶数据是从大到小 规则 （单调递减栈）现在有一组数10，3，7，4，12。从左到右依次入栈，则如果栈为空或入栈元素值小于栈顶元素值，则入栈；否则，如果入栈则会破坏栈的单调性，则需要把比入栈元素小的元素全部出栈。 0入栈时，栈为空，直接入栈，栈内元素为10。 入栈时，栈顶元素10比3大，则入栈，栈内元素为10，3。 入栈时，栈顶元素3比7小，则栈顶元素出栈，此时栈顶元素为10，比7大，则7入栈，栈内元素为10，7。 入栈时，栈顶元素7比4大，则入栈，栈内元素为10，7，4。 2入栈时，栈顶元素4比12小，4出栈，此时栈顶元素为7，仍比12小，栈顶元素7继续出栈，此时栈顶元素为10，仍比12小，10出栈，此时栈为空，12入栈，栈内元素为12。 应用 局部顺序问题，可以使用单调栈解决。例如存在一个局部增序的序列。需要找到所有的局部增序的序列。则单调增栈的每次连续入栈，都是增序。每次连续出栈都是违反增序规...

树状数组Binary Tree Array1 概念lowbit运算$$lowbit(x) = x & ((\sim x)+1)$$ 作用：二进制表示中，保留最后的1。如x=10100100,lowbit(x)=00000100 树状数组 根据lowbit的运算规则构建树状数组。 其中数组A第i个位置的值管理区间[i-lowbit(i)+1,i]。即去掉二进制最后一位后到当前位置的的区间。 $$A[i] = \sum_{k=i-lowbit(i)+1}^i A[k]$$ 其中数组A第i个位置的值的被管节点。即找到所有的之后的$2^i$的点，也包括非$2^i$的点。 $$i = i + lowbit(i) ,i<max(i)$$ 本质理解 怎么看每个原始数组的数字管理多少？只要顺着原始数组的数字往下画竖线，碰到的第一根横线所覆盖的范围就是它能管理的范围。 怎么看每个原始数组的数字被谁管理？顺着原始数组的数字往下画竖线，碰到的第一根横线之后的所有横先，都是管理该数字的树状数组值。 在构建的树状数组中$2^i$管理之前...

线段树Segment Tree1 线段树的概念概述 线段树(Segment Tree)也是一棵树，只不过元素的值代表一个区间。常用区间的 统计 操作，比如一个区间的 最大值(max),最小值(min),和(sum) 等等 如一个长度为10的数组，它对应的 求和 线段树，如下图所示(图中的数字表示索引)： 定义 线段树是一个平衡二叉树，但不一定是完全二叉树。 根节点就是 0~lenght-1 的和 根节点的左右子树平分根节点的区间 然后依次类推，直到只有一个元素不能划分为止，该元素也就是二叉树的叶子节点。 复杂度 时间复杂度为O(log n) 空间复杂度为O(n) 2 线段树的基本操作构建线段树 根据上面我们对线段树的描述，构建一个线段树就比较简单了，根节点就是整个区间，根节点的左右子树平分根节点的区间，直至区间内只剩下一个元素不能平分为止。如下面递归的伪代码： 123456789101112131415161718192021private void buildSegmentTree(int treeIndex, int treeLeft, int treeRi...