字母字符串和整型编号的映射

第一种方法:哈希变化。(用的太少,比特币挖矿)

第二种方法:map容器;

int num=0;//编号从0开始
map<int,string>int2string;
map<string,int>string2int;
int change(string str)
{
    if(string2int.find(str)!=string2int.end())
        return string2int[str];
    else
    {
        string2int[str]=num;
        int2string[num]=str;
        return num++;
    }
}

 

0

1072. Gas Station (30)-PAT甲级真题(Dijkstra)

 

原题:https://www.patest.cn/contests/pat-a-practise/1072

每次遍历d[],求所有最短路径中最小的;

#include<iostream>
#include<algorithm>
#include<string>
#include<sstream>
using namespace std;
const int maxn = 1011, INF = 1000000000;
int n, m, k, ds, g[maxn][maxn], d[maxn], vis[maxn];

int string2int(string str) {
	stringstream ss;
	int a;
	ss << str;
	ss >> a;
	return a;
}
int dijkstra(int v, int &minds, int &add) {
	int min, u;
	fill(vis, vis + maxn, 0);
	fill(d, d + maxn, INF);
	d[v] = 0;
	for (int i = 0; i < n + m; i++) {
		min = INF;
		for (int j = 1; j <= n + m; j++) {
			if (vis[j] == 0 && min > d[j]) {
				min = d[j];
				u = j;
			}
		}
		vis[u] = 1;
		for (int k = 1; k <= n + m; k++) {
			if (vis[k] == 0 && d[k] > d[u] + g[u][k])
				d[k] = d[u] + g[u][k];
		}
	}
for(int i=1;i<=n;i++)/*遍历d[],不能在求d[]的过程中遍历,只能全部求完d[]之后
 {
 if(d[i]>ds)
 return 1;
 add+=d[i];
 if(minds>d[i])
 minds=d[i];
 }
 return -1;
 }
 int main()
 {
 int id1,id2;
 int ansid,ansds=0,ansadd=INF,minds,add;
 cin>>n>>m>>k>>ds;
 fill(g[0],g[0]+maxn*maxn,INF);
 string a,b;
 for(int i=0;i<k;i++)
 {
 cin>>a>>b;
 if(a[0]=='G')
 id1=n+string2int(a.substr(1));
 else
 id1=string2int(a);
 if(b[0]=='G')
 id2=n+string2int(b.substr(1,b.size()-1));
 else
 id2=string2int(b);
 cin>>g[id1][id2];
 g[id2][id1]=g[id1][id2];
 }
 for(int i=1;i<=m;i++)
 {
 minds=INF;
 add=0;
 if(dijkstra(n+i,minds,add)>0)
 continue;
 if(minds>ansds)
 {
 ansds=minds;
 ansid=n+i;
 ansadd=add;
 }
 else if(minds==ansds&&add<ansadd)
 {
 ansid=n+i;
 ansadd=add;
 }
 }
 if(ansadd==INF)
 cout<<"No Solution"<<endl;
 else
 {
 cout<<"G"<<ansid-n<<endl;
 printf("%0.1f %0.1f\n",ansds*1.0,ansadd*1.0/n);
 }
 return 0;
 }

 

0

C++中string与int,double转化

 

注意:保留为浮点数时会有误差,貌似都只能六位有效数字(包括整数)

第一种方法:头文件#include<sstream>,c++98,如果需要转化为long long,返回值前面加上long long即可;与double等浮点数进行转换的时候直接改类型即可。

int stringToint(const string &S)//利用stringstream完成string到int的转换  
{  
    stringstream ss;  
    int result;  
    ss << S; ss >> result;  //string可以为单个字符
    return result;  
}
string intTostring(const int &a)//利用stringstream完成int到string的转换
{
	stringstream  ss;
	string str;
	ss<<a; ss>>str;
	return str;
}

第二种方法:c++11[hermit auto=”1″ loop=”0″ unexpand=”0″

①string to others:String中函数stoi(Convert string to integer),stoll(Convert string to long long),Stod(Convert string to double),stof(Convert string to float)

②others to string:to_string(int val)

 

0

1066. Root of AVL Tree (25)-PAT甲级真题(AVL树)左旋右旋四种类型

原题:https://www.patest.cn/contests/pat-a-practise/1066

代码如下:

#include<iostream>
#include<algorithm>
using namespace std;
struct node {
	int v, height;
	node *lchild, *rchild;
};
int getheight(node *root) //获取高度
		{
	if (root == NULL)
		return 0;
	return root->height;
}
int getbalance(node *root) //获取平衡因子
		{
	return getheight(root->lchild) - getheight(root->rchild);
}
void L(node *&root) //左旋
		{
	node *temp = root->rchild;
	root->rchild = temp->lchild;
	temp->lchild = root;
	root->height = max(getheight(root->lchild), getheight(root->rchild)) + 1;
	temp->height = max(getheight(temp->lchild), getheight(temp->rchild)) + 1;
	root = temp;
}
void R(node *&root) //右旋
		{
	node *temp = root->lchild;
	root->lchild = temp->rchild;
	temp->rchild = root;
	root->height = max(getheight(root->lchild), getheight(root->rchild)) + 1;
	temp->height = max(getheight(temp->lchild), getheight(temp->rchild)) + 1;
	root = temp;
}
void insert(node *&root, int x) //建树并且调整
		{
	if (root == NULL) {
		root = new node;
		root->v = x;
		root->height = 1;
		root->lchild = root->rchild = NULL;
		return;
	}
	if (x < root->v) {
		insert(root->lchild, x);
		root->height = max(getheight(root->lchild), getheight(root->rchild))
				+ 1;
		if (getbalance(root) == 2) {
			if (getbalance(root->lchild) == 1) //LL型
				R(root);
			else if (getbalance(root->lchild) == -1) //LR型
					{
				L(root->lchild);
				R(root);
			}
		}
	} else {
		insert(root->rchild, x);
		root->height = max(getheight(root->lchild), getheight(root->rchild))
				+ 1;
		if (getbalance(root) == -2) {
			if (getbalance(root->rchild) == -1) //RR型
				L(root);
			else if (getbalance(root->rchild) == 1) //RL型
					{
				R(root->rchild);
				L(root);
			}
		}
	}
}
int main() {
	int n, x;
	node *root = NULL;
	cin >> n;
	for (int i = 0; i < n; i++) {
		cin >> x;
		insert(root, x);
	}
	cout << root->v << endl;
	return 0;
}

 

0