常见算法

算法题

LRU (Least Recently Used) 缓存算法

设计一个数据结构，实现最近最少使用缓存。

通过哈希表和双向链表实现。哈希表提供 O(1) 的查找时间，双向链表维护访问顺序。

// 直接继承法，继承LinkedHashMap，只需要重写get和put、修改淘汰规则即可
class LRUCache<K, V> extends LinkedHashMap<K, V> {
    private final int capacity;

    public LRUCache(int capacity) {
        super(capacity, 0.75F, true);
        this.capacity = capacity;
    }

    public V get(Object key) {
        return super.getOrDefault(key, null);
    }

    public V put(K key, V value) {
        super.put(key, value);
        return value;
    }

    @Override
    protected boolean removeEldestEntry(Map.Entry<K, V> eldest) {
        return size() > capacity;
    }
    

    public static void main(String[] args) {
        LRUCacheWithLinkedHashMap map = new LRUCacheWithLinkedHashMap(5);
        map.put(4, 44);
        map.put(1, 11);
        map.put(2, 22);
        map.put(3, 33);
        map.put(7, 77);
        map.put(5, 55);
        map.put(8, 88);
        map.put(6, 66);
        map.put(1, 111);
        map.put(6, 666);
        System.out.println(map);

		
        // 直接实例化法，实例化时重写淘汰规则
        Map<Integer, Integer> LRUmap = new LinkedHashMap<Integer, Integer>(10, 0.75f, true) {
            @Override
            protected boolean removeEldestEntry(Map.Entry eldest) {
                return size() > 10;
            }
        };
    }
}

// 手动实现法，手动实现淘汰规则
class LRUCache<K, V> {
    
    private final int capacity;
    private final Map<K, V> map;

    public LRUCache(int capacity) {
        this.capacity = capacity;
        map = new LinkedHashMap<>();
    }

    public V get(K key) {
        if (!map.containsKey(key)) {
            return null;
        }
        V value = map.remove(key);
        map.put(key, value);
        return value;
    }

    public void put(K key, V value) {
        if (map.containsKey(key)) {
            map.remove(key);
            map.put(key, value);
            return;
        }
        map.put(key, value);
        if (map.size() > capacity) {
            map.remove(map.entrySet().iterator().next().getKey());
        }
    }
}

LFU (Least Frequently Used) 缓存算法

设计一个数据结构，实现最不经常使用缓存。

LFU 缓存需要同时记录使用频率和访问时间，通过哈希表和最小堆实现。

import java.util.*;

class LFUCache {
    private int capacity;
    private int minFrequency;
    private Map<Integer, Integer> valueMap;
    private Map<Integer, Integer> freqMap;
    private Map<Integer, LinkedHashSet<Integer>> freqListMap;

    public LFUCache(int capacity) {
        this.capacity = capacity;
        this.minFrequency = 0;
        this.valueMap = new HashMap<>();
        this.freqMap = new HashMap<>();
        this.freqListMap = new HashMap<>();
    }

    public int get(int key) {
        if (!valueMap.containsKey(key)) return -1;
        int freq = freqMap.get(key);
        freqListMap.get(freq).remove(key);
        if (freqListMap.get(freq).isEmpty() && freq == minFrequency) minFrequency++;
        freqMap.put(key, freq + 1);
        freqListMap.computeIfAbsent(freq + 1, k -> new LinkedHashSet<>()).add(key);
        return valueMap.get(key);
    }

    public void put(int key, int value) {
        if (capacity == 0) return;
        if (valueMap.containsKey(key)) {
            valueMap.put(key, value);
            get(key); // Update frequency
            return;
        }
        if (valueMap.size() == capacity) {
            int evict = freqListMap.get(minFrequency).iterator().next();
            freqListMap.get(minFrequency).remove(evict);
            valueMap.remove(evict);
            freqMap.remove(evict);
        }
        valueMap.put(key, value);
        freqMap.put(key, 1);
        minFrequency = 1;
        freqListMap.computeIfAbsent(1, k -> new LinkedHashSet<>()).add(key);
    }
}

布隆过滤器 (Bloom Filter)

设计一种节省空间的概率型数据结构，用于测试一个元素是否存在于一个集合中。

布隆过滤器使用多个哈希函数和位数组实现。

import java.util.BitSet;

class BloomFilter {
    private int size;
    private int hashCount;
    private BitSet bitSet;

    public BloomFilter(int size, int hashCount) {
        this.size = size;
        this.hashCount = hashCount;
        this.bitSet = new BitSet(size);
    }

    private int[] getHashes(String value) {
        int[] hashes = new int[hashCount];
        for (int i = 0; i < hashCount; i++) {
            hashes[i] = value.hashCode() + i;
            hashes[i] = Math.abs(hashes[i] % size);
        }
        return hashes;
    }

    public void add(String value) {
        int[] hashes = getHashes(value);
        for (int hash : hashes) {
            bitSet.set(hash);
        }
    }

    public boolean mightContain(String value) {
        int[] hashes = getHashes(value);
        for (int hash : hashes) {
            if (!bitSet.get(hash)) return false;
        }
        return true;
    }
}

一致性哈希 (Consistent Hashing)

用于分布式系统中，能够在添加或移除节点时最小化需要重新分配的数据量。

使用哈希环实现，在添加或移除节点时最小化重新分配的数据量。

import java.util.*;

class ConsistentHashing {
    private int numberOfReplicas;
    private SortedMap<Integer, String> circle = new TreeMap<>();

    public ConsistentHashing(int numberOfReplicas, List<String> nodes) {
        this.numberOfReplicas = numberOfReplicas;
        for (String node : nodes) {
            add(node);
        }
    }

    public void add(String node) {
        for (int i = 0; i < numberOfReplicas; i++) {
            int hash = (node + i).hashCode();
            circle.put(hash, node);
        }
    }

    public void remove(String node) {
        for (int i = 0; i < numberOfReplicas; i++) {
            int hash = (node + i).hashCode();
            circle.remove(hash);
        }
    }

    public String get(String key) {
        if (circle.isEmpty()) return null;
        int hash = key.hashCode();
        if (!circle.containsKey(hash)) {
            SortedMap<Integer, String> tailMap = circle.tailMap(hash);
            hash = tailMap.isEmpty() ? circle.firstKey() : tailMap.firstKey();
        }
        return circle.get(hash);
    }
}

跳表 (Skip List)

