- 博客(1164)
- 资源 (2)
- 收藏
- 关注
RSS订阅原创 力扣 384. 打乱数组 随机洗牌算法
https://leetcode-cn.com/problems/shuffle-an-array/思路：随机洗牌算法可以等概率的打乱输入，简单介绍一下经典洗牌算法Knuth−ShuffleKnuth-ShuffleKnuth−Shuffle。它的思路就是逐次遍历数组的每一位，对于第iii位，随机选取0<=j<=i0<=j<=i0<=j<=i，并交换ai、aja_i、a_jai、aj。下面从数学角度上解释一下为什么这个算法是等概率的：对于第iii个元素，其最终位置
2022-03-19 01:36:55
509
原创 力扣 1218. 最长定差子序列 哈希 dp
https://leetcode-cn.com/problems/longest-arithmetic-subsequence-of-given-difference/思路：其实和最长上升子序列是很像的，考虑dpidp_idpi表示以aia_iai结尾的最长等差子序列的长度，那么当j<ij<ij<i且aj=ai+da_j=a_i+daj=ai+d时有dpi=max(dpi,dpj+1)dp_i=max(dp_i,dp_j+1)dpi=max(dpi,dpj+1)，但是这样
2021-11-06 02:09:45
262
原创 力扣 240. 搜索二维矩阵 II 二分
https://leetcode-cn.com/problems/search-a-2d-matrix-ii/思路：做法太多了，最简单的暴力，复杂度O(nm)O(nm)O(nm)，或者依次考虑每行/每列，然后二分判断，复杂度O(nlgm)O(nlgm)O(nlgm)或者O(mlgn)O(mlgn)O(mlgn)。这里就说一下最巧妙的O(n+m)O(n+m)O(n+m)的做法，考虑以矩形右上角为起始点，那么我们可以比较matrixx,ymatrix_{x,y}matrixx,y与targettarget
2021-10-26 23:52:56
289
原创 力扣 229. 求众数 II 思维
https://leetcode-cn.com/problems/majority-element-ii/思路：哈希解法就不多说了，没啥意思。说一下进阶的算法，其实之前做过类似的，不过是求出现超过n/2次的元素，核心思想就是成对消耗：每次选取2个不同的元素从数组中删去，那么最后剩下的元素就是可能的答案。证明略，显然这个结论在此题依然成立，那么直接模拟就行。看了官方题解才知道这是摩尔投票法。class Solution {public: vector<int> majorityEl
2021-10-23 01:51:25
711
原创 力扣 211. 添加与搜索单词 - 数据结构设计 字典树
https://leetcode-cn.com/problems/design-add-and-search-words-data-structure/思路：字典树经典题目。看数据范围，暴力比对的话大概率会超时。字典树就是前缀树，支持插入字符串、快速检索字符串 or 前缀是否出现过，当然它还有一些变体存在，比如01字典树等。详见我的这篇博客，此处就不多说了。字符 “.” 其实也挺好处理的，写个深搜嘛。class TireNode{public: array<TireNode*, 26&
2021-10-20 00:15:37
157
1
原创 高精度模板——C++实现
文章目录综述朴素想法压位模板综述最近闲来无事写了一个比较简单的高精度模板……想来之前没有总结过这一块的知识，就写一篇博客来简单记录一下吧。关于高精度模板的资料其实挺多的，有某个方法不是很理解的话可以再搜搜资料或者自己手动模拟一下。这个模板的效率肯定不是最好的，可能还会有隐藏的bug，仅给大家提供一种实现高精度的思路。朴素想法我们先从最简单的开始，如果让你实现一个正数的高精度加法，你会怎么做？大部分人的做法肯定是用数组或者链表来模拟这个过程，以数组为例，从低位到高位依次存储数字的每一位，那么加法无非就
2021-10-17 17:35:25
1382
1
原创 力扣 282. 给表达式添加运算符 dfs 回溯
https://leetcode-cn.com/problems/expression-add-operators/思路：很明显的回溯了吧。。考虑每个位置的运算符种类有三种以及数字可以连起来，那么相当于每个位置有四种选择，直接暴力计算时间复杂度为O(4n)O(4^{n})O(4n)，考虑nnn最大不过等于10，还是可以通过滴~需要注意的一个细节问题是，如果以位置iii为一个数的起始，且其为0，那么后续就不能再跟其他数字了！class Solution {public: vector<s
2021-10-17 00:45:14
151
原创 力扣 29. 两数相除 位运算 模拟
https://leetcode-cn.com/problems/divide-two-integers/思路：很无聊的题目……商肯定可以用二进制表示，那么我们就可以模拟这个过程来求。class Solution {public: int divide(int dividend, int divisor) { if(dividend==INT_MIN&&divisor==-1) return INT_MAX; if(di
2021-10-13 01:01:33
94
原创 力扣 187. 重复的DNA序列 哈希 位运算
https://leetcode-cn.com/problems/repeated-dna-sequences/思路一：非常直观的方法，逐一取长度为10的子串，通过哈希计数即可。复杂度O(NL)O(NL)O(NL)。class Solution {public: vector<string> findRepeatedDnaSequences(string s) { vector<string> ans; const int LEN=10
2021-10-09 01:20:04
132
原创 力扣 2025. 分割数组的最多方案数 前缀和+哈希
https://leetcode-cn.com/problems/maximum-number-of-ways-to-partition-an-array/思路：第一次在比赛中间干掉hardhardhard题，纪念一下。先计算出前缀和数组sumsumsum，并设整个数组的总和为tottottot，那么问题中的条件就等效于在前缀和数组中寻找sumi=tot−sumisum_i=tot-sum_{i}sumi=tot−sumi的iii的个数，也即sumi=tot/2sum_i=tot/2sumi=to
2021-10-04 23:18:51
147
原创 力扣 166. 分数到小数 模拟 哈希
https://leetcode-cn.com/problems/fraction-to-recurring-decimal/思路：模拟竖式除法即可，关键点在于如何区分有限小数和无限循环小数。其实就是看小数部分会不会出现循环节，在模拟的过程中，如果某个余数出现了多次，那么肯定就是无限循环小数喽。搞个哈希表记录一下位置即可。class Solution {public: using ll=long long; string fractionToDecimal(ll numerator,
2021-10-04 22:29:32
120
原创 python 可迭代对象、迭代器对象、生成器
迭代器 VS 可迭代对象为何在pythonpythonpython中可以很方便的使用forforfor循环来遍历列表、字符串甚至是文件？它的背后实现离不开迭代器和可迭代对象。首先来谈谈pypypy中的迭代器协议：实现内置函数iteriteriter，它返回一个迭代器对象。通过调用迭代器对象的nextnextnext函数，取得每次迭代的内容。多次调用nextnextnext函数后，抛出StopIterationStopIterationStopIteration异常（迭代终止）。可以猜测pyt
2021-09-28 15:21:57
171
原创 力扣 524. 通过删除字母匹配到字典里最长单词 dp
https://leetcode-cn.com/problems/longest-word-in-dictionary-through-deleting/思路：经典题目了，其实就是求满足题意的子序列嘛。直接预处理出dpi,jdp_{i,j}dpi,j数组，dpi,jdp_{i,j}dpi,j表示从第iii个位置开始第一个字符jjj所对应的位置，显然有：dpi,j={dpi,j=dpi+1,j, if si≠ jdpi,j=i,&nb
2021-09-15 01:47:14
96
原创 力扣 447. 回旋镖的数量 哈希 数学
https://leetcode-cn.com/problems/number-of-boomerangs/思路：考虑枚举点iii，如果我们知道其他所有点到点iii的距离，那么可以计算出每个距离对应的点对数量xxx，显然它对答案的贡献为x∗(x−1)x*(x-1)x∗(x−1)——从xxx个元素中有顺序的选出2个元素。通过哈希表可以把时间复杂度降低到O(n2)O(n^2)O(n2)。不过计数方式有很多种，也可以考虑在统计点对数量的时候计算。class Solution {public: in
2021-09-15 01:10:28
111
原创 力扣 678. 有效的括号字符串 贪心
https://leetcode-cn.com/problems/valid-parenthesis-string/思路：星号既可以匹配左括号也可以匹配右括号，由此可以记录从起始位置到当前位置的左括号的最大值和最小值，在更新过程中最大值不能低于0，且最小值不能小于0。当遍历完成后，最小值应该等于0。class Solution {public: bool checkValidString(string s) { int maxBrackets=0,minBrackets=0;
2021-09-15 00:52:22
148
原创 力扣 1994. 好子集的数目 数学 状压dp
https://leetcode-cn.com/problems/the-number-of-good-subsets/思路一：纯数学暴力解法。首先我们知道一个合数一定可以表示为若干个素数的乘积，因为要求素数不能相同，因此子集中的合数一定不能表示成两个相同素数的乘积。注意到元素的取值范围为[1,30][1,30][1,30]，据此我们可以排除一些合数。然后把相同的数合并到一起(记录出现的次数)，那么就只剩下大概20个元素了。此时可以暴力枚举选择的情况，然后对选择的数做因数分解统计每个质因子出现的次数，如
2021-09-09 00:52:57
195
原创 力扣 5865. 访问完所有房间的第一天 dp 前缀和优化
https://leetcode-cn.com/problems/first-day-where-you-have-been-in-all-the-rooms/思路：经典读错题+想歪。分析后不难发现，第一次到达房间iii，下一次必定要回到<=i<=i<=i的房间jjj(不妨把这个操作叫做回访)，且此时<i<i<i的房间都到达了偶数次，那么对于[j,i)[j,i)[j,i)的每个房间，我们都需要再次回访，如果用dpidp_idpi表示在位置iii进行回访操作后再重新回
2021-09-06 01:33:23
121
原创 力扣 470. 用 Rand7() 实现 Rand10() 思维
https://leetcode-cn.com/problems/implement-rand10-using-rand7/思路：有意思的题目。直接用加法、乘法、取模得到的结果是不对的，原因是通过运算得到的结果可能有多种组合形式，就拿加法而言，2=1+12=1+12=1+1，但是3=1+2=2+13=1+2=2+13=1+2=2+1，显然每个数字出现的概率是不一样的，当然我们可以使用出现概率相同的数字来计算，这样也可以保证正确性。不过还有一种更加简单的方法，我们认为每次随机取得的数都是独立的，那么经过两
2021-09-06 00:58:49
147
原创 力扣 5848. 树上的操作 dfs 模拟
https://leetcode-cn.com/problems/operations-on-tree/思路：无聊的模拟题。class LockingTree {public: LockingTree(vector<int>& vec) { parent=vec; int n=parent.size(); tree.resize(n); for(int i=1;i<n;i++)
2021-09-05 00:49:20
96
原创 力扣 528. 按权重随机选择 二分/堆
https://leetcode-cn.com/problems/random-pick-with-weight/思路一：随机+二分。首先独立计算出每个数被选中的概率，然后计算该数组的前缀和。那么aia_iai被选中的概率就等于sumi−sumi−1sum_i-sum_{i-1}sumi−sumi−1，且sum[0..n)=1sum[0..n)=1sum[0..n)=1。因此每次pickpickpick可以先计算一个[0,1][0,1][0,1]内的随机数，然后看它落到哪个元素的区间范围内，利用二
2021-09-02 00:54:34
127
原创 力扣 1109. 航班预订统计 差分
https://leetcode-cn.com/problems/corporate-flight-bookings/思路：最简单的想法，遍历每个区间修改座位数，那么总复杂度可能达到O(n2)O(n^2)O(n2)，大概率会超时。如果你学过线段树/树状数组的话，也可以用O(nlgn)O(nlgn)O(nlgn)的复杂度解决这个问题，就是一个区间修改和单点查询嘛。但是我们有更加巧妙的复杂度为O(n)O(n)O(n)的差分算法。假设最终所求数组为ansansans，我们可以计算其差分数组：diff0=a0,
2021-09-01 00:59:54
182
原创 力扣 789. 逃脱阻碍者 思维
https://leetcode-cn.com/problems/escape-the-ghosts/思路：一开始居然还傻乎乎的写了bfsbfsbfs，其实就是思维类题目。显然无论是你还是阻碍者，到达目标点的距离即二者之间的曼哈顿距离，那么只要有一个阻碍者到终点的距离<=<=<=你到终点的距离，一定不可能逃脱成功，否则可以逃脱成功。class Solution {public: using pr=pair<int,int>; int calDis(in
2021-08-29 02:01:02
95
原创 力扣 787. K 站中转内最便宜的航班 dp
https://leetcode-cn.com/problems/cheapest-flights-within-k-stops/思路：经典dpdpdp题想歪wa半天。考虑dpi,jdp_{i,j}dpi,j表示经过iii条边后到达点jjj的最便宜的价格。显然有dp0,src=0dp_{0,src}=0dp0,src=0，最终答案就是mini,dstmin_{i,dst}mini,dst，其中0<=i<=k+10<=i<=k+10<=i<=k+1。怎么转移呢？其
2021-08-27 02:14:47
111
原创 力扣 797. 所有可能的路径 dfs 回溯
https://leetcode-cn.com/problems/all-paths-from-source-to-target/思路：dfsdfsdfs回溯即可，感觉没什么好说的。因为是有向无环图，所以在一次dfsdfsdfs过程中不可能访问到已经访问过的节点，不需要引入额外的标记数组。class Solution {public: vector<vector<int>> allPathsSourceTarget(vector<vector<int>
2021-08-27 01:28:39
126
原创 力扣 881. 救生艇 贪心 双指针
https://leetcode-cn.com/problems/boats-to-save-people/思路：贪心，我们从体重低的开始考虑，因为一艘船最多可以坐两个人，因此体重低的人应该尽可能的带一个体重最大的人，如果不满足重量限制，那么只能让体重最大的人单独一艘船了。class Solution {public: int numRescueBoats(vector<int>& people, int limit) { sort(people.begi
2021-08-27 01:21:29
106
原创 力扣 5836. 到达目的地的方案数 dijkstra+dp
https://leetcode-cn.com/problems/number-of-ways-to-arrive-at-destination/思路：可恶啊，没开longlong WAlonglong\ WAlonglong WA了几发。题目是求从起点到终点的最短路径的方案数，考虑在求最短路的过程中dpdpdp，用dpidp_idpi表示从起点到点iii的最短路径的方案数，由于此题中起点固定为0，因此可以令dp0=1dp_0=1dp0=1。在使用DijkstraDijkstra
2021-08-22 00:49:33
249
原创 力扣 5835. 最大方阵和 思维+贪心
https://leetcode-cn.com/problems/maximum-matrix-sum/思路：可恶啊，居然被这道题卡了。对于矩阵中任意两个坐标，我们可以找到一条从起始坐标到终止坐标的路径，那么对这条路径上所有相邻点做一次操作，最后的结果就是起始位置和终止位置的值取反，其余值不变。想到这一点就比较好做了，我们可以使用这种方式让所有的负数成对内耗掉，根据贪心想法自然要从小到大开始。需要注意的一点是如果负数的个数是奇数个，那么最终会剩下一个最大的负数没有被消耗掉。此时我们有两种选择：不做任
2021-08-22 00:28:08
111
原创 力扣 552. 学生出勤记录 II dp / 矩阵快速幂
https://leetcode-cn.com/problems/student-attendance-record-ii/思路一：动态规划，dpi,j,kdp_{i,j,k}dpi,j,k表示前iii次出勤缺勤了jjj次且最后连续kkk次迟到情况下能获得出勤奖励的次数。因为当且仅当j<2&&k<3j<2 \&\&k<3j<2&&k<3时才有意义，所以总体复杂度依然是O(n)O(n)O(n)的。下面是状态转移方程的推导
2021-08-20 01:22:23
176
原创 力扣 526. 优美的排列 回溯 状压dp
https://leetcode-cn.com/problems/beautiful-arrangement/思路一：还就内个暴力回溯。究极暴力的解法，枚举所有可能性，加上最简单的剪枝即可。class Solution {public: int countArrangement(int n) { vector<bool> vis(n+1); int ans=0; function<void(int)> dfs=[&
2021-08-17 01:31:27
187
原创 力扣 576. 出界的路径数 dp
https://leetcode-cn.com/problems/out-of-boundary-paths/思路：非常简单的dpdpdp，考虑用dpi,j,kdp_{i,j,k}dpi,j,k表示经过iii次移动后到达坐标(j,k)(j,k)(j,k)的方案数，那么对于任意一个坐标(j,k)(j,k)(j,k)，与其相邻的四个网格坐标即为一次移动后可能到达的点。转移方程比较简单，直接看代码吧。注意到dpidp_idpi只利用到了dpi−1dp_{i-1}dpi−1的信息，因此可以用滚动数组优化
2021-08-16 00:56:38
100
原创 力扣 1583. 统计不开心的朋友 模拟
https://leetcode-cn.com/problems/count-unhappy-friends/思路：无聊的模拟题。class Solution {public: int unhappyFriends(int n, vector<vector<int>>& preferences, vector<vector<int>>& pairs) { vector<vector<int>&g
2021-08-15 00:30:49
77
原创 力扣 233. 数字 1 的个数 数学 计数
https://leetcode-cn.com/problems/number-of-digit-one/思路：答案就是nnn的每一位（个位、十位、百位…）上出现的1的数量的总和。那么对于任意一个数字abcdeabcdeabcde，假设计算ccc位上的1，且有high=ab,cur=c,low=de,digit=102high=ab,cur=c,low=de,digit=10^2high=ab,cur=c,low=de,digit=102，现在开始分类讨论ccc的取值：c=0c=0c=0，为了让这一
2021-08-14 01:46:22
102
原创 力扣 516. 最长回文子序列 dp
https://leetcode-cn.com/problems/longest-palindromic-subsequence/思路一：dpi,jdp_{i,j}dpi,j表示区间[i,j][i,j][i,j]的最长回文子序列的长度，显然dpi,i=1dp_{i,i}=1dpi,i=1，对于区间[i,j][i,j][i,j]如果有si=sjs_i=s_jsi=sj，那么有dpi,j=dpi+1,j−1+2dp_{i,j}=dp_{i+1,j-1}+2dpi,j=dpi+1,j−1+2；否则
2021-08-13 00:50:25
106
原创 力扣 446. 等差数列划分 II - 子序列 dp
https://leetcode-cn.com/problems/arithmetic-slices-ii-subsequence/思路：就知道是dp，但是差一步没写出来，唉。考虑用dp[i][j]dp[i][j]dp[i][j]表示以nums[i]nums[i]nums[i]结尾公差为jjj的长度>=2>=2>=2的子序列个数。那么可以枚举等差数列的最后两项：numsj、numsinums_j、nums_inumsj、numsi。计算其公差dis=numsi−numsjdis=n
2021-08-11 01:46:27
140
原创 力扣 413. 等差数列划分 数学 双指针
https://leetcode-cn.com/problems/arithmetic-slices/思路：显然可以通过双指针找到等差数列的区间[l,r][l,r][l,r]，那么依据题目的定义，分别统计长度为3、4、5...3、4、5...3、4、5...的等差数列的个数即可，即：(r−l−2)+(r−l−3)+...+1(r-l-2)+(r-l-3)+...+1(r−l−2)+(r−l−3)+...+1。这不就是等差数列的和嘛，可以O(1)O(1)O(1)求得，因此算法的总复杂度为O(n)O(n)O
2021-08-11 00:30:00
101
原创 力扣 457. 环形数组是否存在循环 思维
https://leetcode-cn.com/problems/circular-array-loop/思路：用一个数组标记iii是否走过，然后对每个位置做一次循环模拟即可。但是这样复杂度是O(n2)O(n^2)O(n2)的，事实上，对于上次遍历过的点，如果没有找到答案，那么这些点都是无解的，我们可以把它们剔除掉，这样可以把时间复杂度降低到O(n)O(n)O(n)。不过为了区分上次遍历和当前遍历，需要新开一个数组。class Solution {public: bool circularA
2021-08-08 01:19:08
108
原创 力扣 847. 访问所有节点的最短路径 bfs+状压
https://leetcode-cn.com/problems/shortest-path-visiting-all-nodes/思路：考虑用二进制表示走过的点集(状态压缩)，那么可以用dis[i][j]dis[i][j]dis[i][j]表示在状态为iii的情况下到jjj点的最短路径，那么我们期望的答案就是最小的dis[2n−1][...]dis[2^n-1][...]dis[2n−1][...]。依然可以使用bfsbfsbfs来求解最短路，只不过状态是两个维度的。也可以认为这是刷表法的dpdpdp
2021-08-06 21:36:32
249
原创 力扣 802. 找到最终的安全状态 dfs染色法 / 建反图+拓扑排序
https://leetcode-cn.com/problems/find-eventual-safe-states/思路一：dfsdfsdfs染色，对于点uuu，如果正在访问它或者它的子节点，那么令color[u]=1color[u]=1color[u]=1；如果已经访问过它和所有子节点了，令color[u]=2color[u]=2color[u]=2；如果还未访问过令color[u]=0color[u]=0color[u]=0。那么如果递归的过程中，又访问到了一个颜色为1的点，则说明该节点的父节点不
2021-08-06 00:27:35
146
原创 力扣 611. 有效三角形的个数 排序 双指针
https://leetcode-cn.com/problems/valid-triangle-number/思路一：排序+二分，枚举较小的两条边i、ji、ji、j，然后通过二分找到最大的满足a[i]+a[j]>a[k]a[i]+a[j]>a[k]a[i]+a[j]>a[k]的kkk，那么它们对答案的贡献为k−jk-jk−j，代码略。思路二：当iii确定的时候，显然jjj越大，kkk也越大，因此可以利用双指针来做，每次把j+1j+1j+1，然后找到满足题意的最大的kkk统计贡献即可。
2021-08-05 00:43:34
127
原创 力扣 581. 最短无序连续子数组 思维
https://leetcode-cn.com/problems/shortest-unsorted-continuous-subarray/思路一：可以把原数组分为三部分：a、b、ca、b、ca、b、c，其中a、ca、ca、c满足题意，是升序排序的，但是bbb不满足题意。考虑对序列进行排序，排序后的序列必然也是以aaa开头ccc结尾的，减去这两部分即为bbb。class Solution {public: int findUnsortedSubarray(vector<int>
2021-08-04 00:48:33
76
unity3D项目—Flappy Bird
2020-10-14
XNView安装包(exe文件)
2020-09-22
空空如也
TA创建的收藏夹 TA关注的收藏夹
TA关注的人