剑指offer java版(二)

链表中倒数第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);
            }
        }
    }

原文发布于微信公众号 - Android机动车(JsAndroidClub)

原文发表时间:2019-03-20

本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。

发表于

我来说两句

0 条评论
登录 后参与评论

扫码关注云+社区

领取腾讯云代金券