- 博客(38)
- 收藏
- 关注
RSS订阅原创 PAT甲级1043、 Is It a Binary Search Tree
建树的方法就是找到根（第一个位置），然后在树的其他部分找到第一个大于或小于根的元素，这里BST的话就找大于的，因为BST左子树全小于根，镜像的话就是小于的，如果能建出来一棵，那么就是可行的，建不出来的话就说明不行。我没有想到什么特别好的思路，只能一边建树一边判断。1、叶子节点没有孩子，要注意怎么判断出来。2、如果一棵树都只有左子树。然后递归下去就可以了。
2025-02-09 21:44:12
857
原创 PAT甲级1053、 Path of Equal Weight
先给权重后给子节点，用链表的话需要二次操作才能建树，而且涉及到了ID，放在结构体里面肯定不合适，所以考虑到。然后另一个要点的话就是DFS或者说回溯算法，都差不多，去遍历这棵树寻找路径。本来没想写的，但是写完这个题快吃饭了，不知道干点什么，就来水一篇吧。这里的栈有点多余了，用一个vector代替的话应该会更好一点。另外说一下，总结点不过100，量级比较小，冗余的话也不要紧。
2025-02-08 11:58:12
1077
原创 543、二叉树的直径
在这个树中，根为4，最大直径不在4为根的树中，再看-3为根的树，结果等于-3为根的这棵树的左子树最大深度(3)加上右子树最大深度(3)如果不经过根的话，就只看左子树或者右子树，在某一个子树中直径一定等于它的左子树最大深度加上右子树最大深度。整体思路是一样的，但是比我想得少了不少次递归，通过一个私有属性来记录，再用返回值返回深度，挺好！也就是说，要寻找直径的话有两个信息需要传递，一个是当前求出的最大直径，一个是当前子树的深度。3 ，取路径 [4,2,1,3] 或 [5,2,1,3] 的长度。
2025-02-05 16:20:53
337
原创 104、二叉树的最大深度
写的有点麻烦了，本来想着自顶向下遍历去计算深度，结果有点难搞，快成**了。是指从根节点到最远叶子节点的最长路径上的节点数。深度广度优先搜索还是薄弱，没想到，还是得练。后来一看官方题解，感觉还是做麻烦了。弄了一下自底向上，还可以。
2025-02-05 09:58:30
212
原创 PAT甲级1052、Linked LIst Sorting
静态链表首先要求总的节点数量（地址）不能太大，这样才能定义一个大数组然后要求地址不连续，甚至是相当稀疏的最后是在指针链表不太方便做的时候可以用，比如说。
2025-02-04 23:08:49
1138
原创 PAT甲级1032、sharing
To store English words, one method is to use linked lists and store a word letter by letter. To save some space, we may let the words share the same sublist if they share the same suffix. For example, and are stored as showed in Figure 1.Figure 1You are
2025-02-04 22:23:51
508
原创 PAT甲级1093、Count PAT‘s
The string contains two 's as substrings. The first one is formed by the 2nd, the 4th, and the 6th characters, and the second one is formed by the 3rd, the 4th, and the 6th characters.Now given any string, you are supposed to tell the number of 's contain
2025-02-03 10:49:24
260
原创 PAT甲级1101、Quick Sort
这个题目一看上去就有动态规划的意思，用数组记录一个元素前的某种信息，以此来达到节省搜索的时间的目的。那么放两个数组来记录就行了，一个记之前最大的，一个记之后最小的，也就是前后都要遍历一遍。一个元素可以作为pivot，那么前面不可以有比它大的，后面不可以有比它小的。要注意的是N可能为0，没有元素给出，这时需要输出的是0，无元素。题中给的是N为positive integer，怎么会为0呢？测试点2是这个东西。我不知道是我理解的问题还是出题的问题。时间复杂度算是O(n)级别，挺好。
2025-02-02 23:04:44
856
原创 11、盛最多水的容器
我们要找最大的容积，所以要让容积变得尽可能大。无论是让左指针往右跑，还是让右指针往左跑，底边长都会变小，所以如果存在更大的容积的话，那么height一定会更大。在此情况下，容器能够容纳水（表示为蓝色部分）的最大值为 49。首先要双指针怎么跑，并向跑还是相向跑，这里我用了相向跑，因为最后的结果是最大容积，要让容积尽可能大。一个从前往后跑，一个从后往前跑，在这个题中，容积 = 最小height * 底边长。在选定双指针的情况下，最小height和底边长都能很好的确定，不说了。这一次非常顺利，一遍过，很好！
2025-01-31 17:18:31
147
原创 283、移动零
难绷，本来想用类似链表的方式，记录开始first和结束last的位置，让first移动，直到遇见last。这样就忽视了要把0放到最后，问题变成了将所有非零元素换到前面，而不是寻找左指针右边的第一个非零元素。假如左指针已经就位，右指针指向的为非零元素，那么需要交换。没想到在vector中，这个last并不是像指针那样不动的，在删除后last指向的内容竟然变了。思路是利用双指针，因为要保持数组中非零元素的相对顺序，所以都从第一个元素往后遍历。左指针指向零元素，右指针指向左指针后面的第一个非零元素，然后交换。
2025-01-31 16:54:26
234
原创 128、最长连续序列
因为每个元素最多被访问两次，for循环要去count，count在hash中是O(1)，所以每个元素一定会被访问一次，而while循环中是在遍历一个序列，因为一个元素只能存在于一个序列中，而且遍历是从序列的第一个元素开始的，所以一个序列只会被遍历一次，其中的元素也只会被访问一次。我一开始想效法动态规划，hash[i] = hash[i-1] + 1，但是在遍历的过程中只能遍历nums数组，而数组中的元素是无序的，所以这个递推式是不成立的。如果作为键的话，值只能是连续的最长序列长度(还有点像动态规划的)。
2025-01-17 21:51:53
523
原创 49、字母异位词分组
输出是一个又一个vector放到一个大的vector中，那么遍历hash去查找，显然hash中的值就得是这一个又一个vector了。出发点应该是输出中的vector（结构题数组）的形式，那么任务就是要把一些词分到同一组中，判断的根据/标准是同样的字母。那么hash中键是唯一的，所以使用到了字典序来统一。是由重新排列源单词的所有字母得到的一个新单词。键的问题解决了，那么值又放些什么呢？好吧，其实就是没做出来，要和它爆了！给你一个字符串数组，请你将。这就给了hash的使用特征。应该是键，而不会是值。
2025-01-15 22:38:05
358
原创 1001 A+B Format
那么关键是逗号的位置，在第i轮的时候，每隔三个数加个逗号，所以有i*3个数，有i-1个逗号。所以现在用str的length剪掉这些就是要加逗号的位置。整数肯定没办法处理，只能用字符串类型。
2025-01-13 22:15:30
312
原创 7-15 计算圆周率
根据下面关系式，求圆周率的值，直到最后一项的值小于给定阈值。2π=1+31+3×52!+3×5×73!+⋯+3×5×7×⋯×(2n+1)n!+⋯输入格式：输入在一行中给出小于1的阈值。输出格式：在一行中输出满足阈值条件的近似圆周率，输出到小数点后6位。输入样例：0.01输出样例：3.132157本来想着用函数来实现n!/(3*5*7...(2*n+1))的，但是最后输出的结果误差比较大，从第三位小数开始就有了问题，不明白是为什么？？？？（码不小心搞丢了
2022-01-31 09:39:33
1176
原创 7-4 BCD解密
BCD数是用一个字节来表达两位十进制的数，每四个比特表示一位。所以如果一个BCD数的十六进制是0x12，它表达的就是十进制的12。但是小明没学过BCD，把所有的BCD数都当作二进制数转换成十进制输出了。于是BCD的0x12被输出成了十进制的18了！现在，你的程序要读入这个错误的十进制数，然后输出正确的十进制数。提示：你可以把18转换回0x12，然后再转换回12。输入格式：输入在一行中给出一个[0, 153]范围内的正整数，保证能转换回有效的BCD数，也就是说这个整数转换成十六进制时不会出现A-F
2022-01-30 19:19:10
173
原创 7-2 然后是几点
有时候人们用四位数字表示一个时间，比如 1106 表示 11 点零 6 分。现在，你的程序要根据起始时间和流逝的时间计算出终止时间。读入两个数字，第一个数字以这样的四位数字表示当前时间，第二个数字表示分钟数，计算当前时间经过那么多分钟后是几点，结果也表示为四位数字。当小时为个位数时，没有前导的零，例如 5 点 30 分表示为 530；0 点 30 分表示为 030。注意，第二个数字表示的分钟数可能超过 60，也可能是负数。输入格式：输入在一行中给出 2 个整数，分别是四位数字表示的起始时间、以及
2022-01-30 19:10:48
90
原创 6-11 求自定类型元素序列的中位数
本题要求实现一个函数，求N个集合元素A[]的中位数，即序列中第⌊(N+1)/2⌋大的元素。其中集合元素的类型为自定义的ElementType。函数接口定义：ElementType Median( ElementType A[], int N );其中给定集合元素存放在数组A[]中，正整数N是数组元素个数。该函数须返回N个A[]元素的中位数，其值也必须是ElementType类型。裁判测试程序样例：#include <stdio.h>#define MAXN 10t
2022-01-29 15:40:22
1315
原创 6-10 阶乘计算升级版（高精度）
本题要求实现一个打印非负整数阶乘的函数。函数接口定义：void Print_Factorial ( const int N );其中N是用户传入的参数，其值不超过1000。如果N是非负整数，则该函数必须在一行中打印出N!的值，否则打印“Invalid input”。裁判测试程序样例：#include <stdio.h>void Print_Factorial ( const int N );int main(){ int N; sca
2022-01-28 18:01:30
224
原创 6-9 统计个位数字
本题要求实现一个函数，可统计任一整数中某个位数出现的次数。例如-21252中，2出现了3次，则该函数应该返回3。函数接口定义：int Count_Digit ( const int N, const int D );其中N和D都是用户传入的参数。N的值不超过int的范围；D是[0, 9]区间内的个位数。函数须返回N中D出现的次数。裁判测试程序样例：#include <stdio.h>int Count_Digit ( const int N, const int D
2022-01-28 12:05:37
941
原创 6-2 多项式求值 (15 分)
本题要求实现一个函数，计算阶数为n，系数为a[0] ... a[n]的多项式f(x)=∑i=0n(a[i]×xi) 在x点的值。函数接口定义：double f( int n, double a[], double x );其中n是多项式的阶数，a[]中存储系数，x是给定点。函数须返回多项式f(x)的值。裁判测试程序样例：#include <stdio.h>#define MAXN 10double f( int n, double a[], double x
2022-01-27 19:10:45
949
2
空空如也
空空如也
TA创建的收藏夹 TA关注的收藏夹
TA关注的人