4 wind_liang

尚未进行身份认证

我要认证

暂无相关简介

等级
TA的排名 4w+

LeetCode 力扣 138. 复制带随机指针的链表

题目描述(中等难度)给一个链表,返回复制后的链表。链表节点相对于普通的多了一个 random 指针,会随机指向链表内的任意节点或者指向 null。思路分析这道题其实和 133 题 复制一个图很类似,这里的话就是要解决的问题就是,当更新当前节点的 random 指针的时候,如果 random 指向的是很后边的节点,但此时后边的节点还没有生成,那么我们该如何处理。和 133 题 一样,我们...

2020-05-03 10:59:32

LeetCode 力扣 137. 只出现一次的数字 II

题目描述(中等难度)136 题 的升级版,这个题的话意思是,每个数字都出现了 3 次,只有一个数字出现了 1 次,找出这个数字。同样要求时间复杂度为 O(n),空间复杂度为 O(1)。大家可以先看一下 136 题 ,完全按 136 题 的每个解法去考虑一下。解法一先不考虑空间复杂度,用最常规的方法。可以用一个 HashMap 对每个数字进行计数,然后返回数量为 1 的数字就可以了...

2020-04-30 09:37:09

LeetCode 力扣 136. 只出现一次的数字

题目描述(简单难度)所有数字都是成对出现的,只有一个数字是落单的,找出这个落单的数字。解法一题目要求线性复杂度内实现,并且要求没有额外空间。首先我们考虑假如没有空间复杂度的限制。这其实就只需要统计每个数字出现的次数,很容易想到去用 HashMap 。遍历一次数组,第一次遇到就将对应的 key 置为 1。第二次遇到就拿到 key 对应的 value 然后进行加 1 再存入。最后只需要寻找...

2020-04-29 10:25:22

LeetCode 力扣 135. 分发糖果

题目描述(困难难度)给 N 个小朋友分糖,每个人至少有一颗糖。并且有一个 rating 数组,如果小朋友的 rating比它旁边小朋友的 rating 大(不包括等于),那么他必须要比对应小朋友的糖多。问至少需要分配多少颗糖。用 - 表示糖,举几个例子。1 0 2- - -- -总共就需要 5 颗糖。1 2 2- - - -总共就需要 4 颗糖。解法一根据题目,首...

2020-04-28 10:17:26

LeetCode 力扣 134. 加油站

题目描述(中等难度)把这个题理解成下边的图就可以。每个节点表示添加的油量,每条边表示消耗的油量。题目的意思就是问我们从哪个节点出发,还可以回到该节点。只能顺时针方向走。解法一 暴力解法考虑暴力破解,一方面是验证下自己对题目的理解是否正确,另一方面后续的优化也可以从这里入手。考虑从第 0 个点出发,能否回到第 0 个点。考虑从第 1 个点出发,能否回到第 1 个点。考虑从第 2 个...

2020-04-27 10:41:14

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

LeetCode 力扣 132.分割回文串 II

题目描述(困难难度)和 131 题 一样,可以在任意位置切割字符串,需要保证切割后的每个子串都是回文串。问最少需要切割几次。和 131 题 用相同的分析方法即可。解法一 分治大问题化小问题,利用小问题的结果,解决当前大问题。举个例子。aabb先考虑在第 1 个位置切割,a | abb这样我们只需要知道 abb 的最小切割次数,然后加 1,记为 m1aabb再考虑在第 2 ...

2020-04-24 10:33:30

LeetCode 力扣 131. 分割回文串

