广西和住房城乡建设厅网站,做网站的设计流程,网站设置为默认主页,阳光梦网站建设文章目录 1. 汉诺塔问题题干#xff1a;算法原理#xff1a;代码#xff1a; 2. 合并两个有序链表题干#xff1a;算法原理#xff1a;代码#xff1a; 3. 反转链表题干#xff1a;算法原理#xff1a;代码#xff1a; 4. 最大子数组和题干#xff1a;算法原理#… 文章目录 1. 汉诺塔问题题干算法原理代码 2. 合并两个有序链表题干算法原理代码 3. 反转链表题干算法原理代码 4. 最大子数组和题干算法原理1. 状态表示2. 状态转移方程3. 初始化4. 填表顺序5. 返回值 代码 5. 环形子数组的最大和题干算法原理1. 状态表示2. 状态转移方程3. 初始化4. 填表顺序5. 返回值 代码 1. 汉诺塔问题 原题链接 题干 算法原理
利用递归算法
将x柱子上的一堆盘子借助 y柱子转移到z 柱子上面
递归函数流程
当前问题规模为 n1 时直接将 A 中的最上面盘子挪到 C 中并返回递归将 A 中最上面的 n-1 个盘子挪到 B 中将 A 中最上面的⼀个盘子挪到 C 中将 B 中上面 n-1 个盘子挪到 C 中 代码
class Solution {public void hanota(ListInteger a, ListInteger b, ListInteger c) {dfs(a, b, c, a.size());}public void dfs(ListInteger a, ListInteger b, ListInteger 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. 合并两个有序链表 原题链接 题干
升序 链表 新链表是通过拼接给定的两个链表的所有节点组成的 算法原理 重复子问题函数头的设计 合并两个有序链表 只关心一个子问题咋做什么函数体的设计 选择两个头结点中较小的结点作为最终合并后的头结点然后将剩下的链表交给递归函数去处理 递归的出口 谁为空返回另一个 代码
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让当前节点后面的链表先逆序并且把头结点返回 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. 初始化
辅助结点里面的值要「保证后续填表是正确的」「下标的映射关系」 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. 初始化
辅助结点里面的值要「保证后续填表是正确的」「下标的映射关系」
4. 填表顺序
从左往右
5. 返回值
先找到 f 表里面的最大值 - fmax找到 g 表里面的最小值 - gmin统计所有元素的和 - sum返回 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);}
}
