算法-LeetCode练习

链表

链表典型问题参考

逆序遍历链表

简单一个递归，先递归再取值

public static void reverseTraverse(Node node) {
    if (node == null) {
        return ;
    }
    reverseTraverse(node.next);
    System.out.println(node.value);
}

删除倒数第N个节点

和逆序遍历链表一个思路。递归处理，就是反转了，i++就是从后边开始算。 调试下边界即可。

static int i = 0;

public static void reverseDel(Node node, int num) {
    if (node == null) {
        return;
    }
    reverseDel(node.next, num);
    i++;
    // 最后1个，i=2; 倒数第二个，i=3; 这里调试一下即可，边界处理
    if (i == num + 1) {
        // System.out.println(node.value);
        node.next = node.next.next;
    }

}

翻转链表

双指针解决问题

next、node.next、pre、node

public static void main(String[] args) {
    Node node = new Node(1);
    node.next = new Node(2);
    node.next.next = new Node(3);

    Node newHead = reverse(node);

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

// 返回反转后的新头结点
static Node reverse(Node head) {
    if(head == null || head.next == null) {
        return head;
    }
    // 交给递归
    Node newHead = reverse(head.next);
    // 后一个节点指向自己（关键）
    head.next.next = head;
    // 断开旧指向
    head.next = null;
    // newHead 只负责传递，真正改指针是 `head.next.next=head`
    return newHead;
}

俩单链表交叉点

A头节点走完A链表，再走B链表。B头节点走完B链表再走A链表，如果交叉那么就相等的节点就是交叉点。不交叉就都是null。

public ListNode getIntersectionNode(ListNode headA, ListNode headB) {
    if (headA == null || headB == null) {
        return null;
    }
    ListNode pA = headA, pB = headB;
    while (pA != pB) {
        pA = pA == null ? headB : pA.next;
        pB = pB == null ? headA : pB.next;
    }
    return pA;
}

合并两个有序链表

public ListNode mergeTwoLists(ListNode l1, ListNode l2) {
    ListNode prehead = new ListNode(-1);

    ListNode prev = prehead;
    while (l1 != null && l2 != null) {
        if (l1.val <= l2.val) {
            prev.next = l1;
            l1 = l1.next;
        } else {
            prev.next = l2;
            l2 = l2.next;
        }
        prev = prev.next;
    }

    // 将链表末尾指向未合并完的链表
    prev.next = l1 == null ? l2 : l1;

    return prehead.next;
}

链表排序

归并排序

思路：一个链表拆成两个，最后两两merge归并排序 递归

  1. 单链表拆成俩链表
  2. 合并两个有序链表
public class LinkedListSort {
    public static void main(String[] args) {
        Node node2 = new Node(23);
        node2.next = new Node(9);
        node2.next.next = new Node(95);
        node2.next.next.next = new Node(3);
        node2.next.next.next.next = new Node(118);
        node2.next.next.next.next.next = new Node(98);

        Node sort = sort(node2);

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


    /**
     * 思路：一个链表拆成两个，最后两两merge归并排序 递归
     * 1. 单链表拆成俩链表
     * 2. 合并两个有序链表
     * @param node
     * @return
     */
    static Node sort(Node node) {
        if (node == null || node.next == null) {
            return node;
        }
        Node node1 = new Node();
        Node node2 = new Node();


        Node tmpNode1 = node1;
        Node tmpNode2 = node2;

        Node cur = node;

        // 一个链表按奇偶数拆成两个
        while (cur != null) {
            // System.out.println(cur.value);

            tmpNode1.next = cur;
            tmpNode2.next = cur.next;

            // 步长是2 这是把一个链表拆分成两个链表的关键思路
            if (cur.next != null) {
                cur = cur.next.next;
            } else {
                // cur.next是空，表示链表到头了 可以退出了
                break;
            }

            tmpNode1 = tmpNode1.next;
            tmpNode2 = tmpNode2.next;

            // 这里可以调试下，因为上边tmpNode1.next = cur; cur是原链表元素，这里要强制null，否则最后的元素会继承原来的链表
            tmpNode1.next = null;
        }

        // 归并思路
        return merge(sort(node1.next), sort(node2.next));

    }


    /**
     * 合并两个有序链表
     * @param a
     * @param b
     * @return
     */
    static Node merge(Node a, Node b) {
        if (a == null) {
            return b;
        }

        if (b == null) {
            return a;
        }

        Node ret = new Node();
        Node c = ret;

        while (a != null && b != null) {
            if (a.value < b.value) {

                c.next = new Node(a.value);
                a = a.next;

            } else {
                c.next = new Node(b.value);
                b = b.next;
            }
            c = c.next;
        }

        while (a != null) {
            c.next = new Node(a.value);
            a = a.next;
            c = c.next;
        }

        while (b != null) {
            c.next = new Node(b.value);
            b = b.next;
            c = c.next;
        }
        return ret.next;
    }
}

快排

思路：

  1. 分三个链表，小于中枢点值组成一个链表，等于的一个链表，大于的一个链表
  2. 这三个链表组合连接起来
static ListNode quickSort(ListNode head) {
    if (head == null || head.next == null) {
        return head;
    }
    // 定义三个链表头尾节点
    ListNode left = new ListNode(-1);
    ListNode leftTail = left;

    ListNode mid = new ListNode(-1);
    ListNode midTail = mid;

    ListNode right = new ListNode(-1);
    ListNode rightTail = right;

    int pivot = head.value;
    while (head != null) {
        // 比 pivot 小的 给到left链表
        if (head.value < pivot) {
            leftTail.next = head;
            leftTail = leftTail.next;
        } else if (head.value == pivot) {
            midTail.next = head;
            midTail = midTail.next;
        } else {
            rightTail.next = head;
            rightTail = rightTail.next;
        }
        head = head.next;
    }

    // 每个链表隔断
    leftTail.next = midTail.next = rightTail.next = null;

    // 递归左链表
    left.next = quickSort(left.next);
    // 递归右链表
    right.next = quickSort(right.next);

    // 左 中 右 三个链表 连接起来
    getTail(left).next = mid.next;
    getTail(left).next = right.next;

    // 返回最左边的链表头结点
    return left.next;
}

static ListNode getTail(ListNode head) {
    // 判断head.next 需要返回尾节点
    while (head != null && head.next != null) {
        head = head.next;
    }
    return head;
}

二叉树

二叉树典型问题参考

后序遍历框架：

void traverse(TreeNode root) {
    if (root == null) {
        return;
    }
    // 前序位置
    traverse(root.left);
    // 中序位置
    traverse(root.right);
    // 后序位置
}

层序遍历

public class LevelTraverse {
    public static void main(String[] args) {
        TreeNode root = new TreeNode(1);
        root.left = new TreeNode(2);
        root.right = new TreeNode(8);
        root.right.right = new TreeNode(18);

        root.left.right =  new TreeNode(5);
        root.left.left =  new TreeNode(4);
        root.left.left.right =  new TreeNode(9);
        traverse(root);
    }

    static void traverse(TreeNode root) {
        if (root == null) {
            return;
        }

        Queue<TreeNode> queue = new LinkedList<>();

        queue.offer(root);

        while (!queue.isEmpty()) {
            TreeNode treeNode = queue.poll();
            System.out.println(treeNode.value);

            if (treeNode.left != null) {
                queue.offer(treeNode.left);
            }
            if (treeNode.right != null) {
                queue.offer(treeNode.right);
            }
        }
    }
}

最大深度

  1. 层序遍历计算深度
  2. 递归方式(后序遍历框架 涉及左右子树遍历后决策)
static int traverse(TreeNode root) {
    int deep = 0;

    if (root == null) {
        return deep;
    }

    Queue<TreeNode> queue = new LinkedList<>();

    queue.offer(root);


    while (!queue.isEmpty()) {
        int size = queue.size();

        // 把当前队列的元素个数排除完，意味着这一层结束
        for (int i = size; i > 0; i--) {
            TreeNode treeNode = queue.poll();
            // System.out.println(treeNode.value);

            if (treeNode.left != null) {
                queue.offer(treeNode.left);
            }
            if (treeNode.right != null) {
                queue.offer(treeNode.right);
            }
        }
        deep++;
    }
    return deep;
}

/**
 * 递归运算 每一层的深度=子节点最大深度+1
 * @param root
 * @return
 */
static int deep(TreeNode root) {
    if (root == null) {
        return 0;
    }

    // 递归运算 每一层的深度=子节点最大深度+1
    return Math.max(deep(root.left), deep(root.right)) + 1;
}

最近公共祖先

妥妥后序遍历框架，因为涉及到左右子树都要遍历完做决策。

一旦发现题目和子树有关，那大概率要给函数设置合理的定义和返回值，在后序位置写代码了。

static Node lowestCommonAncestor(Node root, Node p, Node q) {
    if (root == null || root == p || root == q) {
        return root;
    }
    Node left = lowestCommonAncestor(root.left, p, q);
    Node right = lowestCommonAncestor(root.right, p, q);
    if (left == null) {
        return right;
    }
    if (right == null) {
        return left;
    }
    return root;
}

翻转二叉树

又一个典型的后序遍历框架，左右子树处理完，做一个交换策略。

public TreeNode invertTree(TreeNode root) {
    if (root == null) {
        return null;
    }
    TreeNode left = invertTree(root.left);
    TreeNode right = invertTree(root.right);
    root.left = right;
    root.right = left;
    return root;
}

相同结构的子树

// TreeNode为根的树序列化 
static Map<String, TreeNode> map = new HashMap<>();
// 重复的树根
static Set<TreeNode> set = new HashSet<>();

static String traverse(TreeNode root) {
    if (root == null) {
        return "";
    }
    String left = traverse(root.left);
    String right = traverse(root.right);

    // 序列化
    String strs = root.value + "(" + left + ")(" + right + ")";

    if (map.containsKey(strs)) {
        set.add(root);
    } else {
        map.put(strs, root);
    }
    return strs;
}

滑动窗口

滑动窗口典型问题参考

框架套路：

int left = 0, right = 0;

while (right < s.size()) {
    // 增大窗口
    window.add(s[right]);
    right++;

    while (window needs shrink) {
        // 缩小窗口
        window.remove(s[left]);
        left++;
    }
}

最长不重复子串

思路：左右窗口界限往后推进，下一个元素已经在窗口，则把left移动到出现过的元素

static int window(char[] chars) {
    LinkedList<String> window = new LinkedList<>();
    if (chars == null || chars.length == 0) {
        return 0;
    }
    int left = 0, right = 0;

    int max = 0;

    while (right < chars.length) {
        max = Math.max(max, window.size());
        String s = String.valueOf(chars[right]);

        // 下一个元素已经在窗口，则把left移动到出现过的元素
        if (window.size() > 0 && window.contains(s)) {
            int i = window.indexOf(s);
            System.out.println(i);
            for (int j = 0; j <= i; j++) {
                left++;
                window.removeFirst();
            }
        }
        window.addLast(s);
        right++;
    }
    return max;
}

最小覆盖子串

static String window(String str, String need) {
    if (str == null || need == null) {
        return "";
    }
    Map<Character, Integer> needMap = new HashMap<>();
    Map<Character, Integer> windowMap = new HashMap<>();


    for (int i = 0; i < need.length(); i++) {
        needMap.put(need.charAt(i), needMap.getOrDefault(need.charAt(i), 0) + 1);
    }
    // System.out.println(needMap);
    int left = 0, right = 0, start = 0;
    int valid = 0;

    int len = Integer.MAX_VALUE;

    while (right < str.length()) {
        char c = str.charAt(right);
        right++;

        if (needMap.containsKey(c)) {

            windowMap.put(c, windowMap.getOrDefault(c, 0) + 1);

            if (windowMap.get(c).equals(needMap.get(c))) {
                valid++;
            }

        }

        // System.out.println(windowMap);
        while (valid == needMap.size()) {
            if (right - left < len) {
                len = right - left;
                start = left;

            }
            char c1 = str.charAt(left);
            left++;

            if (needMap.containsKey(c1)) {
                if (needMap.get(c1).equals(windowMap.get(c1))) {
                    valid--;
                }
                windowMap.put(c1, windowMap.get(c1) - 1);
            }
        }
    }
    return len == Integer.MAX_VALUE ?
            "" : str.substring(start, len + start);

}

排序

堆排序

public class Heap {

    public static void main(String[] args) {
        // 第一个元素充当一个占用值，方便*2
        List<Integer> list = Arrays.asList(-1, 2, 1, 9, 4);

        System.out.println(list);

        // 调整成最大堆，从中间非叶子节点开始 2倍关系
        for (int i = list.size() / 2; i > 0; i--) {
            heapAdjust(i, list.size() - 1, list);
        }

        // 第一个和最后一个交换，最后的逐渐有序
        for (int j = list.size() - 1; j > 0; j--) {
            swap(list, 1, j);

            // 注意这里最大索引是j-1，因为已经被替换完了
            heapAdjust(1, j - 1, list);
        }

        System.out.println(list);

    }

    /**
     * 堆调整
     * @param begin
     * @param end
     * @param arr
     */
    static void heapAdjust(int begin, int end, List<Integer> arr) {
        // 从左叶子开始
        for (int k = begin * 2; k <= end; k = k * 2) {
            if (k + 1 <= end && arr.get(k + 1) > arr.get(k)) {
                k++;
            }
            if (arr.get(begin) > arr.get(k)) {
                break;
            }

            swap(arr, k, begin);

            // 再从begin的孩子继续，因为调整的时候可能下移，得需要再继续以孩子做调整
            begin = k;
        }
    }

    static void swap(List<Integer> list, int a, int b) {
        Integer integer = list.get(a);
        list.set(a, list.get(b));
        list.set(b, integer);
    }

}

归并排序

二叉树后序遍历框架应用

static List<Integer> mergeSort(List<Integer> list) {
    if (list.size() == 1) {
        return list;
    }

    // 二叉树后序遍历框架
    List<Integer> left = mergeSort(list.subList(0, list.size() / 2));
    List<Integer> right = mergeSort(list.subList(list.size() / 2, list.size()));

    return mergeTwoList(left, right);
}


static List<Integer> mergeTwoList(List<Integer> list1, List<Integer> list2) {
    List<Integer> list = new ArrayList<>();

    int i = 0, j = 0;

    while (i < list1.size() && j < list2.size()) {
        if (list1.get(i) < list2.get(j)) {
            list.add(list1.get(i));
            i++;
        } else {
            list.add(list2.get(j));
            j++;

        }
    }
    if (i < list1.size()) {
        list.addAll(list1.subList(i, list1.size()));
    }

    if (j < list2.size()) {

        list.addAll(list2.subList(j, list2.size()));
    }

    return list;
}

快排

二叉树前序遍历框架应用

static void quickSort(List<Integer> list, int low, int high) {
    if (low < high) {
        // 前序遍历框架
        int k = partition(list, low, high);

        quickSort(list, low, k - 1);
        quickSort(list, k + 1, high);
    }
}

static int partition(List<Integer> list, int low, int high) {
    Integer pivot = list.get(low);

    while (low < high) {
        while (low < high && list.get(high) >= pivot) {
            high--;
        }
        swap(list, low, high);

        while (low < high && list.get(low) <= pivot) {
            low++;
        }
        swap(list, low, high);
    }
    return low;
}

static void swap(List<Integer> list, int a, int b) {
    Integer integer = list.get(a);
    list.set(a, list.get(b));
    list.set(b, integer);
}

二分法

static int bsearch(int[] arr, int low, int high) {
    if (low > high) {
        return -1;
    }

    int mid = (low + high) / 2;

    if (obj > arr[mid]) {
        return bsearch(arr, mid + 1, high);
    }

    if (obj < arr[mid]) {
        return bsearch(arr, 0, mid - 1);
    }
    return mid;
}

矩阵

旋转图像：

static int[][] images = {{1, 2, 3}, {4, 5, 6}, {7,8,9}};

public static void main(String[] args) {
    // 调试
    show(images);
    // 1. 按对角线轴，交换(顺时针、逆时针 决定对角线的方向)
    for (int i = 0; i < images.length; i++) {
        // 重点：遍历上半部分矩阵， 每一行 j 比 i 大1个。否则白交换了
        for (int j = i + 1; j < images.length; j++) {
            int tmp = images[i][j];
            images[i][j] = images[j][i];
            images[j][i] = tmp;
        }
    }
    // 调试
    show(images);

    // 2. 按中间竖轴 交换
    for (int i = 0; i < images.length; i++) {
        for (int j = 0; j < images.length / 2; j++) {
            int tmp = images[i][j];
            images[i][j] = images[i][images.length - j - 1];
            images[i][images.length - j - 1] = tmp;
        }
    }
    show(images);
}

static void show(int[][] images) {
    for (int i = 0; i < images.length; i++) {
        String x = "";
        for (int j = 0; j < images.length; j++) {
            x += " " + images[i][j];

        }
        System.out.println(x);
    }
    System.out.println("=========");
}

参考