牛客网(剑指Offer)在线编程-算法

骑猪看日落 2022-05-18 06:25 233阅读 0赞

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

public class Solution { 
        public boolean Find(int target, int [][] array) {
           int len = array.length - 1;
            for(;len>=0;len--){
                for(int i=0;i<array[len].length;i++){
                    if(target<array[len][i]){
                        break;
                    }else if(target>array[len][i]){
                        continue;
                    }else{
                        return true;
                    }
                }
            }
            return false;
        }
    }

2、请实现一个函数，将一个字符串中的每个空格替换成“%20”。例如，当字符串为We Are Happy.则经过替换之后的字符串为We%20Are%20Happy。

public class Solution { 
        public String replaceSpace(StringBuffer str) {
            if(str == null){
                return null;
            }
            StringBuilder  strb = new StringBuilder();
            for(int i=0;i<str.length();i++){
                if(str.charAt(i) == ' '){
                    strb.append('%');
                    strb.append('2');
                    strb.append('0');
                }else{
                    strb.append(str.charAt(i));
                }
            }
            return strb.toString();
        }
    }

3、输入一个链表，按链表值从尾到头的顺序返回一个ArrayList。

/** * public class ListNode { * int val; * ListNode next = null; * * ListNode(int val) { * this.val = val; * } * } * */
    import java.util.ArrayList;
    public class Solution { 
       ArrayList<Integer> arrayList=new ArrayList<Integer>();
        public ArrayList<Integer> printListFromTailToHead(ListNode listNode) {
            if(listNode!=null){
                this.printListFromTailToHead(listNode.next);
                arrayList.add(listNode.val);
            }
            return arrayList;
        }
    }

4、输入某二叉树的前序遍历和中序遍历的结果，请重建出该二叉树。假设输入的前序遍历和中序遍历的结果中都不含重复的数字。例如输入前序遍历序列\{1,2,4,7,3,5,6,8\}和中序遍历序列\{4,7,2,1,5,3,8,6\}，则重建二叉树并返回。

/** * Definition for binary tree * public class TreeNode { * int val; * TreeNode left; * TreeNode right; * TreeNode(int x) { val = x; } * } */
    public class Solution { 
         public TreeNode reConstructBinaryTree(int [] pre,int [] in) {
             if(pre==null||in==null){
             return null;
        }
            //先序：根左右；中：左根右；后：左右根
            //先序第一个一定是根，在中序中找到根，中序中次值左边的就是左子树右边就是右子树
            java.util.HashMap<Integer,Integer> map= new java.util.HashMap<Integer, Integer>();
            for(int i=0;i<in.length;i++){
                map.put(in[i],i);
            }
            return preIn(pre,0,pre.length-1,in,0,in.length-1,map);
        }
    
          public TreeNode preIn(int[] p,int pi,int pj,int[] n,int ni,int nj,java.util.HashMap<Integer,Integer> map){
    
            if(pi>pj || ni>nj){
                return null;
            }
            TreeNode head=new TreeNode(p[pi]);
            //根据先序的根找到中序中此根的左右子树，index就是中序当中根的下标
            int index=map.get(p[pi]);
            //把中序中下标数比根下标数小的放入左子树中
            //(index-ni)的值是中序中根的左子树中的节点个数
            //新的树中的前序开始点就是pi+1,结束点是开始点加上(index-ni)
            head.left=preIn(p,pi+1,pi+(index-ni),n,ni,index-1,map);
            head.right=preIn(p,pi+(index-ni)+1,pj,n,index+1,nj,map);
            return head;
        }
    }

5、用两个栈来实现一个队列，完成队列的Push和Pop操作。 队列中的元素为int类型。

