算法系列：历史算法汇总

/**
 * 题目: 连续子数组，和为固定值 key，求连续子数组的最大长度
 *
 * TODO: 整理独立的博文
 *
 * 备注:
 * 下述代码, 「Map中」只保留了「第一次出现取值的 prefixSum」, 这并不会影响最终的 maxLen,
 * 因为 maxLen 计算过程中, 利用了「后续出现取值的 prefixSum」。
 */
public class SubArraySumKey {
​
    public static int subArraySumKeyMaxLen(int[] array, int destKey) {
        // 1. 边界判断
        if (null == array) {
            return -1;
        }
​
        // 2. 求数组的「前缀和」,并保存到 Map 中, 同时, 统计最大的 Len
        HashMap<Integer, Integer> prefixSumArray = new HashMap<>();
        int prefixSum = 0;
        // a. 设置基准点
        prefixSumArray.put(0, -1);
​
        int maxLen = 0;
​
        for (int index = 0; index < array.length; index++) {
            prefixSum += array[index];
            // b. 判断目标取值是否存在, 若存在, 则,更新 maxLen
            int delta = prefixSum - destKey;
            if (prefixSumArray.containsKey(delta)) {
                int deltaIndex = prefixSumArray.get(delta);
                maxLen = Math.max(index - deltaIndex, maxLen);
            }
​
            // c. 判断当前「前缀和」, 是否存在, 若不存在, 则, 添加到 HashMap 中
            if (!prefixSumArray.containsKey(prefixSum)) {
                prefixSumArray.put(prefixSum, index);
            }
        }
​
        return maxLen;
    }
​
    public static void main(String[] args) {
        int[] inputArray = {1, 3, 4, 5, 8, 5};
        int destValue = 13;
​
        int result = subArraySumKeyMaxLen(inputArray, destValue);
        System.out.println(result);
    }
}

   /**
     * 自顶向下，迭代计算。
     *
     * @param coins 不同面额的数组
     * @param amount 兑换金额
     * @return 所需硬币的最少数量
     */
    public static int coinChangeLoop(int[] coins, int amount) {
        // 边界判断
        if (null == coins || amount <= 0) {
            return -1;
        }
​
        // 终止条件
        int len = coins.length;
        for (int coin : coins) {
            if (coin == amount) {
                return 1;
            }
        }
​
        // 迭代
        int[] deltaAmounts = new int[len];
        for (int i = 0; i < len; i++) {
            deltaAmounts[i] = coinChangeLoop(coins, amount - coins[i]);
        }
​
        // 返回结果
        int min = Integer.MAX_VALUE;
        for (int i = 0; i < len; i++) {
            int currValue = deltaAmounts[i];
            // 此处有：合规匹配
            if (currValue > 0) {
                if (currValue < min) {
                    min = currValue;
                }
            }
        }
​
        return (min == Integer.MAX_VALUE) ? -1 : (min + 1);
    }

/**
     * 自底向上，逐个计算潜在金额，并匹配目标金额.
     *
     * 实现：使用「外部存储」，下标表示目标金额，存储值表示最少硬币数量.
     *
     * @param coins 不同面额的数组
     * @param amount 兑换金额
     * @return 所需硬币的最少数量
     */
    public static int coinChange(int[] coins, int amount) {
        // 边界判断
        if (null == coins || amount <= 0) {
            return -1;
        }
​
        // 借助外部存储: 存储金额对应的硬币数量
        int max = amount + 1;
        int[] dps = new int[amount + 1];
        Arrays.fill(dps, max);
        // 设置起始条件
        dps[0] = 0;
​
        // 从前向后，逐步更新
        for (int i = 1; i <= amount; i++) {
            for (int coin : coins) {
                int delta = i - coin;
                if (delta < 0) {
                    continue;
                }
                dps[i] = Math.min(dps[i], dps[delta] + 1);
            }
        }
​
        return (dps[amount] > amount) ? -1 : dps[amount];
    }

    public static int subArrayDescMaxLen(int[] array) {
        // 边界判断
        if (null == array) {
            return 0;
        }
​
        // 定义：max[i]
        int len = array.length;
        int[] max = new int[len];
        Arrays.fill(max, 1);
​
        for (int i = 0; i < len; i++) {
            // 状态转移函数：回溯
            for (int j = 0; j < i; j++) {
                if (array[i] <= array[j]) {
                    max[i] = Math.max(max[i], max[j] + 1);
                }
            }
        }
​
        return max[len - 1];
    }

