剑指offer练习题实现（java版，持续更新中）

忘是亡心i 2022-09-27 06:23 131阅读 0赞

书：《剑指offer-名企面试官精讲典型编程题》  
心语：已经大三下了，平时写点小程序，始终难登大雅之堂。借此书，练习一下编程能力

面试题3、二维数组的查找  
题目：在一个二维数组中，每一行都按照从左往右的递增顺序，每一列按从上到下进行递增排序。完成一个函数，输入参数数组和一个整数，查找整数是否在这个数组中。  
数组例如：  
int\[\]\[\] array = \{  
\{1,2,8,9\},  
\{2,4,9,12\},  
\{4,7,10,13\},  
\{6,8,11,15\}  
\};

--------------------

思路选取：若选取中间的任意值进行比较的时候会存在重合部分，所以右上角或者左下角的值开始查找

public class ArraySearch {
        public static void main(String[] args) {
            int[][] array = {
                    {
       1,2,8,9},
                    {
       2,4,9,12},
                    {
       4,7,10,13},
                    {
       6,8,11,15}};
            ArraySearch as = new ArraySearch();
            //测试数据
            System.out.println("查找结果为："+as.search(array, 9));
            System.out.println("查找结果为："+as.search(array, 99));
            System.out.println("查找结果为："+as.search(array, 15));
            System.out.println("查找结果为："+as.search(array, 1));
    
        }
        public boolean search(int[][] array,int value){
            if(array==null)
                throw new NullPointerException("该数组为空");
            boolean result=false;
            int rows=array[0].length;      //数组的行数
            int columns=array.length;      //数组的列数
            int column = columns-1;   //查找的行数
            int row=0;
            while(row<rows&&column>=0){
                if(array[row][column]==value){
                    System.out.println("查找成功在["+row+", "+column+"]");
                    return true;
                }else if(value<array[row][column]){
                //索引value小于当前的角上值 继续往左查找
                    column--;
                }else{
                    row++;
                }
            }
            return result;
        }
    
    }

面试题4、替换空格  
字符串 “We are happy”  
将空格替换成%20  
*解法1 顺序替换*  
从头开始遍历遇到第一个空格就进行移位替换成%20  
由于每遇到一个空格就要进行移位操作  
时间复杂度O(n^2)  
×不使用  
解法2 逆向思考 从尾部进行替换  
1、先算出空格数 得出额外需要的空间 2\*空格数  
2、从后往前移，每遇到一个空格 移动2\*现有空格数

面试题5、从尾到头打印链表

java实现  
1、实现结点的创建

public class Node<T> {
        public T data;
        public Node<T> next;
        public Node(T data){
            this.data=data;
            next=null;
        }
    }

2、链表类 仅实现插入和显示链表消息  
思路：如果要求在不改变原链表的情况下进行反向输出链表信息  
可以利用栈先进后出（FILO）的特性即可解决此问题

public class LinkList {
        private Node<Integer> head;
        private Node<Integer> tail;
    
        public static void main(String[] args) {
            LinkList ll = new LinkList();
            for(int i=0;i<10;i++){
                ll.addNode(i);
            }
            ll.display();
            ll.displaybydeserialized();
        }
    
        public void  addNode(int data){
            Node<Integer> NowNode =new Node<Integer>(data);
            if(head==null){
                head=NowNode;
                tail=head;
            }else{
            tail.next=NowNode;
            tail=tail.next;
            }
        }
    
        public boolean isEmpty(){
            if(head==null)
                return true;
            return false;   
        }
        public void display(){
            if(isEmpty()){
                System.out.println("空链表");
                return ;
            }
            Node<Integer> NowNode = head;
            while(NowNode!=null){
                System.out.print(NowNode.data+"\t");
                NowNode=NowNode.next;
            }
            System.out.println();
        }
        public void displaybydeserialized(){
            if(isEmpty()){
                System.out.println("空链表");
                return ;
            }
            Stack mStack = new Stack();
            Node<Integer> NowNode = head;
            while(NowNode!=null){
                mStack.push(NowNode);
                NowNode=NowNode.next;
            }
            while(!mStack.isEmpty()){
               System.out.print(mStack.pop().data+"\t");
            }
            System.out.println();
        }
    }

3、利用栈进行输出

