Oj 题目

本文章是收录有问题的Oj题目，

这里有问题是指做过了但是第二次做依然没有思路的题目

List

给定⼀个链表，判断链表中是否有环

使用快慢指针，一个速度为 2 另一个速度为 1，只要判断它们两是否相遇即可判断是否有环

问题：速度为什么一个是 2，一个是 1 ？一个是 3，一个是 4 行不行？

原因：它们之间的差为 1，只要满足这个条件，就一定可以追上，如果相差不是 1，就可能会跳过甚至永远不会相遇

public boolean chkPalindrome(ListNode A) {
    if (A == null || A.next == null) {
        return true;
    }
    // 1. 先获取中间节点
    ListNode slow = A, fast = A;
    while(fast != null && fast.next != null) {
        slow = slow.next;
        fast = fast.next.next;
    }

    // 2. 调转方向
    ListNode prev = slow, cur = slow.next, next = cur.next;
    slow.next = null; // 制空，最后才不会成环
    while(cur != null) {
        cur.next = prev;
        prev = cur;
        cur = next;
        if (next != null) {
            next = next.next;
        }
    }
    // 3. 判断
    ListNode lastTmp = prev, headTmp = A;
    while (lastTmp != null) { // lastTmp 不能用 headTmp 代替
        if (headTmp.val != lastTmp.val) {
            return false;
        }
        headTmp = headTmp.next;
        lastTmp = lastTmp.next;
    }
    // 如果不执行 slow.next = null; 那么就需要在循环内部进行判断了
    return true;
}

Tree

⼆叉树的构建及遍历

使用递归的思路经行创建，通过外部 index 下标来获取字符

递归终止条件： index 获取到的字符是 # 递归过程： index 获取到的字符不是 #，创建根节点 root ，然后再通过 createTree 这个方法递归， 分别创建左子树与右子树，最后返回 root

就以 abc##de#g##f### 为例， a 就是根节点，左节点就是 bc##de#g##f##，右节点是 #

左节点的根节点是 b，它的左节点是 c## 它的右节点是 de#g##f##。以此类推……

// 只提供核心的创建代码
static int index = 0; // 之后每次执行这个代码的时候，index 都要置为 0
public static TreeNode createTree(String str) {
    // 获取到对应的字符，并且下标加 1
    char ch = str.charAt(index++);
    // 如果为 # 那么就表示为空，返回空指针
    if (ch == '#') {
        return null;
    }
    // 不为空，创建根节点 root
    TreeNode root = new TreeNode(ch);
    // 利用递归思想，创建左子树与右子树
    root.left = createTree(str);
    root.right = createTree(str);

    // 返回 root
    return root;
}

二叉树的最近公共祖先

方法1：

1. 获取到对应的节点到根节点的链表
2. 然后通过寻找链表公共节点来获取到最近公共祖先（速度太慢了，于是看看视频是怎么写的）

public TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) {
    LinkedList<TreeNode> pList = getList(root, p);
    LinkedList<TreeNode> qList = getList(root, q);

    // 此时就可以转化为获取两个链表的公共节点
    if (pList == null || qList == null) {
        return null;
    }
    TreeNode tmp, ret = null;
    while(!pList.isEmpty() && !qList.isEmpty()) {
        if ((tmp = pList.removeLast()) == qList.removeLast()) {
            ret = tmp;
        }
    }
    
    return ret;
}

private LinkedList<TreeNode> getList(TreeNode root, TreeNode val) {
    // 不考虑 val = null 的情况
    if (root == null) {
        return null;
    }

    if (root == val) {
        // 找到目标节点
        LinkedList<TreeNode> ret = new LinkedList<>();
        ret.add(root);
        return ret;
    }

    // root != val
    // 看看左边是否找到，如果不为 null 那么就说明找到了，添加当前根节点后即可放回
    LinkedList<TreeNode> leftList = getList(root.left, val);
    if (leftList != null) {
        leftList.add(root);
        return leftList;
    }

    // 同理
    LinkedList<TreeNode> rightList = getList(root.right, val);
    if (rightList != null) {
        rightList.add(root);
        return rightList;
    }

    // 没找到
    return null;
}

方法2：

1. p/q 是公共祖先
   1. root == q || root == p 那么就返回 root
   2. 不满足上诉条件时候，通过递归来获取
2. p/q 在 root 两边
   1. 通过递归在左右两边同时找到相关的节点，直接返回 root
   2. 找不到直接递归即可

public TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) {
    if (root == null) {
        return null;
    }

    if (root == p || root == q) {
        // 这一步不仅仅可以找到公共祖先，而且可以用来判断是否找到 p/q
        return root;
    }

    TreeNode leftNode = lowestCommonAncestor(root.left, p, q);
    TreeNode rightNode = lowestCommonAncestor(root.right, p, q);

    if (leftNode != null && rightNode != null) {
        // 在两边找到
        return root;
    }
    if (leftNode != null) {
        // 只在左边找到
        return leftNode;
    }
    if (rightNode != null) {
        // 只在右边找到
        return rightNode;
    }
    // 找不到
    return null;
}

