第一题:
在一个二维数组中,每一行都按照从左到右递增的顺序排序,每一列都按照从上到下递增的顺序排序。请完成一个函数,输入这样的一个二维数组和一个整数,判断数组中是否含有该整数。
这是非常简单的一道题,最常规的一种方式就是两个方向上扫描,但是要保证其中一个扫描方向数字是递增的,而另外一个方向上数字是递减的。
下面给出我的解法,从矩阵中的右上角开始,从右往左扫,当横向当前数的下一个数小于目标数的时候往下少,找到返回true,越界返回false。
public class Solution {
public boolean Find(int target, int [][] array) {
for(int i = array[0].length-1; i >= 0; i--) {
if(array[0][i] <= target) {
for(int j = 0; j < array.length; j++) {
if(array[j][i] == target) return true;
}
}
}
return false;
}
}
第二题
请实现一个函数,将一个字符串中的空格替换成“%20”。例如,当字符串为We Are Happy.则经过替换之后的字符串为We%20Are%20Happy。
这题不解释了,太简单,很多编程语言直接用字符串处理函数就能做了,用正则也能做,当然,题目本身可能并不希望你这么干。
public class Solution {
public String replaceSpace(StringBuffer str) {
char[] arr = str.toString().toCharArray();
int len = arr.length;
int blankCount = 0;
for(int i = 0; i < len; i++) {
if(arr[i] == ' ')
blankCount++;
}
int[] res = new int[len+blankCount];
int j = 0;
for(int i = 0; i < len; i++) {
if(arr[i] == ' ') {
res[j++] = '%';
res[j++] = '2';
res[j++] = '0';
} else {
arr[j++] = arr[i];
}
}
StringBuffer sb = new StringBuffer();
for(int i = 0; i < res.length; i++) {
sb.append(res[i]);
}
return sb.toString();
}
}
第三题
输入一个链表,从尾到头打印链表每个节点的值。
最简单的思路就是用栈倒序输出。
public class Solution {
public ArrayList<Integer> printListFromTailToHead(ListNode listNode) {
ArrayList<Integer> list = new ArrayList<>();
Stack<Integer> stack = new Stack<>();
while(listNode != null) {
stack.push(listNode.val);
listNode = listNode.next;
}
while(!stack.isEmpty()) {
list.add(stack.pop());
}
return list;
}
}
第四题
输入某二叉树的前序遍历和中序遍历的结果,请重建出该二叉树。假设输入的前序遍历和中序遍历的结果中都不含重复的数字。例如输入前序遍历序列{1,2,4,7,3,5,6,8}和中序遍历序列{4,7,2,1,5,3,8,6},则重建二叉树并返回。
总算来了个比较有意思的题目。给你前序和中序,让你重构二叉树返回。我们直接按题目中给的例子来讲。
前序遍历是{1,2,4,7,3,5,6,8}
,也就是说 {1}
这个数字就是根。而中序遍历是{4,7,2,1,5,3,8,6}
,从而可以划出两个子集{4,7,2,1}
{5,3,8,6}
分别为组成以{1}
为根的左右子树。
依照这个逻辑下去,就可以得出整棵树的结构了。这显然就是一些重复步骤,用递归去做是最好的方式。再进一步思考,我们只需要知道前序和中序遍历的边界下标,就能在递归过程中计算出我们要得到的数据。接下来,让我们直接看代码。
public class Solution {
public TreeNode reConstructBinaryTree(int [] pre,int [] in) {
return rebuilder(pre, in, 0, pre.length-1, 0, in.length-1);
}
public TreeNode rebuilder(int[] pre, int[] in, int prel, int prer, int inl, int inr) {
if(prel > prer) return null;
TreeNode node = new TreeNode(pre[prel]);
for(int i = inl; i <= inr; i++) {
if(in[i] == pre[prel]) {
node.left = rebuilder(pre, in, prel+1, prel+i-inl, inl, i-1);
node.right = rebuilder(pre, in, prel+i-inl+1, prer, i+1, inr);
break;
}
}
return node;
}
}
第五题
用两个栈来实现一个队列,完成队列的Push和Pop操作。 队列中的元素为int类型。
也是非常简单的一题。要用两个栈模拟队列,我们只需要保持两个原则。第一,当你要push一个元素到其中一个栈时候,另外一个栈必须为空。第二,当你要pop一个元素的时候,必须把栈中的所有元素倾倒到另外一个空栈,然后再pop数据出去。
public class Solution {
Stack<Integer> stack1 = new Stack<Integer>();
Stack<Integer> stack2 = new Stack<Integer>();
public void push(int node) {
while(!stack2.isEmpty()) {
stack1.push(stack2.pop());
}
stack1.push(node);
}
public int pop() {
while(!stack1.isEmpty()) {
stack2.push(stack1.pop());
}
return stack2.pop();
}
}
第六题
把一个数组最开始的若干个元素搬到数组的末尾,我们称之为数组的旋转。 输入一个非递减排序的数组的一个旋转,输出旋转数组的最小元素。 例如数组{3,4,5,1,2}为{1,2,3,4,5}的一个旋转,该数组的最小值为1。 NOTE:给出的所有元素都大于0,若数组大小为0,请返回0。
咋看之下,这题似乎扫描一遍数组就行了。没错,确实如此,但是题目本身是希望你用二分去做的,不然给你非递减这个特性就没有意义了。题目说,非递减数列做旋转,旋转之后其实主要有两种情况,一种就是旋转后和旋转前一样,一种是旋转后和选择前发生了变化(这里暂时忽略数列中过的数全部相等的情况),第一种情况,数列的最后一个数一定是大于第一个数的。第二种情况,最小的数一定在数列中。而这个数列也会分成两个递增的子数列,且两个子序列相连的边界数字一定是递减的,比如:{3,4,5}
{1, 2}
两个递增数列,5和1这两个边界是下降的,从而我们可以得到二分的条件,假设:当前位置为i
,那么当a[i-1] > a[i]
时, i
就是最小的数。
public class Solution {
public int minNumberInRotateArray(int [] array) {
return binarySearch(array, 0, array.length-1);
}
/**
大体上就是一个二分搜索,注意搜索条件即可
*/
public int binarySearch(int[] arr, int l, int r) {
if (arr[0] < arr[arr.length - 1])
return arr[0];
int mid = (l + r) / 2;
// 这一句就是为了覆盖数列数字全部相等的情况
if(mid == r) return arr[r];
if (arr[mid] < arr[mid - 1])
return arr[mid];
int res = 0;
if(l <= r) {
if (arr[mid] < arr[l])
res = binarySearch(arr, l, mid);
else
res = binarySearch(arr, mid, r);
}
return res;
}
}
第七题
大家都知道斐波那契数列,现在要求输入一个整数n,请你输出斐波那契数列的第n项。
n<=39
这题没啥好讲的,为了避免爆栈,应该采用迭代的方式。
public class Solution {
public int Fibonacci(int n) {
if(n == 0)
return 0;
if(n == 1)
return 1;
int count = 1;
Queue<Integer> queue = new LinkedList<Integer>();
queue.add(0);
queue.add(1);
int res = -1;
while(count != n) {
res = queue.poll() + queue.peek();
queue.add(res);
count++;
}
return res;
}
}
第八题
一只青蛙一次可以跳上1级台阶,也可以跳上2级。求该青蛙跳上一个n级的台阶总共有多少种跳法。
这题考察的就是一个递推的是个思想。假设i
表示青蛙要跳上的台阶,当i==1
时,只有一种方法;当i==2
时,可以从上一个台阶,或上上一个台阶跳上去,所有有两种方式,从而可以知道,当i > 1
时,res = step1 + step2
(这里的step1和step2分别表示跳到上一个台阶和跳到上上一个台阶的跳法)。
public class Solution {
public int JumpFloor(int target) {
if(target == 1)
return 1;
if(target == 2)
return 2;
int result = 0;
int step1 = 1, step2 = 1;
target -= 1;
while(target-- != 0) {
result = step1 + step2;
step1 = step2;
step2 = result;
}
return result;
}
}
第九题
一只青蛙一次可以跳上1级台阶,也可以跳上2级……它也可以跳上n级。求该青蛙跳上一个n级的台阶总共有多少种跳法。
这道题,最简单最快速的方法,就是直接用排列组合去做。把n个台阶分成1部分、2部分、3...n部分,c(N,0)+c(N,1)+...+C(N,N) = 2^N。
public class Solution {
public int JumpFloorII(int target) {
return (int)Math.pow(2, target-1);
}
}
第十题
我们可以用21的小矩形横着或者竖着去覆盖更大的矩形。请问用n个21的小矩形无重叠地覆盖一个2*n的大矩形,总共有多少种方法?
这道题的思路其实和第八题非常类似,假设n=5,我们可以看成n=3和n=4两种情况,但是注意:n=3时,剩下2个小矩阵,所以还可以排成2种,但是有其中一种(竖着排列的)会与n=3时候的重复,所以其实也只能排一种。所以我们可以知道:当 n==1
时 res = 1;当n==2
时,res=2,当n>2
时,res = cnt[n-1] + cnt[n-2]。
public class Solution {
public int RectCover(int target) {
if(target == 0)
return 0;
if(target == 1)
return 1;
if(target == 2)
return 2;
return RectCover(target-1) + RectCover(target-2);
}
}
网友评论