20220422java算法笔试题-----栈、队列与哈希表

20220422java算法笔试题-----栈、队列与哈希表,第1张

1.如何实现栈

题目描述:

实现一个栈的数据结构,使其具有以下方法:压栈、d栈、取栈顶元素、判断栈是否为空以及获取栈中元素个数。

//利用数组
class MyStack{
    private ArrayList arr;
    private int stackSize;

    public MyStack() {
        stackSize=0;
        arr=new ArrayList();
    }
    //判断是否为空
    boolean isEmpty(){
        return stackSize==0;
    }
    //返回栈的大小
    int size(){
        return stackSize;
    }
    //返回栈顶元素
    T top(){
        if(isEmpty()){
            return null;
        }
        return arr.get(stackSize-1);
    }
    //d栈
    T pop(){
        if(stackSize>0){
            return arr.get(--stackSize);
        }else{
            System.out.println("栈已经为空");
            return null;
        }
    }
    //压栈
    void push(T item){
        arr.add(item);
        stackSize++;
    }
}
public class ConStack {
    public static void main(String[] args) {
        MyStack stack=new MyStack<>();
        stack.push(1);
        System.out.println("栈顶元素为:"+stack.top());
        System.out.println("栈大小为:"+stack.size());
        stack.pop();
        System.out.println("d栈成功");
        stack.pop();
    }
}
//链表法
class LNode{
    T data;
    LNode next;
}
class myStack{
    private LNode pHead;
    public myStack(){
        pHead =new LNode();
        pHead.data=null;
        pHead.next=null;
    }
    //判断栈是否为空
    boolean empty(){
        return pHead==null;
    }
    //获取栈中的元素个数
    int size(){
        int size=0;
        LNode p=pHead.next;
        while (p!=null){
            p=p.next;
            size++;
        }
        return size;
    }
    //入栈,把e放到栈顶
    void push(T e){
        LNode  p=new LNode<>();
        p.data=e;
        p.next=pHead.next;
        pHead.next=p;
    }
    //出栈,同时返回栈顶元素
    T pop(){
        LNode  tmp=pHead.next;
        if(tmp!=null){
            pHead.next=tmp.next;
            return tmp.data;
        }
        System.out.println("栈已经为空");
        return  null;
    }
    //获取栈顶元素
    T top(){
        if(pHead.next!=null){
            return pHead.next.data;

        }
        System.out.println("栈已经为空");
        return null;
    }

}
public class ListTest {
    public static void main(String[] args) {
        myStack stack=new myStack<>();
        stack.push(1);
        System.out.println("栈顶元素为:"+stack.pop());
        System.out.println("栈大小为:"+stack.size());
        stack.pop();
        System.out.println("d栈成功");
        stack.pop();

    }

}
2.如何实现队列

题目描述:

实现一个队列的数据结构,使其具有入队列、出队列、查看队列首尾元素、查看队列大小等功能。
 

import java.util.ArrayList;

class MyQueue{
    private ArrayList arr=new ArrayList<>();
    private  int front;//队列头
    private  int rear;//队列尾
    public MyQueue(){
        front=0;
        rear=0;
    }
    //判断队列是否为空
    public  boolean isEmpty(){
        return  front==rear;
    }
    //返回队列的大小
    public int size(){
        return rear-front;
    }
    //返回队列首元素
    public T getFront(){
        if(isEmpty()){
            return null;
        }
        return arr.get(front);
    }
    //返回队列尾元素
    public T getRear(){
        if(isEmpty()){
            return null;
        }
        return arr.get(rear-1);
    }
    //删除队列头元素
    public void deleteQueue(){
        if(rear>front){
            front++;
        }else {
            System.out.println("队列已经为空");
        }
    }
    //把新元素加入队列尾
    public void joinQueue(T item){
        arr.add(item);
        rear++;
    }
}