import java.util.Stack;
    
    public class Solution { 
        Stack<Integer> stack1 = new Stack<Integer>();
        Stack<Integer> stack2 = new Stack<Integer>();
    
        //栈1专门存消息
        public void push(int node) {
            stack1.push(node);
        }
    
        //将栈1的数据全部取出来存进去栈2，栈2的数据就和栈1之前的数据顺序相反了，最先存的数据在最上面，达到和队列先进先出的效果
        //当栈2数据取完之后再去栈1里面获取全部数据，依次循环
        public int pop() {
            if(stack1.isEmpty() && stack2.isEmpty()){
                throw new  RuntimeException("Queue is empty");
            }
            if(stack2.isEmpty()){
                while(!stack1.isEmpty()){
                    stack2.push(stack1.pop());
                }
            }
            return stack2.pop();
        }
    }

6、把一个数组最开始的若干个元素搬到数组的末尾，我们称之为数组的旋转。 输入一个非减排序的数组的一个旋转，输出旋转数组的最小元素。 例如数组\{3,4,5,1,2\}为\{1,2,3,4,5\}的一个旋转，该数组的最小值为1。 NOTE：给出的所有元素都大于0，若数组大小为0，请返回0。

import java.util.ArrayList;
    public class Solution { 
        public int minNumberInRotateArray(int [] array) {
                 //数组为空时
                if(array.length == 0){
                    return 0;
                }
                //前部分数据旋转
                for(int i = 0; i < array.length - 1; i++){
                    if (array[i] > array[i + 1])
                        return array[i + 1];
                }
    
                //全部数据旋转，相当于没有旋转，最小数即为第一个数
                return array[0];
            }
    }

7、大家都知道斐波那契数列，现在要求输入一个整数n，请你输出斐波那契数列的第n项（从0开始，第0项为0）。  
n<=39

public class Solution { 
        public int Fibonacci(int n) {
            int[] data = new int[]{
       0,1,1};
            if(n<3){
                return data[n];
            }
            int resultData = 2;
            int n1 = 1;
            int n2 = 1;
            //斐波那契数列，1,1,2，3,5。。。。滴三项开始是前两项之和
            //f(n) = f(n-1)+f(n-2)
            for(int i= 3;i<= n;i++){
                resultData = n1+n2;
                n1 = n2;
                n2 = resultData;
            }
            return resultData;
        }
    }

8、一只青蛙一次可以跳上1级台阶，也可以跳上2级。求该青蛙跳上一个n级的台阶总共有多少种跳法（先后次序不同算不同的结果）。

public class Solution { 
        public int JumpFloor(int target) {
            //此题依然是求一个斐波那契数列
            //n1 = 1,n2=2,n3=3,n4=5,n5=8.......
            int a=1,b=2,c=0;
            if(target == 1){
                return 1;
            }else if(target == 2){
                return 2;
            }else{
                for(int i=3;i<=target;i++){
                    c = a+b;
                    a=b;
                    b=c;
                }
                return c;
            }
        }
    }

9、一只青蛙一次可以跳上1级台阶，也可以跳上2级……它也可以跳上n级。求该青蛙跳上一个n级的台阶总共有多少种跳法。

public class Solution { 
        public int JumpFloorII(int target) {
            /*因为n级台阶，第一步有n种跳法：跳1级、跳2级、到跳n级 跳1级，剩下n-1级，则剩下跳法是f(n-1) 跳2级，剩下n-2级，则剩下跳法是f(n-2) 所以f(n)=f(n-1)+f(n-2)+...+f(1) 因为f(n-1)=f(n-2)+f(n-3)+...+f(1) 所以f(n)=2*f(n-1)*/
            int a=1,b=0;
            if(target==1){
                return 1;
            }else{
                for(int i=2;i<=target;i++){
                b = 2*a;
                a = b;
            }
            return b;
            }
    
        }
    }

10、我们可以用2\*1的小矩形横着或者竖着去覆盖更大的矩形。请问用n个2\*1的小矩形无重叠地覆盖一个2\*n的大矩形，总共有多少种方法？

public class Solution { 
        public int RectCover(int target) {
            //还是斐波那契数列
            int a =1,b=2,c=0;
            if(target == 1 ){
                return 1;
            }else if(target == 2){
                return 2;
            }else{
                for(int i=3;i<=target;i++){
                    c=a+b;
                    a=b;
                    b=c;
                }
                return c;
            }
        }
    }

