_六六先森-CSDN博客

原创根据前序遍历和中序遍历获取后序遍历

算法：根据前序遍历中序遍历得到后序遍历

2022-11-21 16:28:43 972

原创用Go并发来解决leetcode的几道并发编程题

go语言实现leetcode并发题

2022-10-02 11:11:09 755

原创 GO操作其他编程语言代码-命令行，shell，C，python

我们在开发过程中免不了要执行其他编程语言写的代码。下面通过几个例子来示示范。一、命令行执行命令行并且输出结果：func main() { cmdStr:="ps" cmd:=exec.Command(cmdStr,"-ef") output,err:=cmd.Output() if err!=nil{ panic(err) } fmt.Println("get %s result:\n",string(output))}执行命令行但是不需要输出结果：fun

2022-04-16 17:13:46 1032 1

原创【leetcode前500】零钱兑换1+2

我们先观察第一个问题，问题中的黑体字是最少的硬币个数。如果令dp[i]是组合成金额i需要的最少硬币个数，那么很显然dp[i]=min(1+dp[i-c]),其中c是任意一个硬币的值。也就是说，最终用到的硬币个数，应当是一个面值为c的，加上总金额i-c对应的硬币个数。代码如下class Solution: def coinChange(self, coins: List[int], amount: int) -> int: coins.sort() ..

2021-09-13 20:20:34 116

原创剑指offer题集

因为面试前需要快速过一遍剑指offer，共68道，题目太多非常耗费时间，在此只做一遍值得一做的题目。凭我个人的能力（约100+道leetcode水平）是可以完全忽略一些题目的。这里仅给出python代码及思路1.两个栈实现一个队列。此题不难，但是需要考虑减少无用操作，时刻记住第二个栈已经是倒序的了，所以只要没pop完就不要再往里append。class CQueue: def __init__(self): self.stk1=[] self.st

2021-09-09 14:55:34 1689 2

原创【leetcode前500】144+94+145：二叉树的非递归前序/中序/后序遍历

用栈模拟递归形式，值得考虑的是，左子树入栈的时候就先把节点保存好即可。对应的是ret.append(root.val)dfs(root.left)dfs(root.right)class Solution: def preorderTraversal(self, root: TreeNode) -> List[int]: ret=[] stk=[] p=root while p: ...

2021-08-22 22:58:01 71

原创【leetcode前500】439. 三元表达式解析器

题目给了提示，我们需要从右往左结合，这个时候要用到栈。考虑示例3，可以看出我们应当在从右往左遍历到问号时，再对后面的表达式判断，这个时候我们需要对栈进行两种操作：如果是T，那么将栈第二个元素弹出去如果是F，弹出第一个值得去注意的是有的时候栈里保存的不全是数字，也可能是TF，我们需要在搜索到‘?'的时候立即注意到下一个字符的T或者F将会对栈操作。class Solution: def parseTernary(self, expression: str) ->...

2021-08-21 20:40:50 119

原创【leetcode前500】440. 字典序的第K小数字

思考一个问题，字典序的话，我们构造一个数字时，前缀是pre那么，递增和拼接哪个更大？举例示例里面的，前缀是1，递增是2，拼接（变成10，11），看来拼接是字典序更小的。首先我们需要找到一个前缀下所有元素的个数，比如前缀是1，n=125，那么在这颗树下的个数一共有1+10+10+10+6(1，10....19,100...125)。如果我们把这下面所有的节点加到排序里面，但是还未到达相应的序号，那就递增前缀，使其快速的变大；否则我们*10让其缓慢的变大。class Solution: ..

2021-08-21 18:15:18 83

原创【leetcode前500】442. 数组中重复的数据

一般考虑这种题目，通用解法就是将原数组当成哈希表操作（因为元素都是1-n）。这里面需要考虑的是怎样用原数组达到要求。首先我们考虑如何将一个数字标记为已访问过：可以将其置为他的负值。遍历过程中，我们只要发现对应位置上的数组已经被置为负值了，那么就认为是出现第二次了，保存结果。class Solution: def findDuplicates(self, nums: List[int]) -> List[int]: ret=[] for k ..

2021-08-21 09:12:06 64

原创【leetcode前500】446. 等差数列划分 II - 子序列

