算法的深入浅出--8.面试基础问题（1）

秒速五厘米 2021-11-22 06:24 252阅读 0赞

**目录**

1、求最大相邻差值

2、通过数组结构实现栈和队列

3、实现一个特殊的栈，在实现栈的基本功能和基础上，再实现返回栈中最小元素的操作。

4、通过栈实现队列，通过队列实现栈

5、猫狗队列

--------------------

面试基础问题

# 1、求最大相邻差值 #

给定一个数组，求如果排序之后，相邻两数的最大差值，要求时间复杂度O(N)，且要求不能非基于比较的排序。

coding

package cn.mxl.work.problem;
    
    import java.util.Arrays;
    
    public class MaxDistanceValue {
    
    	public static void main(String[] args) {
    		// TODO Auto-generated method stub
    
    	}
    	public static int maxGap(int[] nums) {
    		if(nums==null || nums.length<2) {
    			return 0;
    		}
    		int len=nums.length;
    		int min=Integer.MAX_VALUE;
    		int max=Integer.MIN_VALUE;
    		for(int i=0;i<len;i++) {
    			min=Math.min(min, nums[i]);
    			max=Math.max(max, nums[i]);
    		}
    		if(min==max) {
    			return 0;
    		}
    		boolean[] hasNum=new boolean[len+1];
    		int[] maxs=new int[len+1];
    		int[] mins=new int[len+1];
    		int bid=0;
    		for(int i=0;i<len;i++) {
    			bid=bucket(nums[i],len,min,max);
    			mins[bid]=hasNum[bid]?Math.min(mins[bid],nums[i]):nums[i];
    			maxs[bid]=hasNum[bid]?Math.max(maxs[bid],nums[i]):nums[i];
    			hasNum[bid]=true;
    		}
    		int res=0;
    		int lastMax=maxs[0];
    		int i=1;
    		for(;i<=len;i++) {
    			if(hasNum[i]) {
    				res=Math.max(res, mins[i]-lastMax);
    				lastMax=maxs[i];
    			}
    		}
    		return res;
    	}
    	
    	public static int bucket(long num,long len,long min,long max) {
    		return (int)((num-min)*len/(max-min));
    	}
    }

# 2、通过数组结构实现栈和队列 #

public class ArrayStackAndQueue {
    	public static class ArrayStack{
    		private Integer[] arr;
    		private Integer index;
    		
    		public ArrayStack(int initSize) {
    			if(initSize<0) {
    				throw new IllegalArgumentException("初始化大小不能小于0！");
    			}
    			arr=new Integer[initSize];
    			index=0;
    		}
    		
    		public Integer peek() {
    			if(index==0) {
    				return null;
    			}
    			return arr[index-1];
    		}
    		
    		public void push(int obj) {
    			if(index==arr.length) {
    				throw new ArrayIndexOutOfBoundsException("已经满了");
    			}
    			arr[index++]=obj;
    		}
    		
    		public Integer pop() {
    			if(index==0) {
    				throw new ArrayIndexOutOfBoundsException("栈是空的的");
    			}
    			return arr[--index];
    		}
    	}
    	
    	public static class ArrayQueue{
    		private Integer[] arr;
    		private Integer size;
    		private Integer start;
    		private Integer end;
    		 
    		public ArrayQueue(int initSize) {
    			if(initSize<0) {
    				throw new IllegalArgumentException("The init size is less than 0!");
    			}
    			arr=new Integer[initSize];
    			size=0;
    			start=0;
    			end=0;
    		}
    		public Integer peek() {
    			if(size==0) {
    				return null;
    			}
    			return arr[start];
    		}
    		public void push(int obj) {
    			if(size==arr.length) {
    				throw new ArrayIndexOutOfBoundsException("The queue is full");
    			}
    			size++;
    			arr[end]=obj;
    			end=end==arr.length-1?0:end+1;
    		}
    		
    		public Integer poll() {
    			if(size==0) {
    				throw new ArrayIndexOutOfBoundsException("The queue is empty");
    			}
    			size--;
    			int temp=start;
    			start=start==arr.length-1?0:start+1;
    			return arr[temp];
    		}
    	}
    }

# 3、实现一个特殊的栈，在实现栈的基本功能和基础上，再实现返回栈中最小元素的操作。 #

要求：

