devbox
小丑西瓜9
这个屌丝很懒，什么也没留下！
关注作者
热门标签
热门文章
当前位置:   article > 正文

常见的Java算法面试题_java算法面试题 经典

作者：小丑西瓜9 | 2024-06-09 11:11:38

赞

踩

java算法面试题 经典
1、 使用jedis客户端实现分布式锁方式
public boolean lock(Jedis jedis,String key,String val,int expireTime){
  String lock = jedis.set(key, val, "NX", "PX",
      expireTime);
  return "OK".equals(lock);
}
2、 jedis释放锁实现方式
public void unlock(Jedis jedis,String key,String value) {
    String script_command = "if redis.call('get',KEYS[1]) == ARGV[1] then " +
        "return redis.call('del',KEYS[1]) else return 0 end";
    // 解锁
    jedis.eval(script_command, Collections.singletonList(key), Collections.singletonList(value));
     
  }
3、手写一个阻塞队列
public class AxinBlockQueue {
    //队列容器
    private List<Integer> container = new ArrayList<>();
    private volatile int size;       被volatile修饰时，它会保证修改的值会立即被更新到内存
    private volatile int capacity;
    private Lock lock = new ReentrantLock();    ReentrantLock也是独占锁、可重入，加锁和解锁的过程需要手动进行，次数要一样
    //Condition
    private final Condition isNull = lock.newCondition();
    private final Condition isFull = lock.newCondition();
    AxinBlockQueue(int cap) {
        this.capacity = cap;
    }
    /**
     * 添加方法
     *
     * @param data
     */
    public void add(int data) {
        try {
            lock.lock();
            try {
                while (size >= capacity) {
                    System.out.println("阻塞队列满了");
                    isFull.await();
                }
            } catch (InterruptedException e) {
                isFull.signal();
                e.printStackTrace();
            }
            ++size;
            container.add(data);
            isNull.signal();
        } finally {
            lock.unlock();
        }
    }
    /**
     * 取出元素
     *
     * @return
     */
    public int take() {
        try {
            lock.lock();
            try {
                while (size == 0) {
                    System.out.println("阻塞队列空了");
                    isNull.await();
                }
            } catch (InterruptedException e) {
                isNull.signal();
                e.printStackTrace();
            }
            --size;
            int res = container.get(0);
            container.remove(0);
            isFull.signal();
            return res;
        } finally {
            lock.unlock();
        }
    }
}
public class Test {
    public static void main(String[] args) {
        int n[] = { 6, 5, 2, 7, 3, 9, 8 };
        heapsort(n);
        System.out.print("堆排序结果：");
        for (int m : n) {
            System.out.print(m + " ");
        }
    }
    /**
     * 堆排序
     * @param n 待排序数组
     */
    public static void heapsort(int n[]) {
        for (int i = n.length - 1; i >= 1; i--) {
            buildHeap(n, i);
            swap(n, 0, i);
        }
    }
    /**
     *
     * @param n   待排序数组
     * @param end 待排序数组末位下标
     */
    public static void buildHeap(int n[], int end) {
        int len = end + 1;
        for (int i = len / 2 - 1; i >= 0; i--) {
        //堆中i节点对应的左右子节点l和r
            int l = 2 * i + 1, r = l + 1;
        //指向较大数节点的指针
            int p = l;
            if (r <= len - 1 && n[l] < n[r]) {
                p = r;
            }
            if (n[i] < n[p]) {
                swap(n, i, p);
            }
        }
    }
    /**
     *
     * @param n 待排序数组
     * @param i 待交换数字数组下标
     * @param j 待交换数字数组下标
     */
    private static void swap(int n[], int i, int j) {
        n[i] ^= n[j];
        n[j] ^= n[i];
        n[i] ^= n[j];
    }
}
5、怎么实现一个线程安全的计数器
public class MySafeThread implements Runnable {
        //设置计数初值为0
        private static AtomicInteger count = new AtomicInteger(0);
    @Override
    public void run() {
    
        while (true) {
        try {
            Thread.sleep(1);
        } catch (InterruptedException e) {
            e.printStackTrace();
        }
        MySafeThread.calc();
        }
    }
    
