前往小程序,Get更优阅读体验!
立即前往
首页
学习
活动
专区
工具
TVP
发布
社区首页 >专栏 >剑指offer java版(二)

剑指offer java版(二)

作者头像
蜻蜓队长
发布2019-04-09 11:48:55
5620
发布2019-04-09 11:48:55
举报
文章被收录于专栏:Android机动车

链表中倒数第k个结点

问题描述

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

解题思路

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

代码语言:javascript
复制
    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);
    }

反转单链表

问题描述

反转单链表。

解题思路

两个思路:循环和递归

  • 循环
代码语言:javascript
复制
    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;
        }
    }
  • 递归
代码语言:javascript
复制
    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;

    }

合并两个有序链表

问题描述

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

解题思路
代码语言:javascript
复制
    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为空,则说明第二棵树遍历完了,即匹配成功。

代码语言:javascript
复制
    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;
        }
    }

二叉树镜像

问题描述

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

解题思路

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

代码语言:javascript
复制
    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相撞

代码语言:javascript
复制
    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中的栈顶元素小或等于则入栈,否则用最小元素入栈。

代码语言:javascript
复制
    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就不可能是该压栈序列的弹出序列。(注意:这两个序列的长度是相等的)

解题思路

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

代码语言:javascript
复制
    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();
    }

广度优先遍历二叉树

问题描述

广度优先遍历二叉树

解题思路

借助集合逐层遍历

代码语言:javascript
复制
    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 条评论
热度
最新
推荐阅读
目录
  • 链表中倒数第k个结点
    • 问题描述
      • 解题思路
      • 反转单链表
        • 问题描述
          • 解题思路
          • 合并两个有序链表
            • 问题描述
              • 解题思路
                • 树的子结构
                  • 问题描述
                    • 解题思路
                    • 二叉树镜像
                      • 问题描述
                        • 解题思路
                        • 顺时针打印矩阵
                          • 问题描述
                            • 解题思路
                            • 包含min函数的栈
                              • 问题描述
                                • 解题思路
                                • 栈的压入、弹出序列
                                  • 问题描述
                                    • 解题思路
                                    • 广度优先遍历二叉树
                                      • 问题描述
                                        • 解题思路
                                        领券
                                        问题归档专栏文章快讯文章归档关键词归档开发者手册归档开发者手册 Section 归档