春招学习第三天(3/30)
今天是周末,但依然还是按时参加了周赛,学习还是辛苦啊。但我认为,只要有收获,就是值得的。
205. 同构字符串 (力扣每日一题)
给定两个字符串 s 和 t,判断它们是否是同构的。
如果 s 中的字符可以被替换得到 t ,那么这两个字符串是同构的。
所有出现的字符都必须用另一个字符替换,同时保留字符的顺序。两个字符不能映射到同一个字符上,但字符可以映射自己本身。
示例 1:
输入: s = "egg", t = "add"
输出: true
示例 2:
输入: s = "foo", t = "bar"
输出: false
示例 3:
输入: s = "paper", t = "title"
输出: true
AC代码:
public boolean isIsomorphic(String s, String t) { if (s.length()==0){ return true; } HashMap<Character,Character> sTot = new HashMap<>(); char[] arrayS= s.toCharArray(); char[] arrayT= t.toCharArray(); for (int i = 0; i <s.length() ; i++) { if (sTot.containsKey(arrayS[i])){ if (sTot.get(arrayS[i])!=arrayT[i]){ return false; } } else{ if (!sTot.containsValue(arrayT[i])){ sTot.put(arrayS[i],arrayT[i]); } else{ return false; } } } return true; }
今天滴周赛那叫一个难啊,第二题用优先队列做了半天,但是死活错误,后来到群里一问,原来有的苹果还没有长出来就被我给吃掉了。我真是一个小天才,那难怪会错呢
5637. 判断字符串的两半是否相似 (力扣221周赛第一题)
给你一个偶数长度的字符串 s 。将其拆分成长度相同的两半,前一半为 a ,后一半为 b 。
两个字符串 相似 的前提是它们都含有相同数目的元音('a','e','i','o','u','A','E','I','O','U')。注意,s 可能同时含有大写和小写字母。
如果 a 和 b 相似,返回 true ;否则,返回 false 。
示例 1:
输入:s = "book"
输出:true
解释:a = "bo" 且 b = "ok" 。a 中有 1 个元音,b 也有 1 个元音。所以,a 和 b 相似。
示例 2:
输入:s = "textbook"
输出:false
解释:a = "text" 且 b = "book" 。a 中有 1 个元音,b 中有 2 个元音。因此,a 和 b 不相似。
注意,元音 o 在 b 中出现两次,记为 2 个。
AC代码:
public boolean halvesAreAlike(String s) { String a=s.toLowerCase().substring(0,s.length()/2); String b=s.toLowerCase().substring(s.length()/2,s.length()); char[] aa=a.toCharArray(); char[] bb=b.toCharArray(); int countA=0; int countB=0; for (int i = 0; i <s.length()/2 ; i++) { if (aa[i]=='a'||aa[i]=='e'||aa[i]=='i'||aa[i]=='o'||aa[i]=='u'){ countA++; } Character cb=bb[i]; //System.out.println(cb); if (cb=='a'||cb=='e'||cb=='i'||cb=='o'||cb=='u'){ countB++; } } //System.out.println(a); //System.out.println(b); return countA==countB; }
5210. 球会落何处 (周赛第三题)
这题看了一下大概就是模拟落球的过程,用一个二维数组来记下走过的位置能不能通就可以了。如果每次都重新模拟应该会超时。大概吧
用一个大小为 m x n 的二维网格 grid 表示一个箱子。你有 n 颗球。箱子的顶部和底部都是开着的。
箱子中的每个单元格都有一个对角线挡板,跨过单元格的两个角,可以将球导向左侧或者右侧。
将球导向右侧的挡板跨过左上角和右下角,在网格中用 1 表示。
将球导向左侧的挡板跨过右上角和左下角,在网格中用 -1 表示。
在箱子每一列的顶端各放一颗球。每颗球都可能卡在箱子里或从底部掉出来。如果球恰好卡在两块挡板之间的 "V" 形图案,或者被一块挡导向到箱子的任意一侧边上,就会卡住。
返回一个大小为 n 的数组 answer ,其中 answer[i] 是球放在顶部的第 i 列后从底部掉出来的那一列对应的下标,如果球卡在盒子里,则返回 -1 。
示例 1:
输入:grid = [[1,1,1,-1,-1],[1,1,1,-1,-1],[-1,-1,-1,1,1],[1,1,1,1,-1],[-1,-1,-1,-1,-1]]
输出:[1,-1,-1,-1,-1]
解释:示例如图:
b0 球开始放在第 0 列上,最终从箱子底部第 1 列掉出。
b1 球开始放在第 1 列上,会卡在第 2、3 列和第 1 行之间的 "V" 形里。
b2 球开始放在第 2 列上,会卡在第 2、3 列和第 0 行之间的 "V" 形里。
b3 球开始放在第 3 列上,会卡在第 2、3 列和第 0 行之间的 "V" 形里。
b4 球开始放在第 4 列上,会卡在第 2、3 列和第 1 行之间的 "V" 形里。
AC代码:
class Solution { public int[] findBall(int[][] grid) { int[][] dp = new int[grid.length][grid[0].length]; int[] res = new int[grid[0].length]; for (int i = 0; i < res.length; i++) { res[i]=findBallDfs(grid,dp,0,i); } return res; } public int findBallDfs(int[][] grid,int [][] dp,int i,int j){ if(i>=grid.length){ return j; } if (i<0||j>=grid[0].length){ return -1; } else{ //System.out.println("i: "+i+"j: "+j); if (dp[i][j]!=0){ return dp[i][j]; } if (grid[i][j]==1){ if (j+1>=grid[0].length || grid[i][j+1]==-1){ return -1; } else { dp[i][j]=findBallDfs(grid,dp,i+1,j+1); } } else{ if (j-1<0||grid[i][j-1]==1){ return -1; } else{ dp[i][j]=findBallDfs(grid,dp,i+1,j-1); } } return dp[i][j]; } } }
大数据学习系列
1. URL、HTTP和HTTPS
1.1. URI和URL
URI:Uniform Resource Identifier。统一资源标志符。
URL:Uniform Resource Locator。 统一资源定位符,简称网址,用于唯一确定互联网中的的资源。
URL是URI的子集,即每个URL都是URI。URI还包括一个子类叫做URN
URN全称为Universal Resource Name,即统一资源名称。URN只命名资源而不指定如何定位资源。
URI、URL、URN的关系如图所示。
1.2. HTTP和HTTPS
URL的起始为http
或https
,表示访问资源的协议类型,其中
- HTTP全称为Hyper Text Transfer Protocal,即超文本传输协议,是从网络传输超文本数据到本地浏览器的传输协议,它能保证高效而准确的传送超文本文档。目前广泛使用的是HTTP 1.1版本;
- HTTPS全称为Hyper Text Transfer Protocol over Secure Socket Layer,即以安全为目标的HTTP通道,传输内容都是通过SSL加密,保证数据传输的安全。
2. 网页源代码
HTML全称为Hyper Text Markup Language,即超文本标记语言。事实上,我们每次输入网址后,网站的返回结果即为HTML代码,经过浏览器的解析呈现在用户眼前。
3. HTTP请求过程
我们在浏览器中输入URL,回车之后浏览器向网站服务器发送请求(request),网站服务器处理该请求并返回响应(response),其中包含了网页源代码,通过浏览器解析,呈现在我们眼前。
打开Chrome浏览器,选择菜单中更多工具
-> 开发者工具
,或直接使用快捷键Ctrl + Shift + I
。选择其中的Network
标签卡,即网络监听组件。输入百度首页的URLhttps://www.baidu.com/并按回车。可以看到,`Network`标签卡下方出现了多条记录,每条记录表示一次请求和响应过程。
Name
表示请求的名称,一般为URL按斜杠/分割的最后一部分;Status
表示响应的状态码,之后会详细介绍;Type
表示请求的资源类型,document
为HTML文档,还可以是png
、gif
、svg
之类的媒体资源或script
之类的JavaScript脚本资源等;Initiator
表示请求源,即发起请求的对象或进程;Size
表示请求的资源大小;Time
表示发起请求到得到响应所用的时间;Waterfall
表示网络请求的可视化瀑布流。
点击请求名称为www.baidu.com
的记录,查看详细信息,在Headers
标签卡中,General
部分表示概况, Response Headers
和Request Headers
部分分别表示请求头和响应头,之后会详细介绍。
4. HTTP请求
HTTP请求由4部分组成,分别为请求方法、请求URL、请求头和请求体。
4.1. 请求方法
常用的请求方法有2种,GET和POST。
在浏览器中输入URL并按回车,便发起了一个GET请求,请求的参数直接包含在URL中。例如,在百度中搜索Python,URL为https://www.baidu.com/s?wd=Python 这里的参数wd
表示搜索关键词。POST请求大多在表单提交时发起。POST请求数据以表单形式传输,不以URL参数的形式体现。
GET和POST请求方法区别如下:
- GET请求中的参数包含在URL里面,数据可以在URL中看到,而POST请求的URL不会包含这些数据,数据都是通过表单形式传输的,会包含在请求体中;
- GET请求提交的数据最多只有1024字节,而POST方式没有限制。
除了GET和POST请求方法,还有一些其他的请求方法,如下表所示。
请求方法 | 定义 |
---|---|
GET | 请求页面,并返回页面内容 |
HEAD | 类似于GET请求,只不过返回的响应中没有具体的内容,用于获取报头 |
POST | 大多数用于提交表单或者上传文件,数据包含在请求体中 |
PUT | 从客户端向服务端传送的数据取代指定文档中的内容 |
DELETE | 请求服务器删除指定的页面 |
CONNECT | 把服务器当作跳板,让服务器代替客户端访问其他页面 |
OPTIONS | 允许客户端查看服务器的性能 |
TRACE | 回显服务器收到的请求,主要用于测试或诊断 |
4.2. 请求头
请求头用于存储请求的附加信息。上一步中百度的请求头在Chrome开发者工具中如下所示。
Accept: text/html,application/xhtml+xml,application/xml;q=0.9,image/webp,image/apng,*/*;q=0.8 Accept-Encoding: gzip, deflate, br Accept-Language: en-US,en;q=0.9,zh-CN;q=0.8,zh;q=0.7 Cache-Control: max-age=0 Connection: keep-alive Cookie: BAIDUID=1D6F676DA004A4EF04EC18B523B1188E:FG=1; BIDUPSID=1D6F676DA004A4EF04EC18B523B1188E; PSTM=1522837431; BD_UPN=12314353; delPer=0; BD_HOME=0; H_PS_PSSID=1459_21112_26350_22160 Host: www.baidu.com Upgrade-Insecure-Requests: 1 User-Agent: Mozilla/5.0 (Windows NT 6.1; Win64; x64) AppleWebKit/537.36 (KHTML, like Gecko) Chrome/70.0.3538.67 Safari/537.36
常用的请求头信息包括:
Accept
表示客户端可接受的资源类型;Accept-Language
表示客户端可接受的语言类型;Accept-Encoding
表示客户端可接受的内容编码;Cookie
也称为Cookies,网站用于维持会话而存储在用户本地的数据,之后会给出具体例子;Host
表示请求资源的主机;Referer
表示该请求的页面来源,网站服务器常用该信息做来源统计和防盗链处理;User-Agent
表示客户端的操作系统(及版本)和浏览器(及版本),网站服务器有时会验证该信息以识别爬虫。
请求体一般只在POST请求中包含表单数据。GET请求的请求体为空。
5. HTTP响应
HTTP响应由3部分组成,分别为响应状态码、响应头和响应体。
响应状态码表示网站服务器的响应状态,常用的HTTP响应状态码如下表所示。
响应状态码 | 定义 |
---|---|
1** | 表示信息提示 |
200 | 成功,即服务器已成功处理了请求 |
403 | 禁止访问,即服务器拒绝此请求 |
404 | 未找到,即服务器找不到请求的网页 |
500 | 服务器内部错误 |
响应头用于存储响应的附加信息。上一步中百度的响应头在Chrome开发者工具中如下所示。
Bdpagetype: 1 Bdqid: 0xb2eb9adc00054e1c Cache-Control: private Connection: Keep-Alive Content-Encoding: gzip Content-Type: text/html Cxy_all: baidu+d1fabdd2162dadb51d390e4c31d61e29 Date: Sat, 20 Oct 2018 12:01:19 GMT Expires: Sat, 20 Oct 2018 12:00:23 GMT Server: BWS/1.1 Set-Cookie: delPer=0; path=/; domain=.baidu.com Set-Cookie: BDSVRTM=0; path=/ Set-Cookie: BD_HOME=0; path=/ Set-Cookie: H_PS_PSSID=1459_21112_26350_22160; path=/; domain=.baidu.com Strict-Transport-Security: max-age=172800 Transfer-Encoding: chunked Vary: Accept-Encoding X-Ua-Compatible: IE=Edge,chrome=1
常用的响应头信息包括:
Content-Encoding
表示资源的内容编码;Content-Type
表示资源类型,常用的类型包括:
text/html
为HTML网页;application/x-javascript
为JavaScript脚本;image/jpeg
为图片;
Date
表示响应产生的时间;Expires
表示响应的过期时间,如果重新访问该资源且没超过该过期时间,则可以直接从浏览器缓存中加载资源,降低网站服务器负载,缩短加载资源时间;Server
表示网站服务器的信息,如名称和版本;Set-Cookie
表示浏览器需要设置的Cookies值,下次的请求可以加入这些Cookies值。
响应体为资源的内容,如HTML网页源代码、JavaScript脚本或图片的二进制数据。
6. Cookies
Cookies是网站用于维持会话而存储在用户本地的数据。
每一条记录就是一个Cookie,其中包含了丰富的信息:
Name
表示Cookie的名称;Value
表示Cookie的值;Domain
表示Cookie的域名,即只有来自该域名的网页才能访问该Cookie;Path
表示Cookie的使用路径,即只有该路径的网页才能访问该Cookie;Expires/Max-Age
表示Cookie的有效时间;Size
表示Cookie的大小。
最后还写了一个基础的不能再基础的HTML,但是太菜了,就不放上来了。
1.3 爬取百度网页
之前其实是有学习过爬虫的,但是没有具体应用,所以搁置了这项技术挺久的,最近因为毕设的原因决定重新捡起来学习学习
1. GET方法
调用程序包requests的函数get()发送HTTP的GET请求,其中
• 第1个参数url表示网页的URL链接,这里打开百度的URL链接;
• 参数params表示请求的查询字符串字典,即URL中问号后面的部分;
• 返回结果为类型为Response的HTTP响应。
import requests response = requests.get("http://www.baidu.com")
使用响应的属性encoding得到或设置内容编码,这里设置编码为UTF-8。
In [3]:response.encoding = 'utf-8'
使用响应的属性text得到响应体的内容。
print(response.text)
使用响应的属性status_code得到响应状态码,200表示成功。
response.status_code
使用响应的属性headers得到响应头。
response.headers
在真实数据爬取中,经常由于网络原因导致HTTP请求得不到及时响应而造成程序卡住,可以在调用程序包requests的函数get()中指定参数timeout设置超时时间,如果超时则产生异常ConnectTimeout。例如,这里试图爬取Github并设置0.1秒超时。
response = requests.get("https://github.com", timeout=0.1)
2. POST方法
调用程序包requests的函数get()发送HTTP的GET请求,其中
• 第1个参数url表示网页的URL链接,这里将请求发送到一个测试网页http://httpbin.org/post;
• 参数data表示请求提交的表单数据字典;
• 返回结果为类型为Response的HTTP响应。
data = {'username':'sjtu','password':'123456'} response = requests.post("http://httpbin.org/post", data) print(response.text)
完整代码如下:
import requests response = requests.get("http://www.baidu.com") response.encoding = 'utf-8' print(response.text) print(response.status_code) print(response.headers) response = requests.get("https://github.com", timeout=30) print(response) data = {'username': 'sjtu', 'password': '123456'} response = requests.post("http://httpbin.org/post", data) print(response.text)
爬取结果