    private synchronized static void calc() {
    
        if (count.get() < 1000) {
        
            // 自增1，返回更新后的值
            
            int c = count.incrementAndGet();
            
            System.out.println("线程:" + Thread.currentThread().getName()+" :" + c);
        
        }
    }
    public static void main(String[] args) {
        for (int i = 0; i < 5; i++) {
        
            MySafeThread myThread = new MySafeThread();
            
            Thread t = new Thread(myThread);
            
            t.start();
        }
    }
}
6、快速排序
static int RandPartition(int[] arr, int left, int right) {
            Random rd = new Random();
            int p = rd.Next(left, right + 1);
            Swap(ref arr[p], ref arr[left]);
            int temp = arr[left];
            while (left < right) {
                while (left < right && arr[right] > temp) { right--; count++; }
                arr[left] = arr[right];
                while (left < right && arr[left] <= temp) { left++; count++; }
                arr[right] = arr[left];
            }
            arr[left] = temp;
            return left;
        }
        static int RandSelect(int[] arr, int left, int right, int k) {
            if (left == right) {
                return arr[left];
            }
            int index = RandPartition(arr, left, right);
            int M = index + 1;
            if (M == k) {
                return arr[index];
            }
            int result = -1;
            if (M < k) {
                result = RandSelect(arr, index + 1, right, k);
            }
            else if (M > k) {
                result = RandSelect(arr, left, index - 1, k);
            }
            return result;
        }
7、已经有一个查询好友的接口，设计一个微信朋友圈，可以实现发表朋友圈，添加评论，查看评论等功能。主要是设计数据结构
（1）消息表（ 存储用户发布的信息，utf8m64 可以存表情包 ）
字段
类型
备注
id
bigint
自增主键
uid
varchar(20)
用户id
content
varchar(500)
内容
picture
varchar(200)
图片
location
varbinary(100)
位置
create_time
detetime
创建日期
（2）时间轴表（ 存储这所有有用时间轴的信息，用户拉取朋友圈是查的这张表，根据type判定是否是自己发的）
字段
类型
备注
id
bigInt(15)
自增主键
fcm_id
bigint
朋友圈信息id，消息表中的id
uid 
varchar(20)
用户id
type
tinyInt
0 表示自己的，1表示朋友发的
create_time
datetime
创建时间
（3） 评论表（记录评论和点赞数的）
字段
类型
备注
id
bigInt
自增主键
fcm_id
bigInt
朋友圈信息id,消息表中id
uid
varchar
用户id
content
varchar(200)
评论内容
like_count
int(10)
点赞数
create_time
datetime
时间
8、LRU算法实现
import java.util.HashMap;
public class LRU<K, V> {
    private int currentSize;//当前的大小
    private int capcity;//总容量
    private HashMap<K, Node> caches;//所有的node节点
    private Node first;//头节点
    private Node last;//尾节点
    public LRU(int size) {
        currentSize = 0;
        this.capcity = size;
        caches = new HashMap<K, Node>(size);
    }
    /**
     * 放入元素
     * @param key
     * @param value
     */
    public void put(K key, V value) {
        Node node = caches.get(key);
        //如果新元素
        if (node == null) {
            //如果超过元素容纳量
            if (caches.size() >= capcity) {
                //移除最后一个节点
                caches.remove(last.key);
                removeLast();
            }
            //创建新节点
            node = new Node(key,value);
        }
        //已经存在的元素覆盖旧值
        node.value = value;
        //把元素移动到首部
        moveToHead(node);
        caches.put(key, node);
    }
    /**
     * 通过key获取元素
     * @param key
     * @return
     */
    public Object get(K key) {
        Node node = caches.get(key);
        if (node == null) {
            return null;
        }
        //把访问的节点移动到首部
        moveToHead(node);
        return node.value;
    }
    /**
     * 根据key移除节点
     * @param key
     * @return
     */
    public Object remove(K key) {
        Node node = caches.get(key);
        if (node != null) {
            if (node.pre != null) {
                node.pre.next = node.next;
            }
            if (node.next != null) {
                node.next.pre = node.pre;
            }
            if (node == first) {
                first = node.next;
            }
            if (node == last) {
                last = node.pre;
            }
        }
        return caches.remove(key);
    }
    /**
     * 清除所有节点
     */
    public void clear() {
        first = null;
        last = null;
        caches.clear();
    }
    /**
     * 把当前节点移动到首部
     * @param node
     */
    private void moveToHead(Node node) {
        if (first == node) {
            return;
        }
        if (node.next != null) {
            node.next.pre = node.pre;
        }
        if (node.pre != null) {
            node.pre.next = node.next;
        }
        if (node == last) {
            last = last.pre;
        }
        if (first == null || last == null) {
            first = last = node;
            return;
        }
        node.next = first;
        first.pre = node;
        first = node;
        first.pre = null;
    }
    /**
     * 移除最后一个节点
     */
    private void removeLast() {
        if (last != null) {
            last = last.pre;
            if (last == null) {
                first = null;
            } else {
                last.next = null;
            }
        }
    }
    @Override
    public String toString() {
        StringBuilder sb = new StringBuilder();
        Node node = first;
        while (node != null) {
            sb.append(String.format("%s:%s ", node.key, node.value));
            node = node.next;
        }
        return sb.toString();
    }
     