1、pop、push、getMin操作的时间复杂度都是O（1）。

2、设计的栈类型可以使用现成的栈结构。

package cn.mxl.work.problem;
    
    import java.util.Stack;
    
    public class GetMinStack {
    	public static void main(String[] args) {
    		
    	}
    	public static class MyStack{
    		private Stack<Integer> stackData;
    		private Stack<Integer> stackMin;
    		public MyStack() {
    			this.stackData=new Stack<Integer>();
    			this.stackMin=new Stack<Integer>();
    		}
    		
    		public void push(int newNum) {
    			if(this.stackMin.isEmpty()) {
    				this.stackMin.push(newNum);
    			}else if(newNum<this.getMin()) {
    				this.stackMin.push(newNum);
    			}else {
    				int newMin=this.stackMin.peek();
    				this.stackMin.push(newMin);
    			}
    			this.stackData.push(newNum);
    		}
    		private int getMin() {
    			// TODO Auto-generated method stub
    			if(this.stackMin.size()==0) {
    				throw new RuntimeException("Your stack is empty.");
    			}
    			return this.stackMin.peek();
    		}
    
    		public int pop() {
    			if(this.stackData.isEmpty()) {
    				throw new RuntimeException("Your stack is empty.");
    			}
    			this.stackMin.pop();
    			return this.stackData.pop();
    		}
    	}
    }

# 4、通过栈实现队列，通过队列实现栈 #

package cn.mxl.work.problem;
    
    import java.util.Stack;
    
    import javax.management.RuntimeErrorException;
    
    public class MyTwoStackQueue {
    	public static class TwoStackQueue{
    		private Stack<Integer> stackPush;
    		private Stack<Integer> stackPop;
    		public TwoStackQueue() {
    			stackPush=new Stack<Integer>();
    			stackPop=new Stack<Integer>();
    		}
    		public void push(int pushInt) {
    			stackPush.add(pushInt);
    		}
    		public int poll() {
    			if(stackPop.empty()&&stackPush.empty()) {
    				throw new RuntimeException("Queue is empty!");
    			}else if(stackPop.empty()) {
    				while(!stackPush.empty()) {
    					stackPop.push(stackPush.pop());
    				}
    			}
    			return stackPop.pop();
    		}
    		public int peek() {
    			if(stackPop.empty()&&stackPush.empty()) {
    				throw new RuntimeException("Queue is empty!");
    			}else if(stackPop.empty()) {
    				while(!stackPush.empty()) {
    					stackPop.push(stackPush.pop());
    				}
    			}
    			return stackPop.peek();
    		}
    	}
    }

package cn.mxl.work.problem;
    
    import java.util.LinkedList;
    import java.util.Queue;
    
    public class MyTwoQueueStack {
    	public static class TwoQueueStack{
    		private Queue<Integer> data;
    		private Queue<Integer> help;
    		public TwoQueueStack(){
    			data=new LinkedList<Integer>();
    			help=new LinkedList<Integer>();
    		}
    		public int peek() {
    			if(data.isEmpty()) {
    				throw new RuntimeException("Stack is empty!");
    			}
    			while(data.size()!=1) {
    				help.add(data.poll());
    			}
    			int res=data.poll();
    			help.add(res);
    			swap();
    			return res;
    		}
    		public int pop() {
    			if(data.isEmpty()) {
    				throw new RuntimeException("Stack is empty");
    			}
    			while(data.size()>1) {
    				help.add(data.poll());
    			}
    			int res=data.poll();
    			swap();
    			return res;
    		}
    		private void swap() {
    			Queue<Integer> tmp=help;
    			help=data;
    			data=tmp;
    		}
    	}
    }

# 5、猫狗队列 #

实现一种狗猫队列的结构，要求如下:  用户可以调用add方法将cat类或dog类的实例放入队列中;用户可 以调用polIA1l方法，将队列中所有的实例按照进队列的先后顺序依次弹出;用户可以调用po I IDog方法，将队列中dog类的实例按照进队列的先后顺序依次弹出;  用户可以调用po IICat方法，将队列中cat类的实例按照进队列的先后顺序依次弹出;  用户可以调用isEmpty方法，检查队列中是否还有dog或cat的实例;  用户可以调用i sDogEmpty方法，检查队列中是否有dog类的实例; :  用户可以调用isCatEmpty方法，检查队列中是否有cat类的实例。

