devbox
小丑西瓜9
这个屌丝很懒，什么也没留下！
关注作者
热门标签
热门文章
当前位置:   article > 正文

leetcode题目总结_leetcode将正数放到一侧

作者：小丑西瓜9 | 2024-02-16 13:19:32

赞

踩

leetcode将正数放到一侧

文章目录

基础算法

前缀和

题目名称题目简述
5144矩阵区域和-中稍微变化了一下的二维前缀和。注意不要越界
1310. 子数组异或查询-中异或前缀和
274. H指数直接模拟是O(nlogn)。其实可以先统计一下不同引用数量的论文各有多少篇（大于n的就当成n）。然后求个后缀和，cnt[i]的含义就是有cnt[i]篇论文引用数量大于i。只要i大于s，i就–。同时s加上对应的数值（就是后缀和）
303. 区域和检索 - 数组不可变裸前缀和
304. 二维区域和检索 - 矩阵不可变裸二维前缀和
325. 和等于 k 的最长子数组长度数字可能有负数，所以不能用双指针（双指针得要单调）。就用map记录出现过的数字，sum记录到目前为止的前缀和。如果出现过x，使得sum-x=k。也就是x=sum-k出现过，那就说明这一段之和为k，因为要最大值，所以记录第一个出现的位置就好。
363. 矩形区域不超过 K 的最大数值和前缀和+二分。这道题相当于要暴力所有不同大小的矩形。所以需要遍历每个列，从当前列开始遍历后面所有的列，同时用sum记录所有行的之和。sum这个数组就记录了从当前列开始，矩形的大小。然后要让和<=k。就算对sum算一遍前缀和，sumj - sumi <= k => sumi >= sumj - k。用set存储之前出现过的前缀和。用lower_bound找出>=sumj - k的前缀和。

哈希

题目名称题目简述
不同的循环子字符串-良题目写的不清楚，我还以为要用KMP求循环结。实际上就是比较两端是不是相同。直接字符串哈希。记住13111
30. 串联所有单词的子串-挺好字符串哈希是真的好用啊。不过要主意好get哈希值的时候左右指针的位置。不过我这个算法也是O(n^2)的。

双指针

题目名称题目简述
1. 两数之和双指针，排序之后从两边搜索。如果大了右指针往左移，否则左指针往右移。
2.两数相加一位一位算，记录好进位就行
3. 无重复字符的最长子串滑动窗口，双指针。如果窗口内有重复数字，左指针就不断向右移。
5.最长回文子串每个点暴力搜索一下。记录一下最大区间的左右端点。
11. 盛最多水的容器O(n)时间从左右两边搜索。每次都贪心的让矮的一侧往内走。记录全局最大值就好。
15.三数之和two sum的扩展。遍历第一个数，然后用two sum的方法算后两个数。主要难点在于去重。第一个数去重：如果和上一个数相同就要continue。后两个数去重：搜到一个结果的时候也要跳过和结果相同的几个数字。
16.最接近的三树之和和上面这道题差不多，只不过每次都记录一下和目标最接近的和
18.四数之和就是遍历前两个数字，后面两个数字用two sum的方法。去重可以用哈希表或者跳过重复数字。
26. 删除排序数组中的重复项-水一个指针往后找不重复的数，一个指针把数放在数组前面。
27. 移除元素-水一个指针找不等于val的数，一个指针放置数字
28. 实现 strStr()双指针或字符串
151. 翻转字符串里的单词先整体反转，再一段一段地反转。多余空格的问题再额外多一个指针来专门放置字母。如果不处理后面的空格最后有可能会多一个空格，所以要预处理一下最后的空格。
167. 两数之和 II - 输入有序数组two sum同款，返回index就好
168. Excel表列名称26进制转换
186. 翻转字符串里的单词 II这是151的简化版本。
209. 长度最小的子数组右指针不断搜索。如果满足条件就让左指针不断向右。
228. 汇总区间贪心的来做就好。扫描每个数字，如果和下一个树是连续的，就把这种区间都找出来，然后把结果加入返回数组中。
229. 求众数 II用两个变量统计最多的两个数字。如果两个变量大于三分之一。就把这个数加入到返回数组中。
240. 搜索二维矩阵 II双指针，和之前遇到那道题也没啥变化
283. 移动零一个指针找非0元素，一个指针放置数字（交换就行）。
340. 至多包含 K 个不同字符的最长子串一个指针加数字，另一个指针维护性质
392. 判断子序列简单双指针。

滑动窗口

题目名称题目简述
76. 最小覆盖子串每次移动右指针，直到所有字母都包括在内。然后尝试缩小左指针。直至不包括所有字母就再次移动右指针。
187. 重复的DNA序列长度为10的滑动窗口
219. 存在重复元素 II用哈希表，如果哈希表个数大于k，就把最前面一个元素删掉。

二分

题目名称题目简述
4. 寻找两个有序数组的中位数-好题经典题目。把两个数组分开考虑。两个数组的左边部分都应该小于等于右边部分。否则，就是看看边界情况。如果i0，说明a数组全都大于等于b数组。j0，就说明b全都大于等于a数组。
33. 搜索旋转排序数组-挺好经典题目。旋转之后左边的数都大于等于第一个数，右边的数都小于（因为没有重复的数）。所以先找到分界点。再根据target大小情况在左边或者右边的单调区间里面二分查找。
34. 在排序数组中查找元素的第一个和最后一个位置-不错二分就是要找到区间二分的性质。第一个数右边的数都大于等于它，最后一个数左边的数都小于等于它。记住取中位数的时候，如果是l=mid，记得要(l + r + 1) / 2。
35. 搜索插入位置这道题翻车了。二分的时候如果等于就直接返回。否则等于mid+1或mid-1。这样结果就正好是插入的位置。那个二分模板比较适合找范围内的。这道题会搜到范围外。
69. x 的平方根比较扯淡的是要返回整数。所以等于就返回，大于r=mid-1, 小于l=mid+1
81. 搜索旋转排序数组 II相比于33题有可能出现重复元素。就要把最后的和开头相同的元素删掉。注意不要删空了，长度为1的情况要特判一下。
153. 寻找旋转排序数组中的最小值这个数组前半部分具有二分性质，都大于等于nums【0】。如果最初最后元素就比第一个元素大，那说明没旋转，直接返回第一个元素就好。
154. 寻找旋转排序数组中的最小值 II主要是最后几个数字可能和第一个数相同，把这几个数字全都跳过就好。有一个很神奇的东西，在acwing n成为-1之后数组越界是没问题的。在leetcode就需要特判一下。
162. 寻找峰值首先peak是一定存在的。所以如果num【mid】》num【mid+1】。则peak一定在【l，mid】之间
275. H指数 II反转之后，小于h指数的部分有二分性质：cit[m] >= m。不过有一些边界情况。最后返回的时候要特判一下。
278. 第一个错误的版本二分
374. 猜数字大小标准二分
378. 有序矩阵中第K小的元素第k个数肯定在最大值最小值范围之内，就在这个范围二分。对于一个mid，如果小于等于mid的数小于k个，l=mid+1, 否则r=mid。计算个数的时候，枚举每一行，从右上角开始，向右找到第一个小于等于mid的数。加上j+1之后搜索下一行。复杂度是 O((m+n)log k)
395. 至少有K个重复字符的最长子串没想到这是二分题目。从l到r。先计算这段每个字母出现次数。让mid从l开始往r走。条件是cnt[s[mid]] >= k。如果mid走到了r说明这一段都ok。否则就计算（l, mid）(mid + 1, r)这两段，取最大值。

