0%

Leetcode-75

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
Given an array with n objects colored red, white or blue, sort them in-place so that objects of the same color are adjacent, with the colors in the order red, white and blue.

Here, we will use the integers 0, 1, and 2 to represent the color red, white, and blue respectively.

Note: You are not suppose to use the library's sort function for this problem.

Example:

Input: [2,0,2,1,1,0]
Output: [0,0,1,1,2,2]
Follow up:

A rather straight forward solution is a two-pass algorithm using counting sort.
First, iterate the array counting number of 0's, 1's, and 2's, then overwrite array with total number of 0's, then 1's and followed by 2's.
Could you come up with a one-pass algorithm using only constant space?

solution

题目乍一看非常简单,但确实说使用简单的sort方法以及o(n^2)的排序确实会浪费时间复杂度,本着好奇心,我试了一下,果然成了吊车尾

1
2
3
4
5
6
7
8
9
10
11
12
13
14
class Solution {
public void sortColors(int[] nums) {
for(int i =0;i<nums.length-1;i++){
for(int j=i+1;j<nums.length;j++){
if(nums[i]>nums[j]){
int tmp=nums[i];
nums[i]=nums[j];
nums[j]=tmp;
}
}
}
}
}
Runtime: 1 ms, faster than 6.35% of Java online submissions for Sort Colors.

该题优化的核心位置是该数组是一个一维数组,设置两个指针,左边遍历0,遇到0往左放,遇到2往右放,r和l为左右分界线,index记录最后一个0的位置

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
class Solution {
public void sortColors(int[] nums) {
int l = 0;
int r = nums.length - 1;
int index = 0;
while(l <= r) {
if(nums[l] == 0) {
if(l > index) {
int tmp = nums[index];
nums[index] = nums[l];
nums[l] = tmp;
index++;
}
else {
l++;
index++;
}
}
else if(nums[l] == 2) {
int tmp = nums[r];
nums[r] = 2;
nums[l] = tmp;
r--;
}
else l++;
}

}
}

Leetcode-64

1
2
3
4
5
6
7
8
9
10
11
12
13
14
Given a m x n grid filled with non-negative numbers, find a path from top left to bottom right which minimizes the sum of all numbers along its path.

Note: You can only move either down or right at any point in time.

Example:

Input:
[
[1,3,1],
[1,5,1],
[4,2,1]
]
Output: 7
Explanation: Because the path 1→3→1→1→1 minimizes the sum.

solution

解法为简单的动态规划,只要找到比较该元素,上方和左方的值的最小值,然后与该值相加,就可以得到解

1
2
3
4
5
6
7
8
9
10
11
12
class Solution {
public int minPathSum(int[][] grid) {
for(int i=1; i<grid.length; i++) grid[i][0] += grid[i-1][0];
for(int j=1; j<grid[0].length; j++) grid[0][j] += grid[0][j-1];
for (int i=1; i<grid.length; i++) {
for (int j=1; j<grid[0].length; j++) {
grid[i][j] = Math.min(grid[i][j-1], grid[i-1][j]) + grid[i][j];
}
}
return grid[grid.length-1][grid[0].length-1];
}
}

题目

(这道题在互联网上已经有了)

1
2
3
可以添加任务,任务包含任务数据,任务延迟触发的等待时间。
在任务到达触发时间点时,自动触发执行此任务。
队列中任务保持先进先出原则:假设 A 任务的触发等待时间为 X,B 任务的触发等待时间为 Y,B 在 A 之后被添加入队列,则 A 的前驱任务执行完成后等待时间 X 后,才执行 A,同理在 A 执行完成后,等待时间 Y,才执行 B。

思路过程

1.Java上线

