今天是周末，但依然还是按时参加了周赛，学习还是辛苦啊。但我认为，只要有收获，就是值得的。

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请求方法，还有一些其他的请求方法，如下表所示。

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响应状态码如下表所示。

响应头用于存储响应的附加信息。上一步中百度的响应头在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)

爬取结果