位运算

题目名称题目简述
50. Pow(x, n)注意指数的符号，以及溢出的问题。
136. 只出现一次的数字进店简单位运算
137. 只出现一次的数字 II经典位运算，有基于状态机的解法，但是实在是没记住。这种按位统计的算法比较直观。
190. 颠倒二进制位位运算
191. 位1的个数位运算
201. 数字范围按位与这道题比较trick。其实我也不是很理解
231. 2的幂2的幂只有一个1
260. 只出现一次的数字 III这两个不同的数肯定有一位是不同的，把所有数异或之后，剩下的就是这两个数的异或结果，使用lowbit得到最低一位。用这一位将所有数据分成两堆，然后分别异或就可以得到最终结果。
289. 生命游戏原地操作可以使用第二位保存新的状态。
318. 最大单词长度乘积可以用位运算得到每个单词中有哪些单词。没有重复就是 & 为0。
371. 两整数之和a^b是不进位加法和。a&b << 1是加法后的进位。将两部分不断相加，直至进位全都加完即可。

mergesort

题目名称题目简述
88. 合并两个有序数组就merge呗
315. 计算右侧小于当前元素的个数这道题真的不错，计算每个位置的逆序对个数。记得不要重复申请释放内存，很慢的，比如tmp我放在merge里面每次申请就会卡地超时。
327. 区间和的个数这道题着实有点难，首先求前缀和就很难想到。然后对前缀和mergesort，求nums[r] - nums[l] 在 [lower, higher]区间内的数量，也不好想。

quicksort

题目名称题目简述
215. 数组中的第K个最大元素经典题目。我背的模板求的j是相对于l的第j个元素。l和j之间有（j-l+1）个元素。如果（j-l+1）> k。则在左边继续找第k个元素kth(l, j, k)。否则在左边找第k-(j-i+1)个元素，kth(j+1, r, k-(j-l+1))。
324. 摆动排序 II有几个注意点，1 如果元素是奇数个，则m=n/2+1。因为需要严格大于，小于。所以，要把小于mid放在前面，等于mid放在中间，大于mid放在最后。然后前m个和后n-m个逆序，再把两部分合并（这是因为reverse之后中间相同的数字就会距离很远，就不会相邻了）。

排序

题目名称题目简述
217. 存在重复元素数字范围没说，只能排序或者用哈希表

桶排序

题目名称题目简述
164. 最大间距基于桶排序的算法，根据最大值最小值确定桶大小，再根据桶大小确定桶的个数，把所有元素映射到几个桶之间。每个桶要记录最大值和最小值。最终结果就在前一个桶的最大值和现在桶的最小值之间。
220. 存在重复元素 III哈希表保存最近的k个元素。然后把所有数据映射到宽度为t的桶之中。如果两个数据大小之差小于等于t。那么他们一定在同一个桶或者相邻的桶。

KMP

题目名称题目简述
214. 最短回文串直观来想，在字符串之前加字母只能和字符串后面几个字母匹配。前面的对称部分不用管。前面对称部分的长度可以用kmp算。把串翻转再拼到后面，求一下next，next最后一个数据就是前面对称部分的长度。

数据结构

单链表

题目名称题目简述
19. 删除链表的倒数第N个节点-还行数据保证有效。因为有可能删掉头指针，所以建立虚拟头节点。然后一个指针从虚拟头节点先走n步，另一个指针同时走到底，这样第二个指针就指向倒数n个节点的前一个，直接删除就行。
21. 合并两个有序链表-水merge就行
23. 合并K个排序链表-挺好创建一个小顶堆，把k个链表的头节点值和指针都放进去。以值为键。每次merge堆顶的元素就行。头条面试问过这道题啊
24. 两两交换链表中的节点-不错第一个节点也要交换，所以要建立一个虚拟头节点。pre指向两两每对的前一个，起初就指向虚拟头节点。需要pre->next, pre->next->next都存在才能交换。p=pre->next, next = pre->next->next。交换就是：pre->next=next; p->next=next->next; next->next = p; pre=p;但是momanta问过这道题啊，然后我没搞明白。这种题目就是要多画一画。
25. K 个一组翻转链表-挺好也要建立一个头节点。然后往后走k步，把记录一下头尾节点和next，把tail->next=null，调用reverse(head)把这一段翻转。这时候记录的head就到了最后，head->next指向记录的next
61. 旋转链表首先计算链表长度。然后快慢指针。快指针先走k步，然后慢指针开始走，两个指针走到底的时候，把前后两段交换一下。
86. 分隔链表用两个链表分别保存，最后保存就好。
92. 反转链表 II这是一道全考指针运算的题目。先建立虚拟头节点。然后走m-1到第m个节点前一个。断开后，把后面m-n个节点翻转一下。然后和这一段前后连接在一起。
138. 复制带随机指针的链表挺好的题目。先在每个节点后面都复制一个。然后把random指针全都连好。最后把新建的节点全都拿出来。
141. 环形链表快慢指针看会不会相遇。
142. 环形链表 II快慢指针。慢指针走了t步，快指针走了2t步。假设相遇点为c，入口点为e。则
143. 重排链表找到中点，逆转后半个链表。然后交替merge就可以了。比较考察代码能力
144. 二叉树的前序遍历前序遍历比较简单，压入栈中，弹出后遍历，然后左右按顺序入栈。
45. 二叉树的后序遍历用两个栈，so easy
147. 对链表进行插入排序思路很简单，遍历每个数据，然后在排好序的数据中找到合适的位置（大于等于数据的前一个位置）把数据插入。
148. 排序链表ologn，还要常数空间。就是用迭代的mergesort。思路就是从长度为1开始归并，每次长度变大一倍。要记录的指针比较多。每次切割出两个长度为len的链表，然后合并。把结果和前面merge好的接在一起，再继续取。知道len为n为止。
160. 相交链表算长度，快指针多走几步，然后两个一起走，走到相遇就好。
203. 移除链表元素建立一个虚拟头节点处
206. 反转链表经典题目
234. 回文链表找到中点，把后半部分逆转（如果节点个数是奇数，要再往后走一个节点）。然后对比两个链表是不是一模一样。
237. 删除链表中的节点交换数据，删除节点
328. 奇偶链表遍历模拟题