二叉树的前序遍历（非递归）

递归的方法很简单，这里就不说明了，这里主要说明的通过迭代的方法

迭代方法本质是把递归中系统自动开栈变成手动入栈的过程

把递归变成迭代需要明白 3 个要素

问题	答案
什么时候入栈？	等效于递归中进入方法的时候
为什么要入栈，入栈的目的主要是什么？	为了可以恢复现场，记录下此时的状态，类似递归中的“归”的过程中，依然可以获取到当时的上下文
入栈怎么入？	递归是顺序来，而入栈的时候由于栈的性质，是需要反过来。比如前序遍历中，递归是先左再右，而迭代中入栈是先右再左

public List<Integer> preorderTraversal(TreeNode root) {
    List<Integer> list = new LinkedList<>();
    if (root == null) {
        return list;
    }
    // 先添加 root
    Stack<TreeNode> stack = new Stack<>();
    stack.push(root);
    
    TreeNode cur = null;
    // 使用迭代方法
    while(!stack.isEmpty()) {
        cur = stack.pop();
        list.add(cur.val); // cur 一定不为 null 
        // 必须先右再左，因为栈是先进后出的，
        if (cur.right != null) {
            stack.push(cur.right);
        }
        if (cur.left != null) {
            stack.push(cur.left);
        }
    }
    return list;
}

二叉树的中序遍历（非递归）

递归的方法很简单，这里就不说明了，这里主要说明的通过迭代的方法

1. 用 cur 来表示当前的节点
2. cur 不为空，那么一直添加左子树，然后 cur = cur.left，将 cur 指向左子树
3. cur 为空，说明左子树已经遍历完，就可以遍历右子树了，此时可以弹出根节点，并添加再 list 中，执行 cur = cur.right，把 cur 指向右子树
4. 上诉为一次循环（遍历左子树），只需要再外层添加判断 stack 是否为空即可

public List<Integer> inorderTraversal(TreeNode root) {
    List<Integer> list = new LinkedList<>();
    if (root == null) {
        return list;
    }
    Stack<TreeNode> stack = new Stack<>();
    
    TreeNode cur = root;
    // 使用迭代方法
    while(cur != null || !stack.isEmpty()) {
        while(cur != null) {
            stack.push(cur);
            cur = cur.left;
        }

        // 此时左树已经走完了
        TreeNode pop = stack.pop();
        list.add(pop.val);
        cur = pop.right;
    }

    return list;
}

二叉树的后序遍历（非递归）

大体的思路与 二叉树的中序遍历 一样，只是在左子树遍历完后处理的方式有所不同

1. 是执行 stack.peek() 而不是 stack.pop()，因为不确定有没有遍历到右子树
2. 如果右子树为空 或者 右子树已经遍历过，那么就直接 pop() 弹出，打印根节点，然后记录打印的节点
3. 如果右子树不为空并且没有遍历过，那么将 cur 指向右子树，然后重新遍历

public List<Integer> postorderTraversal(TreeNode root) {
    List<Integer> list = new LinkedList<>();
    if (root == null) {
        return list;
    }
    Stack<TreeNode> stack = new Stack<>();
    
    TreeNode cur = root, prev = null;
    while(cur != null || !stack.isEmpty()) {
        while(cur != null) {
            stack.push(cur);
            cur = cur.left;
        }

        // 此时左树已经走完了, 需要走右树了
        TreeNode peek = stack.peek();
        if (peek.right == null || peek.right == prev) {
            // 没有右子树或者右子树已经打印过了，直接添加到 list 内
            stack.pop();
            list.add(peek.val);
            // 标记一下“打印过”的节点
            prev = peek;
        } else {
            // 有右子树，cur = peek.right 后重复循环
            cur = peek.right;
        }
    }

    return list;
}

Set 与 Map

随机链表的复制

通过 Map 这个数据结构来解决

1. 遍历原数据，构建 Map， Map 的 key 是旧节点下标， val 是新节点下标
2. 此时 map.get(node) 可以获取到旧节点对应新节点的下标， 那么就可以通过 map.get(cur.next) 与 map.get(cur.random) 获取到对应新节点的 next 与 random
3. 最后返回新节点的头节点即可

输入数据：

步骤： 0 / 0

当前动作：等待输入...

public Node copyRandomList(Node head) {
    // 遍历
    Node cur = head;
    Map<Node, Node> map = new HashMap<>();
    while(cur != null) {
        map.put(cur, new Node(cur.val));
        cur = cur.next;
    }

    // 此时已经构建 旧-新 节点的映射表
    cur = head;
    while(cur != null) {
        Node newNode = map.get(cur);
        newNode.next = map.get(cur.next); // 通过 cur.next 获取到旧的节点的 next，然后通过 map 映射关系，获取到对应的新节点的下标
        newNode.random = map.get(cur.random); // 同理
        cur = cur.next;
    }

    return map.get(head);
}