读题目就是延时队列的特征,Java有锁,有多线程,写起来多方便

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
import java.util.concurrent.BlockingQueue;
import java.util.concurrent.DelayQueue;
import java.util.concurrent.Delayed;
import java.util.concurrent.TimeUnit;
public class HandWritingQueue {
public static void main(String[] args) {
final BlockingQueue<DelayedElement> deque = new DelayQueue<>();
Runnable producerRunnable = new Runnable() {
int i = 10;
public void run() {
while (true && i>0) {
try {
--i;
System.out.println("producing "+i+",wait "+i+" seconds");
deque.put(new DelayedElement(1000 * i, "i=" + i));
Thread.sleep(200);
} catch (InterruptedException e) {
e.printStackTrace();
}
}
}
};
Runnable customerRunnable = new Runnable() {
public void run() {
while (true) {
try {
System.out.println("consuming:" + deque.take().msg);
//Thread.sleep(500);
} catch (InterruptedException e) {
e.printStackTrace();
}
}
}
};

Runnable getSize= new Runnable() {
@Override
public void run() {
while (true) {
System.out.println("size="+deque.size());
try {
Thread.sleep(1000);
} catch (InterruptedException e) {
e.printStackTrace();
}

}
}
};

Thread thread1 = new Thread(producerRunnable);
thread1.start();

Thread thread2 = new Thread(customerRunnable);
thread2.start();

Thread thread3 = new Thread(getSize);
thread3.start();

}

static class DelayedElement implements Delayed {

private final long expire;
private final String msg;

public DelayedElement(long delay, String msg) {
this.msg = msg;
expire = System.currentTimeMillis() + delay;
}

@Override
public long getDelay(TimeUnit unit) {
return unit.convert(this.expire - System.currentTimeMillis(), TimeUnit.MILLISECONDS);
}
@Override
public int compareTo(Delayed o) {
return -1;//FIFO
}
}
}

2.Node上线

被提醒该题目可以用node实现,且不需要借助redis来做,然后我上手就是一把操作:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
'use strict'
class DelayElement {
constructor(data, expire) {
this.data = data;
this.expire = expire;//second
}
}
const delayArray = [];

//push two element in delayArray
delayArray.push(new DelayElement(1, 2));
delayArray.push(new DelayElement(2, 1));
let length = delayArray.length;

let time_cnt = 0;
while (delayArray.length > 0) {
let de = delayArray.shift();
time_cnt += de.expire;//serial
(function () {
setTimeout(() => {
console.log('expire data is :' + de.data + ',expire time is :' + de.expire);
}, time_cnt * 1000);
})();
}

我以为设计的考点也就是立即执行函数,延时的使用,但是这里的for循环是个伪串行,实际上是并发的,也为第三步的修改提供了bug

3.Promise时代

一开始我是想把async函数放进去,写了如下的代码:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
'use strict'
const delayArray = [];
const daPush = (data, expire) => {
delayArray.push(async () => {
setTimeout(() => {
console.log('data is ' + data + ' and expire is ' + expire);
}, expire * 1000);
});
}
daPush(1, 4);//2 seconds
daPush(2, 5);

(async () => {
for (const da of delayArray) {
await da();
}
})();

发现代码还是串行的,然后查了一下可能的问题(以下为个人猜测,欢迎指正)async声明的函数会包装成Promise不假,但是for循环会并发去执行await中的async

4.正解

promise执行会阻塞主线程

Macrotasks和Microtasks 都属于上述的异步任务中的一种,他们分别有如下API:
macrotasks: setTimeout, setInterval, setImmediate, I/O, UI rendering
microtasks: process.nextTick, Promise, MutationObserver

任务队列中,在每一次事件循环中,macrotask只会提取一个执行,而microtask一直提取,直到microsoft队列为空为止。

也就是说如果某个microtask任务被推入到执行中,那么当主线程任务执行完成后,会循环调用该队列任务中的下一个任务来执行,直到该任务队列到最后一个任务为止。

而事件循环每次只会入栈一个macrotask,主线程执行完成该任务后又会检查microtasks队列并完成里面的所有任务后再执行macrotask的任务。

以及macrotask应该对应的是check队列(该行未验证)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
'use strict'
const delayArray = [];
const daPush = (data, expire) => {
delayArray.push(() => new Promise((resolve,reject) => {
setTimeout(() => {
if(data)
{
console.log('data is ' + data + ' and expire is ' + expire);
resolve(true);
}
else{
reject('there is nodata');
}
}, expire * 1000);
}));
};
daPush(1, 4);//2 seconds
daPush(2, 5);

(async () => {
for (const da of delayArray) {
da().then((value)=>{
// console.log(value);
}).catch((value)=>{
console.log(value);
});
//没有28-33,只35行也可以
// await da();
}
})();

执行了一下程序:

1
2
3
4
5
while(true){
setTimeout(()=>{
console.log(1)
},0)
}

返回了一下内容:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
<--- Last few GCs --->

[12308:000001E565C2F6F0] 14167 ms: Mark-sweep 1395.9 (1425.2) -> 1395.9 (1423.7) MB, 1754.1 / 0.0 ms (+ 0.0 ms in 39 steps since start of marking, biggest step 0.0 ms, walltime since start of marking 1764 ms) (average mu = 0.105, current mu = 0.020) a[12308:000001E565C2F6F0] 14175 ms: Scavenge 1397.3 (1423.7) -> 1397.3 (1425.2) MB, 7.0 / 0.0 ms (average mu = 0.105, current mu = 0.020) allocation failure


