运营商活动
题目描述
小明每天的话费是1元，运营商做活动，手机每充值K元就可以获赠1元，一开始小明充值M元，问最多可以用多少天？ 注意赠送的话费也可以参与到奖励规则中
输入
输入包括多个测试实例。每个测试实例包括2个整数M，K（2<=k<=M<=1000)。M=0，K=0代表输入结束。
输出
对于每个测试实例输出一个整数，表示M元可以用的天数。
样例输入
2 2
4 3
13 3
0 0
样例输出
3
5
19
提示
注意第三组数据「13 3」结果为什么是19呢， 13/3=4，获得4元奖励。 13%3=1，还剩下1元，4+1=5，5元继续参加奖励规则。 5/3=1，获得1元奖励。 5%3=2，剩下2元，1+2=3，3元继续参与奖励规则。 3/3=1，获得1元奖励。 3%3=0，剩下0元，1+0=1。 1元不能参与剩下奖励。所以一共可以使用的天数是 13+4+1+1=19
代码
在每次充值后，小明会获得额外的1元话费，因此他的总话费是充值金额 M 加上额外的话费。如果我们把每次充值后获得的额外话费也视为一次充值，那么小明每次充值后都会获得额外的 k 元话费。
假设小明一开始充值了 M 元钱，那么他会获得 M / k 元额外话费，以及 M % k 元剩余的钱。其中，M % k 就表示小明无法凑成一次充值的剩余金额。
接着，小明可以利用获得的 M / k 元额外话费再次充值，于是他又会获得 (M / k) / k 元额外话费和 (M / k) % k 元剩余的钱。以此类推，小明可以一直通过充值来获得额外的话费。每次充值所获得的额外话费都是上一次剩余的钱除以 k 得到的。
因此，我们可以用一个 while 循环来模拟小明不断充值的过程，直到无法再获得额外的话费为止。在每次循环中，我们需要计算出当前剩余的钱数 count（包括上一轮的剩余钱数和赠送的额外话费），并将其除以 k 得到额外的话费和剩余的钱数（即下一轮的 M 和 M % k）。最终，小明的总话费就是所有充值所获得的额外话费和剩余话费之和。
因此，m % k 代表了小明一开始充值后剩余的钱数，即无法凑成一次充值的金额，也可以看作是额外话费的一部分。
为什么要凑成一次充值的金额？
在题目中，每充值 K 元就可以获赠 1 元话费，因此，当小明的钱数不能凑成一次充值的金额时，他就无法获得额外的话费了。为了最大化利用每次充值可以获得的额外话费，小明需要确保每次充值的金额都是 K 的整数倍。这样，他就可以获得尽可能多的额外话费，从而最大化使用他的钱数。
例如，假设小明一开始充值了 20 元钱，K=5，那么他可以分别在第 5、10、15、20 天充值，每次充值 5 元，这样他就可以获得 4 元额外话费，总共获得 24 元话费，可以用于 24 天。
如果他在第 4 天充值了 4 元，那么他只能获得 3 元额外话费，总共获得 23 元话费，只能用于 23 天。因此，为了最大化使用他的钱数，小明需要确保每次充值的金额都是 K 的整数倍，也就是凑成一次充值的金额。
#include<iostream>
using namespace std;
int main(){
int m, k;
while(cin >> m >> k){
if(m == 0 && k == 0) break;
int sum = m + m / k;//可以得到的总话费
int extra = m / k + m % k;//额外话费包括：送的+充值时不够K元剩下的
while(extra / k != 0){
sum += extra / k;
extra = extra / k + extra % k;
}
cout << sum << endl;
}
}
简单来说就是：我现在有 M 元，但是因为每充 K 元就送1元话费，所以我要把 M 元尽量分 M/K 次来充，这样每次我就能额外获得 M/K 元
而无法除完的部分，就是剩余话费extra（送的+充值时不够K元剩下的）
然后我们拿剩的话费继续充值，还是以除K的方式充，每次能得到的额外话费就是 extra/K，加到总话费中，直到没有额外话费就结束
打印图形
打印数字图形
题目描述
先要求你从键盘输入一个整数n（1<=n<=9），打印出指定的数字图形。
输入
输入包含多组测试数据。每组输入一个整数n（1<=n<=9）。
输出
对于每组输入，输出指定的数字图形。
注意：每行最后一个数字后没有任何字符。
样例输入
5
样例输出
1
121
12321
1234321
123454321
1234321
12321
121
1
输入输出知识点
这里考察的是输出的技巧
像上面这种图形可以分成上下两部分进行打印
以上半部分为例，假设n = 3，应该怎么打印？
上半部分是由空格、递增的数、递减的数这三部分组成的，分别打印即可。打印时通过循环控制，优先考虑空格
先观察。n为3时，第一行的空格有2个，递增的数有一个，递减的没有；
以此类推，再通过两次for循环控制打印元素的个数（做的时候画图对照就知道该怎么设置循环初始值了）
注意，这只是打印，不要考虑指针会不会重叠，打印东西的时候只需要考虑打几个就行
代码
#include<iostream>
using namespace std;
void printTop(int n){
for(int i = 1; i <= n; ++i){
for(int j = 1; j <= n - i; ++j){//打印空格
cout << " ";
}
for(int j = 1; j <= i; ++j){//打印递增数字
cout << j;//递增肯定从小到大
}
for(int j = i - 1; j >= 1; --j){//打印递减数字
cout << j;//递减肯定从大到小（基于此再去想怎么控制这个数以满足规则）
}
cout << endl;//记得换行
}
}
void printDown(int n){//逻辑一样，只是i的初始值需要修改为从大到小
for(int i = n - 1; i >= 1; --i){
for(int j = 1; j <= n - i; ++j){
cout << " ";
}
for(int j = 1; j <= i; ++j){
cout << j;
}
for(int j = i - 1; j >= 1; --j){
cout << j;
}
cout << endl;
}
}
int main(){
int n;
while(cin >> n){
if(n < 1 || n > 9) cout << "error" << endl;
printTop(n);
printDown(n);
}
}
镂空三角形
题目描述
把一个字符三角形掏空，就能节省材料成本，减轻重量，但关键是为了追求另一种视觉效果。在设计的过程中，需要给出各种花纹的材料和大小尺寸的三角形样板，通过电脑临时做出来，以便看看效果。
输入
每行包含一个字符和一个整数n(0<n<41)，不同的字符表示不同的花纹，整数n表示等腰三角形的高。显然其底边长为2n-1。如果遇到@字符，则表示所做出来的样板三角形已经够了。
输出
每个样板三角形之间应空上一行，三角形的中间为空。行末没有多余的空格。每条结果后需要再多输出一个空行。
样例输入
X 2
A 7
@
样例输出
X
XXX
A
A A
A A
A A
A A
A A
AAAAAAAAAAAAA
输入输出知识点
“打印数字图形”的升级版
还是要遵循分别打印空格和字符的逻辑，如果不清楚要打印多少，就根据示例中每行空格和字符的个数来推导
做的时候记得画图
代码
#include<iostream>
using namespace std;
void printSpace(int n){
for(int i = 0; i < n; ++i) cout << " ";
}
void printChar(int n, char a){
for(int i = 0; i < n; ++i) cout << a;
}
int main(){
char edge;
int n;
while(cin >> edge){
if(edge == '@') break;
cin >> n;
if(n < 0 || n > 41) cout << "error" << endl;
if(n == 1) cout << edge << endl;
for(int i = 1; i <= n - 1; ++i){
printSpace(n - i);//打印空格
if(i == 1){
cout << edge;
}else{
cout << edge;
printSpace(2 * i - 3);//打印中间的空格
cout << edge;
}
cout << endl;
}
if(n > 1){//当n大于1就要打印次变底边
printChar(2 * n - 1, edge);
cout << endl;
}
cout << endl;
}
}
处理n组数据输入
句子缩写
题目描述
输出一个词组中每个单词的首字母的大写组合。
输入
输入的第一行是一个整数n，表示一共有n组测试数据。（输入只有一个n，没有多组n的输入）
接下来有n行，每组测试数据占一行，每行有一个词组，每个词组由一个或多个单词组成；每组的单词个数不超过10个，每个单词有一个或多个大写或小写字母组成；
单词长度不超过10，由一个或多个空格分隔这些单词。
输出
请为每组测试数据输出规定的缩写，每组输出占一行。
样例输入
1
ad dfa fgs
样例输出
ADF
提示
注意：单词之间可能有多个空格
输入输出知识点
1、演示了怎么把一个小写字符转换为大小
用ASCII码
2、演示了如何处理n组数据输入
在循环外用cin接收n，然后在while中n--
3、字符串输入后会带有一个回车，需要处理掉
用tmp = getchar();处理
代码
#include<iostream>
using namespace std;
char char2Capital(char& c){ // 小写变大写
if(c >= 'a' && c <= 'z') c -= 32;
return c;
}
int main(){
int n;
string res, s;
cin >> n;
char tmp;
tmp = getchar(); // 吸收一个回车，因为输入n之后，要输入一个回车
while(n--){//不能--n
res = "";
getline(cin, s);
res += char2Capital(s[0]);
for(int i = 1; i < s.size() - 1; ++i){
if(s[i] == ' ' && s[i + 1] != ' '){
res += char2Capital(s[i + 1]);
}
}
cout << res << endl;
}
}
神秘字符
题目描述
考古学家发现墓碑上有神秘的字符。经过仔细研究，发现原来这是开启古墓入口的方法。
墓碑上有2行字符串，其中第一个串的长度为偶数，现在要求把第2个串插入到第一个串的正中央，如此便能开启墓碑进入墓中。
输入
输入数据首先给出一个整数n，表示测试数据的组数。（整个输入中，只有一个n）
然后是n组数据，每组数据2行，每行一个字符串，长度大于0，小于50，并且第一个串的长度必为偶数。
输出
请为每组数据输出一个能开启古墓的字符串，每组输出占一行。
样例输入
2
asdf
yu
rtyu
HJK
样例输出
asyudf
rtHJKyu
输入输出知识点
1、在获取两个字符串输入时，需要使用一个char变量接收其后的回车键
具体就是
char tmp;
...
tmp = getchar();
代码
#include<iostream>
#include<string>
using namespace std;
int main(){
int n;
char tmp;
cin >> n;
string a, b;
while(n--){
cin >> a;
tmp = getchar();
cin >> b;
string res = "";
for(int i = 0; i < a.size() / 2; ++i){//遍历，将a的前半部分加到res中
res += a[i];
}
res += b;
for(int i = a.size() / 2; i < a.size(); ++i){//处理后半部分
res += a[i];
}
cout << res << endl;
}
}
位置互换
题目描述
给定一个长度为偶数位的字符串，请编程实现字符串的奇偶位互换。
输入
输入包含多组测试数据。
输入的第一行是一个整数n，表示有测试数据。（整个输入中，只有一个n）
接下来是n组测试数据，保证串长为偶数位(串长<=50)。
输出
请为每组测试数据输出奇偶位互换后的结果，每组输出占一行。
样例输入
2
0aa0
bb00
样例输出
a00a
bb00
代码
#include<iostream>
#include<string>
using namespace std;
void swap(char &a, char &b) { // 交换两个字符串
char tmp = a;
a = b;
b = tmp;
}
int main(){
int n;
string s;
cin >> n;
while(n--){
cin >> s;
// for(int l = 0, r = s.size() - 1; l < r; l++, r--){//是相邻奇偶位交换
// swap(s[l], s[r]);
// }
for (int i = 0; i < s.size() - 1; i += 2) { // 在s字符串上原地修改
swap(s[i], s[i + 1]);
}
cout << s << endl;
}
}
出栈合法性
题目描述
已知自然数1，2，...，N（1<=N<=100）依次入栈，请问序列C1，C2，...，CN是否为合法的出栈序列。
输入
输入包含多组测试数据。
每组测试数据的第一行为整数N（1<=N<=100），当N=0时，输入结束。
第二行为N个正整数，以空格隔开，为出栈序列。
输出
对于每组输入，输出结果为一行字符串。
如给出的序列是合法的出栈序列，则输出Yes，否则输出No。
样例输入
5
3 4 2 1 5
5
3 5 1 4 2
0
样例输出
Yes
No
代码
使用一个vector接收输入的数组，方法跟前面的类似
创建一个栈，使用for将自然数1，2，...，N（1<=N<=100）模拟加入栈
同时比较当前的栈顶元素是否与vector中对应下标的一致，一致就弹出并移动索引
#include<iostream>
#include<vector>
#include<stack>
using namespace std;
int main(){
int n;
vector<int> nums(105, 0);
while(cin >> n){
if(n == 0) break;
for(int i = 0; i < n; ++i) cin >> nums[i];
int index = 0;
stack<int> st;
for(int i = 1; i <= n; ++i){
st.push(i);
while(!st.empty() && st.top() == nums[index]){
st.pop();
index++;
}
}
if(st.empty() && index == n) cout << "Yes" <<endl;
else cout << "No" <<endl;
}
}
牛牛出入圈
描述
假设有一群牛要依次入圈和出圈，牛的编号是唯一的且不重复。给定两个牛的序列 enter 和 leave，它们分别表示牛的入圈顺序和出圈顺序。判断是否存在一种操作顺序，使得牛按照给定的入圈和出圈顺序依次进入和离开圈子。如果存在这样的操作顺序，则返回 true，否则返回 false。
注：牛圈狭长，只能先进入的牛必须等后进入的牛出圈后才能出圈。
示例1
输入：
[1, 2, 3, 4],[2, 1, 4, 3]
返回值：
true
代码
这题就是检查出入栈的合法性，不同的是，这这里要使用两个指针leaveIndex和enterIndex（从1开始，因为一开始需要先把enter的第一个元素加入栈中）来控制进出栈的顺序
先遍历入栈数组enter，将遍历元素压栈。过程中不断比较栈顶元素与leave中leaveIndex下标元素是否相等
若相等，弹出当前栈顶元素，移动leaveIndex指针；当leaveIndex等于leave数组长度时就返回true
若不相等，继续将enter中元素压栈，直到压完所有元素，循环结束；
此时，如果栈中还剩元素，那么将其依次出栈并与当前leave中leaveIndex下标元素比较，相等就弹出
如果有一个不相等即返回false；
当栈中元素弹空，则返回true
class Solution {
public:
bool validateCowCircle(vector<int>& enter, vector<int>& leave) {
// write code here
stack<int> st;
int leaveIndex = 0;
st.push(enter[0]);
int enterIndex = 1;
while(true){//一直往栈中添加enter内的元素，并不断判断，如果当前栈顶元素等于leave中leaveIndex下标位置元素，弹出
if(!st.empty() && st.top() == leave[leaveIndex]){
st.pop();
leaveIndex++;
if(leaveIndex == leave.size()) return true;
}else{//否则继续往栈里压入enter元素
st.push(enter[enterIndex]);
enterIndex++;
if(enterIndex == enter.size()) break;
}
}
//处理完压栈过程中的相同元素后，将栈中元素全部弹出，看看是否满足leave的顺序
while(!st.empty()){
if(st.top() == leave[leaveIndex]) {
st.pop();
leaveIndex++;
}else{
return false;
}
}
return true;
}
};
ACM中链表的基本操作
输入
输入数据只有一组，第一行有n+1个整数，第一个整数是这行余下的整数数目n，后面是n个整数。
这一行整数是用来初始化列表的，并且输入的顺序与列表中的顺序相反，也就是说如果列表中是1、2、3那么输入的顺序是3、2、1。
第二行有一个整数m，代表下面还有m行。每行有一个字符串，字符串是“get”，“insert”，“delete”，“show”中的一种。
如果是“get”，代表获得第a个元素。（a从1开始计数）
如果是“delete”，代表删除第a个元素。（a从1开始计数）
如果是“insert”，则其后跟着两个整数a和e，代表在第a个位置前面插入e。（a从1开始计数）
“show”之后没有正数，直接打印链表全部内容。
输出
如果获取成功，则输出该元素；
如果删除成功，则输出“delete OK”；
如果获取失败，则输出“get fail”
如果删除失败，则输出“delete fail”
如果插入成功，则输出“insert OK”，否则输出“insert fail”。
如果是“show”，则输出列表中的所有元素，如果列表是空的，则输出“link list is empty”
注：所有的双引号均不输出。
样例输入
3 3 2 1
21
show
delete 1
show
delete 2
show
delete 1
show
delete 2
insert 2 5
show
insert 1 5
show
insert 1 7
show
insert 2 5
show
insert 3 6
show
insert 1 8
show
get 2
样例输出
1 2 3
delete OK
2 3
delete OK
2
delete OK
Link list is empty
delete fail
insert fail
Link list is empty
insert OK
5
insert OK
7 5
insert OK
7 5 5
insert OK
7 5 6 5
insert OK
8 7 5 6 5
7
提示
初始化链表的元素是倒序的，这个使用题目中创建列表的方法（从头部插入）就可以了。
代码
下面为标答，我自己写的时候虽然都写出来了，但是总是解答错误
主要思路就是定义链表节点，然后直接按照以前的做法，依次实现链表获取指定节点、头插、尾插、指定位置插入、删除指定节点即可，最后根据题目的具体题意再调用各函数来实现所需的功能
#include<iostream>
using namespace std;
// 定义链表节点结构体
struct LinkedNode {
int val;
LinkedNode* next;
LinkedNode(int val):val(val), next(nullptr){}
};
int _size = 0;
LinkedNode* _dummyHead = new LinkedNode(0); // 这里定义的头结点 是一个虚拟头结点，而不是真正的链表头结点
// 获取到第index个节点数值，如果index是非法数值直接返回-1， 注意index是从0开始的，第0个节点就是头结点
int get(int index) {
if (index > (_size - 1) || index < 0) {
return -1;
}
LinkedNode* cur = _dummyHead->next;
while(index--){ // 如果--index 就会陷入死循环
cur = cur->next;
}
return cur->val;
}
// 在链表最前面插入一个节点，插入完成后，新插入的节点为链表的新的头结点
void addAtHead(int val) {
LinkedNode* newNode = new LinkedNode(val);
newNode->next = _dummyHead->next;
_dummyHead->next = newNode;
_size++;
}
// 在链表最后面添加一个节点
void addAtTail(int val) {
LinkedNode* newNode = new LinkedNode(val);
LinkedNode* cur = _dummyHead;
while(cur->next != nullptr){
cur = cur->next;
}
cur->next = newNode;
_size++;
}
// 在第index个节点之前插入一个新节点，例如index为0，那么新插入的节点为链表的新头节点。
// 如果index 等于链表的长度，则说明是新插入的节点为链表的尾结点
// 如果index大于链表的长度，则返回空
// 如果index小于0，则在头部插入节点
int addAtIndex(int index, int val) {
if(index > _size) return -1;
if(index < 0) return -1;
LinkedNode* newNode = new LinkedNode(val);
LinkedNode* cur = _dummyHead;
while(index--) {
cur = cur->next;
}
newNode->next = cur->next;
cur->next = newNode;
_size++;
return 0;
}
// 删除第index个节点，如果index 大于等于链表的长度，直接return，注意index是从0开始的
int deleteAtIndex(int index) {
if (index >= _size || index < 0) {
return -1;
}
LinkedNode* cur = _dummyHead;
while(index--) {
cur = cur ->next;
}
LinkedNode* tmp = cur->next;
cur->next = cur->next->next;
delete tmp;
//delete命令指示释放了tmp指针原本所指的那部分内存，
//被delete后的指针tmp的值（地址）并非就是NULL，而是随机值。也就是被delete后，
//如果不再加上一句tmp=nullptr,tmp会成为乱指的野指针
//如果之后的程序不小心使用了tmp，会指向难以预想的内存空间
tmp=nullptr;
_size--;
return 0;
}
// 打印链表
int printLinkedList() {
LinkedNode* cur = _dummyHead;
if (cur->next == nullptr) return -1;
while (cur->next != nullptr) {
cout << cur->next->val << " ";
cur = cur->next;
}
cout << endl;
return 0;
}
int main() {
int n, a, m, t, z;
string s;
cin >> n;
LinkedNode* head = nullptr;
while (n--) {
cin >> a;
addAtHead(a);
}
cin >> m;
while (m--) {
cin >> s;
if (s == "show") {
if (printLinkedList() == -1) cout << "Link list is empty" << endl;
}
if (s == "delete") {
cin >> t;
// 本题的删除索引是从1开始，函数实现是从0开始，所以这里是 t - 1
if (deleteAtIndex(t - 1) == -1) cout << "delete fail" << endl;
else cout << "delete OK" << endl;
}
if (s == "insert") {
cin >> t >> z;
if (addAtIndex(t - 1, z) == -1) cout << "insert fail" << endl;
else cout << "insert OK" << endl;
}
if (s == "get") {
cin >> t;
int getValue = get(t - 1);
if (getValue == -1) cout << "get fail" << endl;
else cout << getValue << endl;
}
}
}
构造单链表并反转
题目描述
根据一个整数序列构造一个单链表，然后将其反转。
例如：原单链表为 2 3 4 5 ，反转之后为5 4 3 2
输入
输入包括多组测试数据，每组测试数据占一行，第一个为大于等于0的整数n，表示该单链表的长度，后面跟着n个整数，表示链表的每一个元素。整数之间用空格隔开
输出
针对每组测试数据，输出包括两行，分别是反转前和反转后的链表元素，用空格隔开
如果链表为空，则只输出一行，list is empty
样例输入
5 1 2 3 4 5
0
样例输出
1 2 3 4 5
5 4 3 2 1
list is empty
提示
本题用数组，也是可有过的，输入一遍数组，然后倒叙输出。不过建议大家用本题来链表操作
代码
技巧点在于，如何处理输入的链表数据，如何存放
实际上处理这种输入我们只需要两个变量就可以了，一个是n，用于判断我们应该接收多少个节点值；另一个是nodeVal，用于循环接收输入的节点值，并直接用来构造链表。
#include<iostream>
using namespace std;
struct ListNode{
int val;
ListNode* next;
ListNode(int val): val(val), next(nullptr){}
};
ListNode* reverseList(ListNode* head){//双指针法
ListNode* pre = nullptr;
ListNode* cur = head;
while(cur){
ListNode* tmp = cur->next;
cur->next = pre;
pre = cur;
cur = tmp;
}
return pre;
}
void printListNode(ListNode* head){
ListNode* cur = head;
while(cur != nullptr){
cout << cur->val << ' ';
cur = cur->next;
}
cout << endl;
}
int main(){
int n, nodeVal;
ListNode* dummy = new ListNode(0);
while(cin >> n){
if (n == 0) {
cout << "list is empty" << endl;
continue;
}
ListNode* cur = dummy;
while(n--){
cin >> nodeVal;
ListNode* node4add = new ListNode(nodeVal);
cur->next = node4add;
cur = cur->next;
}
printListNode(dummy->next);
printListNode(reverseList(dummy->next));
}
}
删除单链表中的重复数据
题目描述
根据一个递增的整数序列构造有序单链表，删除其中的重复元素
输入
输入包括多组测试数据，每组测试数据占一行，第一个为大于等于0的整数n，表示该单链表的长度，后面跟着n个整数，表示链表的每一个元素。整数之间用空格隔开
输出
针对每组测试数据，输出包括两行，分别是删除前和删除后的链表元素，用空格隔开
如果链表为空，则只输出一行，list is empty
样例输入
5 1 2 3 4 5
5 1 1 2 2 3
0
样例输出
1 2 3 4 5
1 2 3 4 5
1 1 2 2 3
1 2 3
list is empty
代码
题目只是要一个输出，所以没有必要真的去删除某个节点，只需要在打印时跳过就行
#include<iostream>
using namespace std;
struct ListNode{
int val;
ListNode* next;
ListNode(int val): val(val), next(nullptr){}
};
// ListNode* removeDuplicate(ListNode* head){
// ListNode* cur = head;
// while(cur){
// ListNode* tmp = cur;
// cur = cur->next;
// if(cur->val == tmp->val){
// cur = tmp;
// cur->next = cur->next->next;
// }
// }
// return head;
// }
// 过滤掉重复元素输出，不用真的删除
void removeDuplicate(ListNode* head) {
ListNode* cur = head;
while (cur != nullptr && cur->next != nullptr) {
if (cur->val != cur->next->val) cout << cur->val << " ";
cur = cur->next;
}
cout << cur->val << " ";//最后一个节点不满足while没被输出，这里补上
cout << endl;
}
void printListNode(ListNode* head){
ListNode* cur = head;
while(cur){
cout << cur->val << " ";
cur = cur->next;
}
cout << endl;
}
int main(){
int n, nodeVal;
ListNode* dummy = new ListNode(0);
while(cin >> n){
if (n == 0) {
cout << "list is empty" << endl;
continue;
}
ListNode* cur = dummy;
while(n--){
cin >> nodeVal;
ListNode* node4add = new ListNode(nodeVal);
cur->next = node4add;
cur = cur->next;
}
printListNode(dummy->next);
//去重
removeDuplicate(dummy->next);
}
}
ACM构造二叉树
题目描述
给你一棵二叉树的前序遍历和中序遍历结果，要求你写出这棵二叉树的后序遍历结果。
输入
输入包含多组测试数据。每组输入包含两个字符串，分别表示二叉树的前序遍历和中序遍历结果。每个字符串由不重复的大写字母组成。
输出
对于每组输入，输出对应的二叉树的后续遍历结果。
样例输入
DBACEGF ABCDEFG
BCAD CBAD
样例输出
ACBFGED
CDAB
代码
#include <iostream>
#include <unordered_map>
#include <string>
using namespace std;
// 定义二叉树节点结构
struct TreeNode {
char val;
TreeNode* left;
TreeNode* right;
TreeNode(int val) : val(val), left(nullptr), right(nullptr) {}
};
TreeNode* buildTreeRecursive(string& preorder, string& inorder,
int preStart, int inStart, int inEnd,
unordered_map<int, int>& indexMap) {
if (preStart > preorder.size() - 1 || inStart > inEnd) {
return nullptr;
}
// 根据前序遍历结果获取当前子树的根节点值
char rootValue = preorder[preStart];
TreeNode* root = new TreeNode(rootValue);
// 根据中序遍历结果获取当前子树的根节点在中序遍历中的索引
int rootIndex = indexMap[rootValue];
// 递归构造左子树和右子树
root->left = buildTreeRecursive(preorder, inorder, preStart + 1, inStart, rootIndex - 1, indexMap);
root->right = buildTreeRecursive(preorder, inorder, preStart + rootIndex - inStart + 1, rootIndex + 1, inEnd, indexMap);
return root;
}
// 根据前序遍历和中序遍历结果构造二叉树
TreeNode* buildTree(string& preorder, string& inorder) {
// 创建一个哈希表，用于快速查找中序遍历结果中节点值对应的索引
std::unordered_map<int, int> indexMap;
for (int i = 0; i < inorder.size(); ++i) {
indexMap[inorder[i]] = i;
}
// 递归构造二叉树
return buildTreeRecursive(preorder, inorder, 0, 0, inorder.size() - 1, indexMap);
}
// 后序遍历二叉树
void postorderTraversal(TreeNode* root) {
if (root == nullptr) {
return;
}
postorderTraversal(root->left);
postorderTraversal(root->right);
cout << root->val;
}
int main() {
string s;
while (getline(cin, s)) { // 接受一整行字符串
string preorder = "", inorder = "";
// 拆分出两个字符串
int i;
for (i = 0; s[i] != ' '; i++) preorder += s[i];
i++;
for (; i < s.size(); i++) inorder += s[i];
// 开始构造二叉树
TreeNode* root = buildTree(preorder, inorder);
postorderTraversal(root);
cout << endl;
}
return 0;
}
ACM遍历二叉树
代码
#include <iostream>
#include <unordered_map>
#include <vector>
using namespace std;
struct TreeNode {
char val;
TreeNode* left;
TreeNode* right;
TreeNode(char val) : val(val), left(nullptr), right(nullptr) {}
};
// 根据输入数据构造二叉树
TreeNode* buildTree(unordered_map<char, pair<char, char>>& nodeMap, char rootValue) {
if (rootValue == '0') {
return nullptr;
}
TreeNode* root = new TreeNode(rootValue);
int leftChild = nodeMap[rootValue].first;
int rightChild = nodeMap[rootValue].second;
root->left = buildTree(nodeMap, leftChild);
root->right = buildTree(nodeMap, rightChild);
return root;
}
// 前序遍历二叉树
void preorderTraversal(TreeNode* root) {
if (root == nullptr) {
return;
}
cout << root->val;
preorderTraversal(root->left);
preorderTraversal(root->right);
}
// 中序遍历二叉树
void inorderTraversal(TreeNode* root) {
if (root == nullptr) {
return;
}
inorderTraversal(root->left);
cout << root->val;
inorderTraversal(root->right);
}
// 后序遍历二叉树
void postorderTraversal(TreeNode* root) {
if (root == nullptr) {
return;
}
postorderTraversal(root->left);
postorderTraversal(root->right);
cout << root->val;
}
int main() {
int n;
cin >> n;
unordered_map<char, std::pair<char, char>> nodeMap;
// 先保存输入的数据
vector<char> index = vector<char>(n + 1, '0');
vector<vector<int>> nums = vector<vector<int>>(n + 1, vector<int>(2, 0));
for (int i = 1; i <= n; i++) {
cin >> index[i] >> nums[i][0] >> nums[i][1];
}
// 生成二叉树
for (int i = 1; i <= n; i++) {
nodeMap[index[i]] = make_pair(index[nums[i][0]], index[nums[i][1]]);
}
TreeNode* root = buildTree(nodeMap, index[1]);
preorderTraversal(root);
cout << std::endl;
inorderTraversal(root);
cout << std::endl;
postorderTraversal(root);
cout << std::endl;
return 0;
}
ACM二叉树的高度
代码
#include <iostream>
#include <string>
#include <unordered_map>
using namespace std;
struct TreeNode {
char val;
TreeNode* left;
TreeNode* right;
TreeNode(char val) : val(val), left(nullptr), right(nullptr) {}
};
// 根据先序遍历和中序遍历序列构造二叉树
TreeNode* buildTree(string& preorder, string& inorder,
int preStart, int inStart, int inEnd,
unordered_map<char, int>& indexMap) {
if (preStart > preorder.size() - 1 || inStart > inEnd) {
return nullptr;
}
char rootValue = preorder[preStart];
TreeNode* root = new TreeNode(rootValue);
int rootIndex = indexMap[rootValue];
root->left = buildTree(preorder, inorder, preStart + 1, inStart, rootIndex - 1, indexMap);
root->right = buildTree(preorder, inorder, preStart + rootIndex - inStart + 1, rootIndex + 1, inEnd, indexMap);
return root;
}
// 计算二叉树的高度
int getHeight(TreeNode* root) {
if (root == nullptr) {
return 0;
}
int leftHeight = getHeight(root->left);
int rightHeight = getHeight(root->right);
return max(leftHeight, rightHeight) + 1;
}
int main() {
int n;
while (cin >> n) {
string preorder, inorder;
cin >> preorder >> inorder;
unordered_map<char, int> indexMap;
for (int i = 0; i < n; ++i) {
indexMap[inorder[i]] = i;
}
TreeNode* root = buildTree(preorder, inorder, 0, 0, n - 1, indexMap);
int height = getHeight(root);
cout << height << endl;
}
return 0;
}
最长公共子序列
代码
#include <iostream>
#include <vector>
#include <string>
using namespace std;
int main() {
string text1, text2;
while (cin >> text1 >> text2) {
vector<vector<int>> dp(text1.size() + 1, vector<int>(text2.size() + 1, 0));
for (int i = 1; i <= text1.size(); i++) {
for (int j = 1; j <= text2.size(); j++) {
if (text1[i - 1] == text2[j - 1]) {
dp[i][j] = dp[i - 1][j - 1] + 1;
} else {
dp[i][j] = max(dp[i - 1][j], dp[i][j - 1]);
}
}
}
cout << dp[text1.size()][text2.size()] << endl;
}
return 0;
}