剑指Offer
2020-05-14 16:14:38 4 举报AI智能生成
剑指offer解答以及编程
作者其他创作
大纲/内容
剑指offer
数组
03. 数组中重复的数字
在一个长度为n的数组里的所有数字都在0到n-1的范围内。
数组中某些数字是重复的，但不知道有几个数字是重复的。
也不知道每个数字重复几次。
请找出数组中任意一个重复的数字
数组中某些数字是重复的，但不知道有几个数字是重复的。
也不知道每个数字重复几次。
请找出数组中任意一个重复的数字
04. 二维数组中的查找
在一个 n * m 的二维数组中，每一行都按照从左到右递增的顺序排序，
每一列都按照从上到下递增的顺序排序。
请完成一个函数，
输入这样的一个二维数组和一个整数，判断数组中是否含有该整数。
每一列都按照从上到下递增的顺序排序。
请完成一个函数，
输入这样的一个二维数组和一个整数，判断数组中是否含有该整数。
//定义一个整型数组:3行4列
int a[][] = new int[3][4];
//获取行数---3行
int lenY = a.length;
//获取列数---4列
int lenX = a[0].length;
int a[][] = new int[3][4];
//获取行数---3行
int lenY = a.length;
//获取列数---4列
int lenX = a[0].length;
11. 旋转数组的最小数字
输入一个递增排序的数组的一个旋转，输出旋转数组的最小元素。
15. 二进制中1的个数
输入一个整数，输出该数二进制表示中1的个数。其中负数用补码表示。
17. 打印从1到最大的n位数
输入数字 n，按顺序打印出从 1 到最大的 n 位十进制数。
比如输入 3，则打印出 1、2、3 一直到最大的 3 位数 999
比如输入 3，则打印出 1、2、3 一直到最大的 3 位数 999
39. 数组中出现次数超过一半的数字
数组中有一个数字出现的次数超过数组长度的一半，请找出这个数字。
42. 连续子数组的最大和
输入一个整型数组，数组里有正数也有负数。
数组中的一个或连续多个整数组成一个子数组。求所有子数组的和的最大值。
要求时间复杂度为O(n)。
数组中的一个或连续多个整数组成一个子数组。求所有子数组的和的最大值。
要求时间复杂度为O(n)。
45. 把数组排成最小的数
输入一个正整数数组，把数组里所有数字拼接起来排成一个数，打印能拼接出的所有数字中最小的一个
57. 和为S的两个数字
输入一个递增排序的数组和一个数字S，在数组中查找两个数，使得他们的和正好是S，
如果有多对数字的和等于S，输出两个数的乘积最小的。
如果有多对数字的和等于S，输出两个数的乘积最小的。
57 - II. 和为s的连续正数序列
输入一个正整数 target ，输出所有和为 target 的连续正整数序列（至少含有两个数）。
序列内的数字由小到大排列，不同序列按照首个数字从小到大排列。
序列内的数字由小到大排列，不同序列按照首个数字从小到大排列。
66. 构建乘积数组
给定一个数组 A[0,1,…,n-1]，请构建一个数组 B[0,1,…,n-1]，
其中 B 中的元素 B[i]=A[0]×A[1]×…×A[i-1]×A[i+1]×…×A[n-1]。不能使用除法。
其中 B 中的元素 B[i]=A[0]×A[1]×…×A[i-1]×A[i+1]×…×A[n-1]。不能使用除法。
链表
18. 删除链表的节点
给定单向链表的头指针和一个要删除的节点的值，
定义一个函数删除该节点。
返回删除后的链表的头节点。
定义一个函数删除该节点。
返回删除后的链表的头节点。
06、24. 反转链表
输入一个链表的头节点，从尾到头反过来返回每个节点的值（用数组返回）。
输入一个链表，按链表从尾到头的顺序返回一个ArrayList。
定义一个函数，输入一个链表的头节点，反转该链表并输出反转后链表的头节点。
22. 链表中倒数第k个节点
输入一个链表，输出该链表中倒数第k个结点
25. 合并两个排序的链表
输入两个递增排序的链表，合并这两个链表并使新链表中的节点仍然是递增排序的。
52. 两个链表的第一个公共节点
输入两个链表，找出它们的第一个公共节点。
字符串
05. 替换空格
请实现一个函数，把字符串 s 中的每个空格替换成"%20"。
50. 第一个只出现一次的字符
在字符串 s 中找出第一个只出现一次的字符。
如果没有，返回一个单空格。
如果没有，返回一个单空格。
58 - II. 左旋转字符串
字符串的左旋转操作是把字符串前面的若干个字符转移到字符串的尾部。
67. 把字符串转换成整数
写一个函数 StrToInt，实现把字符串转换成整数这个功能。
栈
09. 用两个栈实现队列
用两个栈实现一个队列。队列的声明如下，
请实现它的两个函数 appendTail 和 deleteHead ，
分别完成在队列尾部插入整数和在队列头部删除整数的功能。
(若队列中没有元素，deleteHead 操作返回 -1 )
请实现它的两个函数 appendTail 和 deleteHead ，
分别完成在队列尾部插入整数和在队列头部删除整数的功能。
(若队列中没有元素，deleteHead 操作返回 -1 )
30. 包含min函数的栈
定义栈的数据结构，请在该类型中实现一个能够得到栈的最小元素的 min 函数在该栈中，
调用 min、push 及 pop 的时间复杂度都是 O(1)。
调用 min、push 及 pop 的时间复杂度都是 O(1)。
31. 栈的压入、弹出序列
输入两个整数序列，第一个序列表示栈的压入顺序，请判断第二个序列是否为该栈的弹出顺序。
假设压入栈的所有数字均不相等。
假设压入栈的所有数字均不相等。
堆
40. 最小的k个数
输入整数数组 arr ，找出其中最小的 k 个数。
二叉树
07.重建二叉树
输入某二叉树的前序遍历和中序遍历的结果，请重建该二叉树。
假设输入的前序遍历和中序遍历的结果中都不含重复的数字
假设输入的前序遍历和中序遍历的结果中都不含重复的数字
26. 树的子结构
输入两棵二叉树A和B，判断B是不是A的子结构。
(约定空树不是任意一个树的子结构)
(约定空树不是任意一个树的子结构)
27. 二叉树的镜像
请完成一个函数，输入一个二叉树，该函数输出它的镜像。
28. 对称的二叉树
请实现一个函数，用来判断一棵二叉树是不是对称的。
32 - I. 从上到下打印二叉树
从上到下打印出二叉树的每个节点，同一层的节点按照从左到右的顺序打印。
32 - II. 从上到下打印二叉树 II
从上到下按层打印二叉树，同一层的节点按从左到右的顺序打印，每一层打印到一行
32 - III. 从上到下打印二叉树 III
请实现一个函数按照之字形顺序打印二叉树，即第一行按照从左到右的顺序打印，
第二层按照从右到左的顺序打印，第三行再按照从左到右的顺序打印，其他行以此类推。
第二层按照从右到左的顺序打印，第三行再按照从左到右的顺序打印，其他行以此类推。
33. 二叉搜索树的后序遍历序列
输入一个整数数组，判断该数组是不是某二叉搜索树的后序遍历结果。
如果是则返回 true，否则返回 false。假设输入的数组的任意两个数字都互不相同。
如果是则返回 true，否则返回 false。假设输入的数组的任意两个数字都互不相同。
54. 二叉搜索树的第k大节点
给定一棵二叉搜索树，请找出其中第k大的节点。
55 - I. 二叉树的深度
输入一棵二叉树的根节点，求该树的深度。
从根节点到叶节点依次经过的节点（含根、叶节点）
形成树的一条路径，最长路径的长度为树的深度。
从根节点到叶节点依次经过的节点（含根、叶节点）
形成树的一条路径，最长路径的长度为树的深度。
55 - II. 平衡二叉树
输入一棵二叉树的根节点，判断该树是不是平衡二叉树。
如果某二叉树中任意节点的左右子树的深度相差不超过1，那么它就是一棵平衡二叉树
如果某二叉树中任意节点的左右子树的深度相差不超过1，那么它就是一棵平衡二叉树
68 - I. 二叉搜索树的最近公共祖先
给定一个二叉搜索树, 找到该树中两个指定节点的最近公共祖先
个节点也可以是它自己的祖先
个节点也可以是它自己的祖先
68 - II. 二叉树的最近公共祖先
给定一个二叉树, 找到该树中两个指定节点的最近公共祖先。
个节点也可以是它自己的祖先
个节点也可以是它自己的祖先
其他
父主题
16. 数值的整数次方
实现函数double Power(double base, int exponent)，求base的exponent次方。
不得使用库函数，同时不需要考虑大数问题。
不得使用库函数，同时不需要考虑大数问题。
约瑟夫环
62. 圆圈中最后剩下的数字
0,1,,n-1这n个数字排成一个圆圈，从数字0开始，每次从这个圆圈里删除第m个数字。
求出这个圆圈里剩下的最后一个数字。
求出这个圆圈里剩下的最后一个数字。
父主题
64. 求1+2+…+n
求 1+2+...+n ，
要求不能使用乘除法、for、while、if、else、switch、case等关键字及条件判断语句（A?B:C）
要求不能使用乘除法、for、while、if、else、switch、case等关键字及条件判断语句（A?B:C）
父主题
65. 不用加减乘除做加法
写一个函数，求两个整数之和，
要求在函数体内不得使用 “+”、“-”、“*”、“/” 四则运算符号。
要求在函数体内不得使用 “+”、“-”、“*”、“/” 四则运算符号。
动态规划
10. 斐波那契数列
斐波那契数列由 0 和 1 开始，之后的斐波那契数就是由之前的两数相加而得出
答案需要取模 1e9+7（1000000007）
答案需要取模 1e9+7（1000000007）
一只青蛙一次可以跳上1级台阶，也可以跳上2级台阶。
求该青蛙跳上一个 n 级的台阶总共有多少种跳法。
答案需要取模 1e9+7（1000000007)
求该青蛙跳上一个 n 级的台阶总共有多少种跳法。
答案需要取模 1e9+7（1000000007)
49. 丑数
我们把只包含因子 2、3 和 5 的数称作丑数（Ugly Number）。
求按从小到大的顺序的第 n 个丑数。
求按从小到大的顺序的第 n 个丑数。
60. n个骰子的点数
把n个骰子扔在地上，所有骰子朝上一面的点数之和为s。输入n，打印出s的所有可能的值出现的概率。
你需要用一个浮点数数组返回答案，其中第 i 个元素代表这 n 个骰子所能掷出的点数集合中第 i 小的那个的概率。
你需要用一个浮点数数组返回答案，其中第 i 个元素代表这 n 个骰子所能掷出的点数集合中第 i 小的那个的概率。
0 条评论
下一页
