最近写题记录和学习的总结

引用：PTAL1-103 整数的持续性

从任一给定的正整数 n 出发，将其每一位数字相乘，记得到的乘积为 n1​。以此类推，令 ni+1​ 为 ni​ 的各位数字的乘积，直到最后得到一个个位数 nm​，则 m 就称为 n 的持续性。例如 679 的持续性就是 5，因为我们从 679 开始，得到 6×7×9=378，随后得到 3×7×8=168、1×6×8=48、4×8=32，最后得到 3×2=6，一共用了 5 步。
本题就请你编写程序，找出任一给定区间内持续性最长的整数。

输入格式：

输入在一行中给出两个正整数 a 和 b（1≤a≤b≤10^9 且 (b−a)<10^3），为给定区间的两个端点。

输出格式：

首先在第一行输出区间 [a,b] 内整数最长的持续性。随后在第二行中输出持续性最长的整数。如果这样的整数不唯一，则按照递增序输出，数字间以 1 个空格分隔，行首尾不得有多余空格。

输入样例：

500 700

输出样例：

5

679 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; TreeMap<Integer, 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; } } List<Integer> ans = new ArrayList<>(); for (Map.Entry<Integer, 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(); } }

其实对于子数组的问题，之前总结的还不够深，所以我在这里重新总结一下：

1.普通最大子数组和：

这个我现在所会的方法就三种：①暴力解法，②前缀和+贪心，③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; cin>>n; vector<int> a(n+1); for (int i=1;i<=n;i++) cin>>a[i]; vector<int> b(n+1); b[0]=0; for (int i=1;i<=n;i++) b[i]=b[i-1]+a[i];//构建一个前缀和数组 int Max=b[1];//存储最大值，将它定为第一个元素 int Min=b[0];//存储最小值，将它定为0 for (int i=1;i<=n;i++) { Max=max(Max,b[i]-Min);//运用了贪心算法，计算当前前缀和减去最小值 Min=min(Min,b[i]);//存储当前最小值 } cout<<Max<<endl; return 0; } //解法二：kadane算法 #include <bits/stdc++.h> using namespace std; int main() { ios::sync_with_stdio(false); cin.tie(nullptr); int n; cin>>n; vector<int> dp; for (int i=0;i<n;i++) { int num; cin>>num; dp.push_back(num); } int Max=dp[0]; for (int i=1;i<n;i++) { dp[i]=max(dp[i],dp[i-1]+dp[i]);//这一步就是我前面的最大值加现在的数和现在的数比较, //就是如果说我[2,-1,-9,4,5],我到数字4的时候， ////如果加前面的一段就会负的更多，那我就要选择不加前面的一段，就是窗口后移到4的地方重新开始计算 Max=max(Max,dp[i]);//然后再不断更新我的最大值 } cout<<Max<<endl; return 0; }

2.和不大于目标值k的最长子数组：

代码和思路如下：

//如果全是正数，就用滑动窗口，代码如下： #include <bits/stdc++.h> using namespace std; int main() { ios::sync_with_stdio(false); cin.tie(nullptr); int n,k; cin>>n>>k; vector<int> a(n); for (int i=0;i<n;i++) cin>>a[i]; int left=0;//滑动窗口的左边界 int sum=0,Max=0; for (int right=0;right<n;right++) { sum+=a[right];//窗口右边界向右移动 while(sum > k) {//窗口内的和超过了K sum-=a[left];//窗口左边界向右移动，就是吐出来左边的数 left++;//让左指针向右移动，减小窗口大小 } Max=max(Max,right-left+1);//更新最大长度 } cout<<Max<<endl; return 0; } //如果有负数和0 //这个为啥就不能用滑动窗口了呢？ //举个例子[3, -2, 5, -1],k=5，就是说我们的左指针先不动，右指针一直右移， //找到的第一个满足条件的是[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; vector<int> a(n); for (int i=0; i<n; i++) cin >> a[i]; unordered_map<int, int> mp; mp[0] = -1; //用前缀和 0 出现在 -1 位置 int sum = 0, Max = 0; for (int i=0; i<n; 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，和最大的子数组 //单调队列+前缀和 //第一我们在看前缀和模版的时候，其实就知道前缀和可以用来多次查询[l+1,r]区间的子数组的加和。 //所以说我们要求长度<=k的子数组和的最大值，本质上我们查询区间(限制条件是l-r<=k)的加和最大值 //我们可以向kadane算法一样，就是定一个后缀，然后看以后缀为结尾的窗口的加和最大值，然后更新最大值就可以了 //就好像洛谷P1886滑动窗口/单调队列差不多的，我从队尾弹出一个数，以他为窗口的结尾，当然同时要判断窗口的长度 //然后和上面说的一样，更新最大值就行了 #include <bits/stdc++.h> using namespace std; int main() { int n, k; cin >> n >> k; vector<int> a(n + 1); for (int i = 1; i <= n; i++) { cin >> a[i]; } vector<long long> b(n + 1, 0); for (int i = 1; i <= n; i++) { b[i] = b[i-1] + a[i];//创建一个前缀和数组 } deque<int> 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; pair<int, int> getMaxMin(vector<int>& 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(vector<int>& 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; cin>>n; vector<int> a(n); for (int i=0;i<n;i++) cin>>a[i]; cout<<maxSubarraySumCircular(a)<<endl; return 0; }

