当前位置:   article > 正文

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

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
推荐阅读
相关标签
  

闽ICP备14008679号