后缀表达式—栈的应用

#include<iostream>
#include<algorithm>
using namespace std;
#include<map>
#include<string>
#include<stack>
#include<vector>
#include<sstream>
const int maxn=1000;
int a[maxn];
int string2int(string a)
{
	int b;
	stringstream ss;
	ss<<a; ss>>b;
	return b;
}
int main()
{	
	string a,str;
	getline(cin,a);//每个数字或者运算符空格隔开
	stack<int>s;
	for(int i=0;i<a.size();)
	{
		int pos=a.find(" ",i);
		if(pos!=string::npos)
		{
			str=a.substr(i,pos-i);
			i=pos+1;
		}
		else if(pos==string::npos)
		{
			str=a.substr(i);//长度为i到end()
			i=a.size();
		}
		if(str=="+")
			{
				int x=s.top();
				s.pop();
				int y=s.top();
				s.pop();
				s.push(y+x);
			}
			else if(str=="-")
			{	
				int x=s.top();
				s.pop();
				int y=s.top();
				s.pop();
				s.push(y-x);	
			}
			else if(str=="*")
			{	
				int x=s.top();
				s.pop();
				int y=s.top();
				s.pop();
				s.push(y*x);
			}
			else if(str=="/")
			{	
				int x=s.top();
				s.pop();
				int y=s.top();
				s.pop();
				s.push(y/x);	
			}
			else
			{
				s.push(string2int(str));
			}
	}
	cout<<s.top()<<endl;
}

0

OJ Language

Accepted:答案正确

Wrong Answer:答案错误

Presentation Error:格式错误

Time Limit Exceeded:超出时间限制

Runtime Error:运行时错误

Compile Error:编译错误

Memory Limit Exceeded:内存超限

Output Limit Exceeded:输出超限

0

OOV问题(out of vocabulary words)

一.Character Model/Mixed Word(charCNN)

Jessica,变成<B>J,<M>e,<M>s,<M>s,<M>i,<M>c,<E>a。其中<B><M><E>是Begin,Middle,End的

.Word hashing

Given a word (e.g. good), we first add word starting and ending marks to the word(e.g. #good#). Then, we break the word into lettern-grams(e.g. letter trigrams: #go, goo, ood, od#). Finally, the word is represented using a vector of letter n-grams.

三.sub-word

  • BPE(Byte Pair Encoding):BPE基于概率生成新的subword(regardless of preprocessing, tokenization, or vocabulary size)
    • 首先将词分成一个一个的字符,统计每一个连续字节对的出现频率,选择最高频者合并成新的subword,直到循环次数结束
      原始语料:
      {'l o w </w>': 5, 'l o w e r </w>': 2, 'n e w e s t </w>': 6, 'w i d e s t </w>': 3}
      
      Iter 1, 最高频连续字节对"e"和"s"出现了6+3=9次,合并成"es"。输出:
      {'l o w </w>': 5, 'l o w e r </w>': 2, 'n e w es t </w>': 6, 'w i d es t </w>': 3}
      
      Iter 2, 最高频连续字节对"es"和"t"出现了6+3=9次, 合并成"est"。输出:
      {'l o w </w>': 5, 'l o w e r </w>': 2, 'n e w est </w>': 6, 'w i d est </w>': 3}
      
      Iter 3, 以此类推,最高频连续字节对为"est"和"</w>" 输出:
      {'l o w </w>': 5, 'l o w e r </w>': 2, 'n e w est</w>': 6, 'w i d est</w>': 3}
      
      ......
  • WordPiece:WordPiece基于概率生成新的subword
  • ULM(Unigram Language Model)

四.UNK处理

oov全部替换成<UNK>标签

五.FastText

n-gram向量求平均

六.扩大词表

Refs:

 

0

1107 并查集:求簇的个数以及每个簇的元素个数

 

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

#include<iostream>
#include<algorithm>
#include<vector>
#include<set>

using namespace std;
const int maxn = 1000;
int isroot[maxn], father[maxn];
vector<int> hoby[maxn];
set<int, greater<int>> st;

int findfather(int a) //找根节点
{
    int x = a;
    while (a != father[a]) //因为初始化自己的父节点为自己,所以遍历到自己
    {
        a = father[a];
    }
    while (x != father[x]) //(可以省略)压缩路径:把所有节点的father都改为根节点a
    {
        int z = x;
        x = father[x];
        father[z] = a; //将结点的父亲都改为a;
    }
    return a;
}

void init(int n) {
    for (int i = 0; i < n; i++) {
        father[i] = i; //初始化每个人的父节点为自己
        isroot[i] = 0; //每个簇的元素个数
    }
}

void _union(int a, int b) {
    int faa = findfather(a);
    int fab = findfather(b);
    if (faa != fab)
        father[faa] = father[fab];
}

int main() {
    int n, num, temp;
    cin >> n;
    init(n);
    for (int i = 0; i < n; i++) {
        scanf("%d:", &num);
        for (int j = 0; j < num; j++) {
            cin >> temp;
            hoby[i].push_back(temp);
        }
    }
    for (int i = 0; i < n; i++) {
        for (int j = 0; j < n; j++) {
            for (int k = 0; k < hoby[i].size(); k++) {
                if (find(hoby[j].begin(), hoby[j].end(), hoby[i][k])
                    != hoby[j].end()) {
                    _union(i, j);
                    break;
                }
            }
        }
    }
    for (int i = 0; i < n; i++)
        isroot[findfather(i)]++; //相同根节点即为一簇,那么该蔟的数目++
    int ans = 0; //统计簇的数目
    for (int i = 0; i < n; i++) {
        if (isroot[i] != 0) //等于0表示不是根节点
            ans++;
    }
    cout << ans << endl;
    sort(isroot, isroot + n, greater<int>());
    for (int i = 0; i < ans; i++) {
        cout << isroot[i];
        if (i < ans - 1)
            cout << " ";
    }
    cout << endl;
    return 0;
}

 

 

0