5.求子数组乘积的最大值

代码和思路如下：

//实现乘积最大子数组 //事实上我在写这个题目的时候，我还是想到了kadane算法，本质上我就是想将它加和求最大值的思路移到乘法来 //就是我定义一个mul=a[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; cin>>n; vector<int> a(n); for (int i=0;i<n;i++) cin>>a[i]; int Max=a[0]; int Min=a[0]; int res=a[0]; for (int i=1;i<n;i++) { int tempMax=Max; int tempMin=Min; Max=max(max(tempMax*a[i],tempMin*a[i]),a[i]); Min=min(min(tempMax*a[i],tempMin*a[i]),a[i]); res=max(res,Max); } cout<<res<<endl; return 0; }

引用：PTA算法1-7~9 连续子序列最大和:

给定 n 个整数组成的序列 { a1​,a2​,⋯,an​ }，“连续子序列”被定义为 { ai​,ai+1​,⋯,aj​ }，其中 1≤i≤j≤n。“连续子序列最大和”则被定义为所有连续子序列元素的和中最大者。例如给定序列 { -2, 11, -4, 13, -5, -2 }，其连续子序列 { 11, -4, 13 } 有最大的和 20。请编写程序，计算给定整数序列的连续子序列最大和。

本题旨在测试各种不同的算法在各种数据情况下的表现。各组测试数据特点如下：

• 数据 0~6：测试基本正确性；
• 数据 7：10^3 个随机整数；
• 数据 8：10^4 个随机整数；
• 数据 9：10^5 个随机整数。

输入格式:

输入第一行给出正整数 n (≤10^5)；第二行给出 n 个整数，绝对值均不超过 100，其间以空格分隔。

输出格式:

在第一行中输出连续子序列最大和，第二行输出该子序列首尾的数组下标（从 0 开始），以 1 个空格分隔。若解不唯一，则输出最小的数组下标（如样例所示）。
注意：如果序列中所有整数皆为零或负数，则取空子列的结果是最大的，为 0；此时空子序列数组首尾的下标均为 -1。

输入样例:

10

-10 2 2 3 4 -5 -23 4 7 -21

输出样例:

11

1 4

这个题多出来它子数组的端点输出，联系老登算法(kadane算法），在前面因为有负数让加和小于当前末尾值了的时候，我就把子数组的左边界到当前位置，持续记录就可，代码如下：

#include <bits/stdc++.h> using namespace std; int main() { ios::sync_with_stdio(false); cin.tie(nullptr); int n; cin >> n; vector<int> 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，当前和=3+6=9。集合变为{4, 6}
3 . 选4和6，合并为10，当前和=9+10=19。集合变为{10}
4 . 总长度为19。

在写这个题之前，还是学了一下哈夫曼是啥，看以下总结：

//实现哈夫曼树 //啥是哈夫曼树？ //1.哈夫曼树是一种树形结构，它的特点是： //哈夫曼树是二叉树，它的每个节点的权值是该节点的子树中所有节点权值的和。 //举个例子：初始为[1,1,2,3,5,9],我们每次拿出最小的两个加和来构造二叉树 //一开始取最小的两个数，即为1，1 //就是： 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*5+1*5+2*4+3*3+5*2+9*1=46. //因为我们每次取最小的两个数，所以用优先队列来实现是最好的。 import java.util.PriorityQueue; // 哈夫曼树的节点类 // 实现 Comparable 接口，用于优先队列中按权值自动排序（小顶堆） class Node implements Comparable<Node> { 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. 创建优先队列（最小堆），自动把权值最小的节点放队首 PriorityQueue<Node> 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()); PriorityQueue<Integer> heap = new PriorityQueue<>();//利用小根堆排序 st= new StringTokenizer(br.readLine().trim()); for (int i = 0; i < n; i++) { int num=Integer.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(); } }

所以相应的哈夫曼编码就是我记录一串字符中每个字符出现的个数，将个数以权重加入哈夫曼树中，形成的数字编码。

最后，总结一下，其实学习一些经典题型还是我这个阶段的主要做法，就是缺少思考，题目做得少，关于子数组的问题，前面一直都是零碎的刷题学习，并为有所总结，现在总结的目的就是要整体化学习，也希望大神多提提建议，以后的学习还要更加深入才行。