给定二叉树非递归中序遍历出入栈的顺序，求这个二叉树的后序遍历。 关键是还原二叉树。 没必要真正还原，我们直接转变为后序遍历序列，我们也用一个堆栈模拟。 遇到一个push操作，我们把该节点放入堆栈，然后标记该节点是个新的节点，设置标签0 （0表示新， 1表示旧） 遇到一个pop操作，是该节点左孩子访问完了退回到该节点的情形，我们并不真正pop出去，我们把堆栈顶的元素设置标签1，表示现在这个节点在中序时应该已经出栈了，我们整准备访问它的右孩子节点。前提条件是：堆栈顶部的标签不是1， 如果顶部标签是1，我们应该先pop出去。 总结一下： 原始push就pus...

不太难，我出的题…… 给定一个正整数序列，再给一个正整数p, 选出最多选出多少个数，使得最小值不超过最大值的p倍？ 因为只考虑最小值和最大值，所以可以把原数列排序。  假设数组a[]都排好序了。 我们对起点i，循环找到最后一个满足条件的位置j >= i。 当i + 1的时候，注意j仍然有效，因为a[j] <= p * a[i] <= p * a[i + 1]，所以j没必要重新循环，而是从上一次的最后一个位置继续向后找就行了。 所以不算排序的话，对每个i找到j的时间复杂度是O(n)的，因为i, j都只循环了n次而已。 另外注意，判断...

简单题，给定两个字符串，问哪个键坏了。坏了的键，字母不会被打出来。数据保证合法。 所以我们可以直接比较，一个s，一个t,如果s和t对应字符不等，s的那个键一定坏了，注意这时t指针不动。 注意字母都转换为大写字母。 #include <cstdio> #include <cstring> #include <string> #include <cctype> using namespace std; bool mark[256]; char s[100],t[100]; int main() {     scanf("%...

简单题，给定每个人的分数，姓名，id，再给一个分数区间，按照分数递减的顺序输出这个分数区间的所有人。 题目告诉我们每个分数最多只有一个人，于是我们根本不用排序，直接用一个数组记录这个分数的人的id就好了——类似计数排序。 其实如果每个分数的人不只一个也没关系，可以用vector<int> grade[102]存每个分数的所有人。 另外不知道是不是所有查询的分数区间都在[0..100]内，所以我取了一个from = max(0, from), to = min(100, to); 代码： #include <cstring&gt...

不难，但很麻烦。用中文读一个数。 数不超过9位。 我是补足12位的，首位补0。 按照我们读数的方法，4位一级。 (xxxx)(yyyy)(zzzz) xxxx是亿 yyyy是万 zzzz是个，不用读。 话虽如此，细节很多。 首先，读4位数，先写好，要注意 零什么时候读，什么时候不读，什么时候读一个…… 只有第一次遇到0（前面非0），才读而且值读一个0。 读好4位数，我的算法是读3个4位数就好了。 但是仍然要注意0的问题。 全是0的时候，之前没读过东西就不读，否则要读一个0。 还有如果这个数&lt...

简单题，有理数（分数）求和。 主要掌握两个分数求和就行了， a / b + c / d = (a * d + b * c) / (b * d) 每次约分一下，求最大公约数(***)就好了。我保证了分母总是正数，分子任意…… 还有建议用long long因为乘法可能很大的。 最终输出是带分数，可能整数部分是0， 也可能分数部分是0，要详细判断一下。 代码： #include <cstdio> #include <cstring> #include <string> using namespace std...

其实这个题也不难，算作模拟题吧。给定若干个学校，若干个学生。每个学校有一定的招生名额，每个学生可以报一些志愿，志愿分先后，表示他想去的学校。规则： （1） 每个学生有两个成绩，根据平均分，和一门成绩对学生进行排序——平均分越高则学生越好，平均分相同，第一门课越高则越好，否则学生排名相同。这里需要说一句，其实按平均分排和按总分排是一样的，不用真的除以2。 （2） 每个学校有一定名额，按照学生志愿，优先录取好的学生，但是如果学校录取了某个学生，还有一个和他一样好的学生也报了这个学校，则学校也应该录取他，即使录取他会使人数已经超过了学校的名额。 （3） 学生按照志愿选取学校...

