剑指offer——链表中环入口节点 题目:给一个链表,若其中包含环,请找出该链表的环的入口结点,否则,输出null。 解题思路:通过设置两个指针,快慢指针,其中快指针每次走两步,满指针每次走一步 草图如下: 其中从开始到环的入口长度为x,假设在环(环长度为n)上的B点相遇,设环入口到B点为a,则B到A(顺时针)为n-a 有次可推出: 快指针走过的长度: x+n*K+a(其中...

树的子结构

剑指offer

  

2019-06-03 05:02:12

第十六题:判断是否为树的子结构   题目描述 输入两棵二叉树A,B,判断B是不是A的子结构。(ps:我们约定空树不是任意一个树的子结构)    解析:            rootA     rootB           ①判...

题目描述 输入一个链表,输出该链表中倒数第k个结点。 思路:倒数第k个结点就是正数第n-k+1个结点,其中n是链表的长度。这里我们就需要先遍历链表得到它的长度。然后第二次遍历找到第n-k+1个就是倒数第k个结点。 思路2:可以定义两个指针,一个快指针,一个慢指针。快指针先向前走k-1步,慢指针不动,从第k步开始,两个指针一起走。当快指针走到尾结点时,慢指针恰好走到倒数第k个。   &nb...

题目 输入一个整数,输出该数二进制表示中1的个数。其中负数用补码表示。 思路 1、算术移位与逻辑移位 在计算机指令中,移位操作是一种基本操作,是一种直接对二进制数据的位运算操作。 而移位运算又包含了逻辑移位(logical shift)和算术移位(arithmetic shift)两种。 逻辑移位:移出去的位丢弃,空缺位(vacant bit)用 0 填充。 算术移位:移出去的位丢弃,空缺位(va...

链表中倒数第k个结点

剑指offer  链表

  

2019-06-28 06:20:08

链表中倒数第k个结点 输入一个链表,输出该链表中倒数第k个结点。 思路 解法一 列表。 利用辅助空间stack,遍历链表,将链表中的所有结点添加到辅助空间中,利用列表的索引操作返回倒数第k个结点。 解法二 指针。 创建慢指针和快指针。利用等间隔法可以得到链表中倒数第k个节点。注意异常处理。如果k大于链表长度,那么fast先走时就会越界。 算法比较 解法一额外空间复杂度为O(n),时间复杂度为O(n...

面试题32-2:分行层序打印二叉树 从上到下按层打印二叉树,同一层的结点按从左到右的顺序打印,每一层打印到一行。 分行打印,用两个变量一个指示当前行结点数,一个指示下一行结点数。在队列里入栈和出栈时就能维护了。当前行走到0就打完了一行,换行把下一行拿上来。 面试题32-3:分行层序之字形打印二叉树 请实现一个函数按照之字形顺序打印二叉树,即第一行按照从左到右的顺序打印,第二层按照从右到左的顺序打印...

思路1 基于Partition函数的O(n)算法,受快速排序的算法的启发,在随机快速排序的算法中,我们先在数组中随机的选择一个数字,然后调数组中数字的顺序,使得比选中的数字小数字排在它的左边,比选中的数字大的数字都排在它的右边。比如这个选中的数字的下标刚好是n/2,那么这个数字就是数组中的中位数。如果它的下标大于n/2,那么中位数应该位于它的左边,我们可以接着在它的左边部分的数组中查找。如果它的下...

左旋转字符串

剑指offer

  

2019-07-15 12:20:25

思路 以”abcdeftg”为例,我们可以把它分为两个部分,由于想把它的前两个字符一道后面,我们就把前面两个字符分到第一部分,把后面的所有字符都分到第二个部分。我们先反转这两部分,于是就得到了“bagfedc",接下来我们再翻转整个字符串,得到了”cdefgab"刚好就是把原始字符串左旋转2位的结果。...

面试题39:数组中超过一半的数字 数组中有一个数字出现的次数超过数组长度的一半,请找出这个数字。例如输入一个长度为9的数组{1, 2, 3, 2, 2, 2, 5, 4, 2}。由于数字2在数组中出现了5次,超过数组长度的一半,因此输出2。 解法1 数字超出一半,随机选中该数字的概率就很大。可以随机选一个数字,然后用快排的Partition划分一下,小的放左边,大的放右边,如果当前在中间位置,就说...

题目:输入某二叉树的前序遍历和中序遍历的结果,请重建该二叉树,假设输入的前序遍历和中序遍历的结果中都不含重复的数字。例如,输入前序遍历序列{1,2,4,7,3,5,6,8}和中序遍历{4,7,2,1,5,3,8,6},则重建如图2.6所示的二叉树并输出它的头节点。 分析: 前序遍历:先根,再左,后右; 中序遍历:先左,再根,后右。 那么前序遍历的第一个是根,在中序遍历中找到根位置,即可确定左右子树...