public class ArrayQueue {
    public static void main(String[] args) {
        MyQueue queue =new MyQueue<>();
        queue.joinQueue(1);
        queue.joinQueue(2);
        queue.joinQueue(3);
        System.out.println("队列头元素为:"+queue.getFront());
        System.out.println("队列尾元素为:"+queue.getRear());
        System.out.println("队列大小为:"+queue.size());
    }
}
//利用链表实现队列
class LNode{
    T data;
    LNode next;
}
class MyQueue{
    private LNodepHead;
    private LNode pEnd;
    //分配头结点
    public  MyQueue(){
        pEnd=pHead=null;
    }
    //判断队列是否为空
    boolean empty(){
        if(pHead==null){
            return true;
        }else {
            return false;
        }
    }
    //元素个数
    int size(){
        int size=0;
        LNodep=pHead;
        while (p!=null){
            p=p.next;
            size++;
        }
        return size;
    }
    //添加列尾
    void enQueue(T e){
        LNode p=new LNode<>();
        p.data=e;
        p.next=null;
        if(pHead==null){
            pHead=pEnd=p;
        }else {
            pEnd.next=p;
            pEnd=p;
        }
    }
    //删除队列元素
    void deQueue(){
        if(pHead==null)
            System.out.println("出队列失败,队列已经为空");
            pHead=pHead.next;
            if(pHead==null)
                pEnd=null;
        }
        //获取队列首位元素
    T getFront(){
        if(pHead==null){
            System.out.println("获取队列首元素失败,队列已经为空");
            return null;
        }
        return pHead.data;
    }
    //队列尾元素
    T getBack(){
        if(pEnd==null){
            System.out.println("获取队列尾元素失败,队列已经为空");
            return null;
        }
        return pEnd.data;
    }
}

public class QueueList {
    public static void main(String[] args) {
        MyQueue queue=new MyQueue<>();
        queue.enQueue(1);
        queue.enQueue(2);
        System.out.println("队列头元素为:"+queue.getFront());
        System.out.println("队列尾元素为:"+queue.getBack());
        System.out.println("队列大小为:"+queue.size());
    }
}
3.如何设计一个排序系统

题目描述:

设计一个排队系统,能够让每个进入队的用户都能看到自己在队列中所处的位置和变化,队可能随时有人加入和退出;当有人退出影响到用户的位置排名时需要及时反馈到用户。

package queue;

import java.util.LinkedList;
import java.util.Objects;
import java.util.Queue;
/*1、offer()和add()的区别
add()和offer()都是向队列中添加一个元素。但是如果想在一个满的队列中加入一个新元素,调用 add() 方法就会抛出一个 unchecked 异常,而调用 offer() 方法会返回 false。可以据此在程序中进行有效的判断!

2、peek()和element()的区别
peek()和element()都将在不移除的情况下返回队头,但是peek()方法在队列为空时返回null,调用element()方法会抛出NoSuchElementException异常。

3、poll()和remove()的区别
poll()和remove()都将移除并且返回对头,但是在poll()在队列为空时返回null,而remove()会抛出NoSuchElementException异常。
*/

/**
 * @author 龙御修
 */
class User {
    private int id;
    private String name;
    private int seq;

    public User(int id, String name) {
        this.id = id;
        this.name = name;
        this.seq = seq;
    }

    public int getId() {
        return id;
    }

    public void setId(int id) {
        this.id = id;
    }

    public String getName() {
        return name;
    }

    public void setName(String name) {
        this.name = name;
    }

    public int getSeq() {
        return seq;
    }

    public void setSeq(int seq) {
        this.seq = seq;
    }


    @Override
    public boolean equals(Object o) {
        if (this == o) {
            return true;
        }
        if (o == null || getClass() != o.getClass()) {
            return false;
        }
        User user = (User) o;
        return id == user.id && seq == user.seq && Objects.equals(name, user.name);
    }

    @Override
    public int hashCode() {
        return Objects.hash(id, name, seq);
    }

    @Override
    public String toString() {
        return "User{" +
                "id=" + id +
                ", name='" + name + '\'' +
                ", seq=" + seq +
                '}';
    }

}

class MyQueue {
    private Queue q = new LinkedList<>();

    //进入队列尾部
    public void enQueue(User u) {
        u.setSeq(q.size() + 1);
        q.add(u);
    }
    //对头 出队列

   void deQueue() {
        q.poll();
        updataSep();
    }

    //队列中的人随机离开
    void deQueue(User u) {
        q.remove(u);
        updataSep();
    }

    //出列后更新队列中每个人的序列
    void updataSep() {
        int i = 1;
        for (User u : q) {
            u.setSeq(i++);
        }
    }

    //打印队列的信息
    void printList() {
        for (User u : q) {
            System.out.println(q);
        }
    }
}

