CHuiL

二叉搜索树后序遍历序列

剑指offer

题目描述 输入一个整数数组，判断该数组是不是某二叉搜索树的后序遍历的结果。如果是则输出Yes,否则输出No。假设输入的数组的任意两个数字都互不相同 解法 由于后序遍历的最后一个节点为根节点，且由二叉搜索树的特性可以知道，该树可以根据根节点分为左右两个子树（即将数组分为两个部分，可以是空子树），然后在递归判断子树是否也满足这个条件；不满足时则不是二叉搜索树； 代码 class Soluti...

Posted by chl on January 20, 2019

从上往下打印二叉树

剑指offer

题目描述 从上往下打印出二叉树的每个节点，同层节点从左至右打印。 解法 其实就是bfs，广度优先搜索，层次遍历。bfs的思路就是借助一个队列，从根开始入队，然后再依次出队，查看当前节点的邻接节点是否已经被访问（这是对于图来说的，在树中只要直接判断左右节点是否为空然后按左到右的顺序加入到队列即可），没被访问的就入队，然后重复直到队列为空； 代码 class Solution { publi...

Posted by chl on January 19, 2019

栈的压入，弹出序列

剑指offer

题目描述 输入两个整数序列，第一个序列表示栈的压入顺序，请判断第二个序列是否可能为该栈的弹出顺序。假设压入栈的所有数字均不相等。例如序列1,2,3,4,5是某栈的压入顺序，序列4,5,3,2,1是该压栈序列对应的一个弹出序列，但4,3,5,1,2就不可能是该压栈序列的弹出序列。（注意：这两个序列的长度是相等的） 解法 需要开辟一个辅助栈来将压入序列中的数据压入；然后依次判断弹出序列中的元素...

Posted by chl on January 18, 2019

包含min函数的栈

剑指offer

题目描述 定义栈的数据结构，请在该类型中实现一个能够得到栈中所含最小元素的min函数（时间复杂度应为O（1））。 解法一 所以很容易想到的声明一个最小值指针或者索引，然后每次push的时候来比较当前的最小值；删除的时候注意最小值是不是要删除的值，是的话就要重新遍历一遍来寻找最小值，不过在pop()函数里面遇到这种情况的时候就需要时间复杂度为O(n)；不过这样还是能确保在min函数里面时间复...

Posted by chl on January 18, 2019

对称二叉树

剑指offer

题目描述 请实现一个函数，用来判断一颗二叉树是不是对称的。注意，如果一个二叉树同此二叉树的镜像是同样的，定义其为对称的。 例子： 8 / \ 6 6 / \ / \ 5 7 7 5 8 / \ 6 9 / \ / \ 5 ...

Posted by chl on January 15, 2019

正则表达式匹配

剑指offer

题目描述 请实现一个函数用来匹配包括’.’和’‘的正则表达式。模式中的字符’.’表示任意一个字符，而’‘表示它前面的字符可以出现任意次（包含0次）。 在本题中，匹配是指字符串的所有字符匹配整个模式。例如，字符串”aaa”与模式”a.a”和”abaca”匹配，但是与”aa.a”和”ab*a”均不匹配 解法 字符串和模式一个字符一个字符的进行匹配； 当前字符都相等的情况下就移动到下一个字符； ...

Posted by chl on January 15, 2019

链表中倒数第k个节点

剑指offer

题目描述 输入一个链表，输出该链表中倒数第k个结点。 解法 遍历一遍的方法，需要两个指针，一个指针先走k-1步之后，另外一个指针再走； 因为倒数第k个和最后一个数字的位置直接相差k-1步； 但是注意考虑k的大小，如果k<=0或者k大于总数，那么应该处理错误； ##　代码 ListNode* FindKthToTail(ListNode* pListHead, unsigned in...

Posted by chl on January 11, 2019

表示数值的字符串

剑指offer

题目描述 请实现一个函数用来判断字符串是否表示数值（包括整数和小数）。例如，字符串”+100”,”5e2”,”-123”,”3.1416”和”-1E-16”都表示数值。 但是”12e”,”1a3.14”,”1.2.3”,”+-5”和”12e+4.3”都不是。 解法 分析数值的表示为： A [ . [ B ] ] [ e | E C ]; A为小数点前的有符号整数，B为小数点后的无符号整数，...

Posted by chl on January 11, 2019

链表中环的入口节点

剑指offer

题目描述 给一个链表，若其中包含环，请找出该链表的环的入口结点，否则，输出null。 解法 首先判断是否有环，如果链表从中途开始产生了环，那么可以设置两个指针，一个走得快（两步），一个慢（一步），如果最终他们能相遇，则说明有环，而且相遇点在环中； 寻找入口节点，也是设置两个指针，一开始指向头节点，第一个指针先走n步（n为环中节点个数），然后第二个指针再开始走，当他们相遇时指向的节点就是环入...

Posted by chl on December 30, 2018

链表中环的入口节点

剑指offer

题目描述 输入一个整数，输出该数二进制表示中1的个数。其中负数用补码表示。 解法 n个1循环n次； 对于二进制数来说，每次-1都会将最右边的1变为0，而1后面如果还有0的话，将会全部变为1；而如果最右边的1是最后一位，那么就这一位变为0； 如101001 -1 =>101000; 10100 -1 => 10011; 然后再和n自己与，如10100 & 10011 =...

Posted by chl on December 30, 2018

ABOUT ME

just do it