并查集

题目名称题目简述
leetcode5309. 连通网络的操作次数-中并查集算连通域个数，看看剩下的边可不可以把几个连通域连接起来即可

树

题目名称题目简述
祖父节点值为偶数的节点和-中dfs记录的时候记录父亲和祖父的值即可。没啥意思
94. 二叉树的中序遍历中序遍历最开始都是输出最左边的节点。所以每个节点都要先沿左边走到底。然后栈pop，把结果放入队列中。最后尝试往右边走。
95. 不同的二叉搜索树 II如果要建立1—n的子树。则根节点可以是1—n的任意一个。所以就遍历每个分界点。然后递归生成左右两边所有子树。然后遍历左右所有子树，和根节点连在一起。如果l==r。就返回一个节点。这个过程中会有重复，记录一下中间结果。
96. 不同的二叉搜索树这道题其实是卡特兰数。遍历每个根节点。f(i)=f(j-1)*f(i-j)
98. 验证二叉搜索树二叉搜索树是有序的。左边子树的数值都小于等于树根。右边子树都大于等于树根。所以记录一下范围，如果越过了范围，就说明不是搜索树。
99. 恢复二叉搜索树搜索树的中序遍历结果是有序的。所以就在中序遍历的过程中，记录出现逆序对的两个节点。pre->val > cur->val。记录两个结点之后，最后交换一下就好。
100. 相同的树比较简单。递归判断左右两边就好。
101. 对称二叉树相当于上一道题的延伸。两棵树是相同的，就说明这棵树和自己是一棵树，并且左右子树是相同的树。
102. 二叉树的层次遍历记录每一层的个数
103. 二叉树的锯齿形层次遍历reverse一下就好，这样最简单。用双端队列太麻烦了，push的时候也要改变方向。
104. 二叉树的最大深度easy
105. 从前序与中序遍历序列构造二叉树这个答案着实有点精妙。先序肯定是从前往后走的。所以只需要根据先序第一个元素找到中序的位置，然后递归构建左右子树就好。
106. 从中序与后序遍历序列构造二叉树和前序一样。只不过后序指针从后往前走就好。
107. 二叉树的层次遍历 IIeasy
108. 将有序数组转换为二叉搜索树取中点做根，递归处理左右节点。
109. 有序链表转换二叉搜索树就是要额外写一个找中点的函数。
110. 平衡二叉树求高度过程中如果发现高度差大于1，就不是平衡的
111. 二叉树的最小深度这道题主要关注一下边界情况。如果只有一边是空，则这空的这半边不算的。
112. 路径总和到叶节点的时候判断一下sum是不是空就好1
113. 路径总和 IIdfs的时候记录一下路径的数值就好
114. 二叉树展开为链表-好这道题还是很精妙的。要把所有节点都连到right这边。可以分多步考虑。首先把右边摘下来。把左边放到右边。然后把右边放在原来左边的最右下处。然后往右边走，直到所有左边都移到了右边。
116. 填充每个节点的下一个右侧节点指针这道题还是很巧妙的。根节点不用连接。使用根节点是可以把两个子节点连接在一起的。然后遍历这两个子节点，使用同样的方法把子节点所有的子节点全都连接在一起。（这道题是一棵完美二叉树）
117. 填充每个节点的下一个右侧节点指针 II这道题不是完美二叉树，但是依旧能用同样的方法解出来
124. 二叉树中的最大路径和最大路径肯定是左右两边在加上根节点。所以遍历所有节点，然后保留最大值就好。一侧的最值要和0取max。
125. 验证回文串这让我记住了两个函数，isalnum判断是不是字母和数字。tolower转换成小写字母
129. 求根到叶子节点数字之和dfs到根的时候把和加到总和就好。
199. 二叉树的右视图又是一道层次遍历
222. 完全二叉树的节点个数完全二叉树的节点数量是确定的，所以可以二分最后一层节点位置。
101. 翻转二叉树easy
235. 二叉搜索树的最近公共祖先因为这是二叉搜索树，所以比较简单，根据值就可以判断当前是不是父节点了。如果不是搜索树，就要搜索左右子树，看左右节点有没有p，q节点。再分情况。
236. 二叉树的最近公共祖先二叉搜索树就需要不断遍历子树，看子树有没有p，q。如果都有，说明当前就是父节点，否则，返回不空的左右就好。
257. 二叉树的所有路径dfs记录路径
297. 二叉树的序列化与反序列化stringstream真的好用啊
331. 验证二叉树的前序序列化valid = next()=="#"

排序树

题目名称题目简述
218. 天际线问题这种扫描线没做过。首先把左右区间全都放入multiset。为了区分左右断点，左端点用负数，key还是坐标。然后按顺序遍历每个端点。同时用multiset记录扫描到的高度。如果是左端点就把高度加入，如果是右端点，就把高度删掉。同时记录上一个点，如果最高高度不相同，就说明是转折点，更新last，并把记录结果。
230. 二叉搜索树中第K小的元素前序遍历过程中遍历到第k个的时候返回就好

栈

题目名称题目简述
20. 有效的括号-水栈顶比较一下左右括号匹不匹配就行
32. 最长有效括号-挺好栈低记录有效括号的前一个位置的坐标。初始为-1。如果遇到（就把坐标入栈。遇到）就出栈，如果一出栈栈空了就说明）不合法，再把当前左边入栈。否则合法，并且此时栈顶为上一个（或者栈低坐标。这一段长度为i-stk.top()。后面有一道周赛求合法的括号是那些。每次合法括号匹配的时候都把括号左右坐标记录下来。然后当成区间，合并区间，从连续区间里面找出最长的一段就行。到时候我面试就来这三道题目。
71. 简化路径用栈模拟。不得不说，stringstream真的好用。getline(ss, string, delimiter)这个函数特特别好用。用来分割字符串特别爽。
84. 柱状图中最大的矩形-挺好单调栈求出一个点左右第一个比他小的点的坐标。
85. 最大矩形-挺好同样单调栈。因为是矩形，情况太多不好算。所以就把每个点初始化成从这个点出发往右有几个1。然后调用84题算出这一列的最大矩形。O(nm)
150. 逆波兰表达式求值这是一个贪心的过程。注意栈里面第一个弹出来的是第二个操作数，后一个弹出来的是第一个操作数。如果是除法，要注意第二个操作数不为0。
155. 最小栈再维护一个最小栈存储相同位置最小数据
225. 用队列实现栈用栈实现队列有多种形式。
316. 去除重复字母字符c小于s1的尾字符，其尾字符在字符表中还有剩余，所以我们需要删除尾字符，同时标记尾字符为没有使用过

