算法入门（二）

作者: 拨云见日aaa | 来源:发表于2019-09-29 07:01 被阅读0次

《算法竞赛入门经典第二版》习题2-5分数化小数问题
算法入门——冒泡排序、选择排序
学习路线规划
算法入门（二）
2022-01-16寒假第一周学习总结
经典排序算法总结
算法入门——堆排序
线性回归
《算法竞赛入门经典（第2版）算法艺术与信息学竞赛》PDF高清完
Kylin系列（二）—— Cube 构造算法

一、习题练习

（1）数组排序之后相邻的最大差值

题：给定一个整型数组arr,返回排序之后相邻的两个数最大差值
解题思路：这道题充分利用了桶的思想，这次的桶不是以数据的范围划分桶，而是以数据量划分，假如有N个数，那么就分N+1个桶，然后找出数据的的范围即最大值和最小值。把范围等分N+1份，比如范围1到9有五个桶那么一号桶为1-2范围，二号桶3-4范围。。。，一共N个数却有N+1个桶所以至少有一个桶为空的，空桶左边桶的最大值和右边桶最小值的差必然大于组内相减的差，那么证明了一件事，最大的差值必然不来自组内的差（注意并也不一定只来自空桶周围），所以最大的差值一定来自不相邻桶的差之一。
代码示例

public class MaxGap {
        public static int maxGap(int[] arr){
            
        if(arr==null||arr.length<2){
        return 0;
        }
        int length=arr.length;
        int max=arr[0];
        int min=arr[0];
        for(int i=1;i<arr.length;i++){
        max=Math.max(max,arr[i]);
        min=Math.min(min,arr[i]);
        }
        if(max==min){
        return 0;
        }
        int index=0;
        boolean[] isHave=new boolean[length+1];
        int[] maxbuk=new int[length+1];
        int[] minbuk=new int[length+1];
        for(int i=0;i<length;i++){
        index=getIndex(length,arr[i],max,min);
        maxbuk[index]=isHave[index]?Math.max(maxbuk[index],arr[i]):arr[i];
        minbuk[index]=isHave[index]?Math.min(minbuk[index],arr[i]):arr[i];
        isHave[index]=true;
        }
        int lastMax=maxbuk[0];
        int res=0;
        for(int j=1;j<length+1;j++){
        if(isHave[j]){
        res=Math.max(res,minbuk[j]-lastMax);
        lastMax=maxbuk[j];
        }
        }
        return res;
        }
        public static int getIndex(int length,int number,int max,int min){
        return (int)((number-min)*length/(max-min));
        }
        }

(2)用数组实现栈结构

题：用数组实现一个大小固定的栈
解题思路：设立一个index指针指向要加入数组的位置，数组为空时指向0位置，当入栈时先判断index是否等于了数组的长度如果等于告知栈已满，如不等将数据存入index指向的位置，index+1；出栈判断index是否为零，若为零告知栈为空，若不为零范围index-1的位置的数，且index-1。peek操作（只查看栈顶不出栈）依旧检查栈是否为空，不空返回index-1位置的数，index不变。
代码示例

public class MyStack{
    int[] stack;
int index=0;
public MyStack(int initSize){
    stack=new int[initSize];
}


public void push(int number){
if(index==stack.length){
    System.out.print("满了");
throw new RuntimeException("已经满了");
}
stack[index++]=number;
}
public int pop(){
if(index==0){
throw new RuntimeException("已经空了");
}
return stack[--index];
}
public int peek(){
if(index==0){
throw new RuntimeException("已经空了");
}
return stack[index-1];
}
}

(3)用数组实现队列结构