一种基于概率的数据结构，可以用于实现快速查找、插入和删除操作。在很多数据库和缓存系统中都有应用。

通过多层索引实现快速查找、插入和删除操作。

import java.util.*;

class SkipListNode {
    int val;
    List<SkipListNode> forward;

    public SkipListNode(int val, int level) {
        this.val = val;
        this.forward = new ArrayList<>(Collections.nCopies(level, null));
    }
}

class SkipList {
    private static final float P = 0.5f;
    private static final int MAX_LEVEL = 16;
    private int level = 1;
    private SkipListNode head = new SkipListNode(-1, MAX_LEVEL);

    private int randomLevel() {
        int lvl = 1;
        while (Math.random() < P && lvl < MAX_LEVEL) lvl++;
        return lvl;
    }

    public boolean search(int target) {
        SkipListNode current = head;
        for (int i = level - 1; i >= 0; i--) {
            while (current.forward.get(i) != null && current.forward.get(i).val < target) {
                current = current.forward.get(i);
            }
        }
        current = current.forward.get(0);
        return current != null && current.val == target;
    }

    public void add(int num) {
        SkipListNode current = head;
        List<SkipListNode> update = new ArrayList<>(Collections.nCopies(MAX_LEVEL, null));
        for (int i = level - 1; i >= 0; i--) {
            while (current.forward.get(i) != null && current.forward.get(i).val < num) {
                current = current.forward.get(i);
            }
            update.set(i, current);
        }
        int lvl = randomLevel();
        if (lvl > level) {
            for (int i = level; i < lvl; i++) {
                update.set(i, head);
            }
            level = lvl;
        }
        SkipListNode newNode = new SkipListNode(num, lvl);
        for (int i = 0; i < lvl; i++) {
            newNode.forward.set(i, update.get(i).forward.get(i));
            update.get(i).forward.set(i, newNode);
        }
    }

    public boolean erase(int num) {
        SkipListNode current = head;
        List<SkipListNode> update = new ArrayList<>(Collections.nCopies(MAX_LEVEL, null));
        for (int i = level - 1; i >= 0; i--) {
            while (current.forward.get(i) != null && current.forward.get(i).val < num) {
                current = current.forward.get(i);
            }
            update.set(i, current);
        }
        current = current.forward.get(0);
        if (current == null || current.val != num) return false;
        for (int i = 0; i < level; i++) {
            if (update.get(i).forward.get(i) != current) break;
            update.get(i).forward.set(i, current.forward.get(i));
        }
        while (level > 1 && head.forward.get(level - 1) == null) level--;
        return true;
    }
}

位图 (Bitmap)

使用位数组来表示集合，用于快速查询元素是否存在，常用于大数据处理和数据库中。

class Bitmap {
    private byte[] bitArray;
    private int size;

    public Bitmap(int size) {
        this.size = size;
        this.bitArray = new byte[(size + 7) / 8];
    }

    public void set(int num) {
        int index = num / 8;
        int position = num % 8;
        bitArray[index] |= 1 << position;
    }

    public boolean get(int num) {
        int index = num / 8;
        int position = num % 8;
        return (bitArray[index] & (1 << position)) != 0;
    }

    public void clear(int num) {
        int index = num / 8;
        int position = num % 8;
        bitArray[index] &= ~(1 << position);
    }
}

前缀树 (Trie)

一种树形数据结构，用于高效地检索字符串集合中的字符串，常用于搜索引擎和自动完成功能。

class TrieNode {
    boolean isEnd;
    TrieNode[] children = new TrieNode[26];

    public TrieNode() {
        isEnd = false;
        for (int i = 0; i < 26; i++) children[i] = null;
    }
}

class Trie {
    private TrieNode root;

    public Trie() {
        root = new TrieNode();
    }

    public void insert(String word) {
        TrieNode node = root;
        for (char c : word.toCharArray()) {
            int index = c - 'a';
            if (node.children[index] == null) node.children[index] = new TrieNode();
            node = node.children[index];
        }
        node.isEnd = true;
    }

    public boolean search(String word) {
        TrieNode node = root;
        for (char c : word.toCharArray()) {
            int index = c - 'a';
            if (node.children[index] == null) return false;
            node = node.children[index];
        }
        return node.isEnd;
    }

    public boolean startsWith(String prefix) {
        TrieNode node = root;
        for (char c : prefix.toCharArray()) {
            int index = c - 'a';
            if (node.children[index] == null) return false;
            node = node.children[index];
        }
        return true;
    }
}

滑动窗口协议 (Sliding Window Protocol)

用于网络数据传输中流量控制和拥塞控制的算法。

import java.util.*;

class SlidingWindow {
    private int windowSize;
    private int currentWindowStart;
    private int currentWindowEnd;
    private Set<Integer> receivedPackets;

    public SlidingWindow(int windowSize) {
        this.windowSize = windowSize;
        this.currentWindowStart = 0;
        this.currentWindowEnd = windowSize - 1;
        this.receivedPackets = new HashSet<>();
    }

    public boolean receivePacket(int packetNumber) {
        if (packetNumber < currentWindowStart || packetNumber > currentWindowEnd) {
            return false;
        }
        receivedPackets.add(packetNumber);
        if (packetNumber == currentWindowStart) {
            while (receivedPackets.contains(currentWindowStart)) {
                receivedPackets.remove(currentWindowStart);
                currentWindowStart++;
                currentWindowEnd++;
            }
        }
        return true;
    }
}

负载均衡算法 (Load Balancing Algorithm)

常用于分布式系统中的请求分发。

轮询 (Round Robin)

import java.util.*;

class RoundRobinLoadBalancer {
    private List<String> servers;
    private int currentIndex;

    public RoundRobinLoadBalancer(List<String> servers) {
        this.servers = new ArrayList<>(servers);
        this.currentIndex = 0;
    }

    public String getNextServer() {
        if (servers.isEmpty()) return null;
        String server = servers.get(currentIndex);
        currentIndex = (currentIndex + 1) % servers.size();
        return server;
    }
}

最少连接 (Least Connections)

import java.util.*;

class LeastConnectionsLoadBalancer {
    private Map<String, Integer> serverConnections;

    public LeastConnectionsLoadBalancer(List<String> servers) {
        serverConnections = new HashMap<>();
        for (String server : servers) {
            serverConnections.put(server, 0);
        }
    }