11、输入一个整数，输出该数二进制表示中1的个数。其中负数用补码表示。

public class Solution { 
    
        /*如果一个整数不为0，那么这个整数至少有一位是1。如果我们把这个整数减1， 那么原来处在整数最右边的1就会变为0，原来在1后面的所有的0都会变成1(如果最右边的1后面还有0的话)。 其余所有位将不会受到影响。 举个例子：一个二进制数1100，从右边数起第三位是处于最右边的一个1。 减去1后，第三位变成0，它后面的两位0变成了1，而前面的1保持不变， 因此得到的结果是1011.我们发现减1的结果是把最右边的一个1开始的所有位都取反了。 这个时候如果我们再把原来的整数和减去1之后的结果做与运算，从原来整数最右边一个1那一位开始所有位都会变成0。 如1100&1011=1000.也就是说，把一个整数减去1，再和原整数做与运算，会把该整数最右边一个1变成0. 那么一个整数的二进制有多少个1，就可以进行多少次这样的操作。*/
         public int NumberOf1(int n) {
            int count = 0;
            while(n!= 0){
                count++;
                n = n & (n - 1);
             }
            return count;
        }
    }

12、给定一个double类型的浮点数base和int类型的整数exponent。求base的exponent次方。

public class Solution { 
        public double Power(double base, int exponent) {
            double a = 1;
            if(exponent==0){
                return (double)1;
            }else if(exponent < 0){
                 for(int i=-1;i>=exponent;i--){
                    a = base * a;
                }
                return 1/a;
            }else{
                for(int i=1;i<=exponent;i++){
                    a = base * a;
                }
                return a;
            }
      }
    }

13、输入一个整数数组，实现一个函数来调整该数组中数字的顺序，使得所有的奇数位于数组的前半部分，所有的偶数位于数组的后半部分，并保证奇数和奇数，偶数和偶数之间的相对位置不变。

public class Solution { 
        public void reOrderArray(int [] array) {
            int index = 0;//index标志奇数的下标
            int tmp = 0;
            for(int i=0;i<array.length;i++){
                if(array[i]%2 == 1){
                    tmp = array[i];
                    for(int m=i;m>index;m--){
                        array[m] = array[m-1];
                    }
                    array[index] = tmp;
                    index+=1;
                }
            }
        }
    }

14、输入一个链表，输出该链表中倒数第k个结点。

/* public class ListNode { int val; ListNode next = null; ListNode(int val) { this.val = val; } }*/
    public class Solution { 
        public ListNode FindKthToTail(ListNode head,int k) {
            //两个链表，一个链表比另一个短k，当第一个的next为null时，第二个就是倒数第k个链表节点
            ListNode m,n;
            m=n=head;
            int i=0;
            for(;m!=null;i++){
                m=m.next;
                if(i>=k){
                    n=n.next;
                }
            }
            return i < k?null:n;
        }
    }

15、输入一个链表，反转链表后，输出新链表的表头。

/* public class ListNode { int val; ListNode next = null; ListNode(int val) { this.val = val; } }*/
    public class Solution { 
        public ListNode dataNode;
        public ListNode ReverseList(ListNode head) {
            if(head == null){
                return null;
            }
            ListNode pre = null; //当前节点的上一个节点
            ListNode next = null; //当前节点的下一个节点
            while(head!=null){
                //保存当前节点的下一个节点，因为链表断开了
                next = head.next;
                //反转，将当前节点的上一个节点变为下一个节点
                head.next = pre;
                //此时当前节点将变成下一个节点的上一个节点，故变为pre
                pre = head;
                //将当前节点的下一个节点变为当前节点，进行新的一轮反转，当下一个节点为null的时候链表结束
                head = next;
            }
            return pre;
        }
    }

16、输入两个单调递增的链表，输出两个链表合成后的链表，当然我们需要合成后的链表满足单调不减规则。

