前几天把华为的简单编程题做好了,然后看见是十六题不是那样简单的字符串问题了,所以决定先练习一点关于算法的题目,然后就开始写剑指offer的编程题,下面简单的总结一下前十题。
(发现上次写的博客有牛友给我点赞了,哈哈哈哈哈哈哈哈,好高兴啊!决定从今天(2020.3.3)开始每三天都写一篇博客,记录一下菜鸟的成长!谢谢大家)
一:二维数组中的查找
1:题目
在一个二维数组中(每个一维数组的长度相同),每一行都按照从左到右递增的顺序排序,每一列都按照从上到下递增的顺序排序。请完成一个函数,输入这样的一个二维数组和一个整数,判断数组中是否含有该整数。
2:思路
实际上这个二维数组从左到右递增,从上到下递增。不妨设有两个指针(java中无指针,用下标表示,道理相似)一个指向最后一列,一个指向第一行。判断交叉点处的值,若大于目标值,则列指针左移(该列最小的值都大于目标值,故寻找的值肯定都不在那一列),同理,若小于目标值,行指针下移(该行最大的值都小于目标值,故排除该行,行指针下移),直到二者移动到左下角为止,如此可快速找到目标值。
3:代码(java)
public class Solution { public boolean Find(int target, int [][] array) { int len=array.length-1; int i=0; while(len>=0&&i<array[0].length) { if(array[len][i]>target) { len--;//列指针左移 } else if(array[len][i]<target) { i++;//行指针下移 } else { return true; } } return false; } }
二:替换空格
1:题目
请实现一个函数,将一个字符串中的每个空格替换成“%20”。例如,当字符串为We Are Happy.则经过替换之后的字符串为We%20Are%20Happy。
2:思路
暴力解法(即从前往后遍历,遇到空格,后面的数都要后移)复杂的度n的平方,故不妥:
考虑从后往前,先一遍遍历,获得其空格的数量,记为count,可知空格占一个位置,"%20"占三个位置,所以每次出现一个空格,拓展后的字符串要多两个位置,所以替换后的字符比原字符多(2count)个位置,所以从后往前遍历时,在碰到第一个空格之前,只需要把字符串后移(2count)个位置,遇到第一个空格时,只需要将空格(2count,2count-1,2count-2)替换为"02%",剩下的视为子串,注意到此时count-1即可。
3:代码(C++)
class Solution { public: void replaceSpace(char *str,int length) { if(str==NULL||length==0) { return; } int count=0; for(int i=0;i<length;i++)//从后往前 { if(str[i]==' ') { count++; } } for(int i=length-1;i>=0;i--) { if(str[i]!=' ')//非空格直接后移 { str[i+count*2]=str[i]; } else//是空格替换 { str[i+2*count]='0'; str[i+2*count-1]='2'; str[i+2*count-2]='%'; count--;//计数值减一 } } } };
三:从尾到头打印链表
1:题目
输入一个链表,按链表从尾到头的顺序返回一个ArrayList。
2:思路
利用栈,先将链表中的值全部放入栈里面,然后再将栈中内容全部输出到容器,即可得到倒序。具体操作见注释,我觉得这题就是让我们熟悉容器,栈的操作。
3:代码(C++)
/** * struct ListNode { * int val; * struct ListNode *next; * ListNode(int x) : * val(x), next(NULL) { * } * }; */ #include<vector> class Solution { public: vector<int> printListFromTailToHead(ListNode* head) { vector<int> value;//返回的是一个容器 ListNode*p=head;//取表头 stack<int> stk;//初始化栈 while(p!=NULL)//全部入栈 { stk.push(p->val); p=p->next; } while(!stk.empty()) { value.push_back(stk.top());//取栈顶元素入容器里 stk.pop(); } return value; } };
(决定剑指offer的后面题目都用java写,这样看上去代码简洁,易体现算法思想)
四:重建二叉树
1:题目:
输入某二叉树的前序遍历和中序遍历的结果,请重建出该二叉树。假设输入的前序遍历和中序遍历的结果中都不含重复的数字。例如输入前序遍历序列{1,2,4,7,3,5,6,8}和中序遍历序列{4,7,2,1,5,3,8,6},则重建二叉树并返回。
2:思路
树的题目一般用递归。根据前序遍历,我们知道根节点是1,又根据中序遍历,我们知道左子树是{4,7,2},右子树是{5,3,8,6},反过来根据前序遍历{2,4,7},我们又知道了左子树的根节点是2,而左子树只有左子树的左子树{4,7},依次递归下去即可。
3:代码(此代码是一位大佬牛友写的,简洁易懂,在此引用一下)
public class Solution { public TreeNode reConstructBinaryTree(int [] pre,int [] in) { TreeNode root=reConstructBinaryTree(pre,0,pre.length-1,in,0,in.length-1);//重写了一下函数,加上了参数数组下标 return root; } private TreeNode reConstructBinaryTree(int [] pre,int startPre,int endPre,int [] in,int startIn,int endIn) { if(startPre>endPre||startIn>endIn)//数组为空,返回 return null; TreeNode root=new TreeNode(pre[startPre]);/**从前序遍历数组中的第一个值作为跟节点,通过分析,我们知道了左子树元素和右子树元素,然后调用自己分别再将左子树排序右子树排序**/ for(int i=startIn;i<=endIn;i++) { if(in[i]==pre[startPre]){ root.left=reConstructBinaryTree(pre,startPre+1,startPre+i-startIn,in,startIn,i-1); root.right=reConstructBinaryTree(pre,i-startIn+startPre+1,endPre,in,i+1,endIn); break; } } return root; } }
五:用两个栈实现队列
1:题目
用两个栈来实现一个队列,完成队列的Push和Pop操作。 队列中的元素为int类型。
2:思路
队列的性质是怎样输入某序列,就怎样输出某序列,而栈先进后出,将其逆序,但是有两个栈,倒序的倒序就是正序,正好符合队列的性质。(注意到java中的取栈顶元素函数为peek()而不是C++中的pop())
3:代码
import java.util.Stack; public class Solution { Stack<Integer> stack1 = new Stack<Integer>(); Stack<Integer> stack2 = new Stack<Integer>(); public void push(int node) { stack1.push(node);//进队将其保存在栈1中,如果全部进栈,此时已经逆序了 } public int pop()//逆序的逆序 { int s=0; while(stack2.isEmpty())//栈2为空 { while(!stack1.isEmpty())//栈1非空 { s=stack1.peek(); stack2.push(s); stack1.pop(); } } s=stack2.peek(); stack2.pop(); return s; } }
六:旋转数组的最小数字
1:题目
把一个数组最开始的若干个元素搬到数组的末尾,我们称之为数组的旋转。
输入一个非递减排序的数组的一个旋转,输出旋转数组的最小元素。
例如数组{3,4,5,1,2}为{1,2,3,4,5}的一个旋转,该数组的最小值为1。
2:思路
有人提倡用二分法,可将复杂度降低,但是考虑情况会变得复杂。在此一次遍历,算法较简单。
譬如:3 4 5 1 2
从前往后遍历,遇到5比1大,故最小值就是1
譬如3 3 3 3 3
找不到比后面元素大的,此时最小值就是第一个元素
3:代码
import java.util.ArrayList; public class Solution { public int minNumberInRotateArray(int [] array) { if(array.length==0) { return 0; } if(array.length==1) { return array[0]; } for(int i=0;i<array.length;i++) { if(array[i]>array[i+1]) { return array[i+1]; } else if(i==array.length-2) { return array[0]; } } return 0; } }
七:斐波拉契数列(注意此题非常重要,相当于母体对后面的编程也十分重要)
1:题目
大家都知道斐波那契数列,现在要求输入一个整数n,请你输出斐波那契数列的第n项(从0开始,第0项为0)。
n<=39
2:思路
第一种:递归
如果用递归,最好是先写出递归表达式:
n==0,f(n)=0
n==1,f(n)=1
n>=2,f(n)=f(n-1)+f(n-2)
如果用递归也行,思路非常明确,参考代码如下:
if(n<=1) return n; else return Fibonacci(n-1)+Fibonacci(n-2);
3:代码(此代码用的迭代法)
public class Solution { public int Fibonacci(int n) { if(n==0) { return 0; } if(n==1) { return 1; } int a=0; int b=1; int c=1; for(int i=0;i<n-1;i++) { c=a+b; b=c; a=b-a; } return c; } }
八:跳台阶
1:题目
一只青蛙一次可以跳上1级台阶,也可以跳上2级。求该青蛙跳上一个n级的台阶总共有多少种跳法(先后次序不同算不同的结果)。
2:思路
很显然,一级台阶,1个跳法;
二级台阶,2个跳法
三级台阶呢?
当青蛙走三级台阶时,第一步,不是跳一级,就是跳两级;当他跳一级时,还剩两级,前面有结果了,当他跳两级时,还剩一步,前面也有结果。
综上:f(3)=f(2)+f(1)
同理:f(4)=f(3)+f(2)
故写出递归表达式
n==1,f(1)=1;
n==2,f(2)=2;
n>=3,f(n)=f(n-1)+f(n-2)
3:代码
public class Solution { public int JumpFloor(int target) { if(target<1) { return 0; } else if(target==1) { return 1; } else if(target==2) { return 2; } else { return JumpFloor(target-1)+JumpFloor(target-2); } } }
九:变态跳台阶
1:题目
一只青蛙一次可以跳上1级台阶,也可以跳上2级……它也可以跳上n级。求该青蛙跳上一个n级的台阶总共有多少种跳法。
2:思路
模仿第八题我们可以得出以下递归式
f(n)=f(n-1)+f(n-2)+f(n-3)+...+f(1)
又因为
f(n-1)=f(n-2)+f(n-3)+...+f(1)
所以
f(n)=f(n-1)+f(n-1)=2*f(n-1)
当然我们要先把f(1)和f(2)求出来,口算得知f(2)=2,f(1)=1
3:代码
public class Solution { public int JumpFloorII(int target) { if(target<1) { return 0; } else if(target==1) { return 1; } else if(target==2) { return 2; } else { return 2*JumpFloorII(target-1); } } }
十:矩形覆盖
1:题目
我们可以用21的小矩形横着或者竖着去覆盖更大的矩形。请问用n个21的小矩形无重叠地覆盖一个2n的大矩形,总共有多少种方法?
2:思路
首先当n足够大时,将其分为两个阶段,模仿跳台阶,首先第一个12的地方是横着放还是竖着放,详见下图:
我们容易看出其实这就是一个斐波拉契数列,既然我们得到了递推公式,那么写程序就很简单了
3:代码
public class Solution { public int RectCover(int target) { if(target<1) { return 0; } else if(target==1) { return 1; } else if(target==2) { return 2; } else { return RectCover(target-1)+RectCover(target-2); } } }
好的,以上就是剑指offer的前十题,在接下来的三天我会去写华为的编程题,争取三天后更新“关于华为编程的十六到三十题”,朋友们,三天后再见啦!一起加油冲冲冲!