    public String getNextServer() {
        return serverConnections.entrySet().stream()
                .min(Comparator.comparingInt(Map.Entry::getValue))
                .map(Map.Entry::getKey)
                .orElse(null);
    }

    public void connectToServer(String server) {
        serverConnections.put(server, serverConnections.get(server) + 1);
    }

    public void disconnectFromServer(String server) {
        serverConnections.put(server, serverConnections.get(server) - 1);
    }
}

分布式ID生成算法

Snowflake算法，用于生成唯一的全局ID。

public class SnowflakeIdGenerator {
    private final long workerId;
    private final long datacenterId;
    private final long epoch = 1288834974657L;

    private long sequence = 0L;
    private final long workerIdBits = 5L;
    private final long datacenterIdBits = 5L;
    private final long maxWorkerId = -1L ^ (-1L << workerIdBits);
    private final long maxDatacenterId = -1L ^ (-1L << datacenterIdBits);
    private final long sequenceBits = 12L;

    private final long workerIdShift = sequenceBits;
    private final long datacenterIdShift = sequenceBits + workerIdBits;
    private final long timestampLeftShift = sequenceBits + workerIdBits + datacenterIdBits;
    private final long sequenceMask = -1L ^ (-1L << sequenceBits);

    private long lastTimestamp = -1L;

    public SnowflakeIdGenerator(long workerId, long datacenterId) {
        if (workerId > maxWorkerId || workerId < 0)
            throw new IllegalArgumentException("workerId out of range");
        if (datacenterId > maxDatacenterId || datacenterId < 0)
            throw new IllegalArgumentException("datacenterId out of range");
        this.workerId = workerId;
        this.datacenterId = datacenterId;
    }

    public synchronized long nextId() {
        long timestamp = timeGen();

        if (timestamp < lastTimestamp) {
            throw new RuntimeException("Clock moved backwards");
        }

        if (lastTimestamp == timestamp) {
            sequence = (sequence + 1) & sequenceMask;
            if (sequence == 0) {
                timestamp = tilNextMillis(lastTimestamp);
            }
        } else {
            sequence = 0L;
        }

        lastTimestamp = timestamp;

        return ((timestamp - epoch) << timestampLeftShift) |
                (datacenterId << datacenterIdShift) |
                (workerId << workerIdShift) |
                sequence;
    }

    private long tilNextMillis(long lastTimestamp) {
        long timestamp = timeGen();
        while (timestamp <= lastTimestamp) {
            timestamp = timeGen();
        }
        return timestamp;
    }

    private long timeGen() {
        return System.currentTimeMillis();
    }
}

并发题

多线程交替打印数字

两个线程交替打印数字，一个线程打印奇数，另一个线程打印偶数，直到100。

使用synchronized实现

class PrintOddEven {
    private final Object lock = new Object();
    private int number = 1;

    public void printOdd() {
        synchronized (lock) {
            while (number < 100) {
                if (number % 2 == 0) {
                    try {
                        lock.wait();
                    } catch (InterruptedException e) {
                        Thread.currentThread().interrupt();
                    }
                } else {
                    System.out.println(Thread.currentThread().getName() + ": " + number);
                    number++;
                    lock.notify();
                }
            }
        }
    }

    public void printEven() {
        synchronized (lock) {
            while (number < 100) {
                if (number % 2 != 0) {
                    try {
                        lock.wait();
                    } catch (InterruptedException e) {
                        Thread.currentThread().interrupt();
                    }
                } else {
                    System.out.println(Thread.currentThread().getName() + ": " + number);
                    number++;
                    lock.notify();
                }
            }
        }
    }
    
    public static void main(String[] args) {
        PrintOddEven poe = new PrintOddEven();
        Thread t1 = new Thread(poe::printOdd, "Odd");
        Thread t2 = new Thread(poe::printEven, "Even");
        t1.start();
        t2.start();
    }
    
}

使用ReentrantLock实现

import java.util.concurrent.locks.Condition;
import java.util.concurrent.locks.ReentrantLock;

class PrintOddEvenLock {
    private final ReentrantLock lock = new ReentrantLock();
    private final Condition condition = lock.newCondition();
    private int number = 1;

    public void printOdd() {
        lock.lock();
        try {
            while (number < 100) {
                if (number % 2 == 0) {
                    condition.await();
                } else {
                    System.out.println(Thread.currentThread().getName() + ": " + number);
                    number++;
                    condition.signal();
                }
            }
        } catch (InterruptedException e) {
            Thread.currentThread().interrupt();
        } finally {
            lock.unlock();
        }
    }

    public void printEven() {
        lock.lock();
        try {
            while (number < 100) {
                if (number % 2 != 0) {
                    condition.await();
                } else {
                    System.out.println(Thread.currentThread().getName() + ": " + number);
                    number++;
                    condition.signal();
                }
            }
        } catch (InterruptedException e) {
            Thread.currentThread().interrupt();
        } finally {
            lock.unlock();
        }
    }

    public static void main(String[] args) {
        PrintOddEvenLock poe = new PrintOddEvenLock();
        Thread t1 = new Thread(poe::printOdd, "Odd");
        Thread t2 = new Thread(poe::printEven, "Even");
        t1.start();
        t2.start();
    }
}

使用Semaphore实现

import java.util.concurrent.Semaphore;

class PrintOddEvenSemaphore {
    private final Semaphore oddSemaphore = new Semaphore(1);
    private final Semaphore evenSemaphore = new Semaphore(0);
    private int number = 1;

    public void printOdd() {
        try {
            while (number < 100) {
                oddSemaphore.acquire();
                System.out.println(Thread.currentThread().getName() + ": " + number);
                number++;
                evenSemaphore.release();
            }
        } catch (InterruptedException e) {
            Thread.currentThread().interrupt();
        }
    }

    public void printEven() {
        try {
            while (number < 100) {
                evenSemaphore.acquire();
                System.out.println(Thread.currentThread().getName() + ": " + number);
                number++;
                oddSemaphore.release();
            }
        } catch (InterruptedException e) {
            Thread.currentThread().interrupt();
        }
    }

    public static void main(String[] args) {
        PrintOddEvenSemaphore poe = new PrintOddEvenSemaphore();
        Thread t1 = new Thread(poe::printOdd, "Odd");
        Thread t2 = new Thread(poe::printEven, "Even");
        t1.start();
        t2.start();
    }
}

多线程按顺序打印ABC