题：用数组实现一个固定长度的队列
解题思路：首先设置一个end指针告诉加入的数据放在哪，在设置一个start指针告诉数据应该从哪取，再设置一个size负责记录当时队列里有几个数，当数据放进来时，首先查看size是否等于数组大小的，若等于说明队列是满的，告知用户已满，若不等于把数据放入到end指着的位置，然后判断end+1是否等于数组的length，若等于让end=0；若不等让end+1。当取数据时先判断size是否等于零，为零告知用户队列为空，不为零返回start指的位置的数，判断start+1是否等于数组的length，若等于让start=0；若不等让end+1。peek时检查是否为空，不为空返回start指的位置的数，不再做任何操作。
代码示例

public class MyQueue {
    
        int start=0;
        int end=0;
        int size=0;
        int[] queue;
        public MyQueue(int initSize){
        queue=new int[initSize];
        }
        public void push(int num){
        if(size==queue.length){
        throw new RuntimeException("队列已满");
        }
        queue[end]=num;
        end=end+1==queue.length?0:end+1;
        size++;
        }
        public int pop(){
        if(size==0){
        throw new RuntimeException("队列是空的");
        }
        int res=queue[start];
        size--;
        start=start+1==queue.length?0:start+1;
        return res;
        }
        public int peek(){
        if(size==0){
        throw new RuntimeException("队列是空的");
        }
        return queue[start];
        }
        }

(4)实现一个特殊的栈，在实现栈的最基本功能的基础上，在实现返回栈中最小元素的功能

题：要求pop,push,getMin操作的时间复杂度都是O(1),设计的栈结构可以使用现成的栈
解题思路：创建两个栈，其中一个栈用来保存数据叫dataStack，另一个用来保存最小值叫minStack。dataStack正常入栈出栈。minStack有两种方式操作：

当入栈时如果minStack为空直接把数压进minStack里，如果不为空比较进来的数和minStack栈顶的数大小，如果进来的数小或等于压进栈minStack，如果大则不做任何操作。当出栈时，出栈的数和minStack栈顶的数比较大小，如果大minStack不做任何操作，如果等于minStack出栈。getmin方法就返回minStack栈顶的元素。这种方式比较省空间，但是出栈麻烦一些。
当入栈时，若minStack为空，则直接压进minStack中，若不为空，和栈顶的数比较大小，如果大于栈顶把minStack栈顶的数重复压一遍，若小于等于直接压入栈中。当出栈时，和dataStack同步出栈就可以了。getmin方法就返回minStack栈顶的元素。这种方法稍微浪费空间，但出栈简单。

代码示例
方案一

public class SpecialStack {
Stack<Integer> dataStack=new Stack<>();
Stack <Integer>minStack=new Stack<>();
public void push(int number) {
    dataStack.push(number);
    if(minStack.isEmpty()) {
        minStack.push(number);
    }else {
        int top=minStack.peek();
        if(number<=top) {
            minStack.push(number);
        }
    }
}
public int pop(){
    int popData=dataStack.pop();
    if(popData==minStack.peek()) {
        minStack.pop();
    }
    return popData;
}
public int getMin() {
    
    return minStack.peek();
}
}

方案二

public class SpecialStack2 {
Stack<Integer> dataStack=new Stack<>();
Stack <Integer>minStack=new Stack<>();
public void push(int number) {
    dataStack.push(number);
    if(minStack.isEmpty()) {
        minStack.push(number);
    }else {
        int top=minStack.peek();
        if(number<=top) {
            minStack.push(number);
        }else {
            minStack.push(top);
        }
    }
}
public int pop(){
    minStack.pop();
    return dataStack.pop();
}
public int getMin() {
    
    return minStack.peek();
}
}

(5)使用队列实现栈结构

题：使用队列实现栈结构
解题思路：准备两个队列queue1和queue2，进栈时把数据放入queue1中，当出栈时把queue1中的数放入queue2中，但是不是全放进去queue留一个数，而出栈就是出剩下的这个数，然后把两个队列的引用换一下。
代码示例

