没有合适的资源?快使用搜索试试~ 我知道了~
首页剑指offer题解(Java代码实现)
资源详情
资源评论
资源推荐
一、前言
本文主要记录个人刷剑指offer的过程,一来加深记忆,二来便于复习加强,题目部分为自己解答,其他的有些参考
借鉴了牛客还有其他博客上的答案,望各位大佬轻喷,侵删。
二、题目
1、二维数组中的查找
题目描述:
在一个二维数组中(每个一维数组的长度相同),每一行都按照从左到右递增的顺序排序,每一列都按照从上
到下递增的顺序排序。请完成一个函数,输入这样的一个二维数组和一个整数,判断数组中是否含有该整数。
解题思路: 从题目给的条件来看:每一行从左到右递增,每一列从上到下递增,把每一行看成有序数组,这正好符
合二分查找的规律
这道题还有一种思路,利用每一行从左到右递增,每一列从上到下递增的规律,选取右上角或者左下角的元素a与
target进行比较,(本题我们选取左下角的点为例) 当target小于元素a时,那么target必定在元素a所在列的上方,此
时让元素往上走; 当target大于元素a时,那么target必定在元素a所在行的右边,此时让元素往右走;
//二分查找
public boolean find2(int target, int[][] array) {
int row = array.length;
int col = array[0].length;
if (row == 0 || col == 0)
return false;
if (target < array[0][0] || target > array[row - 1][col - 1])
return false;
for(int i=0; i<row; i++){
int low=0,high=col-1,mid;
while(low <= high){
mid = low+(high - low)/2;
if(target == array[i][mid])
return true;
else if(target < array[i][mid])
high = mid -1;
else
low = mid +1;
}
}
return false;
}
public boolean find1(int target, int[][] array) {
int row = array.length;
int col = array[0].length;
2、替换空格
题目描述:
请实现一个函数,将一个字符串中的每个空格替换成“%20”。例如,当字符串为We Are Happy.则经过替换之后
的字符串为We%20Are%20Happy。
解题思路: 利用辅助空间,创建一个字符数组用来存放字符串,然后利用for循环遍历一遍,遇到空格直接接
上“%20”。
3、从头到尾打印链表
题目描述:
输入一个链表,按链表值从尾到头的顺序返回一个ArrayList。
解题思路: 使用栈,利用栈先进后出的特点将链表从尾到头打印
if (row == 0 || col == 0)
return false;
if (target < array[0][0] || target > array[row - 1][col - 1])
return false;
int x = row - 1, y = 0;
while (x >= 0 && y <= col - 1) {//从左下开始判定,遇小向右,遇大向上。
if (target == array[x][y]){
return true;
}else if (target > array[x][y]){
y++;
}else{
x--;
}
}
return false;
}
public String replaceSpace(StringBuffer str) {
String s = str.toString();
char[] c = s.toCharArray();
StringBuilder sb = new StringBuilder();
for(int i=0; i<c.length; i++){
if(c[i] == ' '){
sb.append("%20");
}else{
sb.append(c[i]);
}
}
return sb.toString();
}
使用递归
4、重建二叉树
题目描述:
输入某二叉树的前序遍历和中序遍历的结果,请重建出该二叉树。假设输入的前序遍历和中序遍历的结果中都
不含重复的数字。例如输入前序遍历序列{1,2,4,7,3,5,6,8}和中序遍历序列{4,7,2,1,5,3,8,6},则重建二叉树并返
回。
解题思路: 二叉树的前序遍历顺序是:先访问根节点,然后遍历左子树,再遍历右子树。 中序遍历顺序是:中序遍
历根节点的左子树,然后是访问根节点,最后中序遍历右子树。 1、二叉树的前序遍历序列一定是该树的根节点 2、
中序遍历序列中根节点前面一定是该树的左子树,后面是该树的右子树 从上面可知,题目中前序遍历的第一个节点
{1}一定是这棵二叉树的根节点,根据中序遍历序列,可以发现中序遍历序列中节点{1}之前的{4,7,2}是这棵二叉树的
左子树, {5,3,8,6}是这棵二叉树的右子树。然后,对于左子树,递归地把前序子序列{2,4,7}和中序子序列{4,7,2}看成
新的前序遍历和中序遍历序列。此时,对于这两个序列, 该子树的根节点是{2},该子树的左子树为{4,7}、右子树为
空,如此递归下去(即把当前子树当做树,又根据上述步骤分析)。{5,3,8,6}这棵右子树的分析也是这样。
public ArrayList<Integer> printListFromTailToHead(ListNode listNode) {
if(listNode == null)
return null;
Stack<Integer> stack = new Stack<Integer>();
ArrayList<Integer> array = new ArrayList<Integer>();
while(listNode != null){
stack.push(listNode.val);
listNode = listNode.next;
}
while(!stack.isEmpty()){
array.add(stack.pop());
}
return array;
}
public ArrayList<Integer> printListFromTailToHead(ListNode listNode) {
ArrayList<Integer> array = new ArrayList<>();
if (listNode != null) {
array.addAll(printListFromTailToHead(listNode.next));
array.add(listNode.val);
}
return array;
}
public TreeNode reConstructBinaryTree(int[] pre, int[] in) {
if(pre.length == 0 || in.length == 0)
return null;
return reConstructBinaryTree(pre, in, 0, pre.length-1, 0, in.length-1);
}
//构建方法,pStart和pEnd分别是前序遍历序列数组的第一个元素和最后一个元素;
//iStart和iEnd分别是中序遍历序列数组的第一个元素和最后一个元素。
5、用两个栈实现队列
题目描述:
用两个栈来实现一个队列,完成队列的Push和Pop操作。 队列中的元素为int类型。
解题思路: 两个栈1和2,栈1用来实现队列的push操作,栈2用来实现pop操作
入队:将元素进栈1
出队:判断栈2是否为空,如果为空,则将栈1中所有元素pop,并push进栈2,然后栈2出栈;
public TreeNode reConstructBinaryTree(int[] pre,int[] in,int pStart,int pEnd,int
iStart,int iEnd){
TreeNode tree = new TreeNode(pre[pStart]);//建立根结点
tree.left = null;
tree.right = null;
if(pStart == pEnd && iStart == iEnd){//递归终止条件
return tree;
}
int root = 0;
for(root=iStart; root<iEnd; root++){//遍历中序数组中的根结点
if(pre[pStart] == in[root]){
break;
}
}
//划分左右子树
int leftLength = root - iStart;
int rightLength = iEnd - root;
if(leftLength > 0){//重建左子树
tree.left = reConstructBinaryTree(pre, in, pStart+1, pStart+leftLength,
iStart, root-1);
}
if(rightLength > 0){//重建右子树
tree.right = reConstructBinaryTree(pre, in, pStart+leftLength+1, pEnd,
root+1, iEnd);
}
return tree;
}
Stack<Integer> stackPush = new Stack<Integer>();//用于push的栈
Stack<Integer> stackPop = new Stack<Integer>();//用于pop的栈
public void push(int node) {
stackPush.push(node);
}
public int pop() {
if(stackPop.isEmpty() && stackPush.isEmpty()){
throw new IllegalArgumentException("队列已空!");
}else if(stackPop.isEmpty()){
while(!stackPush.isEmpty()){
stackPop.push(stackPush.pop());
}
}
6、旋转数组的最小数字
题目描述:
把一个数组最开始的若干个元素搬到数组的末尾,我们称之为数组的旋转。 输入一个非减排序的数组的一个旋
转,输出旋转数组的最小元素。 例如数组{3,4,5,1,2}为{1,2,3,4,5}的一个旋转,该数组的最小值为1。 NOTE:
给出的所有元素都大于0,若数组大小为0,请返回0。
解题思路: 采用二分法解答这个问题,mid = low + (high - low)/2,需要考虑三种情况:
(1)array[mid] > array[high]: 出现这种情况的array类似[3,4,5,6,0,1,2],此时最小数字一定在mid的右边。故
low = mid + 1
(2)array[mid] == array[high]: 出现这种情况的array类似 [1,0,1,1,1] 或者[1,1,1,0,1],此时最小数字不好判断在
mid左边还是右边,这时只好一个一个试 ,故 high = high - 1
(3)array[mid] < array[high]: 出现这种情况的array类似[2,2,3,4,5,6,6],此时最小数字一定就是array[mid]或者在
mid的左边。因为右边必然都是递增的。故 high = mid 注意这里有个坑:如果待查询的范围最后只剩两个数,
那么mid 一定会指向下标靠前的数字,比如 array = [4,6] array[low] = 4 ;array[mid] = 4 ; array[high] = 6 ;如果
high = mid - 1,就会产生错误, 因此high = mid,但情形(1)中low = mid + 1就不会错误
7、斐波那契数列
题目描述:
大家都知道斐波那契数列,现在要求输入一个整数n,请你输出斐波那契数列的第n项(从0开始,第0项为
0)。n<=39
解题思路: 在数学上,斐波纳契数列以如下被以递推的方法定义:F(1)=1,F(2)=1, F(3)=2, F(n)=F(n-1)+F(n-2)
(n>=4,n∈N*)
递归法
return stackPop.pop();
}
public static int minNumberInRotateArray(int[] array){
if(array == null || array.length == 0)
return 0;
int low=0, high=array.length-1;
while(low < high){
int mid = low + (high-low)/2;
if(array[mid] > array[high]){
low = mid + 1;
}else if(array[mid] == array[high]){
high = high - 1;
}else{
high = mid;
}
}
return array[low];
}
剩余47页未读,继续阅读
Felix_ar
- 粉丝: 47
- 资源: 2
上传资源 快速赚钱
- 我的内容管理 收起
- 我的资源 快来上传第一个资源
- 我的收益 登录查看自己的收益
- 我的积分 登录查看自己的积分
- 我的C币 登录后查看C币余额
- 我的收藏
- 我的下载
- 下载帮助
会员权益专享
最新资源
- 2023年中国辣条食品行业创新及消费需求洞察报告.pptx
- 2023年半导体行业20强品牌.pptx
- 2023年全球电力行业评论.pptx
- 2023年全球网络安全现状-劳动力资源和网络运营的全球发展新态势.pptx
- 毕业设计-基于单片机的液体密度检测系统设计.doc
- 家用清扫机器人设计.doc
- 基于VB+数据库SQL的教师信息管理系统设计与实现 计算机专业设计范文模板参考资料.pdf
- 官塘驿林场林防火(资源监管)“空天地人”四位一体监测系统方案.doc
- 基于专利语义表征的技术预见方法及其应用.docx
- 浅谈电子商务的现状及发展趋势学习总结.doc
- 基于单片机的智能仓库温湿度控制系统 (2).pdf
- 基于SSM框架知识产权管理系统 (2).pdf
- 9年终工作总结新年计划PPT模板.pptx
- Hytera海能达CH04L01 说明书.pdf
- 数据中心运维操作标准及流程.pdf
- 报告模板 -成本分析与报告培训之三.pptx
资源上传下载、课程学习等过程中有任何疑问或建议,欢迎提出宝贵意见哦~我们会及时处理!
点击此处反馈
安全验证
文档复制为VIP权益,开通VIP直接复制
信息提交成功
评论0