- 博客(154)
- 资源 (4)
- 收藏
- 关注
RSS订阅原创 WebAssembly入门-未来可能发生的巨变
引言先看下 官网 给的定义。WebAssembly (abbreviated Wasm) is a binary instruction format for a stack-based virtual machine. Wasm is designed as a portable compilation target for programming languages, enabling deployment on the web for client and server applications
2021-02-20 20:03:39
7106
原创 git原理浅析
git 历史linux 之父 Linus Torvalds 大家应该都知道，而 git 也是由 Linus 开发的。从 1991 年发布了第一版的 linux 内核，Linux 内核开源项目有着众多的参与者，但绝大多数的 Linux 内核维护工作都花在了提交补丁和保存归档的繁琐事务上（1991－2002年间）。到 2002 年，整个项目组开始启用一个专有的分布式版本控制系统 BitKeeper 来管理和维护代码，之前市面上也有其他的版本管理系统，比如 CSV、SVN，但是 Linus 觉得它们很蠢，直到有
2020-07-24 19:04:55
690
原创 LeetCode 力扣 138. 复制带随机指针的链表
题目描述（中等难度）给一个链表，返回复制后的链表。链表节点相对于普通的多了一个 random 指针，会随机指向链表内的任意节点或者指向 null。思路分析这道题其实和 133 题 复制一个图很类似，这里的话就是要解决的问题就是，当更新当前节点的 random 指针的时候，如果 random 指向的是很后边的节点，但此时后边的节点还没有生成，那么我们该如何处理。和 133 题 一样，我们...
2020-05-03 10:59:32
430
原创 LeetCode 力扣 137. 只出现一次的数字 II
题目描述（中等难度）136 题 的升级版，这个题的话意思是，每个数字都出现了 3 次，只有一个数字出现了 1 次，找出这个数字。同样要求时间复杂度为 O（n），空间复杂度为 O（1）。大家可以先看一下 136 题 ，完全按 136 题 的每个解法去考虑一下。解法一先不考虑空间复杂度，用最常规的方法。可以用一个 HashMap 对每个数字进行计数，然后返回数量为 1 的数字就可以了...
2020-04-30 09:37:09
901
1
原创 LeetCode 力扣 136. 只出现一次的数字
题目描述（简单难度）所有数字都是成对出现的，只有一个数字是落单的，找出这个落单的数字。解法一题目要求线性复杂度内实现，并且要求没有额外空间。首先我们考虑假如没有空间复杂度的限制。这其实就只需要统计每个数字出现的次数，很容易想到去用 HashMap 。遍历一次数组，第一次遇到就将对应的 key 置为 1。第二次遇到就拿到 key 对应的 value 然后进行加 1 再存入。最后只需要寻找...
2020-04-29 10:25:22
358
原创 LeetCode 力扣 135. 分发糖果
题目描述（困难难度）给 N 个小朋友分糖，每个人至少有一颗糖。并且有一个 rating 数组，如果小朋友的 rating比它旁边小朋友的 rating 大（不包括等于），那么他必须要比对应小朋友的糖多。问至少需要分配多少颗糖。用 - 表示糖，举几个例子。1 0 2- - -- -总共就需要 5 颗糖。1 2 2- - - -总共就需要 4 颗糖。解法一根据题目，首...
2020-04-28 10:17:26
913
原创 LeetCode 力扣 134. 加油站
题目描述（中等难度）把这个题理解成下边的图就可以。每个节点表示添加的油量，每条边表示消耗的油量。题目的意思就是问我们从哪个节点出发，还可以回到该节点。只能顺时针方向走。解法一 暴力解法考虑暴力破解，一方面是验证下自己对题目的理解是否正确，另一方面后续的优化也可以从这里入手。考虑从第 0 个点出发，能否回到第 0 个点。考虑从第 1 个点出发，能否回到第 1 个点。考虑从第 2 个...
2020-04-27 10:41:14
861
原创 LeetCode 力扣 133. 克隆图
题目描述（中等难度）复制一个图，图的节点定义如下。class Node { public int val; public List<Node> neighbors; public Node() {} public Node(int _val,List<Node> _neighbors) { val = _val; ...
2020-04-26 10:59:01
785
原创 LeetCode 力扣 132.分割回文串 II
题目描述（困难难度）和 131 题 一样，可以在任意位置切割字符串，需要保证切割后的每个子串都是回文串。问最少需要切割几次。和 131 题 用相同的分析方法即可。解法一 分治大问题化小问题，利用小问题的结果，解决当前大问题。举个例子。aabb先考虑在第 1 个位置切割，a | abb这样我们只需要知道 abb 的最小切割次数，然后加 1，记为 m1aabb再考虑在第 2 ...
2020-04-24 10:33:30
937
原创 LeetCode 力扣 131. 分割回文串
题目描述（中等难度）给一个字符串，然后在任意位置切割若干次，保证切割后的每个字符串都是回文串。输出所有满足要求的切割结果。解法一 分治将大问题分解为小问题，利用小问题的结果，解决当前大问题。这道题的话，举个例子。aabb先考虑在第 1 个位置切割，a | abb这样我们只需要知道 abb 的所有结果，然后在所有结果的头部把 a 加入abb 的所有结果就是 [a b b] [a ...
2020-04-23 10:09:18
836
原创 LeetCode 力扣 130. 被围绕的区域
题目描述（中等难度）有一点点像围棋，把被 X 围起来的 O 变成 X，边界的 O 一定不会被围起来。如果 O 和边界的 O 连通起来，那么这些 O 就都算作不被围起来，比如下边的例子。X X X X XO O O X XX X X O XX O X X X上边的例子就只需要变化 1 个 O 。X X X X XO O O X XX X X X XX O X X X解法一把...
2020-04-22 09:38:23
1150
原创 LeetCode 力扣 129. 求根到叶子节点数字之和
题目描述（中等难度）从根节点到叶子节点的路径组成一个数字，计算所有的数字和。思路分析和 112 题 有些像，112 题是给出一个 sum，然后去找这条路径。但本质上都一样的，只需要对二叉树进行遍历，遍历过程中记录当前路径的和就可以。说到遍历，无非就是 BFS 和 DFS，如果进行 BFS，过程中我们需要维护多条路径的和，所以我们选择 DFS 。说到 DFS 的话，可以用递归，也可以用栈去...
2020-04-21 11:15:02
802
原创 LeetCode 力扣 129. 求根到叶子节点数字之和
题目描述（中等难度）从根节点到叶子节点的路径组成一个数字，计算所有的数字和。思路分析和 112 题 有些像，112 题是给出一个 sum，然后去找这条路径。但本质上都一样的，只需要对二叉树进行遍历，遍历过程中记录当前路径的和就可以。说到遍历，无非就是 BFS 和 DFS，如果进行 BFS，过程中我们需要维护多条路径的和，所以我们选择 DFS 。说到 DFS 的话，可以用递归，也可以用栈去...
2020-04-20 07:37:56
201
原创 LeetCode 力扣 128. 最长连续序列
题目描述（困难难度）给一个数组，求出连续的数字最多有多少个，时间复杂度要求是 O(n)。解法一首先想一下最直接的暴力破解。我们可以用一个 HashSet 把给的数组保存起来。然后再考虑数组的每个数，比如这个数是 n，然后看 n + 1 在不在 HashSet 中，然后再看 n + 2 在不在，接下来 n + 3、n + 4 直到在 HashSet 中找不到，记录当前的长度。然后继续考虑下一...
2020-04-19 10:00:43
837
原创 LeetCode 力扣 137. 只出现一次的数字 II
题目描述（中等难度）136 题 的升级版，这个题的话意思是，每个数字都出现了 3 次，只有一个数字出现了 1 次，找出这个数字。同样要求时间复杂度为 O（n），空间复杂度为 O（1）。大家可以先看一下 136 题 ，完全按 136 题 的每个解法去考虑一下。解法一先不考虑空间复杂度，用最常规的方法。可以用一个 HashMap 对每个数字进行计数，然后返回数量为 1 的数字就可以了...
2020-04-18 10:19:21
921
原创 LeetCode 力扣 136. 单词接龙 II
题目描述（困难难度）给定两个单词，一个作为开始，一个作为结束，还有一个单词列表。然后依次选择单词，只有当前单词到下一个单词只有一个字母不同才能被选择，然后新的单词再作为当前单词，直到选到结束的单词。输出这个的最短路径，如果有多组，则都输出。思路分析结合了开始自己的想法，又看了 Discuss，这道题有些难讲清楚，一个原因就是解法的代码会很长，这里理一下整个的思路。如果我们从开始的单词，把...
2020-04-17 11:31:37
883
原创 LeetCode 力扣 125. 验证回文串
题目描述（简单难度）判断一个字符串是否是回文串，忽略掉除了字母和数字外的字符。解法一两个指针，一个指针从头进行，一个指针从尾部进行。依次判断两个指针的字符是否相等，同时要跳过非法字符。需要注意的是，两个指针不用从头到尾遍历，当两个指针相遇的时候就意味着这个字符串是回文串了。还需要注意的是 'A' == 'a' ，也就是大写字母和小写字母是相同的。publ...
2020-04-15 10:22:15
916
原创 LeetCode 力扣 124. 二叉树中的最大路径和
题目描述（困难难度）考虑一条路径，可以从任意节点开始，每个节点最多经过一次，问经过的节点的和最大是多少。解法一 递归参考了 这里。首先看到二叉树的题，肯定就是想递归了。递归常规的思路，肯定是递归考虑左子树的最大值，递归考虑右子树的最大值。public int maxPathSum(TreeNode root) { if (root == null) { retu...
2020-04-14 10:54:20
946
原创 LeetCode 力扣 123. 买卖股票的最佳时机 III
题目描述（困难难度）依旧是买卖股票的延伸，但比 121 题 ， 122 题 难度高了不少。这道题的意思是，给一个数组代表股票每天的价格。你最多可以买入卖出两次，但只有卖出了才可以再次买入，求出最大的收益是多少。解法一参考 这里。开始的想法是求出收益第一高和第二高的两次买卖，然后加起来。对于普通的情况是可以解决的，但是对于下边的情况1 5 2 8 3 10第一天买第二天卖，第三天买第四...
2020-04-13 10:51:16
946
原创 LeetCode 力扣 122. 买卖股票的最佳时机 II
题目描述（简单难度）和 121 题 一样，给定一个数组，代表每天的价格。区别在于 121 题只能进行一次买入卖出。但是这道题可以不停的买入、卖出，但是只有卖出了才能继续买入。解法一就用最简单的思想，我们穿越回去了过去，知道了未来每天的股票价格，要怎么操作呢？跌了的前一天卖出，例如下边的例子1 2 3 4 天2 7 8 5第 4 天下跌，我们可以在前一天卖出，下跌当天再次买入，后边...
2020-04-12 09:45:54
769
原创 LeetCode 力扣 121. 买卖股票的最佳时机
题目描述（简单难度）给一个数组，看作每天股票的价格，然后某一天买入，某一天卖出，最大收益可以是多少。可以不操作，收入就是 0。解法一 暴力破解先写个暴力的，看看对题目的理解对不对。用两个循环，外层循环表示买入时候的价格，内层循环表示卖出时候的价格，遍历所有的情况，期间更新最大的收益。public int maxProfit(int[] prices) { int maxProfi...
2020-04-11 10:52:14
681
1
原创 LeetCode 力扣 120. 三角形最小路径和
题目描述（中等难度）当前层只能选择下一层相邻的两个元素走，比如第 3 层的 5 只能选择第4层的 1 和 8 ，从最上边开始，走一条路径，走到最底层最小的和是多少。题目解析先看一下 115 题 吧，和这道题思路方法是完全完全一样的。此外，119 题 倒着循环优化空间复杂度也可以看一下。这道题本质上就是动态规划，再本质一些就是更新一张二维表。 115 题 已经进行了详细介绍，这里就粗略的...
2020-04-10 10:19:46
794
原创 LeetCode 力扣 119. 杨辉三角 II
题目描述（简单难度）和 118 题 一样，依旧是杨辉三角。区别在于之前是输出所有层的数，这道题只需要输出第 k 层的数。解法一和 118 题 一样，我们只需要一层一层的求。但是不需要把每一层的结果都保存起来，只需要保存上一层的结果，就可以求出当前层的结果了。public List<Integer> getRow(int rowIndex) { List<Inte...
2020-04-09 11:10:36
768
原创 LeetCode 力扣 118. 杨辉三角
题目描述（简单难度）其实就是杨辉三角，当前元素等于上一层的两个元素的和。解法一用两层循环，注意一下我们下标是从 0 开始还是从 1 开始，然后就可以写出来了。public List<List<Integer>> generate(int numRows) { List<List<Integer>> ans = new ArrayLi...
2020-04-08 10:52:52
163
原创 LeetCode 力扣 117. 填充每个节点的下一个右侧节点指针 II
题目描述（中等难度）给定一个二叉树，然后每个节点有一个 next 指针，将它指向它右边的节点。和 116 题 基本一样，区别在于之前是满二叉树。解法一 BFS直接把 116 题 题的代码复制过来就好，一句也不用改。利用一个栈将下一层的节点保存。通过pre指针把栈里的元素一个一个接起来。public Node connect(Node root) { if (root == ...
2020-04-07 10:24:37
794
原创 LeetCode 力扣 116. 填充每个节点的下一个右侧节点指针
题目描述（中等难度）给定一个满二叉树，每个节点多了一个next指针，然后将所有的next指针指向它的右边的节点。并且要求空间复杂度是O(1)。解法一 BFS如果没有要求空间复杂度这道题就简单多了，我们只需要用一个队列做BFS，BFS参见 102 题。然后按顺序将每个节点连起来就可以了。public Node connect(Node root) { if (root == nu...
2020-04-06 10:43:38
727
原创 LeetCode 力扣 115. 不同的子序列
题目描述（困难难度）给定两个字符串 S 和T，从 S 中选择字母，使得刚好和 T 相等，有多少种选法。解法一 递归之分治S 中的每个字母就是两种可能选他或者不选他。我们用递归的常规思路，将大问题化成小问题，也就是分治的思想。如果我们求 S[0，S_len - 1] 中能选出多少个 T[0，T_len - 1]，个数记为 n。那么分两种情况，S[0] == T[0]，需要知道两种情况...
2020-04-05 10:11:06
876
原创 LeetCode 力扣 114. 二叉树展开为链表
题目描述（中等难度）把一个二叉树展开成一个链表，展开顺序如图所示。解法一可以发现展开的顺序其实就是二叉树的先序遍历。算法和 94 题 中序遍历的 Morris 算法有些神似，我们需要两步完成这道题。将左子树插入到右子树的地方将原来的右子树接到左子树的最右边节点考虑新的右子树的根节点，一直重复上边的过程，直到新的右子树为 null可以看图理解下这个过程。 1 / \...
2020-04-02 10:57:27
446
原创 LeetCode 力扣 113. 路径总和 II
题目描述（中等难度）112 题 的升级版，给定一个sum，输出从根节点开始到叶子节点，和为sum 的所有路径可能。直接在 112 题 的基础上改了，解法没有新内容，大家可以过去看一看。解法一 递归112 题 的解法是下边的样子。public boolean hasPathSum(TreeNode root, int sum) { if (root == null) { ...
2020-04-01 10:54:12
772
原创 LeetCode 力扣 112. 路径总和
题目描述（简单难度）给定一个sum，判断是否有一条从根节点到叶子节点的路径，该路径上所有数字的和等于sum。解法一 递归这道题其实和 111 题 是一样的，大家可以先看 111 题 的分析，这道题无非是把 111 题 递归传递的depth改为了sum的传递。如果不仔细分析题目，代码可能会写成下边的样子。public boolean hasPathSum(TreeNode root, ...
2020-03-31 10:29:10
740
原创 LeetCode 力扣 111. 二叉树的最小深度
题目描述（简单难度）返回从根节点到叶子节点最小深度。解法一 递归和 104 题 有些像，当时是返回根节点到叶子节点的最大深度。记得当时的代码很简单。public int maxDepth(TreeNode root) { if (root == null) { return 0; } return Math.max(maxDepth(root.le...
2020-03-30 10:46:41
758
原创 LeetCode 力扣 110. 平衡二叉树
题目描述（简单难度）判断一棵树是否是平衡二叉树，平衡二叉树定义如下：它是一棵空树或它的左右两个子树的高度差的绝对值不超过 1，并且左右两个子树都是一棵平衡二叉树。解法一直接按照定义来吧，并且多定义一个求高度的函数，之前在 104 题 做过。public boolean isBalanced(TreeNode root) { //它是一棵空树 if (root == ...
2020-03-29 11:20:41
328
原创 LeetCode 力扣 109. 有序链表转换二叉搜索树
题目描述（中等难度）和 108 题 是一样的，都是给定一个升序序列，然后生成二分平衡查找树。区别在于 108 题给定的是数组，这里给的是链表。解法一大家先看一下 108 题 吧，算法的关键是取到中间的数据做为根节点。而这里链表的话，由于不支持随机访问，所以会麻烦些。最简单的思路就是我们把链表先用线性表存起来，然后题目就转换成 108 题了。为了方便，把上一道题的数组参数改为List 。...
2020-03-28 10:18:53
822
原创 LeetCode 力扣 108. 将有序数组转换为二叉搜索树
题目描述（简单难度）给一个升序数组，生成一个平衡二叉搜索树。平衡二叉树定义如下：它是一棵空树或它的左右两个子树的高度差的绝对值不超过1，并且左右两个子树都是一棵平衡二叉树。二叉搜索树定义如下：若任意节点的左子树不空，则左子树上所有节点的值均小于它的根节点的值；若任意节点的右子树不空，则右子树上所有节点的值均大于它的根节点的值；任意节点的左、右子树也分别为二叉查找树；没有键值...
2020-03-27 10:12:47
1096
原创 LeetCode 力扣 107. 二叉树的层次遍历 II
题目描述（简单难度）树的层次遍历，和 102 题 的不同之处是，之前输出的数组顺序是从根部一层一层的输出，现在是从底部，一层一层的输出。解法一 DFS把 102 题 的DFS贴过来看一下。public List<List<Integer>> levelOrder(TreeNode root) { List<List<Integer>>...
2020-03-26 09:26:22
759
原创 LeetCode 力扣 106. 从中序与后序遍历序列构造二叉树
题目描述（中等难度）根据二叉树的中序遍历和后序遍历还原二叉树。思路分析可以先看一下 105 题，直接在 105 题的基础上改了，大家也可以先根据 105 题改一改。105 题给的是先序遍历和中序遍历，这里把先序遍历换成了后序遍历。区别在于先序遍历的顺序是 根节点 -> 左子树 -> 右子树。后序遍历的顺序是 左子树 -> 右子树 -> 根节点。我们当然还是先...
2020-03-25 10:20:50
786
原创 LeetCode 力扣 105. 从前序与中序遍历序列构造二叉树
题目描述（中等难度）根据二叉树的先序遍历和中序遍历还原二叉树。解法一 递归先序遍历的顺序是根节点，左子树，右子树。中序遍历的顺序是左子树，根节点，右子树。所以我们只需要根据先序遍历得到根节点，然后在中序遍历中找到根节点的位置，它的左边就是左子树的节点，右边就是右子树的节点。生成左子树和右子树就可以递归的进行了。比如上图的例子，我们来分析一下。preorder = [3,9,20,1...
2020-03-24 10:31:19
1284
1
原创 LeetCode 力扣 104. 二叉树的最大深度
题目描述（简单难度）输出二叉树的深度。解法一 DFS依旧是考的二叉树的遍历。最简单的思路就是用递归进行 DFS 即可。public int maxDepth(TreeNode root) { if (root == null) { return 0; } return Math.max(maxDepth(root.left), maxDepth(...
2020-03-23 10:53:01
757
原创 LeetCode 力扣 103. 二叉树的锯齿形层次遍历
题目描述（中等难度）和 102 题 类似，二叉树的层次遍历。只不过这题要求，第 1 层从左到右，第 2 层从右到左，第 3 层从左到右，第 4 层从右到左，交替进行。思路分析大家可以先做下 102 题 吧，直接在 102 题的基础上进行修改即可。从左到右和从右到左交替，所以我们只需要判断当前的 level，层数从 0 开始的话，偶数就把元素添加到当前层的末尾，奇数的话，每次把新元素添加到头...
2020-03-22 10:53:24
816
原创 LeetCode 力扣 102. 二叉树的层次遍历
题目描述（中等难度）二叉树的层次遍历，输出一个 list 的 list。解法一 DFS这道题考的就是 BFS，我们可以通过 DFS 实现。只需要在递归过程中将当前 level 传入即可。public List<List<Integer>> levelOrder(TreeNode root) { List<List<Integer>>...
2020-03-21 11:01:26
833
空空如也
TA创建的收藏夹 TA关注的收藏夹
TA关注的人