微服务

非单体项目,可以用下面的脚本启动微服务。

#!/bin/bash

# 获取服务名称和额外参数
SERVICE_NAME=$1
shift # 移除第一个参数(服务名),将剩余参数保存到 $@
EXTRA_ARGS="$@"

# 检查是否输入服务名称
if [ -z "$SERVICE_NAME" ]; then
echo "Usage: ./run.sh <servicename|all> [additional_maven_args]"
exit 1
fi

# 定义运行单个服务的函数
run_service() {
local service=$1
local args=$2
echo "Building and running $service with args: $args..."
mvn clean install -pl $service -am
if [ "$service" == "gateway/" ]; then
echo "Gateway starting..."
mvn spring-boot:run -pl $service -Dreactor.netty.http.server.accessLogEnabled=true $args
else
mvn spring-boot:run -pl $service $args
fi
}

# 如果输入 "all",运行所有服务(默认不传参)
if [ "$SERVICE_NAME" == "all" ]; then
echo "Building and running all services..."
mvn clean install -pl "!generator"
for module in $(mvn help:evaluate -Dexpression=project.modules -q -DforceStdout | sed -e 's/<[^>]*>//g' -e 's/\s*//g' | tr ',' '\n'); do
if [ "$module" != "generator" ]; then
echo "Running $module..."
mvn spring-boot:run -pl $module
fi
done
else
# 运行指定的单个服务,并传递额外参数
run_service $SERVICE_NAME "$EXTRA_ARGS"
fi

核心命令是这一条:

mvn spring-boot:run -pl $your_service

想要增加JVM参数,指定端口可以加上

-Dspring-boot.run.arguments=--server.port=$your_port

  • 复杂度分析:数据结构和算法的评价维度与方法。时间复杂度、空间复杂度的推算方法、常见类型、示例等。
  • 数据结构:基本数据类型,数据结构的分类方法。数组、链表、栈、队列、哈希表、树、堆、图等数据结构的定义、优缺点、常用操作、常见类型、典型应用、实现方法等。
  • 算法:搜索、排序、分治、回溯、动态规划、贪心等算法的定义、优缺点、效率、应用场景、解题步骤、示例题目等。
阅读全文 »

3513 岛屿个数

#外岛数量 #bfs

杰克船长算法

杰克船长在公海上游荡,每发现一处岛屿,他就会绕着岛走一圈,并把这个岛标记到地图上。

这个问题的解决方法就在这里:我们一定要有一片完全连通的公海,只有在公海上遇到岛屿,才标记岛屿数量;绝不踏入内海。

可是测试用例是这样的:

5 5
01111
11001
10101
10001
11111

这个测试用例,只有(0, 0)是公海,怎么办呢?
我们用一圈公海把测试用例包围起来:

private static void processInput(Scanner sc) {
M = sc.nextInt();
N = sc.nextInt();
sc.nextLine();
map = new int[M + 2][N + 2]; // 注意+2,多一圈'0'表示公海
visitedSea = new boolean[M + 2][N + 2];
visitedIsland = new boolean[M + 2][N + 2];
cnt = 0;
for (int x = 1; x <= M; x += 1) {
String line = sc.nextLine();
for (int y = 1; y <= N; y += 1) {
map[x][y] = line.charAt(y - 1) - '0';
}
}
}
阅读全文 »

Hash

字母异位词

排序每一个单词,就知道是不是异位词。

两数之和

从数组中,找到nums[i] + nums[j] == target,并返回{ i, j }
思路是双重循环,遍历每一个元素,求和是否为target。
然而,双重循环需要O(N2)O(N^2)的复杂度。因此,可以使用一张表,使用containsKey方法识别是否存在当前i的target - nums[i],即可减少一重循环。

关键思想

用Map高效率查找,减少一重循环。

最长连续序列

从乱序数组中,找到最长连续(数组中不一定连续)的序列。要求O(N)O(N)
首先用数组的值存入哈希表,然后遍历数组,判断map.constains(curNum++)
然而,即使这样还是效率不够高。

优化

  1. 中间值不进入循环,序列开始值才进入,使用!contains(curNum - 1)判断是否为序列开始值
  2. 去重,不要哈希表,不需要键值对,使用哈希Set,只存储值。

关键思想

去重;不处理中间值

阅读全文 »