三个线程按顺序打印ABC，重复10次。

class PrintABC {
    private final Object lock = new Object();
    private int state = 0;

    public void printA() {
        synchronized (lock) {
            for (int i = 0; i < 10; i++) {
                while (state % 3 != 0) {
                    try {
                        lock.wait();
                    } catch (InterruptedException e) {
                        Thread.currentThread().interrupt();
                    }
                }
                System.out.print("A");
                state++;
                lock.notifyAll();
            }
        }
    }

    public void printB() {
        synchronized (lock) {
            for (int i = 0; i < 10; i++) {
                while (state % 3 != 1) {
                    try {
                        lock.wait();
                    } catch (InterruptedException e) {
                        Thread.currentThread().interrupt();
                    }
                }
                System.out.print("B");
                state++;
                lock.notifyAll();
            }
        }
    }

    public void printC() {
        synchronized (lock) {
            for (int i = 0; i < 10; i++) {
                while (state % 3 != 2) {
                    try {
                        lock.wait();
                    } catch (InterruptedException e) {
                        Thread.currentThread().interrupt();
                    }
                }
                System.out.println("C");
                state++;
                lock.notifyAll();
            }
        }
    }

    public static void main(String[] args) {
        PrintABC printABC = new PrintABC();
        new Thread(printABC::printA, "A").start();
        new Thread(printABC::printB, "B").start();
        new Thread(printABC::printC, "C").start();
    }
}

模拟死锁

class DeadLockDemo2 {

    private static final Object objectA = new Object();
    private static final Object objectB = new Object();

    public static void main(String[] args) {
        Thread thread1 = new Thread(new MyTask(objectA, objectB), "Thread 1");
        Thread thread2 = new Thread(new MyTask(objectB, objectA), "Thread 2");

        thread1.start();
        thread2.start();
    }

    static class MyTask implements Runnable {
        private final Object firstResource;
        private final Object secondResource;
        public MyTask(Object objectA, Object objectB) {
            this.firstResource = objectA;
            this.secondResource = objectB;
        }
        @Override
        public void run() {
            System.out.println(Thread.currentThread().getName() + "获取第一个资源");
            synchronized (firstResource) {

                System.out.println(Thread.currentThread().getName() + "已获取第一个资源");
                
                try {
                    Thread.sleep(100);
                } catch (InterruptedException e) {
                    throw new RuntimeException(e);
                }

                System.out.println(Thread.currentThread().getName() + "获取第二个资源");
                synchronized (secondResource) {
                    System.out.println(Thread.currentThread().getName() + "已获取第二个资源");
                }
            }
        }
    }
}

生产者消费者问题

使用阻塞队列实现生产者消费者问题。

import java.util.concurrent.ArrayBlockingQueue;
import java.util.concurrent.BlockingQueue;

class ProducerConsumer {
    private static final int CAPACITY = 10;
    private final BlockingQueue<Integer> queue = new ArrayBlockingQueue<>(CAPACITY);

    public void produce() throws InterruptedException {
        int value = 0;
        while (true) {
            queue.put(value);
            System.out.println("Produced: " + value);
            value++;
        }
    }

    public void consume() throws InterruptedException {
        while (true) {
            int value = queue.take();
            System.out.println("Consumed: " + value);
        }
    }

    public static void main(String[] args) {
        ProducerConsumer pc = new ProducerConsumer();
        Thread producer = new Thread(() -> {
            try {
                pc.produce();
            } catch (InterruptedException e) {
                Thread.currentThread().interrupt();
            }
        });
        Thread consumer = new Thread(() -> {
            try {
                pc.consume();
            } catch (InterruptedException e) {
                Thread.currentThread().interrupt();
            }
        });
        producer.start();
        consumer.start();
    }
}

哲学家进餐问题

使用信号量解决哲学家进餐问题。

import java.util.concurrent.Semaphore;

class Philosopher extends Thread {
    private final Semaphore leftChopstick;
    private final Semaphore rightChopstick;
    private final int philosopherNumber;

    public Philosopher(int philosopherNumber, Semaphore leftChopstick, Semaphore rightChopstick) {
        this.philosopherNumber = philosopherNumber;
        this.leftChopstick = leftChopstick;
        this.rightChopstick = rightChopstick;
    }

    public void run() {
        try {
            while (true) {
                think();
                pickUpChopsticks();
                eat();
                putDownChopsticks();
            }
        } catch (InterruptedException e) {
            Thread.currentThread().interrupt();
        }
    }

    private void think() throws InterruptedException {
        System.out.println("Philosopher " + philosopherNumber + " is thinking.");
        Thread.sleep((long) (Math.random() * 1000));
    }

    private void pickUpChopsticks() throws InterruptedException {
        leftChopstick.acquire();
        rightChopstick.acquire();
        System.out.println("Philosopher " + philosopherNumber + " picked up chopsticks.");
    }

    private void eat() throws InterruptedException {
        System.out.println("Philosopher " + philosopherNumber + " is eating.");
        Thread.sleep((long) (Math.random() * 1000));
    }

    private void putDownChopsticks() {
        leftChopstick.release();
        rightChopstick.release();
        System.out.println("Philosopher " + philosopherNumber + " put down chopsticks.");
    }

    public static void main(String[] args) {
        int numberOfPhilosophers = 5;
        Semaphore[] chopsticks = new Semaphore[numberOfPhilosophers];
        for (int i = 0; i < numberOfPhilosophers; i++) {
            chopsticks[i] = new Semaphore(1);
        }
        Philosopher[] philosophers = new Philosopher[numberOfPhilosophers];
        for (int i = 0; i < numberOfPhilosophers; i++) {
            Semaphore leftChopstick = chopsticks[i];
            Semaphore rightChopstick = chopsticks[(i + 1) % numberOfPhilosophers];
            philosophers[i] = new Philosopher(i, leftChopstick, rightChopstick);
            philosophers[i].start();
        }
    }
}

使用CyclicBarrier实现多线程任务

使用CyclicBarrier实现多个线程分段执行任务，每个线程打印自己的任务完成后，等待其他线程到达，然后继续下一段任务。

import java.util.concurrent.BrokenBarrierException;
import java.util.concurrent.CyclicBarrier;

class CyclicBarrierExample {
    private static final int THREAD_COUNT = 3;
    private static final CyclicBarrier barrier = new CyclicBarrier(THREAD_COUNT, () -> System.out.println("All threads completed a phase."));

