事务

原子性 Atomicity

BUSINESS
sql语句1
sql语句2
COMMIT

原子性：事务操作要么同时发生，要么同时失败，不存在中间情况

通过Undo Log回滚实现

一致性 Consistency

账户500元 -> 扣除1000元 -> 账户-500元
-- 非法操作

一致性：每个操作都必须是合法的，账户信息应该从一个有效状态到另一个有效状态。

隔离性 Isolation

商户1转账500元 -> 余额更新为500元
商户2转账500元 -> 余额更新为500元
-- 没有隔离性

隔离性：两个操作对同一个账户并发操作时，应该表现为不相互影响类似串行的操作。

持久性 Durability

转账500元到余额 --服务器宕机--> 余额0元

持久性：操作更新成功后，更新的结果应该永久地保留下来，不会因为宕机等问题而丢失。

阅读全文 »

Git配置

远程仓库 - 廖雪峰的官方网站 (liaoxuefeng.com)

创建ssh key，在c盘用户目录.git文件夹中
ssh-keygen -t ed25519 -C "youremail@example.com"
ssh-keygen -l -f ~/.ssh/id_rsa 可以查看秘钥的配置信息，包括邮箱
在GitHub账号设置页面，添加ssh key，复制.ssh/id_rsa.pub的信息，点击创建即可
测试是否成功：ssh -T git@github.com
注意：如果测试不成功，可能是反向代理的问题

Github 远程仓库

在github上新建一个仓库
git remote add origin git@github.com:github账号名称/仓库名称.git 关联仓库，origin是远程库的名字
git push -u origin master把本地库内容（master分支）推送到远程库（oringin），-u 参数表示会把本地master分支和远程master分支关联起来，方便后面简化命令

git remote set-url origin <URL>更改仓库地址

项目含金量 stars 1k+
fork 拷贝项目到自己的仓库
pull request 合并分支

NJU

学习编程语言如C、Rust
精选精读论文
STFW：比百度更高效的办法

基本操作

General

# 返回给定模式的keys
KEYS patter
KEYS * # 返回全部
KEYS set* # 返回set开头的keys
EXISTS key
TYPE key
DEL key

String

SET key value
GET key
# Set Extend Time
SETEX key seconds value
# Set When Key Not Exist
SETNX key value

Hash

HSET key field value
HGET key field
HDEL key field
# Get All Fields
HKEYS key
# Get All Values
HVALS key

flowchart LR
    key[key]
    item[
    field1: value1
    field2: value2
    ]
    key --> item

List

LPUSH key value1 value2
# Get Key From Start To Stop
LRANGE key start stop
# Right POP
RPOP key
# List Length
LLEN key

典型场景

栈

订阅消息

队列，先来后到

如微信、微博订阅消息
阻塞队列B<L|R>POP，队列为空就等待

Set

SADD key mem1 mem2
SMEMBERS key
# Set Size
SCARD key
SINTER key1 key2
SUNION key1 key2
# Delete
SREM key mem1 mem2

典型场景

抽奖

SADD lottery {user_id}
SMEMBERS lottery
# 开奖（适用于单个奖品）
SRANDMEMBER lottery {drawing_count}
# 开奖并删除（适用于多项奖品，不重复得奖）
SPOP lottery {drawing_count}

点赞、收藏、标签

# 点赞
SADD like:{msg_id} {user_id}
# 取消
SREM like:{msg_id} {user_id}
# 用户是否点赞
SISMEMBER like:{msg_id} {user_id}
# 点赞用户列表
SMEMBERS like:{msg_id}
# 点赞用户数
SCARD like:{msg_id}

关注、商品筛选

利用集合特性运算

如共同关注、推荐关注
商品筛选

Sorted Set / ZSet

ZADD key score1 mem1 score2 mem2
# Show List
ZRANGE key start stop (WITHSCORES)
# Increse Member
ZINCRBY key increment member
ZREM key mem1 mem2

典型场景

日/月/年热点排行榜

# 记录浏览量
ZINCRBY hotNews:{date} 1 {news_id}
# Top 10
ZREVRANGE hotNews:{date} 0 9 WITHSCORES
# Recent 7 days
ZUNIONSTORE hotNews:{start_date}-{end_date} 0 9 WITHSCORES

阅读全文 »

Java多线程

回顾：操作系统的进程概念。进程的问题：上下文切换开销。为了解决这个问题，出现了线程。

Thread thread = (() -> {
    // ...
    System.out.pirntln("Sub Thread");
});
thread.start();
System.out.println("Main Thread");

