Android第十二次面试-多线程和字符串算法总结

多线程的创建与常见使用方法

​一、多线程创建方式​

​1. 继承Thread类​

class MyThread extends Thread {@Overridepublic void run() {// 线程执行逻辑System.out.println(Thread.currentThread().getName() + " is running");}
}// 使用
MyThread thread = new MyThread();
thread.start(); // 启动线程

​2. 实现Runnable接口​

class MyRunnable implements Runnable {@Overridepublic void run() {System.out.println(Thread.currentThread().getName() + " is running");}
}// 使用
Thread thread = new Thread(new MyRunnable());
thread.start();

​3. Android特有方式​

// HandlerThread（自带Looper）
HandlerThread handlerThread = new HandlerThread("WorkerThread");
handlerThread.start();
Handler handler = new Handler(handlerThread.getLooper()) {@Overridepublic void handleMessage(Message msg) {// 后台线程处理消息}
};// 发送消息
handler.sendEmptyMessage(0);

---

​二、线程池使用（推荐方式）​​

​1. 创建线程池​

// 固定大小线程池
ExecutorService fixedPool = Executors.newFixedThreadPool(4);// 缓存线程池（自动扩容）
ExecutorService cachedPool = Executors.newCachedThreadPool();// 单线程池（顺序执行）
ExecutorService singleThreadPool = Executors.newSingleThreadExecutor();

​2. 提交任务​

// 执行Runnable任务
fixedPool.execute(() -> {System.out.println("Task running in thread pool");
});// 提交Callable任务并获取Future
Future<String> future = fixedPool.submit(() -> {return "Task result";
});

​3. 自定义线程池​

ThreadPoolExecutor customPool = new ThreadPoolExecutor(4, // 核心线程数10, // 最大线程数60, // 空闲线程存活时间（秒）TimeUnit.SECONDS,new LinkedBlockingQueue<>(100) // 任务队列
);// 拒绝策略（当队列满时）
customPool.setRejectedExecutionHandler((task, executor) -> {System.err.println("Task rejected: " + task);
});

---

​1. 交替打印数字（两个线程协作）

​题目​：两个线程交替打印1~100，一个线程打印奇数，另一个打印偶数

public class AlternatePrint {private int num = 1;private final Object lock = new Object();public void printOdd() {synchronized (lock) {while (num <= 100) {if (num % 2 == 1) {System.out.println(Thread.currentThread().getName() + ": " + num++);lock.notify(); // 唤醒偶数线程} else {try {lock.wait(); // 等待偶数线程通知} catch (InterruptedException e) {Thread.currentThread().interrupt();}}}}}public void printEven() {synchronized (lock) {while (num <= 100) {if (num % 2 == 0) {System.out.println(Thread.currentThread().getName() + ": " + num++);lock.notify(); // 唤醒奇数线程} else {try {lock.wait(); // 等待奇数线程通知} catch (InterruptedException e) {Thread.currentThread().interrupt();}}}}}public static void main(String[] args) {AlternatePrint printer = new AlternatePrint();new Thread(printer::printOdd, "OddThread").start();new Thread(printer::printEven, "EvenThread").start();}
}

2. 生产者-消费者模型（缓冲区管理）

​题目​：实现生产者线程生成数据，消费者线程消费数据，使用阻塞队列控制

import java.util.concurrent.ArrayBlockingQueue;
import java.util.concurrent.BlockingQueue;public class ProducerConsumer {private static final int CAPACITY = 5;private final BlockingQueue<Integer> queue = new ArrayBlockingQueue<>(CAPACITY);public void produce() throws InterruptedException {int value = 0;while (true) {synchronized (this) {while (queue.size() == CAPACITY) {wait(); // 缓冲区满时等待}queue.put(value);System.out.println("Produced: " + value);value++;notifyAll(); // 通知消费者}Thread.sleep(100); // 模拟生产耗时}}public void consume() throws InterruptedException {while (true) {synchronized (this) {while (queue.isEmpty()) {wait(); // 缓冲区空时等待}int value = queue.take();System.out.println("Consumed: " + value);notifyAll(); // 通知生产者}Thread.sleep(150); // 模拟消费耗时}}public static void main(String[] args) {ProducerConsumer pc = new ProducerConsumer();new Thread(() -> {try { pc.produce(); } catch (InterruptedException e) { Thread.currentThread().interrupt(); }}, "Producer").start();new Thread(() -> {try { pc.consume(); } catch (InterruptedException e) { Thread.currentThread().interrupt(); }}, "Consumer").start();}
}

3. 多线程顺序打印（线程协同）

​题目​：三个线程按顺序循环打印ABC各10次

public class SequentialPrinter {private final Object lock = new Object();private String state = "A";public void printA() {synchronized (lock) {for (int i = 0; i < 10; ) {if (state.equals("A")) {System.out.print("A");state = "B";i++;lock.notifyAll(); // 唤醒所有等待线程} else {try {lock.wait(); // 等待条件满足} catch (InterruptedException e) {Thread.currentThread().interrupt();}}}}}// 类似实现printB()和printC()public void printB() {synchronized (lock) {for (int i = 0; i < 10; ) {if (state.equals("B")) {System.out.print("B");state = "C";i++;lock.notifyAll();} else {try {lock.wait();} catch (InterruptedException e) {Thread.currentThread().interrupt();}}}}}public void printC() {synchronized (lock) {for (int i = 0; i < 10; ) {if (state.equals("C")) {System.out.print("C ");state = "A";i++;lock.notifyAll();} else {try {lock.wait();} catch (InterruptedException e) {Thread.currentThread().interrupt();}}}}}public static void main(String[] args) {SequentialPrinter printer = new SequentialPrinter();new Thread(printer::printA, "Thread-A").start();new Thread(printer::printB, "Thread-B").start();new Thread(printer::printC, "Thread-C").start();}
}

4. 多线程计算素数（任务分发）

​题目​：使用线程池计算1~N范围内素数的数量

import java.util.concurrent.*;public class PrimeCounter {public static void main(String[] args) throws Exception {final int N = 1000000;final int THREADS = Runtime.getRuntime().availableProcessors();ExecutorService executor = Executors.newFixedThreadPool(THREADS);int segment = N / THREADS;Future<Integer>[] results = new Future[THREADS];// 分发任务for (int i = 0; i < THREADS; i++) {final int start = i * segment + 1;final int end = (i == THREADS - 1) ? N : (i + 1) * segment;results[i] = executor.submit(() -> {int count = 0;for (int num = start; num <= end; num++) {if (isPrime(num)) count++;}return count;});}// 汇总结果int totalPrimes = 0;for (Future<Integer> future : results) {totalPrimes += future.get();}System.out.println("Total primes: " + totalPrimes);executor.shutdown();}private static boolean isPrime(int n) {if (n <= 1) return false;if (n == 2) return true;if (n % 2 == 0) return false;for (int i = 3; i <= Math.sqrt(n); i += 2) {if (n % i == 0) return false;}return true;}
}

5. 自定义简单线程池

​题目​：实现一个固定大小的线程池，支持提交任务和执行任务

import java.util.concurrent.*;
import java.util.*;public class SimpleThreadPool {private final BlockingQueue<Runnable> taskQueue;private final List<WorkerThread> workers;private volatile boolean isShutdown = false;public SimpleThreadPool(int poolSize) {this.taskQueue = new LinkedBlockingQueue<>();this.workers = new ArrayList<>();for (int i = 0; i < poolSize; i++) {WorkerThread worker = new WorkerThread("Worker-" + i);worker.start();workers.add(worker);}}public void execute(Runnable task) {if (isShutdown) {throw new IllegalStateException("ThreadPool is shutdown");}taskQueue.offer(task);}public void shutdown() {isShutdown = true;workers.forEach(Thread::interrupt);}private class WorkerThread extends Thread {public WorkerThread(String name) {super(name);}@Overridepublic void run() {while (!isShutdown || !taskQueue.isEmpty()) {try {Runnable task = taskQueue.take();task.run();} catch (InterruptedException e) {// 处理中断，结束线程}}}}public static void main(String[] args) {SimpleThreadPool pool = new SimpleThreadPool(4);// 提交任务for (int i = 0; i < 10; i++) {final int taskId = i;pool.execute(() -> {System.out.println(Thread.currentThread().getName() + " executing Task-" + taskId);try {Thread.sleep(500);} catch (InterruptedException e) {Thread.currentThread().interrupt();}});}// 等待任务完成try {Thread.sleep(3000);} catch (InterruptedException e) {Thread.currentThread().interrupt();}pool.shutdown();}
}

字符串算法总结

1. 字符串反转

​题目​：反转字符串或单词顺序

// 整个字符串反转
public String reverseString(String s) {char[] chars = s.toCharArray();int left = 0, right = chars.length - 1;while (left < right) {char temp = chars[left];chars[left++] = chars[right];chars[right--] = temp;}return new String(chars);
}// 单词顺序反转（保留空格）
public String reverseWords(String s) {String[] words = s.trim().split("\\s+");StringBuilder sb = new StringBuilder();for (int i = words.length - 1; i >= 0; i--) {sb.append(words[i]);if (i > 0) sb.append(" ");}return sb.toString();
}

2. 字符串转换整数 (atoi)

​题目​：处理边界条件（空格/正负号/溢出）

public int myAtoi(String s) {int index = 0, sign = 1, total = 0;// 1. 跳过空格while (index < s.length() && s.charAt(index) == ' ') index++;if (index == s.length()) return 0;// 2. 处理正负号if (s.charAt(index) == '+' || s.charAt(index) == '-') {sign = s.charAt(index) == '+' ? 1 : -1;index++;}// 3. 转换数字并处理溢出while (index < s.length()) {int digit = s.charAt(index) - '0';if (digit < 0 || digit > 9) break;// 检查溢出if (total > Integer.MAX_VALUE / 10 || (total == Integer.MAX_VALUE / 10 && digit > 7)) {return sign == 1 ? Integer.MAX_VALUE : Integer.MIN_VALUE;}total = total * 10 + digit;index++;}return total * sign;
}

3. 最长公共前缀

​题目​：查找字符串数组的最长公共前缀

public String longestCommonPrefix(String[] strs) {if (strs == null || strs.length == 0) return "";for (int i = 0; i < strs[0].length(); i++) {char c = strs[0].charAt(i);for (int j = 1; j < strs.length; j++) {if (i == strs[j].length() || strs[j].charAt(i) != c) {return strs[0].substring(0, i);}}}return strs[0];
}

4. 无重复字符的最长子串

​题目​：滑动窗口经典应用

public int lengthOfLongestSubstring(String s) {Map<Character, Integer> map = new HashMap<>();int maxLen = 0;for (int left = 0, right = 0; right < s.length(); right++) {char c = s.charAt(right);if (map.containsKey(c)) {left = Math.max(left, map.get(c) + 1); // 跳过重复字符}map.put(c, right);maxLen = Math.max(maxLen, right - left + 1);}return maxLen;
}

5. 最长回文子串

​题目​：中心扩展法

public String longestPalindrome(String s) {if (s == null || s.length() < 1) return "";int start = 0, end = 0;for (int i = 0; i < s.length(); i++) {int len1 = expand(s, i, i);      // 奇数长度int len2 = expand(s, i, i + 1);  // 偶数长度int len = Math.max(len1, len2);if (len > end - start) {start = i - (len - 1) / 2;end = i + len / 2;}}return s.substring(start, end + 1);
}private int expand(String s, int left, int right) {while (left >= 0 && right < s.length() && s.charAt(left) == s.charAt(right)) {left--;right++;}return right - left - 1;
}

6. 字符串匹配算法（KMP）

​题目​：实现 strStr()

public int strStr(String haystack, String needle) {// 空模式串直接返回 0if (needle.isEmpty()) return 0;// 核心预处理：计算 next 数组int[] next = getNext(needle);int i = 0, j = 0;while (i < haystack.length()) {// 当前字符匹配：继续比较后续字符if (j == -1 || haystack.charAt(i) == needle.charAt(j)) {i++;j++;} // 字符不匹配：模式串向右滑动else {j = next[j];}// 完整匹配成功if (j == needle.length()) {return i - j;}}return -1;
}// 计算 next 数组（部分匹配表）
private int[] getNext(String pattern) {int[] next = new int[pattern.length()];next[0] = -1;  // 初始值int i = 0, j = -1;while (i < pattern.length() - 1) {if (j == -1 || pattern.charAt(i) == pattern.charAt(j)) {i++;j++;next[i] = j;} else {j = next[j];  // 回退到上一匹配位置}}return next;
}

KMP 算法四步流程

1. ​初始化预处理​

   • 对于模式串 needle，计算其 next 数组
   • next[i] 表示当 needle[i] 匹配失败时，模式串应该回退到的位置

2. ​next 数组构建过程​

   • 使用双指针 i（主指针）和 j（前缀指针）
   • next[0] = -1 作为特殊标记
   • 通过最长公共前后缀的查找计算每个位置的 next 值：

     模式串: "ABCDABD"
     next[]: [-1,0,0,0,0,1,2]

3. ​滑动匹配过程​

   • 主串指针 i ​永不回溯​
   • 当匹配失败时，模式串指针 j 回退到 next[j] 的位置
   • 利用 next 数组避免回溯导致的重复比较

4. ​匹配成功判断​

   • 当 j == needle.length() 时，表示模式串完全匹配
   • 返回起始位置：i - j

优化（Hash） 

7. 有效的括号

​题目​：栈的经典应用

public boolean isValid(String s) {Stack<Character> stack = new Stack<>();for (char c : s.toCharArray()) {if (c == '(') stack.push(')');else if (c == '[') stack.push(']');else if (c == '{') stack.push('}');else if (stack.isEmpty() || stack.pop() != c) return false;}return stack.isEmpty();
}

8. 字母异位词分组

​题目​：HashMap的巧妙使用

public List<List<String>> groupAnagrams(String[] strs) {Map<String, List<String>> map = new HashMap<>();for (String s : strs) {char[] chars = s.toCharArray();Arrays.sort(chars);String key = new String(chars);map.computeIfAbsent(key, k -> new ArrayList<>()).add(s);}return new ArrayList<>(map.values());
}

9. 编辑距离（动态规划）

​题目​：计算最小操作次数

public int minDistance(String word1, String word2) {int m = word1.length(), n = word2.length();int[][] dp = new int[m + 1][n + 1];for (int i = 0; i <= m; i++) dp[i][0] = i;for (int j = 0; j <= n; j++) dp[0][j] = j;for (int i = 1; i <= m; i++) {for (int j = 1; j <= n; j++) {if (word1.charAt(i - 1) == word2.charAt(j - 1)) {dp[i][j] = dp[i - 1][j - 1];} else {dp[i][j] = 1 + Math.min(dp[i - 1][j - 1], Math.min(dp[i][j - 1], dp[i - 1][j]));}}}return dp[m][n];
}

10. 字符串解码

​题目​：嵌套括号处理

public String decodeString(String s) {Stack<Integer> numStack = new Stack<>();Stack<StringBuilder> strStack = new Stack<>();StringBuilder cur = new StringBuilder();int num = 0;for (char c : s.toCharArray()) {if (Character.isDigit(c)) {num = num * 10 + (c - '0');} else if (c == '[') {numStack.push(num);strStack.push(cur);cur = new StringBuilder();num = 0;} else if (c == ']') {StringBuilder tmp = cur;cur = strStack.pop();int repeat = numStack.pop();for (int i = 0; i < repeat; i++) {cur.append(tmp);}} else {cur.append(c);}}return cur.toString();
}