Xuefen's Corner

取乎其上,只得其中


  • 首页

  • 关于

  • 标签

  • 归档

C++正则表达式小结

发表于 2020-04-16 | 阅读次数:

自2011年,C++ 11也将regex列为新标准的一部分。不仅如此,它还支持了6种不同的正则表达式的语法,分别是:ECMASCRIPT、basic、extended、awk、grep和egrep。其中ECMASCRIPT是默认的语法。而正则表达式我在这三年经常接触,往往是学了就忘。在这段时间的C++刷题经验上来看,掌握正则表达式有时候可以极大的节省你做题的时间,比如 这个题。
这是一篇更偏应用的文章,我们这里就直接上一些例子就行。
第一类就是比较常见的单次匹配问题了

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
//写一个匹配函数,()可以分隔语义 ,\\进行转义
bool IsIP(string Str) {
//regex e("\\d+\\.\\d+\\.\\d+\\.\\d"); //IP地址匹配
//regex e("[a-g]"); //区间匹配
//regex e("[a-g]*"); //*号与区间匹配联合使用
//regex e("\\w{4,10}"); //表示4-10个字符 指定个数
//regex e("ada(e|b)"); //表示或者
//regex e("^[a-z]+\\d{1,3}"); //属于小写字母开头包含几个数字而[^a-z] 不属于a-z
//regex e("ab[^cd]*"); // [^...] 任意不在方括号中的字符
//regex e("[a-zA-Z][a-zA-Z0-9_]{4,15}");
//BUAA机考题
//regex e("a[abc]b[abc]c",regex::icase); //忽略大小写
//regex e("\\w*"); //注意是否转义有很大区别
//regex e("abc.", regex::icase); // . 表示除了换行符之外任意字符
//regex e("abc?"); // ? 0个或者1个前面的字符
//regex e("abc|de[fg]"); // | 或者
//regex e("(abc)de+\\1"); // \1 第1个子串
//regex e("(ab)c(de+)\\2\\1");
//regex e("\\w+@[[:w:]]+\\.com"); // [[:w:]] :字母,数字,下划线
regex e("^abc.+$"); // $ 行尾 ^顶格
bool b = regex_match(Str, e);
return b;
}
}

第二类问题和子串提取,多重匹配有关。
上面说了,()可以分隔语义,也可以分出子串1,子串2,子串3。那么,我们也可以通过smatch把这几个子串重定向出来。
这是一些知识总结和实例:

  • smatch string类型的详细的匹配Detailed match in string
  • smatch m; 其实是一个类似vector的数组,但是不是直接按照string存的
  • m[0].str() 整个匹配的字符串 (同m.str(), m.str(0))
  • m[1].str() 第1个子串(同m.str(1)),所以需要一个.str()方法转为string
  • m[2].str() 第2个子串
  • m.prefix() 所有匹配字符串之前的部分
  • m.suffix() 所有匹配字符串之后的部分
    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    16
    17
    18
    19
    int main() {
    string str;

    while (true) {
    cin >> str;
    smatch m; // typedef std::match_results<string>

    regex e("([[:w:]]+)@([[:w:]]+)\\.com");

    bool found = regex_search(str, m, e); //只返回第一个匹配

    cout << "m.size() " << m.size() << endl; //size()==子匹配个数+1
    for (int n = 0; n< m.size(); n++) {
    cout << "m[" << n << "]: str()=" << m[n].str() << endl;
    }
    cout << "m.prefix().str(): " << m.prefix().str() << endl;
    cout << "m.suffix().str(): " << m.suffix().str() << endl;
    }
    }

在上面的例子中,展示了如何提取匹配出的第一个子串,第二个子串,但有时候我们的野心不止于此,我们还希望能够对多个match的串,分别算出他们的子串,这怎么办呢?这时候,就可以用一个很STL style的sregex迭代器来处理了。Show you my code:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
int main() {
cout << "Hi" << endl;
string str = "boq@yahoo.com, boqian@gmail.com; bo@hotmail.com";
regex e("\\w+@\\w+\\.com");
sregex_iterator pos(str.cbegin(), str.cend(), e);
sregex_iterator end; // 默认构造定义了past-the-end迭代器
for (; pos!=end; pos++) {
cout << "Matched: " << pos->str(0) << endl;
cout << "user name: " << pos->str(1) << endl;
cout << "Domain: " << pos->str(2) << endl;
cout << endl;
}
cout << "=============================\n\n";
}