/**
 * 题目：翻转链表的指定区间。
 */
public class ReverseSegmentList {
​
​
    /**
     * 根据给定的位置，进行链表的局部翻转
     *
     * @param head 链表头
     * @param m 第 m 个节点
     * @param n 第 n 个节点
     * @return 翻转之后的节点
     */
    public static Node reverseList(Node head, int m, int n) {
        // 边界判断
        if (null == head) {
            return null;
        }
        if (m >= n) {
            return head;
        }
​
        // a. 获取 pre 节点
        Node bufNode = new Node(0);
        bufNode.next = head;
​
        Node pre = bufNode;
        // 特别说明：pre 停留在 m 编号之前
        for (int index = 1; index < m; index++) {
            pre = pre.next;
        }
​
        // b. 插入法，逐次遍历节点，并插入
        Node start = pre.next;
        Node curr = start.next;
        // 特别说明：插入 n-m 次
        for (int index = m; index < n; index++) {
            start.next = curr.next;
            curr.next = pre.next;
            pre.next = curr;
​
            curr = start.next;
        }
​
        return bufNode.next;
    }
​
    public static void main(String[] args) {
        Node oriList = ListUtils.constructNodeList(8);
        ListUtils.printList(oriList);
​
        int m = 2;
        int n = 5;
​
        Node result = reverseList(oriList, m, n);
        ListUtils.printList(result);
    }
​
}

/**
 * 题目：单链表，排序(升序)
 *
 */
	// 已经提供下面数据结构，表示单个链表节点
	class Node {
        public int value;
        public Node next;

        public Node(int value) {
            this.value = value;
            this.next = null;
        }
    }
 
	// 实现下面方法，对单链表，进行升序排列
	Node sortList(Node head);

/**
 * 题目：单链表，排序(升序)
 *
 * 分析：
 * 1. 方案A：选择排序，时间复杂度 O(n^2)
 * 2. 方案B：归并排序，时间复杂度 O(nlg(n))
 *
 * Created by guoning on 17/8/23.
 */
public class SortList {

    public static void main(String[] args) {
        // 1. 构造列表
        Node node = constructNodeList(4);
        // 2. 排序
        Node result = sortList(node);
        // 3. 输出
        for (Node currNode = result; currNode != null; currNode = currNode.next) {
            System.out.println(currNode.value);
        }
    }

    private static Node constructNodeList(int num) {
        Node node = null;
        Node currNode = null;
        Random random = new Random();
        for (int index = 0; index < num; index++) {
            int value = random.nextInt(100);
            Node newNode = new Node(value);
            if (node == null) {
                node = newNode;
                currNode = node;
            } else {
                currNode.next = newNode;
                currNode = currNode.next;
            }
        }
        return node;
    }

    static class Node {
        public int value;
        public Node next;

        public Node(int value) {
            this.value = value;
            this.next = null;
        }
    }

    // 归并排序
    // 1. 中间节点：找到中间节点，将链表拆为 2 部分
    // 2. 递归：对 2 部分分别进行排序
    // 3. 合并：合并 2 部分有序链表
    private static Node sortList(Node head) {
        // 边界判断
        if (null == head || null == head.next) {
            return head;
        }

        // 1. 中间节点
        Node mid = getMiddleNode(head);

        // 破坏链表结构
        Node second = null;
        if (mid == null) {
            second = null;
        } else {
            second = mid.next;
            mid.next = null;
        }

        // 2. 递归：分别对 2 个链表排序
        Node firstHead = sortList(head);
        Node secondHead = sortList(second);

        // 3. 合并：2 个有序列表，合并
        return mergeSortedList(firstHead, secondHead);
    }

    // 获取中间节点
    private static Node getMiddleNode(Node head) {
        // 边界判断
        if (null == head || null == head.next) {
            return head;
        }
        // 2 只有 2 个节点
        if (head.next.next == null){
            return head;
        }
        // 2 个指针：一个每次 2 步，一个每次 1 步
        Node first = head;
        Node second = head;
        while (second != null && second.next != null) {
            first = first.next;
            second = second.next.next;
        }
        return first;
    }

