引用PTAL1-103 整数的持续性从任一给定的正整数 n 出发将其每一位数字相乘记得到的乘积为 n1​。以此类推令 ni1​ 为 ni​ 的各位数字的乘积直到最后得到一个个位数 nm​则 m 就称为 n 的持续性。例如 679 的持续性就是 5因为我们从 679 开始得到 6×7×9378随后得到 3×7×8168、1×6×848、4×832最后得到 3×26一共用了 5 步。本题就请你编写程序找出任一给定区间内持续性最长的整数。输入格式输入在一行中给出两个正整数 a 和 b1≤a≤b≤10^9 且 (b−a)10^3为给定区间的两个端点。输出格式首先在第一行输出区间 [a,b] 内整数最长的持续性。随后在第二行中输出持续性最长的整数。如果这样的整数不唯一则按照递增序输出数字间以 1 个空格分隔行首尾不得有多余空格。输入样例500 700输出样例5679 688 697这个题目其实还是要看题说话按题目来就行了这个PTA的格式错误是又来了末尾多打空格就格式错误了还是注意一点import java.io.*; import java.util.*; public class Main { public static int getCount(long n) {//求一个数字的位数因为我们在后面的循环停止的条件就是一位数拆不下去了 if (n 0) return 1; int count 0; while (n ! 0) { count; n / 10; } return count; } public static int getNum(long n) {//记录我的持续性步数 int step 0;//步数先记为0 while (getCount(n) 1) { long mul 1; long temp n; while (temp 0) { mul * temp % 10; temp / 10; } n mul;//把求出来的值赋给n再进入循环让step step; } return step; } public static void main(String[] args) throws IOException { BufferedReader br new BufferedReader(new InputStreamReader(System.in)); PrintWriter out new PrintWriter(System.out); StreamTokenizer in new StreamTokenizer(br); in.nextToken(); int a (int) in.nval; in.nextToken(); int b (int) in.nval; TreeMapInteger, Integer treeMap new TreeMap();//用TreeMap的目的是自动排序取最大步数 for (int i a; i b; i) { treeMap.put(i, getNum(i)); } int maxStep Integer.MIN_VALUE; for (int step : treeMap.values()) { if (step maxStep) { maxStep step; } } ListInteger ans new ArrayList(); for (Map.EntryInteger, Integer entry : treeMap.entrySet()) { if (entry.getValue() maxStep) { ans.add(entry.getKey()); } } out.println(maxStep); for (int i 0; i ans.size(); i) { out.print(ans.get(i)); if (i ! ans.size() - 1) out.print( );//这里还是要注意一下空格问题 } out.flush(); br.close(); out.close(); } }其实对于子数组的问题之前总结的还不够深所以我在这里重新总结一下题型序号题型名称对应原题核心解法时间复杂度平台同源题①普通最大子数组和LeetCode 53、洛谷 P11151. Kadane 贪心2. 前缀和 贪心O(n)力扣 53洛谷 P1115②和约束类子数组全正LeetCode 209含负LeetCode 325全正滑动窗口含负前缀和 哈希O(n)力扣 209、325③长度≤K 最大子数组和洛谷 P1714前缀和 单调队列O(n)洛谷 P1714④环形最大子数组和LeetCode 918双 Kadane总和减最小子数组O(n)力扣 918⑤乘积最大子数组LeetCode 152双状态 Kadane同时维护当前最大 / 最小乘积应对负负得正O(n)力扣 1521.普通最大子数组和这个我现在所会的方法就三种①暴力解法②前缀和贪心③kadane贪心事实上还可以用莫队来解不过我并不熟悉这种写法首先前缀和就是把原数组前多少项加起来那么kadane算法是啥其实我和我同学一般叫他老登算法哈哈~~~本质上我们再求子数组的和最大的时候我们遍历数组我们把每一个数字都看作我们子数组部分的末尾求他前面部分的加和如果前面因为有负数让加和小于当前末尾值了那就将子数组的开头移到这个末尾值来重新遍历不断更新最大值就行了这种思想可以用到最长连续上升子序列里去就是如果上升被打断了就舍弃我记录的count让它变为1再进行判断和count的操作甚至我们还可以用它去求最长公共字串一样的遇到不同的字母了count就断掉在后面再更新最大值就行了那么代码如下//普通最大子数组和有正有负 //解法一前缀和贪心: #include bits/stdc.h using namespace std; int main() { ios::sync_with_stdio(false); cin.tie(nullptr); int n; cinn; vectorint a(n1); for (int i1;in;i) cina[i]; vectorint b(n1); b[0]0; for (int i1;in;i) b[i]b[i-1]a[i];//构建一个前缀和数组 int Maxb[1];//存储最大值将它定为第一个元素 int Minb[0];//存储最小值将它定为0 for (int i1;in;i) { Maxmax(Max,b[i]-Min);//运用了贪心算法计算当前前缀和减去最小值 Minmin(Min,b[i]);//存储当前最小值 } coutMaxendl; return 0; } //解法二kadane算法 #include bits/stdc.h using namespace std; int main() { ios::sync_with_stdio(false); cin.tie(nullptr); int n; cinn; vectorint dp; for (int i0;in;i) { int num; cinnum; dp.push_back(num); } int Maxdp[0]; for (int i1;in;i) { dp[i]max(dp[i],dp[i-1]dp[i]);//这一步就是我前面的最大值加现在的数和现在的数比较, //就是如果说我[2,-1,-9,4,5],我到数字4的时候 ////如果加前面的一段就会负的更多那我就要选择不加前面的一段就是窗口后移到4的地方重新开始计算 Maxmax(Max,dp[i]);//然后再不断更新我的最大值 } coutMaxendl; return 0; }2.和不大于目标值k的最长子数组代码和思路如下//如果全是正数就用滑动窗口代码如下 #include bits/stdc.h using namespace std; int main() { ios::sync_with_stdio(false); cin.tie(nullptr); int n,k; cinnk; vectorint a(n); for (int i0;in;i) cina[i]; int left0;//滑动窗口的左边界 int sum0,Max0; for (int right0;rightn;right) { suma[right];//窗口右边界向右移动 while(sum k) {//窗口内的和超过了K sum-a[left];//窗口左边界向右移动就是吐出来左边的数 left;//让左指针向右移动减小窗口大小 } Maxmax(Max,right-left1);//更新最大长度 } coutMaxendl; return 0; } //如果有负数和0 //这个为啥就不能用滑动窗口了呢 //举个例子[3, -2, 5, -1],k5就是说我们的左指针先不动右指针一直右移 //找到的第一个满足条件的是[3]长度1然后右移加-2窗口[3,-2]和1长度2再右移加5窗口[3,-2,5]和6大于k了 //按照我们的想法要让左指针右移把3吐出来窗口变成[-2,5]和3长度2再加入-1窗口就变成了[-2,5,-1]和2长度3。 //最终我们求出来的最大长度为3但是正确答案是整个数组[3,-2,5,-1]和5长度4。 //为什么不对了因为当窗口[3,-2,5]和超标时我们把左边的3扔掉了以为后面再也用不上3了。可是后面来了个-1把和拉低了这时候如果3还在整个数组的和正好是5长度4。 //但是滑动窗口的左指针只能往右走扔掉的3再也回不来了。所以有负数的时候滑动窗口会因为“暂时的超标”而错误地丢弃左边可能被后面负数救回来的元素。这就是不能用它的原因。 //所以说这道题我们要用前缀和哈希表 #include bits/stdc.h using namespace std; int main() { ios::sync_with_stdio(false); cin.tie(nullptr); int n, k; cin n k; vectorint a(n); for (int i0; in; i) cin a[i]; unordered_mapint, int mp; mp[0] -1; //用前缀和 0 出现在 -1 位置 int sum 0, Max 0; for (int i0; in; i) { sum a[i];//创造前缀和 if (mp.count(sum - k)) {//找到前缀和减去k的差就是满足条件的子数组的开始位置 Max max(Max, i - mp[sum - k]);//更新最大长度i-mp[sum - k]为当前子数组的长度 } if (!mp.count(sum)) { // 只存第一次出现的位置保证最长 mp[sum] i;//存前缀和出现的位置,避免重复 } } cout Max endl; return 0; }3.长度小于等于k加和最大的子数组代码和思路如下//长度 ≤ K和最大的子数组 //单调队列前缀和 //第一我们在看前缀和模版的时候其实就知道前缀和可以用来多次查询[l1,r]区间的子数组的加和。 //所以说我们要求长度k的子数组和的最大值本质上我们查询区间(限制条件是l-rk)的加和最大值 //我们可以向kadane算法一样就是定一个后缀然后看以后缀为结尾的窗口的加和最大值然后更新最大值就可以了 //就好像洛谷P1886滑动窗口/单调队列差不多的我从队尾弹出一个数以他为窗口的结尾当然同时要判断窗口的长度 //然后和上面说的一样更新最大值就行了 #include bits/stdc.h using namespace std; int main() { int n, k; cin n k; vectorint a(n 1); for (int i 1; i n; i) { cin a[i]; } vectorlong long b(n 1, 0); for (int i 1; i n; i) { b[i] b[i-1] a[i];//创建一个前缀和数组 } dequeint q; q.push_back(0);//创建一个单调队列, long long Max LLONG_MIN; for (int i 1; i n; i) { while (!q.empty() i - q.front() k) {//在对位取数的时候要判断窗口的长度是否符合要求 q.pop_front(); } Max max(Max, b[i] - b[q.front()]);//然后再不断更新给我们的最大值 while (!q.empty() b[i] b[q.back()]) {//这个是要维护我们单调队列的单调性最后那个数比前的数小就弹出 q.pop_back(); } q.push_back(i);//添加当前数 } cout Max endl; return 0; }4.环形数组子数组和最大值代码和思路如下//环形最大子数组和 //解释一下啥是环形数组就是类似循环链表到最后一个元素后再从第一个开始 //事实上我在看这样的题目的时候觉得可以double一下数组再求 //但这样直接求是不对的因为环形数组的子数组长度不能超过 n。 //比如 [5,-3,5]double 后是 [5,-3,5,5,-3,5]DP 会算出 [5,-3,5,5] 12但实际环形数组最大子数组是 [5,5] 10因为不能重复取元素。 //所以我们在考虑问题的时候就可以思考这个题目可能出现的情况 //1.最长子数组不跨首尾的时候那就和普通的kadane算法一样直接求 //2.那如果跨首尾那我们正难则反就是我们已经知道最大和的那一段是跨首尾的那想想就知道最小的那一段就一定不跨首尾 //所以我们用数组的总和减去最小的不就是最大的吗相当于我用一次kadane算法求最小值一剪就行了 //3.最后我们比较如上两种情况谁最大输出他们的最大值就是答案了 #include bits/stdc.h using namespace std; pairint, int getMaxMin(vectorint a) { int curMax a[0], maxSum a[0]; int curMin a[0], minSum a[0]; for (int i 1; i a.size(); i) { curMax max(a[i], curMax a[i]); maxSum max(maxSum, curMax); curMin min(a[i], curMin a[i]); minSum min(minSum, curMin); } return {maxSum, minSum}; } int maxSubarraySumCircular(vectorint nums) { int sum 0; for (int x : nums) sum x; auto [maxSum, minSum] getMaxMin(nums); int cross sum - minSum; return maxSum 0 ? maxSum : max(maxSum, cross);//这里是处理了全是负数的情况 //如果全是负数那就会出现cross为0的情况这时候我们应该取的是最大的那个负数才对 } int main() { ios::sync_with_stdio(false); cin.tie(nullptr); int n; cinn; vectorint a(n); for (int i0;in;i) cina[i]; coutmaxSubarraySumCircular(a)endl; return 0; }5.求子数组乘积的最大值代码和思路如下//实现乘积最大子数组 //事实上我在写这个题目的时候我还是想到了kadane算法本质上我就是想将它加和求最大值的思路移到乘法来 //就是我定义一个mula[0],然后从前面乘如果当前乘积当前数就舍弃然后从当前数开始乘最后更新最大值 //不过这样是有巨大的bug的因为乘积有一条就是负负得正我如果在前面发现负数太大比当前数小了那我一定会舍弃它 //但是万一后面也有个负数负负得正了和前面的负数乘起来可能就是我们要求的最大值那我在前面就舍弃了那最终结果就不对了 //比如说[-2, 3, -4]其实正确的是24按我上面说的就会算出3所以我们其实应该如下想 //那我们其实可以加入当前最小值就是说因为我们乘积有负负得正的特性那我们把当前最小值加进来判断 //在这个过程中最小值是有可能在后面变成最大值的保存它就可以更精准最后在不断更新最大值就可可以说这还是kadane算法的延申 //那我们思考一下如果是除呢除的情况要不要考虑最小值呢 //其实还是要的还是[-2, 3, -4]我们只记录最大值去比较的话就因为-2/3肯定比3小那我们舍弃它求出来的值就是-3/4实际上正确的是1/6 //而且我们在除的时候也要考虑为0的情况哦 #include bits/stdc.h using namespace std; int main() { ios::sync_with_stdio(false); cin.tie(nullptr); int n; cinn; vectorint a(n); for (int i0;in;i) cina[i]; int Maxa[0]; int Mina[0]; int resa[0]; for (int i1;in;i) { int tempMaxMax; int tempMinMin; Maxmax(max(tempMax*a[i],tempMin*a[i]),a[i]); Minmin(min(tempMax*a[i],tempMin*a[i]),a[i]); resmax(res,Max); } coutresendl; return 0; }引用PTA算法1-7~9 连续子序列最大和:给定 n 个整数组成的序列 { a1​,a2​,⋯,an​ }“连续子序列”被定义为 { ai​,ai1​,⋯,aj​ }其中 1≤i≤j≤n。“连续子序列最大和”则被定义为所有连续子序列元素的和中最大者。例如给定序列 { -2, 11, -4, 13, -5, -2 }其连续子序列 { 11, -4, 13 } 有最大的和 20。请编写程序计算给定整数序列的连续子序列最大和。本题旨在测试各种不同的算法在各种数据情况下的表现。各组测试数据特点如下数据 0~6测试基本正确性数据 710^3 个随机整数数据 810^4 个随机整数数据 910^5 个随机整数。输入格式:输入第一行给出正整数 n (≤10^5)第二行给出 n 个整数绝对值均不超过 100其间以空格分隔。输出格式:在第一行中输出连续子序列最大和第二行输出该子序列首尾的数组下标从 0 开始以 1 个空格分隔。若解不唯一则输出最小的数组下标如样例所示。注意如果序列中所有整数皆为零或负数则取空子列的结果是最大的为 0此时空子序列数组首尾的下标均为 -1。输入样例:10-10 2 2 3 4 -5 -23 4 7 -21输出样例:111 4这个题多出来它子数组的端点输出联系老登算法(kadane算法在前面因为有负数让加和小于当前末尾值了的时候我就把子数组的左边界到当前位置持续记录就可代码如下#include bits/stdc.h using namespace std; int main() { ios::sync_with_stdio(false); cin.tie(nullptr); int n; cin n; vectorint a(n); // 标记数组中是否存在正数 // 作用如果全是负数/0最大子序列和为0且下标输出-1 -1 bool hasPositive false; for (int i 0; i n; i) { cin a[i]; // 只要有一个数 0就标记为true if (a[i] 0) hasPositive true; } // 如果数组中没有正数全负 或 全0 if (!hasPositive) { // 根据题目要求输出最大和0空子序列下标-1 -1 cout 0\n-1 -1\n; return 0; } int maxSum a[0]; // 记录全局最大子数组和 int curSum 0; // 记录当前连续子数组的和 int bestStart 0; // 最优子数组的起点下标 int bestEnd 0; // 最优子数组的终点下标 int curStart 0; // 当前正在累加的子数组起点 // 遍历数组动态更新最大和与区间 for (int i 0; i n; i) { // 如果当前和为负数说明前面的子数组拖累结果重新开始计算 if (curSum 0) { curSum a[i]; // 从当前数字重新开始 curStart i; // 记录新起点 } else { curSum a[i]; // 否则继续累加当前数字 } // 如果当前子数组和 已知最大值更新最大值和最优区间 if (curSum maxSum) { maxSum curSum; bestStart curStart; bestEnd i; } } cout maxSum \n bestStart bestEnd \n; return 0; }学习总结哈夫曼树和哈夫曼编码先看我作业里的一道题题目描述在数据压缩领域哈夫曼编码是一种常用的无损压缩算法。给定 N 个字符及其出现的频率权重我们需要构建一棵哈夫曼树。哈夫曼树的构建规则是每次从集合中选出两个权值最小的节点合并成一个新的节点新节点的权值为两个子节点权值之和直到只剩下一个节点。请计算构建哈夫曼树后的带权路径长度之和即所有非叶子节点的权值之和这代表了编码后的总长度。输入格式第一行包含一个整数 N。第二行包含 N 个整数表示每个字符的频率。其中 1≤N≤1000频率不超过 10000。输出格式一个整数表示哈夫曼编码的总长度。输入样例在这里给出一组输入。例如4 1 2 3 4​输出样例在这里给出相应的输出。例如19​样例解释1 . 选1和2合并为3当前和3。集合变为{3, 3, 4}2 . 选3和3合并为6当前和369。集合变为{4, 6}3 . 选4和6合并为10当前和91019。集合变为{10}4 . 总长度为19。在写这个题之前还是学了一下哈夫曼是啥看以下总结//实现哈夫曼树 //啥是哈夫曼树 //1.哈夫曼树是一种树形结构它的特点是 //哈夫曼树是二叉树它的每个节点的权值是该节点的子树中所有节点权值的和。 //举个例子初始为[1,1,2,3,5,9],我们每次拿出最小的两个加和来构造二叉树 //一开始取最小的两个数即为11 //就是 2 // / \ 然后把这个两个数去掉把生成的2加入变成[2,2,3,5,9],继续构造 // 1 1 //继续 4 7 // / \ 同样的步骤现在是[4,3,5,9],继续就是 / \ // 2 2 3 4 //最后形成一个树 //在这里带权路径长度的定义为从根节点到叶子节点的权值之和即是WPL 叶子节点权值 × 路径长度之和带圈的是原初始里的数。 // 21 0 // / \ ↓ // 12 ⑨ 1 // / \ ↓ // 7 ⑤ 2 // / \ ↓ // 4 ③ 3 // / \ ↓ // 2 ② 4 // / \ ↓ // ① ① 5 //所以他的WPL为1*51*52*43*35*29*146. //因为我们每次取最小的两个数所以用优先队列来实现是最好的。 import java.util.PriorityQueue; // 哈夫曼树的节点类 // 实现 Comparable 接口用于优先队列中按权值自动排序小顶堆 class Node implements ComparableNode { public int weight; // 节点的权值频率 public Node left; // 左子节点 public Node right; // 右子节点 // 构造方法创建一个带权值的节点 public Node(int weight) { this.weight weight; } // 重写比较方法让优先队列按照权值从小到大排序 Override public int compareTo(Node o) { return weight - o.weight; // 升序排序小顶堆 } // 打印节点时显示权值 Override public String toString() { return Node{ weight weight }; } // 核心方法创建哈夫曼树 // 传入一个权值数组返回构建好的哈夫曼树的根节点 public static Node createHuffmanTree(int[] arr) { // 1. 创建优先队列最小堆自动把权值最小的节点放队首 PriorityQueueNode priorityQueue new PriorityQueue(); // 2. 将数组中所有权值变成节点加入优先队列 for (int i 0; i arr.length; i) { priorityQueue.add(new Node(arr[i])); } // 3. 循环合并每次取出两个最小的节点生成父节点 while (priorityQueue.size() 1) { // 取出权值最小的两个节点 Node left priorityQueue.poll(); Node right priorityQueue.poll(); // 父节点权值 两个子节点权值之和 Node parent new Node(left.weight right.weight); // 构建父子关系 parent.left left; parent.right right; // 把新的父节点放回队列 priorityQueue.add(parent); } // 4. 队列最后剩下的一个节点就是哈夫曼树的根节点 return priorityQueue.poll(); } // 打印哈夫曼编码 // 递归遍历哈夫曼树输出每个叶子节点对应的哈夫曼编码 // left - 0, right - 1 public static void printHuffmanCode(Node root, String code) { // 递归出口节点为空直接返回 if (root null) { return; } // 如果是叶子节点没有左右孩子输出它的编码 if (root.left null root.right null) { System.out.println(root.weight : code); return; // 叶子节点无需继续递归 } // 递归遍历左子树路径加 0 printHuffmanCode(root.left, code 0); // 递归遍历右子树路径加 1 printHuffmanCode(root.right, code 1); } }所以这个做一题就是要求WPL用优先队列求即可代码如下import java.io.*; import java.util.*; public class Main { public static void main(String[] args)throws IOException { BufferedReader br new BufferedReader(new InputStreamReader(System.in)); PrintWriter out new PrintWriter(new OutputStreamWriter(System.out)); StringTokenizer st; int n Integer.parseInt(br.readLine().trim()); PriorityQueueInteger heap new PriorityQueue();//利用小根堆排序 st new StringTokenizer(br.readLine().trim()); for (int i 0; i n; i) { int numInteger.parseInt(st.nextToken()); heap.offer(num); } int res 0; while (heap.size() 1) { //每次从中取两个最小的数 int a heap.poll(); int b heap.poll(); //加和为新节点 int sum a b; res sum; //弹出原有数后加入新数 heap.offer(sum); } out.println(res); out.flush(); out.close(); br.close(); } }所以相应的哈夫曼编码就是我记录一串字符中每个字符出现的个数将个数以权重加入哈夫曼树中形成的数字编码。最后总结一下其实学习一些经典题型还是我这个阶段的主要做法就是缺少思考题目做得少关于子数组的问题前面一直都是零碎的刷题学习并为有所总结现在总结的目的就是要整体化学习也希望大神多提提建议以后的学习还要更加深入才行。