    public static void main(String[] args) {
        for (int i = 0; i < THREAD_COUNT; i++) {
            new Thread(new Task(), "Thread-" + i).start();
        }
    }

    static class Task implements Runnable {
        @Override
        public void run() {
            try {
                for (int i = 1; i <= 3; i++) {
                    System.out.println(Thread.currentThread().getName() + " completed phase " + i);
                    barrier.await();
                }
            } catch (InterruptedException | BrokenBarrierException e) {
                Thread.currentThread().interrupt();
            }
        }
    }
}

使用CountDownLatch实现任务协调

使用CountDownLatch等待多个线程完成任务后再继续主线程执行。

import java.util.concurrent.CountDownLatch;

class CountDownLatchExample {
    private static final int THREAD_COUNT = 3;
    private static final CountDownLatch latch = new CountDownLatch(THREAD_COUNT);

    public static void main(String[] args) {
        for (int i = 0; i < THREAD_COUNT; i++) {
            new Thread(new Task(), "Thread-" + i).start();
        }

        try {
            latch.await();
            System.out.println("All threads have finished. Main thread continues.");
        } catch (InterruptedException e) {
            Thread.currentThread().interrupt();
        }
    }

    static class Task implements Runnable {
        @Override
        public void run() {
            try {
                System.out.println(Thread.currentThread().getName() + " is working.");
                Thread.sleep((long) (Math.random() * 1000));
                System.out.println(Thread.currentThread().getName() + " has finished.");
            } catch (InterruptedException e) {
                Thread.currentThread().interrupt();
            } finally {
                latch.countDown();
            }
        }
    }
}

使用Exchanger实现线程间数据交换

使用Exchanger实现两个线程交换数据。

import java.util.concurrent.Exchanger;

class ExchangerExample {
    private static final Exchanger<String> exchanger = new Exchanger<>();

    public static void main(String[] args) {
        new Thread(() -> {
            try {
                String data = "Data from Thread A";
                System.out.println("Thread A is exchanging: " + data);
                String receivedData = exchanger.exchange(data);
                System.out.println("Thread A received: " + receivedData);
            } catch (InterruptedException e) {
                Thread.currentThread().interrupt();
            }
        }, "Thread A").start();

        new Thread(() -> {
            try {
                String data = "Data from Thread B";
                System.out.println("Thread B is exchanging: " + data);
                String receivedData = exchanger.exchange(data);
                System.out.println("Thread B received: " + receivedData);
            } catch (InterruptedException e) {
                Thread.currentThread().interrupt();
            }
        }, "Thread B").start();
    }
}

拓展：实现和指定的线程交换数据

class ExchangerRegistry {
    private static final ConcurrentHashMap<String, Exchanger<String>> exchangers = new ConcurrentHashMap<>();

    public static Exchanger<String> getExchanger(String threadName, String targetThreadName) {
        String key = generateKey(threadName, targetThreadName);
        return exchangers.computeIfAbsent(key, k -> new Exchanger<>());
    }

    private static String generateKey(String threadName, String targetThreadName) {
        return threadName.compareTo(targetThreadName) < 0 ? threadName + "-" + targetThreadName : targetThreadName + "-" + threadName;
    }
}

class ExchangerExample {
    public static void main(String[] args) {
        Thread threadA = new Thread(() -> exchangeData("ThreadB", "Data-A"), "ThreadA");
        Thread threadB = new Thread(() -> exchangeData("ThreadA", "Data-B"), "ThreadB");
        Thread threadC = new Thread(() -> exchangeData("ThreadD", "Data-C"), "ThreadC");
        Thread threadD = new Thread(() -> exchangeData("ThreadC", "Data-D"), "ThreadD");

        threadA.start();
        threadB.start();
        threadC.start();
        threadD.start();
    }

    private static void exchangeData(String targetThreadName, String dataToSend) {
        String threadName = Thread.currentThread().getName();
        Exchanger<String> exchanger = ExchangerRegistry.getExchanger(threadName, targetThreadName);

        try {
            System.out.println(threadName + " is exchanging: " + dataToSend);
            String receivedData = exchanger.exchange(dataToSend);
            System.out.println(threadName + " received: " + receivedData);
        } catch (InterruptedException e) {
            Thread.currentThread().interrupt();
        }
    }
}

数学相关

两数之和

在数组中找到两个数，使它们的和等于给定的数。

public int[] twoSum(int[] nums, int target) {
    Map<Integer, Integer> map = new HashMap<>();
    for (int i = 0; i < nums.length; i++) {
        int complement = target - nums[i];
        if (map.containsKey(complement)) {
            return new int[] { map.get(complement), i };
        }
        map.put(nums[i], i);
    }
    throw new IllegalArgumentException("No two sum solution");
}

快乐数

判断一个数是否为快乐数，即反复将每个位的数字平方求和，最终会得到1。

public boolean isHappy(int n) {
    Set<Integer> seenNumbers = new HashSet<>();
    while (n != 1 && !seenNumbers.contains(n)) {
        seenNumbers.add(n);
        n = getSumOfSquares(n);
    }
    return n == 1;
}
private int getSumOfSquares(int num) {
    int sum = 0;
    while (num > 0) {
        int digit = num % 10;
        sum += digit * digit;
        num /= 10;
    }
    return sum;
}

回文数

判断一个整数是否是回文数，即正读和反读都一样。

public boolean isPalindrome(int x) {
    if (x < 0 || (x % 10 == 0 && x != 0)) {
        return false;
    }
    int revertedNumber = 0;
    while (x > revertedNumber) {
        revertedNumber = revertedNumber * 10 + x % 10;
        x /= 10;
    }
    return x == revertedNumber || x == revertedNumber / 10;
}

罗马数字转整数

将罗马数字转换为整数。

public int romanToInt(String s) {
    Map<Character, Integer> roman = new HashMap<>();
    roman.put('I', 1);
    roman.put('V', 5);
    roman.put('X', 10);
    roman.put('L', 50);
    roman.put('C', 100);
    roman.put('D', 500);
    roman.put('M', 1000);
    
    int sum = 0;
    for (int i = 0; i < s.length(); i++) {
        int current = roman.get(s.charAt(i));
        int next = (i + 1 < s.length()) ? roman.get(s.charAt(i + 1)) : 0;
        if (current < next) {
            sum -= current;
        } else {
            sum += current;
        }
    }
    return sum;
}