    public static void main(String[] args) {
        LRU<Integer, String> lru = new LRU<Integer, String>(5);
        lru.put(1, "a");
        lru.put(2, "b");
        lru.put(3, "c");
        lru.put(4,"d");
        lru.put(5,"e");
        System.out.println("原始链表为:"+lru.toString());
        lru.get(4);
        System.out.println("获取key为4的元素之后的链表:"+lru.toString());
        lru.put(6,"f");
        System.out.println("新添加一个key为6之后的链表:"+lru.toString());
        lru.remove(3);
        System.out.println("移除key=3的之后的链表:"+lru.toString());
    }
}
9、手写一个栈实现Push、pop以及max，要求时间复杂度为O（1）
package com.my.test.datastructure.stack;
import java.util.Stack;
/*
* 实现一个栈 获取最大、最小值、pop()、push()都是O(1)复杂度
*/
public class MinMaxStack
{
    private Stack<Integer> stack = new Stack<>();
    private Stack<Integer> minStack = new Stack<>();
    private Stack<Integer> maxStack = new Stack<>();
    
    public void push(int value) {
        // 插入元素
        stack.push(value);
        
        // 第一次push元素直接插入 或者 小于等于栈顶元素，则插入最小栈
        if (minStack.empty() || minStack.peek() >= value) {
            minStack.push(value);
        }
        
        // 第一次push元素 或者 大于等于栈顶元素，则插入最大栈
        if (maxStack.empty() || maxStack.peek() <= value) {
            maxStack.push(value);
        }
    }
    
    public int pop() {
        if (stack.empty()) {
            System.out.println("stack is empty");
            throw new RuntimeException("stack is empty");
        }
        int popValue = stack.pop();
        // 元素为最大值或最小值则弹出
        if (popValue == minStack.peek()) {
            minStack.pop();
        }
        if (popValue == maxStack.peek()) {
            maxStack.pop();
        }
        return popValue;
    }
    
    public int getMin() {
        if (minStack.empty()) {
            throw new RuntimeException("min stack is empty");
        }
        return minStack.peek();
    }
    
    public int getMax() {
        if (maxStack.empty()) {
            throw new RuntimeException("max stack is empty");
        }
        return maxStack.peek();
    }
    
    public static void main(String args[]) {
        MinMaxStack stack = new MinMaxStack();
        stack.push(2);
        stack.push(3);
        stack.push(1);
        stack.push(3);
        stack.push(1);
        stack.push(4);
        stack.push(2);
        System.out.println(String.format("min: %s, max: %s", stack.getMin(), stack.getMax()));
        stack.pop();
        System.out.println(String.format("min: %s, max: %s", stack.getMin(), stack.getMax()));
        stack.pop();
        System.out.println(String.format("min: %s, max: %s", stack.getMin(), stack.getMax()));
        stack.pop();
        System.out.println(String.format("min: %s, max: %s", stack.getMin(), stack.getMax()));
        stack.pop();
        System.out.println(String.format("min: %s, max: %s", stack.getMin(), stack.getMax()));
    }
}
10、合并链表
/**
* @auther: lawt
* @date: 2018/11/4 08
* @Description: 结点信息
*/
public class Node {
    /**
     * 为了方便，这两个变量都使用public，而不用private就不需要编写get、set方法了。
     * 存放数据的变量，简单点，直接为int型
     */
    public int data;
    /**
     * 存放结点的变量,默认为null
     */
    public Node next;
    /**
     * 构造方法，在构造时就能够给data赋值
     */
    public Node(int data) {
        this.data = data;
    }
}
/**
* @auther: lawt
* @date: 2018/11/6 09
* @Description: 两个有序单链表合并
*/
public class MyList {
    /**
     * 递归方式合并两个单链表
     *
     * @param head1 有序链表1
     * @param head2 有序链表2
     * @return 合并后的链表
     */
    public static Node mergeTwoList(Node head1, Node head2) {
        //递归结束条件
        if (head1 == null && head2 == null) {
            return null;
        }
        if (head1 == null) {
            return head2;
        }
        if (head2 == null) {
            return head1;
        }
        //合并后的链表
        Node head = null;
        if (head1.data > head2.data) {
            //把head较小的结点给头结点
            head = head2;
            //继续递归head2
            head.next = mergeTwoList(head1, head2.next);
        } else {
            head = head1;
            head.next = mergeTwoList(head1.next, head2);
        }
        return head;
    }
    /**
     * 非递归方式
     *
     * @param head1 有序单链表1
     * @param head2 有序单链表2
     * @return 合并后的单链表
     */
    public static Node mergeTwoList2(Node head1, Node head2) {
        if (head1 == null || head2 == null) {
            return head1 != null ? head1 : head2;
        }
        //合并后单链表头结点
        Node head = head1.data < head2.data ? head1 : head2;
        Node cur1 = head == head1 ? head1 : head2;
        Node cur2 = head == head1 ? head2 : head1;
        Node pre = null;//cur1前一个元素
        Node next = null;//cur2的后一个元素
        while (cur1 != null && cur2 != null) {
            //第一次进来肯定走这里
            if (cur1.data <= cur2.data) {
                pre = cur1;
                cur1 = cur1.next;
            } else {
                next = cur2.next;
                pre.next = cur2;
                cur2.next = cur1;
                pre = cur2;
                cur2 = next;
            }
        }
        pre.next = cur1 == null ? cur2 : cur1;
        return head;
    }
    public static void main(String[] args) {
        Node node1 = new Node(1);
        Node node2 = new Node(2);
        Node node3 = new Node(3);
        Node node4 = new Node(4);
        Node node5 = new Node(5);
        node1.next = node3;
        node3.next = node5;
        node2.next = node4;
//        Node node = mergeTwoList(node1, node2);
        Node node = mergeTwoList2(node2, node1);
        while (node != null) {
            System.out.print(node.data + " ");
            node = node.next;
        }
    }
}
11、求二叉树深度

