我太菜了

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

221. Maximal Square

我太难了

同是天涯沦落人 相逢何必曾相识 C++，动态规划。 这里使用二维数组dp，然后 dp[i][j]记录以该元素为右下角的最大正方形的边长，于是就有了转换公式： \[dp[i][j]=\left\{ \begin{aligned} min(dp[i-1][j-1], dp[i-1][j], dp[i][j-1]) + 1 & & matrax[i][j] = ...

Posted by bbkgl on November 22, 2019

215. Kth Largest Element in an Array

我太难了

林花谢了春红 太匆匆 无奈朝来寒雨晚来风 C++，topK问题，快排的分治思想。 按照推理来说，平均复杂度应该是O(N)，最差O(N^2)。 简单来说思路就是： 随机在范围内指定一个元素X 将比元素X小的移到左边，将比元素X大的移动到右边 得到新的X的位置，假设为XPOS 然后分三种情况： 如果XPOS位于倒数第K位，就说明...

Posted by bbkgl on November 21, 2019

208. Implement Trie (Prefix Tree)

我太难了

醉后不知天在水 满船清梦压星河 C++，字典树，实际上本题目就是创造一颗字典树。 创造一颗字典树其实是很简单的，直接构造多叉树就好了，首先得确定多叉树的结点应该是这样的： struct Node { vector<Node *> nexts; char value; bool has_end; ...

Posted by bbkgl on November 20, 2019

207. Course Schedule

我太难了

一霎荷塘过雨 明朝便是秋声 C++，图，拓扑排序。 很经典的拓扑排序题，有向图，判断是否有环。 需要修完所有预修课，才能修当前课，就相当于图中要遍历所有前置结点，才能遍历当前结点，这就是拓扑排序。 思路也很简单： 建立邻接表，使用vector很容易建立 记录所有的入度，即rudu[i]++ 进入循环，深搜遍历所有入度为0的结点 深搜...

Posted by bbkgl on November 19, 2019

200. Number of Islands

我太难了

夜静不堪题绝句 恐惊星斗落江寒 C++，连通图数量，dfs/bfs。 很常见的图论题，求连通图的数量，深搜和广搜都可以。 这里说一个很常用的技巧，是以前准备PAT看别人题解的时候学到的。 利用dx，dy实现四个方向的移位操作。 int dx[] = {1, -1, 0, 0}; int dy[] = {0, 0, 1, -1}; for (int i = 0; i &...

Posted by bbkgl on November 17, 2019

英语单词记录

我太难了

桃李春风一杯酒 江湖夜雨十年灯 记录英语单词啦。 2018-06（1） experts：专家 originally：本来 newsletter：通讯 chronicles：编年史 fascinates：着迷 hypothesis：假设 m...

Posted by bbkgl on November 16, 2019

152. Maximum Product Subarray

我太难了

一叶叶 一声声 空阶滴到明 C++，数组，我觉得不算动态规划。 这个题目感觉不像动态规划，更像“最大子列和”的那种“在线处理”的解法。 如果之前有理解过“在线处理”算法的话，就能比较容易地解出这道题了。 首先假设存在某个最大乘积，然后对数组遍历，在经过每个元素的时候，有以下四种情况： 如果该元素为正数： 如果到上一个元素为止的最大乘积...

Posted by bbkgl on November 16, 2019

148. Sort List

我太难了

借问江潮与海水 何似君情与妾心 C++，链表+排序，非递归，时间O(nlogn)，空间O(1)。 这里使用归并排序的非递归版本实现，说实话leetcode的medium很少有写这么长的。 其实就是归并排序，然后对链表进行排序的话，自然而然的会想到用非递归。 归并排序对于数组而言，是需要借助O(n)的辅助空间的，因为合并两个数组的时候需要储存中间结果，就会用到临时数组。 ...

Posted by bbkgl on November 15, 2019

Insertion Sort List

我太难了

山之高 月出小 月之小 何皎皎 我有所思在远道 一日不见兮 我心悄悄 C++，链表题，在链表上实现插入排序。 仔细一想就发现了在单链表上排序的难处，因为单链表只能往后遍历，而不能往前，因为只有next指针。 所以就想到了用map去记录每个结点的前一个结点，需要注意的是排序的时候要如果改变了next的指向，那必然也要对应修改map。 于是就按数组的类似操作去操...

Posted by bbkgl on November 9, 2019

LRU Cache

我太难了

指上半生了了 人间万事茫茫。 C++，LRU页面置换算法实现。使用数据结构：std::list+std::unordered_map+std::pair。 这道题最重要的就是要想到用链表了，没想到的话就做不出来了。 因为只有链表才能做到插入/删除时间复杂度为O(1)，而std::unordered_map可以做到查询O(1)，自然能达到题目中的要求。 了解下面两个问题就...

Posted by bbkgl on November 8, 2019

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