斯坦福CS106A作业4
这次的作业是做小时候经常玩的猜单词游戏。/*
* File: Hangman.java
* ------------------
* This program will eventually play the Hangman game from
* Assignment #4.
*/
import acm.graphics.*;
import acm.program.*;
import acm.util.*;
import java.awt.*;
import java.io.*;
import java.util.ArrayList;
import java.util.List;
public class Hangman extends ConsoleProgram {
/***********************************************************
* CONSTANTS *
******************* ...
浙大数据结构课程总结
今天把浙大数据结构Mooc的期末考试完成了，结果还算不错。通过这个课程的学习，我从一个对数据结构一窍不通的人变成了一个对数据结构略知一二的人。如果让我再从头学一遍的话，我会先把C语言学好，并且买老师的参考书。后续时间里应该会把课程再复习一遍，用C语言把代码再实现一遍，然后去参加PAT的甲级考试。
这里把编程题贴一下，是一道中序后后续遍历推测前序遍历的问题，之前有做过类似的，还是比较简单的。
习题
7-1 根据后序和中序遍历输出先序遍历（8 分）本题要求根据给定的一棵二叉树的后序遍历和中序遍历结果，输出该树的先序遍历结果。输入格式:第一行给出正整数N(≤30)，是树中结点的个数。随后两行，每行给出N个整数，分别对应后序遍历和中序遍历结果，数字间以空格分隔。题目保证输入正确对应一棵二叉树。输出格式:在一行中输出Preorder:以及该树的先序遍历结果。数字间有1个空格，行末不得有多余空格。输入样例:72 3 1 5 7 6 41 2 3 4 5 6 7输出样例:Preorder: 4 1 3 2 6 5 7
# -*- coding: utf-8 -*-
"""
Created o ...
浙大数据结构Week11
课程地址：https://www.icourse163.org/course/ZJU-93001笔记中图片均来自此mooc中讲义。
这周是最后一周，内容为散列表，下面回顾下。
Part1:回顾1.散列表如果我们有一组数据，这组数据不方便比较大小，那么如何高效地查找其中的元素呢？这就有了散列表。散列表的基本思想就是构造一个映射h，将需要查找的元素映射到一个值上，这个值就是数组存储的地址。但是不同的关键字可能会映射到同一个地址，这就有了冲突，如何解决冲突是我们需要关心的问题。
从散列函数的定义我们可以看出，散列函数应该构造简单，并且尽量减少冲突，老师的课件中介绍了很多种处理方法，这里不一一列出了。下面着重介绍冲突处理方法。
2.冲突处理方法这里老师其是就介绍了两种冲突处理方法，第一种是遇到冲突就换一个位置，第二种是把冲突的对象组织在一起。第一种被称为开放地址法，第二种被称为链地址法。
开放地址法下面分别看下
线性探测法简单来说线性探测法就是在冲突的时候不停地右移，如果到底则从头开始，直至找到一个空的位置。我们从下图看下具体的过程。我们来分析下散列表的性能，这里分别计算成功平均查找长度(AS ...
浙大数据结构Week10
课程地址：https://www.icourse163.org/course/ZJU-93001笔记中图片均来自此mooc中讲义。
这周接着上周又补充了一些排序算法，这里继续回顾下。
Part1:回顾1.快速排序快速排序的思路是这样的，首先选取一个pivot(枢轴元素)，然后将待排数组分为两部分，小于pivot的元素，大于pivot的元素，小于pivot的元素放在pivot元素的前面，大于pivot的元素放在pivot后面，然后对小于pivot的元素和大于pivot的元素分别再采取这个方式处理，具体过程如下：
显然快速排序有随机性，出现随机性的原因是pivot的选取缘故，这里来看个最坏的情形。
为了避免这种情形，老师建议取头，中，尾元素的中位数作为pivot。这里老师还提到在小规模数据时，快速排序可能还不如插入排序，所以老师提出如下解决方案：
2.表排序在对很庞大的结构排序时，交换两个元素的时间和空间都是很大的，如果使用之前的算法效果会不好，所以就有了表排序这种间接排序。表排序的意思构造指针数组，排序时不交换元素本身，只交换指向元素的指针来排序，可以参考下面一个图来理解：这里的意思是根 ...
北理Python爬虫Week3
课程地址:https://www.icourse163.org/course/BIT-1001870001笔记内容结合课件整理。
这里对北理爬虫课程第三周内容回顾,本周主要介绍了正则表达式
1.正则表达式的概念正则表达式是用来简洁表达一组字符串的表达式正则表达式是一种通用的字符串表达框架进一步正则表达式是一种针对字符串表达“简洁” 和“特征” 思想的工具正则表达式可以用来判断某字符串的特征归属
正则表达式的常用操作符
操作符
说明
实例
.
表示任何单个字符
[ ]
字符集，对单个字符给出取值范围
[abc]表示a、 b、 c，[a‐z]表示a到z单个字符
非字符集，对单个字符给出排除范围
abc表示非a或b或c的单个字符
*
前一个字符0次或无限次扩展
abc* 表示 ab、 abc、 abcc、 abccc等
+
前一个字符1次或无限次扩展
abc+ 表示 abc、 abcc、 abccc等
?
前一个字符0次或1次扩展
abc? 表示 ab、 abc
|
左右表达式任意一个
abc|def 表示 abc、 def
...
斯坦福CS106A作业3
这次作业是设计一个很有意思的小游戏。
problem1:
这题还是比较简单的，只要看一下课本第10章即可。
/*
* File: MouseReporter.java
* -----------------------------
* Output the location of the mouse to a label on the
* screen. Change the color of the label to red when
* the mouse touches it.
*/
import java.awt.Color;
import java.awt.event.MouseEvent;
import acm.graphics.*;
import acm.program.*;
public class MouseReporter extends GraphicsProgram {
// A constant for the x value of the label
private static ...
北理Python爬虫Week2
课程地址:https://www.icourse163.org/course/BIT-1001870001笔记内容结合课件整理。
这里对北理爬虫课程第二周内容回顾,本周主要介绍了Beautiful Soup库以及信息标记与提取方法。
1.Beautiful Soup库入门Beautiful Soup库是一个解析网络数据的python库，下面使用下。
import requests
r = requests.get('https://python123.io/ws/demo.html')
r.text
'<html><head><title>This is a python demo page</title></head>\r\n<body>\r\n<p class="title"><b>The demo python introduces several python courses.</b></p>\r\n<p class=&quo ...
Hexo博客next主题数学公式渲染问题
请忽略下述方法，具体的解决方法为换个目录重装，具体步骤见
Hexo博客next主题数学公式重复显示
之前关于hexo渲染数学公式问题纠结了很久，而且我这个问题非常的奇葩:
公式渲染了一遍，但是原来的代码也会显示，非常奇怪。后来找到一篇博客https://ranmaosong.github.io/2017/11/29/hexo-support-mathjax/看了这篇文章之后解决了大部分问题，但是有时候还是会出现公式无法渲染的问题，我看了一下next主题的_config.yml的mathjax配置# MathJax Support
mathjax:
enable: true
per_page: false
cdn: //cdn.mathjax.org/mathjax/latest/MathJax.js?config=TeX-AMS-MML_HTMLorMML
结合博客一看发现这边cdn似乎要修改# MathJax Support
mathjax:
enable: true
per_page: true
#cdn: https://cdnjs.cloudflar ...
浙大数据结构Week9
课程地址：https://www.icourse163.org/course/ZJU-93001笔记中图片均来自此mooc中讲义。
这周主要讲了几种排序算法，下面回顾下。
Part1:回顾首先老师提了几个前提条件。
这里内部排序是指排序的数据可以一次性在内存中进行排序，与此对应的是外部排序，外部排序是指数据量很大，超过内存容量，无法一次性排序完成。
注：下述的$N$均代表排序元素个数，数组元素记为$A[i]$
1.冒泡排序冒泡排序的算法是这样的，一共$N$轮，第$i$轮对前$N-i+1$个元素进行如下操作：从第一个元素开始，如果后一个元素比前一个元素小，则交换两个元素，操作完一步之后对第二个元素重复此操作，直至第$N-i+1$个元素。这样第$i$轮可以保证第$N-i+1$个元素是前$N-i+1$个元素中最大元素，所以第$1$轮使得第$N$个元素为最大元素，第$2$轮使得第$N-1$个元素为第二大的元素，以此类推$N$轮之后排序完成。从以上过程中可以看出，只有两个元素不相等时才会进行交换，所以冒泡排序是稳定的。伪代码如下：
2.插入排序插入排序同样进行$N$轮操作，第$i$轮将第$ ...
Hexo博客sitemap报错
今天想结合网上的教程把博客提交百度谷歌收录,但是碰到一个巨坑,这里记录下给后续的小伙伴参考下。在生成sitemap.xml文件之后,提交谷歌之后sitemap.xml解析错误。出现如下报错:
这个问题整整花费了一个下午才搞定,网上没找到几个相关资料,最后参考一位大佬的博客才找明原因。出现这个问题是由于文章标题里有&导致,只要去除了标题里的&即可。
参考文章: https://www.voidking.com/2016/12/02/deve-hexo-sitemap/
北理Python爬虫Week1
课程地址:https://www.icourse163.org/course/BIT-1001870001笔记内容结合课件整理。
这里对北理爬虫课程第一周内容回顾,本周主要介绍了requests库的使用
1.Request库入门首先来看下request的基本使用,基本使用如下
requests.get(url, params=None, **kwargs)
url : 拟获取页面的url链接
params : url中的额外参数，字典或字节流格式，可选
**kwargs: 12个控制访问的参数
import requests
r=requests.get("http://www.baidu.com")
print(r.status_code)
r.text[:400]
200
'<!DOCTYPE html>\r\n<!--STATUS OK--><html> <head><meta http-equiv=content-type content=text/html;charset=utf-8><me ...
浙大数据结构Week8
课程地址：https://www.icourse163.org/course/ZJU-93001笔记中图片均来自此mooc中讲义。
这周是图的最后一部分内容，介绍的了最小生成树以及拓扑排序，下面回顾下。
Part1:回顾1.最小生成树首先看下最小生成树的定义。最小生成树这个名字中有三重信息，首先树，其次是生成树，最后是最小生成树，具体如下。生成最小生成树使用的是贪心算法，一般有两种，分别为Prim算法以及Kruskal算法，下面分别介绍。
Prime算法Prime算法是让一颗小数长大。具体思路是先任取一个点a包括在树中，选取距离树中顶点距离最短的边，然后将这个边及对应顶点b包括在树中，更新不在树中的点距离树的最短距离，接来下重复此操作即可。注意由于只增加了点b，所以在更新最短距离的时候只要更新b的相邻点即可。可以看到，这个算法和之前讲的Dijkstra算法很相似，下面一起列出。
Kruskal算法Kruskal算法是每次选取最小权重的边，如果加入此边不形成回路，则将边及顶点加入生成树中。在此过程中，判断是否形成回的方法是使用并查集，每次选取权重最小的边使用最小堆。
2.拓扑排序首先 ...