franki Blog

make a small progress every day

剑指offer-用两个栈实现队列

用两个栈实现队列思路 1 入队的时候，把元素都放入到stack1，例如a b c依次输入的话{c, b, a}，c在栈顶，a在栈底 2 出队的时候，检查stack2是否为空，若为空，把stack1的元素依次出栈并在stack2依次入栈，如果是上述输入的话，即是stack1为空，stack2的序列为{a, b, c},a在栈顶，c在栈低，再把stack2出栈，就能模拟出a -> b...

Posted by franki on April 23, 2021

剑指offer-重建二叉树

重建二叉树输入某二叉树的前序遍历和中序遍历的结果，请重建出该二叉树。假设输入的前序遍历和中序遍历的结果中都不含重复的数字。例如输入前序遍历序列{1, 2, 4, 7, 3, 5, 6, 8}和中序遍历序列{4, 7, 2, 1, 5, 3, 8, 6}，则重建出图2.6所示的二叉树并输出它的头结点。思路 1 前序遍历的特点是（根左右），所以第一个值为根节点 2 找到中序遍历中根...

Posted by franki on April 22, 2021

剑指offer-从尾到头打印链表

从尾到头打印链表思路第一种方案：如果可以该表链表结构，可以先反转链表，然后从头到尾打印链表的值即可。第二种方案：从头到尾遍历链表的话，第一个遍历的需要最后被输出，最后一个遍历的需要第一个被输出，故我们可以利用栈后入先出的特性，把遍历的结构存入栈，最后出栈即是所求。第三种方案：既然思路2可以利用栈来解决问题，递归本质上也是栈的调用，所以利用递归也可以解答此题。代...

Posted by franki on April 21, 2021

剑指offer-替换空格

替换空格实现一个函数，把字符串中的每个空格替换成“%20”。例如”we are happy.”，则输出”we%20are%20happy.” 思路两种方案：在原来的字符串上进行替换，可能覆盖修改在该字符串后面的内存。创建新的字符串并在新的字符串上进行替换，可以分配足够多的内存。(计算出当前字符串存在的空格数量，需要开辟新的字符空间为originalLength + ...

Posted by franki on April 20, 2021

剑指offer-二维数组中的查找

二维数组中的查找有一个矩阵为： 1 2 8 9 2 4 9 12 4 7 10 13 6 8 11 15 思路每次找到右上角的值，与传入的值进行比较，如果前者大于后者需要column减1，如果前者小于传入的值，row加1，如果相等即找到。代码 function find(matrix, rows, columns, number) { let found = fa...

Posted by franki on April 19, 2021

剑指offer-不修改数组找出重复的数字

寻找重复数字 0~N-1 个数字长度为n+1，所有的数字在1~n的范围内，所以至少有一个数字是重复的。请找出任意一个重复的数字，但不能修改输入的数字。例如[2,3,5,4,3,2,6,7]那么对应的输出应该是数字2后者3 思路方法一使用一个n+1的数组，直接把原数组里面的每一个值放到对一个的数组下标里这样很容易知道哪个值是重复的方法二二分法代码方法一代码 ...

Posted by franki on April 17, 2021

剑指offer-寻找重复数字 0~N-1 个数字

寻找重复数字 0~N-1 个数字思路遍历数组每次对比当前下标与当前值是否相等，相等就继续下一个；若不等，继续比较当前值与以当前值作为下标对应的值，若相等，则说明有重复，若不等，就交换两者的位置；这个过程其实就是重排，把数字放到应该在的位置上代码 function duplicate(num) { var arr = []; if (num.leng...

Posted by franki on April 17, 2021

数据结构-线索二叉树

线索二叉树背景: 每次需要知道每个节点的前驱后者后继都需要通过遍历一次二叉树来获得，非常不方便，并且存在很多空的节点，赞成资源浪费；因此线索二叉树应用而生。一个有 n 个节点的二叉链表，每一个节点有指向左右孩子的两个指针域，总共就是 2n 个指针域。n 个节点的二叉树共同拥有 n-1 条分支线（跟节点没有前驱），存在 2n-(n-1) = n+1 个空指针域。将指向前驱和后继...

Posted by franki on April 16, 2021

数据结构-图-章节9

章节 8 拓扑排序 AOV kahh 算法应用场景：工程当中需要用到事件活动，其中图中的顶点表示活动，图中的边表示事件遵循原则： <i,j> i 为 j 的直接前驱，j 为 i 的直接后继，当i无直接前驱时，可以先把这个顶点去掉，加到到一个数组里面并删除以 i 为弧尾的边重复以上过程当所有的顶点都已出现在数组中，说明图中不存在环。以下是 js...

Posted by franki on March 22, 2021

数据结构-图-章节8

章节 8 kruskal 算法最小生成树 kruskal 算法是一种贪婪算法，工作流程如下：创建图中所有的边当以上集合不为空，并且所有的顶点还未覆盖移除集合中最小边检查这条边是否构成一个环或者连接成2颗树，因此需要抛弃这条边，否则的话，把它加入到树当中当上述过程完毕后，就产生了一颗最小生成树为了实现这个算...

Posted by franki on March 13, 2021