<--- JS stacktrace --->

==== JS stack trace =========================================

0: ExitFrame [pc: 000002AFCABDC5C1]
Security context: 0x037b5391e6e9 <JSObject>
1: /* anonymous */ [0000016D4360B9A1] [D:\working\h3yun\test.3.js:~1] [pc=000002AFCAC7210F](this=0x016d4360bad1 <Object map = 000001F79EE82571>,exports=0x016d4360bad1 <Object map = 000001F79EE82571>,require=0x016d4360ba91 <JSFunction require (sfi = 00000397F3EC6A31)>,module=0x016d4360ba09 <Module map = 000001F79EED3DA1>,__filename=0x0397f3ece219 <Strin...

FATAL ERROR: Ineffective mark-compacts near heap limit Allocation failed - JavaScript heap out of memory
1: 00007FF7C7BFC6AA v8::internal::GCIdleTimeHandler::GCIdleTimeHandler+4506
2: 00007FF7C7BD7416 node::MakeCallback+4534
3: 00007FF7C7BD7D90 node_module_register+2032
4: 00007FF7C7EF189E v8::internal::FatalProcessOutOfMemory+846
5: 00007FF7C7EF17CF v8::internal::FatalProcessOutOfMemory+639
6: 00007FF7C80D7F94 v8::internal::Heap::MaxHeapGrowingFactor+9620
7: 00007FF7C80CEF76 v8::internal::ScavengeJob::operator=+24550
8: 00007FF7C80CD5CC v8::internal::ScavengeJob::operator=+17980
9: 00007FF7C80D6317 v8::internal::Heap::MaxHeapGrowingFactor+2327
10: 00007FF7C80D6396 v8::internal::Heap::MaxHeapGrowingFactor+2454
11: 00007FF7C8200637 v8::internal::Factory::NewFillerObject+55
12: 00007FF7C827D826 v8::internal::operator<<+73494
13: 000002AFCABDC5C1

why

因为业务代码阻塞住,没有进入timer_handler的循环,所以1虽然进入了timer的红黑树中,但是不可能输出,不像之前for循环会有一个截止条件,后续的定时器还是可以生效的

另外有一个地方记混了,遍历回调的时候,会执行直到回调为空或者最大执行回调数量,而业务代码只会在这里阻塞不会停止,这也是为何出现GC的日志

what

setimeout是JS前端常用的控件用来延时执行一个函数(回调),当执行业务代码的时候我们会将settimeout,setImmediate,nextTick,setInterval插入timer_handler的不同队列中(详见左侧node分支,且文章也在更新中),当JS单线程执行完业务代码后,才开始eventloop查找观察者来进行回调,当然也存在延时不精确的可能

why

gRPC是任何环境都可以运行的高性能开源框架,他可以通过pluggable support来高效实现负载均衡,心跳检测和授权,他也可以应用于分布式计算的最后一个流程(连接各个端到后端)

  • 简单的服务定义
  • 快速启动易扩展
  • 跨语言,跨平台
  • 双向流和鉴权

feature

  • gRPC可以通过protobuf来定义接口,从而可以有更加严格的接口约束条件。关于protobuf可以参见笔者之前的小文Google Protobuf简明教程

  • 另外,通过protobuf可以将数据序列化为二进制编码,这会大幅减少需要传输的数据量,从而大幅提高性能。

  • gRPC可以方便地支持流式通信(理论上通过http2.0就可以使用streaming模式, 但是通常web服务的restful api似乎很少这么用,通常的流式数据应用如视频流,一般都会使用专门的协议如HLS,RTMP等,这些就不是我们通常web服务了,而是有专门的服务器应用。)

node

1
2
3
4
5
6
$ # Clone the repository to get the example code
$ git clone -b v1.25.0 https://github.com/grpc/grpc
$ # Navigate to the dynamic codegen "hello, world" Node example:
$ cd grpc/examples/node/dynamic_codegen
$ # Install the example's dependencies
$ npm install

LeetCode38

Easy

Given a sorted array and a target value, return the index if the target is found. If not, return the index where it would be if it were inserted in order.

You may assume no duplicates in the array.

Example 1:

1
2
Input: [1,3,5,6], 5
Output: 2

Example 2:

1
2
Input: [1,3,5,6], 2
Output: 1

Example 3:

1
2
Input: [1,3,5,6], 7
Output: 4

Example 4:

1
2
Input: [1,3,5,6], 0
Output: 0

离职后的第一题想先简单点热个身(后面有个难的目前还没做出来),就是说给一个target,返回它在数组中的位置

How

该题目一上脑子就可以写下如下的代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
public int searchInsert(int[] nums, int target) {
if (nums == null || nums.length == 0) {
return 0;
}
if (target > nums[nums.length - 1]) {
return nums.length;
}
int pos =1;
for(int i =0;i<nums.length-1;i++){
if(nums[i]<target && nums[i+1]>=target){
pos = ++i;
break;
}
}
return pos;
}

但转念一想,题目中给定的是一个sorted array这是一个优化的切口,可以将O(n)的复杂度降低到O(logn),通过递归来拆解完成这道题

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
private int searchInsert(int[] nums, int target, int low, int high) {
int mid = (low+high)/2;

if (target < nums[mid]) {
if (mid == 0 || target > nums[mid-1]) {
return mid;
}
return searchInsert(nums, target, low, mid-1);
}

if (target > nums[mid]) {
if (mid == nums.length-1 || target < nums[mid+1]) {
return mid+1;
}
return searchInsert(nums, target, mid+1, high);
}

return mid;
}

含义:spring 的简化配置版本(继承父类依赖,拥有父类的所有配置)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
<!--你的项目pom文件-->
<parent>
<groupId>org.springframework.boot</groupId>
<artifactId>spring-boot-starter-parent</artifactId>
<version>2.0.4.RELEASE</version>
<relativePath/> <!-- lookup parent from repository -->
</parent>

<!--点开spring-boot-starter-parent,文件相对位置\org\springframework\boot\spring-boot-starter-parent\2.0.4.RELEASE-->
<parent>
<groupId>org.springframework.boot</groupId>
<artifactId>spring-boot-dependencies</artifactId>
<version>2.0.4.RELEASE</version>
<relativePath>../../spring-boot-dependencies</relativePath>
</parent>

微服务

AOP

简化部署,可以再pom.xml中配置plugins来实现导出jar包,方便执行

Features:

  • starter
  • 入口类标记@SpringBootApplication
  • SpringBoot配置类@SpringBootConfiguration
  • 配置类@Configuration
  • 开启自动配置@EnableAutoConfiguration
  • 自动配置包@AutoConfigurationPackage
  • 导入组件@Import

疑惑

  • 为什么使用注解
  • 为什么需要AOP
  • 为什么选择springboot

含义:动物管理员,管理节点

作用:开源的分布式应用程序协调服务(简单来说,就是一个抽象出来,专门管理各个服务的管理员,发现服务,注册服务,以实现分布式应用的联合工作)

feature

  • 树状目录结构,节点称作znode
  • 持久节点(客户端断开仍然存在)
  • 临时节点(断开消失)
  • 节点监听(通过get exists,getchildren来实行监听)

应用:

  • 分布式锁
描述
问题场景 我们有一个服务C,将A系统的订单数据,发送到B系统进行财务处理,但这个服务部C署了三个服务器来进行并发,其中有些数据在传送处理时会new一个objectid,如果不添加锁,该数据可能被两个服务同时调起,在B服务中生成两条记录
解决方案 我们同步数据时候,需要给同一个数据加锁,防止该数据同时被两个服务调起,服务访问某条订单数据时候,需要先获得锁,操作完后释放锁
实现方式 每个服务连接一个znode的下属有序临时节点,并监听上个节点的变化,编号最小的临时节点获得锁,操作资源,来实现
  • 服务注册和发现
问题场景 我们同步数据的服务C(上个表格中描述),可能是部署在一个机器上的多进程,也可能是部署在多个物理ip上的服务,他是动态变化的,如果没有zookeeper类的软件,可能我每改一次ip,都需要重启一下服务,服务宕机了,也要改ip(不然404)
解决方案 我们需要有个服务来管理应用状态,知道服务的运行状态,这样,当其他服务调起这个服务的时候,才能通过zookeeper提供的地址进行同行
实现方式 服务启动会注册到zookeeper,并保持心跳,其他服务想要调用某服务的时候,询问zookeeper拿到地址,然后发送请求报文(例如RPC)
1.每个应用创建一个持久节点,每个服务在持久节点下建立临时节点,不同应用间会有监听,A服务如果变动,B服务会收到订阅

启动类

我们可以见到最简单的springboot的application.java文件如下

1
2
3
4
5
6
@SpringBootApplication
public class SpringTestApplication {

public static void main(String[] args) {
SpringApplication.run(SpringTestApplication.class, args);
}

实际上,SpringApplication的run方法时首先会创建一个SpringApplication类的对象,利用构造方法创建SpringApplication对象时会调用initialize方法

1
2
3
4
5
6
7
8
9
10
11
public static ConfigurableApplicationContext run(Object source, String... args) {
return run(new Object[] { source }, args);
}

public static ConfigurableApplicationContext run(Object[] sources, String[] args) {
return new SpringApplication(sources).run(args);
}

public SpringApplication(Object... sources) {
initialize(sources);
}

其中initialize方法如下

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
`private void initialize(Object[] sources) {
// 在sources不为空时,保存配置类
if (sources != null && sources.length > 0) {
this.sources.addAll(Arrays.asList(sources));
}
// 判断是否为web应用
this.webEnvironment = deduceWebEnvironment();
// 获取并保存容器初始化类,通常在web应用容器初始化使用
// 利用loadFactoryNames方法从路径MEAT-INF/spring.factories中找到所有的ApplicationContextInitializer
setInitializers((Collection) getSpringFactoriesInstances(
ApplicationContextInitializer.class));
// 获取并保存监听器
// 利用loadFactoryNames方法从路径MEAT-INF/spring.factories中找到所有的ApplicationListener
setListeners((Collection) getSpringFactoriesInstances(ApplicationListener.class));
// 从堆栈信息获取包含main方法的主配置类
this.mainApplicationClass = deduceMainApplicationClass();
}

实例化后调用run:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
public ConfigurableApplicationContext run(String... args) {
StopWatch stopWatch = new StopWatch();
stopWatch.start();
ConfigurableApplicationContext context = null;
FailureAnalyzers analyzers = null;
// 配置属性
configureHeadlessProperty();
// 获取监听器
// 利用loadFactoryNames方法从路径MEAT-INF/spring.factories中找到所有的SpringApplicationRunListener
SpringApplicationRunListeners listeners = getRunListeners(args);
// 启动监听
// 调用每个SpringApplicationRunListener的starting方法
listeners.starting();
try {
// 将参数封装到ApplicationArguments对象中
ApplicationArguments applicationArguments = new DefaultApplicationArguments(
args);
// 准备环境
// 触发监听事件——调用每个SpringApplicationRunListener的environmentPrepared方法
ConfigurableEnvironment environment = prepareEnvironment(listeners,
applicationArguments);
// 从环境中取出Banner并打印
Banner printedBanner = printBanner(environment);
// 依据是否为web环境创建web容器或者普通的IOC容器
context = createApplicationContext();
analyzers = new FailureAnalyzers(context);
// 准备上下文
// 1.将environment保存到容器中
// 2.触发监听事件——调用每个SpringApplicationRunListeners的contextPrepared方法
// 3.调用ConfigurableListableBeanFactory的registerSingleton方法向容器中注入applicationArguments与printedBanner
// 4.触发监听事件——调用每个SpringApplicationRunListeners的contextLoaded方法
prepareContext(context, environment, listeners, applicationArguments,
printedBanner);
// 刷新容器,完成组件的扫描,创建,加载等
refreshContext(context);
afterRefresh(context, applicationArguments);
// 触发监听事件——调用每个SpringApplicationRunListener的finished方法
listeners.finished(context, null);
stopWatch.stop();
if (this.logStartupInfo) {
new StartupInfoLogger(this.mainApplicationClass)
.logStarted(getApplicationLog(), stopWatch);
}
// 返回容器
return context;
}
catch (Throwable ex) {
handleRunFailure(context, listeners, analyzers, ex);
throw new IllegalStateException(ex);
}
}

为了建立调用逻辑画了一张图,比较粗糙

总结

SpringApplication.run一共做了两件事

  • 创建SpringApplication对象;在对象初始化时保存事件监听器,容器初始化类以及判断是否为web应用,保存包含main方法的主配置类。
  • 调用run方法;准备spring的上下文,完成容器的初始化,创建,加载等。会在不同的时机触发监听器的不同事件

https://www.cnblogs.com/davidwang456/p/5846513.html

[TOC]

分布式锁

原因:
目的:

数据库唯一索引

redis 的SETNX

redis的RedLock

分布式事务

CAP

BASE

Paxos

Raft