0.0 代码合并流程

  1. 在各自的分支self上进行开发
  2. 切换到develop分支,git pull --rebase同步最新代码

不要使用Git Pull
git pull会创建一个新的merge commit,这样提交历史不是一条清晰的线,包含无意义的分支合并,非常混乱。
git pull --rebase会解决这个问题,这个命令首先把你的commit放到一边,拉取最新分支状态,最后为你自动变基到最新状态。
如果遇到合并冲突,使用git rebase --abort撤回rebase,然后使用git pull或者使用交互式变基。

  1. 切换到自己的分支selfgit rebase develop对齐代码合并冲突

分支是临时的,完成了分支的职责后,就删除此分支。不要重复用分支,而是从主分支再创建一条特性分支。

1.0 第一件事git config

  • git config --list --show-origin查看所有git配置以及所在文件
  • 使用git config --global可以设置git的基本信息(如用户名、邮箱),使用--unset取消设置
    1. 配置你的名称、邮箱以及编辑器
git config --global user.name "191220000-Zhang San" 
# 全局设置名称
git config --global user.email "zhang3@email.com"
git config --global core.editor vim

# instead of
git config --global url.git@github.com:.insteadOf https://github.com/
# alias
git config --global alias.cin "commit --amend --no-edit"

2.0 初始化仓库

  1. 本地仓库:git init创建一个新的 git 仓库,其数据会存放在一个名为 .git 的目录下
    删除仓库:删除 .git 文件夹
git add <文件名字,*表示全部>
# 提交到暂存区,并附上注释
git commit -m 'initial project version'
# 修改最近的一次提交
git commit --ammend

  1. 远程仓库:git clone克隆远端仓库
# 查看remote
git remote -v

# 添加remote
git remote add origin project_repository_url.git
# 设置push分支为自己的仓库
git remote set-url --add --push origin your_repository_url.git

git clone <网址> <仓库存放文件夹名>
# 使用http克隆

配置SSH

不推荐dsa和rsa,推荐ed25519

ssh-keygen -t ed25519 -C "your_email@email.com"

Tag

git tag v0.0.version
git tag -a v0.version -m "Your Comments to the version"
阅读全文 »

Author:aatalyk
Origin:Link

Before starting the topic let me introduce myself. I am a Mobile Developer currently working in Warsaw and spending my free time for interview preparations. I started to prepare for interviews two years ago. At that time I should say I could not solve the two sum problem. Easy problems seemed to me like hard ones so most of the time I had to look at editorials and discuss section. Currently, I have solved ~800 problems and time to time participate in contests. I usually solve 3 problems in a contest and sometimes 4 problems. Ok, lets come back to the topic.

Recently I have concentrated my attention on Dynamic Programming cause its one of the hardest topics in an interview prep. After solving ~140 problems in DP I have noticed that there are few patterns that can be found in different problems. So I did a research on that and find the following topics. I will not give complete ways how to solve problems but these patterns may be helpful in solving DP.

Patterns

  1. Minimum (Maximum) Path to Reach a Target
  2. Distinct Ways
  3. Merging Intervals
  4. DP on Strings
  5. Decision Making
阅读全文 »

操作系统:原理与实现

Chapter3 操作系统结构

复杂度管理方法 M.A.L.H

Modularity: 模块化,分而治之
Abstraction: 抽象,接口与实现分离,遵循宽进严出原则。例如虚拟内存、文件系统

对于大型系统,只有模块化和抽象,可能导致划分模块太多,交互关系复杂,因此还需要引入分层和层次结构控制复杂度。

Layering: 分层,每个层级是一套完整机制。通常一个模块只能与本层和上下层交互,不能跨层。例如OSI、TCP/IP
Hierarchy: 层次结构,大的子系统由多个小的子系统组织成。即同级模块的分层

宽进严出原则:容忍各种输入(包括恶意输入),严格控制模块的对外输出

微内核

宏内核架构:单点bug使整个系统崩溃。
微内核:解耦单个功能/模块(如文件系统、设备驱动)作为独立服务隔离运行,使内核成为一个最小功能集。

微内核架构服务隔离,单点出问题系统不会崩溃

内核态部分,称为μkernel\mu kernel

微内核优势:

  1. 弹性硬件拓展能力
  2. 硬件异构实现
  3. 功能安全
  4. 信息安全
  5. 时延确定

