美文网首页
【剑指offer】1~10题

【剑指offer】1~10题

作者: 我懒得取名 | 来源:发表于2018-01-17 03:46 被阅读0次

    第一题:

    在一个二维数组中,每一行都按照从左到右递增的顺序排序,每一列都按照从上到下递增的顺序排序。请完成一个函数,输入这样的一个二维数组和一个整数,判断数组中是否含有该整数。

        这是非常简单的一道题,最常规的一种方式就是两个方向上扫描,但是要保证其中一个扫描方向数字是递增的,而另外一个方向上数字是递减的。
        下面给出我的解法,从矩阵中的右上角开始,从右往左扫,当横向当前数的下一个数小于目标数的时候往下少,找到返回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);
        }
    }
    

    相关文章

      网友评论

          本文标题:【剑指offer】1~10题

          本文链接:https://www.haomeiwen.com/subject/dphyoxtx.html