非力扣100原题

 多线程交替打印0-100

2个线程交替打印0-100
public class Main {

    private static final Object LOCK = new Object();
    private static volatile int count = 0;
    private static final int MAX = 100;

    public static void main(String[] args) {
        Thread thread = new Thread(new Seq(0));
        Thread thread1 = new Thread(new Seq(1));
        thread.start();
        thread1.start();
    }

    static class Seq implements Runnable {
        private final int index;

        public Seq(int index) {
            this.index = index;
        }

        @Override
        public void run() {
            // Run方法只要执行结束了,线程就结束了
            while (count < MAX) {
                // 同步代码块,一个时刻只能有一个线程获取到锁
                synchronized (LOCK) {
                    // 获取到锁就进来判断，当前是否轮到该线程打印
                    while (count % 2 != index) {
                        // 不是当前线程打印,那么就让当前线程去wait,它会自动释放锁,所以其他线程可以进来
                        try {
                            LOCK.wait();
                            // 当线程被唤醒时，会尝试重新进入synchronized代码块
                        } catch (Exception e) {
                            e.printStackTrace();
                        }
                    }
                    // 是当前线程打印, 但count>MAX
                    if (count > MAX) {
                        LOCK.notifyAll();
                        return;
                    }
                    System.out.println("Thread-" + index + ":" + count);
                    count++;
                    LOCK.notifyAll();
                }
            }
        }
    }
}

public class Main {

    private static final Object LOCK = new Object();
    private static volatile int count = 0;
    private static final int MAX = 100;

    public static void main(String[] args) {
        Thread thread = new Thread(new Seq(0));
        Thread thread1 = new Thread(new Seq(1));
        Thread thread2 = new Thread(new Seq(2));
        thread.start();
        thread1.start();
        thread2.start();
    }

    static class Seq implements Runnable {
        private final int index;

        public Seq(int index) {
            this.index = index;
        }

        @Override
        public void run() {
            // Run方法只要执行结束了,线程就结束了
            while (count < MAX) {
                // 同步代码块,一个时刻只能有一个线程获取到锁
                synchronized (LOCK) {
                    // 获取到锁就进来判断，当前是否轮到该线程打印
                    while (count % 3 != index) {
                        // 不是当前线程打印,那么就让当前线程去wait,它会自动释放锁,所以其他线程可以进来
                        try {
                            LOCK.wait();
                            // 当线程被唤醒时，会尝试重新进入synchronized代码块
                        } catch (Exception e) {
                            e.printStackTrace();
                        }
                    }
                    // 是当前线程打印, 但count>MAX
                    if (count > MAX) {
                        LOCK.notifyAll();
                        return;
                    }
                    System.out.println("Thread-" + index + ":" + count);
                    count++;
                    LOCK.notifyAll();
                }
            }
        }
    }
}

多线程交替打印ABC

import java.util.concurrent.Semaphore;
// 多线程打印ABC
public class Printer {
    private final Semaphore semA = new Semaphore(1); // 信号量A设置为1,从A开始打印
    private final Semaphore semB = new Semaphore(0);
    private final Semaphore semC = new Semaphore(0);
    private static int n = 3;   // 打印轮次

    public static void main(String[] args) {
        Printer printer = new Printer();
        new Thread(()->printer.print('A',printer.semA,printer.semB)).start();
        new Thread(()->printer.print('B',printer.semB,printer.semC)).start();
        new Thread(()->printer.print('C',printer.semC,printer.semA)).start();
    }
    public void print(char ch, Semaphore current, Semaphore next) {
        try {
            for (int i = 0; i < n; i++) {
                current.acquire();  // 获取当前信号量
                System.out.println(Thread.currentThread().getName() + ": " + ch);
                next.release();     // 释放下一个信号量
            }
        } catch (InterruptedException e) {
            e.printStackTrace();
        }
    }
}

奇偶交换

给定数组，奇数在前，偶数在后

import java.util.Arrays;
public class Solution {
    public static int[] jiaohuang(int[] nums){
        if(nums.length<2||nums == null){
            return nums;
        }

        int left = 0;
        int right = nums.length-1;
        while (left<right){
            //  选定偶数
            while (left<right && nums[left] % 2 !=0){
                left++;
            }
            //  选定奇数
            while (left<right && nums[right]%2 == 0){
                right--;
            }
            if(left < right){
                int temp = nums[left];
                nums[left] = nums[right];
                nums[right] = temp;
                left++;
                right--;
            }
        }
        return nums;
    }

    public static void main(String[] args){
        Solution solution  = new Solution();
        int[] nums = {1,2,3,4};
        int[] result = solution.jiaohuang(nums);
        System.out.print(Arrays.toString(nums));
    }
}

字典序的第k小数字