队列

题目名称题目简述
239. 滑动窗口最大值裸单调队列。如果不需要窗口的话，就是单调栈了

图

题目名称题目简述
207. 课程表拓扑排序
210. 课程表 II拓扑排序

Trie树

题目名称题目简述
208. 实现 Trie (前缀树)设置trienode，里面包含26个字母的指针，还有一个标记
211. 添加与搜索单词 - 数据结构设计Trie树
212. 单词搜索 II这道题有多个单词。所以就把所有单词放到Trie树中。然后在每个位置搜索一下。

线段树

题目名称题目简述
307. 区域和检索 - 数组可修改裸线段树

搜索

bfs

题目名称题目简述
获取你好友已观看的视频-中层次遍历，保留level层的数据即可
1306. 跳跃游戏 III每次都能往两个位置跳。最后看看0所在的位置有没有跳到就行（跳过去的那些位置要加到队列里）
17.电话号码的字母组合-还行每个按键都对应三个字母。每次往三个新的字母扩展一下就行
126. 单词接龙 II就是用bfs搜索，同时要记录图。双端bfs是一种优化策略，奈何实在是有点难写。
127. 单词接龙bfs的时候记录一下步数
133. 克隆图用哈希表记录一下原来的节点和新建的节点之间的映射关系。bfs遍历原来图的时候，根据映射关系把新建节点加入哈希表里记录的对应节点的neighbor列表中就好。
310. 最小高度树从最边缘的节点开始bfs，知道中间只剩1或2个元素的时候停止，这就是离边缘最近的根

dfs

题目名称题目简述
22. 括号生成dfs+剪枝。优先开括号个数要小于n，闭括号个数要小于开括号个数。如果满足这两个条件就能继续搜索。
36. 有效的数独-还行这道题目只是判断一下比较简单。数独、八皇后就记录好几个位置的映射关系。数独每块就是模三除三。n皇后反对角线对角线就是x+y和n+x-y。然后暴力搜索就行。
37. 解数独记录好映射就好。
39. 组合总和直接搜索。每个值都可以重复用。还要避免重复。避免重复就把数组排个序，然后递归dfs的时候记得从当前位置 i 出发。
40. 组合总和 II每个数字只能用一次。就从i+1开始dfs下一轮。因为有重复数字。所以每次枚举数字的时候都把重复数字跳过(要i>index)。
46. 全排列经典dfs
47. 全排列 II要去重，1排序使得相同数字在一起，2 如果前面一个数字和自己相同，并且前面的没有被占用。 说明如果自己选用了，和前面一模一样。所以要跳过重复
51. N皇后主要是对角线和反对角线的对应关系。x+y和n+x-y。然后一行一行搜索就行，每次遍历每一列，尝试放入看是不是解。
52. N皇后 II和上面没区别
60. 第k个排列dfs搜到第k的时候停止
77. 组合dfs，组合式枚举要去重，就记录一下现在dfs到了哪个位置。从这个位置开始继续dfs
216. 组合总和 IIIdfs，不能重复，顺序没关系，就记住一个index，下次搜索从index开始。
282. 给表达式添加运算符每次记录一个位置，pos，从pos开始遍历所有长度。把一段数字转化成数字。如果小于INT_MIN，就尝试添加三种操作符，这里如果pos是0，说明是第一个字符，就不需要添加操作符。因为x的优先级比较高，如果+后面有x，x就应该和上一个数据先结合，把相乘的结果加到当前数据上，即cur-prev+prev*num。
301. 删除无效的括号首先计算一下不合法的左右括号的个数，然后遍历整个序列，如果遇到括号，就尝试删掉，然后继续dfs。如果不合法的左右括号都删掉了，就看看是不是有效的括号序列。
332. 重新安排行程这道题比较骚的就是反向插入。用一个vector记录能到达的点，然后排序之后从小开始，每次要把小的pop掉。如果没有dest了，说明走到头了，就把改点放入结果中。返回的时候要把结果reverse一下
386. 字典序排数dfs每种情况。传入k，然后遍历从i=0—9， 遍历k*10+i。只要k小于等于n，就把k加入返回数组中。
399. 除法求值建立一个图g[a][b]. 表示a/b。对于一个请求c/d，就在图里找一遍c到d的路径。算路径距离的时候要用乘法。

flood fill

题目名称题目简述
130. 被围绕的区域先遍历一下所有边缘。在遍历所有节点就好

暴力

题目名称题目简述
1307. 口算难题-中暴力的时候要顺便计算左右量变的数量值，否则会超时
78. 子集使用二进制直接暴力所有可能即可
79. 单词搜索遍历每个字母，如果和首字母相同，就dfs一下。
90. 子集 II要去重。如果前一个字母和当前字母一样，并且前一个字母没选。那选择当前字母和选择前一个字母是一模一样的。选了当前字母的话就重复了。所以要跳过这种情况。
93. 复原IP地址最多也就12位，直接暴力所有结果。写dfs的话， 还挺麻烦的。
149. 直线上最多的点数这道题就是暴力搜索所有两个点，然后计算从这个点出发，所有斜率相同和同一位置的点的数量，记录最大值。所以重要的如何表示斜率。可以用dx，dy来表示。如果dx，dy有一个为0，就直接返回。否则求一下最小公约数，把两个数化简一下。
306. 累加数这道题更多的是字符串处理的细节以及大整数加法。前两个数只能暴力枚举，前两个数确定之后，后面的数就只用根据规则判断。

其他

题目名称题目简述
74. 搜索二维矩阵从左上或右下开始搜索就行。每次会少一行或一列。复杂度是O(n+m)

贪心