整数反转

给出一个32位的有符号整数，将整数中的数字进行反转。

public int reverse(int x) {
    int rev = 0;
    while (x != 0) {
        int pop = x % 10;
        x /= 10;
        if (rev > Integer.MAX_VALUE/10 || (rev == Integer.MAX_VALUE / 10 && pop > 7)) return 0;
        if (rev < Integer.MIN_VALUE/10 || (rev == Integer.MIN_VALUE / 10 && pop < -8)) return 0;
        rev = rev * 10 + pop;
    }
    return rev;
}

字符串相关

最长公共前缀

找到字符串数组中的最长公共前缀。

public String longestCommonPrefix(String[] strs) {
    if (strs.length == 0) return "";
    String prefix = strs[0];
    for (int i = 1; i < strs.length; i++) {
        while (strs[i].indexOf(prefix) != 0) {
            prefix = prefix.substring(0, prefix.length() - 1);
            if (prefix.isEmpty()) return "";
        }
    }
    return prefix;
}

最长递增非连续子序列长度

public int lengthOfLIS(int[] nums) {
    if (nums.length == 0) {
        return 0;
    }
    int[] dp = new int[nums.length];
    dp[0] = 1;
    int maxans = 1;
    for (int i = 1; i < nums.length; i++) {
        dp[i] = 1;
        for (int j = 0; j < i; j++) {
            if (nums[i] > nums[j]) {
                dp[i] = Math.max(dp[i], dp[j] + 1);
            }
        }
        maxans = Math.max(maxans, dp[i]);
    }
    return maxans;
}

最长递增连续子序列长度

public static int longestContinuousSubsequence(int[] nums) {
    if (nums == null || nums.length == 0) {
        return 0;
    }

    int longest = 1;
    int curLength = 1;

    for (int i = 1; i < nums.length; i++) {
        if (nums[i] == nums[i - 1] + 1) {
            curLength++;
        } else {
            longest = Math.max(longest, curLength);
            curLength = 1;
        }
    }

    // 更新最长连续子序列的长度，以防止最后一段最长序列没有更新
    longest = Math.max(longest, curLength);

    return longest;
}

能否组成顺子

class Shunzi{
    public static boolean isShunzi(int[] places) {
        if (places == null || places.length == 0) {
            return false;
        }
        Arrays.sort(places);
        int zeroCount = 0;
        for (int num : places) {
            if (num == 0) {
                zeroCount++;
            }
        }
        // 计算前后相邻的数字相隔的大小，需要多少个个0去补
        int gapCount = 0;
        for (int i = zeroCount; i < places.length - 1; i++) {
            if (places[i] == places[i + 1]) {
                return false;  // 有重复的非零数字，不能成为顺子
            }
            gapCount += places[i + 1] - places[i] - 1;
        }
        return gapCount <= zeroCount;
    }

    public static void main(String[] args) {
        // 测试用例
        int[] test1 = {1, 2, 3, 4, 5}; // 顺子
        int[] test2 = {0, 2, 3, 4, 5}; // 顺子
        int[] test3 = {1, 0, 0, 4, 5}; // 顺子
        int[] test4 = {0, 0, 0, 0, 0}; // 顺子
        int[] test5 = {1, 2, 4, 5, 6}; // 不是顺子
        int[] test6 = {9, 10, 11, 12, 13}; // 是顺子
        int[] test7 = {0, 2, 4, 6, 7};  // 不是顺子

        System.out.println(isShunzi(test1)); // 输出 true
        System.out.println(isShunzi(test2)); // 输出 true
        System.out.println(isShunzi(test3)); // 输出 true
        System.out.println(isShunzi(test4)); // 输出 true
        System.out.println(isShunzi(test5)); // 输出 false
        System.out.println(isShunzi(test6)); // 输出 true
        System.out.println(isShunzi(test7)); // 输出 false
    }
}

最长回文子串

