# 算法记录（二）





[Leecode 116 填充每个节点的下一个右侧节点指针](https://leetcode.cn/problems/populating-next-right-pointers-in-each-node/)

> 给定一个 完美二叉树 ，其所有叶子节点都在同一层，每个父节点都有两个子节点。二叉树定义如下：
> 填充它的每个 next 指针，让这个指针指向其下一个右侧节点。如果找不到下一个右侧节点，则将 next 指针设置为 NULL。初始状态下，所有 next 指针都被设置为 NULL。

```java
struct Node {
  int val;
  Node *left;
  Node *right;
  Node *next;
}
```
![图片.png](http://malyue.cn/static/img/2c26df8e789aebed326d8c3d08c7ee4f.%C3%A5%C2%9B%C2%BE%C3%A7%C2%89%C2%87.png)

```java
输入：root = [1,2,3,4,5,6,7]
输出：[1,#,2,3,#,4,5,6,7,#]
解释：给定二叉树如图 A 所示，你的函数应该填充它的每个 next 指针，以指向其下一个右侧节点，如图 B 所示。序列化的输出按层序遍历排列，同一层节点由 next 指针连接，'#' 标志着每一层的结束。
```

两种思路，第一种比较好想，就是层序遍历

```java
// 层序遍历解法
        if(root == null) return root;
        Queue<Node> queue = new LinkedList<Node>();
        queue.add(root);
        while(!queue.isEmpty()) {
            // 一层的个数
            int size = queue.size();
            for(int i = 0 ;i<size;i++) {
                // 出队
                Node node = queue.poll();
                if(i<size-1) {
                    node.next = queue.peek();
                }

                if(node.left != null) queue.add(node.left);
                if(node.right != null) queue.add(node.right);
            }
        }
        return root;
```

层序遍历很好理解，就是创建一个队列，然后每次向队列里加入一层，当队列非空，则出队且获得当前队列的元素个数，这个元素个数就是当前这层的个数，然后分别将每个出队的元素的左右孩子加入队列，重复以上步骤，直到队列为空

而在这个题目中，如果根据层序遍历来实现的话，next指针直接指向出队后当前队列的队头即可，当然要注意，如果是当前这一层的最后一个，则直接指向null，好了这道题目就这个解法

那第二种解法就比较巧妙，不用额外的空间，这里是利用了前一个结点创建的`next指针`

很显而易见，每个节点的两个孩子节点之间可以直接通过next指针相连，而不同节点的两个孩子节点之间就无法直接相连了，这是我们要解决的问题

我们是从上往下进行连接的，这时候我们发现，我们要连接第N+1层的next指针的时候，其实我们是站在第N层的位置进行连接的，换句话说，我们在连接第N+1层的next指针的时候，我们是已经连好了第N层的next指针，所以可以通过第N层的next指针取将不同节点的两个孩子节点相连

即`root.right.next = root.next.left`
代码如下，这里用的是递归解法

```java
// 递归解法
        if(root == null || root.left == null) {
            return root;
        }
        // 将左孩子的下一个指向右孩子
        root.left.next = root.right;
        if(root.next!=null){
            root.right.next = root.next.left;
        }else{
            root.right.next = null;
        }
        connect(root.left);
        connect(root.right);
        
        return root;
```

算法（三）

# 算法刷题记录
## 贪心算法



-  概念

    所谓的贪心算法，即在对一个问题进行求解的时候，总是选择在当时情况下看来最好的一个选择，即不从整体最优上考虑，而是选择局部最优解
    
    这个算法没有一个固定的模板，主要是选择对应的贪心策略.
    
    需要注意的是,贪心算法不一定能得到整体最优解，且选择的贪心策略必须具备无后效性，即某个状态以后的过程不会影响以前的过程，只与当前的状态有关
    
    所以我认识，贪心算法最大的难点在于，什么时候我们才要用贪心，那这个没有什么好的方法，如果数学好那可以用数学方法来进行推导，不行的话则用几个特例来进行尝试，至于怎么选择例子，只能多刷题了
    
-  基本思路

    将求解的问题分成若干个子问题，再对每个子问题一一进行求解，得到子问题的局部最优解，最后将子问题的解合并成原来解中的一个解
    
接下来直接先照常看看Leecode的题目
### [Leecode 605 种花问题](https://leetcode.cn/problems/can-place-flowers/)

> 假设有一个很长的花坛，一部分地块种植了花，另一部分却没有。可是，花不能种植在相邻的地块上，它们会争夺水源，两者都会死去。
> 给你一个整数数组  flowerbed 表示花坛，由若干 0 和 1 组成，其中 0 表示没种植花，1 表示种植了花。另有一个数 n ，能否在不打破种植规则的情况下种入 n 朵花？能则返回 true ，不能则返回 false。

```js
输入：flowerbed = [1,0,0,0,1], n = 1
输出：true

输入：flowerbed = [1,0,0,0,1], n = 2
输出：false
```

题目其实很好理解，简单来说，就是在数组中，1的左右两边不能有两个1，在满足这个条件的情况下，尽可能的把0反转为1

在这里的话贪心就在于，我从左往右遍历，只要能种花就一定会种,因为对于每个位置来说，他的局部最优解就是在满足条件下种花

数学的角度可能不会推，只能大概猜想一下，即拆成n个子问题就是在当前位置是否要种花

那我们从左往右遍历，在当前位置我们只需要考虑右边的情况，如果我们在当前位置可以种花的情况下不种花的话，在后一个位置你无法保证其一定可以种花，在后一个位置种花的概率不为100%，即可能得到的花会比之前少，那我还是选择在前面尽可能的增加花的数量比较好，且你后面不管如何选择，都对我前面是没有影响的，我前面一定是得到了我在当前长度的花坛里得到的最优解，那就顺着这个情况下去，我们总能得到一个在最终长度下的最优解

```java
class Solution {
    public boolean canPlaceFlowers(int[] flowerbed, int n) {
        int i =0;
        while(i<flowerbed.length) {
            // 分为几种情况
            // 如果当前没有花
            if(flowerbed[i] == 0) {
                // 如果没有下个位置了，则直接种花
                if(i+1 == flowerbed.length) {
                    n--;
                    i++;
                }
                //如果下一个位置没种花
                else if(flowerbed[i+1]==0){
                    //则在当前位置种花
                    n--;
                    // 跳过一个位置
                    i += 2;
                    // continue;
                }
                // 如果下一个位置种花了
                else if(flowerbed[i+1]==1){
                    // 即010情况，则直接到0的后一个
                    i += 3;
                }
            }else if(flowerbed[i] == 1) {
                i += 2;
            }
            if(n <= 0) return true;
        }
        return false;
    }
}
```

换一道题试试看，还是简单题先试一下


### [Leecode 561 数组拆分](https://leetcode.cn/problems/array-partition/)
> 给定长度为 2n 的整数数组 nums ，你的任务是将这些数分成 n 对, 例如 (a1, b1), (a2, b2), ..., (an, bn) ，使得从 1 到 n 的 min(ai, bi) 总和最大。
返回该 最大总和 。


```js
入：nums = [1,4,3,2]
输出：4
解释：所有可能的分法（忽略元素顺序）为：
1. (1, 4), (2, 3) -> min(1, 4) + min(2, 3) = 1 + 2 = 3
2. (1, 3), (2, 4) -> min(1, 3) + min(2, 4) = 1 + 2 = 3
3. (1, 2), (3, 4) -> min(1, 2) + min(3, 4) = 1 + 3 = 4
所以最大总和为 4

输入：nums = [6,2,6,5,1,2]
输出：9
解释：最优的分法为 (2, 1), (2, 5), (6, 6). min(2, 1) + min(2, 5) + min(6, 6) = 1 + 2 + 6 = 9
```

题意就是如何进行两两分组得到多个最小值，且这些最小值的总和最大

如果是想要总和最小就很明显了，那样的话就是每次选择一个最小的和一个最大的为一组就可以，其实就是等价于选择数组种最小的几个数相加

但是总和最大的话就要考虑别的情况了，那我们分成多个子问题，这里的子问题就是分成多个分组，每次分组怎么选择，那我们就先排个序吧，其实最需要注意的就是我们需要减小较小值的影响，例如[6,2,6,5,1,2]先排序[1,2,2,5,6,6],然后从左往右开始找，我的贪心策略就是每次找一个最接近当前值的，即当前索引的下一位，即[1,2],[2,5],[5,6]

至于如何证明这个贪心策略是正确的，其实我还没想好,还是老样子，数学推导不会，那我们就靠猜来试一下.

我们要最大值，那么其实肯定得减小最小值的影响，类似于田忌赛马，我们不能拿最大值去和最小值一组的，这点就不需要证明了，那我们就是拿剩下的值里的下等马去和当前取出来的值来进行分组。

或者换个思路，其实求这个最大值的话，就是在数组所有数的总和-(每组的损失值的总和)，每组的损失值就是|a1-a2|，那我们要使得最后的值最大，那就是将使得损失最小，最自然是选择一个最接近的

```java
class Solution {
    public int arrayPairSum(int[] nums) {
        // 策略就是排序后，每次都选择一个最接近
        Arrays.sort(nums);
        int result = 0;
        for(int i =0;i<nums.length;i+=2 ){
            result+=nums[i];
        }
        return result;
    }
}
```

这两道题都是属于一眼能看出来的.接下来就再试一下难一点的题是什么样的

算法（二）

# Go微服务

## 	ProtoBuf

​		在网络通信和通用数据交换等应用场景中经常使用的技术是JSON和XML，在微服务架构中则一般使用另外一个数据交换的协议的工具==ProtoBuf==

​		全称：protocol buffers，*即协议缓冲区*，是一种与语言无关、与平台无关的可扩展机制，用于序列化结构化数据

​		和json/xml最大区别：json/xml基于文本格式，ProtoBuf是二进制格式

​	首先先去下载protoc

- [Windows 64位 点这里下载](https://link.juejin.cn?target=https%3A%2F%2Fgithub.com%2Fprotocolbuffers%2FProtoBuf%2Freleases%2Fdownload%2Fv3.20.2%2Fprotoc-3.20.2-win64.zip)

- [Linux 64位 点这里下载](https://link.juejin.cn?target=https%3A%2F%2Fgithub.com%2Fprotocolbuffers%2FProtoBuf%2Freleases%2Fdownload%2Fv3.20.2%2Fprotoc-3.20.2-linux-x86_64.zip)

​	之后将解压后的bin目录放到环境变量中，在命令行执行protoc，若有输出则配置成功

这时候在go中使用，先在goland里写一段protoc代码

```protobuf
syntax = "proto3";

package hello;

option go_package = "./;hello";

message Say{
  int64 id = 1;
  string hello = 2;
  repeated string word = 3;
}
```

在文件的目录下执行

```properties
protoc --go_out=. hello.proto
```

这时候可能会报错

```go
'protoc-gen-go' 不是内部或外部命令，也不是可运行的程序
或批处理文件。
--go_out: protoc-gen-go: Plugin failed with status code 1.
```

这时候是因为缺少了差距，下载即可

```go
go get -u google.golang.org/protobuf/cmd/protoc-gen-go
go install google.golang.org/protobuf/cmd/protoc-gen-go
go get -u google.golang.org/grpc/cmd/protoc-gen-go-grpc
go install google.golang.org/grpc/cmd/protoc-gen-go-grpc
```

代码解析：

```protobuf
// 定义proto版本号
syntax = "proto3";

// 定义包名，用于proto
package hello;

// 定义go包名，用于生成的.pd.go文件
option go_package = "./;hello";

// 定义消息体
message Say{
  int64 id = 1;
  string hello = 2;
  repeated string word = 3;
}
```

- synatx:必写，而且要定义在第一行，不写默认proto2
- package：定义proto文件的包名
- option go_package：定义生成的pb.go的包名，通常在proto文件中定义，如果不在proto文件中定义，也可以使用protoc生成代码时指定文件包名
- message：用于定义消息结构体

#### message类型：

​	定义数组类型时，是在字段前面增加repeated关键词来实现，标记当前字段是一个数组

​	message类似go中定义的结构体，在protobuf中指的就是我们要定义的数据结构

###### 	分配标识号：

​		==string query = 1==，其中的1就是分配标识号，在消息定义中，每个字段后面都有一个唯一的数字，这个就是标识号。

​		标识号的作用：在消息的二进制格式中识别各个字段，一旦开始使用就不能够再改变

​		注：分配标识号在每个消息内唯一，不同的消息体是可以拥有相同的标识号的。

> 小技巧：[1,15]之内的标识号在编码的时候会占用一个字节。[16,2047]之内的标识号则占用2个字节。所以应该为那些频繁出现的消息元素保留 [1,15]之内的标识号。

###### 保留标识号：

> ​	要为将来有可能添加的、频繁出现的字段预留一些标识号

```protobuf
message Reserver {
	// 保留2，5，7到10这些标识号
	reserver 2,5,7 to 10;
}
```

如果使用了这些保留的标识号，protocol buffer编译器无法编译通过，会输出警告信息。



##### 将消息编译成各种语言版本的类库

​	编译器命令格式：

```protobuf
protoc [OPTION] PROTO_FILES
```

常用的OPTION选项

```go
 --go_out=OUT_DIR            指定代码生成目录，生成 Go 代码
  --cpp_out=OUT_DIR           指定代码生成目录，生成 C++ 代码
  --csharp_out=OUT_DIR        指定代码生成目录，生成 C# 代码
  --java_out=OUT_DIR          指定代码生成目录，生成 java 代码
  --js_out=OUT_DIR            指定代码生成目录，生成 javascript 代码
  --objc_out=OUT_DIR          指定代码生成目录，生成 Objective C 代码
  --php_out=OUT_DIR           指定代码生成目录，生成 php 代码
  --python_out=OUT_DIR        指定代码生成目录，生成 python 代码
  --ruby_out=OUT_DIR          指定代码生成目录，生成 ruby 代码
```



##### 其他类型

- ###### 枚举类型

​		Enum：当定义一个消息类型时，如果想为一个字段指定的”预定义值“中的其中一个值，这时候就可以通过枚举实现

```protobuf
syntax = "proto3";//指定版本信息，非注释的第一行

enum SexType //枚举消息类型，使用enum关键词定义,一个性别类型的枚举类型
{
    UNKONW = 0; //proto3版本中，首成员必须为0，成员不应有相同的值
    MALE = 1;  //1男
    FEMALE = 2; //2女  0未知
}

// 定义一个用户消息
message UserInfo
{
    string name = 1; // 姓名字段
    SexType sex = 2; // 性别字段，使用SexType枚举类型
}

```

- ###### 消息嵌套

  ​	在实际开发中，我们需要定义多个proto，消息嵌套则可以帮助我们做到消息的服用

  ​	例如在go中时常嵌套使用结构体，在protobuf中同样可以如此，在一个消息中嵌套另外一个消息，字段类型可以是另外一个消息类型

​	而且在protoc文件中，可以import另外一个文件，且可以使用其定义的消息体

- ###### map类型

  ```go
  map<key_type,value_type> map_field = N;
  ```

  1. key_type可以是任何整数或字符串类型(除浮点类型和字节之外的任何标量类型)
  2. 注意：枚举不是有效的key_type
  3. value_type 可以是除另一个映射之外的任何类型
  4. Map字段不能使用repeated关键字修饰



#### 了解RPC

​	RPC--远程过程调用，对于全称为：Remote Procedure Call，可以简单理解为一个节点请求另外一个节点提供的服务

​	RPC主要依赖于客户端与服务的建立socket链接，而http rest实现通讯的代价比较高，这是RPC的一个优势体现、

###### 	本地过程调用：

​		如果要将本地对象student的age+1，可以实现一个addAge()方法，将student对象传入，对年龄进行更新之后返回即可，本地方法调用的函数体通过函数指针来指定

###### 	远程过程调用：

​		如果addAge()方法在服务端，执行函数的函数体在远程机器上，又该如何调用？

1. 首先客户端需要告诉服务器，需要调用的函数，这里函数和进程id存在一个映射，客户端远程调用时，需要查一下函数，找到对应的ID，如何执行函数的代码
2. 客户端需要把本地参数传给远程函数，本地调用的过程中，直接压入栈即可，但是远程调用过程不在同一个内存当中，无法直接传递函数的参数，因此需要客户端将参数转换成字节流，传给服务端，如何服务端将字节流转换成自身能读取的格式，是一个序列号和反序列化的过程。
3. 数据准备好了以后，如何进行传输？

​		网络传输层把调用的ID和序列化后的参数传给服务端，然后把计算出来的结果序列号传给客户端，因此TCP层即可完成上述过程，gRPC中采用的是HTTP2协议。

```go
// Client端 
//    Student student = Call(ServerAddr, addAge, student)
1. 将这个调用映射为Call ID。
2. 将Call ID，student（params）序列化，以二进制形式打包
3. 把2中得到的数据包发送给ServerAddr，这需要使用网络传输层
4. 等待服务器返回结果
5. 如果服务器调用成功，那么就将结果反序列化，并赋给student，年龄更新

// Server端
1. 在本地维护一个Call ID到函数指针的映射call_id_map，可以用Map<String, Method> callIdMap
2. 等待客户端请求
3. 得到一个请求后，将其数据包反序列化，得到Call ID
4. 通过在callIdMap中查找，得到相应的函数指针
5. 将student（params）反序列化后，在本地调用addAge()函数，得到结果
6. 将student结果序列化后通过网络返回给Client
```


![image-20230114213801646.png](http://malyue.cn:85/static/img/57be260663da1c05222ab209ff66bee3.image-20230114213801646.png)

##### 	为什么使用RPC

​		因为无法在同一个进程内，或者无法在同一个服务器上通过本地调用的方式实现需求，http能满足需求但是不够高效。

​		使用情况：比如不同系统间通讯，由于计算能力需要横向扩展，需要在多台机器组成的集群上部署应用

##### RPC和HTTP对比

1. RPC主要用于公司内部的服务调用，性能消耗低，传输效率高，服务治理方便
2. HTTP主要用于对外的异构环境，浏览器接口调用，APP接口调用，第三方接口调用等

###### RPC基本构成

1. RPC基本构成：服务端、客户端
2. 服务端基本构成：结构体，请求结构体，响应结构体
3. 客户端基本构成：请求结构体，响应结构体

## Consul

​	是HashiCorp公司推出的开源工具，用于实现分布式系统的服务发现与配置。Consul是分布式的，高可用的，可横向扩展的

### 	注册中心Consul基本介绍

- Consul是一种服务网格解决方案
- 提供具有服务发现，配置和分段功能的全功能控制平面
- Consul附带一个简单的内置代理，可以开箱即用

### 	注册中心Consul关键功能

- 服务发现

  ​	客户端可以注册服务，程序可以轻松找到它们所依赖的服务

- 运行状况检查

  ​	Consul客户端可以提供任意数量的运行状况检查

- KV存储

  ​	应用程序可以将Consul的层级键/值存储用于任何目的，包括动态配置，功能标记，协调，领导者选举等

- 安全服务通信

  ​	Consul可以为服务生成和分发TLS证书，建立相互的TLS连接

- 多数据中心

  ​	Consul支持多个数据中心

### 	注册中心Consul两个重要协议

- Gossip Protocol(八卦协议)
- Raft Protocol(选举协议)





​		

go微服务入门(一)

**搜索算法**




这里直接上例题

[> leecode 733 图像渲染](https://leetcode.cn/problems/flood-fill/?envType=study-plan&id=suan-fa-ru-men&plan=algorithms&plan_progress=xhn9yyze)

有一幅以 m x n 的二维整数数组表示的图画 image ，其中 image[i][j] 表示该图画的像素值大小。
你也被给予三个整数 sr ,  sc 和 newColor 。你应该从像素 image[sr][sc] 开始对图像进行 上色填充 。为了完成 上色工作 ，从初始像素开始，记录初始坐标的 上下左右四个方向上 像素值与初始坐标相同的相连像素点，接着再记录这四个方向上符合条件的像素点与他们对应 四个方向上 像素值与初始坐标相同的相连像素点，……，重复该过程。将所有有记录的像素点的颜色值改为 newColor。最后返回 经过上色渲染后的图像 。

![图片.png](http://malyue.cn:85/static/img/579620f637e171e695cc7dc51ed8c589.%C3%A5%C2%9B%C2%BE%C3%A7%C2%89%C2%87.png)




```js
输入: image = [[1,1,1],[1,1,0],[1,0,1]]，sr = 1, sc = 1, newColor = 2
输出: [[2,2,2],[2,2,0],[2,0,1]]
解析: 在图像的正中间，(坐标(sr,sc)=(1,1)),在路径上所有符合条件的像素点的颜色都被更改成2。
注意，右下角的像素没有更改为2，因为它不是在上下左右四个方向上与初始点相连的像素点。
```
题意很简单，就是给定一个初始位置，每次只能上下左右移动一次，且只能在数值相同的位置之间移动，将从初始位置能经过有限次次数到达的位置的值全修改为给定的newColor即可

那这种四个方向都可以走的搜索，我第一个想到的就是使用深度或广度优先搜素，下面是使用了广度优先搜素的代码，先建立一个队列来存储中间访问的过程，首先将初始位置入队，若队列非空，则每次出队一个，修改其值，且将其能访问到的位置入队，重复以上过程，直到队列为空，则修改完毕


```java
class Solution {
    public int[][] floodFill(int[][] image, int sr, int sc, int color) {
        // 从image[sr][sc]开始，将待修改的颜色改为newColor
        // 需要修改的点则是能够走到初始点的点，且只有上下左右四个方向，只能走到数值相同的点
        // 广度优先似乎最适合，一次性能够接触所有能到达的点
        // 需要建一个队列
        Queue<int[]> queue = new LinkedList<int[]>();
        int curColor = image[sr][sc];
        if(curColor == color) {
            return image;
        }
        //起始点入队
        queue.add(new int[]{sr,sc});
        int row = image.length;
        int column = image[0].length;
        // 队列非空
        while(!queue.isEmpty()){
            // 出队队头
            int[] local = new int[2];
            local = queue.poll();
            // 将队头能到达的点入队
            // 往左
            if(local[0] != 0){
                if(image[local[0]-1][local[1]] == curColor) {
                    // 入队
                    queue.add(new int[]{local[0]-1,local[1]});
                }
            }
            if(local[1] != 0){
                if(image[local[0]][local[1]-1]==curColor) {
                    queue.add(new int[]{local[0],local[1]-1});
                }
            }
            if(local[0] != row-1){
                if(image[local[0]+1][local[1]]==curColor) {
                    queue.add(new int[]{local[0]+1,local[1]});
                }
            }
            if(local[1] != column-1) {
                if(image[local[0]][local[1]+1]==curColor) {
                    queue.add(new int[]{local[0],local[1]+1});
                }
            }
            // 入队后修改当前的颜色
            image[local[0]][local[1]] = color;
        }
        return image;
    }
}
```




[leecode 695 岛屿的最大面积](https://leetcode.cn/problems/max-area-of-island/?envType=study-plan&id=suan-fa-ru-men&plan=algorithms&plan_progress=xhn9yyze)

给你一个大小为 m x n 的二进制矩阵 grid 。
岛屿 是由一些相邻的 1 (代表土地) 构成的组合，这里的「相邻」要求两个 1 必须在 水平或者竖直的四个方向上 相邻。你可以假设 grid 的四个边缘都被 0（代表水）包围着。
岛屿的面积是岛上值为 1 的单元格的数目。
计算并返回 grid 中最大的岛屿面积。如果没有岛屿，则返回面积为 0 。

![图片.png](http://malyue.cn:85/static/img/ae5172ee2e576de2cd715e88332b78e0.%C3%A5%C2%9B%C2%BE%C3%A7%C2%89%C2%87.png)

```golang
输入：grid = [[0,0,1,0,0,0,0,1,0,0,0,0,0],[0,0,0,0,0,0,0,1,1,1,0,0,0],[0,1,1,0,1,0,0,0,0,0,0,0,0],[0,1,0,0,1,1,0,0,1,0,1,0,0],[0,1,0,0,1,1,0,0,1,1,1,0,0],[0,0,0,0,0,0,0,0,0,0,1,0,0],[0,0,0,0,0,0,0,1,1,1,0,0,0],[0,0,0,0,0,0,0,1,1,0,0,0,0]]
输出：6
解释：答案不应该是 11 ，因为岛屿只能包含水平或垂直这四个方向上的 1 。
```

即求连成1的最大区域的方块个数，这与上一题是一样的思路，只不过没给定起始位置，而是自己去遍历二维数组，这里有一个小技巧，即为了重复的进行遍历，可以采取将已经走过的岛屿反转为水，即将访问过的1改为0，这样就避免了例如在遍历到[1,2]时访问到了[1,3]，但在遍历到[1,3]时还需要再次访问[1,2]，其余的思路就与上一题是一样的，即你当前遍历到的位置就是你的起点，通过深度或广度去找连接起来的区域，深度和广度主要的区别主要就还是使用栈还是队列来储存中间节点，或者可以使用递归的方法，下面的代码样例为递归，更容易理解

```java
class Solution {
    public int maxAreaOfIsland(int[][] grid) {
        // 求最大的岛屿，且是上下左右四个方向相连起来的
        int max = 0;
        for(int i = 0;i<grid.length;i++) {
            for(int j = 0;j<grid[0].length;j++){
                int cur = 0;
                // 通过栈，入栈，直到没有下一个才开始出栈
                // 为了防止重复，经历过的都置为0
                if(grid[i][j] == 1) {
                    max = Math.max(max,dfs(grid,i,j));
                }
            }
        }
        return max;
    }
    public int dfs(int[][] grid,int i,int j) {
        //当超出边缘或者遇到海洋则退出
        if(i<0||j<0||i>=grid.length||j>=grid[0].length||grid[i][j]==0) return 0;
        int sum = 1;
        // 经历过的直接改为海洋
        grid[i][j] = 0;
        sum += dfs(grid,i+1,j);
        sum += dfs(grid,i-1,j);
        sum += dfs(grid,i,j-1);
        sum += dfs(grid,i,j+1);
        return sum;
    }
}
```

深度优先搜索和广度优先搜索

## 网络的连接过程

此书主要是讲解了一条浏览器发送的请求到接受的过程经历的事情

### 浏览器生成消息

##### 	解析URL

​	首先当用户输入了类似 `https://www.baidu.com`,按下回车，那这时候浏览器发生了什么？

​	我们都知道，按下后如果网络正常的情况下，出现的效果就是对应的网页页面，包括文字、图片等，都渲染到了浏览器页面上，

即我们能看到的整个页面都呈现了出来

​	在这个过程中，你与浏览器之间的主要交互就是你输入了`https://www.baidu.com`这一串字母，对于人们来说，这个就是一个网址，或者可以称为`URL`，这个网址对应的就是一个页面，按下回车后，其实就是告诉浏览器，我想要这个网址对应的内容，那么浏览器怎么知道这个网址对应的是哪个页面呢，这自然就有他一套解析的规则。

​	首先我们要知道，这个页面对应的是什么内容浏览器也不知道，他只能根据你的要求，去向Web服务器发送请求，而得到对应的内容,浏览器负责的就是替你转达要求(将你输入的网址，解析为例如`给我index.html这一个文件储存的网页数据`)，以及渲染对应的数据,发送消息则是由操作系统对应的部分来处理.

​	浏览器会先解析URL，URL可以分为`协议类型://(user:password)@webServer/file(或dir)`,类似这样的形式

​	例如 https://www.abc.com/a.html 包含的信息就是，采取了HTTPS协议，Web服务器名称为www.abc.com,请求文件路径名为a.html

而有时候文件名是可以省略的，那就是会访问服务器上事先设置好的默认文件名

​	根据这个规则，浏览器完成了对URL的解析，接下来就需要进行下一步



##### 	生成HTTP请求消息

​	http消息的格式如下:

```shell
// 请求消息
<方法><空格><URI><空格><HTTP版本>
// 下面直到空行称为消息头
<字段名>:<字段值>
...
...
<空行>
<消息体>

// 响应消息
<HTTP版本><空格><状态码><空格><响应短语>
<字段名>:<字段值>
...
...
<空行>
<消息体>
```

HTTP状态码概要

| 状态码 |           含义           |
| :----: | :----------------------: |
|  1xx   | 告知请求的处理进度和情况 |
|  2xx   |           成功           |
|  3xx   |    表示需要进一步操作    |
|  4xx   |        客户端错误        |
|  5xx   |        服务器错误        |

返回响应消息后,浏览器就会将数据提取出来并且显示在屏幕上,这就是我们看到的网页的样子,如果网页中还包括图片的话,浏览器还需要再次发送请求,获得对应的图片再次渲染到预留的空间中.

#### DNS服务器解析Web服务器的IP地址

我们都知道,在网络中传递其实靠的都是ip地址去进行查询,在网络中,所有的设备都会被分配一个地址,相当于`xx号xx室`,其中的号对应是子网,而室对应某个子网中的某台计算机,称为`网络号和主机号`.,只有知道了IP地址才能找到对应的主机,判断出访问的服务器的位置

在发送的过程中,发送者送出的消息首先会经过子网中的集线器,转发到距离发送者最近的路由器上,经过多次重复最终将消息传到目的地

(TODO 怎么判断距离发送者最近的路由器)

###### 认识IP

实际的IP地址就是一段32比特的数字,即4个字节,8比特为一组划分

`114.132.232.37`这就是一段ip地址

`114.132.232.37/255.255.255.0`或`114.132.232.37/24`,`/`后面的称为子网掩码,24即前24位为1的子网掩码

ip中,前三段代表的是网络号,而最后一段代表的是主机号,`当主机号为0时代表的是整个子网而不是单独某台计算机,当主机号为1时代表的是对整个子网进行广播`

真实的网络号和主机号是将ip地址与子网掩码进行异或操作后得出的(有一个不为1则为0)

那这时候问题来了,浏览器怎么知道对应服务器的IP地址是多少?

前面解析URL的时候,浏览器得到一个WebServer-即`www.baidu.com`,这个又称为域名,这时候我们就需要将它转化为我们要的ip地址.

> 或者有人会觉得为什么不用某个域名来代表某台主机,毕竟一个域名对应也是一个ip,何必需要加上转换这一步呢?
>
> 从运行效率上来考虑,这不是一个好主意,IP地址32比特,即4字节,换成名称的话,最短都需要几十个字节了,处理起来就麻烦了不少,增加了路由器的负担,花费更多的时间来进行数据传输,而且不定长度的名称,可能会使得处理起来更不方便

但是IP让人来记忆似乎也十分麻烦,那么最终人们采取的方案就是让人来使用名称,路由器使用IP地址,在提供对应的转换服务,这个机制称为`DNS`

查询DNS很简单,计算机上有对应的DNS客户端-称为`DNS解析器,或者简称解析器`,通过DNS查询IP地址称为域名解析

解析器其实就是一段程序,这时可以采用Socket库的方法直接调用对应程序即可,这时解析器会生成要发送给DNS服务器的查询信息,生成一条消息,发送给DNS服务器,而发送消息这个过程与浏览器一样,不是由解析器本身来操作,而是委托给了操作系统内部的协议栈执行,协议栈执行发送消息操作,然后通过网卡将消息发送给DNS服务器

如果被访问的服务器在DNS上注册则能找到该记录,将其IP地址写回响应信息返回给客户端

> 那DNS服务器的地址在哪里知道?
>
> 向DNS服务器发送消息时,当然也需要知道对应服务器的IP地址,不过这个IP地址是作为TCP/IP的一个设置项目事先设置好的

#### DNS介绍

一般来自客户端的查询消息包括三个信息:

- 域名

- Class

  在最早涉及的时候,DNS考虑到在互联网以外的应用,设置来识别网络的信息,不过如今基本只有互联网了,所以一般是代表互联网的IN

- 记录类型

  当类型为A时,表示对应的是IP地址,类型为MX时,对应的是邮件服务器,对于不同记录类型,服务器向客户端返回的信息也不同

DNS服务器接受到记录类型为A的消息后,会从域名与IP地址的对照表中查找相应的记录,并返回IP地址



##### 域名的层次结构

由于互联网中服务器数量庞大,不可能全部存于一台DNS服务器当中,那又应该如何解决?

那肯定是需要多台服务器互相协作,这时还记得类似`www.baidu.com`的域名中的`.`符号,这个就是将域名进行分割的,每一部分称为域,层级从右边往左边递减,每个域在DNS服务器中都是作为一个整体来处理的,一个域的信息都是作为一个整体存放到DNS服务器中.

从上往下数的话,其实最顶层应该是根域,之后`com,jp`等顶级域是在根域之下一级,根域保存着com等顶级域名的服务器的信息,所以可以从根域开始一路往下找到任意一个域的DNS服务器

且根域的DNS服务器信息保存在互联网中所有的DNS服务器当中,即每个服务器都可以找到并访问所有的DNS服务器了