public class SoftSystem {
    public static void main(String[] args) {
        User u1=new User(1,"User1");
        User u2=new User(2,"User2");
        User u3=new User(3,"User3");
        User u4=new User(4,"User4");

        MyQueue queue=new MyQueue();
         //存入队列
        queue.enQueue(u1);
        queue.enQueue(u2);
        queue.enQueue(u3);
        queue.enQueue(u4);
        //删除队列头和队列u3
        queue.printList();
        queue.deQueue();
        queue.deQueue(u3);
        queue.printList();
    }


}
4.如何实现LRU缓存方案 

题目描述:

LRU是Least Recently Used 的缩写,它的意思是“最近最少使用”。LRU缓存就是使用这种原理实现,简单地说,就是缓存一定量的数据,当超过设定的阈值时就把一些过期的数据删除掉。常用于页面置换算法,是为虚拟页式存储管理中常用的算法。如何实现LRU缓存方案? 

package queue;

import java.util.ArrayDeque;
import java.util.HashSet;

/**
 * @author tarena
 */
public class Test1 {
    public static void main(String[] args) {
        /*设置缓存大小*/
        LRU lru = new LRU(3);
        /*访问page*/
        lru.accessPage(1);
        lru.accessPage(2);


        lru.accessPage(5);
        lru.accessPage(1);
        lru.accessPage(6);
        lru.accessPage(7);
        /*通过上面的访问序列后,缓存的信息为*/
        lru.printQueue();


    }


}

class LRU {
    private int cacheSize;
    private ArrayDeque queue = new ArrayDeque<>();//双向链
    private HashSet hashSet = new HashSet<>();//哈希表

    public LRU(int cacheSize) {
        this.cacheSize = cacheSize;
    }

    /*判断缓存队列是否已满*/
    private boolean isQueueFull() {
        return queue.size() == cacheSize;
    }

    /*把页号为PageNum的也缓存到队列中,同时也添加都Hash表中*/
    private void enqueue(int pageNum) {
        /*如果队列满了,需要删除队尾的缓存的页*/
        if (isQueueFull()) {
            hashSet.remove(queue.getLast());
            queue.pollLast();
        }
        queue.addFirst(pageNum);
    }

    /*当访问某一个page的时候会调用这个函数,对于访问的page有两种情况:
     * 1.如果page在缓存队列中,直接把这个结点移动到队首
     * 2.如果page不在缓存队列中,把这个page缓存到队首*/
    public void accessPage(int pageNum) {
        /*page不在缓存队列中,把它缓存到队首*/
        if (!hashSet.contains(pageNum)) {
            enqueue(pageNum);
            /*page已经在缓存队列中了,移动到队首*/
        } else if (pageNum != queue.getFirst()) {
            queue.remove(pageNum);
            queue.addFirst(pageNum);
        }
    }

    public void printQueue() {
        while (!queue.isEmpty()) {
            System.out.print(queue.pop() + "");
        }
    }
}
5.如何从数组中找出满足a+b=c+d的两个数对

题目描述:

给定一个数组,找出数组中是否有两个数对(a, b)和(c, d),使得a+b=c+d,其中a、b、c和d是不同的元素。如果有多个答案,打印任意一个即可。例如,给定数组:{3, 4, 7, 10, 20, 9, 8},可以找到两个数对(3, 8)和(4, 7),使得3+8=4+7。
 

补充:拓扑排序是对一个有向图构造拓扑序列,解决工程是否能顺利进行的问题。构造时有 2 种结果:

  1. 此图全部顶点被输出:说明说明图中无「环」存在, 是 AOV 网

  2. 没有输出全部顶点:说明图中有「环」存在,不是 AOV 网

import java.util.HashMap;

/**
 * @author 龙御修
 * @create 2022-05-01 16:23
 */
public class ArrayElements {
    boolean findPairs(int arr[]){
        /*键为数对和和,值为数对*/
        HashMap sumPair=new HashMap<>();
        int n= arr.length;
        /*遍历数组中所有可能的数对*/
        for(int i=0;i

欢迎分享,转载请注明来源:内存溢出

原文地址: http://outofmemory.cn/langs/797073.html

(0)
打赏 微信扫一扫 微信扫一扫 支付宝扫一扫 支付宝扫一扫
上一篇 2022-05-06
下一篇 2022-05-06

发表评论

登录后才能评论

评论列表(0条)