找到一个字符串中的最长回文子串。

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 = expandAroundCenter(s, i, i);
        int len2 = expandAroundCenter(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 expandAroundCenter(String s, int left, int right) {
    while (left >= 0 && right < s.length() && s.charAt(left) == s.charAt(right)) {
        left--;
        right++;
    }
    return right - left - 1;
}

数组相关

两数之和 II

在一个排序列表中找到两个数，使它们的和等于给定的数。

public int[] twoSum(int[] numbers, int target) {
    int left = 0, right = numbers.length - 1;
    while (left < right) {
        int sum = numbers[left] + numbers[right];
        if (sum == target) {
            return new int[] { left + 1, right + 1 };
        } else if (sum < target) {
            left++;
        } else {
            right--;
        }
    }
    throw new IllegalArgumentException("No two sum solution");
}

合并两个有序数组

合并两个有序数组为一个有序数组。

public void merge(int[] nums1, int m, int[] nums2, int n) {
    int i = m - 1, j = n - 1, k = m + n - 1;
    while (i >= 0 && j >= 0) {
        if (nums1[i] > nums2[j]) {
            nums1[k--] = nums1[i--];
        } else {
            nums1[k--] = nums2[j--];
        }
    }
    while (j >= 0) {
        nums1[k--] = nums2[j--];
    }
}

最大子数组和

class MaxSubArray{
    public static int maxSubArray(int[] nums) {
        for (int i = 1; i < nums.length; i++) {
            nums[i] = nums[i] + Math.max(0, nums[i - 1]);
        }
        System.out.println("动规结果：" + Arrays.toString(nums));
        return Arrays.stream(nums).max().getAsInt();
    }

    public static int maxSubArray2(int[] nums) {
        int pre = 0, res = nums[0];
        for (int num : nums) {
            pre = Math.max(pre + num, num);
            res = Math.max(pre, res);
        }
        return res;
    }

    public static void main(String[] args) {
        int[] nums = {-2, 1, -3, 4, -1, 2, 1, -5, 4};
        System.out.println(maxSubArray2(nums));
    }
}

最大连续子数组和

class MaxContinuousSubArray {
    public static int maxSubArray(int[] nums) {
        int cur = nums[0], max = nums[0];
        for (int i = 1; i < nums.length; i++) {
            cur = Math.max(nums[i], cur + nums[i]);
            max = Math.max(max, cur);
        }
        return max;
    }

    public static void main(String[] args) {
        int[] nums = {-2, 1, -3, 4, -1, 2, 1, -5, 4};
        System.out.println(maxSubArray(nums)); // 输出: 6
    }
}

旋转数组

给定一个数组，将数组中的元素向右移动 k 个位置。

public void rotate(int[] nums, int k) {
    k %= nums.length;
    reverse(nums, 0, nums.length - 1);
    reverse(nums, 0, k - 1);
    reverse(nums, 0, nums.length - 1);
}

private void reverse(int[] nums, int start, int end) {
    while (start < end) {
        int temp = nums[start];
        nums[start] = nums[end];
        nums[end] = temp;
        start++;
        end--;
    }
}

搜索旋转排序数组

在旋转排序数组中查找一个特定的元素。

public int search(int[] nums, int target) {
    int left = 0, right = nums.length - 1;
    while (left <= right) {
        int mid = left + (right - left) / 2;
        if (nums[mid] == target) return mid;
        if (nums[left] <= nums[mid]) {
            if (nums[left] <= target && target < nums[mid]) {
                right = mid - 1;
            } else {
                left = mid + 1;
            }
        } else {
            if (nums[mid] < target && target <= nums[right]) {
                left = mid + 1;
            } else {
                right = mid - 1;
            }
        }
    }
    return -1;
}

链表相关

static class ListNode {
    int val;
    ListNode next;

    ListNode(int x) {
        val = x;
    }
}

反转链表

反转一个单链表。

public ListNode reverseList(ListNode head) {
    ListNode prev = null;
    ListNode curr = head;
    while (curr != null) {
        ListNode nextTemp = curr.next;
        curr.next = prev;
        prev = curr;
        curr = nextTemp;
    }
    return prev;
}

合并两个链表

将两个升序链表合并为一个升序链表。

public ListNode mergeTwoLists(ListNode l1, ListNode l2) {
    ListNode dummy = new ListNode(-1);
    ListNode current = dummy;
    while (l1 != null && l2 != null) {
        if (l1.val <= l2.val) {
            current.next = l1;
            l1 = l1.next;
        } else {
            current.next = l2;
            l2 = l2.next;
        }
        current = current.next;
    }
    current.next = (l1 != null) ? l1 : l2;
    return dummy.next;
}

删除链表中的节点

删除链表中等于给定值的所有节点。

public ListNode removeElements(ListNode head, int val) {
    ListNode dummy = new ListNode(0);
    dummy.next = head;
    ListNode current = dummy;
    while (current.next != null) {
        if (current.next.val == val) {
            current.next = current.next.next;
        } else {
            current = current.next;
        }
    }
    return dummy.next;
}

倒数第K个节点

public int LastNode1(ListNode head, int k) {
    if (head == null) return 0;

    // 用一个集合记录所有的链表元素
    List<ListNode> list = new ArrayList<>();
    while (head != null) {
        list.add(head);
        head = head.next;
    }
    return list.get(list.size() - k).val;
}

public int LastNode2(ListNode head, int k) {
    if (head == null) return 0;

    int N = 0;
    ListNode curr = head;
    // 第一次遍历，找到链表的长度
    while (curr != null) {
        curr = curr.next;
        N++;
    }
    // 第二次遍历，遍历到 N - k 即可
    for (int i = 0; i < N - k; i++) {
        head = head.next;
    }
    return head.val;
}

栈和队列相关

有效的括号

判断字符串中的括号是否有效配对。

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();
}

最小栈

设计一个支持常数时间复杂度内获取最小元素的栈。

class MinStack {
    private Stack<Integer> stack;
    private Stack<Integer> minStack;

    public MinStack() {
        stack = new Stack<>();
        minStack = new Stack<>();
    }

    public void push(int val) {
        stack.push(val);
        if (minStack.isEmpty() || val <= minStack.peek()) {
            minStack.push(val);
        }
    }

    public void pop() {
        if (stack.pop().equals(minStack.peek())) {
            minStack.pop();
        }
    }

    public int top() {
        return stack.peek();
    }

    public int getMin() {
        return minStack.peek();
    }
}

树和图相关

static class TreeNode {
    int val;
    TreeNode left;
    TreeNode right;
    TreeNode(int x) {
        val = x;
    }
}

二叉树遍历

实现二叉树的前序、中序、后序、层次遍历。

// Preorder traversal
public List<Integer> preorderTraversal(TreeNode root) {
    List<Integer> result = new ArrayList<>();
    preorderHelper(root, result);
    return result;
}

private void preorderHelper(TreeNode node, List<Integer> result) {
    if (node != null) {
        result.add(node.val);
        preorderHelper(node.left, result);
        preorderHelper(node.right, result);
    }
}

// Inorder traversal
public List<Integer> inorderTraversal(TreeNode root) {
    List<Integer> result = new ArrayList<>();
    inorderHelper(root, result);
    return result;
}

private void inorderHelper(TreeNode node, List<Integer> result) {
    if (node != null) {
        inorderHelper(node.left, result);
        result.add(node.val);
        inorderHelper(node.right, result);
    }
}

// Postorder traversal
public List<Integer> postorderTraversal(TreeNode root) {
    List<Integer> result = new ArrayList<>();
    postorderHelper(root, result);
    return result;
}

private void postorderHelper(TreeNode node, List<Integer> result) {
    if (node != null) {
        postorderHelper(node.left, result);
        postorderHelper(node.right, result);
        result.add(node.val);
    }
}

public List<List<Integer>> levelOrder(TreeNode root) {
    List<List<Integer>> result = new ArrayList<>();
    if (root == null) return result;
    
    Queue<TreeNode> queue = new LinkedList<>();
    queue.add(root);
    while (!queue.isEmpty()) {
        int size = queue.size();
        List<Integer> level = new ArrayList<>();
        for (int i = 0; i < size; i++) {
            TreeNode node = queue.poll();
            level.add(node.val);
            if (node.left != null) queue.add(node.left);
            if (node.right != null) queue.add(node.right);
        }
        result.add(level);
    }
    return result;
}

路径总和

判断二叉树中是否存在一条路径，其路径和等于给定的数值。

public boolean hasPathSum(TreeNode root, int sum) {
    if (root == null) return false;
    if (root.left == null && root.right == null) return sum == root.val;
    return hasPathSum(root.left, sum - root.val) || hasPathSum(root.right, sum - root.val);
}

对称二叉树

判断一个二叉树是否是它的镜像。