现代操作系统特征:1)虚拟内存;2)用户态、内核态隔离。

阅读全文 »

Web浏览器

网址就是请求服务器上对应的文件
DNS从顶级域名开始根据网址查IP。DNS服务器通过缓存查过的IP来加快服务响应(缓存拥有有效期)。
浏览器调用Socket库建立连接管道

TCP/IP协议栈

应用将数据分割为许多个网络包,TCP加上头部发送出去。需要发送的信息会缓存起来,超出计时时间或者数据量大于一个包大小时才发出去。
TCP需要确认对方收到数据,但是为了不浪费时间,实际上TCP在等待确认信息的过程中也在发送包,这个方法称为滑动窗口
为了使接收方有足够的时间处理数据,接收方有一个接收缓存,当缓存满了会在TCP头部中通知发送方;处理完成,缓冲区有空余时也会通过TCP头部通知发送方。
通信完成后,发送方会保留套接字一段时间,以防对方的FINISH信号发送有延迟,把新的相同端口的套接字错误删除。

用电信号传输数据时,用高电平表示1,低电平表示0.为了防止连续的低电平读不出来,会有一条时钟信号(固定切换高低电平)
ICMP:定义各种消息,如超时、无法到达、超出转发能力

UDP在发送的数据少于一个包(重发也只需要发一个包,代价小,如DNS查询控制信息)、发送的数据具有时效性(如音视频,必须快速发送,即使重发也没有意义)的情况下使用。UDP只负责收发数据,对方没收到就全部重发一遍。

1.0 Session

有状态:用户请求接口 -> 从Session中读取用户信息 -> 根据当前的用户来处理业务 -> 返回

缺点:不支持分布式

2.0 Token

无状态:用户携带Token请求接口 -> 从请求中获取用户信息 -> 根据当前的用户来处理业务 -> 返回

<dependency>
<groupId>com.auth0</groupId>
<artifactId>java-jwt</artifactId>
<version>4.3.0</version>
</dependency>
  • 工具类
public class JwtUtils {
//Jwt秘钥
private static final String key = "abcdefghijklmn";

// 根据用户信息创建Jwt令牌
public static String createJwt(UserDetails user){
Algorithm algorithm = Algorithm.HMAC256(key);
Calendar calendar = Calendar.getInstance();
Date now = calendar.getTime();
calendar.add(Calendar.SECOND, 3600 * 24 * 7);
return JWT.create()
.withClaim("name", user.getUsername()) // 配置JWT自定义信息
.withClaim("authorities", user.getAuthorities().stream().map(GrantedAuthority::getAuthority).toList())
.withExpiresAt(calendar.getTime()) // 设置过期时间
.withIssuedAt(now) // 设置创建创建时间
.sign(algorithm); // 最终签名
}

// 根据Jwt验证并解析用户信息
public static UserDetails resolveJwt(String token){
Algorithm algorithm = Algorithm.HMAC256(key);
JWTVerifier jwtVerifier = JWT.require(algorithm).build();
try {
DecodedJWT verify = jwtVerifier.verify(token); // 对JWT令牌进行验证,看看是否被修改
Map<String, Claim> claims = verify.getClaims(); // 获取令牌中内容
if(new Date().after(claims.get("exp").asDate())) // 如果是过期令牌则返回null
return null;
else
// 重新组装为UserDetails对象,包括用户名、授权信息等
return User
.withUsername(claims.get("name").asString())
.password("")
.authorities(claims.get("authorities").asArray(String.class))
.build();
} catch (JWTVerificationException e) {
return null;
}
}
}
  • Filter