// 字典序：数字的前缀进行排序，如10<9,因为10的前缀是1<9
// 数组{1，2，-，9，10，11，12}-->{1,10,11,12,2,--,9}
// 思路：当前指针+前缀数(非指针概念)，当成一个(key，value)形式,cur为key，value = 前缀数
// 如果当前指针<目标指针，while循环，
// 计算当前数的节点数(如1-201，那么在1和2之间隔着10-19，100-199：节点数为1+10+10*10)
// 如果 当前指针 + 当前前缀节点 <=k,即不在k的范围内，那么当前指针（下个前缀节点） = 当前指针 + 当前前缀节点，前缀数++
// else，在k的范围内，那么当前指针 = cur指针+1，前缀数*10更加细分
//（其实这里有点无限迭代的意思，判断在10-19区间还是继续细分在100-109~190-199区间，但n是固定的，有限迭代）

public int findKthNumber(int n, int k) {
         long cur = 1; // 当前指针对应
         long prix = 1; // 当前前缀数，可以把当成一个(key，value)形式,cur为key，value = 前缀数
         while (cur < k){
             long prixNum = getCount(prix,n);// 当前前缀节点数量
             // k不在当前前缀数
             if(cur+prixNum <= k){
                 cur+=prixNum; // 下个指针 = 当前指针+节点数
                 prix++; // 前缀数++
             }else {
                 cur++; // 在当前前缀循环，从1变成10，指针从索引0（1）到索引1（10）
                 prix*=10; // 前缀细分
             }
         }
         return (int)prix;
    }
    // 当前前缀下的所有子节点数总和=下一个前缀的起点-当前前缀的起点
    public long getCount(long prix,long n){
        long count = 0;// 节点数量
        long prixNext = prix+1; // 下一个前缀数
        while (prix <= n){
            count += Math.min(n-1,prixNext)-prix;
            prix*=10;
            prixNext*=10;
        }
        return count;
    }

带TTL的LRU缓存

相对于LRU：有一个时间字段ttl，需要改变的是put方法，仅在node不为空时，覆盖时间值，记得加上系统当前时间；在getNode方法中判断，当前节点是否过期，过期则移除节点以及对应的map的key，并返还为空

public class Solution {
    static class Node{
        int key,value;
        long expireTime;// 预定过期时间
        Node prev,next;

        Node(int key,int value,long ttl){
            this.key = key;
            this.value = value;
            this.expireTime = System.currentTimeMillis() + ttl;
        }
    }

    static class LRUCacheTTL{
        private  final int capacity;
        private final Node dummy = new Node(-1,-1,0);
        private final Map<Integer,Node> map = new HashMap<>();

        LRUCacheTTL(int capacity) {
            this.capacity = capacity;
            dummy.prev = dummy;
            dummy.next = dummy;

        }

        public int get(int key){
            Node node = getNode(key);
            if(node == null){
                return -1;
            }
            return node.value;
        }

        public void put(int key,int value,long ttl){
             Node node = getNode(key);
             if(node != null){
                 node.value = value;
                 node.expireTime = System.currentTimeMillis()+ttl;
             }
             node = new Node(key,value,ttl);
             map.put(key,node);
             pushFront(node);

             if(map.size()>capacity){
                 Node backNode = dummy.prev;
                 remove(backNode);
                 map.remove(backNode.key);
             }

        }

        public Node getNode(int key){
            Node node = map.get(key); // key不存在，返还为null
            if(node == null){
                return null;
            }
            if(node.expireTime <= System.currentTimeMillis()){
                remove(node);
                map.remove(key);
                return null;
            }
            remove(node);
            pushFront(node);
            return node;
        }

        public void remove(Node node){
           node.next.prev = node.prev;
           node.prev.next = node.next;
        }

        public void pushFront(Node node){
            node.prev = dummy;
            node.next = dummy.next;

            dummy.next = node;
            node.next.prev = node;
        }
    }

    public static void main(String[] args) {
        LRUCacheTTL cache = new LRUCacheTTL(2);

        cache.put(1, 1, 3000); // TTL: 3秒
        cache.put(2, 2, 5000); // TTL: 5秒

        System.out.println("get(1): " + cache.get(1)); // 1

        try {
            Thread.sleep(2000); // 等待2秒
        } catch (InterruptedException e) {
            Thread.currentThread().interrupt();
        }

        System.out.println("get(2): " + cache.get(2)); // 2

        try {
            Thread.sleep(3000); // 再等3秒 → key=1 已过期
        } catch (InterruptedException e) {
            Thread.currentThread().interrupt();
        }

        System.out.println("get(1): " + cache.get(1)); // -1 (已过期)

        cache.put(3, 3, 1000); // 触发淘汰，key=2 应该被踢掉
        System.out.println("get(2): " + cache.get(2)); // -1
        System.out.println("get(3): " + cache.get(3)); // 3
    }
}