franki Blog

make a small progress every day

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

剑指offer-链表中倒数第k个节点

链表中倒数第k个节点输入一个链表，输出该链表中倒数第k个节点。思路双指针 1 第一个指针先走k步 2 第二个指针从头结点开始走，第一个指针同步走 3 当第一个指针走到结尾时 4 返回当前第二个指针指向的位置代码 function getKthFromEnd(head, k) { if (head === null || k === 0) { ...

Posted by franki on April 25, 2021

剑指offer-剪绳子

剪绳子给一根一段长度为n的绳子，请把绳子剪成m段，每一段绳子为k[0] k[1] … k[m]，请问k[0]*k[1]…k[m]可能的乘积是多少？例如长度为8的绳子，我们把它剪成长度为2 3 3的三段，此时得到的最大乘积是18。思路把长度为n的绳子剪成若干段后各段长度乘积，剪第一刀的时候，有n-1中可能的选择，也就是长度分别为1,2,…n-1，因此f(n) = max(f(i)...

Posted by franki on April 24, 2021