《剑指offer》牛客网1-20

发表于 | 阅读数
字数统计: 2.6k | 阅读时长 ≈ 12

以下代码都在牛客网上提交成功,由于时间紧就不写题解了要学的还很多。

1.二维数组中的查找

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

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
public class Solution {
    public boolean Find(int target, int [][] array) {
        if(array==null||array.length<=0)
            return false;
        int row=array.length-1;
        int col=array[0].length-1;
        int r=0;
        int c=col;
        while(r<=row&&c>=0){
            if(array[r][c]==target){
                return true;
            }else if(array[r][c]<target)
                r++;
            else{
                c--;
            }
        }
        return false;

    }

}

2.替换空格

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

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
public class Solution {
    public String replaceSpace(StringBuffer str) {
        int p1=str.length()-1;
        for(int i=0;i<=p1;i++){
            if(str.charAt(i)==' ')
                str.append("  ");
        }
        int p2=str.length()-1;
        while(p1<p2&&p1>=0){
            char c=str.charAt(p1--);
            if(c==' '){
                str.setCharAt(p2--,'0');
                str.setCharAt(p2--,'2');
                str.setCharAt(p2--,'%');
                

            }else
                str.setCharAt(p2--,c);
                
        }
        return str.toString();
    	
    }

}

3.从尾到头打印链表

题目描述
输入一个链表，按链表从尾到头的顺序返回一个ArrayList。

  • 1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    import java.util.ArrayList;
    public class Solution {
    public ArrayList<Integer> printListFromTailToHead(ListNode listNode) {
        ArrayList<Integer> list=new ArrayList<Integer>();

        if (listNode!=null){
            list.addAll(printListFromTailToHead(listNode.next));
            list.add(listNode.val);
        }
        return list;

    }
    }

4.重建二叉树

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

  • 1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    16
    17
    18
    19
    20
     public class Solution {
    public TreeNode reConstructBinaryTree(int [] pre,int [] in) {
            if(pre==null||in==null||pre.length<=0||in.length<=0)
                throw new RuntimeException("数组不符合规范");
            return construct(pre,in,0,pre.length-1,0,in.length-1);
        }
        public TreeNode construct(int []pre,int[]in,int pStart,int pEnd,int iStart,int iEnd){
            TreeNode root=new TreeNode(pre[pStart]);
            int index=iStart;
            while(root.val!=in[index]&&index<=iEnd){
                index++;
            }
            int leftlength=index-iStart;
            if(leftlength>0)
                root.left=construct(pre,in,pStart+1,pStart+leftlength,iStart,index-1);
            if(leftlength<iEnd-iStart)
                root.right=construct(pre,in,pStart+1+leftlength,pEnd,index+1,iEnd);
            return root;
        }
        }
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
 
 
#### 5.用两个栈实现队列 

**题目描述**
用两个栈来实现一个队列，完成队列的Push和Pop操作。 队列中的元素为int类型。