我们观察下面的数据长度，那么平方级别时间应该是足够了。这里示例给了一个很好的例子，可以看出是可以重复的。我们选定一个以x结尾的序列，遍历它前面的数字y，设公差为d，那么以y结尾的所有序列且公差为d的序列个数加1就是以x结尾的公差为d的个数。需要注意的是，这里公差可能的范围非常大，将二维数组的第二维度换成字典保存公差d，这样就得到下列代码，需要注意的是，最终结果是返回所有可以成为等差序列的序列个数。class Solution: def numberOfArithmeticSlice..

2021-08-20 19:27:21 74

原创【leetcode前500】452. 用最少数量的箭引爆气球

一般对于这种区间计算的题，首先想到的是先排序，把区间弄得有序然后再分段计算。这里我们需要考虑的是一箭射爆多个气球的情况，我们可以在数轴上画画图，只要尽量重合，那就能尽量多的射爆。所以为了让他们重合，我们需要不断计算重合区间，直到下一气球再也无法重合为止。复杂度是O（nlogn）。class Solution: def findMinArrowShots(self, points: List[List[int]]) -> int: points.sort() ...

2021-08-15 00:21:12 62

原创【leetcode前500】454. 四数相加 II

这题其实挺有意思的。如果我们采用一个哈希表保存a+b+c，遍历D获取和为0个数那么是O(N)+O(N^3)如果我们采用一个哈希表保存d，遍历A+B+C，那么和上面一样。但是如果我们采用一个哈希表保存a+b，遍历C+D，那么时间是O(N^2)+O(N^2)class Solution: def fourSumCount(self, nums1: List[int], nums2: List[int], nums3: List[int], nums4: List[int]) ...

2021-08-14 21:43:17 61

原创【leetcode前500】456. 132 模式

按经验应当使用一个单调栈，但是这里的用法比较奇特，需要从后往前遍历。我们考虑递减栈pop过程中被弹出去的元素，如果能够找到一个比前面的大的，就说明成功了。试想[-1,3,2,0]栈增长分别为[0]--[2]，那么0就是被弹出的元素。被弹出说明了两件事情：1，前面必定有一个比他大的元素。2，只要前面再有一个比它小的那么查找就完成了。我们用一个变量保存被弹出的最大值，只要遍历时发现有数字比这个值小，就好了。class Solution: def find132pattern...

2021-08-14 19:37:27 65

原创【leetcode前500】457. 环形数组是否存在循环

其实这种题，对于查找环的问题，我们应该立即想到快慢指针，但是对于一个整体的设计，确实没有一下子想出来。1.如何去除重复路径的问题。我们观察数组元素是正数或者负数，因此我们用遍历置零的办法去掉重复路径搜索。2.同方向的问题。题目中要求成环条件是下标是同一方向的，也就是应当全为正数或者全为负数，遍历过程中应当与快指针节点以及快指针的下一个节点比较符号即可。3.特殊情况比如[2,1]，一直重复2-2-2....这样是要过滤掉的class Solution: def circu...

2021-08-14 18:47:14 65

原创【leetcode前500】458. 可怜的小猪

这是一道纯数学分析题，首先我们考虑minToDie和minToTest，这两个表明了可用的“批次”。比如示例1，p=60/15=4，说明我们可以用n头猪，测试p=4次。不妨假设毒药总是在最后一桶，而且测试总是从小到大开始测试。假设n=1，也就是仅有一头猪，测试p=4次，可能的结果是：1.第一次测试就中毒；2.躲过第一次，第二次中毒；3.躲过第二次，第三次中毒；4.躲过第三次，第四次中毒；5.躲过第四次，依然存活。那么对于这一只猪可能有五种状态，s=p+1。接下...

2021-08-11 13:07:36 91

原创【leetcode前500】459. 重复的子字符串

暴力法就不说了，官方给的一个解法挺有意思的。假设S=ss....s也就是由多个重复串组成，那么只要把第一个s移到最后面也是能够构成S的。比如S=abcaabcaabca ==>S=[abca][abcaabca]。这个时候我们令S'=[abca][abcaabca][abca][abcaabca]可以看出中间肯定是包含S的，哪怕去掉首位两段，如果这重复串非常小S=aaa，那么S'=[a][aa][a][aa]，如果去掉首位两段也能获得S，那么说明也是。因此我们把新串掐头去尾，看...

