后端面试高频笔试题（非常规LeetCode类型）

目录

1. 常见的五种单例模式的实现⽅式
2. 约瑟夫环 （递归）
3. 交替打印奇偶数 （Semaphore、synchronized搭配wait、notify）
4. 交替打印 ABC （Semaphore）
5. 三个线程交替打印 1 到 99 （Semaphore、AtomicInteger）
6. 实现⼀个线程安全的计数器 （ThreadPool、AtomicInteger / LongAdder）
7. 控制三个线程的执⾏顺序 （CountDownLatch、join）
8. 五⼈赛跑裁判 （ThreadPool、AtomicInteger、CountDownLatch）
9. LRU缓存（升级版：带缓存过期时间）

常见的五种单例模式的实现⽅式

1、枚举（推荐）:

public enum Singleton {INSTANCE;public void doSomething(String str){System.out.println(str);}
}

《Effective Java》 作者推荐的⼀种单例实现⽅式，简单⾼效，⽆需加锁，线程安全，可以避免通过反射破坏枚举单例。

2、静态内部类（推荐）:

public class Singleton {// 私有化构造方法public Singleton() {}// 对外提供获取实例的公共⽅法public static Singleton getInstance() {return SingletonInner.INSTANCE;}// 定义静态内部类private static class SingletonInner {private final static Singleton INSTANCE = new Singleton();}
}

当外部类 Singleton 被加载的时候，并不会创建静态内部类 SingletonInner 的实例对象。只有当调⽤ getInstance() ⽅法时， SingletonInner 才会被加载，这个时候才会创建单例对象INSTANCE 。INSTANCE 的唯⼀性、创建过程的线程安全性，都由 JVM 来保证。

这种⽅式同样简单⾼效，⽆需加锁，线程安全，并且⽀持延时加载。

3、双重校验锁:

public class Singleton {private volatile static Singleton uniqueInstance;// 私有化构造⽅法private Singleton(){}public static Singleton getInstance(){//先判断对象是否已经实例过，没有实例化过才进⼊加锁代码if(uniqueInstance == null){//类对象加锁synchronized (Singleton.class){if (uniqueInstance == null){uniqueInstance = new singlton();}}}return uniqueInstance;}
}

uniqueInstance 采⽤ volatile 关键字修饰也是很有必要的， uniqueInstance = new Singleton();

这段代码其实是分为三步执⾏：

1. 为 uniqueInstance 分配内存空间
2. 初始化 uniqueInstance
3. 将 uniqueInstance 指向分配的内存地址

但是由于 JVM 具有指令重排的特性，执⾏顺序有可能变成 1->3->2。指令排在单线程环境下不会出现问题，但是在多线程环境下会导致⼀个线程获得还没有初始化的实例。例如，线程 T1 执⾏了 1 和 3，此时 T2 调⽤ getUniqueInstance () 后发现 uniqueInstance 不为空，因此返回 uniqueInstance ，但此时 uniqueInstance 还未被初始化。

这种⽅式实现起来较麻烦，但同样线程安全，⽀持延时加载。

4、饿汉式：

public class HungrySingleton {// 类加载时就创建实例，保证线程安全private static final HungrySingleton INSTANCE = new HungrySingleton();// 私有构造方法，防止外部实例化private HungrySingleton() {}// 获取单例实例public static HungrySingleton getInstance() {return INSTANCE;}
}

利⽤ Java 的静态特性，在类加载时就创建实例，天然线程安全，但可能会导致资源浪费。

5、懒汉式：

public class LazySingleton {private static LazySingleton instance;// 私有构造方法，防止外部实例化private LazySingleton() {}// 线程不安全的懒汉式public static LazySingleton getInstance() {if (instance == null) {instance = new LazySingleton();}return instance;}
}

在第⼀次使⽤时才创建实例。在多线程环境下，可能会出现多个线程同时进入 if (instance == null)语句块，导致创建多个实例，不符合单例模式的设计。

五种单例模式对比

