很简单就是在传统二叉排序树的构建过程中略略修改：比较key的过程改为字符串的比较。
然后结点的数据形式变成字符串。最后再加上深度的求解。
直接
代码#include
#include
#include
#include
using namespace std;
const int N=1000;
char str[N][N];
struct Node{
char ch[N];
Node *lchild,*rchild;
};
class BST{
private:
Node* root;
public:
void insertBST(Node* &bt,char *s);
void inOrder(Node*bt);
BST(char str[N][N],int length);
Node* getRoot(){return root;}
int getDepth(Node* bt);
};
BST::BST(char str[N][N],int length){
root=NULL;
for(int i=0;ich[i]=s[i];
}
bt->ch[i]='\0';
bt->lchild=NULL;
bt->rchild=NULL;
}
else{
if(strcmp(s,bt->ch)<0) insertBST(bt->lchild,s);
else insertBST(bt->rchild,s);
}
}
void BST::inOrder(Node* bt){
if(bt==NULL) return;
else{
inOrder(bt->lchild);
cout<ch<<" ";
inOrder(bt->rchild);
}
return;
}
int BST::getDepth(Node* bt){
if(bt->lchild==NULL&&bt->rchild==NULL) return 1;
else{
int l=0,r=0;
if(bt->lchild!=NULL) l=getDepth(bt->lchild);
if(bt->rchild!=NULL) r=getDepth(bt->rchild);
return 1+max(l,r);
}
}
int main(){
int n;
cin>>n;
for(int i=0;i>str[i];
}
BST bst(str,n);
Node* root=bst.getRoot();
bst.inOrder(root);
cout< 思路
这题可以看到之前写过的出栈合法性那题的影子。就是模拟，不赘述惹。
直接
代码#include
#include
#include
using namespace std;
const int N=100;
int a[N],b[N];
int main(){
int n;
cin>>n;
for(int i=0;i>a[i];
for(int i=0;i>b[i];
int ans=0;
stack st;
for(int i=0,k=0;i
已A！
思路
稀疏矩阵压缩那节就提到过，一直没写。今天稍稍写一下吧。
注意是对称的！！
#include
using namespace std;
const int N1=35;
const int N2=55;
//矩阵压缩之稀疏矩阵实现矩阵相乘。
struct Tri{
int x;
int y;
int w;
};
int n,num1,num2;
Tri tria[N2],trib[N2];
int getAW(int x,int y){
for(int i=0;i>n;
cin>>num1>>num2;
for(int i=0;i>tria[i].x>>tria[i].y>>tria[i].w;
for(int i=0;i>trib[i].x>>trib[i].y>>trib[i].w;
for(int i=0;i
Blah数集
问题分析
暴力？
所谓万物皆可暴力（bushi），我们直接用循环把他前n个数存在一个数组里面然后排个序？
不会分析时间复杂度就很grass了。
（我自己的想法）
找找规律？
（这个图是不是蛮对称的hhhh，或许可以思考下去？）
以1为例。
1的2x+1这一路下去肯定是比3x+1下去要小。
而一次2x+1后的3x+1,与一次3x+1后的2x+1大小不确定，是不是需要比较一下嘞？
同时，先计算出来的数，也会比后面计算出来的数小。（不信你看图）
以上是废话，我自己是这么think了一下的。
key
如果说暴力是全部找出来之后在排序，我们是不是可以想一下有什么可以边找边排序的？
单调栈？单调队列？
好的，已经想到了栈与队列了。
栈先进先出没什么关系，好像。
队列呢？二叉树层序遍历里面不是有一个使用队列的地方吗？
仔细想想好像有一点类似哦，层序遍历是使用一个队列，每输出一个根节点，就将他的左右子树入队。这样就可以保证根节点下一层左边部分的结点先输出了。
那这里呢?
我们是否可以把计算出来的数输出的同时，将他的后续入队，让他后续满足相对较小的先输出呢？
可是怎么区分“2x+1这一路”和“3x+1”？
对的，用两个队列，一个存放2x+1，一个存放3x+1。从起始的值开始入队，利用先进先出的性质。
这里我们就直接可以发现，两个队列是天然的单调队列了。
之前是相对较小，这下只需一步“相对”变“绝对”。
在每次要输出的时候，把两个队列的头头比较，输出那个较小的。
不知道这种带着思考的问题分析效果怎么样，反正我是蛮享受的。找个时间把单调队列的滑动窗口水一下hhhhh
现在应该就有思路了吧，用stl可以，数组模拟队列也可以。
代码
#include
#include
using namespace std;
int main(){
int num,n;
while(cin>>num>>n){
priority_queue,greater > c;
int i=1;
c.push(num);
while(i
优先队列
与前端的梦幻联动！hhhhhh
不会写，补正则表达式呜呜呜呜呜呜。
最大字典序
先决知识
字典序是什么
字典序（dictionary order），又称 字母序（alphabetical order），原意是表示英文单词在字典中的先后顺序，在计算机领域中扩展成两个任意字符串的大小关系。
简言之 就是将两个字符串从左到右按照ASCII码比较大小，如果有一方大，他的字典序就大，相同的话继续比较，直到出现不同的字符或者最后两个串相等。
问题分析
我们当然要把最大的那个n放在第一个咯！
那第二个嘞？
首先我们知道，如果要出栈n这个最大的数，就需要先从头扫描，依次入栈，直到我们入栈出栈了n，对吧。
这时候栈可能已经有一定的基础了（栈中有一定的元素了）我们接着怎么比较？
这时候我们就有两种出栈的方式，1.直接d栈顶 2.看一看后面有没有更大的数可以出栈。
所以
比较这时候的栈顶和后续数的最大那个。看看我们具体该走哪一个方案（我愿称之为试探）
第三个第四个就一次类推
代码
#include
#include
#include
using namespace std;
const int N=5e4+10;
int q[N];
int n;
vector getResult(){
stack st;
vector ans;
int i=0;
while(q[i]!=n)
st.push(q[i++]);
ans.push_back(q[i++]);
for(;ib) b=q[j],index=j;
}
if(b>a) {
while(i!=index) st.push(q[i++]);
ans.push_back(q[i++]);
}
else ans.push_back(a),st.pop();
}
else st.push(q[i++]);
}
while(!st.empty()) ans.push_back(st.top()),st.pop();
return ans;
}
int main(){
stack st;
cin>>n;
for(int i=0;i>q[i];
vector answer=getResult();
for(int i=0;i
嘿嘿~更新了一个高清图~
欢迎分享，转载请注明来源：内存溢出
微信扫一扫
支付宝扫一扫
评论列表（0条）