    // 合并 2 个有序列表
    private static Node mergeSortedList(Node firstHead, Node secondHead) {
        // 边界条件
        if (null == firstHead) {
            return secondHead;
        }
        if (null == secondHead) {
            return firstHead;
        }

        // 2 个指针：遍历 2 个链表，调整链表指向关系
        if (firstHead.value < secondHead.value) {
            firstHead.next = mergeSortedList(firstHead.next, secondHead);
            return firstHead;
        } else {
            secondHead.next = mergeSortedList(firstHead, secondHead.next);
            return secondHead;
        }
    }
}

/**
 * 题目：重构二叉查找树，找出被交换的 2 个节点
 */
public class RecoverTree {
​
    private static TreeNode firstNode = null;
    private static TreeNode secondNode = null;
​
    private static TreeNode preNode = null;
​
    /**
     * 修复二叉查找树。
     *
     * @param root 二叉查找树的根节点。
     */
    public static void recoverTree(TreeNode root) {
        if (null == root) {
            return;
        }
​
        // 中序遍历：找出 2 个逆序的节点
        inOrderTraverse(root);
​
        int tmp = firstNode.value;
        firstNode.value = secondNode.value;
        secondNode.value = tmp;
    }
​
    /**
     * 中序遍历二叉查找树，同时，判断逆序节点
     *
     * @param root 二叉查找树的根节点
     */
    public static void inOrderTraverse(TreeNode root) {
        if (null == root) {
            return;
        }
​
        inOrderTraverse(root.left);
​
        if (preNode != null) {
            if (preNode.value > root.value) {
                if (firstNode == null) {
                    firstNode = preNode;
                    secondNode = root;
                } else {
                    secondNode = root;
                }
            }
        }
​
        preNode = root;
​
        inOrderTraverse(root.right);
    }
​
}

/**
 * 题目：二叉树，路径和为固定值
 *
 * 1. 判断：是否存在路径
 * 2. 输出满足条件的路径
 */