方式	线程安全性	是否懒加载	实现难度	性能
饿汉式	✅ 线程安全	❌ 不是懒加载	⭐⭐ 易实现	⭐⭐⭐ 访问快
懒汉式（非线程安全）	❌ 线程不安全	✅ 懒加载	⭐⭐ 易实现	⭐⭐⭐ 访问快
懒汉式（DCL双重检查锁）	✅ 线程安全	✅ 懒加载	⭐⭐⭐ 代码复杂	⭐ 访问需加锁
静态内部类	✅ 线程安全	✅ 懒加载	⭐⭐ 易实现	⭐⭐⭐ 访问快

---

约瑟夫环

约瑟夫环问题的核心思想是：一群人围成一圈，从某个起点开始依次报数，报到特定数字的人出局，直到只剩下最后一个人为止。

求解思路

这个问题可以用 递推公式 来表示：

其中：

• f(n, k) 代表 n 个人围成一圈，每次报数到 k 的人出局，最终留下的人的编号。
• 递归的终止条件是当 n = 1 时，唯一的那个人自然是编号 1（即 f(1, k) = 1)。
• 递推公式的含义是：在 n - 1 个人的情况下找到安全位置，然后映射到当前 n 个人的编号。

---

换个更直观的理解

想象有 n 个人站成一个圈，他们按顺序报数，每报到 k 的人出局。我们希望知道最终谁能存活下来。

• 从 1 个人开始（显然他是幸存者）。
• 增加到 2 个人，谁存活取决于前一个人的位置加上 k，再取模计算位置。
• 每次增加 1 个人，都要重新计算安全位置。

这就像我们 不断从后往前推导，找到一个人站在“安全位置”。最终，我们得到了 最后留下的那个人的编号。

---

代码实现