public class QueueToStack {
Queue<Integer> queue1;
Queue<Integer> queue2;
public QueueToStack() {
    queue1=new LinkedList<>();
    queue2=new LinkedList<>();
}
public void push(int number) {
    queue1.add(number);
}
public int pop() {
    if(queue1.isEmpty()) {
        throw new RuntimeException("栈已空");
    }
    while(queue1.size()!=1) {
        queue2.add(queue1.poll());
    }
    int res=queue1.poll();
    swap();
    return res;
}
public int peek() {
    if(queue1.isEmpty()) {
        throw new RuntimeException("栈已空");
    }
    while(queue1.size()!=1) {
        queue2.add(queue1.poll());
    }
    int res=queue1.poll();
    queue2.add(res);
    swap();
    return res;
}
public void swap() {
    Queue<Integer> temp;
    temp=queue1;
    queue1=queue2;
    queue2=temp;
}
}

（6）用栈实现队列

题：用栈结构实现队列结构
解题思路：创建两个栈stack1和stack2，进栈时往stack1进，出栈时把stack1里面的数倒进stack2里面，然后数从stack2里面出。倒数据需要满足两个条件，只要满足这两个条件什么时候倒数据都可以，条件是stack2不为空的时候不能倒，条件二是要是倒就要把stack1里面的数全部倒进stack2中。

-代码示例

public class StackToQueue {
Stack<Integer> stack1;
Stack<Integer> stack2;
public StackToQueue() {
    stack1=new Stack<>();
    stack2=new Stack<>();
}
public void add(int number) {
    stack1.push(number);
}
public int poll() {
    if(stack2.isEmpty()) {
        while(stack1.size()!=0) {
            stack2.push(stack1.pop());
        }
    }
    return stack2.pop();
}
public int peek() {
    if(stack2.isEmpty()) {
        while(stack1.size()!=0) {
            stack2.push(stack1.pop());
        }
    }
    return stack2.peek();
}
}

(7)猫狗队列问题

题：有dog，cat，pet类如下
class Pet{
private String type;
public Pet(String type) {
this.type=type;
}
public String getType() {
return type;
}
}
class Dog extends Pet{
public Dog() {
super("dog");
}
}
class Cat extends Pet{
public Cat() {
super("cat");
}
}

实现一种猫狗队列的结构，要求如下：
用户可以调用add方法将猫或狗的实例放入队列中
用户可以调用pollAll方法将队列中所有实例按照进队列的先后顺序依次弹出
用户可以调用pollDog方法将队列中的狗类按照进队列的先后顺序依次弹出
用户可以调用pollCat方法将队列中的猫类按照进队列的先后顺序依次弹出
用户可以调用isEmpty方法，检查队列中是否还有dog或者cat的实例存在
用户可以调用isDogEmpty方法，检查队列中是否还有dog的实例存在
用户可以调用isCatEmpty方法，检查队列中是否还有cat的实例存在

解题思路：将传进来的猫狗类重新封装成一个类，这个里面有一个属性用来记录猫狗实例的传进来的顺序，然后创建两个队列分别放猫的实例和狗的实例。当pollAll的时候，先比较猫和狗队列的第一个实例的顺序值大小谁小谁弹出。当pollDog的时候从dog队列中弹出，当pollCat的时候从cat队列中弹出。isEmpty检查两个队列是否都为空，都为空才为空，isDogEmpty和isCatEmapty分别检查狗的队列和猫的队列。
代码示例

猫狗封装类
class QueueEnter{
    private Pet pet;
    private int count;
    public QueueEnter(Pet pet,int count) {
        this.pet=pet;
        this.count=count;
    }
    public Pet getPet() {
        return pet;
    }
    public int getCount() {
        return count;
    }
}

猫狗队列

