菜鸡的博客 | WTCL

315. Count of Smaller Numbers After Self

315. 计算右侧小于当前元素的个数

明月不谙离恨苦斜光到晓穿朱户以前刷PAT的时候经常能做到二叉搜索树的题了，现在刷leetcode蛮难遇到的。理解这道题能用BST做的关键在于理解插入顺序应该是倒序。首先肯定的是，可以利用BST的特性，在树中每次插入结点时，都更新各个结点 “索引大于该结点且值小于该结点的个数”，即遍历每个位于该结点右侧的结点，修改右侧每个结点的“索引大于该结点且值小于该结点的个数”...

Posted by bbkgl on July 11, 2020

面试题 17.13. Re-Space LCCI

面试题 17.13. 恢复空格

我心匪石不可转也 dp题，算是少有的能不看任何提示、评论和题解就写出来并一次AC的题了。简单来说，用dp[i]表示sentence前i个字符中，能够被识别的最多字符数。如果字典中存在一个长度为len的字符串s，且满足s == sentence.substr(i, len)那么就有： dp[i - 1 + len] = dp[i - 1] + len 不过记得一...

Posted by bbkgl on July 9, 2020

662. Maximum Width of Binary Tree

662. 二叉树最大宽度

世间无限丹青手一片伤心画不成题目还是蛮简单的，以前这个层序遍历我都是用递归。。。其实dfs代码很短，也更好理解，但我怕自己忘了bfs了，就写一次2333。一般来说，这种要求统计某一层信息的，需要利用额外的东西记录层数信息，所以这种情况下递归就很合适，进入下一层递归就意味着到了树的下一层结点。同时也需要掌握父子结点之间的一些联系，比如在完全二叉树中，按照从上到下...

Posted by bbkgl on July 8, 2020

31. Next Permutation

31. 下一个排列

数学结论：字典序法中，对于数字1、2、3……n的排列，不同排列的先后关系是从左到右逐个比较对应的数字的先后来决定的。例如对于5个数字的排列12354和12345，排列12345在前，排列12354在后。按照这样的规定，5个数字的所有的排列中最前面的是12345，最后面的是54321。字典序算法如下：设P是1～n的一个全排列:p=p1p2……pn=p1p2……pj-1pjpj+1……p...

Posted by bbkgl on July 8, 2020

https的知识整理

https

荷风送香气竹露滴清响看了最近大家的面经，感觉现在https已经成了必问的一部分了。当然现在因为要睡觉了，我还是只简单过一下内容。请求流程为了快速清楚描述流程，先用一张图：简单来说，原来的TCP其实是3次握手，实际在3次握手成功以后，还需要进行一次握手，就是在使用非对称加密的情况下，如何让客户端如何获得公钥，且能够让客户端判断出服务器是真实的还是黑客。 ...

Posted by bbkgl on July 5, 2020

289. Game of Life

289. 生命游戏

我且为君槌碎黄鹤楼君亦为吾倒却鹦鹉洲原地哈希2333。 class Solution { private: static int dx[8]; static int dy[8]; inline void check_for_alive(vector<vector<int>> &board, int i, int ...

Posted by bbkgl on July 3, 2020

378. Kth Smallest Element in a Sorted Matrix

378. 有序矩阵中第K小的元素

一身转战三千里一剑曾当百万师这个题目还蛮有意思的。按值二分而不是按索引二分。首先设想一个场景，在如下的矩阵中： [ 1, 5, 9] [10, 11, 13] [12, 13, 15] 如何快速找到矩阵中<= 14的数的个数呢？找的方法可以参考剑指offer：二维数组中的查找。有两种找法，从左下角或者是右上角，比如从右上角开始，那样就往左下角移...

Posted by bbkgl on July 2, 2020

718. Maximum Length of Repeated Subarray

718. 最长重复子数组

故国三千里深宫二十年动态规划，用dp[i][j]表示以A[i]以及B[j]为结尾的子串的公共串的长度。则很显然有公式： dp[i][j] = A[i] == B[j] ? dp[i-1][j-1] + 1 : 0; 所以代码也很简短，复杂度O(N^2)，完全可以接受！ class Solution { public: int findLength(vect...

Posted by bbkgl on July 1, 2020

199. Binary Tree Right Side View

199. 二叉树的右视图

同心而离居忧伤以终老其实就是层序遍历的时候，每一层直接取最后遍历的元素。。。现在一想到层序遍历，我就习惯用dfs了。。。 class Solution { private: void dfs(TreeNode *root, vector<int> &ans, int depth) { if (root == nullptr...