利用递归求解

class TreeNode {
    int val = 0;
    TreeNode left = null;
    TreeNode right = null;
    public TreeNode(int val) {
        this.val = val;
    }
}
public class Solution {
    public int TreeDepth(TreeNode root) {
        if(root==null){
            return 0;
        }
        int left=TreeDepth(root.left);
        int right=TreeDepth(root.right);
        return left>right?left+1:right+1;
    }
}

利用非递归求解：利用队列（Queue）进行层次遍历

import java.util.Queue;
import java.util.LinkedList;
class TreeNode {
    int val = 0;
    TreeNode left = null;
    TreeNode right = null;
    public TreeNode(int val) {
        this.val = val;
    }
}
public class Solution {
    public int TreeDepth(TreeNode root) {
        if(root==null){
            return 0;
        }
        int deep=0,count=0,nextCount=1;
        //Queue<TreeNode> queue=new Queue<TreeNode>();
        //Solution.java:17: error: Queue is abstract; cannot be instantiated
        Queue<TreeNode> queue=new LinkedList<TreeNode>();
        queue.add(root);
        while(!queue.isEmpty()){
            TreeNode p=queue.poll();
            count++;
            if(p.left!=null){
                queue.add(p.left);
            }
            if(p.right!=null){
                queue.add(p.right);
            }
            if(count==nextCount){
                nextCount=queue.size();
                count=0;
                deep++;
            }            
        }
        return deep;
    }
}
12、 两个栈实现队列
class CQueue {
    Stack<Integer> stack1;
    Stack<Integer> stack2;
    int size;
    public CQueue() {
        stack1 = new Stack<Integer>();
        stack2 = new Stack<Integer>();
        size = 0;
    }
     
    public void appendTail(int value) {
        while (!stack1.isEmpty()) {
            stack2.push(stack1.pop());
        }
        stack1.push(value);
        while (!stack2.isEmpty()) {
            stack1.push(stack2.pop());
        }
        size++;
    }
     
    public int deleteHead() {
        if (size == 0) {
            return -1;
        }
        size--;
        return stack1.pop();
    }
}
13、给定一个二叉树, 找到该树中两个指定节点的最近公共祖先。
  private TreeNode lca = null;
    public TreeNode lowestCommonAncestor(TreeNode root,TreeNode p,TreeNode q){
        if(root == null){
            return null;
        }
        findNode(root,p,q);
        return lca;
    }
    private boolean findNode(TreeNode root,TreeNode p,TreeNode q){
        if(root == null){
            return false;
        }
        int left = findNode(root.left,p,q)?1:0;
        int right = findNode(root.right,p,q)?1:0;
        int mid = (root == p || root == q)?1:0;
        if(left + right + mid >= 2){
            lca = root;
        }
        return (left + right + mid)>0;
    }
声明：本文内容由网友自发贡献，不代表【wpsshop博客】立场，版权归原作者所有，本站不承担相应法律责任。如您发现有侵权的内容，请联系我们。转载请注明出处：https://www.wpsshop.cn/w/小丑西瓜9/article/detail/693854
推荐阅读
相关标签

Copyright © 2003-2013 www.wpsshop.cn 版权所有，并保留所有权利。

  

闽ICP备14008679号