public class JosephusProblem {public static int josephus(int n, int k) {// 如果只有⼀个⼈，则返回 1if (n == 1) return 1;return (josephus(n - 1, k) + k - 1) % n + 1;}public static void main(String[] args) {int n = 10;int k = 3;System.out.println("最后留下的人的编号是：" + josephus(n, k));}
}

输出：

最后留下的人的编号是：4

---

交替打印奇偶数

问题描述：写两个线程打印 1-100，⼀个线程打印奇数，⼀个线程打印偶数。

这道题的实现⽅式还是挺多的，线程的等待/通知机制 （ wait() 和 notify() ） 、信号Semaphore 等都可以实现。

synchronized+wait/notify 实现

/** synchronized+wait/notify 实现*/
class ParityPrinter {private final int max;// 从1开始计数private int count = 1;private final Object lock = new Object();public ParityPrinter(int max) {this.max = max;}public void printOdd() {print(true);}public void printEven() {print(false);}private void print(boolean isOdd) {while (count <= max) {synchronized (lock) {while (isOdd == (count % 2 != 0)) {System.out.println(Thread.currentThread().getName() + " : " + count++);lock.notify();  // 唤醒另一个线程}// 只有正确的线程才能打印，错误的线程会 lock.wait() 进入等待状态try {lock.wait();} catch (InterruptedException e) {Thread.currentThread().interrupt();return;}}}}
}public class OddAndEven {public static void main(String[] args) {// 打印 1-100ParityPrinter printer = new ParityPrinter(100);// 创建打印奇数和偶数的线程Thread t1 = new Thread(printer::printOdd, "Odd");Thread t2 = new Thread(printer::printEven, "Even");t1.start();t2.start();}
}

输出：

Odd : 1
Even : 2
Odd : 3
Even : 4
Odd : 5
...
Odd : 95
Even : 96
Odd : 97
Even : 98
Odd : 99
Even : 100

Semaphore 实现

如果想要把上⾯的代码修改为基于 Semaphore 实现也挺简单的。

/*** Semaphore 实现*/
class ParityPrinter {private int max;private int count = 1;private Semaphore semaphoreOdd = new Semaphore(1);private Semaphore semaphoreEven = new Semaphore(0);public ParityPrinter(int max) {this.max = max;}public void printOdd() {print(semaphoreOdd, semaphoreEven);}public void printEven() {print(semaphoreEven, semaphoreOdd);}public void print(Semaphore cur, Semaphore next) {while (true) {try {// 信号量 -1 cur.acquire();// 防止 max 取值导致多打印或者死锁if (count > max) {next.release();break;}System.out.println(Thread.currentThread().getName() + " : " + count++);// 信号量 +1 next.release();} catch (InterruptedException e) {Thread.currentThread().interrupt();return;}}}
}public class OddAndEven {public static void main(String[] args) {// 打印 1-100ParityPrinter printer = new ParityPrinter(100);// 创建打印奇数和偶数的线程Thread t1 = new Thread(printer::printOdd, "Odd");Thread t2 = new Thread(printer::printEven, "Even");t1.start();t2.start();}
}

可以看到，我们这⾥使⽤两个信号 semaphoreOdd 和 semaphoreEven 来确保两个线程交替执⾏。semaphoreOdd 信号先获取，也就是先执⾏奇数输出。⼀个线程执⾏完之后，就释放下⼀个信号。

输出：

Odd : 1
Even : 2
Odd : 3
Even : 4
Odd : 5
Even : 6
Odd : 7
Even : 8
...
...
...
Odd : 95
Even : 96
Odd : 97
Even : 98
Odd : 99
Even : 100

---

交替打印 ABC

问题描述：写三个线程打印 “ABC”，⼀个线程打印 A，⼀个线程打印 B，⼀个线程打印 C，⼀共打印 10 轮。

这个问题其实和上⾯的交替打印奇偶数是⼀样的。

class ABCPrinter {private int max;private Semaphore semaphoreA = new Semaphore(1);private Semaphore semaphoreB = new Semaphore(0);private Semaphore semaphoreC = new Semaphore(0);public ABCPrinter(int max) {this.max = max;}public void printerA() {print(semaphoreA, semaphoreB, "A");}public void printerB() {print(semaphoreB, semaphoreC, "B");}public void printerC() {print(semaphoreC, semaphoreA, "C");}private void print(Semaphore cur, Semaphore next, String x) {for (int i = 0; i < max; i++) {try {cur.acquire();System.out.println(Thread.currentThread().getName() + " : " + x);next.release();} catch (InterruptedException e) {e.printStackTrace();}}}
}public class ABC {public static void main(String[] args) {ABCPrinter abcPrinter = new ABCPrinter(30);Thread a = new Thread(abcPrinter::printerA, "Thread 1");Thread b = new Thread(abcPrinter::printerB, "Thread 2");Thread c = new Thread(abcPrinter::printerC, "Thread 3");a.start();b.start();c.start();}
}

输出：

Thread 1 : A
Thread 2 : B
Thread 3 : C
Thread 1 : A
Thread 2 : B
Thread 3 : C
...
...
...
Thread 1 : A
Thread 2 : B
Thread 3 : C

---

三个线程交替打印 1 到 99

问题描述：写三个线程 A、B、C，A 线程打印 3n+1，B 线程打印 3n+2，C 线程打印 3n+3。

这道题和三个线程交替打印 ABC 这道题有挺多相似之处，唯一不同之处就是对count计数的调整，这次我们选用线程安全的原子类AtomicInteger 来作替代。话不多说上代码：

class NumPrinter {private final int max;// 用线程安全的原子类来替代count变量private final AtomicInteger count = new AtomicInteger(1);private final Semaphore semaphoreA = new Semaphore(1);private final Semaphore semaphoreB = new Semaphore(0);private final Semaphore semaphoreC = new Semaphore(0);public NumPrinter(int cap) {this.max = cap;}public void printerA() {print(semaphoreA, semaphoreB);}public void printerB() {print(semaphoreB, semaphoreC);}public void printerC() {print(semaphoreC, semaphoreA);}private void print(Semaphore cur, Semaphore next) {while (true){try {cur.acquire();// 取值并逐渐递增int value = count.getAndIncrement();if (value > max) {  // 超出范围，释放信号量防止死锁next.release();return;}System.out.println(Thread.currentThread().getName() + " : " + value);next.release();} catch (InterruptedException e) {Thread.currentThread().interrupt();return;}}}
}public class OneTo99 {public static void main(String[] args) {NumPrinter numPrinter = new NumPrinter(99);Thread a = new Thread(numPrinter::printerA,"Thread A");Thread b = new Thread(numPrinter::printerB,"Thread B");Thread c = new Thread(numPrinter::printerC,"Thread C");a.start();b.start();c.start();}
}

输出：

Thread A : 1
Thread B : 2
Thread C : 3
Thread A : 4
Thread B : 5
Thread C : 6
Thread A : 7
Thread B : 8
...
...
...
Thread A : 94
Thread B : 95
Thread C : 96
Thread A : 97
Thread B : 98
Thread C : 99

---

实现⼀个线程安全的计数器

问题描述：实现⼀个线程安全的计数器，100 个线程，每个线程累加 100 次。

AtomicLong 通过使⽤ CAS（Compare-And-Swap） 操作，实现了⽆锁的线程安全机制，能够对⻓整型数据进⾏原⼦操作。⾼并发的场景下，乐观锁相⽐悲观锁来说，不存在锁竞争造成线程阻塞，也不会有死锁的问题，在性能上往往会更胜⼀筹。

public class SafeCounter {public static void main(String[] args) {// 创建⼀个线程安全的计数器AtomicLong counter = new AtomicLong();// 创建⼀个固定⼤⼩的线程池ExecutorService executor = Executors.newFixedThreadPool(100);for (int i = 0; i < 100; i++) {// 100 个线程，每个线程累加 100 次executor.submit(() -> {for (int j = 0; j < 100; j++) {counter.getAndIncrement();}});}// 关闭线程池executor.shutdown();System.out.println("Final Counter Value: " + counter.get());}
}

输出：

10000

虽然 AtomicLong 的性能已经相当优秀，但在⾼并发场景下仍存在⼀些效率问题。JDK 8 新增了⼀个原⼦性递增或者递减类 LongAdder ⽤来克服在⾼并发下使⽤ AtomicLong 的⼀些缺点。

使⽤ LongAdder 改造后的代码如下：

public class SafeCounter {public static void main(String[] args) {LongAdder counter = new LongAdder();// 创建⼀个固定⼤⼩的线程池ExecutorService executor = Executors.newFixedThreadPool(100);for (int i = 0; i < 100; i++) {// 100 个线程，每个线程累加 100 次executor.execute(() -> {for (int j = 0; j < 100; j++) {counter.increment();}});}// 关闭线程池executor.shutdown();System.out.println("Final Counter Value: " + counter.sum());}
}

LongAdder 使⽤ increment() ⽅法累加，所有累加的总和通过 sum() ⽅法获取。

---

控制三个线程的执⾏顺序

问题描述：假设有 T1、T2、T3 三个线程，你怎样保证 T2 在 T1 执⾏完后执⾏，T3 在 T2 执⾏完后执⾏？

这道题不难，⼤部分⼈都是⽤ join() 或者 CountDownLatch 实现。话不多说上代码：

public class ThreadSequence {public static void main(String[] args) {// join();countDownLatch();}private static void countDownLatch() {CountDownLatch latch1 = new CountDownLatch(1);CountDownLatch latch2 = new CountDownLatch(1);// 创建三个线程Thread t1 = new Thread(() -> {try {System.out.println("T1 is running");Thread.sleep(1000);System.out.println("T1 finished");} catch (InterruptedException e) {e.printStackTrace();} finally {latch1.countDown(); // T1 完成后释放 latch1}});Thread t2 = new Thread(() -> {try {// 等待 T1 完成latch1.await();System.out.println("T2 is running");Thread.sleep(1000); // 模拟工作System.out.println("T2 finished");} catch (InterruptedException e) {e.printStackTrace();} finally {latch2.countDown(); // T2 完成后释放 latch2}});Thread t3 = new Thread(() -> {try {// 等待 T2 完成latch2.await();System.out.println("T3 is running");Thread.sleep(1000); // 模拟工作System.out.println("T3 finished");} catch (InterruptedException e) {e.printStackTrace();}});// 启动所有线程t1.start();t2.start();t3.start();}private static void join() {// 创建三个线程Thread t1 = new Thread(() -> {System.out.println("T1 is running");try {Thread.sleep(1000);} catch (InterruptedException e) {e.printStackTrace();}System.out.println("T1 finished");});Thread t2 = new Thread(() -> {System.out.println("T2 is running");try {Thread.sleep(1000); // 模拟工作} catch (InterruptedException e) {e.printStackTrace();}System.out.println("T2 finished");});Thread t3 = new Thread(() -> {System.out.println("T3 is running");try {Thread.sleep(1000); // 模拟工作} catch (InterruptedException e) {e.printStackTrace();}System.out.println("T3 finished");});try {// 启动 T1 并等待其完成t1.start();t1.join();// T1 完成后启动 T2 并等待其完成t2.start();t2.join();// T2 完成后启动 T3 并等待其完成t3.start();t3.join();} catch (InterruptedException e) {e.printStackTrace();}}
}

---

五⼈赛跑裁判

问题描述：有 5 个⼈赛跑，请你设计⼀个多线程的裁判程序给出他们赛跑的结果顺序，5 个⼈的速度随机处理。

我们借助线程池和 CountDownLatch 来实现这⼀需求即可。

public class Racing {// 使⽤ AtomicInteger 确保线程安全public static AtomicInteger num = new AtomicInteger(0);public static String[] res = new String[5];private static final int threadCount = 5;public static void main(String[] args) throws InterruptedException {// 创建⼀个固定⼤⼩的线程池ExecutorService threadPool = Executors.newFixedThreadPool(threadCount);CountDownLatch latch = new CountDownLatch(threadCount);Random random = new Random();for (int i = 0; i < threadCount; i++) {final int id = i + 1;threadPool.execute(() -> {try {// 模拟随机耗时int sleepTime = random.nextInt(401) + 100; // 100ms ~ 500msThread.sleep(sleepTime);// 使⽤ AtomicInteger 确保线程安全int index = num.getAndIncrement();res[index] = "运动员" + id + "消耗的时间为" + sleepTime;} catch (InterruptedException e) {throw new RuntimeException(e);} finally {latch.countDown();}});}// 等待所有线程完成latch.await();threadPool.shutdown();// 输出结果for (String x : res) {System.out.println(x);}}
}

输出：

运动员5消耗的时间为162
运动员2消耗的时间为181
运动员4消耗的时间为266
运动员3消耗的时间为425
运动员1消耗的时间为452

解题的核⼼是 AtomicInteger 和 CountDownLatch 类的运⽤：

• AtomicInteger 是⼀个线程安全的整数类，⽀持原⼦性操作。
• CountDownLatch 是⼀个线程同步⼯具类，⽤于让主线程等待其他线程完成⼯作。在本题中，初始化计数器为线程数 5。每个线程完成任务后，调⽤countDownLatch.countDown() ，主线程调⽤countDownLatch.await() 。

完整的执⾏流程如下：

1. 创建⼀个固定⼤⼩的线程池和⼀个 CountDownLatch ，初始化为5。
2. 提交5个线程任务到线程池，模拟每个运动员完成⽐赛的过程：
   • 每个线程随机等待⼀定时间 （100ms~500ms），表示运动员⽐赛时⻓。
   • 使⽤ AtomicInteger 确保线程安全，将⽐赛结果写⼊数组。
   • 每个线程完成后，调⽤ countDown() 减少计数器值。
3. 主线程调⽤ await() ，等待所有线程完成。
4. 所有线程完成后，主线程输出⽐赛结果。

---

9. LRU缓存（升级版：带缓存过期时间）

👉详情见该博客

---

最后

如果您渴望探索更多精心挑选的高频LeetCode面试题，以及它们背后的巧妙解法，欢迎您访问我的博客，那里有我精心准备的一系列文章，旨在帮助技术爱好者们提升算法能力与编程技巧。

👉更多高频有趣LeetCode算法题

👉LeetCode高频面试题题单

在我的博客中，每一篇文章都是我对算法世界的一次深入挖掘，不仅包含详尽的题目解析，还有我个人的心得体会、优化思路及实战经验分享。无论是准备面试还是追求技术成长，我相信这些内容都能为您提供宝贵的参考与启发。期待您的光临，让我们共同在技术之路上不断前行！