public class JwtAuthenticationFilter extends OncePerRequestFilter {  
// 继承OncePerRequestFilter表示每次请求过滤一次,用于快速编写JWT校验规则

@Override
protected void doFilterInternal(HttpServletRequest request, HttpServletResponse response, FilterChain filterChain) throws ServletException, IOException {
// 首先从Header中取出JWT
String authorization = request.getHeader("Authorization");
// 判断是否包含JWT且格式正确
if (authorization != null && authorization.startsWith("Bearer ")) {
String token = authorization.substring(7);
// 开始解析成UserDetails对象,如果得到的是null说明解析失败,JWT有问题
UserDetails user = JwtUtils.resolveJwt(token);
if(user != null) {
// 验证没有问题,那么就可以开始创建Authentication了,这里我们跟默认情况保持一致
// 使用UsernamePasswordAuthenticationToken作为实体,填写相关用户信息进去
UsernamePasswordAuthenticationToken authentication =
new UsernamePasswordAuthenticationToken(user, null, user.getAuthorities());
authentication.setDetails(new WebAuthenticationDetailsSource().buildDetails(request));
// 然后直接把配置好的Authentication塞给SecurityContext表示已经完成验证
SecurityContextHolder.getContext().setAuthentication(authentication);
}
}
// 最后放行,继续下一个过滤器
// 可能各位小伙伴会好奇,要是没验证成功不是应该拦截吗?这个其实没有关系的
// 因为如果没有验证失败上面是不会给SecurityContext设置Authentication的,后面直接就被拦截掉了
// 而且有可能用户发起的是用户名密码登录请求,这种情况也要放行的,不然怎么登录,所以说直接放行就好
filterChain.doFilter(request, response);
}
}
  • Security修改为无状态
// 将Session管理创建策略改成无状态,这样SpringSecurity就不会创建会话了,也不会采用之前那套机制记录用户,因为现在我们可以直接从JWT中获取信息
.sessionManagement(conf -> {
conf.sessionCreationPolicy(SessionCreationPolicy.STATELESS);
})
// 添加我们用于处理JWT的过滤器到Security过滤器链中,注意要放在UsernamePasswordAuthenticationFilter之前
.addFilterBefore(new JwtAuthenticationFilter(), UsernamePasswordAuthenticationFilter.class)

JWT退出登录

采用黑名单方案。一台服务器存储JWT黑名单,共享给所有微服务。

JWT.create()
// 额外添加一个UUID用于记录黑名单,将其作为JWT的ID属性jti
.withJWTId(UUID.randomUUID().toString())
public class JwtUtils {    

private static final HashSet<String> blackList = new HashSet<>();
// 加入黑名单方法
public static boolean invalidate(String token){
Algorithm algorithm = Algorithm.HMAC256(key);
JWTVerifier jwtVerifier = JWT.require(algorithm).build();
try {
DecodedJWT verify = jwtVerifier.verify(token);
Map<String, Claim> claims = verify.getClaims();
//取出UUID丢进黑名单中
return blackList.add(verify.getId());
} catch (JWTVerificationException e) {
return false;
}
}

public static UserDetails resolveJwt(String token){
Algorithm algorithm = Algorithm.HMAC256(key);
JWTVerifier jwtVerifier = JWT.require(algorithm).build();
try {
DecodedJWT verify = jwtVerifier.verify(token);
// 判断是否存在于黑名单中,如果存在,则返回null表示失效
if(blackList.contains(verify.getId()))
return null;
Map<String, Claim> claims = verify.getClaims();
if(new Date().after(claims.get("exp").asDate()))
return null;
return User
.withUsername(claims.get("name").asString())
.password("")
.authorities(claims.get("authorities").asArray(String.class))
.build();
} catch (JWTVerificationException e) {
return null;
}
}
}

Chapter2 指令:计算机的语言

本章将介绍MIPS汇编语言指令。

三条设计原则

  1. 简单源于规整 Simplicity favors regularity.
  2. 越小越快 Smaller is faster.
  3. 优秀的设计需要适宜的折中方案 Good design demands good compromises.

2.2 硬件的操作与操作数

规整

add a, b, c // a = b + c MIPS汇编语言使用这样的固定记法。
每条MIPS算术指令只执行1个操作,仅有3个变量。

操作数必须来自寄存器

变量f、g、h、i、j依次分配给$s0~$s4,编译下面的C语句

f = (g + h) - (i + j);
---
add $t0, $s1, $s2 // t0 = s1 + s2
add $t1, $s3, $s4
sub $s0, $t0, $t1 // s0 = t0 + t1

数据传输

只有少量数据存在寄存器中,因此需要在存储器和寄存器间传输数据

A的基址是存在$s3,编译下面的C语句

A[12] = h + A[8]
---
lw $t0, 32($s3) // 先读数,再相加;32为偏移量,8*4byte
add $t0, $s2, $t0
sw $t0, 48($s3) // 存数

立即数

addi $t0, $t1, 4 // t0 = t1 + 4;无需读取4,作为立即数相加
subi $t0, $t1, 4
阅读全文 »
0%