我太菜了

喜欢写Hello World的未来程序员.

215. Kth Largest Element in an Array

215. 数组中的第K个最大元素

立如芝兰玉树 笑如朗月入怀 很多人是直接排序的2333。还是那句话，希望这样的老哥多一点，这样我在找工作的时候会轻松一点。 面试的时候经常被问到topK的问题，topK就能够用快排的partition来解，这道题也是内味。 每次调用partition，都能确定出整个数组中某个元素的位置。。。根据这个功能，就可以递归地缩小范围，直到某次调用partition时确定的某个元素...

Posted by bbkgl on June 29, 2020

209. Minimum Size Subarray Sum

209. 长度最小的子数组

落花人独立 微雨燕双飞 双指针，也可以说是滑动窗口。 双指针比较难理解的地方在于，怎么确定这两个下标移动的时候不会漏掉可能最优的情况。 一般来说对于有序数组，我们要找到某个和，可以用双指针中的左右指针。同样这次也是要找某个满足条件的和，所以首先就是要构造前缀和数组，这样直接就能根据差确定某段连续元素的和。 然后就是用双指针维护一个最小的窗口，如果前缀和的差小于S，则需要...

Posted by bbkgl on June 29, 2020

983. Minimum Cost For Tickets

983. 最低票价

二八笙歌云幕下 三千世界雪花中 使用dp解本题的关键在于理解 如果今天发现7天前买周票，则到今天的总消费最低这件事，不会改变昨天的最低总消费，也不会改变前天的最低总消费，当然也不改变之前任何一天的最低总消费。换句话说，完全可以当作，如果一周前买了周票，则最后结算的那天才算钱，前面都不算钱！！！。 题目本身是很简单的，理解我刚刚说的那部分。。。这个就是最简单的dp题，不需要任...

Posted by bbkgl on June 28, 2020

41. First Missing Positive

41. 缺失的第一个正数

化蝶去寻花 夜夜栖芳草 在评论里说看到一个词“原地哈希”，感觉非常贴切呀。。。做过类似的这种题不少了，很多时候规定常数的空间复杂度，我都会采用“标记为负数”等方式记录额外信息，感觉类似的方式都可以称作“原地哈希”。 这道题的话，如果允许用额外空间，那简直不要太简单，直接开个数组就完事，评论区也会看到类似这样的做法。作为参与互联网内卷的一颗韭菜苗，我由衷地希望这样的同学能够多...

Posted by bbkgl on June 26, 2020

974. Subarray Sums Divisible by K

974. 和可被 K 整除的子数组

从此无心爱良夜 任他明月下西楼 一开始我就想到了前缀和，通过前缀和的差可以很快确定某段连续元素的和，能够被K整除的和就能满足条件。 不过问题就在于这样子的复杂度是O(N2)，我感觉是过不去的。 看了评论区才发现同余定理这个“显而易见”的定理。 简单来说就是如果(a - b) % k == 0，则a % k == b % k。 如果存在多个取模相等的数，则按照顺序两两组...

Posted by bbkgl on June 26, 2020

45. Jump Game II

跳跃游戏2

我有所感事 结在深深肠 贪心，每次跳跃都选择加上第二次跳跃距离后，和最远的哪个台阶。即选择j + nums[j]最大的那个台阶j，且j能够从i的位置跳到。。。 当然一开始我还是用dp做的，跳台阶第一反应就是dp。 但是dp会超时。 class Solution { public: int jump(vector<int>& nums) { ...

Posted by bbkgl on June 26, 2020

210. Course Schedule II

210. 课程表 II

世间无限丹青手 一片伤心画不成 拓扑排序，这题今年春招实习两次面到，一次wxg，一次阿里云，不过最后都没去2333。 第一次见到这道题，是2018年准备保研的时候，刷PAT甲级刷到的，反正当时都是做不出来的，都得看别人的题解才能想到这个道题是拓扑排序。 当然这道题也不是直接拓扑排序，需要先建立有向图。有向图可以用二维数组，也可以用邻接表，这个看个人喜好了。 简单讲下步骤...

Posted by bbkgl on June 26, 2020

139. Word Break

单词拆分

幸对清风皓月 苔茵展 云幕高张 这种一看就是dp的题，我都直接先用暴力dfs解一遍，暴力思路：每次匹配遍历wordDict中所有的单词，然后取到合适的单词（能够匹配上字符串的开头），就将字符串的开头去掉，然后进入下一层函数。。。最后字符串为空，就返回true，如果遍历wordDict中所有的单词，没有能够匹配字符串开头的，就直接返回false。 代码比较简洁，缺点就是...

Posted by bbkgl on June 25, 2020

990. Satisfiability of Equality Equations

990. 等式方程的可满足性

我梦扁舟浮震泽 雪浪摇空千顷白 其实就是图中计算两点是否连通。。。 在leetcode中碰到的图论题不算多，这次也算一个，应该也可以用并查集来做。 我们可以用提供的所有等式来建立图，然后用所有的不等式验证两点之间的连通性。 取出所有的等式建立图，其中每个顶点就是变量，变量最多26个，如果两个变量之间存在直接的相等关系，则建立无向边。 后面就是验证不等式顶点之间的连通性...

Posted by bbkgl on June 23, 2020

面试题 16.18. Pattern Matching LCCI

字符串匹配

侯门一入深如海 从此萧郎是路人 字符串匹配题。。。 题目如果简化一下，已知a对应的字符串的长度len_a以及数量cnt_a，b对应的字符串的长度len_b以及数量cnt_b，这样是不是就能很快求解出a对应的字符串是什么以及b对应的字符串是什么，然后再判断是否match。。。 因为cnt_a以及cnt_b在pattern中可以得到，所以问题就变成了，如果求解a对应的字符串的...

Posted by bbkgl on June 23, 2020

FEATURED TAGS
Blog leetcode C++ 剑指offer http Raft Linux Hadoop 设计模式 CV 链表 动态规划 图 拓扑排序 快排 二叉树 leveldb 数学 数组 二分 dfs profile hash表 字符串 贪心 01背包 最小堆 单调栈 luajit 计算机网络 操作系统 共享内存 linux 原地哈希 双指针 滑动窗口 UE4 编译原理
ABOUT ME

写过Hello World, 下过矿。

✉️ zoujiakun@zju.edu.cn

FRIENDS