一定要早日上岸鸭

每天至少一道力扣喔

August 1, 2021

1337. 矩阵中战斗力最弱的 K 行

1337. 矩阵中战斗力最弱的 K 行 思路: 此题有两种方法:朴素和 二分+优先队列 朴素的很简单,用一个二元数组记录每一行战力和index 然后 自定义一个Arrays.sort()按照值优先其次是index来排序 由于军人在前面,所以可以用二分来查找右边的最后一个军人的下标,由于存在没有军人的情况,所以需要额外判断下下标在哪里。之后用大根堆来存储二元数组,并且更新当前的最大值。最后堆顶弹出并从右往左放入数组即可:...

Read More
July 30, 2021

1254. 统计封闭岛屿的数目

1254. 统计封闭岛屿的数目 此题是典型的岛屿问题;可以拆分为两个部分:寻找连通块已经去除边界的连通块; 此题中学到了用dx, dy来移动,并且用一个布尔数组来表示是否遍历过点来避免重复遍历;已经用flag传址来标记是否为边界上的连通块即不为封闭岛屿:代码如下: class Solution { // 记录x和y的移动值 public...

Read More
July 29, 2021

1104. 二叉树寻路

1104. 二叉树寻路 思路: 本题有两种解法,第一种是模拟第二种是用数学的方法,首先要考虑的是若一个二叉树没有奇偶性质,那么他的父节点一定是 当前节点/2;因此,在得知某一层的最大值和最小值后,我们便可以由计算或模拟来得到其父节点: 利用从根节点到任意一层都是满二叉树,我们可以先确定 label 所在的层级 level,然后计算出当前层起始节点值(最小值)和结束节点值(最大值)。再利用「每层节点数量翻倍」&「隔层奇偶性翻转」,寻址出上一层的节点下标(令每层下标均「从左往右」计算,并从 11 开始),直到构造出答案(寻址到根节点)。...

Read More
July 28, 2021

863. 二叉树中所有距离为 K 的结点

863. 二叉树中所有距离为 K 的结点 思路:DFS+哈希 第一次DFS来用哈希表存储节点和其父节点这样就可以在之后回溯得到距离为k的点 第二次DFS从target开始,以target为root,这样就可以用递归来找当前depth和k相同的节点了,需要注意的是,在回溯过程中会出现遍历过已经出现的数字的情况,因此我们需要记录下之前的节点是哪个。 ps:由于节点的值都不相同因此hashmap的key选择了值 代码: // /**...

Read More
July 27, 2021

671. 二叉树中第二小的节点

671. 二叉树中第二小的节点 此题有三种情况: 可以定义两个小值 d1, d2 若树上的值 X < d1 < d2 --> d1 = X d2 = d1; 若树上的值 d1 < X < d2 --> d2 = X; 若树上的值 d1 < d2 < X --> 不变// DFS: /** * Definition for...

Read More