public class PathSum {
​
    /**
     * 判断：是否存在路径，路径和为指定值.
     */
    public static boolean hasPathSatisfySum(TreeNode root, int sum) {
        if (null == root) {
            return false;
        }
​
        // 终止条件：叶子节点
        if (root.left == null && root.right == null) {
            if (sum == root.value) {
                return true;
            }
        }
​
        // 迭代判断
        int delta = sum - root.value;
        boolean leftResult = hasPathSatisfySum(root.left, delta);
        boolean rightResult = hasPathSatisfySum(root.right, delta);
​
        return leftResult || rightResult;
    }
​
    private ArrayList<ArrayList<Integer>> listAll = new ArrayList<ArrayList<Integer>>();
    private ArrayList<Integer> list = new ArrayList<Integer>();
​
    /**
     * 输出满足条件的路径
     * @param root
     * @param target
     * @return
     */
    public ArrayList<ArrayList<Integer>> FindPath(TreeNode root,int target) {
        if(root == null){
            return listAll;
        }
​
        list.add(root.value);
​
        // 终止条件
        int delta = target -  root.value;
        if(target == 0 && root.left == null && root.right == null){
            listAll.add(new ArrayList<Integer>(list));
        }
​
        // 迭代
        FindPath(root.left, delta);
        FindPath(root.right, delta);
​
        // 移除当前节点
        list.remove(list.size()-1);
        return listAll;
    }
​
}

    /**
     * 遍历：前序（非递归，循环方式）
     *
     * Note：有独立的示意图
     *
     * @param root 二叉树根节点
     * @param result 中序遍历的结果
     */
    public static void preOrderTraverseLoop(TreeNode root, List<TreeNode> result) {
        Stack<TreeNode> stack = new Stack<>();
​
        // 基本逻辑：
        // 1. 初始化：root 入栈
        // 2. 循环逻辑：弹出一个节点，并将右、左子节点入栈
        // 3. 终止条件：节点为 null，不再入栈，stack 为空，终止处理
​
        if (null == root) {
            return;
        }
​
        stack.push(root);
        while (!stack.isEmpty()) {
            // a. 弹出元素
            TreeNode currNode = stack.pop();
​
            // b. 子节点入栈：右、左节点，入栈
            if (null != currNode.right) {
                stack.push(currNode.right);
            }
            if (null != currNode.left) {
                stack.push(currNode.left);
            }
​
            // c. 节点增加到返回队列
            result.add(currNode);
        }
​
    }

    /**
     * 遍历：中序（非递归，循环方式）
     *
     * @param root 二叉树根节点
     * @param result 中序遍历的结果
     */
    public static void inOrderTraverseLoop(TreeNode root, List<TreeNode> result) {
        Stack<TreeNode> stack = new Stack<>();
​
        // 基本逻辑：
        // 1. 初始化：记录当前节点，为 root 节点
        // 2. 循环逻辑：
        // a. 「当前节点」非 null，则入栈，并，将「左子节点」设置为「当前节点」
        // b. 如果「当前节点」为 null，则，弹出一个节点，记录到结果中
        // c. 以「弹出的节点」的「右子节点」为基准，设置为「当前节点」
        // 3. 终止条件：「栈」为空，且，「当前节点」也为空
​
        if (null == root) {
            return;
        }
​
        TreeNode currNode = root;
​
        while (!stack.isEmpty() || null != currNode) {
            if (null != currNode) {
                stack.push(currNode);
                currNode = currNode.left;
            } else {
                TreeNode validNode = stack.pop();
                result.add(validNode);
                currNode = validNode.right;
            }
        }
​
    }

    /**
     * 遍历：后续（非递归，循环方式）
     *
     * @param root 二叉树根节点
     * @param result 遍历输出的结果
     */
    public static void postOrderTraverseLoop(TreeNode root, List<TreeNode> result) {
        Stack<TreeNode> stack = new Stack<>();
​
        // 基本逻辑：非空「左子树」循环入栈，顶点不出栈，右子树有效则继续「左子树循环入栈」，若子节点全部出栈则顶部节点出栈
        // 1. 初始化：记录当前节点，为 root 节点
        // 2. 循环逻辑：
        // a. 「当前节点」非 null，则，入栈，并将「左子节点」设置为「当前节点」
        // b. 如果「当前节点」为 null，则，查询顶部节点（不弹出），判断其「右子节点」是否为 null or 为「上次输出」的节点，若满足，则，弹出「顶部节点」并输出
        // c. 如果「当前节点」为 null，且顶部节点（不弹出），其「右子节点」不为 null，且「未被输出」，则，将其作为「当前节点」，进入循环逻辑
        // 3. 终止条件：「栈」为空，且，「当前节点」也为空
​
        if (null == root) {
            return;
        }
​
        TreeNode currNode = root;
        TreeNode lastRecordNode = null;
​
        while (!stack.isEmpty() || currNode != null) {
            // a. 「当前节点」不为 null，则，入栈，并以「左子节点」作为当前节点，继续迭代
            if (null != currNode) {
                stack.push(currNode);
                currNode = currNode.left;
            } else {
                // b. 当前节点为 null，则，查询顶部节点
                TreeNode topNode = stack.peek();
​
                if (null != topNode.right && lastRecordNode != topNode.right) {
                    // 1. 「顶部节点」可以「右子节点」进行递归，则继续递归
                    currNode = topNode.right;
                } else {
                    // 2. 「顶部节点」满足「出栈条件」，则出栈访问
                    topNode = stack.pop();
                    lastRecordNode = topNode;
                    result.add(topNode);
                }
​
            }
        }
    }

    public static TreeNode treeToList(TreeNode root) {
        if (null == root) {
            return root;
        }
​
        Stack<TreeNode> stack = new Stack<>();
        TreeNode currNode = root;
​
        TreeNode preNode = null, headNode = null;
​
        while (!stack.isEmpty() || null != currNode) {
            if (null != currNode) {
                // 左子节点，循环入栈
                stack.push(currNode);
                currNode = currNode.left;
            } else {
                // 弹出栈顶元素
                TreeNode topNode = stack.pop();
​
                // 标记：head
                if (null == headNode) {
                    headNode = topNode;
                }
                if (null != preNode) {
                    preNode.right = topNode;
                }
​
                // 更新「前驱节点」
                topNode.left = preNode;
                preNode = topNode;
​
                // 迭代：右子节点，继续迭代
                currNode = topNode.right;
            }
        }
        return headNode;
    }

    public static List<TreeNode> rightMost(TreeNode root) {
        List<TreeNode> list = new LinkedList<>();
​
        if (null == root) {
            return null;
        }
​
        rightMost(root, 0, list);
​
        return list;
    }
​
​
    public static void rightMost(TreeNode currNode, int depth, List<TreeNode> list) {
        if (list.size() == depth) {
            list.add(currNode);
        }
​
        // 右侧优先
        if (currNode.right != null) {
            rightMost(currNode.right, depth + 1, list);
        }
        if (currNode.left != null) {
            rightMost(currNode.left, depth + 1, list);
        }
​
    }