其他
2025年7月27日大约 8 分钟
其他
线程安全单例
双重检查锁定（DCL）
public class Singleton {
// volatile保证可见性和禁止指令重排
private static volatile Singleton instance;
public static Singleton getInstance() {
if (instance == null) { // 第一次检查 不加锁直接读，效率高
synchronized (Singleton.class) { // 加锁后再次检查，避免多个线程同时创建实例
if (instance == null) { // 第二次检查
instance = new Singleton();
}
}
}
return instance;
}
}静态内部类（推荐）
public class Singleton {
private Singleton() {}
// 静态内部类，延迟加载
private static class SingletonHolder {
private static final Singleton INSTANCE = new Singleton();
}
public static Singleton getInstance() {
return SingletonHolder.INSTANCE;
}
}枚举单例（最安全）
public enum Singleton {
INSTANCE;
public void doSomething() {
System.out.println("单例方法执行");
}
}
// 使用
Singleton.INSTANCE.doSomething();各方案对比：
- DCL：性能好，但实现复杂
- 静态内部类：简单安全，推荐使用
- 枚举：最安全，自动序列化支持
找出输入字符串中所有最长的回文子串
public String[] longestPalindrome(String inPutStr) {
if (inPutStr == null || inPutStr.length() == 0) {
return new String[]{};
}
String longest = "";
// 检查所有可能的子串
for (int i = 0; i < inPutStr.length(); i++) {
for (int j = i; j < inPutStr.length(); j++) {
String substring = inPutStr.substring(i, j + 1);
if (isPalindrome(substring) && substring.length() > longest.length()) {
longest = substring;
}
}
}
// 找出所有与最长回文串长度相同的回文串
List<String> result = new ArrayList<>();
for (int i = 0; i < inPutStr.length(); i++) {
for (int j = i; j < inPutStr.length(); j++) {
String substring = inPutStr.substring(i, j + 1);
if (isPalindrome(substring) && substring.length() == longest.length()) {
if (!result.contains(substring)) {
result.add(substring);
}
}
}
}
return result.toArray(new String[0]);
}
// 辅助方法：检查字符串是否为回文
private boolean isPalindrome(String s) {
int left = 0;
int right = s.length() - 1;
while (left < right) {
if (s.charAt(left) != s.charAt(right)) {
return false;
}
left++;
right--;
}
return true;
}给定一个整数列表，求这些数所有非空子集的和有多少种不同的取值
public int numTilePossibilities(List<Integer> titles) {
Set<Integer> res = new HashSet<>(); // 存储所有子集的和
for(int num : titles) {
Set<Integer> newSums = new HashSet<>(); // 存储新的子集的和
newSums.add(num); // 将当前数字添加到新的子集的和中
for(int sum : res) { // 遍历res中的所有子集的和
newSums.add(sum + num); // 将当前数字添加到新的子集的和中
}
res.addAll(newSums); // 将新的子集的和添加到res中
}
return res.size();
}布尔表达式求值
给定一个布尔表达式，计算有多少种加括号的方式能得到期望的结果。
public long GetNumOfExpress(String express, boolean desired) {
char[] ch = express.toCharArray();
return countWays(ch, 0, ch.length - 1, desired);
}
private long countWays(char[] ch, int start, int end, boolean target) {
// 基础情况：只有一个数字
if (start == end) {
boolean val = ch[start] == '1';
return val == target ? 1 : 0;
}
long count = 0;
// 尝试每个运算符作为主运算符
for (int i = start + 1; i < end; i += 2) {
char op = ch[i];
// 递归计算左右两部分的所有可能
long leftTrue = countWays(ch, start, i - 1, true);
long leftFalse = countWays(ch, start, i - 1, false);
long rightTrue = countWays(ch, i + 1, end, true);
long rightFalse = countWays(ch, i + 1, end, false);
// 根据运算符计算结果
if (op == '&') {
if (target) {
count += leftTrue * rightTrue;
} else {
count += leftTrue * rightFalse + leftFalse * rightTrue + leftFalse * rightFalse;
}
} else if (op == '|') {
if (target) {
count += leftTrue * rightTrue + leftTrue * rightFalse + leftFalse * rightTrue;
} else {
count += leftFalse * rightFalse;
}
} else if (op == '^') {
if (target) {
count += leftTrue * rightFalse + leftFalse * rightTrue;
} else {
count += leftTrue * rightTrue + leftFalse * rightFalse;
}
}
}
return count;
}算法思路：
- 使用分治法，尝试每个运算符作为主运算符
- 递归计算左右子表达式为true和false的方案数
- 根据运算符类型组合左右结果：
&（与）：true需要两边都true；false需要至少一边false|（或）：true需要至少一边true；false需要两边都false^（异或）：true需要两边不同；false需要两边相同
时间复杂度：O(4^n)，可用记忆化优化到O(n³)
快速排序
public class QuickSort {
public static void quickSort(int[] arr, int low, int high) {
if (low < high) {
// 分区操作，返回基准元素位置
int pivot = partition(arr, low, high);
// 递归排序基准元素左边
quickSort(arr, low, pivot - 1);
// 递归排序基准元素右边
quickSort(arr, pivot + 1, high);
}
}
private static int partition(int[] arr, int low, int high) {
// 选择最后一个元素作为基准
int pivot = arr[high];
int i = low - 1; // 小于基准元素的指针
for (int j = low; j < high; j++) {
// 如果当前元素小于等于基准
if (arr[j] <= pivot) {
i++; // 将小于基准元素的指针右移
swap(arr, i, j); // 将当前元素与小于基准元素的指针交换
}
}
// 将基准放到正确位置
swap(arr, i + 1, high);
return i + 1; // 返回基准元素的索引
}
private static void swap(int[] arr, int i, int j) {
int temp = arr[i];
arr[i] = arr[j];
arr[j] = temp;
}
// 主方法
public static void quickSort(int[] arr) {
quickSort(arr, 0, arr.length - 1);
}
}线程交替打印
public class AlternatePrint {
private static final Object lock = new Object();
private static int number = 1;
private static final int MAX = 100;
private static boolean turnA = true;
public static void main(String[] args) {
Thread t1 = new Thread(() -> {
while (true) {
synchronized (lock) {
while (!turnA) { // 不是A线程的回合，等待
try {
lock.wait();
} catch (InterruptedException e) {
e.printStackTrace();
}
}
if (number > MAX) break;
System.out.println("Thread A: " + number++);
turnA = false;
lock.notify(); // 唤醒B线程
}
}
});
Thread t2 = new Thread(() -> {
while (true) {
synchronized (lock) {
while (turnA) { // 不是B线程的回合，等待
try {
lock.wait();
} catch (InterruptedException e) {
e.printStackTrace();
}
}
if (number > MAX) break;
System.out.println("Thread B: " + number++);
turnA = true;
lock.notify(); // 唤醒A线程
}
}
});
t1.start();
t2.start();
}
}字符串相加 - LeetCode 415
class Solution {
public String addStrings(String num1, String num2) {
int i = num1.length() - 1, j = num2.length() - 1, add = 0; // 初始化指针和进位 从后往前遍历
StringBuilder ans = new StringBuilder();
while (i >= 0 || j >= 0 || add != 0) { // 当指针未遍历完或进位不为0时，继续遍历
int x = i >= 0 ? num1.charAt(i) - '0' : 0; // 如果指针未遍历完，则将当前字符转换为数字 否则为0
int y = j >= 0 ? num2.charAt(j) - '0' : 0; // 如果指针未遍历完，则将当前字符转换为数字 否则为0
int result = x + y + add; // 计算当前位和进位
ans.append(result % 10); // 将当前位添加到结果中
add = result / 10; // 更新进位
i--; // 更新指针
j--; // 更新指针
}
ans.reverse(); // 计算完以后的答案需要翻转过来 因为是从个位开始计算的
return ans.toString();
}
}字符串乘法 - LeetCode 43
- 都是倒叙遍历 因为从个位开始计算
public String multiply(String num1, String num2) {
if("0".equals(num1) || "0".equals(num2)){ // 如果有一个是0，则直接返回0
return "0";
}
int len1=num1.length();
int len2=num2.length();
int[] ans=new int[len1+len2]; // 存储结果
for(int i=len1-1;i>=0;i--){ // 从后往前遍历 num1
int value1=num1.charAt(i)-'0'; // 将字符转换为数字
for(int j=len2-1;j>=0;j--){ // 从后往前遍历 num2
int value2=num2.charAt(j)-'0'; // 将字符转换为数字
int sum=ans[i+j+1]+value1*value2; // 计算当前位和进位
ans[i+j+1]=sum%10; // 将当前位添加到结果中
ans[i+j]+=sum/10; // 更新进位
}
}
StringBuilder sb=new StringBuilder(); // 存储结果
for(int i=0;i<ans.length;i++){
if(i==0 && ans[i]==0){ // 如果结果是0，则直接返回0
continue;
}
sb.append(ans[i]);
}
return sb.toString();
}缺失的第一个正数 - LeetCode 41
public int firstMissingPositive(int[] nums) {
int n = nums.length;
// Step 1: 交换，把每个 num 放到 num-1 的位置
for (int i = 0; i < n; ++i) {
while (
nums[i] > 0 && nums[i] <= n && // 有效正整数
nums[nums[i] - 1] != nums[i] // 没放到该在的位置 比如 1 应该在 0 位置 2 应该在 1 位置
) {
int temp = nums[nums[i] - 1]; // 目标位置上的值
nums[nums[i] - 1] = nums[i]; // 放到正确位置
nums[i] = temp; // 当前位交换过来
}
}
// Step 2: 找第一个位置不符合规则的
for (int i = 0; i < n; ++i) {
if (nums[i] != i + 1) {
return i + 1; // 缺失的就是这个
}
}
return n + 1; // 全都有，从 1 到 n 全在
}死锁例子
public class DeadlockDemo {
private static final Object resourceA = new Object();
private static final Object resourceB = new Object();
public static void main(String[] args) {
// 线程 1
Thread t1 = new Thread(() -> {
synchronized (resourceA) {
System.out.println("线程1：锁定 resourceA");
try {
Thread.sleep(100); // 模拟执行时间
} catch (InterruptedException e) {
e.printStackTrace();
}
System.out.println("线程1：等待获取 resourceB");
synchronized (resourceB) {
System.out.println("线程1：获取到 resourceB");
}
}
});
// 线程 2
Thread t2 = new Thread(() -> {
synchronized (resourceB) {
System.out.println("线程2：锁定 resourceB");
try {
Thread.sleep(100); // 模拟执行时间
} catch (InterruptedException e) {
e.printStackTrace();
}
System.out.println("线程2：等待获取 resourceA");
synchronized (resourceA) {
System.out.println("线程2：获取到 resourceA");
}
}
});
t1.start();
t2.start();
}
}限流器(固定窗口)
public class RateLimiter {
private final int limit; // 最大请求次数
private final long interval; // 时间窗口（毫秒）
private final Queue<Long> queue; // 存储请求时间戳
public RateLimiter(int limit, int intervalSeconds) {
this.limit = limit;
this.interval = intervalSeconds * 1000L;
this.queue = new LinkedList<>();
}
public synchronized boolean allowRequest() {
long now = System.currentTimeMillis();
// 移除过期的请求（10秒之前的）
while (!queue.isEmpty() && now - queue.peek() > interval) {
queue.poll();
}
// 判断当前请求是否超限
if (queue.size() < limit) {
queue.offer(now);
return true;
} else {
return false;
}
}
public static void main(String[] args) throws InterruptedException {
RateLimiter limiter = new RateLimiter(5, 10); // 10秒内最多5次
for (int i = 1; i <= 10; i++) {
boolean allowed = limiter.allowRequest();
System.out.println("请求 " + i + " 是否允许: " + allowed);
Thread.sleep(2000); // 每隔2秒请求一次
}
}
}三个线程交替打印1-100
import java.util.concurrent.locks.Condition;
import java.util.concurrent.locks.ReentrantLock;
public class PrintNumbers {
// 共享的计数器
private static int count = 1;
// 控制线程执行顺序的标识，0、1、2分别代表三个线程
private static int flag = 0;
// 锁对象
private static final ReentrantLock lock = new ReentrantLock();
// 三个条件对象，分别对应三个线程的等待/唤醒
private static final Condition condition0 = lock.newCondition();
private static final Condition condition1 = lock.newCondition();
private static final Condition condition2 = lock.newCondition();
public static void main(String[] args) {
// 线程1：打印flag为0时的数字
Thread thread1 = new Thread(() -> print(0, condition0, condition1));
// 线程2：打印flag为1时的数字
Thread thread2 = new Thread(() -> print(1, condition1, condition2));
// 线程3：打印flag为2时的数字
Thread thread3 = new Thread(() -> print(2, condition2, condition0));
thread1.start();
thread2.start();
thread3.start();
}
/**
* 打印数字的方法
* @param threadFlag 当前线程对应的标识
* @param currentCondition 当前线程的条件对象
* @param nextCondition 下一个线程的条件对象
*/
private static void print(int threadFlag, Condition currentCondition, Condition nextCondition) {
while (true) {
lock.lock();
try {
// 当不是当前线程该执行时，等待
while (flag != threadFlag) {
currentCondition.await();
}
// 打印数字
System.out.println("线程" + (threadFlag + 1) + ": " + count);
count++;
// 如果已经打印到100，退出循环
if (count > 100) {
// 唤醒下一个线程，让它也能退出
flag = (flag + 1) % 3;
nextCondition.signalAll();
break;
}
// 切换到下一个线程
flag = (flag + 1) % 3;
// 唤醒下一个线程
nextCondition.signal();
} catch (InterruptedException e) {
Thread.currentThread().interrupt(); // 中断线程
return;
} finally {
lock.unlock();
}
}
}
}