ARTS-第一周

耗子叔发起的ARTS计划,第一周。
ARTS计划简介:

https://time.geekbang.org/column/article/85839?from=singlemessage

A

leetcode题库中第19题:删除链表的倒数第N个节点


给定一个链表,删除链表的倒数第 n 个节点,并且返回链表的头结点。

示例:
1
2
3
给定一个链表: 1->2->3->4->5, 和 n = 2.

当删除了倒数第二个节点后,链表变为 1->2->3->5.
说明:

给定的 n 保证是有效的。

解答:

思路一
两次遍历,第一次遍历获取总数,第二次遍历在sum-n处进行处理,让sum-n指向sum-n-2。

两次遍历
优点 实现简单,不浪费空间
缺点 不是最优实现
时间复杂度 O(N)
空间复杂度 O(1)

思路二
一次遍历,但是在第一次遍历中创建一个map,key为position,value为ListNode.这样可以一次遍历拿到值。

一次遍历
优点 实现简单,相比于两次循环,节省了部分时间。
缺点 浪费空间
时间复杂度 O(N)
空间复杂度 O(1)

思路三
根据提示,第三次实现使用了双指针,即快慢指针。代码如下:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
public ListNode removeNthFromEnd(ListNode head, int n) {
ListNode first = head;
ListNode second = null;
for (int i = 1; i < n + 1; i++) {
//快指针
first = first.next;
}
//慢指针开始跑
ListNode position = head;
while (first != null) {
second = position;
first = first.next;
position = position.next;
}
//如果second为null,代表N刚好等于链表的长度。
if (second == null) {
head = head.next;
} else {
second.next = second.next.next;
}
return head;
}

快指针默认指向head,然后移动N步。
如果first不为null,那么开始移动second,这样当first指向null的时候second与尾节点刚好N+1个间隔。让second指向下下个位置,就可以把第N个元素删除。
如果second为null,则说明,n刚好等于链表的长度,那么直接点将第一个节点后移即可。

因为链表的知识已经忘的差不多,所以忘记头结点怎么用了。这里这么写可实现,但是代码不易阅读,等将头结点复习一下对代码进行重构。

双指针
优点 相比于一次循环,节省了空间
缺点 实现相对复杂
时间复杂度 O(N)
空间复杂度 O(1)

R

R选择的是Alibaba/Sentinel的官方文档。选取这个原因是因为,我需要学习Sentinel,同时因为Sentinel是双语版的,可以在读完英文文档之后再读一遍中文文档,进行验证。

https://github.com/alibaba/Sentinel

概述:

Sentinel主要提供了流量控制,熔断,系统自适应保护的功能,来保证多个微服务之间的稳定。

特性:
  • Sentinel在Alibaba中被广泛应用,在双十一中覆盖了几乎所有的核心场景。例如: 秒杀,流量削峰填谷,断开下游服务(熔断), 集群流量控制等。
  • Sentinel同时提供了实时监控的能力,可以实时查看单机机器的运行时信息,和少于500节点的集群的聚合信息。
  • Sentinel可以提供了开箱即用的接口去接入一些常见的框架,例如:springCloud,dubbo,gRPC。我们可以方便的在我们的项目中加入Sentinel的依赖。
  • 提供了丰富的SPI拓展,我们可以方便快速的自定义我们的逻辑,例如自定义路由管理和自适应数据源。

从架构图上还能看出来有: 路由管理,服务发现,链路追踪?集群限流,热点数据限流,来源访问控制的功能。

使用:
  1. 加入依赖
  2. 定义资源, Sentinel的资源 可以直接用API包装我们的业务代码,也可以使用注解。
  3. 定义规则, 规则要绑定到一个资源上。(从代码上来看是这样的, 而且这里的规则是一个流控的规则)

以上是Sentinel的概览。

T

今天在阅读RocketMQ源码的时候发现了一个之前从未使用过的方法就是StringBuilder.setLength();

介绍:

StringBuilder的setLength()方法可以重用StringBuilder对象。
看一下方法

1
2
3
4
5
6
7
8
9
10
11
12
 public void setLength(int newLength) {
//如果newLength<0抛出异常
if (newLength < 0)
throw new StringIndexOutOfBoundsException(newLength);
ensureCapacityInternal(newLength);
if (count < newLength) {
//如果count小于传递的值,那么将count-->newLength之间的值置为空。
Arrays.fill(value, count, newLength, '\0');
}
//count为newLength.
count = newLength;
}

再看一下toString方法

1
2
3
4
public String toString() {
// Create a copy, don't share the array
return new String(value, 0, count);
}

这里会对0-count的范围内进行拷贝。调用的Arrays.copyOfRange().

总结:

StringBuilder.setLength()函数只重置它的count指针,而char[]则会继续重用,而toString()时会把当前的count指针也作为参数传给String的构造函数,所以不用担心把超过新内容大小的旧内容也传进去了。

通过使用StringBuilder.setLength(0) 可以避免重复创建StringBuilder对象。

网上博客

https://www.cnblogs.com/Zombie-Xian/p/6237409.html

S

在看RocketMQ消息生产以及消息消费的过程中,总是对broker端做的动作有些模糊不解,在看broker端处理的代码时候,因为不理解RocketMQ的消息布局,所以也看不大懂。因此下定决心将RocketMQ中消息存储部分的源码进行梳理,从而对RocketMQ的核心部分有一个整体的了解,同时方便之后的复习。本周的Share主要是记录RocketMQ中消息存储的commitLog源码的跟踪。
地址为:

http://www.xunyajie.com/2019/03/24/RocketMQ消息存储/