- 博客(87)
- 收藏
- 关注
RSS订阅原创 【力扣岛屿数量】时间复杂度分析
可以从每个网格被触发的次数考虑， 一个网格只可能被上下左右四个网格做dfs时被触发，由于每个网格最多往周边扩散一次dfs，所以一个网格最多被周围四个网格触发四次，除此之外还有在外层全遍历中的一次。因此一个网格最多被触发五次，为常数项，所以时间复杂度为o(m*n)
2023-05-12 12:32:52
160
1
原创 waymo数据集总结
其中，top lidar为64线的mid-range（maximum of 75 meters），出点数为1w左右。其余lidar为short-range（maximum of 20 meters）。每个frame提供的是range image list(len=5)的形式。可以通过waymo官网提供的api转化成points list(len=5)，然后再contact，总点数为12w左右。5个激光雷达+5个摄像头。
2022-10-12 11:08:28
557
原创 【上/下一个排列】找断层+找紧邻+交换+逆排列
从右往左找第一个非递增，然后在区间从右往左找第一个比它大的，替换+逆序。从右往左找第一个非递减，然后在区间从右往左找第一个比它小的，替换+逆序。【注意】不等于逆序后做下一个排列后再逆序回！
2022-09-03 22:27:43
114
原创 【华为机试】工单题
这个问题一直放在我的 todo list里，今天还是靠陈博大佬给整出来了。题目大概意思是，有一批工单号，每个工单有一个时效SLA，也有一个得分score，每处理一个工单耗时一个单位。问应如何按时间处理这些工单号使得收益最大。牛客网找的样例：错误思路在机试的时候立马想到的是优先处理快过期的，即按时间排序，时间相同的按得分降序。然后沿时间处理，累计得分。但是样例一直只能通过45，百思不得其解，后来牛客网看到有大佬说下面这种情况所以说并非每次优先处理即将过期的，因为可能有稍晚过期但得分高的工单
2022-05-12 22:55:54
283
原创 【前缀+动规】头脑风暴之区间摘果实
题目有一天小明要去果园里采摘果子，果子是直线分布的，已知所有果子的一维位置，小明的采摘机最多能采摘区间长度为k的所有果子，也就是说，假设采摘机左端位于x，则能摘完区间[x, x+k]的所有果子。小明的采摘机能开启两次，请问小明最多能摘到多少果子。第一行表示果子数量和采摘机的区间范围k第二行代表每个果子出现的位置样例输入：7 11 5 2 3 1 5 4样例输出 6思路对所有果子按位置排序后，遍历得到以任意位置为起始位置采一次果子的最大值。因为小明能够采摘两次，那么可以枚举第一次采摘的
2022-05-11 23:26:34
139
原创 【数组循环移位】的四种解法
将一个数组循环左移k位，返回移动后的数组。其中，循环左移的含义为：原nums = [1, 2, 3, 4, 5, 6, 7, 8, 9, 10]，循环左移k位后，nums = [5, 6, 7, 8, 9, 10, 1, 2, 3, 4]。常规解法1：拷贝时间复杂度o(n)，空间复杂度o(n)新开辟一个数组，从原数组中拷贝。常规解法2：k次移位时间复杂度o(kn)，空间复杂度o(1)经过k次循环移位1位技巧解法1：转置时间复杂度o(n)，空间复杂度o(1)将目标以k为分界线，分为前半部分
2022-04-25 19:05:28
2001
原创 【腾讯笔试】一元三次方程求根 —— 万能的二分
一元三次方程，若已知必有一正实根，求根（若有多个根只需求任意一个）二分解法数值法，用二分去逼近解的区间，高中数学流程图那章有类似的题。对于区间[a,b]，若满足下式，则区间内必有一根。对于必有一根的区间[a,b]，可以如下所示用二分去缩小区间。停止条件为解的误差（即区间长度）小于某值或者解代入函数十分接近0。核心代码如下：ans = 0while (r-l) > 10**(-7): mid = (l+r)/2 fmid = f(mid, a, b, c) i
2022-04-24 22:57:40
371
原创 力扣随机数randX——透过现象看本质之二元独立随机分布
用randX 实现 randY（X < Y）其中，randN表示等概生成[1，N]的数从一个力扣上的例子来引入吧470. 用 Rand7() 实现 Rand10()最直观的想法是用rand7()+rand7()-1去生成[1, 13]的数，然后只取[1, 10]，但实际上这里的每个数并不是等概的，例如1的概率是1/49（1+1），但10的概率是4/49（4+7，5+6，6+5，7+4）。所以该方法并不可行。事实上，可以把第一个rand7()和第二个rand7()分别看成两个维度，假设分别为A
2022-04-23 21:09:31
723
原创 【突然科研】解决分布式训练时突然断开并报错
今天在训模型时突然报错查了一下可能是内存问题，但有观察显存一直是比较稳定的。请教了一下群里的大佬可能是cpu内存不足，进程被系统杀掉。因为终端没有输出详细报错信息，大佬建议我去/var/log下查系统日志【凡是被系统kill的都会写进系统日志里的】通过命令sudo egrep -i -r 'killed process' /var/log或者用专门的dmesgsudo dmesg|grep -i kill | less查到：果然是内存不足被杀了，然后top看了一下果然cpu被占满了
2022-04-13 23:05:51
571
1
原创 【突然炼丹】模型加载预训练权重
最近被找实习搞累了突然开始炼丹？？？场景：在centerpoint里面加了个小模块。之前有原网络训练好的权重，与当前网络并不完全匹配（当前网络有新加的层，也有去掉的原网络的部分层）。现在不希望从头开始训，希望使用原网络的部分权重。。。我用reusme_from 加载，但报错说。“ValueError: loaded state dict contains a parameter group that doesn’t match the size of optimizer’s”可以看到网络层不匹
2022-04-11 20:59:31
439
1
原创 【摆动序列】合集
这里写自定义目录标题欢迎使用Markdown编辑器新的改变功能快捷键合理的创建标题，有助于目录的生成如何改变文本的样式插入链接与图片如何插入一段漂亮的代码片生成一个适合你的列表创建一个表格设定内容居中、居左、居右SmartyPants创建一个自定义列表如何创建一个注脚注释也是必不可少的KaTeX数学公式新的甘特图功能，丰富你的文章UML 图表FLowchart流程图导出与导入导出导入欢迎使用Markdown编辑器你好！ 这是你第一次使用 Markdown编辑器 所展示的欢迎页。如果你想学习如何使用Mar
2022-04-10 09:34:37
261
原创 美团面试手撕 —— 往集合S中加入最少的数，使得集合T达到要求，那些我当时被冲昏了头脑的题
给定一个集合S， S到集合T的映射是S中的元素任意组合之和构成的集合。现在可以往S中加一些数，使得集合T能覆盖1至N，求加数的最少的个数。分析：1. 先通过一个例子来体会其中的规律假设S = {2, 3, 5}，首先1必须加进去，1的加入使得集合变成了S1 = {1, 2, 3, 5}，此时的T = {1,2,3,4,5,6,7,8,9,10,11}，即T的区间为[1, 11]，此时还不能达到目标。若想达到[1, 20]，再往其中加任意一个大于位于区间[9, 12]的数都可以达到目标【因为小于9无法.
2022-04-02 23:25:50
178
原创 莉莉丝笔试题之 N的阶层 末尾0的个数 —— —— 数学推导得到递归式
莉莉丝笔试第一题，上来就被吓一跳，肯定不能暴力，要去找规律末尾想要0，只能靠 2 × 5，思考一下n！中2的因子数肯定比5的因子数要多。因此着重考虑5的因子数就可。n = int(input())res = 0while n: res += n // 5 n //= 5print(res)...
2022-04-01 22:50:00
689
原创 面试题— —从很长的数据流等概率随机采样的两种实现方法
从很长的数据流等概率随机采样“给出一个数据流，这个数据流的长度很大或者未知。并且对该数据流中数据只能访问一次。请写出一个随机选择算法，使得数据流中所有数据被选中的概率相等。” 在搜索引擎等相关领域也会被问到哦假设数据流长度为n，那么我们希望数据流中的每个数据都是以 1/n 的概率返回。相关题目：382. 链表随机节点398. 随机数索引不合适的但容易想到的两种方法：直观的做法是生成一个 1-n 的随机数 i，代表我们想取第 i 个数据。但是这个前提是我们知道了数据流的长度。通常来说，数据
2022-03-29 12:01:48
1527
原创 美团面试—手撕numpy之fps点云最远点采样实现
FPS没有想到不按套路出牌的美团今早就撕了这个。点云最远点采样，从一堆点集中选出一些点，使得他们尽可能地远离。这样采样出来的点能比较好的表征整个轮廓。在pointnet++中就用到过。整体思路是：分别维护一个已选取和待选取的点云集合。先从点云集合中选出一个点，然后计算其余所有点到该点的距离，距离最大的那个点是下次要加入的点。当pick集合中有多个点时，距离的定义为到集合每个点距离中的最小距离。关于距离的计算：维护一个distance列表，对于每次pick出来的点，去更新distance。可以利用
2022-03-26 21:35:41
5203
2
原创 手撕之numpy实现ROC和PCR曲线，同时计算AUC和MAP
ROC与AUC### 计算AUC## 对于正样本N和负样本M， 枚举正负样本对(Ni, Mj)，如果正样本分值大于负样本，则+1，相等则+0.5，小于则不加分，再用总分除以N*Mimport numpy as npimport matplotlib.pyplot as pltdef AUC(pre, label): label = label == 1 print(label) pos = pre[label] neg = pre[~label] pos
2022-03-21 16:45:13
2084
原创 python并查集模板
1319. 连通网络的操作次数class UnionFind(): def __init__(self, n): self.parent = list(range(n)) self.setcnt = n ## 连通分量数 self.size = [1]*n ## 每个连通分量的大小 def findset(self, x): if self.parent[x] == x: return x
2022-03-20 17:59:20
1170
2
原创 力扣之数组重复/缺失/超过一半的元素题解大全【持续更新】
最近刷力扣总能碰到各种关于数组数字元素的题目，而且这些题基本都有很多巧妙的多重解法，博主自己想不出，只能靠大量的记录了。287. 寻找重复数不考虑题目的限制条件，立马想到的解法是:①边遍历边加入set, 直到出现一个原本就存在set中的元素②遍历并交换数组元素到相应位置上[数字x应填入下标x-1中], 直到出现一个元素与相应位置相等, 就找到了重复元素了但是以上解法1需要用到额外的o(n)空间, 解法2需要修改原数组, 都不满足条件…这时猪脑过载了, 只能去看大佬解析解法一: 二分查找仔.
2022-03-18 20:33:02
435
原创 背包变种的动规问题【持续更新】
动态规划问题(背包问题)的精髓就是枚举所有可能情况,为转移做准备一、满减凑单问题:在凑够满减条件的前提下，让选出来的商品价格总和最大程度的接近满减条件与leetcode416有异曲同工之妙。用布尔变量dp[i][j] 代表是否存在一种方案:使用前i件商品使得总价为j。# 4 30# 18 20 22 21n, Y = map(int, input().split())cost = list(map(int, input().split()))# y = sum(cost) ## 可以.
2022-03-17 22:38:08
378
原创 二叉树的前/中/后序遍历,递归+栈迭代实现[同门说今天字节刚面迭代版]
递归版本很简单就直接贴下代码了:前序## 递归实现class Solution: def preorderTraversal(self, root: Optional[TreeNode]) -> List[int]: if not root: return [] return [root.val] + self.preorderTraversal(root.left) + self.preorderTraversal(root.right)中序##
2022-03-16 21:41:54
918
原创 美团笔试3.12— —只要你够贪心
题目一：n个房间（0<n<=10)，初始的时候A在第一个房间，现在有一个游戏，游戏时长为m（0<m<=10000)秒，给出m秒每秒的炸弹所在的房间，A需要在每秒避开这些炸弹，也就是A不能在有炸弹的房间。A可以在每秒后选择移动到n个房间中的一个，但是需要消耗1个能量，当然也可以不移动，问A最少需要消耗多少能量。样例输入：n=2, m=4, bursts=[2,1,1,2]；样例输出：2解题思路：有人说dp但我同门想出了贪心，只需遍历一次。贪心体现在：在炸弹💣爆炸的
2022-03-12 21:58:57
1825
原创 神经网络必面之手撕 —— IOU、NMS、正向卷积、池化、BN【持续更新】
一、IOU：import numpy as npdef ComputeIOU(boxA, boxB): ## 计算相交框的坐标 x1 = np.max([boxA[0], boxB[0]]) x2 = np.min([boxA[2], boxB[2]]) y1 = np.max([boxA[1], boxB[1]]) y2 = np.min([boxA[3], boxB[3]]) ## 计算交区域，并区域，及IOU interAre
2022-03-10 18:02:41
7882
4
原创 回溯大全【持续更新】
回溯本质上是靠递归实现的一种暴力搜索。基本思想是：尝试，如果不满条件就回溯，继续尝试，不满足就回溯，……如此反复，知道搜索完所有的解空间。尝试代表着一次选择，可以基于不同选择展开成多个解空间（树），到达叶子节点则代表找到一组解，但此时算法并未终结，依旧要向上回溯去尝试其他的解，直到遍历所有的可能情况。回溯有一个好处是可以剪枝，通过约束条件，去除不可能的尝试（解空间），缩小搜索范围。递归的题目：77.组合（组合问题）78.子集（子集问题）90. 子集 II（子集问题）46.全排列（排列问题）51.
2022-03-01 11:45:41
93
原创 面试必问——python中的赋值、浅拷贝、深拷贝
总结直接赋值：其实就是对象的引用。浅拷贝(copy)：拷贝父对象，不会拷贝对象的内部的子对象（采用同一引用）。深拷贝(deepcopy)：copy 模块的 deepcopy 方法，完全拷贝了父对象及其子对象。引用在python中，每个对象都会在内存中申请开辟一块空间，使用变量名引用该空间地址。可变对象：允许其在引用空间不变的情况下修改对象的值。如，列表、字典、集合不可变对象：具有固定值的对象，若要改变其值，必须重新创建一个对象引用。如，数值型、布尔型、字符串、元组可使用id(
2022-02-23 16:47:55
480
原创 力扣刷题之单调栈【持续更新】
单调栈一般能化时间复杂度o(n^2) -> o(n)，很巧妙leetcode中相关题目有：739. 每日温度84. 柱状图中最大的矩形402. 移掉 K 位数字316. 去除重复字母581. 最短无序连续子数组
2022-02-21 17:03:21
105
原创 队列、栈的互相实现及快速获取最大最小值等相关问题汇总
1.两个栈实现一个队列JZ9：用两个栈实现队列思路：不用每次出队完后都把栈B的元素倒腾回栈A。而是依照以下原则：入队都进栈A，出队都从栈B出，一旦要出队但栈B为空，就将栈A元素依次弹出并入栈B复杂度分析：由于每个元素都经历了进A出A和进B出B，因此时间复杂度o(n)，空间复杂度o(n)代码实现：class Solution: def __init__(self): self.stack1 = [] self.stack2 = [] def pu
2022-01-18 22:40:23
527
原创 动态规划专题【持续更新】
题目一： 机器人走无障碍物的方格的不同路径个数leetcode62. 不同路径解题思路典型的递归: f(m,n) = f(m-1,n) + f(m,n-1)，到达当前位置的所有路径可以来自上面一格的down，也可以是左边一格的right。# 开辟一个dp内存，空间复杂度o(m*n)class Solution: def uniquePaths(self, m: int, n: int) -> int: dp = [[1]*n for i in range(m)]
2022-01-07 21:16:55
762
原创 剑指 day 12【JZ59 滑动窗口的最大值】滑窗集锦
解题思路分析: 这道题是滑窗中的最大值, 和之前的从头开始的最大值有所不同, 从头开始的可以永远保留此刻的最大值,新的最大值只会在新加入的元素和原最大值中产生。然而这道题的滑窗会让左边的元素出窗, 那么就可能导致原来的最大值过期, 因此比较复杂。暴力解法:对于每一次的窗都遍历一遍得到最大值。时间复杂度o(n*k), 空间复杂度o(1)优化暴力:不是每一次都去遍历窗, 而是维护一个最大值及其索引, 只有当最大值的索引超出了窗范围才去重新遍历窗得到新的最大值。时间复杂度o(n)-o(n*k), .
2021-12-24 11:34:11
427
原创 剑指 day 11【JZ38 字符串的排列】深入理解递归
解题思路递归思想: n个字符的排列可以转化为 先从n个字符当中pick出一个,然后再对剩余n-1个全排列。例如: abcd, f(‘abcd’) = [‘a’ + f(‘bcd’)] + [‘b’ + f(‘acd’)] + [‘c’ + f(‘abd’)] + [‘d’ + f(‘abc’)]找到这种前后递归关系后, 就可以轻松写下如下代码。但需要注意的是, 可能会有如下重复的情况出现, 因此, 用set来添加新排列。class Solution: def Permutation(se.
2021-12-23 11:00:56
341
原创 数据结构之二分查找及其变种
二分查找某元素值def binary_find(arr, x): st, ed = 0, len(arr)-1 while st <= ed: mid = (st+ed)//2 if arr[mid] == x: return mid # 找到并返回索引 elif arr[mid] > x: ed = mid - 1 else: st
2021-12-20 11:30:28
996
原创 python的一些高效率写法【持续更新】
Python列表解析配合if else[i for i in range(k) if condition]：此时if起条件判断作用，满足条件的，将被返回成为最终生成的列表的一员[i if condition else exp for exp]：此时if…else被用来赋值，满足条件的i以及else被用来生成最终的列表print([i for i in range(10) if i%2 == 0])print([i if i == 0 else 100 for i in range(10)])
2021-12-19 12:45:02
565
原创 数据结构之二叉树的递归应用大全【持续更新】
前言：在递归时，我们经常需要判断某个节点是否满足条件。当满足条件时，我们希望进行一系列的操作。例如统计满足条件的节点个数，或是记录路径等。最简单直白的办法是维护一个全局变量。但很多情况我们想直接用一个递归完成任务，而不去额外设置全局变量，这就要充分利用起递归函数传递参数和返回值。在这篇文章中，我们避免使用全局变量，而更多地介绍如何巧妙利用递归传参和设置返回值完成任务。在剑指offer中的相关题目有：JZ82 二叉树中和为某一值的路径(一)；JZ34 二叉树中和为某一值的路径(二)；JZ84 二叉树.
2021-12-18 11:33:08
519
空空如也
空空如也
TA创建的收藏夹 TA关注的收藏夹
TA关注的人