算法第五周

1.汉诺塔问题

描述

在经典汉诺塔问题中，有 3 根柱子及 N 个不同大小的穿孔圆盘，盘子可以滑入任意一根柱子。一开始，所有盘子自上而下按升序依次套在第一根柱子上(即每一个盘子只能放在更大的盘子上面)。移动圆盘时受到以下限制:

1. 每次只能移动一个盘子;
2. 盘子只能从柱子顶端滑出移到下一根柱子;
3. 盘子只能叠在比它大的盘子上。

请编写程序，用栈将所有盘子从第一根柱子移到最后一根柱子。
你需要原地修改栈。

示例1:

输入：A = [2, 1, 0], B = [], C = []
输出：C = [2, 1, 0]

示例2:

输入：A = [1, 0], B = [], C = []
输出：C = [1, 0]

提示:

A中盘子的数目不大于14个。

1.汉诺塔问题详解

2.汉诺塔的图解递归算法

public void hanota(List<Integer> A, List<Integer> B, List<Integer> C) {
    move(A.size(), A, B, C);
}

public void move(int size, List<Integer> A, List<Integer> B, List<Integer> C) {
    if (size == 1) {
        C.add(A.remove(A.size() - 1));
    } else {
        move(size - 1, A, C, B);
        Integer remove = A.remove(A.size() - 1);
        C.add(remove);
        move(size - 1, B, A, C);
    }
}

2.排序链表

描述

给你链表的头结点 head ，请将其按 升序 排列并返回 排序后的链表 。

进阶：

你可以在 O(n log n) 时间复杂度和常数级空间复杂度下，对链表进行排序吗？

示例 1：

输入：head = [4,2,1,3]
输出：[1,2,3,4]

示例 2：

输入：head = [-1,5,3,4,0]
输出：[-1,0,3,4,5]

示例 3：

输入：head = []
输出：[]

提示：

链表中节点的数目在范围 [0, 5 * $10^4$] 内

$-10^5$ <= Node.val <= $10^5$

1.图解排序算法之归并排序

1.归并排序

public ListNode sortList(ListNode head) {
    if (head == null) return head;
    List<Integer> newlist = new ArrayList<>();
    ListNode cur = head;
    while (cur != null) {
        newlist.add(cur.val);
        cur = cur.next;
    }

    int[] temp = new int[newlist.size()];

    merge_sort_list(newlist, temp, 0, newlist.size() - 1);

    ListNode newNode = new ListNode();
    newNode.val = newlist.get(newlist.size() - 1);
    for (int i = newlist.size() - 2; i >= 0; i--) {
        ListNode pre = new ListNode();
        pre.val = newlist.get(i);
        pre.next = newNode;
        newNode = pre;
    }

    return newNode;
}
//归并排序
public void merge_sort_list(List<Integer> list, int[] temp, int start, int end) {
    if (start >= end) {
        return;
    }

    int mid = (start + end) / 2;
    merge_sort_list(list, temp, start, mid);
    merge_sort_list(list, temp, mid + 1, end);
    merge(list, temp, start, end, mid);
}

public void merge(List<Integer> list, int[] temp, int start, int end, int mid) {
    int i = start;
    int j = mid + 1;
    int t = 0;

    while (i <= mid && j <= end) {
        if (list.get(i) <= list.get(j)) {
            temp[t++] = list.get(i++);
        } else {
            temp[t++] = list.get(j++);
        }
    }
    while (i <= mid) {
        temp[t++] = list.get(i++);
    }

    while (j <= end) {
        temp[t++] = list.get(j++);
    }
    t = 0;
    while (start <= end) {
        list.set(start++, temp[t++]);
    }
}

2.快慢双指针法

public ListNode sortList(ListNode head) {
        if (head == null || head.next == null) {
            return head;
        }

        ListNode fast = head.next;
        ListNode slow = head;
        while (fast != null && fast.next != null) {
            slow = slow.next;
            fast = fast.next.next;//快指针以两倍步进增加
        }
        ListNode mid = slow.next; //找到中间点
        slow.next = null;//截断中间点

        ListNode left = sortList(head);
        ListNode right = sortList(mid);

        ListNode h = new ListNode(0);
        ListNode ret = h;

        while (left != null && right != null) {
            if (left.val > right.val) {
                h.next = right;
                right = right.next;
            } else {
                h.next = left;
                left = left.next;
            }
            h = h.next;
        }
        h.next = left != null ? left : right;
        return ret.next;
    }