- 博客(208)
- 收藏
- 关注
RSS订阅原创 搬砖神器 VScode
记得在实验室的时候，有一位师兄是忠实 vim 党，鄙视一些 ide。的确，熟练掌握各种 vim 命令的大神，用起 vim 来可以秀得天花乱坠，vim 的轻巧也使得启动变得非常的轻易。不过 ide 也有 ide 的好处，就好比一把好的武器，能够使你更好的发挥你的功夫。即使你的功夫功底已经很深了，赤手空拳也能展示你的实力，但如果多一把好的武器，能够让你事半功倍，岂不是更美滋滋。
2022-09-03 21:49:35
1912
1
原创 leetcode hot100 之 找到所有数组中消失的数字
给定一个长度为 n 数组，其数字由 [1, n] 组成。在 [1, n] 当中，有重复出现的数字，也有从未出现的数字。请找出所有从未出现的数字。原题链接： https://leetcode.cn/problems/find-all-numbers-disappeared-in-an-array/由于所有数字均在 [1, n] 的范围内，我们可以通过打 tag 的方式来标记，一个数字是否出现。举个例子，比如数组 nums = [4,3,2,7,8,2,3,1]，长度 n = 8。对于数字 4，我们找到其下
2022-06-19 23:46:21
209
1
原创 leetcode hot100 之 完全平方数
给定一个数 n，返回和为 n 的完全平方数的最少数量。完全平方数指的是 一个整数，其值正好等于另一个整数的平方。如 1、4、9、16、25 等。原题链接：https://leetcode.cn/problems/perfect-squares/动态规划。先上公式再解释dp[i]=1+minj=1idp[i−j∗j] dp[i] = 1 + \min^{\sqrt i}_{j=1} dp[i - j*j] dp[i]=1+j=1minidp[i−j∗j]对于数字n，如果有某个数字 j，j * j
2022-06-19 23:16:03
169
原创 leetcode hot100 之 搜索二维矩阵II
题目给定一个矩阵和一个目标值，请判断目标值是否在矩阵当中。该矩阵有如下特征：每列从上往下升序排列；每行从左往右升序排列。输入：matrix = [[1,4,7,11,15],[2,5,8,12,19],[3,6,9,16,22],[10,13,14,17,24],[18,21,23,26,30]], target = 5输出：true原题链接：https://leetcode.cn/problems/search-a-2d-matrix-ii/思路从左下角开始出发，如果目标值比当前值小
2022-05-29 21:09:00
115
原创 leetcode hot100 之 除自身以外数组的乘积
题目给定一个数组 nums，返回一个数组 answer，其中 answer[i] 为 nums 除 nums[i] 外所有数字的乘积。输入: nums = [1,2,3,4]输出: [24,12,8,6]原题链接：https://leetcode.cn/problems/product-of-array-except-self/思路借用一下 Krahets 的图从上面的图可以看到，res[0] = (1) x (num[1] x num[2] x … x num[n-1])res[1
2022-05-29 17:20:12
1112
原创 leetcode hot100 之 最大正方形
题目给一个只包含 0 和 1 的 metrix 中，找到只包含 1 的最大正方形，返回其面积。输入：matrix = [[“1”,“0”,“1”,“0”,“0”],[“1”,“0”,“1”,“1”,“1”],[“1”,“1”,“1”,“1”,“1”],[“1”,“0”,“0”,“1”,“0”]]输出：4原题链接：https://leetcode.cn/problems/maximal-square/思路动态规划。这道题难点在于 找到转移方程。设 dp(i, j) 表示以 (i, j)
2022-05-29 15:51:06
104
原创 leetcode hot100 之 数组中的第K个最大元素
题目给定一个数组，找出数组中第K大。输入: [3,2,1,5,6,4] 和 k = 2输出: 5原题链接：https://leetcode.cn/problems/kth-largest-element-in-an-array/思路求 topK 是很经典的题目，经典的思路就是快排和堆排了。思路1快排思路。（非完整版快排）我们从大到小进行排列，在 partition 的过程中，如果分界值刚好在 k 的位置，则提前返回该分界值作为结果即可，如果分界值的坐标落在 k 往后的位置，则说明 to
2022-05-25 16:10:58
546
原创 leetcode hot100 之 实现 Trie（前缀树）
题目Trie（发音类似 “try”）或者说 前缀树 是一种树形数据结构，用于高效地存储和检索字符串数据集中的键。这一数据结构有相当多的应用情景，例如自动补完和拼写检查。请你实现 Trie 类：Trie() 初始化前缀树对象。void insert(String word) 向前缀树中插入字符串 word 。boolean search(String word) 如果字符串 word 在前缀树中，返回 true（即，在检索之前已经插入）；否则，返回 false 。boolean startsWi
2022-05-24 22:36:21
110
原创 大数据浅谈
对于一名算法工程师来说，大数据的应用也是技术栈之一。本文将以算法工程师，从大数据应用的视角，粗略浅显地做一些总括性的概述，作为自己学习的记录。大数据技术概览文件存储：Hadoop HDFS离线计算：Hive、Hadoop MapReduce、Spark流式计算：Flink、Storm、Spark StreamingKV、NoSQL 数据库：HBase、Redis、MongoDB日志收集：Flume、Kibana资源管理：Hadoop YARN、kubernetes(k8s)消息系统：Ka
2022-05-23 23:19:23
133
原创 leetcode hot100 之 移动零
题目给定一个数组，请将数组中的零移动数组末尾，并保持其他数字的相对顺序。输入: nums = [0,1,0,3,12]输出: [1,3,12,0,0]原题链接： https://leetcode.cn/problems/move-zeroes/思路直接遍历数组，不断地将非0数组移动到最前面，同时统计数组中 零 的个数。遍历完一遍数组后，再直接从数组末尾开始补相应的零即可。复杂度分析时间复杂度 O(n)。空间复杂度 O(1)。代码class Solution {publi
2022-05-23 15:37:49
132
原创 leetcode hot100 之 课程表
题目你这学习需要学习 numCourses 门课程，编号记为 0 到 numCourses - 1。在选修某些课程之前你需要完成一些必修课程。先修课程按 prerequisites 给出关系，如 prerequisites[i] = [a_i, b_i]，表示在选修 a_i 之前需要先完成 b_i。请判断你最终能否完成所有课程。示例1:输入：numCourses = 2, prerequisites = [[1,0]]输出：true解释：总共有 2 门课程。学习课程 1 之前，你需要完成课程
2022-05-23 15:05:42
106
原创 leetcode hot100 之 回文子串
题目给定一个字符串，请统计回文子串的数量。输入：s = “aaa”输出：6解释：6个回文子串: “a”, “a”, “a”, “aa”, “aa”, “aaa”原题链接： https://leetcode.cn/problems/palindromic-substrings/思路思路1动态规划。题目和《最长回文子串》。如果 s[i, j] 是一个回文子串，那么 s[i+1, j-1] 也是一个回文子串。反过来，如果s[i+1, j-1] 是一个回文子串，且 s[i] == s[j]，那
2022-05-15 14:24:09
237
原创 leetcode hot100 之 回文链表
题目给定一个链表，请判断其是否是回文链表。输入：head = [1,2,2,1]输出：true原题链接：https://leetcode.cn/problems/palindrome-linked-list/思路思路1首先计算链表的长度，这样便于把链表分为两半。一个不用改变原链表的方式，就是借用栈，将前半部分入栈。再遍历后半部分，同时不断出栈和相应的节点对比即可。这种方法好处是不用改变原链表，但是会有额外空间开销。复杂度分析时间复杂度 O(n)。空间复杂度 O(n)。
2022-05-15 12:23:13
308
原创 leetcode hot100 之 LRU缓存机制
题目请你设计并实现一个满足 LRU (最近最少使用) 缓存 约束的数据结构。实现 LRUCache 类：LRUCache(int capacity) 以 正整数 作为容量 capacity 初始化 LRU 缓存int get(int key) 如果关键字 key 存在于缓存中，则返回关键字的值，否则返回 -1 。void put(int key, int value) 如果关键字 key 已经存在，则变更其数据值 value ；如果不存在，则向缓存中插入该组 key-value 。如果插入操作导
2022-05-13 11:55:42
117
原创 leetcode hot100 之 二叉树的最近公共祖先
题目给定一个二叉树，以及两个节点 p、q。求这两个二叉树的最近公共祖先。一个节点也可以是它自己的祖先。输入：root = [3,5,1,6,2,0,8,null,null,7,4], p = 5, q = 1输出：3解释：节点 5 和节点 1 的最近公共祖先是节点 3 。原题链接：https://leetcode.cn/problems/lowest-common-ancestor-of-a-binary-tree/思路dfs 递归。首先思考三种情况。一种是公共祖先节点是 root，
2022-05-12 22:41:00
170
原创 leetcode hot100 之 多数元素
题目给定一个数组。其中某个数字出现次数大于 ⌊ n/2 ⌋ 次，请找出这个数字。输入：nums = [2,2,1,1,1,2,2]输出：2原题链接：https://leetcode.cn/problems/majority-element/思路思路1哈希法，维护一个哈希表，记录数字的次数，超过 n/2即可。复杂度分析时间复杂度 O(n)。遍历一次数组即可。实际不用遍历完就能找到结果。空间复杂度 O(n)。实际储存数字最多为 n/2 个。思路2排序法。排序完后，下标为 n
2022-05-12 22:03:00
139
原创 leetcode hot100 之 最小栈
题目设计一个支持 push ，pop ，top 操作，并能在常数时间内检索到最小元素的栈。实现 MinStack 类:MinStack() 初始化堆栈对象。void push(int val) 将元素val推入堆栈。void pop() 删除堆栈顶部的元素。int top() 获取堆栈顶部的元素。int getMin() 获取堆栈中的最小元素。输入：[“MinStack”,“push”,“push”,“push”,“getMin”,“pop”,“top”,“getMin”][[],[-
2022-05-12 21:41:51
801
原创 leetcode hot100 之 单词拆分
题目给定一个字符串，和一个字典。请判断该字符串能否有字典中的词拼接产生。字典中的词可以重复使用，也可以不使用。输入: s = “leetcode”, wordDict = [“leet”, “code”]输出: true解释: 返回 true 因为 “leetcode” 可以由 “leet” 和 “code” 拼接成。原题链接：https://leetcode.cn/problems/word-break/思路动态规划。设 dp[i] 表示以 i 为结尾的子字符串能否由字典中的词产生。那
2022-05-12 10:15:36
109
原创 leetcode hot100 之 乘积最大子数组
题目给定一个整型数组。找出最大乘积的连续子数组，返回其乘积。结果是一个 int 32 位数字。输入: nums = [2,3,-2,4]输出: 6解释: 子数组 [2,3] 有最大乘积 6。原题链接：https://leetcode.cn/problems/maximum-product-subarray/思路思路1双指针滑窗法。首先连续子数组肯定不能包含0 ，因为 0 乘任何数都为 0。所以我们可以每次从非 0 的数字开始滑窗。当我们不断地把非 0 的数字乘到一起，绝对值一定是越来
2022-05-11 20:47:14
194
原创 leetcode hot100 之 岛屿数量
题目给定一个metrix，由 0 和 1 构成，每个岛屿由相邻的 1 构成，0 为海洋。求 metrix 当中的岛屿数量有多少。输入：grid = [[“1”,“1”,“1”,“1”,“0”],[“1”,“1”,“0”,“1”,“0”],[“1”,“1”,“0”,“0”,“0”],[“0”,“0”,“0”,“0”,“0”]]输出：1原题链接：https://leetcode.cn/problems/number-of-islands/思路dfs。用一个 visited 来辅助记录是
2022-05-11 19:36:47
191
原创 leetcode hot100 之 翻转二叉树
题目给定一个二叉树，将其左右孩子进行翻转。输入：root = [4,2,7,1,3,6,9]输出：[4,7,2,9,6,3,1]原题链接：https://leetcode.cn/problems/invert-binary-tree/思路递归法。复杂度分析时间复杂度 O(n)。空间复杂度 O(n)。取决于递归的深度。极端情况为 n。代码/** * Definition for a binary tree node. * struct TreeNode { *
2022-05-11 12:33:51
102
原创 leetcode hot100 之 环形链表II
题目给定一个链表，判断其是否有环，如果有，则返回相交的节点。输入：head = [3,2,0,-4], pos = 1输出：返回索引为 1 的链表节点解释：链表中有一个环，其尾部连接到第二个节点。原题链接：https://leetcode.cn/problems/linked-list-cycle-ii/思路这道题是《环形链表》的进阶版。第一版只要求判断是否有相交，这一版要求返回具体的相交节点。思路1哈希法。维护一个哈希表，每遍历一个节点则加入哈希表。然后不断判断哈希表中是否有这个节
2022-05-11 12:19:56
106
原创 leetcode hot100 之 相交链表
题目给定两个链表。判断两个链表是否有相交的节点，如果有则返回相交的节点，反之返回NULL。输入：intersectVal = 8, listA = [4,1,8,4,5], listB = [5,6,1,8,4,5], skipA = 2, skipB = 3输出：Intersected at ‘8’解释：相交节点的值为 8 （注意，如果两个链表相交则不能为 0）。从各自的表头开始算起，链表 A 为 [4,1,8,4,5]，链表 B 为 [5,6,1,8,4,5]。在 A 中，相交节点前有
2022-05-10 22:26:41
99
原创 leetcode hot100 之 打家劫舍
题目给定一个数组，表示每间房屋的金币。你是一个盗贼，想要盗窃这里的金币。但如果盗窃两家相邻的房屋则会引起报警器报警。求问你可以盗窃的最大金币和为多少。输入：[1,2,3,1]输出：4解释：偷窃 1 号房屋 (金额 = 1) ，然后偷窃 3 号房屋 (金额 = 3)。偷窃到的最高金额 = 1 + 3 = 4 。原题链接：https://leetcode.cn/problems/house-robber/思路动态规划。dp[i] 表示当前为止能获得的金额。dp[i] = max(dp[i-2
2022-05-10 22:06:16
100
原创 leetcode hot100 之 排序链表
题目给定一个链表，请将升序排序后返回。输入：head = [4,2,1,3]输出：[1,2,3,4]原题链接：https://leetcode.cn/problems/sort-list/思路排序中，O(nlogn) 的方法有 快排、堆排、归并等。最适合链表的排序方式是归并排序。复杂度分析时间复杂度 O(n)。遍历所有节点。空间复杂度 O(1)。代码/** * Definition for singly-linked list. * struct ListNode
2022-05-10 21:47:24
143
原创 leetcode hot100 之 反转链表
题目给定一个链表，请将其返回再返回头节点。输入：head = [1,2,3,4,5]输出：[5,4,3,2,1]原题链接：https://leetcode.cn/problems/reverse-linked-list/思路维护一个 pre 和 cur 以及 next 指针，不断地使 cur 指向 pre，然后更新 pre 、cur 和 next。利用 preHead 更方便。最终记得处理下 head，使其指向NULL。复杂度分析时间复杂度 O(n)。遍历所有节点。空间复杂度
2022-05-09 10:37:44
378
原创 leetcode hot100 之 二叉树展开为链表
题目给定一个二叉树，将其按照先序遍历的方式展开成一个链表。left 始终为 NULL， right 为下一个节点。输入：root = [1,2,5,3,4,null,6]输出：[1,null,2,null,3,null,4,null,5,null,6]原题链接：https://leetcode-cn.com/problems/flatten-binary-tree-to-linked-list/思路直接按先序遍历进行写递归即可，同时用一个全局的 pre 变量来记录遍历过程中的上一个节点。需
2022-05-08 22:22:54
493
原创 leetcode hot100 之 从前序与中序遍历序列构造二叉树
题目给定两个数组，分别表示前序遍历和中序遍历的结果。根据这两个数组构造二叉树。输入: preorder = [3,9,20,15,7], inorder = [9,3,15,20,7]输出: [3,9,20,null,null,15,7]原题链接：https://leetcode-cn.com/problems/construct-binary-tree-from-preorder-and-inorder-traversal/思路preorder 数组的首个数字就是根节点，假设这个数字是
2022-05-08 22:00:03
480
原创 leetcode hot100 之 环形链表
题目给定一个链表，判断其是否有环。输入：head = [3,2,0,-4], pos = 1输出：true解释：链表中有一个环，其尾部连接到第二个节点。这里 pos 只是说明链表存在环，且链表末尾连接到链表第 pos 的节点。原题链接：https://leetcode-cn.com/problems/linked-list-cycle/思路快慢指针法。慢指针走一步，快指针走两步。那么慢指针走一圈时，快指针走两圈。也就是慢指针和快指针的距离最大为一圈，且两者每走一次，两者距离缩小一步。一圈
2022-05-08 13:33:29
380
原创 leetcode hot100 之 最长连续序列
题目给定一个未排序的非负整型数组，找出数字连续的最长序列的长度。要求时间复杂度 O(n)输入：nums = [100,4,200,1,3,2]输出：4解释：最长数字连续序列是 [1, 2, 3, 4]。它的长度为 4。原题链接：https://leetcode-cn.com/problems/longest-consecutive-sequence/思路思路1哈希法首先暴力法就是，外循环遍历每一个数，设这个数为 x，然后进一步查找数组当中有没有 x + 1、 x + 2，但这样每一次查
2022-05-08 12:40:19
161
原创 leetcode hot100 之 只出现一次的数字
题目给定一个非负整数数组，除了某个数字出现一次外，其他都出现过两次。 请找出这个唯一的数字。输入: [4,1,2,1,2]输出: 4原题链接：https://leetcode-cn.com/problems/single-number/思路直接亦或就完事了。x ^ x = 0x ^ 0 = x复杂度分析时间复杂度 O(n)。空间复杂度 O(1)。代码class Solution {public: int singleNumber(vector<int&
2022-05-08 12:04:46
267
原创 leetcode hot100 之 买卖股票的最佳时机
题目给定按时间顺序的股票价格，求最大获利可以达到多少。输入：[7,1,5,3,6,4]输出：5解释：在第 2 天（股票价格 = 1）的时候买入，在第 5 天（股票价格 = 6）的时候卖出，最大利润 = 6-1 = 5 。注意利润不能是 7-1 = 6, 因为卖出价格需要大于买入价格；同时，你不能在买入前卖出股票。原题链接：https://leetcode-cn.com/problems/best-time-to-buy-and-sell-stock/思路直接维护一个变量，记录到当前为止，
2022-05-08 11:59:07
311
原创 leetcode hot100 之 二叉树的最大深度
题目给定一个二叉树，求其最大深度。给定二叉树 [3,9,20,null,null,15,7]，3/ \9 20/ \15 7返回它的最大深度 3 。原题链接：https://leetcode-cn.com/problems/maximum-depth-of-binary-tree/思路递归。DFS。当前节点的高度，等于左子树的高度 或 右子树的高度 最大值 +1。复杂度分析时间复杂度 O(n)。遍历所有节点。空间复杂度 O(n)。空间取决于栈的大小，极端情况为
2022-05-08 11:49:52
119
原创 leetcode hot100 之 二叉树的层序遍历
题目给定一个二叉树，返回层序遍历的结果输入：root = [3,9,20,null,null,15,7]输出：[[3],[9,20],[15,7]]原题链接：https://leetcode-cn.com/problems/binary-tree-level-order-traversal/思路维护一个队列。第一次只将根节点入队。然后统计当前队列中的节点数，也就是当前层的节点数，并弹出相应的节点数。将其组合成一个子结果，再加入总的结果当中。节点出队后，需要把出队后的节点的左右孩子加入队
2022-05-07 23:10:55
126
原创 leetcode hot100 之 对称二叉树
题目给定一个二叉树，判断其是否轴对称输入：root = [1,2,2,3,4,4,3]输出：true原题链接：https://leetcode-cn.com/problems/symmetric-tree/思路递归。首先判断左右孩子是否相同，如果相同，则进一步对比 左孩子的左孩子 与 右孩子的右孩子，以及 对比 左孩子的右孩子 与 右孩子的左孩子。（有点绕。。。）当左右孩子都是NULL时，说明当前为止是对称的；当左右孩子只有一个是NULL，则说明不对称；当左右孩子的 val 不相等，也
2022-05-07 22:23:51
259
原创 leetcode hot100 之 验证二叉搜索树
题目给定一个二叉树，判断其是否是二叉搜索树。输入：root = [5,1,4,null,null,3,6]输出：false解释：根节点的值是 5 ，但是右子节点的值是 4 。原题链接：https://leetcode-cn.com/problems/validate-binary-search-tree/思路二叉搜索树的三个条件：左子树所有节点小于根节点右子树所有节点大于根节点左右子树本身也是二叉搜索树进行中序遍历，并保证当前节点比上一个节点大，则满足二叉搜索树。反之不成立。
2022-05-07 22:08:02
160
原创 leetcode hot100 之 不同的二叉搜索树
题目给定一个整数 n，求恰由 n 个节点且节点值由 1 ~ n 构成的二叉搜索树有多少种。输入：n = 3输出：5原题链接：https://leetcode-cn.com/problems/unique-binary-search-trees/思路首先说明一下二叉搜索树的定义：左子树所有节点小于根节点，右子树所有节点大于根节点。动态规划法。找到转移方程是关键。假定 G(n) 表示：节点数为 n 的二叉搜索树有多少种。F(i, n) 表示：以 i 为根节点，节点数为 n 的二叉搜索树有
2022-05-07 18:00:44
175
原创 leetcode hot100 之 二叉树的中序遍历
题目给定一个二叉树，返回其中序遍历。输入：root = [1,null,2,3]输出：[1,3,2]原题链接：https://leetcode-cn.com/problems/binary-tree-inorder-traversal/思路思路1递归。复杂度分析时间复杂度 O(n)。遍历所有节点。空间复杂度 O(n)。空间取决于递归层数，树的极端情况为 n 层。思路2用 stack 来模拟递归过程。先不断遍历左节点，直到没有为止。然后访问当前节点，再访问右节点。复
2022-05-07 15:41:10
127
原创 leetcode hot100 之 最大矩形
题目给定一个只包含 0、1 的 m x n 的矩阵，求矩阵当中只包含1的最大矩阵。输入：matrix = [[“1”,“0”,“1”,“0”,“0”],[“1”,“0”,“1”,“1”,“1”],[“1”,“1”,“1”,“1”,“1”],[“1”,“0”,“0”,“1”,“0”]]输出：6解释：最大矩形如上图所示。原题链接：https://leetcode-cn.com/problems/maximal-rectangle/思路这个题可以理解为《柱状图中最大的矩形》题目的改头换面版。思
2022-05-07 14:47:47
262
原创 leetcode hot100 之 柱状图中最大的矩形
题目给定一个数组，表示一系列连续的柱子，每个数字代表柱子的高度，宽度统一为 1。求在这个柱状图当中最大能构建的矩形面积。输入：heights = [2,1,5,6,2,3]输出：10解释：最大的矩形为图中红色区域，面积为 10原题链接：https://leetcode-cn.com/problems/largest-rectangle-in-histogram/思路思路1动态规划。记 dp[i][j] 表示 i 到 j 之间，最小的高度。可以初始化 dp[i][i] = heights
2022-05-07 12:05:59
168
空空如也
空空如也
TA创建的收藏夹 TA关注的收藏夹
TA关注的人