剑指offer java版（二）

蜻蜓队长

发布于 2019-04-09 11:48:55

5620

发布于 2019-04-09 11:48:55

文章被收录于专栏：Android机动车

链表中倒数第k个结点

问题描述

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

解题思路

经典的双指针法。定义两个指针，第一个指针从链表的头指针开始遍历向前走k-1步，第二个指针保持不动，从第k步开始，第二个指针也开始从链表的头指针开始遍历，由于两个指针的距离保持在k-1，当第一个指针到达链表的尾节点时，第二个指针刚好指向倒数第k个节点。

    public void findK(LinkNode node, int k) {
        if (node == null || node.next == null) return;
        // 判断链表长度是否超过k
        int num = 1;
        while (node.next != null) {
            num++;
            if (num == k) break;
        }
        if (num < k) return;

        LinkNode node1 = node;
        LinkNode node2 = node;
        for (int i = 0; i < k - 1; i++) {
            node1 = node1.next;
        }
        while (node1.next != null) {
            node1 = node1.next;
            node2 = node2.next;
        }

        System.out.println("倒数第k个元素值" + node2.value);
    }

反转单链表

问题描述

反转单链表。

解题思路

两个思路：循环和递归

循环

    public void method1(LinkNode head) {
        if (head == null || head.next == null) return;

        LinkNode pre = null;
        LinkNode next = null;

        while (head != null) {
            next = head.next;
            head.next = pre;
            pre = head;
            head = next;
        }

        System.out.println(pre.value);
        while (pre.next != null) {
            System.out.println(pre.next.value);
            pre = pre.next;
        }
    }

递归

    public LinkNode method2(LinkNode head) {
        if (head == null || head.next==null) return head;

        LinkNode pre = method2(head.next);
        head.next.next = head;
        head.next = null;

        return pre;

    }

合并两个有序链表

问题描述

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

解题思路

    public LinkNode merge(LinkNode node1, LinkNode node2) {
        // 如果其中一个为空，就返回另一个链表
        if (node1 == null) {
            return node2;
        }
        if (node2 == null) {
            return node1;
        }

        // 先确定头结点
        LinkNode head = null;
        if (node1.value <= node2.value) {
            head = node1;
            node1 = node1.next;// 后移
        } else {
            head = node2;
            node2 = node2.next;// 后移
        }

        // 将头结点赋给另一个变量，头结点不能直接参与循环，否则会改变头结点值
        LinkNode cur = head;
        // 两个链表都不为空时
        while (node1 != null && node2 != null) {
            if (node1.value <= node2.value) {
                cur.next = node1;
                node1 = node1.next;
            } else {
                cur.next = node2;
                node2 = node2.next;
            }
            cur = cur.next;
        }

        // 一方已遍历完成后
        if (node1 == null) {
            cur.next = node2;
        } else if(node2 == null){
            cur.next = node1;
        }

        return head;
    }

树的子结构

问题描述

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

解题思路

递归思想，如果根节点相同则递归调用IsSubtree()，如果根节点不相同，则判断root1的左子树和roo2是否相同，再判断右子树和root2是否相同;注意节点为空的条件，hasChild，只要有树为空就返回false;

isSub，要先判断root2，如果root2为空，则说明第二棵树遍历完了，即匹配成功。

    public boolean hasChild(TreeNode nodeA, TreeNode nodeB) {
        if (nodeA == null || nodeB == null) return false;

        boolean result;
        result = isSub(nodeA, nodeB);
        if (!result) {
            result = hasChild(nodeA.left, nodeB);
        }
        if (!result) {
            result = hasChild(nodeA.right, nodeB);
        }
        return result;
    }

    public boolean isSub(TreeNode nodeA, TreeNode nodeB) {
        if (nodeB == null) return true;
        if (nodeA == null) return false;
        if (nodeA.value == nodeB.value) {
            return isSub(nodeA.left, nodeB.left) && isSub(nodeA.right, nodeB.right);
        } else {
            return false;
        }
    }

二叉树镜像

问题描述

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

解题思路

通过对以上两棵树的观察，我们可以总结出这两棵树的根节点相同，但它们的左、右两个子节点交换了位置。所以我们可以得出求一棵树的镜像的过程：先前序遍历这棵树的每个节点，如果遍历到的节点有子节点，就交换它的两个子节点。当交换完所有非叶节点的左、右子节点之后，就得到了树的镜像。

    public void image(TreeNode root) {
        //当前节点为空，直接返回
        if (root == null) return;
        //当前节点没有叶子节点，直接返回
        if (root.left == null && root.right == null) return;
        // 交换
        TreeNode temp = root.left;
        root.left = root.right;
        root.right = temp;
        // 递归
        if (root.left != null) {
            image(root.left);
        }
        if (root.right != null) {
            image(root.right);
        }
    }

