爬虫小项目——抓取博客文章名和时间
用python及requests库,beautifulSoup库,正则表达式等抓取博客文章名,创建时间,修改时间,并存到excel文件中
requests库
beautifulSoup4库
openpyxl库
正则表达式
思路和框架思路
抓取网页源码
分析源码,并将需要的结果储存到合适的数据结构内
把结果存入excel文件
框架12345678910111213141516171819202122232425import requestsimport bs4import reimport openpyxlimport osdef getHTMLText(url): #抓取网页代码 return ""def fillTitleList(titleList, html): #填充数据结构 passdef storageTitleList(TitleList): #存入excel passdef main(): #主函数 titleList = [] url = 'http://treasurew.com' try: ...
正则表达式初学笔记
学习自《python编程快速上手——让繁琐的工作自动化》
前置知识关于正则表达式正则表达式可以在文本中快速查找或修改某一类文本
也是爬虫等等技术的前置知识中重要的一个部分
正则表达式基本操作12345import re #导入正则表达式的库phoneNumRegex = re.compile(r'\d\d\d-\d\d\d\d') #创建正则表达式(Regex)对象mo = phoneNumRegex.search('My number is 415-555-4242.') #使用Regex对象的search()方法查找文本,返回Match对象print('Phone number found: ' + mo.group()) #使用Match对象的group()方法打印结果
正则表达式正则表达式符号速查
符号
作用
备注
\d
匹配一个数字
()
分组
可以用\来转义()
|
匹配多个分组
?
实现可选匹配
*
匹配零次或一次
+
匹配一次或多次
{& ...
基础dp练习
基础dp练习
HDU1024(m段子序列最大和,dp + 滚动数组 )错误思路
我一开始的思路
123456789设dp[i][j]:前i个数,分为j段的最大和dp[i][j] = max( dp[i-1][j] //不选第i个数 max(dp[k][j-1] + a[i], (0 < k < i)) //第i个数独立一段 dp[i-1][j] + a[i] //第i个数并入最后一段**) **:很明显,打了**的那个状态无法推到这个状态,因为最后一段的结尾未必是a[i-1]
正确思路思考过程
初做dp,力求搞懂,所以写下思路
1234567891011121314151617181920212223242526272829设dp[i][j]:选取第i个数,并把前i个数分为j段的最大和(注意:a[i]必选) dp[i][j] = max( dp[i-1][j] + a[i], //把a[i]归入最后一段 max(dp[k][j-1] + a[i], 0 < k < i) //把a[i]独立一段)//简单计算,发现 ...
简单搜索练习
kuangbin专题和洛谷专题的刷题记录,以及简单搜索总结
知识点
BFS
DFS
路径还原
白书例题(DFS + 简单剪枝)
给定整数a1、a2…、an,判断是否可以从中选出若干数,使他们的和恰好为k。
123456789101112131415161718192021222324252627282930#include<iostream>#include<algorithm>using namespace std;const int MAX_N = 20;int n;int a[MAX_N];int k;bool dfs(int i, int sum){ if(sum > k) return false;//剪枝 if(i == n) return sum == k; if(dfs(i+1, sum)) return true; if(dfs(i+1, sum+a[i])) return true; return false;}int main(){ cin >> ...
集合的整数表示
做POJ3279的时候,苦于不知道怎么枚举集合,于是看了白书中的专栏《集合的整数表示》小白表示被惊艳到了!
前置知识
左移运算符<<和右移运算符>>
整数的二进制表示
各种操作用一个整数S表示集合,通过检查S的二进制位数来判断元素有无
此方法可以方便地表示集合(如输出{0, 1, …, n-1}的所有子集,编程较困难,这里只需要for(int S = 0; S < 1 << n; S++)
如S = 6时,二进制为110,第1个元素无,第二三个元素有
下面是对整数表示集合的各种操作
方法
表示
建立空集
0
只含有第i个元素的集合
1 << i
含有全部n个元素的集合{0, 1, …, n-1}
(1 << n) - 1
判断第i个元素是否属于集合S
if(S >> i & 1)
向集合中加入第i个元素S∪{i}
S | 1 << i
从集合中去除第i个元素S\{i}
S & ~ (1 << i)
集合S和T的并 ...
最短路算法
Dijistra及其堆优化
Bellman-Ford及其队列优化(SPFA)
Floyd-Warshall算法
Dijistra算法及其堆优化Dijistra算法
适用于单源最短路径
不适用于权为负数的情况
时间复杂度O(n2)
大致思路:设起点为s
先找到离s最近的结点t,则此时dis[t]则为s到t的最短路,即dis[t]值已经固定。
用t来更新其它结点(松弛)
dis[r] = min(dis[r], dis[t] + cost[t][r]);
重复上述过程。
代码12345678910111213141516171819202122232425262728293031323334353637383940414243#include<cstdio>#include<algorithm>using namespace std;const int MAX_N = 100 + 5;const int INF = 1e9;int n, A, B;int cost[MAX_N][MAX_N];int vis[MAX_N];int dis[MAX_N];voi ...
图论刷题记录
图的遍历
最短路算法
最小生成树
图的遍历洛谷P2661(并查集求有向图最小环)也放在并查集那一章里了,装作刷题很多的样子
123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566676869707172737475//图论最小环问题, 并查集#include<cstdio>#include<algorithm>using namespace std;const int MAX_N = 2e5 + 2;int par[MAX_N];int d[MAX_N];int n;int ans = 2e9;void init(){ for(int i = 0; i <= n; ++i) { par[i] = i; d[i] = 0; }}int find(int x) //查询根节点并更新 ...
辗转相除法和扩展欧几里得算法
参考自https://www.cnblogs.com/bljfy/p/9316784.html
https://blog.csdn.net/weixin_44073496/article/details/85225355
辗转相除法证明设q = a / b;
r = a % b;
1)若r == 0,则b为a的最大公因数
2)设a和b有公因数d,则d为r的因数
3)设b和r有公因数d,则d为a的因数
先证明2):设a = xd, b = yd,则r = a - bq = d(x - yq)
所以,a和b的公因数都为r的因数,也为b和r的公因数
在证明3):b = xd,r = yd,a = bq + r = d(xq+y)
所以,b和r的公因数都为a的因数,也为a和b的公因数
所以二者公因数集相等,那么gcd也相等
所以gcd(a, b) == gcd(a, a%b)
结合1,当a%b为0时,gcd(a, 0) ==…==gcd(a, b)
代码12345int gcd(int a, int b){ if(b == 0) return a; return g ...
欧拉回路
参考自https://blog.csdn.net/qq_41730082/article/details/84927199
参考自《算法竞赛入门经典》
前置定义欧拉通路: 通过图中每条边且只通过一次,并且经过每一顶点的通路
欧拉回路: 通过图中每条边且只通过一次,并且经过每一顶点的回路
有向图的基图:忽略有向图所有边的方向,得到的无向图称为该有向图的基图。
前置简单证明不难发现,在欧拉道路中,“进”和“出”是对应的——除起点和终点外,其它点的“进出”此书应该相等。换句话说,除了起点和终点外,其它点的度数应该是偶数
无向图情况欧拉通路:设G是连通无向图,则称经过G的每条边一次并且仅经过一次的路径为欧拉通路;
欧拉回路:如果欧拉通路是回路(起点和终点是同一个顶点),则称此回路是欧拉回路
欧拉图:具有欧拉回路的无向图G成为欧拉图
有向图情况欧拉通路:设D是有向图,D的基图连通,则称经过D的每条边一次并且仅有一次的有向路径为有向欧拉通路
欧拉回路:如果有向欧拉通路是有向回路,则称此有向回路为 有向欧拉回路
欧拉图:具有有向欧拉回路的图D称为有向欧拉图
无向图中定理无向图G存在欧拉通路 ...
基础数据结构刷题记录
栈
队列
链表
并查集
洛谷P1449(栈和逆序表达式)
水题
1234567891011121314151617181920212223242526272829303132333435363738394041424344454647#include<cstdio>#include<cstring>#include<stack>using namespace std;int main(){ char str[10001]; scanf("%s", str); int len = strlen(str); int num = 0; stack<int> s; for(int i = 0; i < len; ++i) { if(str[i] >= '0' && str[i] <= '9') { num *= 10; ...