欢迎您访问程序员文章站本站旨在为大家提供分享程序员计算机编程知识!
您现在的位置是: 首页  >  IT编程

【好书推荐】《剑指Offer》之硬技能(编程题7~11)

程序员文章站 2022-06-19 17:08:48
本文例子完整源码地址:https://github.com/yu-linfeng/BlogRepositories/tree/master/repositories/sword 《【好书推荐】《剑指Offer》之软技能》 《【好书推荐】《剑指Offer》之硬技能(编程题1~6)》 持续更新,敬请关注 ......

本文例子完整源码地址:https://github.com/yu-linfeng/blogrepositories/tree/master/repositories/sword

《【好书推荐】《剑指offer》之软技能》

《【好书推荐】《剑指offer》之硬技能(编程题1~6)》

持续更新,敬请关注公众号:coderbuff,回复关键字“sword”获取相关电子书。

 

7.重建二叉树

题目:输入某二叉树的前序遍历和中序遍历的结果,请重建该二叉树。例如:输入前序遍历序列{1, 2, 4, 7, 3, 5, 6, 8}和中序遍历序列{4, 7, 2, 1, 5, 3, 8, 6}。

  定义二叉树节点

 1 /**
 2 * 二叉树节点
 3 * @author okevin
 4 * @date 2019/5/30
 5 **/
 6 public class node<t> {
 7    /**
 8     * 左孩子
 9     */
10    private node left;
11 
12    /**
13     * 右孩子
14     */
15    private node right;
16 
17    /**
18     * 值域
19     */
20    private t data;
21 
22    public node() {
23    }
24 
25    public node(t data) {
26        this.data = data;
27    }
28 
29    //省略getter/setter方法
30 }

  解法一:递归

 1 /**
 2 * 根据前序遍历序列和中序遍历序列重建二叉树
 3 * @author okevin
 4 * @date 2019/5/30
 5 **/
 6 public class solution {
 7    public node<integer> buildbinarytree(integer[] preorder, integer[] inorder) {
 8        if (preorder.length == 0 || inorder.length == 0) {
 9            return null;
10        }
11        node<integer> root = new node<>(preorder[0]);
12        int index = search(0, inorder, root.getdata());
13        root.setleft(buildbinarytree(arrays.copyofrange(preorder, 1, index + 1), arrays.copyofrange(inorder, 0, index)));
14        root.setright(buildbinarytree(arrays.copyofrange(preorder, index + 1, preorder.length), arrays.copyofrange(inorder, index + 1, inorder.length)));
15        return root;
16    }
17 
18    /**
19     * 在中序遍历的序列中查询根节点所在的位置
20     * @param start 开始查找的下标
21     * @param inorder 中序遍历序列
22     * @param rootdata 根节点值
23     * @return 节点值在中序遍历序列中的下标位置
24     */
25    private int search(int start, integer[] inorder, integer rootdata) {
26        for (; start < inorder.length; start++) {
27            if (rootdata.equals(inorder[start])) {
28                return start;
29            }
30        }
31        return -1;
32    }
33 }

二叉树的遍历一共分为:前序遍历、中序遍历和后序遍历

前序遍历遍历顺序为:根节点->左节点->右节点

中序遍历遍历顺序为:左节点->根节点->右节点

后序遍历遍历顺序为:左节点->右节点->根节点

例如二叉树:

           1

        /     \

      2       3

     /       /   \

    4    5     6

      \        /

       7   8 

前序遍历结果为:1、2、4、7、3、5、6、8

中序遍历结果为:4、7、2、1、5、3、8、6

后序遍历结果为:7、4、2、5、8、6、3、1

此题给出前序和中序的遍历结果,要求重建二叉树。从前序遍历结果得知,第一个节点一定是根节点。从中序遍历结果可知,根节点左侧一定是其左子树右侧一定是其右子树。

那么可以得到:

第一次:

根据前序遍历结果得知,1为根节点,根据中序遍历结果得知,4、7、2为左子树,5、3、8、6为右子树。

第二次:

根据前序遍历结果得知,2为节点,根据中序遍历,4、7位节点2的左子树,节点2没有右子树。

第三次:

根据前序遍历结果得知,4为节点,根据中序遍历,7为节点4的右子树,节点4没有左子树。

以此类推,根据递归即可构建一颗二叉树。

  测试程序

 1 /**
 2 *          1
 3 *         / \
 4 *        2   3
 5 *       /   / \
 6 *      4   5   6
 7 *       \     /
 8 *        7   8
 9 * @author okevin
10 * @date 2019/5/30
11 **/
12 public class main {
13    public static void main(string[] args) {
14        integer[] preorder = new integer[]{1, 2, 4, 7, 3, 5, 6, 8};
15        integer[] inorder = new integer[]{4, 7, 2, 1, 5, 3, 8, 6};
16        solution solution = new solution();
17        node<integer> node = solution.buildbinarytree(preorder, inorder);
18    }
19 }