Main Thread # 主线程先输出结果，说明两个线程同时运行！
Sub Thread

线程优先级

Java使用抢占式调度，有以下三种优先级

MIN_PRIORITY
MAX_PRIORITY
NOM_PRIORITY

线程同步

共享内存会出现缓存一致性问题，因此需要线程锁机制保证数据安全性（原子性）。

synchronized // 悲观锁

synchronized (Class.class / this) { ... } // 类锁
synchronized (new Class() / instanceOfClass) { ... } // 实例锁
public synchronized void operation() { ... }

锁

synchronized使用的锁存储在Java对象头中。

重量级锁

JDK6以前，synchronized被称为重量级锁。因为Java的线程是映射在OS原生线程上，上下文切换成本高；直到JDK6以后才优化了锁的实现。
简单来说，每个等待锁都会被封装成ObjectWaiter对象，分为三个区域

direction: right
Entry Set -> The Owner
The Owner <-> Wait Set

Entry Set会排队，直到它成为The Owner，享有资源。当The Owner调用wait()方法，就会挂起进入Wait Set，直到wait()所等待的操作完成。
但是每个线程占用同步代码块的时间并不长，完全不需要挂起又唤醒。
因此，可以使用自旋锁

自旋锁

调用wait()，自旋锁并不是被挂起，而是无限循环是否能够获取锁；当等待时间太长，会恢复重量锁机制。
JDK6以后，自旋时间是动态变化的。如果某个线程经常自旋失败，它会直接使用重量级锁；反之，则会延长自旋时间。

轻量级锁

JDK6后，为了减少获得和释放锁的消耗，引入了轻量级锁。
轻量级锁的设计目标是，在无竞争状态下减少重量级锁带来的性能消耗（切换内核态、线程阻塞引发线程切换）。

如果只有一个线程占用资源，那就不要加锁、解锁。
轻量级锁需要向系统申请互斥量。

CAS算法

Compare and Swap
CAS算法不是加锁，而是通过比较来判断对象是否已被修改，如果没有直接替换；如果被修改，那么修改失败。

轻量级锁就是使用CAS算法，如果CAS失败，那么进入重量级锁状态。

偏向锁

Biased Locking
-XX:UserBiasLock
当只有一个线程反复访问同步代码块，JVM直接让该线程获取锁，避免不必要的不同步操作。
根据对象头底层数据结构，如果对象调用过hashCode()通过哈希值来检查一致性，那么对象头就没有空间存放ThreadId了（JVM通过这个id判断是否频繁访问），此时该线程只能使用轻量级锁。

锁消除和锁粗化

如果在运行过程中，根本没有出现资源竞争，那就会直接把锁消除掉。
如果某个资源频繁地开锁解锁（比如在循环内部synchronized），JVM会把锁的范围放大，避免加锁解锁的开销。

Java Memory Model

Java Thread 1 <-> Working Memory 1 <-> Save/Load Operation 
Java Thread 2 <-> Working Memory 2 <-> Save/Load Operation 
Java Thread 3 <-> Working Memory 3 <-> Save/Load Operation 
Save/Load Operation <-> Main Memory

JMM内存模型中有以下规定：

所有变量存储在主内存
每条线程有自己的工作内存，不能直接操作主内存
不同线程间互相隔离，要传递内容，必须通过主内存

volatile

volatile的最大作用是保证变量可见性，即发生修改后强制刷新到主内存中，使其他线程的缓存失效；相当于通知了其他线程要更新变量为最新版本。
注意，volatile不能保证原子性。

Lock&Condition

Lock用法：

Lock lock = new ReentrantLock(); // 可重入锁
Runnable action = () -> {
    for (int i = 0; i < 100000; i += 1) {
        lock.lock();
        i += 1; // 保证同一时刻只有一个线程操作i
        lock.unlock();
    }
}

new Thread(action).start();
new Thread(action).start();

Condition用法：

Condition cond = lock.newCondition();

Thread thread1 = () -> {
    ...
    cond.await(); // 等待
    ...
}
Thread thread2 = () -> {
    ...
    cond.signal(); // 唤醒await线程
    ...
}
new Thread(thread1).start();
new Thread(thread2).start();

LeetCode 1114 顺序打印123

class Foo {
    private Lock lock = new ReentrantLock();
    private Condition cond1 = lock.newCondition();
    private Condition cond2 = lock.newCondition();
    private volatile int state = 0;

    public Foo() { }

