franki Blog

make a small progress every day

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

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

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

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

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

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

剑指offer-序列化二叉树

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

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

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

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

剑指offer-对称的二叉树

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

剑指offer-二叉树的镜像

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

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

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

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