猫狗队列
注意：
查找了一些网上的写法，发现很多样本再处理pollAll pollDog pollCat方法的时候，并不是如下边的要求弹出所有，原因不详，以我对文字的
敏感性来说，这种只弹出一个的方式是错误的，奈何很多公司的算法题
答案也是如此，所以暂且先这样处理，你完全可以添加一个循环将所有
元素弹出
实现一种猫狗队列的结构，要求如下：
用户可以调用add方法将cat类或者dog类的实例放入队列中；
用户可以调用pollAll方法，将队列中所有的实例按照队列的先后顺序依次弹出；
用户可以调用pollDog方法，将队列中dog类的实例按照队列的先后顺序依次弹出；
用户可以调用pollCat方法，将队列中cat类的实例按照队列的先后顺序依次弹出；
用户可以调用isEmpty方法，检查队列中是否还有dog和cat的实例；
用户可以调用isDogEmpty方法，检查队列中是否还有do的实例；
用户可以调用isCatEmpty方法，检查队列中是否还有cat的实例。
public class CatDogQueue {
private LinkedList<PetHolder> dogs;
private LinkedList<PetHolder> cats;
private int order;
public CatDogQueue() {
dogs = new LinkedList<>();
cats = new LinkedList<>();
order = 0;
}
public void add(Pet pet) {
if ("cat".equals(pet.getPetType())) {
cats.add(new PetHolder(pet, order++));
} else if ("dog".equals(pet.getPetType())) {
dogs.add(new PetHolder(pet, order++));
}
}
public void pollAll() {
if (!dogs.isEmpty() && !cats.isEmpty()) {
if (dogs.peek().getOrder() < cats.peek().getOrder()) {
dogs.poll();
} else {
cats.poll();
}
} else if (!dogs.isEmpty()) {
dogs.poll();
} else if (!cats.isEmpty()) {
cats.poll();
}
}
public Dog pollDog() {
if (!dogs.isEmpty()) {
return (Dog) dogs.poll().getPet();
}
return null;
}
public Cat pollCat() {
if (!cats.isEmpty()) {
return (Cat) cats.poll().getPet();
}
return null;
}
public boolean isEmpty() {
return dogs.isEmpty() && cats.isEmpty();
}
public boolean isCatsEmpty() {
return cats.isEmpty();
}
public boolean isDogsEmpty() {
return dogs.isEmpty();
}
}
class Pet {
private String type;
public Pet(String type) {
this.type = type;
}
public String getPetType() {
return this.type;
}
}
class PetHolder {
private Pet pet;
private long order;
public PetHolder(Pet pet, long order) {
this.pet = pet;
this.order = order;
}
public Pet getPet() {
return this.pet;
}
public long getOrder() {
return this.order;
}
public String getEnterPetType() {
return this.pet.getPetType();
}
}
class Cat extends Pet {
public Cat() {
super("cat");
}
}
class Dog extends Pet {
public Dog() {
super("dog");
}
}用两个栈实现队列，支持队列的基本操作(add,poll, peek)
简单分析：
1.先进先出，那么两个栈结合刚好满足这一点
2.两个栈顺序操作，全部添加到第一个栈之后，当要开始出的时候再往第二个栈中添加，从而保证先进先出的特性
public class QueueMadeOfStack {
private Stack<Integer> pushStack;
private Stack<Integer> popStack;
public QueueMadeOfStack() {
pushStack = new Stack<Integer>();
popStack = new Stack<Integer>();
}
public void add(int value) {
pushStack.push(value);
}
public int poll() {
if(popStack.empty() && pushStack.empty()) {
throw new RuntimeException("queue is empty");
}else if(popStack.empty()) {
while(!pushStack.empty()) {
popStack.push(pushStack.pop());
}
}
return popStack.pop();
}
public int peek() {
if(popStack.empty() && pushStack.empty()) {
throw new RuntimeException("queue is empty");
}else if(popStack.empty()) {
while(!pushStack.empty()) {
popStack.push(pushStack.pop());
}
}
return popStack.peek();
}
}
设计一个有获取最小值功能的栈，支持栈的基本功能，额外郑家一个getMin方法，要求pop,push,getMin时间复杂度为O(1)。可以使用现成的栈结构
简单分析：需要满足的要求大概如下：
1.先进后出
2.未进数据之前，为空，出完数据之后为空，所以如下实现中，pop使要保证两个stack都要pop干净
public class StackGetMin {
Stack<Integer> stack = null;
Stack<Integer> stackMin = null;
public StackGetMin(){
stack = new Stack<Integer>();
stackMin = new Stack<Integer>();
}
public int size(){
return stack.size();
}
public int pop(){
if(!stackMin.empty()){
stackMin.pop();
}
if(!stack.empty()){
return stack.pop();
}
return 0;
}
public void push(int i){
stack.push(i);
if(stackMin.empty()){
stackMin.push(i);
}else{
int temp = stackMin.peek();
if(i < temp){
stackMin.push(i);
}
}
}
public int getMin(){
if(!stackMin.empty()){
return stackMin.peek();
}
return 0;
}
}
快速排序
通过一趟排序将要排序的数据分割成独立的两部分，其中一部分的所有数据都比另外一部分的所有数据都要小，然后再按此方法对这两部分数据分别进行快速排序，整个排序过程可以递归进行，以此达到整个数据变成有序序列。快速排序 的平均时间复杂度为O(NlogN),是冒泡排序的一种改进版。
注意，最外层的判断必不可少
public static void sortAgain(int [] s,int a,int b) {
if(a <b) {
int low = a;
int high = b;
int key = s[a];
while(low < high) {
while(low < high && s[high] >= key) {
high --;
}
if(low < high) {
s[low++] = s[high];
}
while(low < high && s[low] < key) {
low++;
}
if(low < high) {
s[high--] = s[low];
}
}
s[low] = key;
sortAgain(s, a, low-1);
sortAgain(s, low+1, b);
}
}冒泡排序
冒泡排序重复地走访过要排序的数列，一次比较两个元素，如果它们的顺序错误就把它们交换过来。走访数列的工作是重复地进行直到没有再需要交换，也就是说该数列已经排序完成。这个算法的名字由来是因为越小的元素会经由交换慢慢“浮”到数列的顶端。
1.比较相邻的元素。如果第一个比第二个大，就交换它们两个；
2.对每一对相邻元素作同样的工作，从开始第一对到结尾的最后一对，这样在最后的元素应该会是最大的数；
3.针对所有的元素重复以上的步骤，除了最后一个；
4.重复步骤1~3，直到排序完成。
public static void bubble(int [] s) {
for(int i = 0 ; i < s.length - 1;i++) {
for(int j = 0;j<s.length -1 -i;j++) {
if(s[j] > s[j+1]) {
int temp = s[j];
s[j] = s[j+1];
s[j+1]=temp;
}
}
}
}选择排序
原理：首先在未排序序列中找到最小（大）元素，存放到排序序列的起始位置，然后，再从剩余未排序元素中继续寻找最小（大）元素，然后放到已排序序列的末尾。以此类推，直到所有元素均排序完毕。
public static void change(int [] arr) {
for(int i = 0 ; i < arr.length;i++) {
int minIndex = i;
for(int j = i+1; j < arr.length;j++) {
if(arr[j] < arr[minIndex]) {
minIndex = j;
}
}
int temp = arr[i];
arr[i] = arr[minIndex];
arr[minIndex] = temp;
}
}未完，待续...