    public void first(Runnable printFirst) throws InterruptedException {
        lock.lock();
        try {
            // printFirst.run() outputs "first". Do not change or remove this line.
            printFirst.run();
            state = 1;
            cond1.signal();
        } finally {
            lock.unlock();
        }
    }

    public void second(Runnable printSecond) throws InterruptedException {
        lock.lock();
        try {
            while (state != 1) {
                cond1.await();
            }
            // printSecond.run() outputs "second". Do not change or remove this line.
            printSecond.run();
            state = 2;
            cond2.signal();
        } finally {
            lock.unlock();
        }
    }

    public void third(Runnable printThird) throws InterruptedException {
        lock.lock();
        try {
            while (state != 2) {
                cond2.await();
            }
            // printThird.run() outputs "third". Do not change or remove this line.
            printThird.run();
        } finally {
            lock.unlock();
        }
    }
}

可重入锁

Re-entrant-Lock
这种锁可以多次加锁，同时也要多次解锁才算真的解锁了。

可重入锁是一种排他锁，其他线程必须等锁释放了才可以获取到锁。

公平锁与非公平锁

公平锁：按照申请锁的时间去获得锁，会进入队列排队
非公平：抢占式获取锁

读写锁

读写锁在同一时刻，可以让多个线程获取到锁。

读锁：没有线程占用写锁的情况下，同一时间可以有多个线程加读锁。
写锁：没有线程占用读锁的情况下，只有一个线程可以加写锁。

Lock reEntLock = new ReentrantLockReadWriteLock();
reEntLock.readLock().lock();
reEntLock.writeLock().lock();

锁降级、锁升级

reEntLock.writeLock().lock();
// 先加写锁，后加读锁，降级
reEntLock.readLock().lock();

...

// 然后释放写锁，只留下读锁，锁降级
reEntLock.writeLock().unlock();

AQS实现

Abstract Queued Synchronizer
在AQS中，一个线程获取锁后，其他线程进入等待队列。
等待队列由双向链表实现。

算法

发表于 2023-11-09 更新于 2025-03-20

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

阅读全文 »

3513 岛屿个数

#外岛数量 #bfs

杰克船长算法

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

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

可是测试用例是这样的：

这个测试用例，只有(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(N^2)$ 的复杂度。因此，可以使用一张表，使用containsKey方法识别是否存在当前i的target - nums[i]，即可减少一重循环。

关键思想

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

最长连续序列

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

优化

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

关键思想

去重；不处理中间值

阅读全文 »

0.0 代码合并流程

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

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

切换到自己的分支self，git 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 初始化仓库

本地仓库：git init创建一个新的 git 仓库，其数据会存放在一个名为 .git 的目录下
删除仓库：删除 .git 文件夹

git add <文件名字，*表示全部>
# 提交到暂存区，并附上注释
git commit -m 'initial project version' 
# 修改最近的一次提交
git commit --ammend

远程仓库：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"

阅读全文 »

动态规划学习指南

发表于 2024-10-22 更新于 2025-03-16

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

阅读全文 »

OS 操作系统

发表于 2024-08-07 更新于 2025-03-15

操作系统：原理与实现

Chapter3 操作系统结构

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

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

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

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

宽进严出原则：容忍各种输入（包括恶意输入），严格控制模块的对外输出

微内核

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

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

内核态部分，称为 $\mu kernel$

微内核优势：

弹性硬件拓展能力
硬件异构实现
功能安全
信息安全
时延确定

现代操作系统特征：1）虚拟内存；2）用户态、内核态隔离。

阅读全文 »

事务

原子性 Atomicity

一致性 Consistency

隔离性 Isolation

持久性 Durability

Git配置

Github 远程仓库

github trending 热门软件

NJU

基本操作

General

String

Hash

List

典型场景

栈

订阅消息

Set

典型场景

抽奖

点赞、收藏、标签

关注、商品筛选

Sorted Set / ZSet

典型场景

日/月/年热点排行榜

Java多线程

线程优先级

线程同步

锁

重量级锁

自旋锁

轻量级锁

CAS算法

偏向锁

锁消除和锁粗化

Java Memory Model

volatile

Lock&Condition

LeetCode 1114 顺序打印123

可重入锁

公平锁与非公平锁

读写锁

锁降级、锁升级

AQS实现

3513 岛屿个数

杰克船长算法

Hash

字母异位词

两数之和

关键思想

最长连续序列

关键思想

0.0 代码合并流程

1.0 第一件事git config

2.0 初始化仓库

配置SSH

Tag

Patterns

操作系统：原理与实现

Chapter3 操作系统结构

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

微内核