顺时针打印矩阵

问题描述

顺时针打印矩阵（二维数组）

解题思路

顺时针打印,核心在于控制上下左右四个坐标，循环条件是left和right相撞并且top和bottom相撞

    public void print(int[][] matrix) {
        if (matrix == null) return;

        int col = matrix[0].length;
        int row = matrix.length;

        if (row == 0 || col == 0) return;

        List<Integer> list = new ArrayList<>();

        int left = 0;
        int top = 0;
        int right = col - 1;
        int bottom = row - 1;
        while (left <= right && top <= bottom) {
            for (int i = left; i <= right; i++) {
                list.add(matrix[top][i]);
            }
            top++;

            for (int i = top; i <= bottom; i++) {
                list.add(matrix[i][right]);
            }
            right--;

            for (int i = right; i >= left; i--) {
                list.add(matrix[bottom][i]);
            }
            bottom--;

            for (int i = bottom; i >= top; i--) {
                list.add(matrix[i][left]);
            }
            left++;
        }


        for (Integer i : list) {
            System.out.println(" " + i);
        }
    }

包含min函数的栈

问题描述

设计一个数据结构实现栈的基本功能，和获取最小值的函数。

解题思路

用一个栈stack保存数据，用另外一个栈temp保存依次入栈最小的数比如，stack中依次入栈 5, 3, 4, 10, 2, 12, 1, 8 则temp依次入栈 5, 3, 3，3, 2, 2, 1, 1

每次入栈的时候，如果入栈的元素比min中的栈顶元素小或等于则入栈，否则用最小元素入栈。

    public class MyStack {
        Stack<Integer> stack1 = new Stack<>();// 存放数据
        Stack<Integer> stack2 = new Stack<>();// 存放对应size最小值
        int min = Integer.MAX_VALUE;

        public void push(Integer i) {
            stack1.push(i);
            if (i < min) {
                min = i;
            }
            stack2.push(min);
        }

        public Integer pop() {
            if (!stack1.isEmpty()) {
                int i = stack1.pop();
                stack2.pop();
                return i;
            } else {
                throw new RuntimeException("Stack is Empty");
            }
        }

        public Integer min() {
            if (!stack2.isEmpty()) {
                int i = stack1.pop();
                stack2.push(i);
                return i;
            } else {
                throw new RuntimeException("Stack is Empty");
            }
        }
    }

栈的压入、弹出序列

问题描述

输入两个整数序列，第一个序列表示栈的压入顺序，请判断第二个序列是否为该栈的弹出顺序。假设压入栈的所有数字均不相等。例如序列1,2,3,4,5是某栈的压入顺序，序列4,5,3,2,1是该压栈序列对应的一个弹出序列，但4,3,5,1,2就不可能是该压栈序列的弹出序列。（注意：这两个序列的长度是相等的）

解题思路

模拟堆栈操作的过程，将原数列依次压栈，把栈顶元素与所给出栈队列相比，如果相同则出栈，如果不同则继续压栈，直到原数列中所有数字压栈完毕。最后，检测栈中是否为空，若空，说明出栈队列可由原数列进行栈操作得到。否则，说明出栈队列不能由原数列进行栈操作得到。

    public boolean isPopOrder(int[] push, int[] pop) {
        if (push.length != pop.length || push.length == 0 || pop.length == 0)
            return false;

        Stack<Integer> stack = new Stack<>();
        int index = 0;
        for (int i = 0; i < push.length; i++) {
            stack.push(push[i]);
            while (!stack.isEmpty() && stack.peek() == pop[index]) {
                stack.pop();
                index++;
            }
        }

        return stack.isEmpty();
    }

广度优先遍历二叉树

问题描述

广度优先遍历二叉树

解题思路

借助集合逐层遍历

    public void print(TreeNode node) {
        if (node == null) return;
        List<TreeNode> list = new ArrayList<>();
        list.add(node);
        for (int i = 0; i < list.size(); i++) {
            System.out.println(" " + list.get(i).value);
            if (list.get(i).left != null) {
                list.add(list.get(i).left);
            }
            if (list.get(i).right != null) {
                list.add(list.get(i).right);
            }
        }
    }

本文参与腾讯云自媒体同步曝光计划，分享自微信公众号。

原始发表：2019-03-20，如有侵权请联系 cloudcommunity@tencent.com 删除

编程算法

二叉树

本文分享自 Android机动车微信公众号，前往查看

如有侵权，请联系 cloudcommunity@tencent.com 删除。

本文参与腾讯云自媒体同步曝光计划，欢迎热爱写作的你一起参与！

编程算法

二叉树

登录后参与评论

0 条评论

热度