第三类问题和匹配替换有关。
regex_replace()算法要求输入一个正则表达式,以及一个用于替换匹配子字符串的格式化字符串。这个格式化字符串可以通过转义序列引用匹配子字符串中的部分内容。

  • $n 匹配第n个捕捉组的字符串。例如\$l表示第一个捕捉组,\$2表示第二个,依此类推
  • $& 匹配整个正则表达式的字符串,等同于\$0
  • $` 在源字符串中,在匹配正则表达式的子字符串左侧的部分
  • $’ 在源字符串中,在匹配正则表达式的子字符串右侧的部分
  • $$ 美元符号
    看一个简单例子:
    1
    2
    3
    4
    5
    int main() {
    string str = "11sigalhu22sigalhu33",str1;
    str1 = regex_replace(str,regex("s(igal)h(u)"),"SS$1HH$2");
    cout<<str1<<endl;
    //应该输出11SSigalHHu22SSigalHHu33

数学之美——矩阵旋转

发表于 2020-04-14 | 阅读次数:

这几天在疯狂用C++学习和练习算法,昨天刷完了一道北航的研究生上机题目,觉得很有意思。之后查看了一下别人都是怎么想这些问题的,现在就是觉得数学非常美,有了数学好像好多问题,都不用去记忆规律或者推导规律了。
问题:如何将一个矩阵旋转0,90,180,270度?或许这个问题你接触过烂熟于心,或许你觉得可以花时间加以推导还是可以推出来,或者你和我一样,最开始拿到这个问题并没有自信one-take就搞出来。但如果你对矩阵论有所了解,你会发现以下方法给了你一定的perspective。总而言之,就是找到基向量的位置。在通过旋转基向量来旋转矩阵。旋转矩阵按列向量来思考会简单一些。
matrix
如果在实际编程中,遇到数组,因为数组的index不能为负,比如10*10的数组,旋转后整体应该移了10个单位。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
#include<stdio.h>
void print(int a[][10]){
for(int i=0;i<10;i++){
for(int j=0;j<10;j++){
printf("%3d",a[i][j]);
}
printf("\n");
}
}
int main(){
int a[10][10];
int k = 0;
//原图像
for(int i=0;i<10;i++){
for(int j=0;j<10;j++){
a[i][j] = k++;
}
}
//顺时针旋转90
int shun90[10][10];
for(int i=0;i<10;i++){
for(int j=0;j<10;j++){
shun90[j][9-i] = a[i][j];
}
}
//逆时针旋转90
int ni90[10][10];
for(int i=0;i<10;i++){
for(int j=0;j<10;j++){
ni90[9-j][i] = a[i][j];
}
}
//旋转180
int zhuan180[10][10];
for(int i=0;i<10;i++){
for(int j=0;j<10;j++){
zhuan180[9-i][9-j] = a[i][j];
}
}
printf("原矩阵\n\n");
print(a);
printf("\n\n顺时针90\n\n");
print(shun90);
printf("\n\n逆时针90\n\n");
print(ni90);
printf("\n\n转180\n\n");
print(zhuan180);
return 0;
}

而在面对面试或者机考的时候,简单记住(i,j)==>(j,-i),(-i,-j),(-j,i)这样的映射关系就好了,举个例子就知道应该映射到哪个位置。同理,在给出两个矩阵让你判断他们是否是旋转关系,如果是,旋转多少度也可以通过这个关系直接判断。这就是北航那个题目了。这里也简单贴出核心代码吧。

1
2
3
4
5
6
7
8
9
int flag[4]={1,1,1,1};  /**标记0,90,180,270四个方向*/
for(i=0;i<n;i++)
for(j=0;j<n;j++)
{
if(a[i][j]!=b[i][j]) flag[0]=0;
if(a[n-1-j][i]!=b[i][j]) flag[1]=0;
if(a[n-1-i][n-1-j]!=b[i][j]) flag[2]=0;
if(a[j][n-1-i]!=b[i][j]) flag[3]=0;
}

C++算法竞赛踩坑心得

发表于 2020-04-06 | 阅读次数:

这几天开始继续刷算法了,昨天晚上写了一道大模拟,今天看了半天才知道bug出在哪里,以后每犯一个值得纪念的错误都会列出来,用以自勉。

  • cin,getline的区别
  • scanf(“%d”,&n);scanf(“%s”,str);需要注意中间要加getchar读掉缓冲区
  • string也可以实现切片,需要参考string的构造函数,如string test(src,beginPos,endPos),不可以直接将一个字符赋给一个string
  • C++11及以下不提供split,可以使用vector作为返回结果手写一个,这也是头条面试的一道经典题目
  • 有时候必须采用哈希,比如在遇到TLE的时候,考虑哈希是否能用,或者怎么哈希

    1
    2
    3
    4
    5
    6
    7
    int hashID(char name[]){ //这是一道PAT题目的例子,名字的格式如THU1,PKU2,BNU1这样
    int id=0;
    for(int i=0;i<3;i++)
    id=id*26+(name[i]-'A');
    id=id*10+(name[3]-'0');
    return id;
    }
  • 有时候大数据点string比如char数组,因为容易超时

  • strcmp函数返回值不一定为正负1和0,取决于编译器

    1
    2
    3
    bool cmp(char A[],char B[]){
    return strcmp(A,B)<0;
    }
  • vector的排序:sort(vec.begin(),vec.end(),cmp),略类似于数组

  • 输出格式可能会成为一个坑,比如”%05d”在输出-1就会有问题
  • C语言结构体也可以有构造函数

    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    #include <iostream>
    using namespace std;

    struct Node {
    int x, y, z;
    Node(int _x, int _y, int _z) : x(_x), y(_y), z(_z) {}
    };

    int main() {
    Node a(1, 2, 3);
    cout << a.x << " , " << a.y << " , " << a.z << endl;
    return 0;
    }
  • 剑指offer第二题:

    1
    2
    3
    //auto ret=s.c_str();      //比较迷的类型转换可以尝试以下auto
    const char* ret=s.c_str(); //C_str()返回的是const char*,不能直接赋值
    strcpy(str,ret);
  • vector的自身反转可以直接用reverse:reverse(A.begin(), A.end());

  • MAP是关联性容器,erase不当容易引发错误
    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    16
    17
    18
    19
    20
    21
    // 错误的写法
    for (itor = m.begin(); itor != m.end(); ++itor)
    {
    if (itor->second == "def")
    {
    m.erase(itor) ; // map是关联式容器,调用erase后,当前迭代器已经失效
    }
    }

    // 正确的写法
    for (itor = m.begin(); itor != m.end();)
    {
    if (itor->second == "def")
    {
    m.erase(itor++) ; // erase之后,令当前迭代器指向其后继。
    }
    else
    {
    ++itor;
    }
    }

核函数

发表于 2020-02-24 | 阅读次数:

这两天学了下SVM,SVM我觉得其实比起很多其他的机器学习算法更“数学”一些。前几天和房哥羊哥也聊到了这个,于是简单小结一下。
首先,我们要知道SVM是在解决什么问题,他其实要做的是在给定范围下的最优化问题。本来这个问题是需要用到拉普拉斯算子等处理,通过这样一些“高深”的数学方法,这个问题最后可以简化成一个另一个相对简单的优化问题。但这个问题可能会带来很大的计算开销。在下面的例子中,我将高斯核函数的一个简化版的应用呈现,来展示一下其作用。

1
2
3
4
5
6
7
8
9
import numpy as np
import matplotlib.pyplot as plt

x = np.arange(-4, 5, 1) #array([-4, -3, -2, -1, 0, 1, 2, 3, 4])
y = np.array((x >= -2) & (x <= 2), dtype='int') #array([0, 0, 1, 1, 1, 1, 1, 0, 0])

plt.scatter(x[y==0], [0]*len(x[y==0]))
plt.scatter(x[y==1], [0]*len(x[y==1]))
plt.show()

png
上面的点是排在一个直线上,用SVM很显然是线性不可分的。能想办法使之线性可分吗?和多项式回归一样,我们可以依靠升维来使之线性可分。为了方便可视化,这里通过采用两个landmark简单升成2维。也就是我们把一个数据点小x,通过landmark映射成了(K(x,landmark1),K(x,landmark2)),这里的K函数就是高斯核函数,因为他和高斯分布的公式结构一致,因此得名。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
def gaussian(x, l):
gamma = 1.0
return np.exp(-gamma * (x-l)**2)

l1, l2 = -1, 1
X_new = np.empty((len(x), 2))
for i, data in enumerate(x):
X_new[i, 0] = gaussian(data, l1)
X_new[i, 1] = gaussian(data, l2)


plt.scatter(X_new[y==0,0], X_new[y==0,1])
plt.scatter(X_new[y==1,0], X_new[y==1,1])
plt.show()

png
现在,我们就可以看到原本线性不可分的数据点,变得线性可分了。但对真正的高斯核来说,每一个数据点都是一个landmark。假设原本的数据是m*n的数据,因为每一个数据点都是landmark,我们相当于把这个m*n的数据映射成了m*m,也是“升维”的一种体现。这种方法一般计算开销会大一些,但如果在数据量m小而单数据点特征n多的情况下,反而采用这种方案会好一些。正式采用高斯核函数时,里面会有一个调节范数的超参数gamma,这里也举出一个例子,具体的代码可以在我的Github里面PythonAdvanced里面的Fenkit-learn文件夹(一个使用python实现的sklearn-style的ML轮子库)里面看到,gamma一般来说也需要训练取得一个较好的值。而多项式核函数其实和它原理上也差不太多,也是一定程度上简化了我们表示的难度,有机会再说吧。
png

2019->2020

发表于 2019-12-31 | 阅读次数:

2019-12-31 21:36:03,在教室的我复习不进去操作系统,开始考虑本次的年终总结了.
在键盘前敲敲打打,我却想不出应该如何构思这篇年终总结的内容.
2019年似乎过得很快,起起落落,似乎做到了很多以前想去做的事情,但似乎又过得很失败.
我们应该去追求什么呢?我们应该怎么构建自己的未来蓝图呢?我们到底是为了什么而学习呢?
去哪个学校读研呢?自己未来应该去投身哪一个领域呢?怎样才能让自己成长地更快呢?
要怎么才能形成自己的核心竞争力呢?一个人的价值应该体现在哪里呢?怎样才能进一步提高自己的效率呢?
类似的问题还有很多,我也没有得到一个自己满意的答案,或许永远也没有答案.
这一年自己的心态已经变得更加成熟了,眼界也没有以前那么狭隘了,发现以前追求的很多东西在实现后都失去了意义,或者说他们本来就没有意义.
还是给自己这一年定一个目标吧,先是继续提高编程与算法的能力,然后是要稳在专业前两名,不论是智育成绩还是综合成绩,嗯.
这一年我想要做到的是,让很多事情都可以按照自己的想法来推进,不要让自己变得被动.
“阿甘说生活就像巧克力,可惜我并不喜欢吃.”

November

发表于 2019-11-23 | 阅读次数:
  • 人生只有一次,所以要拼尽全力去做自己想做的事,成为想要成为的人啊.
  • 前半学期做得还不错,但还需要反思,提高学习和做事的效率
  • 时间过得很快,把心思放在学习上.学习要抓紧,科研也要推进
  • 时刻保持清醒,做事要有原则,少说话多做事
  • 离期末还有一个多月了,后半期要着重学习通信原理
  • 逐渐向C、C++转型,多刷图和树的算法题

Ambition

发表于 2019-10-16 | 阅读次数:

志坚者,功名之柱也。登山不以艰难而止,则必臻乎峻岭。

杂感

发表于 2019-10-06 | 阅读次数:

今天觉得有必要记录一些文字了,希望能给未来三个月的自己一点斗志。
从九月开学前给羊主席庆祝生日的晚上,到一个月后的现在,一个月就这么过去了。
短期来看,暑假随便学了些东西,突击了一下算法,然后就去面试,找了个清闲一点的岗,从8月20号到10月3号在小猿打杂学习了一个半月,迫于学业压力选择全身心投入学习了。
大学两年,勉强水了几个比赛,也取得了一些成绩,也在综合排名上每次都狗进了计院前50,但整体上没有什么变化,都还是被动式学习,回想起感觉挺失败的。
以前给自己立了很多flag,现在觉得这些flag需要精确到日期,或是时间段,不要过于高估自己的能力,于是在十月的小心愿如下:

  • 可以晚睡,但别晚起床
  • Keep concentrated while learning
  • 在复习的同时,养成预习的好习惯,并且要勤加练习,动手做题
  • 学习都在实验室或者教室,一般别宅宿舍
  • 该准备的不要拖到DDL再突击
  • 10.25 19:30
  • 不要成为DDL玩家

清华科技园四日游(误)

发表于 2019-07-23 | 阅读次数:

生活不易,猫猫哭泣。
"Summary"

Last Day in ShaHe

发表于 2019-07-12 | 阅读次数:

How time flies, 这已是在沙河的最后一天了.
从两年前乘上北京西站到沙邮的直达校车,到今天收拾完准备搬回西土城校区,对于这两年的总结,却很难一言以蔽之.
和梓义一起前往北京的K1364,军训期间的绚烂晚霞,闫浩老师的线性代数,北邮数学人的期末复习讲座,Boy♂Next♂Door的朋友萌为自己的生日庆祝…
一次次深夜补作业&写代码,一次次的大作业验收,一次次的团支部工作,凌晨四点的望京明空,为挚友们的生日庆祝会,和基友们一起去看的每一次电影…
何萌妹、东哥与博涵学长的次次答疑,和xio姐的快落聊天日常,生病时室友的一声问候,清晨的“学分快关了你的闹钟”,624“白马”会所散伙饭的一壶清酒,交心的寝室夜聊,季语成的网球单独辅导…
etc…
沙河的故事到此为止了,而新的挑战才刚刚开始.
“唯有前进的勇气长存!”
"shahe"

123
Xuefen

Xuefen

A secret life corner

28 日志
7 标签
215437588 GitHub E-Mail 知乎
友情链接
  • HZY🔔
  • 🐟大佬
  • QQ🌙
  • 法师🧙‍
  • 耿导🥔
  • 🐏主席
  • 🏠大哥
  • 锦祺🚩
  • 牛🍺轩
  • 歪鸽🐤
  • 子麒🐉
  • 瑞宝📷
  • hf🌼
  • ClSlaid学弟👾
© 2020 Xuefen
本站总访问量 次 | 有人看过我的博客啦
由 Hexo 强力驱动
|
主题 — NexT.Gemini v5.1.4