package cn.mxl.work.problem;
    
    import java.util.LinkedList;
    import java.util.Queue;
    
    public class MyDogCatQueue {
    
    	public static class Pet {
    		private String type;
    
    		public Pet(String type) {
    			this.type = type;
    		}
    
    		public String getPetType() {
    			return this.type;
    		}
    	}
    
    	public static class Dog extends Pet {
    		public Dog() {
    			super("dog");
    		}
    	}
    
    	public static class Cat extends Pet {
    		public Cat() {
    			super("cat");
    		}
    	}
    
    	public static class PetEnterQueue {
    		private Pet pet;
    		private long count;
    
    		public PetEnterQueue(Pet pet, long count) {
    			this.pet = pet;
    			this.count = count;
    		}
    
    		public Pet getPet() {
    			return this.pet;
    		}
    
    		public long getCount() {
    			return this.count;
    		}
    
    		public String getEnterPetType() {
    			return this.pet.getPetType();
    		}
    	}
    
    	public static class DogCatQueue {
    		private Queue<PetEnterQueue> dogQ;
    		private Queue<PetEnterQueue> catQ;
    		private long count;
    
    		public DogCatQueue() {
    			this.dogQ = new LinkedList<PetEnterQueue>();
    			this.catQ = new LinkedList<PetEnterQueue>();
    			this.count = 0;
    		}
    
    		public void add(Pet pet) {
    			if (pet.getPetType().equals("dog")) {
    				this.dogQ.add(new PetEnterQueue(pet, this.count++));
    			} else if (pet.getPetType().equals("cat")) {
    				this.catQ.add(new PetEnterQueue(pet, this.count++));
    			} else {
    				throw new RuntimeException("err, not dog or cat");
    			}
    		}
    
    		public Pet pollAll() {
    			if (!this.dogQ.isEmpty() && !this.catQ.isEmpty()) {
    				if (this.dogQ.peek().getCount() < this.catQ.peek().getCount()) {
    					return this.dogQ.poll().getPet();
    				} else {
    					return this.catQ.poll().getPet();
    				}
    			} else if (!this.dogQ.isEmpty()) {
    				return this.dogQ.poll().getPet();
    			} else if (!this.catQ.isEmpty()) {
    				return this.catQ.poll().getPet();
    			} else {
    				throw new RuntimeException("err, queue is empty!");
    			}
    		}
    
    		public Dog pollDog() {
    			if (!this.isDogQueueEmpty()) {
    				return (Dog) this.dogQ.poll().getPet();
    			} else {
    				throw new RuntimeException("Dog queue is empty!");
    			}
    		}
    
    		public Cat pollCat() {
    			if (!this.isCatQueueEmpty()) {
    				return (Cat) this.catQ.poll().getPet();
    			} else
    				throw new RuntimeException("Cat queue is empty!");
    		}
    
    		public boolean isEmpty() {
    			return this.dogQ.isEmpty() && this.catQ.isEmpty();
    		}
    
    		public boolean isDogQueueEmpty() {
    			return this.dogQ.isEmpty();
    		}
    
    		public boolean isCatQueueEmpty() {
    			return this.catQ.isEmpty();
    		}
    
    	}
    
    	public static void main(String[] args) {
    		DogCatQueue test = new DogCatQueue();
    
    		Pet dog1 = new Dog();
    		Pet cat1 = new Cat();
    		Pet dog2 = new Dog();
    		Pet cat2 = new Cat();
    		Pet dog3 = new Dog();
    		Pet cat3 = new Cat();
    
    		test.add(dog1);
    		test.add(cat1);
    		test.add(dog2);
    		test.add(cat2);
    		test.add(dog3);
    		test.add(cat3);
    
    		test.add(dog1);
    		test.add(cat1);
    		test.add(dog2);
    		test.add(cat2);
    		test.add(dog3);
    		test.add(cat3);
    
    		test.add(dog1);
    		test.add(cat1);
    		test.add(dog2);
    		test.add(cat2);
    		test.add(dog3);
    		test.add(cat3);
    		while (!test.isDogQueueEmpty()) {
    			System.out.println(test.pollDog().getPetType());
    		}
    		while (!test.isEmpty()) {
    			System.out.println(test.pollAll().getPetType());
    		}
    	}
    
    }