/** * 栈是限定仅在表尾进行插入和删除操作的线性表 在栈顶进行插入和删除操作 * * @author SJ-PC * */
    public class Stack { 
        public Node<Integer> top;
        public Node<Integer> bottom;
    
        // 在尾部增加一个结点
        public void push(Node<Integer> node) {
            if (bottom == null) {
                bottom = node;
                top = bottom;
            } else {
                top.next = node;
                top = top.next;
            }
        }
    
        // 在尾部删除一个结点
        public Node<Integer> pop() {
            // 从栈底进行遍历到栈顶之前一个结点
            if (bottom == null || top == null) {
                throw new NullPointerException("栈为空");
            } else {
                Node<Integer> temp = top; // 暂时存放top值
                Node<Integer> NowNode = bottom;
                while (NowNode.next != top) { // 出现空指针
                    if (bottom == top) {
                        bottom = null;
                        top=null;
                        break;
                    } else {
                        NowNode = NowNode.next;
                    }
                }
                top = NowNode; // top向栈顶bottom移动一个结点
                return temp;
            }
    
        }
    
        public boolean isEmpty() {
            if (bottom == null) {
                return true;
            }
            return false;
        }
    
    }

测试：  
单个结点  
![这里写图片描述][SouthEast]

面试题6、重构二叉树  
由二叉树的前序和中序结果生成二叉树  
比如  
前序：int\[\] PreOrder = \{ 1, 2, 4, 7, 3, 5, 6, 8 \};中序： int\[\] Inorder = \{ 4, 7, 2, 1, 5, 3, 8, 6 \};  
主要思想：  
**每次在前序遍历中取父结点 ，然后在中序遍历中找到父结点的位置，这样既可判定左右子树。**  
同样的，在前序遍历中左子树中找父结点， 在中序遍历总找左子树的父结点，依次下去可用递归方式解决问题。

详细代码：  
1，二叉树的结构类

public class BinaryTreeNode {
        int value;
        BinaryTreeNode LeftNode;
        BinaryTreeNode RightNode;
        public BinaryTreeNode(int value) {
            this.value = value;
        }
    }

2、构建二叉树

/* * 1 * 47(2) 5(3)86 (4)7 (5) (6)8 * (7) (8) */
    public class BuildBinaryTree {
        public static void main(String[] args) {
    
    
            int[] PreOrder = { 1, 2, 4, 7, 3, 5, 6, 8 };
            int[] Inorder = { 4, 7, 2, 1, 5, 3, 8, 6 };
            BinaryTreeNode root=BuildBinaryTree.buildBinary(PreOrder, Inorder);
            //后序答案 :74258631
            afterorder(root);
    
        }
    
        public static void afterorder(BinaryTreeNode root){
            if(root!=null){
                afterorder(root.LeftNode);
                afterorder(root.RightNode);
                System.out.print(root.value+"\t");
            }
    
        }
    
        public static BinaryTreeNode buildBinary(int[] preorder, int[] inorder) {
            if(preorder==null||inorder==null){
                return null;
            }
            int rootvalue = preorder[0];
            System.out.println(rootvalue);
            BinaryTreeNode root = new BinaryTreeNode(rootvalue);
            System.out.println(searchIndex(rootvalue, inorder));
            return constructOneNode(preorder,inorder,0,preorder.length-1,0,inorder.length-1);
        }
    
        private static BinaryTreeNode constructOneNode(int[] preorder,
                int[] inorder, int startPreorder, int endPreorder, int startInOrder, int endInOrder) {
            if(startPreorder>endPreorder||startInOrder>endInOrder){
                return null;
            }
            BinaryTreeNode node = new BinaryTreeNode(preorder[startPreorder]);
            int index=0;  //在中序遍历中获得当前父节点的位置
            while(index<=endInOrder&&inorder[index]!=node.value){
                index++;
            }
            int offset=index-startInOrder;
    
            node.LeftNode=constructOneNode(preorder, inorder, 
                    startPreorder+1, startPreorder+offset, startInOrder, startInOrder+offset-1);
            node.RightNode=constructOneNode(preorder, inorder,
                    startPreorder+offset+1, endPreorder, index+1, endInOrder);
            return node;
        }
    
        public static int searchIndex(int value, int[] array) {
            if (array == null) {
                throw new NullPointerException("传入数组为空");
            }
            for (int i = 0; i < array.length; i++) {
                if (array[i] == value) {
                    return i;
                }
            }
            return -1;
    
        }
    
    }

[SouthEast]: /images/20220708/6536b638c1c9454eb4ea42f79f800500.png