franki Blog

make a small progress every day

剑指offer-平衡二叉树

平衡二叉树输入一棵二叉树的根节点，判断该树是不是平衡二叉树。如果某二叉树中任意节点的左右子树的深度相差不超过1，那么它就是一棵平衡二叉树。示例给定二叉树 [3,9,20,null,null,15,7] 3 / \ 9 20 / \ 15 7 返回 true 。思路后续遍历+剪枝对二叉树做后序遍历，从底至顶返回子树深度，若判定某...

Posted by franki on May 18, 2021

剑指offer-二叉树的深度

二叉树的深度输入一棵二叉树的根节点，求该树的深度。从根节点到叶节点依次经过的节点（含根、叶节点）形成树的一条路径，最长路径的长度为树的深度。例如：给定二叉树 [3,9,20,null,null,15,7]，示例 3 / \ 9 20 / \ 15 7 返回它的最大深度 3 。思路方案一：dfs 利用后序遍历，每次获取当前节点的...

Posted by franki on May 17, 2021

剑指offer-二叉搜索树的第k大节点

二叉搜索树的第k大节点给定一棵二叉搜索树，请找出其中第k大的节点。示例输入: root = [3,1,4,null,2], k = 1 3 / \ 1 4 \ 2 输出: 4 思路方案一：利用中序遍历，把所有的值放到一个数组里面，遍历结束后，返回arr[arr.length-k]，即是所求。方案二：利用逆中序遍历（右-根-左）,依次k–，...

Posted by franki on May 16, 2021

剑指offer-0～n-1中缺失的数字

0～n-1中缺失的数字一个长度为n-1的递增排序数组中的所有数字都是唯一的，并且每个数字都在范围0～n-1之内。在范围0～n-1内的n个数字中有且只有一个数字不在该数组中，请找出这个数字。示例输入: [0,1,3] 输出: 2 思路二分查找，当中间值与中间值在其所在的下标值说明缺失的数字在右边，当中间值与其所在的下标值不等时，继续看mid-1与其下标值是否相等，如果相等说...

Posted by franki on May 15, 2021

剑指offer-两个链表的第一个公共节点

两个链表的第一个公共节点输入两个链表，找出它们的第一个公共节点。示例输入：intersectVal = 8, listA = [4,1,8,4,5], listB = [5,0,1,8,4,5], skipA = 2, skipB = 3 输出：Reference of the node with value = 8 输入解释：相交节点的值为 8 （注意，如果两个列表相交则不能为...

Posted by franki on May 14, 2021

剑指offer-数组中的逆序对

数组中的逆序对在数组中的两个数字，如果前面一个数字大于后面的数字，则这两个数字组成一个逆序对。输入一个数组，求出这个数组中的逆序对的总数。示例输入: [7,5,6,4] 输出: 5 代码 /** * @param {number[]} nums * @return {number} */ var reversePairs = function(nums) { ...

Posted by franki on May 13, 2021

剑指offer-礼物的最大价值

礼物的最大价值在一个 m*n 的棋盘的每一格都放有一个礼物，每个礼物都有一定的价值（价值大于 0）。你可以从棋盘的左上角开始拿格子里的礼物，并每次向右或者向下移动一格、直到到达棋盘的右下角。给定一个棋盘及其上面的礼物的价值，请计算你最多能拿到多少价值的礼物？示例输入: [ [1,3,1], [1,5,1], [4,2,1] ] 输出: 12 解释: 路径 1→3→5...

Posted by franki on May 12, 2021

剑指offer-丑数

丑数我们把只包含质因子 2、3 和 5 的数称作丑数（Ugly Number）。求按从小到大的顺序的第 n 个丑数。示例输入: n = 10 输出: 12 解释: 1, 2, 3, 4, 5, 6, 8, 9, 10, 12 是前 10 个丑数。思路方案1：利用最小堆 - 使用一个集合记录每次与因子乘积后的值，并且把它添加入最小堆 - 不断pop最小堆...

Posted by franki on May 11, 2021

剑指offer-第一个只出现一次的字符

第一个只出现一次的字符在字符串 s 中找出第一个只出现一次的字符。如果没有，返回一个单空格。 s 只包含小写字母。示例 s = "abaccdeff" 返回 "b" s = "" 返回 " " 思路利用空间换时间的思路，采用hash记录每个字符出现的次数，接着遍历一遍即可知道第一个出现一次的字符代码 /** * @param {string} s * @ret...

Posted by franki on May 10, 2021

剑指offer-数据流中的中位数

数据流中的中位数如何得到一个数据流中的中位数？如果从数据流中读出奇数个数值，那么中位数就是所有数值排序之后位于中间的数值。如果从数据流中读出偶数个数值，那么中位数就是所有数值排序之后中间两个数的平均值。例如， [2,3,4] 的中位数是 3 [2,3] 的中位数是 (2 + 3) / 2 = 2.5 设计一个支持以下两种操作的数据结构： void addNum(int num...

Posted by franki on May 9, 2021