给了经销商，零售商，供应商的关系，其实就是一棵有根树，根节点售价已知，每下一层售价增加r%，这样我们可以知道每个叶节点（供应商）的售价，dfs即可。又知道每个叶节点要卖多少，所以乘一下累加就能得到最终总的收入。 我没有区分叶节点和中间节点，而是用了一个数组a，表示每个节点要卖多少，事实上非叶节点这个值是0，所以累加到总和叶没关系。 代码： #include <cstdio> #include <cstring> #include <string> #include <vector> using namespace std; ...

这个题我觉得也不难。给定微博上每个人的粉丝数，假设它发一条微博，所有粉丝都会转发，并且粉丝的粉丝也会转发……问L层之后有多少人转发，其实就是查询每个人的L级粉丝数。 如果A是B的粉丝，就连一条B到A的边，我们就有了一个有向图，原始问题变成了查询一个点距离不超过L的点有哪些了。 查询有多个，显然可以根据每个查询bfs L层……我采用了最暴力的做法，先用n^3的floyd算出任意两点间的最短路，对每个查询，枚举所有点，把距离不超过L的都输出就好了。 代码： #include <cstdio> #include <cstring> #incl...

关于hash的模拟，不难。首先hash的size需要自己确定，找到不小于m的第一个质数就可以了，质数判断用暴力判断，从2到sqrt(m)枚举因数就可以。 hash探测x采用看一下x % m,  (x + 1 ^ 2) % m, (x + 2 ^ 2) % m.... (x + (m - 1) ^ 2) % m, 第一个没有使用的位置来保存x，如果全占满了，没地方存x，输出"-"。 代码： #include <cstdio> #include <cstring> #include <string> using ...

简单题，就是排序问题。 n个队伍m个题目，每个队伍的每个题目有3种状态： （1） 没提交—— 不计入总分 （2） 提交但没通过编译——不计入总分 （3） 提交通过编译得到了一个分数 [0..p], 计入总分 对队伍排名，要求： （1） 至少提交并通过编译一个题目的队伍才出现在排名上——也就是说至少有一个情况（2）或者（3）的队伍 （2） 总分最高则排在前面，相同则完全对的题目也就是上面情况（3）越多排在前面，还相同队伍id小的排在前面 （3） 总分相同的队伍名次相同，这就需要维护一个名次值，只要出现不同的总分，才更新为（ 前面总分大于他的队伍数-...

众数问题，从m * n个数中找出出现多于一半的数——保证存在。 本质： 同时删掉两个不同的数，众数不变。 于是我们随便记录一个数x， 来一个数 y， 和x不同的话就把x ,y都扔了，相当于扔掉两个不同的数，和x相同的话，就把计数器加1。 所以操作简化为 （1） x出现次数的计数器加1 （2） x出现次数的计数器减1 #include <cstdio> #include <cstring> #include <string> using namespace std; int main() { int m,n,answ...

简单题，每k个元素一组翻转链表。链表给的形式比较有意思，PAT的题链表都如此给。就是地址、元素值（一般是整数）、下一个元素的地址或者-1表示空，其实和指针真正的指针没什么区别的。 做法也比较直接，注意如果长度对k取余数非0，最后那几个是不动的。 （1）先计算链表长度n （2）循环出最近k个元素，截断，得到一个长度恰好为k的链表，和剩余部分，注意维护好两部分的表头 （3） 翻转长度为k的链表 （4） 把（3）翻转的结果接到之前保存的结果上 （5） 转（2） （6） 如果有“尾巴”，接到之前的结果上。 关键问题，每次连接注意可能当前结果就是第一段，之...

简单题，字符串处理，把科学计数法转变为普通浮点数。 科学计数法是一位整数的标准形式，保证有E，并且带指数。可以先找到E，把E转变为空格，然后把指数读出来，如果指数是0，则把E之前的完整输出。 如果指数小于0，则一定是0.xxxx, 注意调整小数点，小数点后补0，输出即可。 如果指数大于0，则一定大于等于1，同样注意小数点，而且有可能最后没有小数点了，结尾还可能要补0。 请注意如果原来输入末尾有0，能不动就补动。 #include <cstdio> #include <cstring> #include <string> ...