​```java
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);
        
    }
    
    public int pop() {
        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。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
import java.util.*;
public class Solution {
    public int minNumberInRotateArray(int [] array) {
        if (array == null || array.length <= 0) 
            return 0;
        int low = 0;
        int high = array.length - 1;
        int mid = (low + high) / 2;
        if (array[low] < array[high])
            return array[low];
        if (array[mid] == array[high] && array[mid] == array[low]) {
            for (int i = 1; i <= high; i++) {
                if (array[i] < array[i - 1])
                    return array[i];
            }
            return array[low];
        }
        while (low < high) {
            if (high - low == 1)
                break;
            mid = (low + high) / 2;
            if (array[mid] <= array[high])
                high = mid;
            if (array[mid] > array[high])
                low = mid;
        }
        return array[high]; 
    }
}

7.斐波那契数列

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

1
2
3
4
5
6
7
8
9
10
11
12
13
14
public class Solution {
    public int Fibonacci(int n) {
        if(n<=1)
            return n;
        int fib[]=new int[n+1];
        fib[0]=0;
        fib[1]=1;
        for(int i=2;i<=n;i++)
            fib[i]=fib[i-1]+fib[i-2];
        return fib[n];

    }

}

8.跳台阶

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

1
2
3
4
5
6
7
8
9
10
public class Solution {
    public int JumpFloor(int target) {
        if (target==1 || target==0){
            return 1;
        }
        else{
            return JumpFloor(target-1)+JumpFloor(target-2);
        }
    }
}

9.变态跳台阶

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

1
2
3
4
5
6
public class Solution {
    public int JumpFloorII(int target) {
        return (int)Math.pow(2,target-1
    }

}

10.矩形覆盖

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

1
2
3
4
5
6
7
8
9
10
11
12
public class Solution {
    public int RectCover(int target) {
         if(target <=2){
            return target;
        }else{
            return RectCover(target-1) + RectCover(target-2);
        }
        

    }

}

11.二进制中1的个数

题目描述
输入一个整数，输出该数二进制表示中1的个数。其中负数用补码表示。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
public class Solution {
    public int NumberOf1(int n) {
        int flag=1;
        int count=0;
        while(flag!=0){
            if((flag&n)!=0)
                count++;
            flag=flag<<1;
        }
        return count;

    }

}

12.数值的整数次方

题目描述
给定一个double类型的浮点数base和int类型的整数exponent。求base的exponent次方。

保证base和exponent不同时为0 

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
public class Solution {
    public double Power(double base, int exponent) {
        if(exponent==0){
            return 1;
        }
        if(exponent==1){
            return base;
        }
        boolean isfu=false;
        if(exponent<0){
            exponent=-exponent;
            isfu=true;
        }
        double result=Power(base*base,exponent/2);
        if(exponent%2!=0)
            result=result*base;
        return isfu? 1/result:result;
  }
}

13.调整数组顺序使奇数位于偶数前面

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

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
import java.util.LinkedList;
import java.util.Queue;
public class Solution {
    public void reOrderArray(int [] array) {
        Queue<Integer> queue = new LinkedList<Integer>();
        for(int i=0;i<array.length;i++){
            if(array[i]%2==1){
                queue.add(array[i]);
            }
        }

        for(int i=0;i<array.length;i++){
            if(array[i]%2==0){
                queue.add(array[i]);
            }
        }
     
           for(int i=0;i<array.length;i++){
               array[i]=queue.poll();
        }
    }

}

14.链表中倒数第k个结点

题目描述
输入一个链表，输出该链表中倒数第k个结点。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
public class Solution {
    public ListNode FindKthToTail(ListNode head,int k) {
        if(head==null || k<=0)
            return null;
        ListNode pAhead=head;
        for(int i=1;i<k;i++){
            pAhead=pAhead.next;
            if(pAhead==null)
                return null;
        }
        ListNode pBehind = head;
        while(pAhead.next!=null) {
            pAhead=pAhead.next;
            pBehind=pBehind.next;
        }
        return pBehind;

    }

}

15.反转链表

题目描述
输入一个链表，反转链表后，输出新链表的表头

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
public class Solution {
    public ListNode ReverseList(ListNode head) {
        if(head==null){
            return null;
        }
        ListNode reversehead=head;
        ListNode preNode=null;
        ListNode pNode=head;
        while(pNode!=null){
            ListNode pNext=pNode.next;
            if(pNode.next==null)
                reversehead=pNode;
            pNode.next=preNode;
            preNode=pNode;
            pNode=pNext;
        }
        return reversehead;

    }

}

16.合并两个排序的链表

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

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
public class Solution {
    public ListNode Merge(ListNode list1,ListNode list2) {
        if(list1==null) 
            return list2;
        if(list2==null) 
            return list1;
        if(list1.val<=list2.val){
            list1.next=Merge(list1.next,list2);
            return list1;
        }else{
            list2.next=Merge(list1,list2.next);
            return list2;           
        }     
    }
}

17.树的子结构

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

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
public class Solution {
    public boolean HasSubtree(TreeNode root1,TreeNode root2) {
        if(root1==null||root2==null){
            return false;
        }
        return isSubtreeWithRoot(root1,root2)||HasSubtree(root1.left,root2)||HasSubtree(root1.right,root2);
    }
    public boolean isSubtreeWithRoot(TreeNode root1,TreeNode root2){
        if(root2==null)
            return true;
        if(root1==null)
            return false;
        if(root1.val!=root2.val)
            return false;
        return  isSubtreeWithRoot(root1.left,root2.left)&&isSubtreeWithRoot(root1.right,root2.right);
    }
}

18.二叉树的镜像

题目描述
操作给定的二叉树，将其变换为源二叉树的镜像。

输入描述:
二叉树的镜像定义：

​ 源二叉树
​ 8
​ /
​ 6 10
​ / \ /
​ 5 7 9 11
​ 镜像二叉树
​ 8
​ /
​ 10 6
​ / \ /
​ 7 5 11 9

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
public class Solution {
    public void Mirror(TreeNode root) {
        if(root ==null)
            return;
        if(root.left ==null && root.right ==null)
            return;
        TreeNode tmp = root.left;
        root.left = root.right;
        root.right = tmp;
        if(root.left !=null)
            Mirror(root.left);
        if(root.right !=null)
            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.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
import java.util.ArrayList;
public class Solution {
    public ArrayList<Integer> printMatrix(int [][] matrix) {
        if(matrix==null || matrix.length<=0)
            return null;
        ArrayList<Integer> list=new ArrayList<Integer>();
        int r1=0;
        int r2=matrix.length-1;
        int c1=0;
        int c2=matrix[0].length-1;
        while(r1<=r2&&c1<=c2){
            for(int i=c1;i<=c2;i++){
                list.add(matrix[r1][i]);
            }
            for(int j=r1+1;j<=r2;j++){
                list.add(matrix[j][c2]);
            }
            if(r1!=r2)
                for(int i=c2-1;i>=c1;i--)
                    list.add(matrix[r2][i]);
            if(c1!=c2)
                for(int j=r2-1;j>r1;j--)
                    list.add(matrix[j][c1]);
            r1++;
            r2--;
            c1++;
            c2--;
        }
        return list;
    }
    
}

20.包含min函数的栈

题目描述
定义栈的数据结构，请在该类型中实现一个能够得到栈中所含最小元素的min函数（时间复杂度应为O（1））。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
import java.util.Stack;

public class Solution {
    private Stack <Integer> dataStack=new Stack <Integer>();
    private Stack <Integer> minStack=new Stack <Integer>();
    

    public void push(int node) {
        dataStack.push(node);
        minStack.push(minStack.isEmpty()?node:Math.min(minStack.peek(),node));
    }
    
    public void pop() {
        dataStack.pop();
        minStack.pop();
        
    }
    
    public int top() {
        return dataStack.pop();
        
    }
    
    public int min() {
        return minStack.peek();
        
    }

}
-------------本文结束感谢您的阅读-------------
0%