- 博客(175)
- 收藏
- 关注
RSS订阅原创 剑指offer-js 矩阵中的路径
矩阵中的路径题目描述：请设计一个函数，用来判断在一个矩阵中是否存在一条包含某字符串所有字符的路径。路径可以从矩阵中的任意一个格子开始，每一步可以在矩阵中向左，向右，向上，向下移动一个格子。如果一条路径经过了矩阵中的某一个格子，则该路径不能再进入该格子。 例如 [ a b c e][ s f c s][ a d e e] 矩阵中包含一条字符串"bcced"的路径，但是矩阵中不包含"abcb"路径， 因为字符串的第一个字符b占据了矩阵中的第一行第二个格子之后，路径不能再次进入该格子。
2020-08-10 11:51:27
380
1
原创 剑指offer-js 机器人的运动范围
机器人的运动范围题目描述： 地上有一个m行和n列的方格。一个机器人从坐标0,0的格子开始移动，每一次只能向左，右，上，下四个方向移动一格，但是不能进入行坐标和列坐标的数位之和大于k的格子。 例如，当k为18时，机器人能够进入方格（35,37），因为3+5+3+7 = 18。但是，它不能进入方格（35,38）， 因为3+5+3+8 = 19。请问该机器人能够达到多少个格子？问题分析：其实题意就是在一个矩阵范围内找出 和小于等于某一个值的所有点，进行计数那么相应的 边界值就出来了：不超出矩阵范
2020-08-10 11:22:01
340
原创 剑指offer-js 剪绳子
剪绳子题目描述：给你一根长度为n的绳子，请把绳子剪成整数长的m段（m、n都是整数，n>1并且m>1，m<=n），每段绳子的长度记为k[1],...,k[m]。请问k[1]x...xk[m]可能的最大乘积是多少？例如，当绳子的长度是8时，我们把它剪成长度分别为2、3、3的三段，此时得到的最大乘积是18。 输入描述: 输入一个数n，意义见题面。（2 <= n <= 60）输出描述: 输出答案。 示例1 输入 8 输出 18问题分析：动态规划的
2020-08-08 18:04:16
307
原创 剑指offer-js 序列化二叉树
序列化二叉树题目描述：请实现两个函数，分别用来序列化和反序列化二叉树二叉树的序列化是指：把一棵二叉树按照某种遍历方式的结果以某种格式保存为字符串，从而使得内存中建立起来的二叉树可以持久保存。序列化可以基于先序、中序、后序、层序的二叉树遍历方式来进行修改，序列化的结果是一个字符串，序列化时通过 某种符号表示空节点（#），以 ！ 表示一个结点值的结束（value!）。二叉树的反序列化是指：根据某种遍历顺序得到的序列化字符串结果str，重构二叉树。例如，我们可以把一个只有根节点为1的二叉树序列
2020-08-08 15:06:55
205
原创 剑指offer-js 二叉搜索树的第k个结点
二叉搜索树的第k个结点题目描述：给定一棵二叉搜索树，请找出其中的第k小的结点。例如， （5，3，7，2，4，6，8） 中，按结点数值大小顺序第三小结点的值为4。问题分析：二叉搜索树：左子树都比根结点小，右子树都比根结点大中序遍历：左结点-根结点-右结点，对于二叉搜索树来说，中序遍历就是有序的序列对于本题而言，中序遍历之后，找第 k-1 个就行代码展示：/* function TreeNode(x) { this.val = x; this.left = null;
2020-08-08 11:48:34
194
原创 剑指offer-js 按之字形打印二叉树
按之字形打印二叉树推荐阅读二叉树从上到下打印把二叉树打印成多行三道题其实是递进关系 二叉树从上到下打印： while 下遍历所有节点，将节点插入到 res[] ，中 return 把二叉树打印成多行： while下遍历所有节点，然后实现 BFS（通过循环实现），将每层的的数据放到 temp[] 中，然后放到 res[] 中return 按之字形打印二叉树： while下遍历所有节点，然后实现 BFS（通过循环实现），将每层的的数据放到 temp[] 中，按顺序进行反转(判断 fla
2020-08-08 10:20:24
227
原创 剑指offer-js 把二叉树打印成多行
把二叉树打印成多行题目描述：从上到下按层打印二叉树，同一层结点从左至右输出。每一层输出一行。问题分析：剑指offer-js 二叉树从上到下打印和上面这道题结合起来，其实对于BFS,主要在于如何对同一个层级的节点数据进行展开，循环 就是一个利器，通过对该层节点的循环完成展开代码展示：/* function TreeNode(x) { this.val = x; this.left = null; this.right = null;} */function Pri
2020-08-07 21:30:31
205
原创 剑指offer-js 对称的二叉树
对称的二叉树题目描述：请实现一个函数，用来判断一棵二叉树是不是对称的。注意，如果一个二叉树同此二叉树的镜像是同样的，定义其为对称的。代码展示：/* function TreeNode(x) { this.val = x; this.left = null; this.right = null;} */function isSymmetrical(pRoot){ // 直接写就好了 if(pRoot == null) return tr
2020-08-07 12:44:53
169
1
原创 剑指offer-js 二叉树的下一个结点
二叉树的下一个结点题目描述：给定一个二叉树和其中的一个结点，请找出中序遍历顺序的下一个结点并且返回。注意，树中的结点不仅包含左右子结点，同时包含指向父结点的指针。问题分析：两种方法：方法一：暴力解法 1，根据给出的结点求出整棵树的根节点 2，根据根节点递归求出树的中序遍历，存入vector 3，在vector中查找当前结点，则当前结点的下一结点即为所求。方法二：画出图形总结要求结点的规律 （放一下官方题解给出的示意图），然后使用js实现它代码展示：/*functio
2020-08-07 11:32:36
268
原创 剑指offer-js 删除链表中重复的结点
删除链表中重复的结点相似题目：leetcode-java 删除排序链表中的重复元素–保留一个元素leetcode-java 删除排序链表中的重复元素II – 不保留重复元素上面用的方法会多一点，可以从多个角度理解一下题目描述： 在一个排序的链表中，存在重复的结点，请删除该链表中重复的结点，重复的结点不保留，返回链表头指针。 例如，链表1->2->3->3->4->4->5 处理后为 1->2->5问题分析： 方法一： 直接修改
2020-08-05 11:51:02
201
原创 剑指offer-js 链表中环的入口节点
链表中环的入口节点相似推荐判断链表中有无环判断是否有环并返回入口节点(java)题目描述：给一个链表，若其中包含环，请找出该链表的环的入口结点，否则，输出null。问题分析：两种方法： 1，哈希表法 创建一个数组，遍历所有链表元素，判断是否在数组内，若不在，则加入；若在，就将第一个在的节点返回 2，快慢指针，floyd算法 借用两张官方解法放出的图片第一张图告诉我们，对于快慢指针，当slow和fast相遇时，相遇点在C, 同时推导出 =>2(AB+BC) = A
2020-08-04 11:27:04
274
原创 剑指offer-js 字符串的排列
字符串的排列题目描述：输入一个字符串,按字典序打印出该字符串中字符的所有排列。例如输入字符串abc,则按字典序打印出由字符a,b,c所能排列出来的所有字符串abc,acb,bac,bca,cab和cba。输入描述: 输入一个字符串,长度不超过9(可能有字符重复),字符只包括大小写字母。问题分析：固定一个值与其他值交换位置顺序，然后将生成的字符串放入res，放入时判断有无重复注意： 两次代码中的swap交换：第一次：可以看成abc->abc；第二次：abc->bac
2020-08-01 10:51:59
248
原创 剑指offer-js 二叉搜索树与双向链表
二叉搜索树与双向链表题目描述：输入一棵二叉搜索树，将该二叉搜索树转换成一个排序的双向链表。要求不能创建任何新的结点，只能调整树中结点指针的指向。代码展示：/* function TreeNode(x) { this.val = x; this.left = null; this.right = null;} */function Convert(pRootOfTree){//1，构建左子树为双向链表，返回链表头节点left//2，定位到左双向链表最后一个节点//
2020-07-28 11:49:55
177
原创 剑指offer-js 扑克牌顺子
扑克牌顺子题目描述：LL今天心情特别好,因为他去买了一副扑克牌,发现里面居然有2个大王,2个小王(一副牌原本是54张^_^)...他随机从中抽出了5张牌,想测测自己的手气,看看能不能抽到顺子,如果抽到的话,他决定去买体育彩票,嘿嘿！！“红心A,黑桃3,小王,大王,方片5”,“Oh My God!”不是顺子.....LL不高兴了,他想了想,决定大\小 王可以看成任何数字,并且A看作1,J为11,Q为12,K为13。上面的5张牌就可以变成“1,2,3,4,5”(大小王分别看作2和4),“So Luck
2020-07-28 11:09:05
146
原创 剑指offer-js 孩子们的游戏(圆圈中最后剩下的数)
孩子们的游戏(圆圈中最后剩下的数)题目描述：每年六一儿童节,牛客都会准备一些小礼物去看望孤儿院的小朋友,今年亦是如此。HF作为牛客的资深元老,自然也准备了一些小游戏。其中,有个游戏是这样的:首先,让小朋友们围成一个大圈。然后,他随机指定一个数m,让编号为0的小朋友开始报数。每次喊到m-1的那个小朋友要出列唱首歌,然后可以在礼品箱中任意的挑选礼物,并且不再回到圈中,从他的下一个小朋友开始,继续0...m-1报数....这样下去....直到剩下最后一个小朋友,可以不用表演,并且拿到牛客名贵的“名侦
2020-07-27 11:51:59
220
原创 剑指offer-js 复杂链表的复制
复杂链表的复制题目描述：输入一个复杂链表（每个节点中有节点值，以及两个指针，一个指向下一个节点，另一个特殊指针random指向一个随机节点），请对此链表进行深拷贝，并返回拷贝后的头结点。注意，输出结果中请不要返回参数中的节点引用，否则判题程序会直接返回空。问题分析：两种方式： 1，利用map对象，使用哈希表，通过哈希表来对应拷贝前后的两个复杂链表， 通过原链表的random作为键，取到新链表的random应该指向的结点。 2，直接递归复制代码展示：/*function
2020-07-27 11:48:26
143
原创 剑指offer-js 平衡二叉树
平衡二叉树题目描述：输入一棵二叉树，判断该二叉树是否是平衡二叉树。在这里，我们只需要考虑其平衡性，不需要考虑其是不是排序二叉树问题分析：遍历左右子树，当左子树-右子树的深度大于1时，返回-1，否则返回二叉树的深度代码展示：/* function TreeNode(x) { this.val = x; this.left = null; this.right = null;} */// 平衡二叉树：任意一子节点的左右子树高度差不大于1 (包含空树)// 思路
2020-07-25 16:51:19
162
原创 剑指offer-js 和为s的两个数字&&和为s的连续正数序列
和为s的两个数字&&和为s的连续正数序列和为s的两个数字题目描述：输入一个递增排序的数组和一个数字S，在数组中查找两个数，使得他们的和正好是S，如果有多对数字的和等于S，输出两个数的乘积最小的。输出描述: 对应每个测试案例，输出两个数，小的先输出。问题分析：两个for循环找到这样的数字，进行乘积比较，然后决定数组是否push这两个数字代码展示：function FindNumbersWithSum(array, sum){ // 找到这样的数字，进行乘积比
2020-07-25 16:24:47
167
原创 剑指offer-js 数组中只出现一次的数字
数组中只出现一次的数字题目描述：一个整型数组里除了两个数字之外，其他的数字都出现了两次。请写程序找出这两个只出现一次的数字。问题分析：js中用对象做这类题，比较直观，python中的话字典也不错代码展示：function FindNumsAppearOnce(array){ // 对这些计数的问题，使用对象是一个不错的方法 // return list, 比如[a,b]，其中ab是出现一次的两个数字 var arr = []; var nums = {};
2020-07-25 15:14:56
321
原创 剑指offer-js 两个链表的第一个公共节点
两个链表的第一个公共节点题目描述：输入两个链表，找出它们的第一个公共结点。（注意因为传入数据是链表，所以错误测试数据的提示是用其他方式显示的，保证传入数据是正确的）。问题分析：有这样几种思路： 链表中有关的相交就是结点相等。三种方法： 第一种：双重循环， 遍历第一个链表，然后遍历另一个链表，如果相等，return 第二种：哈希表 遍历一个链表并且将链表存在哈希表中，而后遍历另一个链表，如果相等，return 第三种：双指针法（使用此方法） 两条链表，共同的部分
2020-07-25 15:01:01
358
原创 剑指offer-js 丑数
丑数题目描述：把只包含质因子2、3和5的数称作丑数（Ugly Number）。例如6、8都是丑数，但14不是，因为它包含质因子7。 习惯上我们把1当做是第一个丑数。求按从小到大的顺序的第N个丑数。问题分析：两种思路： 1，直接算 -- 这种思路过于繁琐，应该还有其他直接算的简便算法 a，从num=2进行遍历 b，找出这个数的所有因子 c，找出所有因子中的质因子 d，判断有无除了2，3，5之外的质因子 e,若满足条件，则将该数字放在数组中，后续按
2020-07-25 11:09:38
122
原创 剑指offer-js 第一个只出现一次的字符
第一个只出现一次的字符题目描述：在一个字符串(0<=字符串长度<=10000，全部由字母组成)中找到第一个只出现一次的字符,并返回它的位置, 如果没有则返回 -1（需要区分大小写）.（从0开始计数）问题分析： 遍历字符串，判断字符是否放在 对象res中，若不在，则加进去，同时 value=1， 若在，则对原来的值+1 遍历结束后，找到第一个value等于1的字符，然后在字符串中找到他的index索引代码展示：function FirstNotRepeatingChar
2020-07-24 11:53:46
378
原创 剑指offer-js 把数组排成最小的数
把数组排成最小的数题目描述：输入一个正整数数组，把数组里所有数字拼接起来排成一个数，打印能拼接出的所有数字中最小的一个。例如输入数组{3，32，321}，则打印出这三个数字能排成的最小数字为321323。问题分析：两种思路： 1，找出所有的可能排列，然后进行大小的比较 2，通过组合比较确定先后顺序，进行拼接代码展示：错误的代码var numbers = [3,32,321];function PrintMinNumber(numbers){ console.log("nu
2020-07-24 11:33:16
451
原创 剑指offer-js 整数中1出现的次数
整数中1出现的次数题目描述： 求出1~13的整数中1出现的次数,并算出100~1300的整数中1出现的次数？为此他特别数了一下1~13中包含1的数字有1、10、11、12、13因此共出现6次,但是对于后面问题他就没辙了。ACMer希望你们帮帮他,并把问题更加普遍化,可以很快的求出任意非负整数区间中1出现的次数（从1 到 n 中1出现的次数）。问题分析：两种方式： 1，找规律，找出1-9，10-99，100-999 这种个，十，百位上1出现的规律进行求解。。。(真心考验人，所以采用第二种方法，
2020-07-23 11:38:50
404
原创 剑指offer-js 连续子数组的最大和
连续子数组的最大和题目描述： HZ偶尔会拿些专业问题来忽悠那些非计算机专业的同学。今天测试组开完会后,他又发话了:在古老的一维模式识别中,常常需要计算连续子向量的最大和,当向量全为正数的时候,问题很好解决。但是,如果向量中包含负数,是否应该包含某个负数,并期望旁边的正数会弥补它呢？例如:{6,-3,-2,7,-15,1,2,2},连续子向量的最大和为8(从第0个开始,到第3个为止)。给一个数组，返回它的最大连续子序列的和，你会不会被他忽悠住？(子向量的长度至少是1)问题分析：动态规划问题，核
2020-07-23 11:10:16
240
原创 剑指offer-js 最小的k个数
最小的k个数题目描述：输入n个整数，找出其中最小的K个数。例如输入4,5,1,6,2,7,3,8这8个数字，则最小的4个数字是1,2,3,4。问题分析：排序，拿数据，不同的是排序的方法排序方法： 1，使用数组的sort() 2，快排 3，堆排序代码展示：function GetLeastNumbers_Solution(input, k){ //1,直接排序，push数据，return var res = []; if(input.length <=0
2020-07-23 10:39:09
354
原创 剑指offer-js 二叉树中和为某一值的路径
二叉树中和为某一值的路径题目描述：输入一颗二叉树的根节点和一个整数，按字典序打印出二叉树中结点值的和为输入整数的所有路径。路径定义为从树的根结点开始往下一直到叶结点所经过的结点形成一条路径。问题分析：大概的思想就是：二叉树的遍历（递归）+动态规划（push，pop数据）每次遍历的时候先将数字的值放入数组，计算数字的值是否满足条件（等于给出的num），同时当数字满足条件时是否还有多余节点，如果有，则已有路径无效，将数组中数字弹出；如果没有，则已有路径有效，将数组的值放入最终数组，然后将数组中
2020-07-22 11:45:03
270
原创 剑指offer-js 求1+2+3+...+n
题目描述：求1+2+3+...+n，要求不能使用乘除法、for、while、if、else、switch、case等关键字及条件判断语句（A?B:C）。问题分析：都不能用，就用递归好了代码展示：function Sum_Solution(n){ // write code here if(n <= 0) return n; let ans = n; return ans + Sum_Solution(n - 1);}...
2020-07-20 11:33:44
228
原创 git相关命令操作及多人协同开发流程
git相关命令操作及多人协同开发流程git 安装安装git -- git bash 等(官网上下载安装就好)推荐安装教程git 初始化配置1.配置用户名，邮箱git config --global user.name "git用户名"git config --global user.email "git邮箱"2.设置ssh key查看是否存在密钥cd ~/.sshls若无，则生成密钥ssh-keygen -t rsa -C "git邮箱"3.将key 添加到 git账号s
2020-07-10 11:07:18
183
原创 剑指offer-js 数组中出现次数超过一半的数字
数组中出现次数超过一半的数字JS中的Map对象1，js创建map对象 var map = new Map();2.将键值对放入map对象 map.set("key",value)3.根据key获取map值 map.get(key)4.删除map指定对象 delete map[key] 或 map.delete(key)5.循环遍历map map.forEach(function(key){ console.log("key",key) //输出的是map中的value值 })
2020-07-09 11:43:04
570
原创 剑指offer-js 二叉树的深度
二叉树的深度题目描述：输入一棵二叉树，求该树的深度。从根结点到叶结点依次经过的结点（含根、叶结点）形成树的一条路径，最长路径的长度为树的深度。问题分析：用递归一层一层往下走，同时记上数字就行，注意这种递归时的思想，通过max选出最深的代码展示：/* function TreeNode(x) { this.val = x; this.left = null; this.right = null;} */function TreeDepth(pRoot){
2020-07-09 10:37:35
209
原创 剑指offer-js 二叉搜索树的后序遍历
二叉搜索树的后序遍历题目描述：输入一个整数数组，判断该数组是不是某二叉搜索树的后序遍历的结果。如果是则输出Yes,否则输出No。假设输入的数组的任意两个数字都互不相同。问题分析：二叉搜索树的特点： 根结点的左子树都小于根结点，根结点的右子树都大于根结点思路： 1，根据特性找到根结点 2，从后往前找到第一个不大于根结点的索引，记录下位置 3，以这个结点为分割，进行递归代码展示：function VerifySquenceOfBST(sequence){ // wr
2020-06-10 20:19:57
186
原创 剑指offer-js 二叉树从上到下打印
二叉树从上到下打印题目描述：从上往下打印出二叉树的每个节点，同层节点从左至右打印。问题分析：从上到下遍历，自然要记住顺序，那么一个数组用来存节点，一个用来存要打印的值按照顺序： res 添加值，queue添加节点，按照左右顺序添加，这样，每次从queue中出队的时候都有顺序代码展示：/* function TreeNode(x) { this.val = x; this.left = null; this.right = null;} */function
2020-06-07 12:39:52
215
原创 剑指offer-js 栈的压入、弹出序列
栈的压入、弹出序列题目描述：输入两个整数序列，第一个序列表示栈的压入顺序，请判断第二个序列是否可能为该栈的弹出顺序。假设压入栈的所有数字均不相等。例如序列1,2,3,4,5是某栈的压入顺序，序列4,5,3,2,1是该压栈序列对应的一个弹出序列，但4,3,5,1,2就不可能是该压栈序列的弹出序列。（注意：这两个序列的长度是相等的）问题分析： 借用一个辅助的栈，遍历压栈顺序，先讲第一个放入栈中，这里是1， 然后判断栈顶元素是不是出栈顺序的第一个元素，这里是4， 很显然1≠4，所以我们继续压栈，
2020-06-04 20:40:13
317
原创 剑指offer-js 包含min函数的栈
包含min函数的栈题目描述：定义栈的数据结构，请在该类型中实现一个能够得到栈中所含最小元素的min函数（时间复杂度应为O（1））。注意：保证测试中不会当栈为空的时候，对栈调用pop()或者min()或者top()方法。问题分析：js里面的栈，大多数时候都和数组脱不了关系，在python里，栈也可以由列表来实现用一个新的数组，完成添加，删除，自然不是什么难事，主要是要想到用数组来解决代码展示：var stack = [];//数组function push(node){ sta
2020-06-04 20:35:46
184
原创 剑指offer-js 顺时针打印矩阵
顺时针打印矩阵题目描述：输入一个矩阵，按照从外向里以顺时针的顺序依次打印出每一个数字，例如，如果输入如下4 X 4矩阵： 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 则依次打印出数字1,2,3,4,8,12,16,15,14,13,9,5,6,7,11,10.问题分析：定义四个变量，表示左上和右下的打印范围，按照 右--下--左--上 一次旋转打印结束后，往对角分别前进和后退一个单位，也就是四个变量的值进行更改，直到最后循环结束代码展示：functio
2020-05-31 19:48:28
289
原创 剑指offer-js 二叉树的镜像
二叉树的镜像题目描述：操作给定的二叉树，将其变换为源二叉树的镜像。输入描述:二叉树的镜像定义：源二叉树 8 / \ 6 10 / \ / \ 5 7 9 11 镜像二叉树 8 / \ 10 6 / \ / \ 11 9 7 5问题分析：将左右子节点调换，利用递归走完所有的节点代码展示：/* function Tre
2020-05-31 12:05:56
230
原创 剑指offer-js 树的子结构
树的子结构题目描述：输入两棵二叉树A，B，判断B是不是A的子结构。（ps：我们约定空树不是任意一个树的子结构）问题分析：判断B是不是A的子树，那么就必须有两个操作， 遍历A子树找对应的根结点， 遍历B结点比较A树的子结构是否和B树相同通过递归完成B树节点的逐个比较，return 结果代码展示：/* function TreeNode(x) { this.val = x; this.left = null; this.right = null;} */fu
2020-05-30 12:18:55
186
原创 剑指offer-js 合并两个排序的链表
合并两个排序的链表题目描述：输入两个单调递增的链表，输出两个链表合成后的链表，当然我们需要合成后的链表满足单调不减规则。问题分析：对于已经排序的两个链表来说，合成一个不减的链表，核心就是通过比较，把小的放在链表前面，然后进行逐个元素的循环，当有一个链表循环结束之后，就把另一个剩余的直接挂上去两种方式： 1，采用递归的方式(核心还是比较) 2，创建一个新链表，通过比较，依次挂载节点代码展示：/*function ListNode(x){ this.val = x; t
2020-05-29 12:10:14
218
原创 剑指offer-js 反转链表
反转链表题目描述：输入一个链表，反转链表后，输出新链表的表头。问题分析：利用三指针，通过链表的遍历完成顺序的反转1，创建前后指针2，用next指针指向剩余链表的头部，进行保存；3，让当前遍历到的链表结点与链表断开，再去连接链表头部pre；4，接着更新pre，让它指向当前结点；5，让链表头部参数指向下一个结点。代码展示：/*function ListNode(x){ this.val = x; this.next = null;}*/function Rever
2020-05-27 13:20:46
177
空空如也
空空如也
TA创建的收藏夹 TA关注的收藏夹
TA关注的人