奇偶半排序
设计算法将顺序线性表中的所有奇数集中到数组的左边，所有的偶数集中到数组的右边，要求算法的时间复杂度为O(n)。
#include<iostream>
#include<algorithm>
using namespace std;
int main() {
int n;
while(cin>>n) {
int a[n];
for(int i=0; i<n; i++) cin>>a[i];
for(int L=0,R=n-1;L<R;){
while(a[L]&1) ++L;
while((L<R)&&!(a[R]&1)) --R;
if(L<R) swap(a[L++],a[R--]);
}
for(int i=0; i<n; i++) cout<<a[i]<<' ';
cout<<endl;
}
return 0;
} #include<iostream>
#include<algorithm>
using namespace std;
int main() {
int n;
while(cin>>n) {
int a[n];
for(int i=0; i<n; i++) cin>>a[i];
for(int i=0,j=0; i<n; i++)
if(a[i]&1) swap(a[i],a[j++]);
for(int i=0; i<n; i++) cout<<a[i]<<' ';
cout<<endl;
}
return 0;
} 循环移动
设将n(n>1)个整数存放到一维数组R中。试设计一个在时间和空间两方面都尽可能高效的算法。将R中保存的序列循环左移p(0<p<n)个位置，即将R中的数据由(X0,X1,…,Xn-1)变换为(Xp,Xp+1,…,Xn-1,X0,X1,…,Xp-1)。
思路：逆序的逆序就是有序，可以通过提前完成一遍操作来“保护”部分元素使其不被乱序，从而完成部分整体交换。
void Swap(int *a, int *b){
*a^=*b;
*b^=*a;
*a^=*b;
}
void Reverse(int a[], int L, int R) {
int n=((R-L+1)>>1);
for(int i=0; i<n; i++)
Swap(&a[L+i],&a[R-i]);
}
void Solve(int a[], int n, int p) {
Reverse(a, 0, p-1);
Reverse(a, p, n-1);
Reverse(a, 0, n-1);
} 进制转换
十进制数n 转换成其他进制
#include<iostream>
#include<stack>
#include<algorithm>
using namespace std;
int main() {
int n,m;
while(cin>>n>>m) {
stack<int>st;
while(n){
st.push(n%m);
n/=m;
}
while(!st.empty()){
cout<<st.top();
st.pop();
}
cout<<endl;
}
return 0;
} 这也太水了
栈 中缀转后缀
#include <bits/stdc++.h>
using namespace std;
int main() {
map<char,int>level;
level['+']=1;
level['-']=1;
level['*']=3;
level['/']=3;
level['(']=0;
stack<char>op;
string s;
while(printf("请输入中缀表达式： \n"),cin>>s) {
printf("后缀表达式为：\n");
for(int i=0,n=s.length(); i<n; i++) {
if(s[i]=='+'||s[i]=='-'||s[i]=='*'||s[i]=='/') {
if(op.empty()) op.push(s[i]);
else if(level[s[i]]>level[op.top()]) op.push(s[i]);
else {
while(!op.empty()&&level[op.top()]>=level[s[i]]) cout<<op.top(),op.pop();
op.push(s[i]);
}
} else if(s[i]=='(') op.push('(');
else if(s[i]==')') {
while(op.top()!='(') cout<<op.top(),op.pop();
op.pop();
} else cout<<s[i];
}
while(!op.empty()) cout<<op.top(),op.pop();
cout<<endl<<endl;
}
return 0;
} 思路：
从左到右开始扫描中缀表达式
遇到非运算符时，加入后缀表达式
遇到运算符时：
- 若为'('，入栈
- 若为')'，则依次将栈中的运算符加入到后缀表达式中，直到出现'('为止，从栈中删除'('
- 若为除括号外的其它运算符，当优先级高于除'('以外的栈顶运算符时，直接入栈；
否则从栈顶开始，依次弹出比当前处理的运算符优先级高和优先级相等的运算符，
直到出现一个比它优先级低或者遇到了一个左括号为止。
后缀表达式计算
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N=1e5+7;
double getnum(string str) {
int n=str.size();
int pos=-1;
double ans=0.0;
for(int i=n-1; i>=0; --i) if(str[i]=='.') {
pos=i;
break;
}
if(pos==-1) for(ll i=n-1,j=1; i>=0; --i,j*=10) ans+=(str[i]-'0')*j;
else {
for(ll i=pos-1,j=1; i>=0; --i,j*=10) ans+=(str[i]-'0')*j;
double j=0.1;
for(int i=pos+1; i<n; i++,j*=0.1) ans+=(str[i]-'0')*j;
}
return ans;
}
int main() {
string s;
while(getline(cin,s)){
stack<double>st;
double ans=0;
bool vis=0;
for(int i=0,n=s.size(),t; i<n; i++) {
if(s[i]>='0'&&s[i]<='9') {
for(t=i; i<n&&((s[i]>='0'&&s[i]<='9')||s[i]=='.'); ++i) ;
double num=getnum(s.substr(t,i-t));
st.push(num);
} else if(s[i]=='+') {
if(!vis) ans=st.top(),st.pop(),vis=1;
double a=st.top();
st.pop();
ans=a+ans;
} else if(s[i]=='-') {
if(!vis) {
double b=st.top();
st.pop();vis=1;
double a=st.top();
st.pop();
ans=a-b;
}else {
double a=st.top();
st.pop();
ans=ans-a;
}
} else if(s[i]=='*') {
if(!vis) ans=st.top(),st.pop(),vis=1;
double a=st.top();
st.pop();
ans=ans*a;
} else if(s[i]=='/') {
if(!vis) {
double b=st.top();
st.pop();vis=1;
double a=st.top();
st.pop();
ans=a/b;
}else {
double a=st.top();
st.pop();
ans=ans/a;
}
}
}
cout<<ans<<endl;
}
return 0;
} 下面的是杨文冠的代码（数组倒着用就是了……
#include<bits/stdc++.h>
using namespace std;
int main() {
char str[500];
int cnt=10,top=0;
float num=0,num1=0,s[500];
scanf("%[^\n]",str); //读入含空格的模板，直接scanf是做不到的
for(int i=0;str[i]!='#';) { //遍历
if(str[i]>='0'&&str[i]<='9') //如果是数字就转为整数（小数点前面的数就是整数）
num=num*10+str[i++]-'0';
else if(str[i]=='.') while(str[++i]!=' ') { //小数点前面的整数加上小数点后面的小数就是这个小数的值了
num+=(float)(str[i]-'0')/cnt;
cnt*=10;
}
else if(str[i]==' ') { //如果当前位置是空格
if(str[i-1]>='0'&&str[i-1]<='9') { //如果前面输入了数字，就进栈并且初始化
s[top++]=num;
num=0;
cnt=10;
}
++i;
}
else { //出栈进行计算，先出栈的是被操作数（即num1）
num1=s[--top]; //--top起到删除栈顶元素的作用
num =s[--top];
switch(str[i++]) {
case '+': num+=num1; break;
case '-': num-=num1; break;
case '*': num*=num1; break;
case '/': num/=num1; break;
}
s[top++]=num; //得到的新数进栈
num=0;
}
}
cout<<s[0]<<endl; //运算结束后只有一个数
return 0;
} 出栈序列
递归，二进制枚举
#include <iostream>
#include <stack>
#include <vector>
using namespace std;
int num = 0,n;
void f(vector<bool>pos, int cnt[], int a[]) {
if (cnt[1]) {
pos.push_back(1);
--cnt[1];
f(pos, cnt, a);
++cnt[1];
pos.pop_back();
}
if (cnt[0] && cnt[0] > cnt[1]) {
pos.push_back(0);
--cnt[0];
f(pos, cnt, a);
++cnt[0];
pos.pop_back();
}
if (pos.size() == 2 * n) {
stack<int>stk;
int j = 0;
for (vector<bool>::iterator it = pos.begin(); it != pos.end(); ++it) {
if (*it) stk.push(a[j++]);
else cout << stk.top() << " ", stk.pop();
}
++num;
cout << endl;
}
}
int main() {
while (cout << "Input the number: ", cin >> n) {
int a[n];
for (int i = 0; i < n; i++) a[i] = 1 + i;
int cnt[2] = {n, n-1};
vector<bool>pos;
pos.push_back(1);
f(pos, cnt, a);
cout << "Total: " << num << endl;
num = 0;
}
return 0;
} 全排列
#include <bits/stdc++.h>
using namespace std;
bool chk(vector<int> pushV, vector<int> popV) {
stack<int>stk;
for (int i=0,j=0; i < pushV.size(); ++i) {
stk.push(pushV[i]);
while (!stk.empty() && stk.top() == popV[j]) {
stk.pop();
++j;
}
}
return stk.empty();
}
int main() {
int n;
while(~scanf("%d", &n)) {
vector<int> p, q;
for (int i=1; i<=n; ++i) p.push_back(i), q.push_back(i);
do {
if (chk(q, p)) {
for (auto i : p) printf("%d ",i);
printf("\n");
}
} while (next_permutation(p.begin(), p.end()));
}
return 0;
}//全排列方案 链表倒数第k
已知一个带有表头结点的单链表，结点结构为（data,link），假设该链表只给出了头指针list。在不改变链表的前提下，请设计一个尽可能高效的算法，查找链表中倒数第k个位置上的结点（k为正整数）。若查找成功，算法输出该结点的data域的值，并返回1；否则，只返回0。要求：
（1）描述算法的基本设计思想；
（2）描述算法的详细实现步骤；
（3）根据设计思想和实现步骤，采用程序设计语言描述算法，关键之处请给出简要注释。
#include <iostream>
#include <cstdio>
#include <cstdlib>
using namespace std;
struct node {
int data;
struct node *link;
};
node *GetList() {
node *head=NULL,*rear=NULL;
printf("Input List, end with -1 :\n");
int TmpVal=0;
while(scanf("%d",&TmpVal),TmpVal!=-1) {
node *TmpNode=(node *)malloc(sizeof(node));
TmpNode->data=TmpVal;
if (head==NULL) head=TmpNode;
else rear->link=TmpNode;
rear=TmpNode;
}
if (rear) rear->link=NULL;
return head;
}
int main() {
node *head=GetList();
if (head==NULL) {
printf("List is empty!\n");
return 0;
}
//倒数第k==正数第n-k+1==n-(k-1)
//指针i从头指针开始遍历，向前走k-1，指针j不动
//i j同时向前移动 直到i到达n 此时j指向即为所求
int k;
while(printf("Input K : "),~scanf("%d",&k)) {
node *i=head,*j=head;
for(int cnt=1; cnt<=k&&i; ++cnt,i=i->link);
for(; i; i=i->link,j=j->link);
printf("The K-th last number is: %d\n\n",j->data);
}
return 0;
} 链表公共起始位
假定采用带头节点的单链表保存单词，当两个单词有相同的后缀时，则可共享相同的后缀存储空间，例如，“loading”和“being”，如下图所示。
请设计一个时间上尽可能高效的算法，找出由str1和str2所指向两个链表共同后缀的起始位置（如图中字符i所在节点的位置p）。要求：
（1）给出算法的基本设计思想。
（2）根据设计思想，采用C或C++或JAVA语言描述算法，关键为之处给出注释。
（3）说明你所设计算法的时间复杂度。
//将两个str以尾部为基准对齐，指针指向最小点
//两个指针同时右移，直到指向地址相同/指向NULL
//指向点即为所求
//O(m+n)线性阶
typedef struct Node{
char data;
struct Node *next;
} SNODE;
SNODE * Findlist(SNODE *str1,SNODE *str2){
int m,n;
SNODE *p,*q;
m=Listlen(str1); //求单链表str1的长度m
n=Listlen(str2); //求单链表str2的长度n
for (p=str1;m>n;m--) //若m大，则str1后移m-n个节点
p=p->next;
for (q=str2;m<n;n--) //若n大，则str2后移n-m个节点
q=q->next;
while (p->next!=NULL && p->next!=q->next){
p=p->next; //p、q两步后移找第一个指针值相等的节点
q=q->next;
}
return p->next;
} 链表排序-归并
链表的高效排序 O(nlogn)
#include<iostream>
#include<stack>
#include<string>
using namespace std;
ListNode* sortList(ListNode* head) {
if(head==nullptr)
return nullptr;
if(head->next==nullptr)
return head;
ListNode *slow = head; //设置一个慢指针
ListNode *fast = head->next; //设置一个快指针
while(fast!=nullptr) { //找出链表的中间节点
fast = fast->next;
if(fast==nullptr)
break;
fast = fast->next;
slow = slow->next;
}
ListNode *list1 = head;
ListNode *list2 = slow->next;
slow->next = nullptr;
ListNode *left = sortList(list1); //递归左归并
ListNode *right = sortList(list2); //递归右归并
ListNode *output = merge(left,right); //合并两个有序链表
return output;
}
//合并两个有序链表
ListNode* merge(ListNode *left, ListNode *right) {
ListNode *out;
if(left->val<right->val) {
out = left;
left = left->next;
} else {
out = right;
right = right->next;
}
ListNode *p = out;
p->next = nullptr;
while(left&&right) {
if(left->val<right->val) {
p->next = left;
left = left->next;
p = p->next;
p->next = nullptr;
} else {
p->next = right;
right = right->next;
p = p->next;
p->next = nullptr;
}
}
if(left!=nullptr)p->next = left;
if(right!=nullptr)p->next = right;
return out;
} 提取数字
从一个混有英文字母的字符串中提取数字。
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
int main() {
int a[105];
int cnt = 0;
char ch;
do {
ch=getchar();
int num = 0;
bool vis = 0;
while (ch >= '0' && ch <= '9') {
num = num * 10 - '0' + ch;
//num = num << 3 + num << 1 + ch ^ 48;
ch = getchar();
vis = 1;
}
if (vis) a[cnt++] = num;
} while (ch != '\n');
for (int i = 0; i < cnt; ++i) printf("%d ", a[i]);
return 0;
} 如果考虑大数的话，用字符串/字符数组来做即可。
#include <iostream>
#include <string>
#include <vector>
using namespace std;
typedef long long ll;
int main() {
char ch;
vector<string> ans;
do {
ch = getchar();
string tmp = "";
while (ch >= '0' && ch <= '9') {
tmp += ch;
ch = getchar();
}
if (tmp != "") ans.push_back(tmp);
} while (ch != '\n');
for (auto x : ans) cout << x << endl;
return 0;
} 其他数之积
给你一个数组A[0..n-1]，请你在O(n)的时间里构造一个新的数组B[0..n-1]，使得：
不能使用除法运算。
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N = 1e3 + 5;
//two pointers
int main() {
int a[N], b[N], l[N], r[N];
int n;
cin >> n;
for (int i = 0; i < n; ++i) cin >> a[i];
l[0] = a[0], r[n - 1] = a[n - 1];
for (int i = 1; i < n; ++i) l[i] = l[i - 1] * a[i];
for (int i = n - 2; i >= 0; --i) r[i] = r[i + 1] * a[i];
b[0] = r[1], b[n - 1] = l[n - 2];
for (int i = 1; i < n - 1; ++i) b[i] = l[i - 1] * r[i + 1];
for (int i = 0; i < n; ++i) cout << b[i] << ' ';
return 0;
} KMP算法
#include <iostream>
#include <string>
using namespace std;
const int N = 255;
void GetNextval(string p, int next[]) {//递归实现优化
int pLen = p.length();
next[0] = -1;
int j = -1;
int i = 0;
while (i < pLen - 1) {
if (j == -1 || p[i] == p[j]) {
++i,++j;
if (p[i] != p[j])
next[i] = j;
else
next[i] = next[j];
} else
j = next[j];
}
}
void GetNext(string p, int next[]) {//递归实现
int pLen = p.length();
next[0] = -1;
int j = -1;
int i = 0;
while (i < pLen - 1) {
if (j == -1 || p[i] == p[j])
next[++i] = ++j;
else
j = next[j];
}
}
void Getnext(string T, int next[]) {//循环实现
int n = T.size();
next[0] = -1;
next[1] = 0;
for (int i = 1; i < n - 1;) {
int t = i;
while (i < n - 1 && T[i] == T[i - t]) next[++i] = i - t;
if (i == t) next[++i] = 0;
}
}
int KMP(string a, string b, int next[]) {
int i = 0, j = 0, lena = a.length(), lenb = b.length();
while (i < lena && j < lenb) {
if (j == -1 || a[i] == b[j])
++i, ++j;
else
j = next[j];
}
if (j == lenb)
return i - j;
else
return -1;
}
int main() {
string a = "ababaaaba";
string b = "ababaaaba";
int next[N];
for (int i = 0; i < b.length(); i++) printf("%3c", b[i]);
cout << endl;
Getnext(b, next);
for (int i = 0; i < b.length(); i++) printf("%3d", next[i]);
cout << endl;
GetNext(b, next);
for (int i = 0; i < b.length(); i++) printf("%3d", next[i]);
cout << endl;
return 0;
}
优化后的输出结果
-1 -1 1 0 0 -1 -1 1 3 0 -1 -1 -1 -1 -1 -1 -1 -1 0 -1 1 0 -1 3 -1
课本式KMP的结果
//严蔚敏原版
#include <iostream>
#include <string>
using namespace std;
const int N = 255;
void GetNextval(string p, int next[]) {
int i=1,j=0;
next[1]=0;
while(i<p.length()) {
if(j==0||p[i]==p[j])next[++i]=++j;
else j=next[j];
}
}
int main() {
string a = "bbdcfbbdac";
string b = "aaaaaaa";
string c = "babbabab";
int next[N];
cout << endl;
GetNextval(a, next);
for (int i = 1; i < a.length(); i++) printf("%3d", next[i]);
cout << endl;
GetNextval(b, next);
for (int i = 1; i < b.length(); i++) printf("%3d", next[i]);
cout << endl;
GetNextval(c, next);
for (int i = 1; i < c.length(); i++) printf("%3d", next[i]);
cout << endl;
return 0;
}
运行结果：
0 1 1 1 1 2 2 3 1
0 1 2 3 4 5
0 1 1 1 2 3 2 //严蔚敏改进
#include <iostream>
#include <string>
using namespace std;
const int N = 255;
void GetNextval(string p, int next[]) {
int i=1,j=0;
next[1]=0;
while(i<p.length()) {
if(j==0||p[i]==p[j]){
++i,++j;
if(p[i]!=p[j]) next[i]=j;
else next[i]=next[j];
}
else j=next[j];
}
}
int main() {
string a = "bbdcfbbdac";
string b = "aaaaaaa";
string c = "babbabab";
int next[N];
cout << endl;
GetNextval(a, next);
for (int i = 1; i < a.length(); i++) printf("%3d", next[i]);
cout << endl;
GetNextval(b, next);
for (int i = 1; i < b.length(); i++) printf("%3d", next[i]);
cout << endl;
GetNextval(c, next);
for (int i = 1; i < c.length(); i++) printf("%3d", next[i]);
cout << endl;
return 0;
}
运行结果：
0 1 1 1 0 2 1 3 1
0 0 0 0 0 0
0 1 1 0 1 3 1 这是因为超级老的老教材，清华大学出版社《数据结构》第二版默认字符串第一个字符存数组长度，所以next数组的首下标也是从0开始……
其实很多东西本身并不复杂，而是有些“学者”在传播的时候把它弄复杂了。
推荐这一篇博客，我们都是跟着这个学的。
https://blog.csdn.net/v_july_v/article/details/7041827#
应要求写一下这个。
按照优化后的KMP算法生成P串next数组为 -1 -1 1
ababbaabaa
aa
aa
a
aab括号/层号表示构建树
复古了一下，用了次c语言。
#include <stdio.h>
const int maxn = 3;
const int maxsize = 20;
typedef char datatype;
typedef struct treenode {
datatype data;
int child[maxn];
} treenode;
typedef struct levelnode {
datatype data;
int level;
} levelnode;
void leveltotree(int length, levelnode ltree[], int *root, treenode tree[]) {
for (int i = 0; i < length; ++i)
for (int j = 0; j < maxn; ++j) tree[i].child[j] = -1;
*root = 0;
tree[0].data = ltree[0].data;
//初始化
for (int i = 1, j = i - 1, tmp = j; i < length; ++i) {
tree[i].data = ltree[i].data; //本个节点
if (ltree[i].level > ltree[i - 1].level) {
tmp = j;
j = i - 1;
for (int k = 0; tree[j].child[k] != -1; ++k)
tree[j].child[k] = i; //将自己连接到双亲节点上
} else if (ltree[i].level > ltree[j].level) { //纳入孩子
tree[j].child[0] = i;
} else {
j = tmp;
for (int k = 0; tree[j].child[k] != -1; ++k)
tree[j].child[k] = i; //将自己连接到双亲节点上
}
} 二叉树的遍历和构建
#include <memory.h>
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
typedef char TreeElemType;
typedef struct BinTreeNode {
TreeElemType Data;
struct BinTreeNode *Lchild, *Rchild;
} BinTreeNode, *BinTree;
void CreatBinTree(BinTree *T) {
// input as PreOrderTraversal
// eg. AB#D##C##
TreeElemType ch;
scanf("%c", &ch);
if (ch == '#')
*T = NULL;
else {
*T = (BinTree)malloc(sizeof(BinTreeNode));
if (!*T) exit(-1);
(*T)->Data = ch;
CreatBinTree(&(*T)->Lchild);
CreatBinTree(&(*T)->Rchild);
}
}
void PreOrderTraverse(BinTree T) {
if (T == NULL) return;
printf("%c", T->Data);
PreOrderTraverse(T->Lchild);
PreOrderTraverse(T->Rchild);
}
// To construct a binary tree through post-order traversal,
// the sequence needs to be read from back to front.
// Root ---> RChild ---> LChild
void InOrderTraverse(BinTree T) {
if (T == NULL) return;
InOrderTraverse(T->Lchild);
printf("%c", T->Data);
InOrderTraverse(T->Rchild);
}
void PostOrderTraverse(BinTree T) {
if (T == NULL) return;
PostOrderTraverse(T->Lchild);
PostOrderTraverse(T->Rchild);
printf("%c", T->Data);
} 穿线二叉树
上图是一个常规的二叉树结构。它有很多指针指向了NULL。我们可以利用这些空的指针，来更快地实现先序/中序/后序的访问。
具体怎么做呢？其实很简单，就是让每一个有空指针的节点，左指针指向前驱，右指针指向后继。
前序+中序推树
（不带虚空节点）
#include <stdio.h>
const int N = 1010;
int pre[N], in[N], post[N];
int k;
struct node {
int value;
node *l, *r;
node(int value = 0, node *l = NULL, node *r = NULL)
: value(value), l(l), r(r) {}
};
void buildtree(int l, int r, int &t, node *&root) {
int flag = -1;
for (int i = l; i <= r; ++i)
if (in[i] == pre[t]) {
flag = i;
break;
}
if (flag == -1) return;
root = new node(pre[t++]);
if (flag > l) buildtree(l, flag - 1, t, root->l);
if (flag < r) buildtree(flag + 1, r, t, root->r);
}
void preorder(node *root) {
if (root != NULL) {
pre[k++] = root->value;
preorder(root->l);
preorder(root->r);
}
}
void inorder(node *root) {
if (root != NULL) {
inorder(root->l);
post[k++] = root->value;
inorder(root->r);
}
}
void postorder(node *root) {
if (root != NULL) {
postorder(root->l);
postorder(root->r);
post[k++] = root->value;
}
}
void removetree(node *root) {
if (root == NULL) return;
removetree(root->l);
removetree(root->r);
delete root;
}
int main() {
int n;
while (~scanf("%d", &n)) {
for (int i = 1; i <= n; ++i) scanf("%d", &pre[i]);
for (int i = 1; i <= n; ++i) scanf("%d", &in[i]);
node *root;
int t = 1;
buildtree(1, n, t, root);
k = 0;
postorder(root);
for (int i = 0; i < k; ++i)
printf("%d%c", post[i], i == k - 1 ? '\n' : ' ');
removetree(root);
}
return 0;
} 后序+中序
/*test data
9
7 4 2 8 9 5 6 3 1
4 7 2 1 8 5 9 3 6
1 2 4 7 3 5 8 9 6
*/
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N = 1010;
int pre[N], in[N], post[N];
int k;
struct node {
int value;
node *l, *r;
node(int value = 0, node *l = NULL, node *r = NULL)
: value(value), l(l), r(r) {}
};
void buildtree(int l, int r, int &t, node *&root) {
int flag = -1;
for (int i = l; i <= r; ++i)
if (in[i] == post[t]) {
flag = i;
break;
}
if (flag == -1) return;
root = new node(post[t--]);
if (flag < r) buildtree(flag + 1, r, t, root->r);
if (flag > l) buildtree(l, flag - 1, t, root->l);
}
void preorder(node *root) {
if (root != NULL) {
pre[k++] = root->value;
preorder(root->l);
preorder(root->r);
}
}
void inorder(node *root) {
if (root != NULL) {
inorder(root->l);
post[k++] = root->value;
inorder(root->r);
}
}
void postorder(node *root) {
if (root != NULL) {
postorder(root->l);
postorder(root->r);
post[k++] = root->value;
}
}
void removetree(node *root) {
if (root == NULL) return;
removetree(root->l);
removetree(root->r);
delete root;
}
int main() {
int n;
while (~scanf("%d", &n)) {
for (int i = 1; i <= n; ++i) scanf("%d", &post[i]);
for (int i = 1; i <= n; ++i) scanf("%d", &in[i]);
node *root;
int t = n;
buildtree(1, n, t, root);
k = 0;
preorder(root);
for (int i = 0; i < k; ++i)
printf("%d%c", pre[i], i == k - 1 ? '\n' : ' ');
removetree(root);
}
return 0;
} 小学奥数 填数字
1到9，填成两个三位数之和等于另一个三位数。
数量级太小，全排列查一遍就行了
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N = 1e5 + 7;
const ll mod = 1e9 + 7;
int main() {
vector<int> a;
for (int i = 1; i < 10; ++i) a.push_back(i);
vector<vector<int>> ans;
do {
ans.push_back(a);
} while (next_permutation(a.begin(), a.end()));
for (vector<vector<int>>::iterator it = ans.begin(); it != ans.end(); ++it) {
vector<int>::iterator iter = (*it).begin();
int a = iter[0] * 100 + iter[1] * 10 + iter[2];
int b = iter[3] * 100 + iter[4] * 10 + iter[5];
int c = iter[6] * 100 + iter[7] * 10 + iter[8];
if (a + b == c) {
for (int i = 0; i < 9; ++i) cout << iter[i] << " ";
cout << endl;
}
}
return 0;
} 其实也不用存，只是熟悉一下迭代器写法。
vector<int> a;
for (int i = 1; i < 10; ++i) a.push_back(i);
do {
if (a[0] * 100 + a[1] * 10 + a[2] + a[3] * 100 + a[4] * 10 + a[5] == a[6] * 100 + a[7] * 10 + a[8])
for (int i = 0; i < 9; ++i) printf("%d%c", a[i], i == 8 ? '\n' : ' ');
} while (next_permutation(a.begin(), a.end())); 
京公网安备 11010502036488号