【算法刷题】Day30

1. 汉诺塔问题

原题链接

---

题干：

---

算法原理：

利用递归算法

将x柱子上的一堆盘子，借助 y柱子，转移到z 柱子上面

递归函数流程：

1. 当前问题规模为 n=1 时，直接将 A 中的最上面盘子挪到 C 中并返回
2. 递归将 A 中最上面的 n-1 个盘子挪到 B 中
3. 将 A 中最上面的⼀个盘子挪到 C 中
4. 将 B 中上面 n-1 个盘子挪到 C 中

---

代码：

class Solution {public void hanota(List<Integer> a, List<Integer> b, List<Integer> c) {dfs(a, b, c, a.size());}public void dfs(List<Integer> a, List<Integer> b, List<Integer> c, int n) {if(n == 1) {c.add(a.remove(a.size() - 1));return;}dfs(a, c, b, n - 1);c.add(a.remove(a.size() - 1));dfs(b, a, c, n - 1);}
}

---

2. 合并两个有序链表

原题链接

---

题干：

升序 链表
新链表是通过拼接给定的两个链表的所有节点组成的

---

算法原理：

1. 重复子问题（函数头的设计）
   合并两个有序链表

2. 只关心一个子问题咋做什么（函数体的设计）
   选择两个头结点中较小的结点作为最终合并后的头结点，然后将剩下的链表交给递归函数去处理

3. 递归的出口
   谁为空返回另一个

---

代码：

class Solution {public ListNode mergeTwoLists(ListNode l1, ListNode l2) {if(l1 == null) {return l2;}if(l2 == null) {return l1;}if(l1.val <= l2.val) {l1.next = mergeTwoLists(l1.next, l2);return l1;}else {l2.next = mergeTwoLists(l1, l2.next);return l2;}}
}

---

3. 反转链表

原题链接

---

题干：

单链表的头节点 head ，反转链表，并返回反转后的链表

---

算法原理：

利用递归

1. 从宏观角度
   1）让当前节点后面的链表先逆序，并且把头结点返回
   2）让当前节点添加到逆置后的链表的后面
2. 将链表看成一棵树
   仅需做一次 dfs 即可
   后序遍历
   

---

代码：

class Solution {public ListNode reverseList(ListNode head) {if(head == null || head.next == null) {return head;}ListNode newheader = reverseList(head.next);head.next.next = head;head.next = null;return newheader;}
}

---

4. 最大子数组和

原题链接

---

题干：

一个整数数组 nums
找出一个具有最大和的连续子数组

---

算法原理：

1. 状态表示：

dp[i] 表示：以 i 位置为结尾的所有子数组中的最大和

2. 状态转移方程

dp[i] = max(nums[i], dp[i - 1] + nums[i])

3. 初始化

1. 辅助结点里面的值要「保证后续填表是正确的」
2. 「下标的映射关系」

4. 填表顺序

从左往右

5. 返回值

整个dp表的最大值

---

代码：

class Solution {public int maxSubArray(int[] nums) {int n = nums.length;int[] dp = new int[n + 1];int ret = Integer.MIN_VALUE;for(int i = 1; i <= n; i++) {dp[i] = Math.max(nums[i - 1], dp[i - 1] + nums[i - 1]);ret = Math.max(ret, dp[i]);} return ret;}
}

5. 环形子数组的最大和

原题链接

---

题干：

长度为 n 的环形整数数组 nums
返回 nums 的非空 子数组 的最大可能和

---

算法原理：

1. 状态表示：

2. 状态转移方程

f[i] = max(nums[i], f[i - 1] + nums[i])

g[i] = min(nums[i], g[i - 1] + nums[i])

3. 初始化

1. 辅助结点里面的值要「保证后续填表是正确的」
2. 「下标的映射关系」
3. 

4. 填表顺序

从左往右

5. 返回值

1. 先找到 f 表里面的最大值 -> fmax
2. 找到 g 表里面的最小值 -> gmin
3. 统计所有元素的和 -> sum
4. 返回 sum == gmin ? fmax : max(fmax, sum - gmin)

---

代码：

class Solution {public int maxSubarraySumCircular(int[] nums) {int n = nums.length;int[] f = new int[n + 1];int[] g = new int[n + 1];int sum = 0;int fmax = Integer.MIN_VALUE;int gmin = Integer.MAX_VALUE;for(int i = 1; i <= n; i++) {int x = nums[i - 1];f[i] = Math.max(x, x + f[i - 1]);fmax = Math.max(fmax, f[i]);g[i] = Math.min(x, x + g[i - 1]);gmin = Math.min(gmin, g[i]);sum += x;}return sum == gmin ? fmax : Math.max(fmax, sum - gmin);}
}