C语言正则表达式使用及注意点
正则表达式作为程序员必备的高效率技能之一,程序开发中不可避免的就会用到,最近在开发中就需要使用C语言的正则表达式来解决一些问题。吐槽一句(gcc版本太低,用不了C++11的特性,也就用不了c++的regex)。
最近因为需要把字符串中的html标签替换掉,想到的是使用正则来做,因为原来模块是用C++码的,所以就用的glibc的regex来做的。后来查资料发现用python来做这件事,简单方便,而且一次性可以完成所有替换,不想用C还需要自己写程序移动指针完成替换。不多说了上代码,很简单。
工作一段快两年了,感觉之前学的数据结构和算法基本忘得差不多了,最近一段时间准备复习一下相关知识。
有一个求数组中最大和最小数的题目,基本的思路是遍历一遍数组,然后每个一个元素都和最大值和最小值比较,时间复杂度是2(N-1)或2N。
比较简单的一种减少复杂度的方法是把数组的元素两两分组比较,然后较大的数和max比较,较小的数和min比较,这种实现方法的时间复杂度是1.5N。
还有一种是采用分治法,比较次数也是1.5N,思路是将数组一分为二,分别获取两个子数组的最大和最小值,然后进行取两个子数组中较小的最小值和较大的最大值。
O(N) = (N/2 + N/4 + … + N/2^(log2(N))) = 3N/2 (收敛?)