题目名称题目简述
45. 跳跃游戏 II
53. 最大子序和这道题，我是有点理解不了。如果和大于0就把当前数加到sum里。否则sum就等于当前数。
55. 跳跃游戏刚开始只能到1号位置。mxpos=1,往后遍历每个数字，如果mxpos >= i+1。就说明能到 i 这个位置，此时就能尝试更新mxpos=max(mxpos, i + 1 + nums[i])；
56. 合并区间记录区间端点st，ed。
57. 插入区间插入后用上面的代码
134. 加油站只要油的总和大于等于消耗，就肯定能走一圈。至于从那个店出发，如果油不够了，这一段肯定走不通。肯定要从下一站开始走。
135. 分发糖果这道题说是hard不太准确。首先每个人都至少分1个。然后先从前往后遍历，如果当前元素比前一个大，那当前元素肯定是前一个元素分的糖果数量加一。然后再从后往前遍历，如果当前元素比后一个元素大，f【cur】=max（f【cur】，f【cur+1】+1）
179. 最大数这道题是贪心的。a，b两个数，如果（a+b）大于（b+a），a就应该排在前面。这个比较关系是满足传递率和反对称性的。所以只要根据这个规则把数组排序就好。
330. 按要求补齐数组要拼成一个数，一定要有小于等于这个数。初始化能拼成的数为[1,1)，就是一个都没有，miss=1，如果一个数nums[i]<=miss, 说明miss这个数能拼成连续区间。即[1, nums[i] + miss)，然后看下一个数，nums[i]>miss,说明有缺失，要补充数字，补充的数字要尽量大并且要组成连续区间，所以就选择miss。这样就能拼成[1, miss+miss)里的所有数。
373. 查找和最小的K对数字最小的k对数，其和也是最小的。就遍历所有可能，把所有的和都存下来，排个序，取前k个就好。
402. 移掉K位数字扫描每个字母。如果字母比栈顶小，就pop栈顶。有几个coner case。如果栈是空，并且字母是0，不要入栈。如果扫描所有字母后k还没用完，就pop k 个。

动态规划

背包问题

题目名称题目简述
322. 零钱兑换完全背包，f(i, j) = min(f(i- 1, j), f(i, j - v)+w)。这里w为1
377. 组合总和 Ⅳ完全背包求方案数。因为顺序不同就算做不同组合。所以要先遍历体积，再遍历物品（这里我也不是很懂）。

编辑距离类型

题目名称题目简述
让字符串成为回文串的最少插入次数-良再区间左右两侧都可以插入，如果相同就无需操作。不相同就看看插左边和插右边那边比较小。
10.正则表达式匹配经典dp问题，这道题*可以匹配前面的字母任意多次。所以如果跳过的话，也跳过字母和通配符
44. 通配符匹配经典问题,这道题*可以匹配任意字符串。所以可以匹配一个，或者跳过通配符。f(i, j)表示a的i后面和b的j后面是否匹配。
70. 爬楼梯f(i)表示走到 i 号楼梯可能的走法数目。f(i)=f(i-1) + f(i-2)
72. 编辑距离经典题目。f(i, j)所有将a[1-i]变成b[1-j]的操作方式中操作次数最少的操作。对于三种操作，删除：说明要把a[1，i-1]变成b[1，j],f(i-1, j)+1。增加一个字母，加的字母和b[j]相同，则a[1，i]和b[1，j-1]相同，f(i, j-1)+1。修改,a[i] 改为b[j]， 说明a[1，i-1]=b[1，j-1]，f(i-1, j-1)+1。当然如果a[i]=b[j]，则无需操作，f(i-1, j-1)。四种情况取min即可
115. 不同的子序列-不错f(i, j)表示t的前j个字母由s的前i个字母的子序列组成的个数。要组成t的前i个字母。可以只看最后一个字母。f(i, j - 1)表示s的前j-1个字母的子序列能组成t的前i个字母的个数。如果t[i-1]==s[j-1]，就可以加上f(i - 1, j -1)，就是说s的前j-1个字母只要可以组成t的前i-1个字母就ok，应为最后两个字母一样。
132. 分割回文串 II1，如何快速判断一段子串是不是回文的，f（i，j）表示s【i，j】这一段是不是回文的。长度为一的全是回文的，长度是2的也可以预处理一下。然后遍历i，j。如果i，j两个字母一样，并且f（i-1，j-1）为真，则f（i，j）也为真。g（i）表示前 i 个字母切割成回文串的最小花费。如果f（0，i）为真，则g（i）为0。否则将g（i）初始化为 i ，这肯定是正确的。然后 j 遍历每一个位置，如果【j， i】这段是回文的，就更新g（i）=max（g（i）， g（j - 1）+1）。
139. 单词拆分f（i）表示前i个字母可不可以被表示出来。更新f（i）的时候，就遍历所有j=【0， i】。如果f（j）为真，并且【j，i】存在于单词列表中，f（i）就为真。
140. 单词拆分 II记录一下每个状态是由哪个状态转移过来的，最后反推一遍就好。

各种子序列问题

题目名称题目简述
300. 最长上升子序列n^2的定义是：f(i)为nums[i]结尾的最长长度。nlong的定义是，f(i)为长度为i的序列结尾最小元素是多少。
368. 最大整除子集这道题的主要问题是如何判断一个子集是可以整除的。首先将数组排序，如果有a[i] < a[j]，并且a[i]能够整除a[j]。并且整除关系是可以传递的a[i] 整除 a[j], a[j] 整除 a[k]。则a[i]也可以整除a[k]。所以和300题一样。如果a[i]整除a[j], f[j] = f[i] + 1。不过这里要记录一下方案。用prev记录f[j]是从前面哪个数跳过来的。

状态转移类型

