WenlSun Blog

我干了什么 究竟拿了时间换了什么

差分数组题目总结

差分数组

最大重叠区间数(会议室II) 小猿非常热爱学习，所以他在猿辅导上购买了$N$节课来提升自己，每节课有一个开始时间$S$和结束时间$E$（$S$和$E$均用正整数表示）。买完课程后，粗心的小袁发现这些课程之间有些时间冲突，幸好小猿有一种“一心多用”的超能力，能同时兼顾$K$节课上课。当然是$K$越大，使用这种能力就越累。请问小猿最少需要一心几用，才能上完所有他买的课程呢？ 思路1：差分数组...

Posted by WenlSun" on August 19, 2020

前缀和题目总结

前缀和

和为k的子数组(中等) 给定一个整数数组和一个整数 k，你需要找到该数组中和为 k 的连续的子数组的个数。和为0的只是和为k的特殊情况。和为k的子数组 参考代码 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 cl...

Posted by WenlSun" on July 26, 2020

力扣HOT100题目及代码

力扣100

两数之和(简单) 给定一个整数数组 nums 和一个目标值 target，请你在该数组中找出和为目标值的那 两个 整数，并返回他们的数组下标。你可以假设每种输入只会对应一个答案。但是，数组中同一个元素不能使用两遍。两数之和 参考代码 1 2 3 4 5 6 7 8 9 vector<int> twoSum(vector<int>& nums, int t...

Posted by WenlSun" on July 14, 2020

线性dp题目总结

动态规划

连续子数组的最大和(简单) 输入一个整型数组，数组里有正数也有负数。数组中的一个或连续多个整数组成一个子数组。求所有子数组的和的最大值。时间复杂度：$O(n)$连续子数组的最大和 参考代码 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 int maxSubArray(vector<int>& num...

Posted by WenlSun" on July 13, 2020

博弈类dp题目总结

动态规划

除数博弈 爱丽丝和鲍勃一起玩游戏，他们轮流行动。爱丽丝先手开局。最初，黑板上有一个数字 N 。在每个玩家的回合，玩家需要执行以下操作：选出任一 x，满足 0 < x < N 且 N % x == 0 。用 N - x 替换黑板上的数字 N 。如果玩家无法执行这些操作，就会输掉游戏。只有在爱丽丝在游戏中取得胜利时才返回 True，否则返回 false。假设两个玩家都以最佳状态参与...

Posted by WenlSun" on July 13, 2020

优化算法总结

优化算法

各优化算法的优缺点整理 梯度下降算法 一维梯度下降算法 \[x_t=x_{t-1}-\eta f'(x)\] 根据泰勒展开公式，可以得到下面的近似 \[f(x+\epsilon )\approx f(x)+f'(x)\cdot \epsilon\] 这里$f’(x)$是f在x点处的梯度，一维函数的梯度是一个标量，即导数。 多维梯度下降算法 \[\boldsymbol {x :...

Posted by WenlSun" on July 5, 2020

经典面试题总结

面试题

高效寻找素数 统计所有小于非负整数 n 的质数的数量。计数质数 参考代码 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 int countPrimes(int N) { vector<bool> isPrime(N + 1, true); // 判断一个数n是否是素数，只需要判断[1,sqrt(n)]中有没有...

Posted by WenlSun" on June 29, 2020

拓扑排序算法模板及相关题目

拓扑排序

拓扑排序（Topological Sorting）是一个有向无环图（DAG, Directed Acyclic Graph）的所有顶点的线性序列。且该序列必须满足下面两个条件：1. 每个顶点出现且只出现一次。2. 若存在一条从顶点 A 到顶点 B 的路径，那么在序列中顶点 A 出现在顶点 B 的前面。有向无环图（DAG）才有拓扑排序，非DAG图没有拓扑排序一说。 拓扑排序算法模板 c++...

Posted by WenlSun" on June 24, 2020

并查集算法模板及相关题目

并查集

并查集是一种可以动态维护若干个不重叠的结合,并且支持合并与查询的数据结构.也就是擅长维护各种各样的具有传递性质的关系.基本操作： Find 操作，查询一个元素所属哪一个集合。 Union 合并操作，把两个集合合并成一个集合。 并查集算法模板 c++版本代码 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 2...

Posted by WenlSun" on June 22, 2020

回溯深搜广搜题目总结

回溯深搜广搜

电话号码的字母组合(中等) 给定一个仅包含数字 2-9 的字符串，返回所有它能表示的字母组合。电话号码的字母组合 参考代码 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 vector<string> res; vector<string> letterCombinations(string digits) ...

Posted by WenlSun" on June 19, 2020

FEATURED TAGS
笔记 算法 Object Detection 算法模板 pytorch 笔经 动态规划 面经 面试题 C++ Vim
ABOUT ME

For the next quantum leap
离开世界之前，一切都是过程

FRIENDS