8.二叉树的下一个节点

题目:给定一颗二叉树和其中的一个节点,如何找出中序遍历序列的下一个节点?节点中除了两个分别指向左、右子节点的指针,还有一个指向父节点的指针。

分析:熟悉二叉树中序遍历的特点。查找节点的下一个节点,一共有两种情况:一、节点有右子树,节点的下一个节点即为右子树的最左子节点;二、节点没有右子树,此时又要分为两种情况:1、如果节点位于父节点的左节点,节点的下一个节点即为父节点;2、如果节点位于父节点的右节点,此时向上遍历,找到它是父节点的左节点。

  节点定义

 1 /**
 2 * 二叉树节点定义
 3 * @author okevin
 4 * @date 2019/6/3
 5 **/
 6 public class node<t> {
 7    /**
 8     * 值域
 9     */
10    private t data;
11 
12    /**
13     * 左节点
14     */
15    private node<t> left;
16 
17    /**
18     * 右节点
19     */
20    private node<t> right;
21 
22    /**
23     * 父节点
24     */
25    private node<t> parent;
26 
27    public node() {
28    }
29 
30    public node(t data) {
31        this.data = data;
32    }
33    //省略getter/setter方法
34 }

中序遍历情况下,查找二叉树节点的下一个节点

 1 /**
 2 * 中序遍历情况下,查找节点的下一个节点
 3 * @author okevin
 4 * @date 2019/6/3
 5 **/
 6 public class solution {
 7    public node getnextnode(node<integer> head) {
 8        if (head == null) {
 9            return null;
10        }
11        node<integer> p = head;
12        //第一种情况,节点有右子树。节点右子树的最左子节点即为节点中序遍历的下一个节点
13        if (p.getright() != null) {
14            p = p.getright();
15            while (p.getleft() != null) {
16                p = p.getleft();
17            }
18            return p;
19        }
20        //第二种情况,节点没有右子树。仍然有两种情况:一、节点位于父节点的左节点,此时父节点即为节点中序遍历的下一个节点;二、节点位于父节点的右节点,此时一直向上查找,直到是它父节点的左节点
21        while (p.getparent() != null) {
22            if (p == p.getparent().getleft()) {
23                return p.getparent();
24            }
25            p = p.getparent();
26        }
27        return null;
28    }
29 }

  测试程序 

 1 /**
 2 *          1
 3 *         / \
 4 *        2   3
 5 *       /   / \
 6 *      4   5  6
 7 *       \    /
 8 *        7  8
 9 * 中序遍历序列:4,7,2,1,5,3,8,6
10 * @author okevin
11 * @date 2019/6/3
12 **/
13 public class main {
14    public static void main(string[] args) {
15        node<integer> node1 = new node<>(1);
16        node<integer> node2 = new node<>(2);
17        node<integer> node3 = new node<>(3);
18        node<integer> node4 = new node<>(4);
19        node<integer> node5 = new node<>(5);
20        node<integer> node6 = new node<>(6);
21        node<integer> node7 = new node<>(7);
22        node<integer> node8 = new node<>(8);
23        node1.setleft(node2);
24        node1.setright(node3);
25        node2.setleft(node4);
26        node2.setparent(node1);
27        node3.setleft(node5);
28        node3.setright(node6);
29        node3.setparent(node1);
30        node4.setright(node7);
31        node4.setparent(node2);
32        node5.setparent(node3);
33        node6.setleft(node8);
34        node6.setparent(node3);
35        node7.setparent(node4);
36        node8.setparent(node6);
37        solution solution = new solution();
38        system.out.println(solution.getnextnode(node6).getdata());
39    }
40 }

9.用两个栈实现队列

题目:用两个栈实现一个队列。 

分析:栈的结构是filo(先进后出),队列的结构是fifo(先进先出)。栈s1用于存储元素,栈s2当执行删除队列尾元素时,从s1弹出数据进入s2,再弹出s2,即实现一个队列。

 1 /**
 2 * 两个栈实现一个队列
 3 * @author okevin
 4 * @date 2019/6/3
 5 **/
 6 public class myqueue<t> {
 7    private stack<t> s1 = new stack<>();
 8    private stack<t> s2 = new stack<>();
 9 
10    /**
11     * 从队尾添加元素
12     * @param t 元素
13     * @return 添加的数据
14     */
15    public t appendtail(t t) {
16        s1.push(t);
17        return t;
18    }
19 
20    /**
21     * 对队头删除元素
22     * @return 删除的元素
23     */
24    public t deletetail() {
25        if (s1.empty() && s2.empty()) {
26            return null;
27        }
28        if (s2.empty()) {
29            while (!s1.empty()) {
30                s2.push(s1.pop());
31            }
32        }
33        t t = s2.pop();
34        return t;
35    }
36 }