题目名称题目简述
leetcode5310. 二指输入的的最小距离-好f(i, a, b)表示按了前i个字母，并且第一根手指在a，第二根手指在b的所有按法中距离最短的那种按法的距离之和。O(n^3)
91. 解码方法f(i)表示到 i 这个字母最多有多少种转移方法。f(i)可以由f(i-1),f(i-2)转移过来。前者的条件是上一个字母不为0，后一个的条件是前两个字母符合条件。
97. 交错字符串f(i,j)就表示s3的 i+j 个字母是由s1的前 i 个字母和s2的前 j 个字母组成的。所以由两种情况s3[i+j] 和 s1[i] 相同，这种情况只需要 f(i - 1, j) 是true就可以。或者s3[i-j] == s2[j]。这种情况 f(i, j - 1) 为true。
121. 买卖股票的最佳时机这道题是比较经典的状态转移题目。有两种状态：有股票=1，无股票=0。f(i, k)表示到了第i天，手中有（k=1）无（k=0）时最多的钱数。f(i, 0) = max(f(i-1, 0), f(i-1, 1) + w[i])。f(i,1)=max(f(i-1, 1), -w[i])。最终结果是f(n, 0)。初始化的时候f(0, 0)=0, f(0, 1)=-w[i]。
122. 买卖股票的最佳时机 II和上面一道题的差别是，这道题可以多次交易。所以f(i, 1)=max(f(i-1, 1), f(i-1, 0)-w[i])。其他都不变。也可以把空间优化成常数的。
123. 买卖股票的最佳时机 III这道题说可以交易两次。f(i, k, 0/1)表示交易到第i天，交易了k次，手里有（1）无（0）股票时最大收益是多少。每次买入算作一次交易。f(i,k,0)=max(f(i - 1, k, 0), f(i-1, k - 1, 1) + w[i]), f(i, k, 1)=max(f(i - 1, k, 1), f(i - 1, k - 1, 0)-w[i])
152. 乘积最大子序列maxDP[i + 1] =max(maxDP[i] * A[i + 1], A[i + 1],minDP[i] * A[i + 1])minDP[i + 1] = min(minDP[i] * A[i + 1], A[i + 1], maxDP[i] * A[i + 1])，dp[i + 1] = max(dp[i], maxDP[i + 1])。其实只需要保存三个变量。mx，mn，ret。如果当前数值为负数，则大数字乘负数会变成小负数。
188. 买卖股票的最佳时机 IV这里面k就很有意思。如果k大于n/2。那相当于交易次数无限制。否则f（i，j，0/1）表示交易到第i天，交易了j次，有或无股票的时候的最大钱数。i，j是要遍历的。f(i,j,0) = max( f(i - 1, j, 0), f(i - 1, j, 1) + w[i]), f(i, j, 1)=max( f(i - 1, j, 1), f(i - 1, j - 1, 0) - w[i] ), 规定买入算一次交易结果是 f(n, k, 0)。
309. 最佳买卖股票时机含冷冻期f(i, 0)=max(f(i-1, 0), f(i-1, 1) + w[i]), f(i, 1)=max(f(i - 1, 1), i >= 2 ? f(i - 2, 0) : 0 - w[i])

数字三角形

题目名称题目简述
62. 不同路径dp(i,j)表示走到这个点的路径数量。dp(i,j) = dp(i - 1, j) + dp(i, j - 1)。dp(1,1)=1。
63. 不同路径 II有障碍的位置跳过就好
64. 最小路径和f(i,j)表示走到这个点的最短距离。f(i,j)=min(f(i - 1, j), f(i, j - 1)) + w[i][j]
118. 杨辉三角f(i, j) = f(i - 1, j) + f(i-1,j-1)。如果j0或ji，说明是第一个或最后一个，只加f(i-1,j)。
119. 杨辉三角 II这道题也是挺巧妙的。第k行有k+1个元素。首先把第一个元素设置为1。然后重复k次，每次从后往前f(i)+=f(i-1)。从后往前是为了避免前面已经更新过的结果。
120. 三角形最小路径和可以在原数组上直接求。注意一下边界情况和初始值就好。
174. 地下城游戏如果是负数-a，就要生命值至少是a才能走进这个格子。f（i，j）表示从（i，j）走到目的地需要的最小生命值。f（i，j）=min（f（i+1，j），f（i，j+1））-w（i，j）和0 取max。当然边界情况取不到的时候就不要取了。
221. 最大正方形如果一个点为1，则以这个点结束的正方形的变长为max(f(i - 1, j), f(i, j - 1), f(i - 1, j - 1)) + 1。

线性简单dp

题目名称题目简述
198. 打家劫舍f(i)表示到i这一点最大收益。f(i)=max(f(i - 1), f(i - 2) + w[i])
213. 打家劫舍 II围成了一个圈之后，首尾两个元素不能一起选到。所以就是nums[0, len - 1], nums[1, len]用198算两个结果，取最大值就好
279. 完全平方数f(i)表示用平方数组成i这个数最小的个数。f(i)=min(f(i), f(i - j * j) + 1), i - j * j > 0;
338. 比特位计数f(i)表示i这个数有多少个1。f(i) = f(i >> 1) + i & 1.
343. 整数拆分f(i)表示i这个数最大是多少。i可以分成两部分，j 和 i - j。 f(i) = max ( f(i), max ( f(j), j) * (i - j) )
376. 摆动序列up表示到目前为止，最后一步向上走的序列长度，down表示到目前为止，最后一步向下走的序列长度。up = max(up, down + 1), down = max(down, up + 1)。要求分别是a[i] > a[i - 1] 和 a[i] < a[i - 1]

数形dp

题目名称题目简述
337. 打家劫舍 IIIf(i, j)表示i这个点，抢(1)或不抢(0)的最大值。f(i, 0) = sum(max(f(c, 0), f(c, 1))), f(i, 1) = i.v + sum( f(c, 0) )

记忆化搜索

题目名称题目简述
241. 为运算表达式设计优先级表达式所有加括号的可能。如果搜到了运算符，就递归运算左右两边。然后遍历两边结果，根据运算符把结果加到返回数组中。
312. 戳气球区间dp，f(i,j)表示戳 i，j 这几个气球得到的最大分数。为了避免边界问题，在首尾加上一个1。f(i, j) = max(f(i,j), f(i, k - 1) + nums[i - 1] * nums[k] * nums[j + 1] + f(k + 1, j))
329. 矩阵中的最长递增路径这道题dp顺序不好确定，但每个点序列长度是一样的，所以就遍历每个节点，最后记录一下节点的序列长度就好。
375. 猜数字大小 II这道题说的是至少多少，所以f(i,j)表示猜出i-j范围内的数的最小话费。f(i,j) = f(i, k - 1) + k + f(k + 1, j)。枚举所有k，然后记录最小值就好。
403. 青蛙过河这道题有点递推的感觉。开始只能走1步。如果上一步走了k步，下一步就可以走k-1， k, k + 1步。所以记录没给点能由哪些步数走到。对于每个步数k，遍历k-1, k, k + 1。并把步数加到相应的位置。最后查看最后一个位置能不能走到就好。

模拟题