public boolean isSymmetric(TreeNode root) {
    if (root == null) return true;
    return isMirror(root.left, root.right);
}

private boolean isMirror(TreeNode t1, TreeNode t2) {
    if (t1 == null && t2 == null) return true;
    if (t1 == null || t2 == null) return false;
    return (t1.val == t2.val)
            && isMirror(t1.right, t2.left)
            && isMirror(t1.left, t2.right);
}

翻转二叉树

public void invertTree(TreeNode root) {
    if (root == null) return;

    // 交换当前节点的左右子树
    TreeNode temp = root.left;
    root.left = root.right;
    root.right = temp;

    // 递归地对左子树和右子树进行翻转
    invertTree(root.left);
    invertTree(root.right);
}

排序相关

冒泡排序

public void bubbleSort(int[] arr) {
    int n = arr.length;
    boolean swapped;
    for (int i = 0; i < n - 1; i++) {
        swapped = false;
        for (int j = 0; j < n - i - 1; j++) {
            if (arr[j] > arr[j + 1]) {
                // 交换 arr[j] 和 arr[j + 1]
                int temp = arr[j];
                arr[j] = arr[j + 1];
                arr[j + 1] = temp;
                swapped = true;
            }
        }
        if (!swapped) break;
    }
}

插入排序

在插入排序时，使用二分查找找到插入的位置，从而减少比较次数（但仍然需要线性时间插入元素）。

public void insertionSort(int[] arr) {
    for (int i = 1; i < arr.length; i++) {
        int key = arr[i];
        int j = i - 1;

        // 使用二分查找确定插入位置
        int insertPos = binarySearch(arr, 0, j, key);

        // 移动元素
        while (j >= insertPos) {
            arr[j + 1] = arr[j];
            j--;
        }
        arr[insertPos] = key;
    }
}

选择排序

在选择最小元素时，记录最小元素的索引，并在每次找到更小元素时更新索引。

public void selectionSort(int[] arr) {
    int n = arr.length;
    for (int i = 0; i < n - 1; i++) {
        int minIndex = i;
        for (int j = i + 1; j < n; j++) {
            if (arr[j] < arr[minIndex]) {
                minIndex = j;
            }
        }
        // 交换 arr[i] 和 arr[minIndex]
        if (minIndex != i) {
            int temp = arr[i];
            arr[i] = arr[minIndex];
            arr[minIndex] = temp;
        }
    }
}

快速排序

/**
 * 快速排序的主方法
 * 
 * @param array 需要排序的数组
 * @param low   当前排序部分的左边界
 * @param high  当前排序部分的右边界
 */
public void quickSort(int[] array, int low, int high) {
    if (low < high) {
        int pivotIndex = partition(array, low, high);
        quickSort(array, low, pivotIndex - 1);
        quickSort(array, pivotIndex + 1, high);
    }
}

/**
 * 将数组分区，并返回分区点的索引
 * 
 * @param array 需要排序的数组
 * @param low   当前分区部分的左边界
 * @param high  当前分区部分的右边界
 * @return 分区点的索引
 */
private int partition(int[] array, int low, int high) {
    int pivot = array[high];  // 选择最后一个元素作为枢轴
    int i = low - 1;  // 小于枢轴的元素的边界

    for (int j = low; j < high; j++) {
        if (array[j] < pivot) {
            // 交换小于枢轴的元素到前面
            i++;
            swap(array, i, j);
        }
    }

    // 将枢轴放到正确的位置
    swap(array, i + 1, high);
    return i + 1;
}

/**
 * 交换数组中两个元素
 * 
 * @param array 需要排序的数组
 * @param i     元素一的索引
 * @param j     元素二的索引
 */
private void swap(int[] array, int i, int j) {
    int temp = array[i];
    array[i] = array[j];
    array[j] = temp;
}

归并排序

/**
 * 主排序方法，递归地将数组分成两部分进行排序
 * 
 * @param array 需要排序的数组
 * @param left  当前排序部分的左边界
 * @param right 当前排序部分的右边界
 */
public void mergeSort(int[] array, int left, int right) {
    if (left < right) {
        int middle = (left + right) / 2;
        mergeSort(array, left, middle);
        mergeSort(array, middle + 1, right);
        merge(array, left, middle, right);
    }
}

/**
 * 合并两个已排序的子数组
 * 
 * @param array 需要排序的数组
 * @param left  当前合并部分的左边界
 * @param middle 中间分隔点
 * @param right 当前合并部分的右边界
 */
private void merge(int[] array, int left, int middle, int right) {
    int leftSize = middle - left + 1;
    int rightSize = right - middle;

    int[] leftArray = new int[leftSize];
    int[] rightArray = new int[rightSize];

    // 复制数据到临时数组
    System.arraycopy(array, left, leftArray, 0, leftSize);
    System.arraycopy(array, middle + 1, rightArray, 0, rightSize);

    int i = 0, j = 0, k = left;

    // 合并两个临时数组
    while (i < leftSize && j < rightSize) {
        array[k++] = (leftArray[i] <= rightArray[j]) ? leftArray[i++] : rightArray[j++];
    }

    // 复制剩余的元素
    while (i < leftSize) {
        array[k++] = leftArray[i++];
    }

    while (j < rightSize) {
        array[k++] = rightArray[j++];
    }
}

动态规划

爬楼梯

public int climbStairs(int n) {
    if (n <= 2) return n;
    int[] dp = new int[n + 1];
    dp[1] = 1;
    dp[2] = 2;
    for (int i = 3; i <= n; i++) {
        dp[i] = dp[i - 1] + dp[i - 2];
    }
    return dp[n];
}

public int lengthOfLIS(int[] nums) {
    if (nums == null || nums.length == 0) return 0;
    int[] dp = new int[nums.length];
    int len = 0;
    for (int num : nums) {
        int i = Arrays.binarySearch(dp, 0, len, num);
        if (i < 0) i = -(i + 1);
        dp[i] = num;
        if (i == len) len++;
    }
    return len;
}

特殊题

数组中重复的数字

public int findRepeatNumber(int[] nums) {
    for (int i = 0; i < nums.length; i++) {
        while (nums[i] != i) {
            if (nums[i] == nums[nums[i]]) return nums[i];
            int temp = nums[i];
            nums[i] = nums[temp];
            nums[temp] = temp;
        }
    }
    return -1;
}

替换空格

public String replaceSpace(String s) {
    return s.replace(" ", "%20");
}