blueDolphin

blueDolphin 查看完整档案

武汉编辑  |  填写毕业院校  |  填写所在公司/组织填写个人主网站
编辑
_ | |__ _ _ __ _ | '_ \| | | |/ _` | | |_) | |_| | (_| | |_.__/ \__,_|\__, | |___/ 个人简介什么都没有

个人动态

blueDolphin 发布了文章 · 2020-09-23

二分查找_ x 的平方根

题目描述

实现 int sqrt(int x) 函数。
计算并返回 x 的平方根,其中 x 是非负整数。
由于返回类型是整数,结果只保留整数的部分,小数部分将被舍去。

示例:
输入: 8
输出: 2
说明: 8 的平方根是 2.82842...,
  由于返回类型是整数,小数部分将被舍去。

解题思路

使用二分查找,找到最后一个平方值小于x的数

语言积累和技巧

1、将平方值转为long类型,避开溢出问题
2、使用46340 这个最大的可能值,可以减少几次运算
3、编写程序的时候,取到最后一个平方值小于x的数(y),下一个的话,因为mid-1的原因会导致low >= high,所以会退出循环,我们将y返回即可。可以减少几个逻辑判断

代码链接

https://github.com/lunaDolphi...
https://github.com/lunaDolphi...

查看原文

赞 0 收藏 0 评论 0

blueDolphin 发布了文章 · 2020-09-22

二分查找_供暖半径_475

题目描述

冬季已经来临。 你的任务是设计一个有固定加热半径的供暖器向所有房屋供暖。

现在,给出位于一条水平线上的房屋和供暖器的位置,找到可以覆盖所有房屋的最小加热半径。

所以,你的输入将会是房屋和供暖器的位置。你将输出供暖器的最小加热半径。

说明:

给出的房屋和供暖器的数目是非负数且不会超过 25000。
给出的房屋和供暖器的位置均是非负数且不会超过10^9。
只要房屋位于供暖器的半径内(包括在边缘上),它就可以得到供暖。
所有供暖器都遵循你的半径标准,加热的半径也一样。
示例 1:

输入: [1,2,3],[2]
输出: 1
解释: 仅在位置2上有一个供暖器。如果我们将加热半径设为1,那么所有房屋就都能得到供暖。

解题思路

1、根据房子,找到最近的加热器的距离(二分查找、快慢指针)
2、在所有的距离中找到最小的

实现方式:
1、循环查找
2、迭代
3、快慢指针

语言积累和技巧

1、边界场景处理起来须小心点

代码链接

https://github.com/lunaDolphi...
https://github.com/lunaDolphi...
https://github.com/lunaDolphi...

查看原文

赞 0 收藏 0 评论 0

blueDolphin 发布了文章 · 2020-09-18

斐波那契数_leetcode_509_offer_10_1

题目描述

斐波那契数,通常用 F(n) 表示,形成的序列称为斐波那契数列。该数列由 0 和 1 开始,后面的每一项数字都是前面两项数字的和。也就是:

F(0) = 0,   F(1) = 1
F(N) = F(N - 1) + F(N - 2), 其中 N > 1.
给定 N,计算 F(N)。

解题思路

一、递归 借用数组或者散列表来存储中间值,这样空间换时间
二、迭代 思路本质都是一样,用数组的下标作为n值,在数组内存入对应的结果

语言积累和技巧

使用map或者数组存储中间的计算值,能有效减小重复计算的次数,提升效率

代码链接

https://github.com/lunaDolphi...
https://github.com/lunaDolphi...
https://github.com/lunaDolphi...

查看原文

赞 0 收藏 0 评论 0

blueDolphin 发布了文章 · 2020-09-17

二叉树的直径_leetcode_543

题目描述

给定一棵二叉树,你需要计算它的直径长度。一棵二叉树的直径长度是任意两个结点路径长度中的最大值。这条路径可能穿过也可能不穿过根结点。

示例 :
给定二叉树

      1
     / \
    2   3
   / \     
  4   5    

返回 3, 它的长度是路径 [4,2,1,3] 或者 [5,2,1,3]。

注意:两结点之间的路径长度是以它们之间边的数目表示。

解题思路

递归,当前节点的长度为左右两节点的和+1;返回该节点的直径最大值(左右长度和的最大值+1)