题目名称题目简述
解压缩编码列表-水水题
1309. 解码字母到整数映射-水注意从后往前模拟，这样不会有歧义
5307. 将整数转换为两个无零整数的和-水直接暴力
5308. 或运算的最小翻转次数-水一位一位算
6. Z 字形变换建立n个数组，然后一行一行模拟。先往下走，如果走到头了，就转换方向就好。这道题还比较有意思
7.整数反转比较水
8.字符串转整数这道题主要就是记录符号。然后累加数字的时候要注意会不会超过范围。如果是正数，num>INT_MAX/10
9.回文数转换成字符串或者把每一位都抠出来都行
12.整数转罗马数字也是贪心的做。罗马数字从大到小排列。注意900，400，90，40，9，4这种数字是对应两个罗马字母的。
13.罗马数字转整数和上面一道题相反，这道题也是贪心地做，不过每次从开头先贪心地找有没有连个罗马字母，没有的话再去找一个罗马数字
14.最长公共前缀多个字符串地最长公共前缀。也没啥好办法，就是一位一位地尝试。
29. 两数相除用减法模拟除法的过程。为了优化速度。每次都倍增，加的i也倍增。如果比被除数大了，就让除数变为最初的除数
31. 下一个排列-挺好这道题得好好观察。要求下一个比较大的排列。3 2 1这种全降序的是没有比他大的排列的。所以要从后往前找到第一个正序对 1 【2 5】4 3。【2，5】就是一个正序对。正序对的第一个和最后一个字母交换得到1 3 5 4 2。2变成了3肯定是变大的。后面的全是降序的，然后把正序对第二个靠后的部分全都翻转一下就得到了结果: 1 3 2 4 5。如果没有正序对，就把整个串翻转一下。
38. 外观数列，一般循环n次，根据题目模拟。
41. 缺失的第一个正数这道题首先一共有n个数，如果缺失的正数在1~n之中。那么根据抽屉原理，这个数组里面一定有数字在1—n这个范围外。则数值1—n之间的数换到坐标1—n之间之后。一定会有一个位置，数值和坐标不一样。（因为数值是1—n的，坐标是0—n-1的，所以数值都要减1）。
42. 接雨水这道题记录每个点左右最高的柱子就行。记录一边最高的柱子，只需要记录一下最大值就行。
43. 字符串相乘主要是模拟。a是n位，b是m位。那么成绩就是n+m位。a的第i位和b的第j位相乘之后，其实结果是ret的第i+j+1位。进位在i+j位（应为高位在前)。所以每次tmp=a[i] * b[j] + ret[i + j + 1]。ret[i+j+1] = tmp % 10, ret[i+j] += tmp / 10;
48. 旋转图像这道题是正方形，还比较简单，每次交换四个点的位置就行。
49. 字母异位词分组这道题比较简单。配个单词排序或者记录一下字母数量就行。排序是最简单的。
54. 螺旋矩阵经典题目，记录好边界和访问过的位置。每次一个方向走到头就换个方向。
58. 最后一个单词的长度找到最后一个不为空格的字符， 在从这里开始找第一个空格
59. 螺旋矩阵 II和54题差不多
66. 加一翻转一下会比较方便
67. 二进制求和同样reverse一下比较方便
73. 矩阵置零遇到0就把行列都标记成一个负数，最后全都改成0
75. 颜色分类遍历了两遍
80. 删除排序数组中的重复项 II记录一下出现次数就好
83. 删除排序链表中的重复元素模拟题，如果当前数值和下一个数值相同，就删除下一个节点
87. 扰乱字符串-有点难这道题也不知道是啥算法。两个字符串首先排序之后要相等。有两种情况。1.a[0,i] = b[0,i], a[i, n]=b[i,n]。或者a[0,i] = b[n-i, n], a[n-i, n]=b[0, i]。枚举每个分界点，然后递归处理这两种情况就行。
89. 格雷编码这个，比较套路
128. 最长连续序列先把所有数据放入set中。遍历每个数，如果没有比这个数小1的数，就一直找比他大1的数。统计连续数列的长度。内层虽然有一个while循环，但是内层while循环总数不会超过n次。所以也是O(N)的算法
163. 缺失的区间就是使用nums里面的数切割lower到upper这个区间。注意会溢出
165. 比较版本号一个一个比较，如果相等要设置为0。
166. 分数到小数这道题主要是模拟除法。并且记录商在结果的什么位置。如果商重复了，说明循环了，在记录的位置处加上括号，最后也加上闭括号，直接返回。
169. 多数元素经典题目
171. Excel表列序号26进制转10进制
189. 旋转数组三次旋转
202. 快乐数这是一道模拟题。中间产生的数字全都记录一下，如果出现重复了，就说明出现重复了，直接返回false
205. 同构字符串把两个字符串全都映射成从1开始的字符串。然后对比s和t是不是相同就好
238. 除自身以外数组的乘积-挺好如果能用除法就很简单了。不让用除法，就来两边，第一次从左到右，ret[i] = mul(a[0, i - 1])。第二次从右到左,ret[i] *= mul(a[i + 1, n]).
242. 有效的字母异位词排序看看是不是一样的就好
258. 各位相加O(n)的算法
263. 丑数查看一个数是不是只有2，3，5这三个因子
264. 丑数 II有点想三路归并，不过三个序列是相同的。i2,i3,i5指向2，3，5包含这三个因子的最小的数。每次用i2,i3,i5指向的数和2,3,5生成最小的数，下一个最小的数肯定从这三个数里面产生，如果产生了，则对应的指针++。
273. 整数转换英文表示要抓住几个关键点，分别是20，100，1000，一百万，一个亿。一百一下的要特殊处理。二十一下的也要特殊处理。如果等于0就直接返回，如果小于20就返回对应单词，如果小于100就返回对应单词，各位数递归处理。否则，从大到小处理，数字除以关键点的商递归处理，然后加上关键点的单词。剩下的数据递归处理。
290. 单词规律模拟题，可以用map记录字母和单词的对应关系
299. 猜数字游戏模拟题
313. 超级丑数题目给了很多个质数，所以只好用小顶堆（要重载 > ）把所有质数放入堆中，每次取堆顶元素（堆顶可能有多个相同），然后把新的值再加入堆中就好。
334. 递增的三元子序列用两个变量记录最小的两个元素，如果有一个数比次小元素都大，说明有递增三元组
335. 路径交叉这道题着实有点鬼畜
336. 回文对这道题还挺好的。首先把所有字符串都reverse并加入map中。然后遍历所有单词，将单词分为left+right两部分，如果right是回文的，reverse(left)存在，并且reverse(left)的序列号不是当前单词就说明是一个回文对。corner cases是“”，如果有“”，上面的算法只能处理 回文+“”的情况，不能处理 “”+回文的情况。后面这种情况要单独处理。
345. 反转字符串中的元音字母先把元音字母拿出来，再逆序放回去
385. 迷你语法分析器对于每种情况分别考虑。【就新建一个对象，放入栈顶。】拿出栈顶元素，如果有数字就把数字加入，如果栈空了就直接返回，否则把当前对象加到栈顶里面。如果是，把数字加入栈顶。如果是数字就用tmp记录一下。
388. 文件的最长绝对路径这道题比较方便的是制表符就是文件的层次。所以先用换行符切割，然后计算制表符个数。用一个栈记录之前所有文件夹的长度。如果栈的size大于制表符个数了，就要pop。然后记录当前的长度。如果当前字符串有.就说明是一个文件了，就尝试更新长度。记住一个方法 getline(stringstream, string, delimiter(char)).
391. 完美矩形遍历所有矩形。并遍历每个点。如果某个点出现过，就删除。同时统计所有小矩形的面积。最后看看是不是只剩4个点。并且四个点组成的面积和统计的小矩形的面积一样
394. 字符串解码需要记录重复次数和字符串。用栈记录（replica，str）。如果扫描到数字，就加到replica中。【就使用replica加入新建node，加入栈顶。】pop出栈顶，重复replica次字符串，如果此时栈为空，就把结果加到ret中，否则把结果放入栈顶字符串。如果是字符串。如果此时栈空，就直接加到ret中，否则加到栈顶字符串。
401. 二进制手表遍历所有情况，保留数字个数相同的情况。

