剑指Offer(第二版)示例
##【2-3】一个数组中找出重复元素
描述:在一个长度为n的数组里的所有数字都在 0 ~ n-1 的范围内。数组中的某些数字是重复的,但不知道有几个数字重复了,也不知道每个数字重复了几次。 请找出数组中任意一个重复的数字。例如,如果输入长度为7的数组『2,3,1,0,2,5,3』,那么对应的输出是重复的数字 2 或者 3。
##【2-4】一个数组中找出重复元素
描述:在一个二维数组中,每一行都按照从左到右递增的顺序排序,每一列都按照从上到下的递增顺序排序。请完成一个函数, 输入这样的一个二位数组和一个整数,判断数组中是否含有该整数`
##【2-5】替换空格
描述:请实现一个函数,把字符串中的每个空格替换成“%20”。 例如,输入“We are happy.”,则输出“We%20are%20happy.”。
##【2-6】从尾到头打印列表
描述:输入一个链表的头节点,从尾到头倒序打印每个节点的值。
##【2-7】重建二叉树
描述:输入某二叉树的前序遍历和中序遍历的结果,请重建二叉树。假设输入的前序遍历和中序遍历的结果中都不含重复的数字。 例如,输入前序遍历序「1,2,4,7,3,5,6,8」和中序遍历结果『4,7,2,1,5,3,8,6』,则重建二叉树并输出头节点。
##【2-8】题目:二叉树的下一个节点
描述:给定一棵二叉树和其中的一个节点,如何找出中序遍历序列的下一个节点?树种的节点除了有两个分别指向左右子节点的指针, 还有一个指向父节点的指针。中序遍历「d,b,h,e,i,a,f,c,g」
##【2-9】题目:用两个栈实现队列
描述:队列声明如下,请实现它的两个函数appendTail和deleteHead,分别完成在队列尾部插入和队列头部删除节点的功能。
##【2-10】题目:斐波那契数列
描述:求斐波那契数列的第n项
##【2-11】题目:旋转数组中的最小数字
描述:把一个数组最开始的若干个元素搬到数组的末尾,我们称之为数组的旋转。输入一个递增排序数组的一个旋转,输出旋转数组的最小元素。 例如:数组「3,4,5,1,2」为「1,2,3,4,5」的一个旋转,该数组的最小值为1.
##【2-12】题目:矩阵中的路径
描述:请设计一个函数,用来判断在一个矩阵中是否存在一条包含某字符串所有字符的路径。路径可以从矩阵中的任意位置开始, 每一步可以向左上右下移动一格。如果一条路径经过了矩阵的某一格,那么改路径不能再次进入该格子。
##【2-13】题目:机器人的运动范围
描述:地上有一个m行n列的方格。一个机器人从坐标(0,0)的格子开始移动,它每次可以向左右上下移动一格,但不能进去行坐标和列坐标的数位之和大于K的格子。 例如,当k=18时,机器人能够进去方格(35,37),因为3+5+3+7=18.请问机器人最多到达多少个格子?
##【2-14】题目:剪绳子
描述:给你一根长度为n的绳子,请把绳子剪成m段(m,n都是整数,n>1并且m>1),每段绳子的长度记为k[0],k[1],...k[m]。 请问k[0]k[1]...k[m]可能的最大乘积是多少?例如,绳子长度为8时,分别剪成2,3,3三段,乘积最大18。
##【2-15】题目:二进制中1的个数
描述:请实现一个函数,输入一个整数,输出该数二进制表示中的1的个数。 例如:把9表示成1001,有2位是1。因此,如果输入9,则该函数输出2。