yeshaoting 写道
算法描述:
一个栈stack,具有push和pop操作,其时间复杂度皆为O(1)。
设计算法max操作,求栈中的最大值,该操作的时间复杂度也要求为O(1)。
可以修改栈的存储方式,push,pop的操作,但是要保证O(1)的时间复杂度,空间时间复杂度无要求。
思路:
我借助一个变量count和一个数组空间(其实就是一个栈)完成该时间复杂度为O(1)的算法设计。
这里面不需要用到快排吧。。那样的话还能叫o(1)?
贴上我的code:用了个最大栈保存添加路径上的最大值,删除的时候如果相等撤销最大值栈中的顶部元素即可。
另鄙视下,共享东西的时候都鼓掌叫好,求助发问就隐藏哦鄙视哦扣分哦臭鸡蛋烂白菜都来了。。。不多说了 果断以后文章只丢博客里
package sunfa;
import java.util.Arrays;
import java.util.Comparator;
import java.util.LinkedList;
import java.util.Random;
public class LinkedListMaxVal<E> {
public static void main(String[] args) {
LinkedListMaxVal<Integer> stack = new LinkedListMaxVal<Integer>(
new Comparator<Integer>() {
public int compare(Integer o1, Integer o2) {
return o1 - o2;
}
});
Random ran = new Random();
for (int i = 1; i <= 20; i++) {
stack.push(ran.nextInt(100));
System.out.println(stack + "," + stack.max()+","+stack.maxStack);
if (i % 4 == 0) {
Integer ee = stack.peek();
System.out.println("=============>pop:"+ee+"," + stack + "," + stack.max()+","+stack.maxStack);
stack.pop();
}
}
System.out.println("pop all>>>>>>>>>>>>>------------------");
System.out.println("删除的元素 | 数据栈 | 最大值 | 最大值栈");
while(!stack.isEmpty()){
Integer ee = stack.peek();
System.out.println("pop:" +ee+","+ stack + "," + stack.max()+","+stack.maxStack);
stack.pop();
}
System.out.println("---end-----");
System.out.println(stack);
}
private Object[] item;
private int count;//栈内元素数目 ,栈顶元素索引为count-1
private LinkedList<E> maxStack = new LinkedList<E>();//最大值备用栈,为省事借用链表
private final String EMPTY_STACK_STR = "空栈";
private Comparator<E> comp;
public LinkedListMaxVal(Comparator<E> c) {
item = new Object[10];
comp = c;
}
public void push(E e) {
if (e == null)
throw new NullPointerException();
if (count + 1 == item.length)
item = Arrays.copyOf(item, item.length << 1);
item[count++] = e;
if (count == 1)
maxStack.push(e);
else {
if (compare(maxStack.peekFirst(), e) <= 0)//=号不要丢了,这很关键
maxStack.push(e);
}
}
public E pop() {
if (isEmpty())
throw new NullPointerException(EMPTY_STACK_STR);
E e = peek();
item[count - 1] = null;
if (count == 1)
maxStack.pop();
else {
if (compare(maxStack.peekFirst(), e) == 0)
maxStack.pop();
}
count--;
return e;
}
public E max() {
if (maxStack.isEmpty())
throw new NullPointerException(EMPTY_STACK_STR);
return maxStack.peekFirst();
}
public E peek() {
if (isEmpty())
throw new NullPointerException(EMPTY_STACK_STR);
return (E) item[count - 1];
}
private int compare(E e1, E e2) {
return comp != null ? (((comp).compare(e1, e2)))
: (((Comparable<E>) e1).compareTo(e2));
}
public boolean isEmpty() {
return count == 0;
}
public String toString() {
String s = "[";
for (int i = 0; i < item.length; i++) {
if (item[i] != null)
s += item[i] + ",";
}
if (s.length() == 1) {
s += "]";
} else {
s = s.substring(0, s.length() - 1) + "]";
}
return s;
}
}
分享到:
相关推荐
实验题目: 基于栈的算术表达式求值算法 实验环境: 学习完了数据结构第三章内容栈和队列 实验目的: 1.掌握栈的定义及实现; 2.掌握利用栈求解算术表达式的方法。 实验内容: 通过修改完善教材中的算法...
数据结构与算法:栈队列的题库
利用模拟退火算法实现解决多元函数(一元函数)最优值问题(单目标问题),读者根据代码修改测试函数,不管是一元还是多元,都可以解决其最优话问题。
遗传算法求函数最大值和最小值matlab源码
用C++实现的遗传算法求函数的最大值,可运行
遗传算法(Genetic Algorithms,GA)是一种基于自然选择和自然遗传机制的搜索算法,它是一种有效的解决最优化问题的方法,属于一种进化算法。本实验要求采用简单遗传算法求解如下一元函数的最大值:
数据结构第二章上机作业,张宪超。 已知head为单链表的表头指针,链表中储存的都是整形数据,实现下列运算的递归算法: 1.求链表中最大值 2.求链表中的节点个数 3.求所有整数平均值
常见:百度微软等算法面试题及答案1
3.内容:基础遗传算法求二次函数最大值,在抛物线的定点显示GA优化解。 [objvalue]=calobjvalue(pop); %计算目标函数 fitvalue=calfitvalue(objvalue); %计算群体中每个个体的适应度 [newpop]=selection(pop,...
该资源主要是对于人工智能当中一个经典课题--遗传算法求解函数最大值,其中包含对于该算法的C#代码实例,并且可以直接在visual studio运行,有需要的欢迎下载!!
本文档是matlab遗传算法求最大值,网上很多资源不可以运行,这个可以运行
求解找到数组A[1..n]中元素的最大值和次最大值(本小题以数组元素的比较为标准操作)的算法,并分析其最坏情况的时间复杂度。
百度开发测试面试算法题汇总,希望对大家有所帮助
使用遗传算法求解函数最大值问题
该算法有助于初学者深入理解遗传算法,运用遗传算法求解最大值问题,求解TSP问题中的最短路径,问题中的求解的函数会在下一个帖子发布,如有问题可以询问QQ1846403892
MATLAB神经网络和优化算法:3.遗传算法求解最优解最大值.zip
1.通过修改完善课件案例 3.3 的算法,利用栈来实现算术表达式求值的算法。对算法中调 用的几个函数要给出其实现过程: (1) 函数 In(c):判断 c 是否为运算符; (2) 函数 Precede(t1,t2):判断运算符 t1 和 t2 的...
利用遗传算法求多元函数最大值的matlab算法
分治算法求n个数的数组中找出第二个最大元素
#运用python实现差分进化算法计算函数最大值 import random import math import numpy as np import random cr = 0.6 Population = np.random.rand(100,2) cycle = 500 hig , low = math.pi , 0 def eval(x): y =...