博弈论

题目名称题目简述
292. Nim 游戏1,2,3是必赢局面。4是比输局面。所以只要%4不为0，就是必赢局面。

设计题目

题目名称题目简述
146. LRU缓存机制这道题很不错。数据考虑放在可以O（1）修改的数据结构里。数据就放在list中。至于key对应的数据在list的什么地方，就用一个map存储。get的时候，从map里找一下有没有这个数据，如果有就用迭代器返回数据，并使用emplace_front把当前数据O（1）的放到最前面。put的时候，在map里找一下数据，找到了就更新数据，并放到list最前面。没找到，如果已经满了，就删除list最后的数据，然后把数据放入list头部。
170. 两数之和 III - 数据结构设计哈希表存储所有数据。find的时候最坏会遍历整个哈希表。
173. 二叉搜索树迭代器暴力做法就是直接遍历一遍。（因为next要常数时间，还没有fathre指针）
223. 矩形面积算出上下左右的边界，然后用两个面积减去重叠的面积。
224. 基本计算器这道题有括号。遇到（就先把结果和符号压入栈中。如果遇到）就先把临时结果加到结果中，然后再乘栈中的符号，再加上栈中的结果。
227. 基本计算器 II这道题只有加减乘除。乘除优先级比加减高。所以记录上一个数字last。如果是乘除，n = last * n or last / n。因为优先级比较高。所以要ans要减去之前的数据last，然后再加上新结果n。ans=ans - last + n
232. 用栈实现队列用两个栈模拟，一个进，一个出。
284. 顶端迭代器用一个队列缓存peek的数据
287. 寻找重复数可以排序，或者根据鸽笼原理原地交换
341. 扁平化嵌套列表迭代器这道题还挺巧妙。主要就是要记录每个list的begin和end迭代器。hasNext是关键。这个函数要把begin的迭代器指向第一个数字。如果begins和ends两个栈top相同，说明一个list走到头了。就pop掉。如果begins的top不是数字，说明是列表，把当前栈顶移向下一个位置，同时把列表的begin和end押入栈中。
380. 常数时间插入、删除和获取随机元素删除元素的时候，把元素和vector最后一个数字交换，然后pop_back。
381. O(1) 时间插入、删除和获取随机元素 - 允许重复记录数组坐标的时候记录多个就好，删除的时候随便删一个

数学推公式

题目名称题目简述
172. 阶乘后的零阶乘的那些数字里，一对因子2和5就会产生一个0。因子2的数量肯定比因子5的数量多。所以只需要算5的数量。5每5个出现一次。25每25出现一次。
204. 计数质数线性筛质数。
233. 数字 1 的个数数位统计，一位一位算就好
268. 缺失数字所有数都知道，就求个和，然后把有的数减去，剩下的就是少的那个数据。
319. 灯泡开关最后结果是开方。。有点扯
321. 拼接最大数从a中挑选k个，b中挑选n-k个。a中的k个一定是a里面最大的k个数。然后挑选出来的数组成一个新的数字，保留最大的一个。没有所有可能的k就好。
326. 3的幂是否只有3这个因子
342. 4的幂是否只有4这个因子
357. 计算各个位数不同的数字个数可以一位一位算。一位数有A(9,1)中选择。两位数有A(9,2)+A(9,1)中选择。i位数有A(9,i) + (i-1)A(9, i -1)。A(9,i)中没有考虑有0的情况。(i-1)A(9, i - 1)中考虑了有0的情况（0也不能重复，所以只需考虑一个0的情况）。
367. 有效的完全平方数i*i <= num, 或者i <= num / i 。后面一种请款不会爆int，但是要判0。
372. 超级次方a^(abc) = a(100a)a(10b)a©。
382. 链表随机节点蓄水池抽样（原理不太懂）。让 cnt 递增。如果rand() % cnt == 0就取当前的数。
384. 打乱数组洗牌算法，遍历每个数，尝试交换当前数和后面某个数。后面数字的 index=i + (rand() % (n - i))
396. 旋转函数f(0)=0A0 + 1A1 + (n-1)An-1. f(1) = 0An-1 + 1A0 + … + (n - 1)An-2. f(i) = f(i - 1) + sum - n A[n - i]
397. 整数替换欧树的时候直接移为。奇数的时候，如果减1后的1比加一后的1多，就减一（n=3的时候也减一，这是特例。。）
398. 随机数索引蓄水池抽样，遍历一遍所有数字。用cnt记录遇到target的个数。每次j=rand()/cnt, 如果j等于0，就选取这个坐标。这保证每个target遇到的概率最后都是1/cnt
400. 第N个数字先算有几位，1位有9个。两位有90个。。。。算出有几位之后，再算是什么数。（n-1）/ len，就是剩下的数除以位数。然后在数的第(n-1)%len就是结果。
声明：本文内容由网友自发贡献，不代表【wpsshop博客】立场，版权归原作者所有，本站不承担相应法律责任。如您发现有侵权的内容，请联系我们。转载请注明出处：https://www.wpsshop.cn/w/小丑西瓜9/article/detail/93673
推荐阅读
相关标签

Copyright © 2003-2013 www.wpsshop.cn 版权所有，并保留所有权利。

  

闽ICP备14008679号