精华内容
下载资源
问答
  • 问题描述: n不相同元素顺序输入到 一个栈, 可以里的元素可在任意时刻出栈. 求出栈的可能序列.  这是一填空题, 求出当N等于5的情况的可能序列. 很容易可以得到N等于2,3,4 时的序列为 2,5,14. 这可...

    问题描述: n个不相同元素顺序输入到 一个栈, 栈可以里的元素可在任意时刻出栈. 求出栈的可能序列数. 


    这是一个填空题, 求出当N等于5的情况的可能序列数. 很容易可以得到N等于2,3,4 时的序列数为 2,5,14. 这可通过在已有序列的基础上添加下一元素的可能性来寻找规律. 

    当N为2时, 序列为 2,1 及 1,2. 当N为3时, 3可从2的序列中的最后插入, 第二个位置插入. 以及出现在2,1的前面. 如下图:



    由此可得 当N为3时, 可能插入的位置为5, 即出栈序列的可能数 为 5. 再来看看当n为4时:



    一共有14个位置可以插入. 共同的地方是最前只能插入一个, 最后及倒数第二个位置全都可以进行插入. 以及倒序输出的那个行的任意位置都可以进入插入. 此时, 输出的可能序列增加到了 14个. 那么当n为5 时, 可能输出的序列是多少个呢? 好吧, 我没找出规律来, 求解答. 

    当然, 这个问题可以解决, 那就依靠我们强大的计算机吧. 

    ruby代码如下:

    a = [] #用来存放输出到栈中的数的
    for i in 1 .. ARGV[0].to_i 
    	a[i-1] = i
    end
    stack = []
    printarray = [] #栈中输出先放至这个数组中, 满了就存放到vav中
    vav = Array.new(){[]} #此也就是数组的数组, 存放合法的输出序列
    
    def find(ith, stack, printarray, a, stack_push, vav)
    	stack = Array.new stack
    	printarray = Array.new printarray
    	if ith == ARGV[0].to_i #若顺序输出完毕, 则栈中全部出栈, 存入打印数组中
    		while !stack.empty?
    			printarray.push stack.pop
    		end
    		vav.push printarray
    	else
    		if stack_push 
    			stack.push a[ith]
    			find(ith+1, stack, printarray, a, true, vav)
    			find(ith+1, stack, printarray, a, false, vav)
    		elsif !stack.empty?
    			printarray.push stack.pop
    			find(ith, stack, printarray, a, true, vav)
    			find(ith, stack, printarray, a, false, vav)
    		end
    	end
    end
    
    find(0, stack, printarray, a, true, vav)
    vav.uniq! #除去vav中的重复序列
    vav.each{|i|
    	p i
    }
    p vav.size


    现在让我们来看来结果是什么, 首先先试一下  n 为3, 及 n 为 4 时. 如下:


    结果是正确的, n 为5,6,7 时结果分别为: 42 , 132, 429.

    详细的看一下wiki百科: 卡塔兰数


    展开全文
  • 队列有从1到7(由小到大排列)的7整数,问经过一整数后,出栈的所有排列有多少? 如果整数的容量是4(最多能容纳4整数),那么出栈的排列又是多少? 问题1代码 public class Catalan { ...

    问题

    1. 队列中有从1到7(由小到大排列)的7个整数,问经过一个整数栈后,出栈的所有排列数有多少?
    2. 如果整数栈的容量是4(栈最多能容纳4个整数),那么出栈的排列数又是多少?

    问题1代码

    
    public class Catalan {
    
        public static int answers = 0;
        int maxStackSize = 4; //栈最大容量
    
        public static void go(int deq, int sta) {
            if(deq>0) {
                go(deq-1, sta+1);
            }
            if(sta>0) {
                go(deq, sta-1);
            }
            if(deq==0&&sta==0) {
                answers++;
            }
        }
    
        public static void main(String[] args) {
            Deque from = new Deque();
            Deque to = new Deque();
            Stack s = new Stack();
            for(int i=1;i<=7;i++) {
                from.addLast(i);
            }
            go(7, 0);
            System.out.println(answers);
        }
    }
    

    问题2代码

    
    public class Catalan {
    
        public static int answers = 0;
        int maxStackSize = 4;
    
        public static void go(int deq, int sta) {
            if(deq>0 &&sta<maxStackSize) {  //仅此行比问题1多了一个限制
                go(deq-1, sta+1);
            }
            if(sta>0) {
                go(deq, sta-1);
            }
            if(deq==0&&sta==0) {
                answers++;
            }
        }
    
        public static void main(String[] args) {
            Deque from = new Deque();
            Deque to = new Deque();
            Stack s = new Stack();
            for(int i=1;i<=7;i++) {
                from.addLast(i);
            }
            go(7, 0);
            System.out.println(answers);
        }
    }
    
    展开全文
  • 算法-的出栈个数

    千次阅读 2018-03-18 09:12:13
    import java.math.BigInteger... n个元素的出栈次序 f(n)=f(0)*f(n-1)+f(1)*f(n-2)...+f(n-2)*f(1)+f(n-1)*f(0) 输出样例: 0:1 1:1 2:2 3:5 4:14 5:42 6:132 7:429 8:1430 9:4862 10:16796 11:58786 12:208012 13:742
    import java.math.BigInteger;
    
    /**
    问题描述:
    	n个元素的出栈次序
    	f(n)=f(0)*f(n-1)+f(1)*f(n-2)...+f(n-2)*f(1)+f(n-1)*f(0)
    输出样例:
    0:1
    1:1
    2:2
    3:5
    4:14
    5:42
    6:132
    7:429
    8:1430
    9:4862
    10:16796
    11:58786
    12:208012
    13:742900
    14:2674440
    15:9694845
    16:35357670
    17:129644790
    18:477638700
    19:1767263190
    20:6564120420
    
     * @author Vivinia
     */
    public class StackNum {
    	static BigInteger[] num=new BigInteger[101];         //使用数组存储之前计算过的数据
    	public static void main(String[] args) {
    		for(int i=0;i<=100;i++)         
    			num[i]=BigInteger.valueOf(0);           //先全部赋值为0
    		num[0]=BigInteger.valueOf(1);             
    		for(int i=0;i<=100;i++)
    			System.out.println(i+":"+f(i));
    	}
    
    	private static BigInteger f(int n) {
    		BigInteger total=BigInteger.valueOf(0);
    		if(n==0)
    			return num[0];        //0是退出递归的边界条件
    		if(num[n]!=BigInteger.valueOf(0))
    			return num[n];        //判断以前是否计算过数据,如果计算过数据直接从数组中取出,不用再次计算
    		for(int i=0;i<n;i++)
    			total=total.add((f(i).multiply(f(n-i-1))));   //循环累加每次成绩
    		num[n]=total;        //将该次数据存储起来
    		return total;
    	}
    
    }
    


    需要注意的地方:

    1.首先找到通用公式 f(n)=f(0)*f(n-1)+f(1)*f(n-2)...+f(n-2)*f(1)+f(n-1)*f(0),嗯,我从网上查的。。。

    2.核心代码就是递归中的for循环语句,外加退出递归的return 1,但是如果只这样递归,在n为16时就明显感觉时间变慢,大约接近一秒钟,然后往后时间为指数增长,到20就已经超过人的耐心等待时间了,这是因为每次计算一个数,都把前边的数据重新算了一遍,做了很多无用功,所以定义一个数组把每次计算的数据存储起来,以后先查询数组,数组没有存储再计算;

    3.虽然网上搜着long型数据很大,但是如果用long到n=20时就溢出了,所以改用BigInteger型,现在测试到100输出都没问题,而且时间很快,只不过就是不知道数据的数据对不对,反正很大。。。

    展开全文
  • 单调

    万次阅读 多人点赞 2018-09-15 21:29:28
    通过使用简单的结构,我们可以巧妙地降低一些问题的时间复杂度。 单调性质: 1、若是单调递增,则从栈顶到底的元素是严格递增的。若是单调递减,则从栈顶到底的元素是严格递减的。 2、越靠近栈顶...

    通过使用栈这个简单的结构,我们可以巧妙地降低一些问题的时间复杂度。

    单调栈性质:

    1、若是单调递增栈,则从栈顶到栈底的元素是严格递增的。若是单调递减栈,则从栈顶到栈底的元素是严格递减的。

    2、越靠近栈顶的元素越后进栈。(显而易见)

    本文介绍单调栈用法

    通过一道题来说明。

    POJ2559

    1. 题目大意:链接

    给出一个柱形统计图(histogram), 它的每个项目的宽度是1, 高度和具体问题有关。 现在编程求出在这个柱形图中的最大面积的长方形。

    7 2 1 4 5 1 3 3

    7表示柱形图有7个数据,分别是 2 1 4 5 1 3 3, 对应的柱形图如下,最后求出来的面积最大的图如右图所示。

    做法1:枚举每个起点和终点,矩形面积就是长*最小高度。O(N^3)

    做法2:区间最小值优化。O(N^2)

    做法3:以每一个下标为中心向两边扩,遇到更短的就停,这样我们可以确定以每一个下标高度为最高的矩形。O(N^2)

    单调栈:维护一个单调递增栈,所有元素各进栈和出栈一次即可。每个元素出栈的时候更新最大的矩形面积。

    过程:

    1)判断当前元素小于栈顶

    2)条件满足,就可以更新栈顶元素的最大长度了,并且把栈顶弹出

    3)继续执行(1),直到条件不满足。

     

    重要结论:

    1)栈顶下面一个元素一定是,栈顶左边第一个比栈顶小的元素

    2)当前元素一定是,右边第一个比栈顶小的元素。

    为什么呢?

    比如这是个栈

    1)如果右边存在距离更近的比1号小的数,1号早已经弹出了。

    2)如果左边有距离更近的比1号小的数

                    如果它比2号小,它会把2号弹出,自己成为2号

                     如果它比2号大,它不会弹出2号,但是它会压栈,变成2号,原来的2号成为3号。

    所以不管怎么说,这个逻辑是正确的。

    最后放代码并讲解

     

    下面看一道难一些的题

    LeetCode 85 Maximal Rectangle

    1 0 1 0 0

    1 0 1 1 1

    1 1 1 1 1

    1 0 0 1 0

    Return 6.二三行后面那六个1

     

    给定一个由二进制组成的矩阵map,找到仅仅包含1的最大矩形,并返回其面积。

    这道题是一行一行的做。对每一行都求出每个元素对应的高度,这个高度就是对应的连续1的长度,然后对每一行都更新一次最大矩形面积。

    连续1长度也很好更新,本个元素是0,长度就是0,本个元素是1,那就加上之前的。

    具体思路代码中讲解。

    import java.util.Stack;
    
    public class MaximalRectangle {
    
    	public static int maxRecSize(int[][] map) {
    		if (map == null || map.length == 0 || map[0].length == 0) {
    			return 0;
    		}
    		int maxArea = 0;
    		int[] height = new int[map[0].length];
    		for (int i = 0; i < map.length; i++) {
    			for (int j = 0; j < map[0].length; j++) {
    				height[j] = map[i][j] == 0 ? 0 : height[j] + 1;//0长度为0,1长度为前面+1
    			}
    			maxArea = Math.max(maxRecFromBottom(height), maxArea);//调用第一题的思想
    		}
    		return maxArea;
    	}
    
    	//第一题思路
    	public static int maxRecFromBottom(int[] height) {
    		if (height == null || height.length == 0) {
    			return 0;
    		}
    		int maxArea = 0;
    		Stack<Integer> stack = new Stack<Integer>();
    		for (int i = 0; i < height.length; i++) {
                    //栈非空并且栈顶大
    			while (!stack.isEmpty() && height[i] <= height[stack.peek()]) {
    				int j = stack.pop();//弹出
    				int k = stack.isEmpty() ? -1 : stack.peek();
    				int curArea = (i - k - 1) * height[j];//计算最大
    				maxArea = Math.max(maxArea, curArea);//更新总体最大
    			}
    			stack.push(i);//直到栈顶小,压入新元素
    		}
    		//最后栈非空,右边没有更小元素使它们弹出
    		while (!stack.isEmpty()) {
    			int j = stack.pop();
    			int k = stack.isEmpty() ? -1 : stack.peek();
    			int curArea = (height.length - k - 1) * height[j];
    			maxArea = Math.max(maxArea, curArea);
    		}
    		return maxArea;
    	}
    
    	public static void main(String[] args) {
    		int[][] map = { { 1, 0, 1, 1 }, { 1, 1, 1, 1 }, { 1, 1, 1, 0 }, };
    		System.out.println(maxRecSize(map));
    	}
    
    }

     

     

    展开全文
  • 在表达式计算过程的应用

    千次阅读 2017-07-31 23:12:06
    在表达式计算过程的应用 :建立操作数栈和运算符。运算符有优先级。 规则: 自左至右扫描表达式,凡是遇到操作一律进操作数栈。 当遇到运算符时,如果它的优先级比运算符栈顶元素的优先级高就进栈。...
  • JVM以方法作为最基本的执行单元,栈帧则是用于支持虚拟机进行方法调用与方法执行背后的数据结构,同样它也是JVM运行时数据区的虚拟机栈的栈元素
  • 这么说吧,网上的解释看着蛋疼,...现在有一容量为m的S,有n个元素S顶端一侧等待进栈,另一侧是出栈序列。现在要使用push和pop这两种操作,由一操作序列可以得到一系列的输出序列。请你编程求出对于给定的...
  • 以至于很多文章或课本喜欢直接给出计算方法一步到位,但关于其中的原理却并未深究,本文试图通过分析运算符的内优先级,外优先级的排序方法探求中缀表达式计算中的原理。为了简便起见,在本文的讨论只考虑双目...
  • SWUSTOJ #1044 顺序基本操作的实现

    千次阅读 2019-04-26 13:55:20
    编程实现顺序栈的初始化、入栈、出栈、取栈顶元素计算栈中元素个数等基本操作。
  • 应用之缀转后缀表达式(C语言版) 这篇文章已经讲了如何把中缀表达式转化为后缀表达式,这一篇就讲如何计算后缀表达式,计算比转换容易得多得多了。C++代码实现下载 java代码实现下载 (备用下载地址 )步骤...
  • 计算数组个数左边第一比其大的值 如果用最简单的暴力法,时间复杂度最坏情况下 O(n^2) 用解决,遍历到a[i] 当中为空,直接压入 不为空,比较栈顶元素 top 和 a[i]。 若 top &lt; a[i] ,弹出栈顶...
  • 因为sizeof运算符可以求出每对象所占内存的字节,并且在这些基本类型组成的数组,每个元素所占内存空间都是相同的,因此我们可以使用 “数量 = 总价 / 单价” 这种方式来计算。 而我们的string字符串数组是可...
  • C++获取数组元素个数的问题

    万次阅读 2017-02-14 16:21:46
    C++数组可分为堆区的数组和区的数组,对于两种数组C++都没有函数可以直接获取数组...堆区的数组不能计算出包含元素个数。 二、区的数组 区的数组是系统自动分配的。 int arr[10] = { 1,2,3,4,5,6,7,8,9,0 };
  • 使用栈计算表达式

    千次阅读 2018-09-26 22:54:00
    我们一般使用的表达式是中缀表达式即A+B这样的,后缀表达式就是另一种便于计算机计算的表达式。通过使中缀表达式成为一颗二叉树,中缀表达是二叉树的中序遍历...如果遇到操作符就从栈中弹出两操作,这操作...
  • 使用实现表达式求值,运用栈计算

    千次阅读 2020-09-26 15:13:58
    遇到操作符时,如果优先级低于或等于栈顶操作符优先级,则从nums弹出两个元素进行计算,并压入nums, 继续与栈顶操作符的比较优先级 4.如果遇到操作符高于栈顶操作符优先级,则直接入栈ops 5.遇到左括号,直接...
  • 栈中插入元素 出栈(pop) 删除栈中元素 栈顶元素(peek) 返回栈顶元素(未出栈) 注:顺序–入出栈采用尾插入、删除,时间复杂度为O(1),自动扩充容量时入栈为O(n); 链...
  • 计算机二级考试公共基础知识点:及其基本运算2018年计算机二级考试公共基础知识点:及其基本运算考点5及其基本运算考试链接:考点5在笔试考试,是一必考的内容,在笔试考试出现的几率为100%,主要是以...
  • 补充完善下面的C语言代码,实现顺序的基本操作,然后借助所实现的顺序完成十进制转八进制的算法(请参考课本算法3.1),最后在主函数测试该算法(测试用例:(1348)10=(2504))8. /*①顺序的定义*/ ...
  • 计算数组个数左边第一比其大的值 如果用最简单的暴力法,时间复杂度最坏情况下 O(n^2),遍历每一个数,再遍历它的两边 arr = [5,2,4,9,3,1,5,7,8,6,1,3,5,5] stack = [] n = len(arr) leftFirstMax = [None]*n...
  • 在表达式计算中的应用

    千次阅读 2014-09-19 23:06:11
    首先需要分配2个栈,一作为临时存储运算符的S1(含一结束符号),一作为输入逆波兰式的S2(空栈),S1可先放入优先级最低的运算符#,注意,中缀式应以此最低优先级的运算符结束。可指定其他字符,不一定...
  • 算术表达式的计算(的应用)

    千次阅读 2016-05-29 16:51:30
    受大一学妹沈灵邀请,编了一个计算算术表达式的程序,主要运用来实现,具体思想参照,《数据结构》胡学刚,张晶主编第2章的应用 首先,我们建立两个栈,一用来保存数字,一用来保存字符。对于输入的字符串...
  • 转换成走格子问题以5格子为例1 2 3 4 52 5 9 145 14 2814 4242不难发现其中规律,如果想要详细了解可以去这链接...n个元素的入栈顺序有多少种出栈顺序? 1个元素:1种 2个元素:2种 3...
  • 其实此题还可以用动归方法解决,f[i,j],i表示入栈的个数,j表示出栈的个数,那f[i,j]就表示入栈i个数中出j个数的,但是此题要注意的是出栈不能大于入栈,那动归方程该如何推导,再次谢谢一位某位具有探索精神的...
  • 递归的分解为普通表达式普通表达式只有2优先级,+-为0,×÷为0.5进入括号时,括号对应的这一层运算符的优先级基础值赋值为左括号左边一运算符的优先级+1运算符的优先级=括号层base+4运算符(+-×÷)自身的...
  • 编程实现顺序栈的初始化、入栈、出栈、取栈顶元素计算栈中元素个数等基本操作。 输入 第一行为入栈元素的个数; 第二行依次为入栈的元素; 出栈操作的次数n. 输出 输出n次出栈后的栈顶元素值。如果是空栈,...
  • 对于JVM执行引擎来说,在在活动线程,只有位于JVM虚拟机栈顶的元素才是有效的,即称为当前栈帧,与这栈帧相关连的方法称为当前方法,定义这方法的类叫做当前类。 执行引擎运行的所有字节码指令都只针对当前
  • 然后元素开始出栈,出栈的元素依次和存放在数组的第二部分元素进行比较,形象一点说也就是从原字符正中间取两个元素开始依次向两边比较(奇数字符的话跳过中间那个取其两边的),一直比到两边尽头。...
  • 入门

    万次阅读 多人点赞 2020-05-02 20:30:12
    的定义: (stack)又名堆栈,它是一种运算受限的...从一个栈删除元素又称作出栈或退,它是把栈顶元素删除掉,使其相邻的元素成为新的栈顶元素。 基本概念 要搞清楚这概念,首先要明白”“原来的意思...
  • 2018安徽大学计算机机试2--单调

    千次阅读 2018-03-30 09:41:00
    问题描述 ...例如:栈元素为2 3 7,如栈元素为6, 则7出栈,6入栈,最后结果为2 3 6; 输入输出 第一行输入一整数0&lt;n&lt;100000,表示待入栈的元素序列 第二行输入n待入栈的...

空空如也

空空如也

1 2 3 4 5 ... 20
收藏数 127,459
精华内容 50,983
关键字:

如何计算栈中元素个数