- 博客(55)
- 收藏
- 关注
RSS订阅原创 数据结构算法刷题（29）动态规划
res = max(dfs(i-1),dfs(i-2)+nums[i]) #如果选，下一次递归的就是i-2，并且要加上nums[i]的值，如果不选，下一次递归i-1。dp1 = min(cost[0],cost[1]) #第1级台阶的顶部台阶的最小花费是cost[0]或cost[1]的最小值。思路三：我们可以确定的知道每个节点是那几个数归的结果，那把递的过程省略，直接归，也就是从下往上计算结果。f = [0]*(n+2) #归的数组长度是n+2，每个数组的值是0。n = len(nums) #数组的长度。
2023-09-11 18:38:20
284
原创 数据结构算法刷题：背包问题
return 1 if c == 0 else 0 #如果c小于0，那就没有找到，返回0，c==0返回1。return dfs(i-1,c)+dfs(i-1,c-nums[i]) #返回选或者不选的和。return dfs(i-1,c)+dfs(i-1,c-nums[i]) #返回选或者不选的和。return dfs(i-1,c)+dfs(i-1,c-nums[i]) #不会判断nums[i]>c的情况。整数和是p，负数和是s-p，那么target = p - (s-p)，求出p = (s+t)//2。
2023-09-08 12:28:17
273
原创 《热题100》字符串、双指针、贪心算法篇
思路：设置上下左右的边界值，然后开始遍历，从左到右遍历一次，更新up的值，然后判断当前是否还有行：up <= down，然后从上到下遍历，更新right值，之后判断当前时候还有列：left <= right。思路：让两个指针i j,分别从两个字符串的最后一位开始向前遍历，设置进位ind，当i j都没有走到-1时，如果当前和a = i+j+ind大于9，那就res.insert(0,a-10)，将ind置为1，如果当前和小于等于9，res.insert(0,a)，将ind置为0.如果大于，就更新边界。
2023-09-07 19:37:59
761
原创 《热题101》动态规划篇
思路：可以有多次买卖股票的情况下，当前是第i天，在当前能够得到的最大获利分为两种情况，第一种是今天持有股票：dp[i][1] = max(dp[i-1][1],dp[i-1][0]-prices[i])要么前一天也持有，今天就不变，要么前一天不持有，今天就购买。思路：需要一个二维数组dp来记录当前的公共子序列长度，如果当前的两个值等，则dp[i][j]=dp[i-1][j-1]+1,否则dp[i][j] = max(dp[i-1][j],dp[i][j-1])。第一个格子的路径置为1，计算dp。
2023-09-04 17:08:01
226
原创 《热题100》回溯篇
思路：单纯的深度递归会超时，因为之前会有大量的数据计算，所以需要一个数组来保存当前的最大递增路径的值。在遍历当前值时，如果当前dp值不是0，那就说明之前计算过该值，直接返回。比较记录中的每个字典，如果有相同key和value，就合并（d1.update(d2)），然后删除多余的那个字典。思路：每一行每一列都需要放入一个皇后，我们可以递归行号，然后在该行内，找列可以放的位置，如果都不冲突，就可以放入。思路：遍历二维数组，遇到1之后，就先给答案加1，然后进入递归，将1的上下左右都换成0，避免之后再进入。
2023-08-29 16:26:25
496
原创 《热题100》二分查找、排序、二叉树篇
然后遍历数组，先将头结点入队，然后取数组中的两个数，如果当前值不是'#'，就创建新节点，连接到队中的节点上，每次移动两个数。如果p、q都在左子树，就去左子树递归。思路：如果当前为空，返回0，递归左子树，如果结果是-1，就返回-1，再继续递归右子树，如果结果是-1或者abs(l-r)>1，就返回-1.其余正常情况，返回当前的树高度max(r,l)+1。思路：利用前序遍历，每次新建一个节点，如果两个节点都在，就计算和为当前节点值，然后当前节点的左子树等于遍历两个左子树的结果，右子树等于遍历两个右子树的结果。
2023-08-25 18:37:13
441
原创 《热题101》链表篇
用左右指针来确定当前反转的区间，每次反转之前都检查一下当前区间是否足够k，即区间之后的节点cur，足够就可以反转，反转之后找到当前的cur，循环反转。当两个链表都走到最后了，查看进位值是否为1，如果是就再新增一个节点，如果不是，就把全部新增节点反转输出。思路：因为是升序链表，设置头结点（为了删除head），如果dump.next.val==dump.next.next.val ，记录当前的value值，删除所有值是value的节点。思路：先遍历一次链表，用数组存储，然后快排数组，最后将数组转化成链表。
2023-08-23 19:02:38
118
原创 《剑指offer》（7）动态规划、回溯
主要是招路径的dfs方法，想象成一颗4叉树，如果当前i,j越界或者不匹配路径，返回false，如果走到了路径尾就返回ture，然后递归找上下左右的路。思路：使用左右指针同向移动，并且使用dp数组 记录当前的最大和，如果出现了新的最大和，或者区间增加，就修改start,end指针，最后输出start到end+1的范围即可。思路：从（0,0）开始找上下左右可以去的格子，如果越界或者这个格子来过或者格子不满足条件，都返回0，否则就标注格子可达（将对应位置置位1），然后返回1+上下左右的和。
2023-08-17 17:32:55
136
原创 《剑指offer》（6）其他算法
假设长度为i的绳子的不可分割长度是j，那么此时的最大乘积是dp[i] = max(dp[i], j*dp[i-j]) 初始化dp，前面四个数是1,2,3,4。把一个数a乘n次，按照二分的思想，将n不断除以2，如果是偶数，就累乘a = a*a ,如果是奇数，就将当前的a和结果相乘。n = m*x, 最大乘积是x^m, m=n/x , 所以最大乘积是x^(n/x) ,将常数n提出，最大乘积是x^(1/x)dp[1],dp[2],dp[3],dp[4] = 1,2,3,4 #跳过0。
2023-08-09 17:00:17
309
原创 《剑指offer》（5）搜索算法、位运算、模拟
如果mid比right小，mid在后半段，让right=mid,如果等无法判断是前半段还是后半段，right-=1，缩小判断范围。#将数组排序，计算0的个数，超过4就返回FALSE，找到第一个不为0的数，计算两两差值，累加和0比较。全排列，递归回溯，每次将递归的层数和字符串下传，在[h，size-1]中的元素互换，然后递归，递归回来恢复现场。#首先去掉字符串的首位空格，然后判断数字的符号位，然后开始遍历字符串，遇到非数字就跳过，最后做范围判断。s[i],s[h] = s[h],s[i] #恢复现场。
2023-08-08 16:13:10
137
原创 《剑指offer》（4）二叉树篇
if a.val == pRoot2.val : status = check(a,pRoot2) #遇到相等的节点就check一下。#反序列化的时候，依旧按照入队出队，把根节点入队，然后取s中的两个数，如果不是'#'创建左子树并入队，i每次增加2。#确定左右子树的分界，因为值各不相等，如果遍历到了大于等于树的值，则遍历到了根或者右子树。#递归左子树和右子树的深度，如果深度差超过1，就返回-1，遇到-1就直接退出。#设置全局变量记录答案，把当前深度和答案长度对比，如果相等，就可以记入答案。
2023-08-04 19:06:08
177
原创 《剑指offer》（3）排序算法篇
smaller.append(i) #放到smaller中，此时对于small中的每一个数，逆序对都至少等于bigger中的个数（不考虑smaller内部情况）res += len(bigger) + 1 if num[i] < prev else len(bigger) #如果严格不等值，就得加上基准，否则不加。return res+self.merge(bigger)+self.merge(smaller) #递归去查看bigger和smaller中的情况。bigger = [] #比基准大的数字。
2023-08-03 18:23:18
756
原创 《剑指offer》刷题（1）链表篇
分别找两个指针指向两个链表，如果指针1为空，就指向链表2，指针2为空就指向链表1，当两个指针相同时（可能都是空或者相遇了）跳出循环。while p.next and p.next.val == temp: #循环删除p.next。#使用快慢指针，先让快慢指针相遇，确定有环，然后将快指针指回头结点，和慢指针一起重新走一遍，步长为1，相遇节点就是环入口。#使用hash表来存储新链表与旧链表的节点，key:旧链表节点，value:新链表节点。if p.next.val == val: #删除p.next。
2023-08-02 22:29:29
178
原创 计算机网络面试题总结
（1）OSI七层模型分别是什么，各自的功能是什么？自底向上来说，首先是物理层（比如集线器等，负责传输光电信号，在物理网络中传输数据），数据链路层（网桥或者交换机工作，负责数据的封帧和错误检测以及mac寻址，有ARQ自动重传请求协议，PPP点对点协议），网络层（路由器工作，有IP协议，ICMP Internet控制报文协议，ARP地址转换协议。负责数据的路由、转发、分片），传输层（TCP,UDP协议，提供端到端的数据传递），会话层（负责建立、管理、终止会话），表示层（对数据进行翻译、加密、
2023-07-11 18:35:42
794
原创 数据结构算法刷题（28）回溯组合型和全排列
第二是如何避免对角线打架：因为我们是按照从上到下的行数来放置的，所以只需要考虑左上方和右上方的数据，左上方和皇后位置的行列和一致，右上方和皇后位置的行列差一致。思路：相当于从2n个位置上，选择n个位置放置左括号，但是左右括号是有约束的，左括号不能超过n，右括号不能超过左括号。思路：在每一个位置上，选择一个数填入，但是该数和前面的数不能相同，维护一个s，来存放当前可以选的数字，每次加入path之后，就把该数字减去。思路：首先在[1,9]中选出不同的k个元素的子集，如果sum(path)==n,就更新答案。
2023-06-16 21:35:31
393
原创 数据结构算法刷题（27）回溯（子集型）
当不选择逗号时，初始位置start不变，但是终止位置i+1（i截止到n-1），当选择逗号时，意味着从逗号处开始分割，取此时的s[start:i+1]，判断是否是回文串，如果是，就加入到path中，继续递归剩下的字符串（s[i+1:],开始位置和结束位置都重新设置为i+1），递归之后要恢复现场。思路：对于nums中的每一个数字，都有选和不选两种可能，一共有n次选择的机会，用n来控制递归，每选择一次，就给n减一再去递归，直到n是0，就要将path写入答案。首先，当digits是空，那返回也是空。
2023-06-15 16:06:41
361
原创 数据结构算法刷题（26）层序遍历二叉树
思路：维护一个deque，首先把节点入队，然后从队头pop出来node，将node的val存入当层的数组中，如果node的左子树在，就左子树入队，如果node的右子树在，就右子树入队。小循环结束后要把当层的val数组清空，当队空时跳出循环。思路：层序遍历二叉树，第一次遇到某个节点没有左右子树的时候，就return出当前节点的层数。思路二：让右子树先入队，再入队左子树，最后一个节点就是答案。思路一：层序遍历，然后返回ans[-1][0]思路：返回层序遍历每一层的最后一个值。思路：层序遍历，每层将ans+1。
2023-06-01 17:09:34
103
原创 数据结构算法刷题（25）二叉搜索树
后序遍历，当该树是空，返回-inf,inf,0，这样，在归的时候，这个条件就满足二叉搜索树，如果不满足二叉搜索树，就要返回inf,-inf,0，让l_max >= node.val or r_min <= node.val不成立。思路：边界条件是：如果root是空，就返回空，如果root.val==val,就返回该root。然后递归左子树，如果递归结果不是空，就返回这个结果，空则继续递归右子树，不空就返回结果。if not a and not b: #如果递归结果都不存在，那p,q不在该节点上，返回空。
2023-06-01 16:12:03
132
原创 数据结构算法刷题（24）二叉树
两个边界条件：（1）root是空的时候，返回FALSE（2）当root的左右子树都是空的时候，判断现在root的val和目标值是否相等。思路：对于最小深度有两种特殊情况：如果root是空，那最小深度是0，如果root没有左右子树，那最小深度是1.假设该树有左子树，那计算叶子节点的最小深度。然后递归p和q的值是否相同，以及两颗树的左子树，和两棵树的右子树。思路：维护一个ans，先递归右子树，当ans的长度小于该节点的的高度时，就把答案写进去，如果大于就不写，然后再递归左子树。
2023-05-30 11:53:30
202
原创 数据结构算法刷题（23）快慢指针、前后指针
第二种思路：用两个指针， 第一个right指针从dummynode走出n+1步之后，left从dummy移动，同时移动right，当right指向最后一个节点的时候，left指向倒数n+1个节点。思路：#需要一个dummynode，当p的后面两个节点值相同时，进入一个循环，删除这些值相同的元素，如果后面两个节点值不同，就移动cur到下一个节点，直到只剩下两个节点。思路：#cur指向头结点，如果下一个节点的值与cur相同就删除掉下一个节点，如果不同就移动到下一个节点，知道cur.next是空。
2023-05-25 11:43:29
130
原创 数据结构算法刷题（22）反转链表
思路：首先找到left的前一个节点（为了避免left是头结点，所以我们给头结点之前再加一个节点），然后反转（right-left+1）个节点，反转方式如上，最后，修改这段数据前的指针。思路：先求出链表的长度，当n>=k的时候，可以反转，反转从left= 1开始，每次反转k个节点，反转之后，更新p0的值（下一次反转的前一个节点），让前后连接。#用三个指针，pre指向当前节点的前一个节点，cur指向当前节点，nextcur指向当前节点的后一个节点。p0 = nxt #下一次反转的left的前一个节点。
2023-05-23 14:48:07
103
原创 数据结构算法刷题（21）二分查找
区间有序，如果中间值比右边大，那有可能出现最小值的区间就是[mid+1,right),如果右边值大，出现区间可能是[left,mid]if nums[mid] > nums[right]:#mid是在一段序列中,left向右移动。大于：lower_bound（nums,target+1）#不包含target，所以target+1。left,right = -1,len(nums)-1 #开区间，（-1，n-1）if nums[mid] > nums[-1]:#mid在第一段序列中。
2023-05-19 16:48:35
64
原创 数据结构算法刷题（20）双指针：相向指针
思路：遍历最大边，只要剩下的两边和大于最大边，就可以得到一个三角形。固定right找到能够大于target的最小left之后，right-left中的全部数值都可以大于target。思路就是套娃：四数之和就调用三数之和，三数之和调用两数之和，然后注意优化一下时间，以及判断数组的长度，以及当前元素和前一个重复的时候跳过。break #如果当前值加上比他大一点点的值就大于0，那就没有元组和为0 了。continue #如果当前值和最后两个数加起来都比0小，就跳过当前值。left += 1 #寻找left。
2023-05-18 10:59:05
150
原创 数据结构算法刷题（19）双指针问题
思路：在窗口之外的字符串中，如果每个出现的元素是小于等于len(s)//4的话，那么改变窗口就可以让其平衡。ans = min(ans,right-left+1) #移动好左端点之后，再去更新窗口大小。ans = len(nums)+1 #设置一个不可能的值，这样取min的时候就不会取到。target = sum(nums) - x #反向思考，取数组中间的一段和为target的子数组。使用滑动窗口来解决该问题，枚举右边界， 给窗口内的和增加，当窗口的值大于某个数时。left += 1 #右移左端点。
2023-05-16 19:35:18
121
原创 复现pointpillars，anaconda
解决方法一：将conda-forge添加到搜索路径上首先，当出现这种报错时，应该首先尝试使用以下命令将conda-forge channel添加到你的channel列表中：conda config --append channels conda-forge它告诉conda在搜索软件包时也要在conda-forge channel上查看。在此期间我遇到下不下来最后一个包google-sparsehash，参考以下内容，在conda的官网上找到自己包的下载指令，如果依旧下载不下来，就直接本地下载。
2023-05-09 21:46:23
692
原创 OpenPCDet复现pointpillars，win10
下载好zip文件之后，需要将数据集放在OpenPCDet/data/kitti文件夹下面，新建training、testing文件夹，将calib、velodyne、label_2、image_2文件夹解压，并把他们放到对应的training、testing文件夹中，testing文件夹没有label_2文件。出错：Could not build wheels for SharedArray，我查看了conda网站上的内容，sharedarray是只支持Linux系统，不支持Windows的。
2023-05-09 21:45:18
2335
7
原创 数据结构算法刷题（18）二叉树的层序遍历
解法二：从右往左的层序遍历二叉树，最后一个出队的节点就是所求节点。ans.append(value) #该层节点值加入最终层。cur = [root] #每层的根节点。解法一：层序遍历二叉树之后，返回最后一层的第一个节点。ans = [] #最终的答案数组。ans = [] #最终的答案数组。ans = [] #存放层序遍历。将cur和nex合并成一个队列，先进先出。cur = nex #更换当前层。
2023-05-06 17:47:28
122
原创 数据结构算法刷题（17）二叉树、二叉搜索树（深度优先）
if (p.val < root.val and q.val >root.val) or (p.val > root.val and q.val < root.val): #分别在左右子树。最后是后续遍历，对于某个根节点来说，root.val要大于左边的最大值，并且要小于右边的最小值。if p.val < root.val and q.val < root.val: #都在左子树。if p.val > root.val and q.val > root.val: #都在右子树。
2023-05-06 15:47:39
112
原创 数据结构算法刷题（16）二叉树纲领篇
首先我们需要计算左右子树的高度，如果高度差大于1的时候，将高度设置为-1返回，并且每一个接口都不做改变，一直返回到递归入口。其特点如下：设x为二叉查找树中的一个结点，x节点包含关键字key，一句话就是左孩子比父节点小，右孩子比父节点大，还有一个特性就是”中序遍历“可以让结点有序。首先我们判断两棵树的节点值是否一样，然后再递归判断左子树是否一样，右子树是否一样，当p,q有一个是空的时候，退出递归，如果pq相等就是True否则就是False。我们可以根据返回每一个节点的左右子树的最长路径，求得节点的最长路径。
2023-05-05 20:02:58
67
原创 数据结构算法刷题（15）高效、等概率地随机获取元素，数据流的中位数
if self.getRight(k) < len(self.tree1) and self.less(self.tree1[self.getRight(k)],self.tree1[self.getLeft(k)]):# 右孩子存在而且右孩子大。if len(self.queue_large.tree1) <= len(self.queue_small.tree1):#应该large加。a = int(random.random()*len(self.setlist)) #随机取一个下标。
2023-05-05 15:44:18
135
原创 CNN卷积神经网络学习笔记（特征提取）
vgg16总共有16层，13个卷积层和3个全连接层，第一次经过64个卷积核的两次卷积后，采用一次pooling，第二次经过两次128个卷积核卷积后，再采用pooling，再重复两次三个512个卷积核卷积后，再pooling，最后经过三次全连接。1）输入图像尺寸为224x224x3，经64个通道为3的3x3的卷积核，步长为1，padding=same填充，卷积两次，再经ReLU激活，输出的尺寸大小为224x224x64。3）经128个3x3的卷积核，两次卷积，ReLU激活，尺寸变为112x112x128。
2023-04-26 17:13:10
9634
原创 pycharm调试时高亮的行与实际运行的行不一致解决方案
（2）解决方案就是将PYDEVD_USE_CYTHON=NO。（1）清楚缓存（我这没用，但标准答案里有，就写一下）环境变量添加到用于启动调试器的运行配置中。（3）在调试的时候不要去修改代码。原因：debug的过程中修改代码。
2023-04-25 17:40:14
600
原创 数据结构算法刷题（14）LRU算法、LFU算法
if self.minfreq == freq and len(self.cache[freq]) == 0:#当前key的频率是最小频率，而且cache中该频率的value是空。：将现有 key 移动到有序字典的任一端。if len(self.key_and_freq) == self.capacity: #缓存满，要删freq最小且最近不出现的key。self.key_and_freq = collections.defaultdict() # 记录key值和当前key出现的频率。
2023-04-20 14:06:09
214
原创 数据结构算法刷题笔记（13）栈、队列的应用
res[i] = -1 if len(stack) == 0 else stack[-1] #上一个循环结束后，如果栈中仍有元素，说明该栈顶比当前元素大，写入res相应位置，如果栈空，则写入-1。while queue and nums[queue[-1]]
2023-04-18 21:06:00
104
原创 数据结构算法刷题（11）田忌赛马
田忌赛马的主要思想是：如果劣等马能够比得过齐王的劣等马，就直接得分，如果比不过，就让它对阵齐王目前的最优马（挑最好的送人头）将田忌的马nums1递增排序，用劣马对抗劣马，如果对抗不过就去齐王的最优马处送人头，然后right++，换剩下元素的最优值。nums2[b[left]]就表示nums2中的最小值，nums2[b[right]]就表示nums2的最大值。res[b[right]] = i #将该值写入nums2最大值的的位置。res[b[left]] = i #将该值写入有优势的下标处。
2023-04-18 10:30:51
163
原创 数据结构刷题（10）二分搜索题型（python实现）
对于该题目的分析就是找到最小的装载能力k，船舶最大的装载能力high应该是sum(weights)，也就是一天可以把全部货物送达。由此我们确定二分法雏形，吃一堆香蕉最快的速度是max(pile)，因为题目中说每个小时会挑一堆来吃，就算提前吃完也不会吃下一堆，所以最快的速度是这一堆中最大的元素。对于该问题，我们要求最小速度k,在最小速度k下计算吃完这一堆香蕉的时间：sum+=math.ceil(piles[i]/k) （根据题目要求，向上取整）day = 0 #计算当前装载能力k下的运输天数。
2023-04-17 16:59:53
123
空空如也
空空如也
TA创建的收藏夹 TA关注的收藏夹
TA关注的人