蒙娜丽莎法师

life is not just live

二叉树的锯齿形层次遍历-LeetCode103

题目描述

给定一个二叉树,返回其节点值的锯齿形层次遍历。(即先从左往右,再从右往左进行下一层遍历,以此类推,层与层之间交替进行)。

例如:
给定二叉树 [3,9,20,null,null,15,7],

1
2
3
4
5
  3
/ \
9 20
/ \
15 7

返回锯齿形层次遍历如下:

1
2
3
4
5
[
[3],
[20,9],
[15,7]
]

所谓的锯齿形遍历,即是在第一层从左向右遍历,在第二层从右向左遍历,依次遍历完成。

自己动手实现一个RPC框架(七)

rpc-client

消费者端,通过代理来进行调用。

与生产者端类型,首先定义配置类:

1
2
3
4
5
6
7
8
9
10
public class ClientConfig {

private Class<? extends Encoder> encoder = FastJsonEncoder.class;

private Class<? extends Decoder> decoder = FastJsonDecoder.class;

private Class<? extends TransportClient> transportClient = NettyClient.class;

private Class<? extends RpcRegister> rpcRegister = ZookeeperRegistry.class;
}

自己动手实现一个RPC框架(六)

rpc-server

消费者的部分,这里使用配置类,将各种实现的部分在配置类中进行定义。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
public class ServerConfig {
/**
* 监听端口
*/
private int port = 9090;
/**
* 网络传输
*/
private Class<? extends TransportServer> transportClass = NettyServer.class;
/**
* 注册中心
*/
private Class<? extends RpcRegister> rpcRegister = ZookeeperRegistry.class;
/**
* 编码
*/
private Class<? extends Encoder> encoder = FastJsonEncoder.class;
/**
* 解码
*/
private Class<? extends Decoder> decoder = FastJsonDecoder.class;

}

这这个配置中,定义了服务启动的端口,网络传输,注册中心,编解码的各种实现,当我们需要更换实现时只需要在这里修改即可。

自己动手实现一个RPC框架(四)

rpc-register

注册中心,这里使用zookeeper来实现。

生产者在启动服务时,将自己实现的服务注册到注册中心。

消费者调用服务时,来注册中心查找,返回调用服务实例的地址信息。

并且为了适应不同的注册实现,我们将功能定义为接口,在替换实现时在配置文件中进行替换即可。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
public interface RpcRegister {
/**
* 注册服务
* @param serviceDescriptor
* @param responseServiceDescription
*/
void register(ServiceDescriptor serviceDescriptor, ResponseServiceDescription responseServiceDescription);
/**
* 根据服务名称查询实例地址
* @param serviceDescriptor
* @return
*/
ResponseServiceDescription lookup(ServiceDescriptor serviceDescriptor);
}

自己动手实现一个RPC框架(二)

自己动手实现一个RPC框架
使用fastjson,netty,反射,动态代理,zookeeper实现一个RPC框架。

代码链接:https://github.com/liunaijie/self-rpc-framwork`

各模块说明:

  • rpc-commons
    通用设置模块,包括网络传输的数据格式,请求编号工具类,反射工具类等一些底层协议,工具相关的内容

  • rpc-register
    服务注册模块,主要包括服务的注册与发现功能。这里使用zookeeper来进行实现。
    在这里,服务端注册时,使用通用模块中的ServiceDescriptor,ResponseServiceDescription类来进行注册
    ResponseServiceDescription类是ServiceDescription的子类,添加了实现类,实例地址等属性。
    消费者查找服务时,发送ServiceDescription得到ResponseServiceDescription,一个类可能有多个实现类,多个实例,在返回时进行随机返回。
    对于同一个实现的不同版本实现,或多个服务实例这种情况随机返回没有问题。对于不同实现类,采用随机返回可能有些问题,但是在spring中对于多实现类也需要指定实现类,所以后面再考虑更改。

有序链表转换为二叉搜索树—LeetCode109

题目描述

给定一个单链表,其中的元素按升序排序,将其转换为高度平衡的二叉搜索树。

本题中,一个高度平衡二叉树是指一个二叉树每个节点 的左右两个子树的高度差的绝对值不超过 1。

示例:

给定的有序链表: [-10, -3, 0, 5, 9],

一个可能的答案是:[0, -3, 9, -10, null, 5], 它可以表示下面这个高度平衡二叉搜索树:

1
2
3
	0
-3 9
-10 5

答案不唯一,只要满足平常二叉树的特性即可。

题目中给出的数组已经按升序排序,我们需要将其转换为平衡二叉树。

之前写过一篇平衡二叉树的插入,可以直接调用平衡二叉树的插入方法即可。但是这一次并不是使用插入方法,而是根据升序的特性来做。

自己动手实现一个RPC框架(一)

前言

现在微服务体系流行,而RPC框架作为微服务中重要的一环,为了弄明白RPC的整体过程,决定要自己动手实现一个RPC框架。

我们先了解一下什么是RPC,RPC全程是Remote Procedure Call,翻译过来就是远程过程调用,我们先思考一下没有使用rpc的项目的调用流程:

  1. 通过@Autoware注解注入另外的类
  2. 在需要调用的地方直接调用即可

当需要调用其他功能的接口时,比如调用其他公司的接口,或者调用自己公司内部的其他业务或功能接口。这时一般需要使用http来进行网络调用。

那么使用http调用其他的功能接口算不算是rpc调用呢?我感觉也是算的,因为这也是一种通过网络从计算机程序上请求服务的过程。

只不过由于调用的功能不严格意义上属于一个大项目,所以不算一个程序直接的内部调用,所以这里只讨论 一个大项目拆分成不同模块后,不同模块直接调用的过程。

RPC是原来一个程序分为多个不同的程序,分别运行在不同的jvm上。部署在多台机器上后,就涉及到网络通信,需要将调用的信息发送到被调用的机器上,调用完成后再进行返回。

rpc的流程图如下所示,

RPC调用流程

牵扯到网络请求,那么就可以使用之前的http请求,但是由于http请求需要封装一些对于我们而言无用的信息,所以使用http的方式可以采用,比如springcloud就采用了http来进行通信的方式,而这次我准备使用其他的网络通信方式,这一篇中先使用bio来实现网络通信。

还有一个序列化过程,它主要是将信息进行编解码,然后通过网络传输,因为网络传输中都是传输的二进制字节码文件,所以我们需要定义规则,将信息进行转换,消费者发送出去的信息生产者能明白其调用的内容,消费者也能明白生产者返回的信息。这一篇文章中也不去使用复杂的序列化方式,直接实现java中的Serializable接口。

二分查找及几种变形

二分查找

这个查找的要求是数组有序,我们要查找一个元素是不是存在于已排序数组中,先拿中间值与它比较,如果中间值比寻找值小则在中间值后面继续查找,否则在前面进行查找。

它的时间复杂度是o(logn)。所以它在查找时非常快,比如1024个数据他也就用10次就可以完成查找。

Proudly powered by Hexo and Theme by Hacker
© 2020 Liu NaiJie