public class DogAndCatQueue {
int count=0;
Queue<QueueEnter> dogQueue;
Queue<QueueEnter> catQueue;
public DogAndCatQueue() {
    dogQueue=new LinkedList<>();
    catQueue=new LinkedList<>();
}
public void add(Pet pet) {
    if(pet.getType().equals("dog")){
        dogQueue.add(new QueueEnter(pet,count++));
    }else {
        catQueue.add(new QueueEnter(pet,count++));
    }
}
public Pet pollAll() {
    if(dogQueue.isEmpty()&&catQueue.isEmpty()) {
        throw new RuntimeException("队列已空");
    }
    if(dogQueue.isEmpty()) {
        return (Cat)catQueue.poll().getPet();
    }
    if(catQueue.isEmpty()) {
        return (Dog)dogQueue.poll().getPet();
    }
    int dogCount=dogQueue.peek().getCount();
    int catCount=catQueue.peek().getCount();
    if(dogCount<catCount) {
        return (Dog)dogQueue.poll().getPet();
    }else {
        return (Cat)catQueue.poll().getPet();
    }
}
public Pet pollDog() {
    if(dogQueue.isEmpty()) {
        throw new RuntimeException("队列中已没有dog实例");
    }
    return (Dog)dogQueue.poll().getPet();
}
public Pet pollCat() {
    if(catQueue.isEmpty()) {
        throw new RuntimeException("队列中已没有cat实例");
    }
    return (Cat)catQueue.poll().getPet();
}
public boolean isEmpty() {
    if(dogQueue.isEmpty()&&catQueue.isEmpty()) {
        return false;
    }else {
        return true;
    }
}
public boolean isDogEmpty() {
    return dogQueue.isEmpty();
}
public boolean isCatEmpty() {
    return catQueue.isEmpty();
}
public int size() {
    return dogQueue.size()+catQueue.size();
}
}

二、拓展

综合排序，当数据量大时，首先用归并或者快速排序，当递归到数量小于一定数量以后直接用插入排序排，选择归并还是快速排序看数据是否是基本类型，当是基本类型时用快速排序，因为快排不具备稳定但速度更快，而且基本类型也不需要稳定性，当是非基本类型时，用归并排序，归并排序稳定性高

《算法竞赛入门经典第二版》习题2-5分数化小数问题
这是大三阅读《算法竞赛入门经典第二版》时写的，当时是为了准备算法题：关于《算法竞赛入门经典第二版》习题2-5分数化...
算法入门——冒泡排序、选择排序
上篇文章学习了算法入门——顺序查找、二分查找，这篇文章我们学习算法入门——冒泡排序、选择排序。冒泡排序冒泡排序...
学习路线规划
目前有两本书，《算法竞赛入门经典》和《算法竞赛进阶指南》。根据书名应该先看《算法竞赛入门经典》（《算法竞赛入门经...
算法入门（二）
一、习题练习（1）数组排序之后相邻的最大差值题：给定一个整型数组arr,返回排序之后相邻的两个数最大差值解题...
2022-01-16寒假第一周学习总结
一、本周计划完成任务参加牛客网校内赛项目算法二、最终的结果&具体行动 leetcode算法算法入门 70...
经典排序算法总结
经典排序算法集锦冒泡法排序算法入门之冒泡排序排序算法入门之冒泡排序优化
算法入门——堆排序
上篇文章我们学习了算法入门——插入排序、快速排序，这篇文章我们学习算法入门——堆排序。堆堆是一种特殊的完全二叉...
线性回归
线性回归是机器学习算法的入门，通过该算法，管中窥豹，研究该算法的精髓之处。线性回归线性回归的损失函数为最小二乘...
《算法竞赛入门经典（第2版）算法艺术与信息学竞赛》PDF高清完
《算法竞赛入门经典（第2版）算法艺术与信息学竞赛》PDF高清完整版-免费下载《算法竞赛入门经典（第2版）算法...
Kylin系列（二）—— Cube 构造算法
总目录 Kylin系列（一）—— 入门Kylin系列（二）—— Cube 构造算法 [TOC] Kylin cub...