语言积累和技巧

使用全局变量max来进行最大值的传递
一般可以使用全局变量的方法,还可以使用参数传递的方式

代码链接

https://github.com/lunaDolphi...

查看原文

赞 0 收藏 0 评论 0

blueDolphin 发布了文章 · 2020-09-17

另一个树的子树_leetcode_572

题目描述

给定两个非空二叉树 s 和 t,检验 s 中是否包含和 t 具有相同结构和节点值的子树。s 的一个子树包括 s 的一个节点和这个节点的所有子孙。s 也可以看做它自身的一棵子树。

示例 1:
给定的树 s:

 3
/ \

4 5
/ \
1 2
给定的树 t:

4
/ \
1 2
返回 true,因为 t 与 s 的一个子树拥有相同的结构和节点值。

解题思路

双层递归
1、对节点、左节点、右节点 都对t进行递归,只要有一个成立即成功 ||
2、对两树的对比进行递归,root节点进行对比 空、值对比,然后再进行左右递归,所有节点都相同,且数量相同才能返回true, &&

语言积累和技巧

想通了就很简单,分别进行处理
在处理根节点和左右节点关系的时候,要考虑清楚,用||和&&来处理,代码简洁明了

代码链接

https://github.com/lunaDolphi...
https://github.com/lunaDolphi...

查看原文

赞 0 收藏 0 评论 0

blueDolphin 发布了文章 · 2020-09-16

二叉搜索树转换为单向链表_interview_17.12

题目描述

二叉树数据结构TreeNode可用来表示单向链表(其中left置空,right为下一个链表节点)。实现一个方法,把二叉搜索树转换为单向链表,要求依然符合二叉搜索树的性质,转换操作应是原址的,也就是在原始的二叉搜索树上直接修改。
返回转换后的单向链表的头节点。

示例:

输入: [4,2,5,1,3,null,6,0]
输出: [0,null,1,null,2,null,3,null,4,null,5,null,6]

解题思路

二叉排序树:
1、若它的左子树不空,则左子树上所有结点的值均小于它的根结点的值; 2、若它的右子树不空,则右子树上所有结点的值均大于它的根结点的值; 3、它的左、右子树也分别为二叉排序树
#### 思路一:使用递归,中序遍历,先左边,再处理,再右边
#### 思路二:借用哨兵,仍然使用递归
#### 思路三:使用迭代+栈

语言累计和技巧

使用了前置节点来降低逻辑的处理难度
哨兵的使用

代码链接

https://github.com/lunaDolphi...
https://github.com/lunaDolphi...
https://github.com/lunaDolphi...

查看原文

赞 0 收藏 0 评论 0

blueDolphin 发布了文章 · 2020-09-10

相同的树_leetcode_100

题目描述

给定两个二叉树,编写一个函数来检验它们是否相同。

如果两个树在结构上相同,并且节点具有相同的值,则认为它们是相同的。

示例 1:

输入: 1 1

      / \       / \
     2   3     2   3

    [1,2,3],   [1,2,3]

输出: true

解题思路

一、递归遍历两个树,如果存在一个节点值不同,则置false,然后返回;
二、迭代遍历两个树,如果存在一个节点值不同,则置false,然后返回;

语言积累和技巧

遍历二叉树的两个方法
1、递归---> 深度优先
2、迭代--->queue的使用很巧妙,广度优先

vscode代码链接

https://github.com/lunaDolphi...
https://github.com/lunaDolphi...

查看原文

赞 0 收藏 0 评论 0

blueDolphin 发布了文章 · 2020-09-10

二叉树中第二小的节点_leetcode_671

题目描述

给定一个非空特殊的二叉树,每个节点都是正数,并且每个节点的子节点数量只能为 2 或 0。如果一个节点有两个子节点的话,那么该节点的值等于两个子节点中较小的一个。

给出这样的一个二叉树,你需要输出所有节点中的第二小的值。如果第二小的值不存在的话,输出 -1 。

示例 1:
输入:
2

/ \
2 5

 / \
5   7

输出: 5
说明: 最小的值是 2 ,第二小的值是 5 。

解题思路

题目解析:刚开始解这题没看懂题目意思,根据题目的约束,根节点必然是最小的节点,所以第二小节点就变成了求剩下子节点的最小值
这题想通了就简单

