算法总结

简介: 猫狗队列 注意: 查找了一些网上的写法,发现很多样本再处理pollAll pollDog pollCat方法的时候,并不是如下边的要求弹出所有,原因不详,以我对文字的 敏感性来说,这种只弹出一个的方式是错误的,奈何很多公司的算法题 答案也是如此,所以暂且先这样处理,你完全可以添加一个循环将所有 元.

猫狗队列

注意:

查找了一些网上的写法,发现很多样本再处理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;
        }
    }

未完,待续...

相关文章
|
算法 C++ 计算机视觉
区域生长算法 C++实现
在比赛和项目中用opencv用多了,就会发现很多opencv没有实现的算法,其中一些还是十分常用,在教科书上经常出现的。作为一个弱鸡,有的简单的算法能够自己实现(比如本文所要讲的),有的写到一半就打出GG,有的直接就下不了手。
1935 0
|
27天前
|
存储 算法 C++
【算法】粘木棍问题(C/C++)
【算法】粘木棍问题(C/C++)
|
3月前
|
人工智能 算法 搜索推荐
什么是算法?一切皆算法
如果有人问我什么算法?我就一句话:算法就是对一类问题的最优求解路径。
|
11月前
|
传感器 人工智能 算法
图象处理算法(介绍)
图象处理算法(介绍)
|
算法
算法
一、算法 常见的图查找算法包括: 1. 深度优先搜索(DFS):从图中的一个节点开始,沿着一条路径一直深入直到无法再深入为止,然后回溯到上一个节点,继续深入其他路径,直到找到目标节点或遍历完所有节点。 2. 广度优先搜索(BFS):从图中的一个节点开始,先访问它的所有邻居节点,然后再依次访问邻居的邻居节点,直到找到目标节点或遍历完所有节点。 3. Dijkstra算法:用于在带权有向图中找到从一个节点到其他节点的最短路径。该算法通过不断更新节点的最短距离来逐步找到最短路径。 4. A*算法:类似于Dijkstra算法,但在计算最短路径时加入了启发式函数,用于估计目标节点的距离,从而加速搜索过程
392 0
|
算法 数据安全/隐私保护
《算法》世界 二
一.算法要素 1.数据对象的运算和操作:计算机可以执行的基本操作是以指令的形式描述的。一个计算机系统能执行的所有指令的集合,成为该计算机系统的指令系统。一个计算机的基本运算和操作有如下四类: 1.算术运算:加减乘除等运算 2.逻辑运算:或、且、非等运算 3.关系运算:大于、小于、等于、不等于等运算 4.数据传输:输入、输出、赋值等运算 2.算法的控制结构:一个算法的功能结构不仅取决于所选用的操作,而且还与各操作之间的执行顺序有关。
170 1
《算法》世界 二
推公式算法的实现
推公式算法的实现
推公式算法的实现
|
算法 Java C++
算法题0
第一题:判断数字 给定一个整数 n,请你统计其各位数字中 4 和 7 的出现次数。 如果 4 的出现次数加上 7 的出现次数恰好等于 4 或 7,则输出 YES,否则输出 NO。 例如,当 n=40047 时,4 出现了 2 次,7 出现了 1 次,2+1=3,既不是 4 也不是 7,因此,输出 NO;当 n=7747774 时,4 出现了 2 次,7 出现了 5 次,2+5=7,因此,输出 YES。
152 0
|
算法 C++
|
算法
插值查找算法
插值查找算法
222 0