题目描述(中等难度)给一个字符串,然后在任意位置切割若干次,保证切割后的每个字符串都是回文串。输出所有满足要求的切割结果。解法一 分治将大问题分解为小问题,利用小问题的结果,解决当前大问题。这道题的话,举个例子。aabb先考虑在第 1 个位置切割,a | abb这样我们只需要知道 abb 的所有结果,然后在所有结果的头部把 a 加入abb 的所有结果就是 [a b b] [a ...

2020-04-23 10:09:18

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

LeetCode 力扣 129. 求根到叶子节点数字之和

题目描述(中等难度)从根节点到叶子节点的路径组成一个数字,计算所有的数字和。思路分析和 112 题 有些像,112 题是给出一个 sum,然后去找这条路径。但本质上都一样的,只需要对二叉树进行遍历,遍历过程中记录当前路径的和就可以。说到遍历,无非就是 BFS 和 DFS,如果进行 BFS,过程中我们需要维护多条路径的和,所以我们选择 DFS 。说到 DFS 的话,可以用递归,也可以用栈去...

2020-04-21 11:15:02

LeetCode 力扣 129. 求根到叶子节点数字之和

题目描述(中等难度)从根节点到叶子节点的路径组成一个数字,计算所有的数字和。思路分析和 112 题 有些像,112 题是给出一个 sum,然后去找这条路径。但本质上都一样的,只需要对二叉树进行遍历,遍历过程中记录当前路径的和就可以。说到遍历,无非就是 BFS 和 DFS,如果进行 BFS,过程中我们需要维护多条路径的和,所以我们选择 DFS 。说到 DFS 的话,可以用递归,也可以用栈去...

2020-04-20 07:37:56

LeetCode 力扣 128. 最长连续序列

题目描述(困难难度)给一个数组,求出连续的数字最多有多少个,时间复杂度要求是 O(n)。解法一首先想一下最直接的暴力破解。我们可以用一个 HashSet 把给的数组保存起来。然后再考虑数组的每个数,比如这个数是 n,然后看 n + 1 在不在 HashSet 中,然后再看 n + 2 在不在,接下来 n + 3、n + 4 直到在 HashSet 中找不到,记录当前的长度。然后继续考虑下一...

2020-04-19 10:00:43

LeetCode 力扣 137. 只出现一次的数字 II

题目描述(中等难度)136 题 的升级版,这个题的话意思是,每个数字都出现了 3 次,只有一个数字出现了 1 次,找出这个数字。同样要求时间复杂度为 O(n),空间复杂度为 O(1)。大家可以先看一下 136 题 ,完全按 136 题 的每个解法去考虑一下。解法一先不考虑空间复杂度,用最常规的方法。可以用一个 HashMap 对每个数字进行计数,然后返回数量为 1 的数字就可以了...

2020-04-18 10:19:21

LeetCode 力扣 136. 单词接龙 II

题目描述(困难难度)给定两个单词,一个作为开始,一个作为结束,还有一个单词列表。然后依次选择单词,只有当前单词到下一个单词只有一个字母不同才能被选择,然后新的单词再作为当前单词,直到选到结束的单词。输出这个的最短路径,如果有多组,则都输出。思路分析结合了开始自己的想法,又看了 Discuss,这道题有些难讲清楚,一个原因就是解法的代码会很长,这里理一下整个的思路。如果我们从开始的单词,把...

2020-04-17 11:31:37

LeetCode 力扣 125. 验证回文串

题目描述(简单难度)判断一个字符串是否是回文串,忽略掉除了字母和数字外的字符。解法一两个指针,一个指针从头进行,一个指针从尾部进行。依次判断两个指针的字符是否相等,同时要跳过非法字符。需要注意的是,两个指针不用从头到尾遍历,当两个指针相遇的时候就意味着这个字符串是回文串了。还需要注意的是 'A' == 'a' ,也就是大写字母和小写字母是相同的。publ...

2020-04-15 10:22:15

LeetCode 力扣 124. 二叉树中的最大路径和

题目描述(困难难度)考虑一条路径,可以从任意节点开始,每个节点最多经过一次,问经过的节点的和最大是多少。解法一 递归参考了 这里。首先看到二叉树的题,肯定就是想递归了。递归常规的思路,肯定是递归考虑左子树的最大值,递归考虑右子树的最大值。public int maxPathSum(TreeNode root) { if (root == null) { retu...

2020-04-14 10:54:20

LeetCode 力扣 123. 买卖股票的最佳时机 III

题目描述(困难难度)依旧是买卖股票的延伸,但比 121 题 , 122 题 难度高了不少。这道题的意思是,给一个数组代表股票每天的价格。你最多可以买入卖出两次,但只有卖出了才可以再次买入,求出最大的收益是多少。解法一参考 这里。开始的想法是求出收益第一高和第二高的两次买卖,然后加起来。对于普通的情况是可以解决的,但是对于下边的情况1 5 2 8 3 10第一天买第二天卖,第三天买第四...

2020-04-13 10:51:16

LeetCode 力扣 122. 买卖股票的最佳时机 II

题目描述(简单难度)和 121 题 一样,给定一个数组,代表每天的价格。区别在于 121 题只能进行一次买入卖出。但是这道题可以不停的买入、卖出,但是只有卖出了才能继续买入。解法一就用最简单的思想,我们穿越回去了过去,知道了未来每天的股票价格,要怎么操作呢?跌了的前一天卖出,例如下边的例子1 2 3 4 天2 7 8 5第 4 天下跌,我们可以在前一天卖出,下跌当天再次买入,后边...

2020-04-12 09:45:54

LeetCode 力扣 121. 买卖股票的最佳时机

题目描述(简单难度)给一个数组,看作每天股票的价格,然后某一天买入,某一天卖出,最大收益可以是多少。可以不操作,收入就是 0。解法一 暴力破解先写个暴力的,看看对题目的理解对不对。用两个循环,外层循环表示买入时候的价格,内层循环表示卖出时候的价格,遍历所有的情况,期间更新最大的收益。public int maxProfit(int[] prices) { int maxProfi...

2020-04-11 10:52:14

LeetCode 力扣 120. 三角形最小路径和

题目描述(中等难度)当前层只能选择下一层相邻的两个元素走,比如第 3 层的 5 只能选择第4层的 1 和 8 ,从最上边开始,走一条路径,走到最底层最小的和是多少。题目解析先看一下 115 题 吧,和这道题思路方法是完全完全一样的。此外,119 题 倒着循环优化空间复杂度也可以看一下。这道题本质上就是动态规划,再本质一些就是更新一张二维表。 115 题 已经进行了详细介绍,这里就粗略的...

2020-04-10 10:19:46

查看更多

勋章 我的勋章
  • 持之以恒
    持之以恒
    授予每个自然月内发布4篇或4篇以上原创或翻译IT博文的用户。不积跬步无以至千里,不积小流无以成江海,程序人生的精彩需要坚持不懈地积累!
  • 勤写标兵Lv3
    勤写标兵Lv3
    授予每个自然周发布7篇到8篇原创IT博文的用户。本勋章将于次周周三上午根据用户上周的博文发布情况由系统自动颁发。