一、 使用递归,
1、如果当前节点和父节点的值不等,那么当前节点就是第二小的节点,剩下的节点就不用管了,直接返回节点值
2、如果当前节点和父节点的值相同,则将当前节点作为根节点进行递推,先判空,然后获取左右两节点的返回值,再根据返回值,看返回上一层的值 a:左/右节点没找到,则返回右/左节点的值,b:如果左右都有返回值,则取小值。

二、使用迭代

1、根据题意,先对根几点进行判断,
2、然后找到剩下所有节点的值中,不等于根节点值的节点的最小值
3、将找到的最小值,综合根节点的左右节点值执行判断
    a、最小值和根节点值不相同,则找到了第二小值,直接返回;
    b、最小值和根节点值相同,再判断,如果最小值和左右节点的大值都相等---->最小值就是根值--->未找到第二小的值,返回-1;
    c、最小值和根节点值相同,如果最小值小于左右节点的大值--->根节点左右值中的大值即使第二小的值--->返回大值

语言积累和技巧

q.offer
q.poll

对题意的理解和对约束条件的使用很重要

vscode 代码链接

https://github.com/lunaDolphi...
https://github.com/lunaDolphi...

查看原文

赞 0 收藏 0 评论 0

blueDolphin 发布了文章 · 2020-09-04

二叉树的路径总和_leetcode_112

问题描述

给定一个二叉树和一个目标和,判断该树中是否存在根节点到叶子节点的路径,这条路径上所有节点值相加等于目标和。

说明: 叶子节点是指没有子节点的节点。

示例: 
给定如下二叉树,以及目标和 sum = 22,

          5
         / \
        4   8
       /   / \
      11  13  4
     /  \      \
    7    2      1

返回 true, 因为存在目标和为 22 的根节点到叶子节点的路径 5->4->11->2。

解题思路

一、使用递归

使用全局变量获取sum的目标,方便在方法中进行对比
每层递归都将上面的和传递过去,然后在每个节点进行数据和的对比
当为叶子节点且和和全局变量的sum一致的时候,直接返回true
如果一直都没有找到的话,则返回false

二、使用迭代

使用queue进行入队和出队,把每层的节点入队
把左右节点val值改成和上层节点的和
用和跟目标值对比

语言积累和技巧

1、使用迭代时,在迭代的参数里面加个数据,就和在节点中增加个属性,有同样的效果,就像本例中的sum,如果在每个节点加个sum,其实也是一样的
2、使用递归也可以从上到下的获取和,就跟迭代是一样的。
3、迭代中也要灵活使用全局变量和迭代方法的参数

vscode 代码链接

https://github.com/lunaDolphi...
https://github.com/lunaDolphi...

查看原文

赞 0 收藏 0 评论 0

blueDolphin 发布了文章 · 2020-09-03

二叉树的最大深度_leetcode_104

题目描述

给定一个二叉树,找出其最大深度。

二叉树的深度为根节点到最远叶子节点的最长路径上的节点数。

说明: 叶子节点是指没有子节点的节点。

示例:
给定二叉树 [3,9,20,null,null,15,7],

3

/ \
9 20

/  \

15 7
返回它的最大深度 3 。

解题思路

1、递归
终止条件: 叶子节点
递归执行:返回最大值(当前最大值、左右节点返回的最大值)+1
2、迭代
终止调价: 叶子节点
借用数组,按深度优先的原则,先扫描一层的节点,然后分别弹出,无叶子节点,则将子节点入队;有叶子节点则返回

语言积累和技巧

queue的poll、offer等方法
使用迭代时,判断条件为,叶子节点返回统计数,非叶子节点,则将非空子节点压入队列中

vscode 代码链接

https://github.com/lunaDolphi...
https://github.com/lunaDolphi...
https://github.com/lunaDolphi...

查看原文

赞 0 收藏 0 评论 0

认证与成就

  • 获得 0 次点赞
  • 获得 0 枚徽章 获得 0 枚金徽章, 获得 0 枚银徽章, 获得 0 枚铜徽章

擅长技能
编辑

(゚∀゚ )
暂时没有

开源项目 & 著作
编辑

(゚∀゚ )
暂时没有

注册于 2020-07-11
个人主页被 360 人浏览