10.斐波那契数列

题目:求斐波那契数列的第n项。 

  解法一:递归

 1 /**
 2 * 求斐波那契数列的第n项
 3 * @author okevin
 4 * @date 2019/6/3
 5 **/
 6 public class solution1 {
 7 
 8    public integer fibonacci(integer n) {
 9        if (n.equals(0)) {
10            return 0;
11        }
12        if (n.equals(1)) {
13            return 1;
14        }
15        return fibonacci(n - 1) + fibonacci(n - 2);
16    }
17 }

优点:简单易懂

缺点:如果递归调用太深,容易导致栈溢出。并且节点有重复计算,导致效率不高。

  解法二:循环

 1 /**
 2 * 求斐波那契数列的第n项
 3 * @author okevin
 4 * @date 2019/6/3
 5 **/
 6 public class solution2 {
 7 
 8    public integer fibonacci(integer n) {
 9        if (n.equals(0)) {
10            return 0;
11        }
12        if (n.equals(1)) {
13            return 1;
14        }
15        integer first = 0;
16        integer second = 1;
17        integer result = first + second;
18        for (int i = 2; i <= n; i++) {
19            result = first + second;
20            first = second;
21            second = result;
22        }
23        return result;
24    }
25 }

通过循环计算斐波那契数列能避免重复计算,且不存在调用栈过深的问题。

11. 旋转数组的最小数字

题目:把一个数组最开始的若干个元素搬到数组的末尾,我们称之为数组的旋转。输入一个递增的数组的一个旋转,输出旋转数组的最小元素。例如,数组{3,4,5,1,2}为{1,2,3,4,5}的一个旋转,该数组的最小值为1。

*题中本意是希望能找到数组中的最小数字,直接暴力解法遍历即可。

 引子:通过“二分查找”算法查找有序数组中的数字。

  二分查找有序数组是否存在数字

 1 /**
 2 * 二分查找有序数组中的数字
 3 * @author okevin
 4 * @date 2019/6/3
 5 **/
 6 public class binarysearch {
 7 
 8    public boolean find(integer[] array, integer target) {
 9        integer start = 0;
10        integer end = array.length - 1;
11        return partition(array, start, end, target);
12    }
13 
14    private boolean partition(integer[] array, integer start, integer end, integer target) {
15        if (target < array[start] || target > array[end] || start > end) {
16            return false;
17        }
18 
19        int middle = (end + start) / 2;
20 
21        if (target > array[middle]) {
22            return partition(array, middle + 1, end, target);
23        } else if (target < array[middle]) {
24            return partition(array, start, middle - 1, target);
25        } else {
26            return true;
27        }
28    }
29 }

利用二分法思想查找旋转数组中的最小数字,注意当出现原始数组为:{0,1,1,1,1}时,{1,1,1,0,1}和{1,0,1,1,1}均是旋转数组,这两种情况left=middle=right都是1,不能区别,此时只能按照顺序查找的方式。

 1 /**
 2 * 找到旋转数组中的最小值
 3 * @author okevin
 4 * @date 2019/6/3
 5 **/
 6 public class solution {
 7 
 8    public integer find(integer[] array) {
 9        if (array.length == 0) {
10            return -1;
11        }
12        int left = 0;
13        int right = array.length - 1;
14        int middle = 0;
15        while (array[left] >= array[right]) {
16            if (right - left == 1) {
17                middle = right;
18                break;
19            }
20            middle = (left + right) / 2;
21            if (array[left].equals(array[right]) && array[left].equals(array[middle])) {
22                return min(array, left, right);
23            }
24            if (array[middle] >= array[left]) {
25                left = middle;
26            } else {
27                right = middle;
28            }
29        }
30        return array[middle];
31    }
32 
33    /**
34     * 当出现原始数组为:{0,1,1,1,1}时,{1,1,1,0,1}和{1,0,1,1,1}均是旋转数组,这两种情况left=middle=right都是1,不能区别
35     * @param array 数组
36     * @param left 起始
37     * @param right 结束
38     * @return
39     */
40    private integer min(integer[] array, int left, int right) {
41        int min = array[left];
42        for (int i = left + 1; i < right; i++) {
43            if (array[i] < min) {
44                min = array[i];
45            }
46        }
47        return min;
48    }
49 }

本文例子完整源码地址:https://github.com/yu-linfeng/blogrepositories/tree/master/repositories/sword

《【好书推荐】《剑指offer》之软技能》

《【好书推荐】《剑指offer》之硬技能(编程题1~6)》

持续更新,敬请关注公众号:coderbuff,回复关键字“sword”获取相关电子书。

 

 

这是一个能给程序员加buff的公众号 (coderbuff)

【好书推荐】《剑指Offer》之硬技能(编程题7~11)