/* public class ListNode { int val; ListNode next = null; ListNode(int val) { this.val = val; } }*/
    public class Solution { 
        public ListNode Merge(ListNode list1,ListNode list2) {
            if(list1==null){
                return list2;
            }else if(list2==null){
                return list1;
            }
            ListNode newList = null;
            //使用递归，比较两条链的当前节点，小的那条移到下一个节点和第二条的当前节点继续比较
            if(list1.val<list2.val){
                newList = list1;
                newList.next = Merge(list1.next,list2);
            }else{
                newList = list2;
                newList.next = Merge(list1,list2.next);
            }
            return newList;
        }
    }

17、输入两棵二叉树A，B，判断B是不是A的子结构。（ps：我们约定空树不是任意一个树的子结构）

/** public class TreeNode { int val = 0; TreeNode left = null; TreeNode right = null; public TreeNode(int val) { this.val = val; } } */
    public class Solution { 
          /*1.找到相等的根节点 2.依次比较各自的左右儿子*/
        public boolean HasSubtree(TreeNode root1,TreeNode root2) {
            boolean result = false;
             //当Tree1和Tree2都不为零的时候，才进行比较。否则直接返回false
            if(root2 != null && root1 != null){
                 //如果找到了对应Tree2的根节点的点
                if(root1.val == root2.val){
                     //以这个根节点为为起点判断是否包含Tree2
                    result = hasSonTree(root1,root2);
                }
                 //如果找不到，那么就再去root的左儿子当作起点，去判断时候包含Tree2
                if(!result){
                    result = HasSubtree(root1.left,root2);
                }
                 //如果还找不到，那么就再去root的右儿子当作起点，去判断时候包含Tree2
                if(!result){
                    result = HasSubtree(root1.right,root2);
                }
            }
              //返回结果
            return result;
        }
    
        public boolean hasSonTree(TreeNode root1,TreeNode root2){
             //如果Tree2已经遍历完了都能对应的上，返回true
            if(root2 == null){
                return true;
            }
             //如果Tree2还没有遍历完，Tree1却遍历完了。返回false
            if(root1 == null){
                return false;
            }
              //如果其中有一个点没有对应上，返回false
            if(root1.val != root2.val){
                return false;
            }
            //如果根节点对应的上，那么就分别去子节点里面匹配
            return hasSonTree(root1.left,root2.left)&&hasSonTree(root1.right,root2.right);
        }
    }

18、操作给定的二叉树，将其变换为源二叉树的镜像

/** public class TreeNode { int val = 0; TreeNode left = null; TreeNode right = null; public TreeNode(int val) { this.val = val; } } */
    public class Solution { 
        public void Mirror(TreeNode root) {
            if(root != null){
                TreeNode tem = root.left;
                root.left = root.right;
                root.right = tem;
                Mirror(root.left);
                Mirror(root.right);
            }
        }
    }

19、输入一个矩阵，按照从外向里以顺时针的顺序依次打印出每一个数字，例如，如果输入如下4 X 4矩阵： 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 则依次打印出数字1,2,3,4,8,12,16,15,14,13,9,5,6,7,11,10.

import java.util.ArrayList;
    public class Solution { 
        public ArrayList<Integer> printMatrix(int [][] matrix) {
            ArrayList<Integer> list = new ArrayList<Integer>();
            int row=matrix.length;//行数
            int collor=matrix[0].length;//列数
            //计算打印的圈数
            int circle=((row<collor?row:collor)-1)/2+1;//圈数
            for(int i=0;i<circle;i++){
                //从左向右打印
                for(int j=i;j<collor-i;j++)
                    list.add(matrix[i][j]);         
                //从上往下的每一列数据
                for(int k=i+1;k<row-i;k++)
                    list.add(matrix[k][collor-1-i]);
                //判断是否会重复打印(从右向左的每行数据)
                for(int m=collor-i-2;(m>=i)&&(row-i-1!=i);m--)
                    list.add(matrix[row-i-1][m]);
                //判断是否会重复打印(从下往上的每一列数据)
                for(int n=row-i-2;(n>i)&&(collor-i-1!=i);n--)
                    list.add(matrix[n][i]);}
            return list;
        }
    }