franki Blog

make a small progress every day

剑指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

剑指offer-连续子数组的最大和

连续子数组的最大和输入一个整型数组，数组中的一个或连续多个整数组成一个子数组。求所有子数组的和的最大值。要求时间复杂度为O(n)。示例: 输入: nums = [-2,1,-3,4,-1,2,1,-5,4] 输出: 6 解释: 连续子数组 [4,-1,2,1] 的和最大，为 6。思路动态规划 1 定义两个变量 curSum greatestSum 2 遍历数组，每...

Posted by franki on May 8, 2021

剑指offer-序列化二叉树

序列化二叉树请实现两个函数，分别用来序列化和反序列化二叉树。示例: 你可以将以下二叉树： 1 / \ 2 3 / \ 4 5 序列化为 "[1,2,3,null,null,4,5]" 思路 1 利用层序遍历，序列化二叉树 2 通用利用层序遍历，反序列化二叉树代码 /** * Definition for a binar...

Posted by franki on May 7, 2021

剑指offer-二叉树中和为某一值的路径

二叉树中和为某一值的路径输入一颗二叉树和一个整数，打印出二叉树中的节点值的和为输入整数的所有路径。从树的根节点开始往下一直到叶节点所经过的节点形成一条路径。思路 1 利用深度优先遍历，记录经过的路径，当遍历到叶子节点时，查看当前的路径和与目标值是否相等，若相等，那么说明找到了；若不相等，那么说明不符合；需要回退，继续查找 2 重复1的过程，即可找到所有符合的路径代码 /**...

Posted by franki on May 6, 2021

剑指offer-顺时针打印矩阵

顺时针打印矩阵输入一个矩阵，按照从外向里以顺时针的顺序依次打印出每一个数字。示例：输入：matrix = [[1,2,3],[4,5,6],[7,8,9]] 输出：[1,2,3,6,9,8,7,4,5] 思路按层模拟代码 var spiralOrder = function(matrix) { if (!matrix.length || !matrix[0]...

Posted by franki on May 5, 2021

剑指offer-对称的二叉树

对称的二叉树请实现一个函数，用来判断一棵二叉树是不是对称的。如果一棵二叉树和它的镜像一样，那么它是对称的。思路通过前序遍历和对称前序遍历序列来判断二叉树是不是对称的，如果两个序列是一样的，那么二叉树是对称的。代码 /** * Definition for a binary tree node. * function TreeNode(val) { * this...

Posted by franki on May 4, 2021

剑指offer-二叉树的镜像

二叉树的镜像请完成一个函数，输入一颗二叉树，该函数输出它的镜像。思路递归法 1 终止条件：当节点root为空时，即返回null 2 递推工作：初始化temp，用于暂存root的左子节点开启递归右子节点mirrorTree(root.right)，并将返回值作为root的左子节点开启递归左子节点mirrorTree(temp)，并将返回值作为root的右...

Posted by franki on May 3, 2021

剑指offer-树的子结构

树的子结构输入两棵二叉树A和B，判断B是不是A的子结构。思路 1 在树A中找到和树B的根节点的值一样的节点R 2 判断树A中以R为根节点的子树是不是包含和树B一样的结构代码 /** * Definition for a binary tree node. * function TreeNode(val) { * this.val = val; * t...

Posted by franki on May 2, 2021

剑指offer-合并两个排序的链表

合并两个排序的链表输入两个递增排序的链表，合并这两个链表并使新链表中的节点仍然是递增顺序的。思路 1 链表1的头结点的值小于链表2的头结点的值，因此链表1的头结点是合并后链表的头结点 2 在剩余的结点中，链表2的头结点的值小于链表1的头结点的值，因此链表2的头结点是剩余节点的头结点，把这个节点和之前已经合并好的链表的尾结点链接起来代码 var mergeTwoLists =...

Posted by franki on May 1, 2021