2021-08-11 11:55:52 57

原创【leetcode前500】460. LFU 缓存

此题有两个需要注意的点，最近-最少未使用。比如说我们有几个键值对，那么，如果要淘汰一个的话按照题意“存在相同使用频率应该去除最近最久未使用的”，应当先比较计数器，不相等淘汰计数器最少的；若计数器相等，那么淘汰最晚加入的。我们在类内部维护一个时间戳，只要进入一个操作内，时间戳就+1来维护时间序列。剩下的是就是节点的更新工作，在本题刚开始时，准备使用堆来维护节点，以哈希表来维护键，但事实实际上用树状结构足够了，因为维护的代价都是log（n）。需要注意的就是节点的先删除再插入，在这个过程中，更新计..

2021-08-11 11:41:22 75

原创【leetcode前500】463. 岛屿的周长

很容易我们能观察出，一个块能带来4条边，但是一旦有邻接就会损失2条。我们需要计算的是1.一共多少个块，这个很容易，遍历即可2.判断它的每条边是否是邻接的一旦邻接，就把总数减一，因为遍历到他的邻接块还会计算一次。class Solution: def islandPerimeter(self, grid: List[List[int]]) -> int: def check(i,j): if 0<=i<len(grid..

2021-08-10 00:36:14 56

原创【leetcode前500】464. 我能赢吗

令maxn=maxChooseableInteger,total=desiredTotal。如果maxn大于等于total，那么先手一次拿取就获胜，直接返回。如果1+2...maxn都是小于total的，那么无论怎么取，先手都不能获胜，直接返回。对于博弈论的函数，一般模式我们判定需要的是:check(...当前状态）= true if not check(下一状态，也就是对手的状态）else false为最基本的模板，这里因为要时刻记住1~maxn的数字到底被用过了没有，并且要...

2021-08-08 23:47:26 93

原创【leetcode前500】467.环绕字符串中的唯一子串

我们可以先忽略他奇奇怪怪的定义，考虑一个数字序列共有多少个连续子串。比如[0,1,2,5,6]那么应该是"0","1","2","5","6","01","12","56","012"。观察很容易得出，如果分类为以某个数字结尾的连续子串个数，那么"2"==>3;"1"==>2;"0"==>1;"5"==>1;"6"==>2;很显然就是需要在遍历的过程中计算出前方有多少个数字是连着的，然后将这个连续值取到最大。在判断有序的过程中其实就已...

2021-08-08 20:36:06 73

原创【leetcode前500】472. 连接词

对于该题，我想到的策略是递归判断。对于一个字符串word，在某处切分成left_word,和right_word，如果已经知道left_word是一个在给定单词集合中的，然后再递归判断right_word即可。不过重复的判断串太多了，我们用缓存记录一下已经被判定为是连接词的词。值得注意的是需要先把空串过滤掉，否则容易无线递归。PS：lc加强了用例class Solution: def findAllConcatenatedWordsInADict(self, words: Li..

2021-08-08 18:33:24 86

原创【leetcode前500】473. 火柴拼正方形

此题递归做是没毛病的，有三个优化的点：1）预先判断变长总和，如果不是4的倍数直接pass掉2）如果总边长为S，那么最终结果应该是每条边都是L/4，递归时要过滤掉能让变长大于这个值的所有情况3）有一些情况是无需考虑的，例如：L1=2,L2=2,L3=2,L4=2情况下，新的长度t=1先加到哪条边?实际上加在哪里都可以，但会导致重复，所以我们限定只加在L1上。再次递归时t=1，我们加在L2上，也就是说因为L3和L4已经是相等的了，我们不去破坏，从而造成大量的浪费。class So...

2021-08-08 16:28:29 47

原创【leetcode前500】474. 一和零

套路太深了，看出是01背包了，但没想到要变成三维数组降为二维来做。定义dp[i][j][k]为前i个字符串，能够0个数小于j，1个数小于k的集合最大元素数量。很显然dp[i][j][k]=max{dp[i-1][j][k],dp[i-1][j-C0_i][k-C1_i]+1}，其中C0_i表示当前字符串0的个数。由01背包模板的经验，最外层可以被优化掉，因此只要考虑dp[j][k]就行了。不过要注意里面是一个双层循环。class Solution: def findMax...

2021-08-08 15:39:33 48

原创【leetcode前500】475. 供暖器

光看数据量可以知道一定要用二分法了。考虑示例2，对于每个house的位置，我们需要找到最近的heater的位置，可以知道用二分法比较方便。（前提先对heaters排个序，题目没说有序）接下来考虑二分的边界条件，因为是前插，举个例子2应该插在【1，3，5，7】的第1的位置。因此只需要分别考虑最左边，最右边和处于中间的情况。class Solution: def findRadius(self, houses: List[int], heaters: List[int]) -&gt..

2021-08-08 15:09:31 57

原创【leetcode前500】476. 数字的补数

硬算谁都会算，能用位运算玩明白才是真牛啤。假设num=0b00001011 ，假设用8位好算一点，实际上应当是32位，道理大同小异。我们需要一个mask值mask=0b11110000来掩掉前4个0.这样最终结果应当是~mask^num得到0b00000100。现在用一个循环来获得mask值，原理很简单，只要后面的1与num有重叠，就左移。值得注意的是c++应当用unsigned，否则会报运行时异常。class Solution {public: int findComp..

2021-08-02 19:53:05 55

原创【leetcode前500】477. 汉明距离总和

本题的解法已经藏在示例1了。考虑第2位，4、14为1，2为0，那么其二进制对应位的不同数量就是2，尝试扩展该示例使得更清晰。[4,2,4,2,4]，那么仅考虑第二位（按4位计算）那么就是1-0-1-0-1，那么但就这一位考虑来说应当是6，也就是不同位数量是2*3。因此我们可以采用一个逐个位算法。而且可以先采用统计的策略尽量减小重复计算。class Solution: def totalHammingDistance(self, nums: List[int]) -> int: ..

2021-08-02 19:34:23 54

原创【leetcode前500】478. 在圆内随机生成点

这里采用一个极坐标的算法。首先随机出一个圆，与给定的圆同心，但是我们知道一个点落在小圆的概率与大圆的概率比值是面积的比值。然后随机一个角度出来，0~2PI。利用x=R*sin(t),y=R*cos(t)得到最终结果。import randomimport mathclass Solution: def __init__(self, radius: float, x_center: float, y_center: float): self.r=radius...

2021-08-02 19:15:47 121

原创【leetcode前500】481. 神奇字符串

本题其实很简单，开头序列为[1,2,2]，之后可以直接迭代出剩余的部分。已知如果现在数字序列是[1,2,2]时，字符串序列为['1','22']，那么需要第三个数字迭代（加粗的2），添加进'11'到字符串序列的同时也会添加进2个1到数字序列变为[1,2,2,1,1]，这样的话，下一轮迭代用的就是1（加粗的1）。因此可以归纳为添加的数字、个数是已有序列迭代的前面部分迭代出来的，因此，根本不需要字符串序列，仅需要一个array即可完成计数。class Solution: def magical..

2021-07-29 19:46:07 74

原创【leetcode前500】483. 最小好进制

从示例可知，最坏情况的进制base大小可能达到n，那么线性扫描的时间是不可能了，这里采用了一个二分法的策略。我们比如我们尝试以b进制构造x个1组成的数字，那么这里可以计算得val=b**(x-1)+b**(x-2)....b**0。最快的方式是采用等比数列算法，也就是v=(b**x-1)//(b-1)。我们与输入数字比较，如果比他小，说明进制不够大，如果比他大，说明进制要缩小。而且这个x个1的常识，只需要63次即可，因为63个1组成的二进制数字已经可以容下1e18了。细节问题是，我们一旦找到..

2021-07-28 20:14:11 91

原创【leetcode前500】486. 预测赢家

很明显是一道动态规划题。这道题需要我们转换思路，改为”玩家1能够领先玩家2多少分“。如果数组的长度是1的话，那对于数组为[x]的结果，应该就是x。令dp[i][j]表示数组i~j区间内的数字，能够领先对手的最大值，那么dp[i][j]=max(nums[i]-dp[i-1][j],nums[j]-dp[i][j-1])，解释起来就是，dp[i-1][j]是被对手领先的值在nums[i-1..j]的体现，本轮取了nums[i]，相减就得到能够领先对手的值，题中例子1，某一轮user1领先对手5，那么...

2021-07-28 19:25:43 60

原创【Leetcode前500】493. 翻转对

做过求逆序对那道题可以一眼看出这应该是那道题的变种，但是与之不同的是我们要用其他方法归并计数。考虑两个排序好的数组[1,3,5,7] [1,2,3]在这俩数组中可以采用双重for循环一次判断A[i]>2*B[j]能否成立。因为已经破坏了排序条件，所以计算的时候是不能对其排序的，要等计算完毕再排序递归。那么这个计数方法复杂度就是L1*L2（两个数组长度）。但是这样的话，复杂度是大大增加了，相当于整个的复杂度变成了平方时间。我们需要一个能够接近O（n）的时间计数。...

2021-07-24 13:04:46 58

原创【leetcode前500】494. 目标和

先考虑对称性，如果把示例的正负号颠倒一下，就是-3了，所以target只要是大于等于0的即可，先取个绝对值简化计算。因此很容易想到特殊情况一：如果所有数字只和S都比target小，那返回0.我们将前面带正号的数字和为Sp,带符号的为Sq，那么S=Sp+Sq并且Sp-Sq=target因此得到Sq=(S-target)/2我们知道要计算的数字都是整数，因此得到特殊情况2：(S-target)/2非正整数的返回0，也就是(S-target)%2==1的情况。现在问题转化成..

2021-07-24 12:30:18 50

原创【Leetcode前500】497. 非重叠矩形中的随机点

此题关键是构造出来一个”均匀选取“的方式。我们先考虑如何在一个矩阵里面均匀选点，比如(1,1),(4,5)构造的，很容易看出一共有20个点，如果我们把它看成一条一条的，就很容易去获取了。现在我们需要获取这里面的第10个点，我们从下往上构造,从0开始计数，dx=1,dy=2。这是因为w=(x2-x1+1)的话，9%4=1,9//4=2。这样就很明朗了。接下来我们如何得知从哪个矩形选择，需要根据矩形的面积来给定一个权重。具体见代码即可，但是随即得到的数字其实已经相当于第K个点了。...

2021-07-16 23:55:57 96 1

原创【Leetcode前500】498. 对角线遍历

这里可能很多人大多人会选择难搞的箭头方向旋转+边界判断的算法，但是这里给出一个比较容易弄的，BFS算法：class Solution: def findDiagonalOrder(self, mat: List[List[int]]) -> List[int]: if not mat: return [] m,n=len(mat),len(mat[0]) ret=[] loc=[(0,0)] ..

2021-07-16 22:38:41 52

原创【复习】剑指offer值得一做的题

因为面试前需要快速过一遍剑指offer，共68道，题目太多非常耗费时间，在此只做一遍值得一做的题目。凭我个人的能力（约100+道leetcode水平）是可以完全忽略一些题目的。这里仅给出python代码及思路...

2021-07-05 22:14:28 159

原创 libevent2从入门到原理解读（1）：安装及使用

一、编译构建libevent是一个用c编写的高性能网络框架，通过简单的封装，就能构造自己的应用服务器，从https://libevent.org就能下载到相应的版本tar包。因为我们要在linux系统中使用，所以找到一个linux环境，编译并使用它：./configure --prefix=/root/libevent/libevent-2.1.12-stable先用configure二进制文件发起检查，没问题了就可以了。然后进入cmake文件夹cmake .. &&am

2021-02-27 00:26:46 1208

原创 C++项目的构建（一）：静态库、动态库、共享库

通俗意义上讲，静态库就是Linux系统中的”XXX.a“文件，它实际上是一组目标文件的集合（”XXX.o")，多个目标文件经过打包，就得到了静态库。我们都知道，一个.cpp文件需要经过预编译（包括去掉#define并将其替换，处理条件编译如#if、#ifdef，删掉注释，添加行号，保留#pragma指令）得到.ii文件；编译（将c++代码翻译成汇编代码）得到.s文件；汇编（将汇编代码翻译成机器指令）得到目标文件即.o文件；链接（-lXXX链接一些库）得到可执行文件（一般来说是a.out),之后就可以执行..

2020-05-24 16:50:04 743

空空如也

空空如也