精华内容
下载资源
问答
  • 已知n长度的元素序列,列出所有栈输出的可能结果 今天上数据结构课时遇到了一个题目: 设数据元素序列{a,b,c,d,e,f,g}的进堆栈操作和出堆栈操作可任意进行(排除堆栈...其实用递归做起来还是蛮简单的,栈的输出结构画张...

    已知n长度的元素序列,列出所有栈输出的可能结果

    今天上数据结构课时遇到了一个题目:
    设数据元素序列{a,b,c,d,e,f,g}的进堆栈操作和出堆栈操作可任意进行(排除堆栈为空时的出栈情况),下列哪些元素序列可由堆栈序列得到?
    哇…这要一个一个列出来岂不是疯掉…

    因为对公式还不是很了解,所以决定先把代码写出来,把所有可能都列出来,这样说不定会好理解一点
    其实用递归做起来还是蛮简单的,栈的输出结构画张图可以发现和二叉树结构类似
    在这里插入图片描述
    这样,代码就比较容易实现了,一开始打算用C语言来实现的,结果太久没碰C语言,能算出多少种,但输出结果不会打出来…所以又改用Python来实现

    def copyData(tmpStack,tmpRes,popTime,pushTime):
        # copy
        return tmpStack[:],tmpRes[:],popTime,pushTime
    
    def printAllRes(tmpStack,tmpRes,popTime,pushTime,count):
        # 参数:临时栈,显示结果,出栈次数,入栈次数,数据总长度
        if(len(tmpRes) == count):
            # 当出栈次数等于数据总长度,将临时显示的结果添加到总结果中
            results.append(tmpRes)
        if(pushTime < count):
            # 当入栈次数小于上限,优先进行入栈操作
            t_tmpStack,t_tmpRes,t_popTime,t_pushTime = copyData(tmpStack,tmpRes,popTime,pushTime)
            t_tmpStack.append(data[t_pushTime])
            printAllRes(t_tmpStack,t_tmpRes,t_popTime,t_pushTime+1,count)
        if(popTime < count and len(tmpStack) > 0):
            # 当出栈次数小于上限并且临时存储的栈不为空时,出栈
            t_tmpStack,t_tmpRes,t_popTime,t_pushTime = copyData(tmpStack,tmpRes,popTime,pushTime)
            t_tmpRes.append(t_tmpStack.pop())
            printAllRes(t_tmpStack,t_tmpRes,t_popTime+1,t_pushTime,count)
    
    if __name__ == "__main__":
        data = [1,2,3] # 待入栈的数据
        results = [] # 临时存放所有结果的列表
    
        printAllRes([],[],0,0,len(data))
        print('共有' + str(len(results)) + '种方式')
        for item in results:
            print(item)
    
    

    刚开始因为不太常用递归,没有加入 t_ 的临时变量…,怎么做都不对,改了无数次都不对,一个晚上的时间都花在这上面了,甚至都开始怀疑python不能递归了😂,看来还是自己不熟练啊…

    展开全文
  • 2019-03-25 15:47:00
    题目大意:给定一个序列序列数两两不同,每一步进行两种操作,压栈和弹,问可能得到多少序列输出总数。 n<=1000 考虑到每一次只有两种操作,并且不合法情况就是弹次数多余压栈次数,这个就和括号...

    题目大意:给定一个序列,序列中的数两两不同,每一步进行两种操作,压栈和弹栈,问可能得到多少序列,输出总数。

    n<=1000

    考虑到每一次只有两种操作,并且不合法的情况就是弹栈次数多余压栈次数,这个就和括号匹配是一个原理,很显然就是卡特兰数了。

    卡特兰数的递推公式:C(2n,n)/(n+1),根据我们的常识判断,当n达到1000时,这个数已经远远超过了LL的范围,所以我们考虑高精,但是如果是每一次都乘并更新进位的话,那么恭喜你:时间空间两开花

    那么我们先从C(2n,n)上下手,(2n)!/n!/n!,这就是从n+1乘到2n除以1乘到n,那么由于我们知道除完之后得到的一定是整数,所以除数一定含有被除数的所有质因子,并且比被除数多,我们就可以考虑质因数分解。

    我们利用线性筛筛出每一个数的最小质因子,将其分解,并记录每一个质因子出现了多少次,遇到一个新的数就不断将其拆分直到为1为止,最后我们利用高精度乘法将他们乘到一起即可。

    最后,附上本题代码:

     1 #include<cstdio>
     2 #define maxn 4000
     3 #define LL long long
     4 using namespace std;
     5 
     6 LL n,ans[maxn+5],prime[maxn+5],cnt;
     7 LL min_prime[maxn+5],cou_prime[maxn+5];
     8 bool vis[maxn+5],ok;
     9 
    10 int main()
    11 {
    12     scanf("%lld",&n);
    13     for(int i=2; i<=n; i++)
    14     {
    15         if(vis[i]==0)
    16         {
    17             prime[++cnt]=i;
    18             min_prime[i]=i;
    19         }
    20         LL temp=i;
    21         while(min_prime[temp]!=temp)
    22         {
    23             cou_prime[min_prime[temp]]--;
    24             temp/=min_prime[temp];
    25         }
    26         cou_prime[min_prime[temp]]--;
    27         for(int j=1; j<=cnt&&i*prime[j]<=n*2; j++)
    28         {
    29             vis[i*prime[j]]=1;
    30             min_prime[i*prime[j]]=prime[j];
    31             if(i%prime[j]==0)
    32             {
    33                 break;
    34             }
    35         }
    36     }
    37     /*for(int i=1;i<=n;i++)
    38     {
    39         printf("%lld",cou_prime[i]);
    40     }*/
    41     for(int i=n+2; i<=n*2; i++)
    42     {
    43         if(vis[i]==0)
    44         {
    45             prime[++cnt]=i;
    46             min_prime[i]=i;
    47         }
    48         LL temp=i;
    49         while(min_prime[temp]!=temp)
    50         {
    51             cou_prime[min_prime[temp]]++;
    52             temp/=min_prime[temp];
    53         }
    54         cou_prime[min_prime[temp]]++;
    55         for(int j=1; j<=cnt&&i*prime[j]<=n*2; j++)
    56         {
    57             vis[i*prime[j]]=1;
    58             min_prime[i*prime[j]]=prime[j];
    59             if(i%prime[j]==0)
    60             {
    61                 break;
    62             }
    63         }
    64     }
    65     /*for(int i=1; i<=n*2; i++)
    66     {
    67         printf("%lld",cou_prime[i]);
    68     }*/
    69     ans[1]=1;
    70     for(int i=1; i<=n*2; i++)
    71     {
    72         for(int j=1; j<=cou_prime[i]; j++)
    73         {
    74             for(int k=1; k<=2000; k++)
    75             {
    76                 ans[k]*=i;
    77             }
    78             for(int k=1; k<=2000; k++)
    79             {
    80                 ans[k+1]+=ans[k]/10;
    81                 ans[k]%=10;
    82             }
    83         }
    84     }
    85     for(int i=2000; i>=1; i--)
    86     {
    87         if(ans[i]!=0)
    88         {
    89             ok=1;
    90         }
    91         if(ok==1)
    92         {
    93             printf("%lld",ans[i]);
    94         }
    95     }
    96     return 0;
    97 }

     

    转载于:https://www.cnblogs.com/yufenglin/p/10594156.html

    展开全文
  • 栈的应用

    2019-08-06 17:18:21
    来源:牛客网 给定一个数组序列, 需要求选出一个区间, 使得该区间是所有区间中...区间中最小数 * 区间所有数和最后程序输出经过计算后最大值即可,不需要输出具体区间。如给定序列 [6 2 1]则根据上述公式,...

    链接:https://www.nowcoder.com/questionTerminal/e6e57ef2771541dfa2f1720e50bebc9a
    来源:牛客网

    给定一个数组序列, 需要求选出一个区间, 使得该区间是所有区间中经过如下计算的值最大的一个:

    区间中的最小数 * 区间所有数的和最后程序输出经过计算后的最大值即可,不需要输出具体的区间。如给定序列 [6 2 1]则根据上述公式, 可得到所有可以选定各个区间的计算值:

    [6] = 6 * 6 = 36;

    [2] = 2 * 2 = 4;

    [1] = 1 * 1 = 1;

    [6,2] = 2 * 8 = 16;

    [2,1] = 1 * 3 = 3;

    [6, 2, 1] = 1 * 9 = 9;

    从上述计算可见选定区间 [6] ,计算值为 36, 则程序输出为 36。

    区间内的所有数字都在[0, 100]的范围内;

    输入描述:

    第一行输入数组序列长度n,第二行输入数组序列。
    对于 50%的数据, 1 <= n <= 10000;
    对于 100%的数据, 1 <= n <= 500000;

    输出描述:

    输出数组经过计算后的最大值。

    示例1
    输入

    3
    6 2 1

    输出

    36

    #include<iostream>
    #include<algorithm>
    #include<stack>
    #include<vector>
    using namespace std;
    int main()
    {
        int n,maxs=0,pre=0,after=0,a;
        stack<int> s;
        cin>>n;
        vector<int>vsum(n+1,0);
        vector<int>v(n+1,0);
        for(int i=0;i<n;i++)
        {
            cin>>a;
            v[i]=a;
            if(i==0) vsum[i]=a;
            else
                vsum[i]=vsum[i-1]+a;
        }
        for(int i=0;i<=n;i++)
        {
                while(!s.empty()&&v[i]<v[s.top()])
                {
                    int t=s.top(),sum;
                    s.pop();
                    if(s.empty())
                        sum=v[t]*(vsum[i-1]);
                    else
                    {
                        int pre=s.top();
                        sum=v[t]*(vsum[i-1]-vsum[pre]);
                    }
                    maxs=max(maxs,sum);
                }
                s.push(i);
            
        }
        cout<<maxs<<endl;
    
    }
    
    展开全文
  • 单调

    2021-03-14 15:01:58
    单调 1、字节跳动抖音客户端二面笔试...如给定序列 [6 2 1]则根据上述公式, 可得到所有可以选定各个区间计算值: [6] = 6 * 6 = 36; [2] = 2 * 2 = 4; [1] = 1 * 1 = 1; [6,2] = 2 * 8 = 16; [2,1] = 1 * 3 = 3; [6,

    单调栈

    1、字节跳动抖音客户端二面笔试题 题目链接
    给定一个数组序列, 需要求选出一个区间, 使得该区间是所有区间中经过如下计算的值最大的一个:

    区间中的最小数 * 区间所有数的和最后程序输出经过计算后的最大值即可,不需要输出具体的区间。如给定序列 [6 2 1]则根据上述公式, 可得到所有可以选定各个区间的计算值:

    [6] = 6 * 6 = 36;

    [2] = 2 * 2 = 4;

    [1] = 1 * 1 = 1;

    [6,2] = 2 * 8 = 16;

    [2,1] = 1 * 3 = 3;

    [6, 2, 1] = 1 * 9 = 9;

    从上述计算可见选定区间 [6] ,计算值为 36, 则程序输出为 36。

    区间内的所有数字都在[0, 100]的范围内;

    输入描述:

    第一行输入数组序列长度n,第二行输入数组序列。
    对于 50%的数据, 1 <= n <= 10000;
    对于 100%的数据, 1 <= n <= 500000;

    输出描述:

    输出数组经过计算后的最大值。

    示例1

    输入

    3
    6 2 1

    输出

    36

    思路:
        将每个元素都当做当前最小值,从该元素i开始向左右分别遍历,直到找到比他小的元素为止,将当前数组范围内的元素和*nums[i]的值与最大值进行比较。
        很显然这种方法的时间复杂度为O(n^2)。
        其实上面关于找到比当前元素小的值可以提前预处理,利用单调栈实现O(n)的预处理。
    left数组存储左边比他小的元素的下标值,right数组存储右边比他小的元素的下标值,
    对于left数组,当栈不为空时且栈顶元素比当前值更大,就将栈顶元素弹出
    当栈为空时,说明左边没有比他更小的元素了,所以压入-1
    当栈顶元素比当前值更小时,压入当前位置的下标。

    #include<stdio.h>
    #include<vector>
    #include<algorithm>
    #include<stack>
    using namespace std;
    int main() {
    	int n;
    	scanf("%d", &n);
    	vector<int> nums(n + 2), l(n + 1), r(n + 1), sum(n + 1, 0);
    	stack<int> sk;
    	int a[105];
    	for (int i = 1; i <= n; ++i) {//累计值,将sum[n]=nums[1]+……+nums[n];sum[0]=0;
    		scanf("%d", &nums[i]);
    		sum[i] = sum[i - 1] + nums[i];
    	}
    	for (int i = 1; i <= n; ++i) {
    		while (!sk.empty() && sk.top()>=nums[i]) {
    			sk.pop();
    		}
    		if (sk.empty()) l[i] = 0;//为了方便累计值运算
    		else l[i] = a[sk.top()];
    		sk.push(nums[i]);
    		a[nums[i]] = i;
    	}
    	while (!sk.empty()) sk.pop();
    	for (int i = n; i>0; --i) {
    		while (!sk.empty() && sk.top()>=nums[i]) {
    			sk.pop();
    		}
    		if (sk.empty()) r[i] = n+1;
    		else r[i] = a[sk.top()];
    		sk.push(nums[i]);
    		a[nums[i]] = i;
    	}
    	int maxm = 0;
    	for (int i = 1; i <= n; ++i) {
    		maxm = max(maxm, nums[i] * (sum[r[i]-1] - sum[l[i]]));
    	}
    	printf("%d", maxm);
    }
    

    LeetCode第232场周赛题T4 题目链接
    给你一个整数数组 nums (下标从 0 开始)和一个整数 k 。

    一个子数组 (i, j) 的 分数 定义为 min(nums[i], nums[i+1], …, nums[j]) * (j - i + 1) 。一个 好 子数组的两个端点下标需要满足 i <= k <= j 。

    请你返回 好 子数组的最大可能 分数 。

    示例 1:

    输入:nums = [1,4,3,7,4,5], k = 3
    输出:15
    解释:最优子数组的左右端点下标是 (1, 5) ,分数为 min(4,3,7,4,5) * (5-1+1) = 3 * 5 = 15 。

    示例 2:

    输入:nums = [5,5,4,5,4,1,1,1], k = 0
    输出:20
    解释:最优子数组的左右端点下标是 (0, 4) ,分数为 min(5,5,4,5,4) * (4-0+1) = 4 * 5 = 20 。

    提示:

    1 <= nums.length <= 105
    1 <= nums[i] <= 2 * 104
    0 <= k < nums.length

    思路与上面一致

    int maximumScore(vector<int>& nums, int k) {
    	int n = nums.size();
    	vector<int> l(n,-1),r(n,n);
    	stack<int> sk;
    	for (int i = 0; i < n; ++i) {
    		while (!sk.empty() && nums[sk.top()] >= nums[i]) sk.pop();
    		if (sk.empty()) {
    			l[i] = -1;
    		}
    		else if (nums[sk.top()] < nums[i]) {
    			l[i] = sk.top();
    		}
    		sk.push(i);
    	}
    	while (!sk.empty()) sk.pop();
    	for (int i = n - 1; i >= 0;--i) {
    		while (!sk.empty() && nums[sk.top()] >= nums[i]) sk.pop();
    		if (sk.empty()) {
    			r[i] = n;
    		}
    		else if (nums[sk.top()] < nums[i]) {
    			r[i] = sk.top();
    		}
    		sk.push(i);
    	}
    	int maxm = 0;
    	for (int i = 0; i < n; ++i) {
    		if (l[i] < k&&k < r[i]) {
    			maxm = max(maxm, (r[i] - l[i] - 1)*nums[i]);
    		}
    	}
    	return maxm;
    }
    
    展开全文
  • 卡特兰数公式

    千次阅读 2017-07-21 18:29:32
    今天在刷题时,遇到了一个题:设栈的初始状态为空,当字符序列a3_作为栈的输入时,输出长度为3的且可以用作C语言标识符的字符串序列有()个。开始我是一个一个试试的,但是如果序列较多时,这种情况并不好计算。看...
  • 在学习数据结构的栈的合法输出序列时,我发现栈的合法输出序列的计算公式居然是著名的Catalan number,然后找了些资料学习了一下。 Catalan number 一般项公式 在解决计数问题时,我们常会遇到卡特兰数,卡特兰数的...
  • 文章目录前言栈序列内存存储存储结构模拟队列无归类曾经数据结构学很透,不常看,就,就忘了呀,sincerely,end. 前言   为提升和巩固个人现有知识水平,选择牛客网选择题进行练习,仅作为个人总结,分享...
  • 卡特兰数公式: 2.一个(无穷大)进栈序列为1,2,3,… ,n,有多少个不同出栈序列? 分析: (1)对于每个数来说,必须进栈一次,出栈一次。...=b),因此输出序列的总数目等于由左到右扫...
  • 仲恺acm 1095:火车出站【java】

    千次阅读 2016-01-03 09:14:23
    题目描述 铁路进行列车调度时,常把站台设计成式结构站台,试问: 设有编号为1到nn辆列车,顺序开入栈式...输出可能出栈序列有多少种。 样例输入 4 3 样例输出 14 5 通过百度,得到公式(2*n)! / (n! * n!
  • 火车出站

    千次阅读 2017-07-09 15:07:39
    题目描述 铁路进行列车调度时,常把站台设计成式结构站台,试问: ...输出可能出栈序列有多少种。 样例输入 4 3 样例输出 14 5 思路:利用公式ans=1/(n+1)*(2*n)!/n! 计算过程要注意
  • 火车出栈问题

    千次阅读 2018-06-28 17:08:04
    题目描述铁路进行列车调度时,常把站台设计成式结构站台,试问:设有编号为1到nn辆列车,顺序开入栈式结构站台,则可能出栈序列有多少种?输入输入包含多组测试数据。每组为一个正整数n(1&lt;=n&...
  • 浙江大学ACM题型分类

    2009-09-28 23:18:23
    1004 Anagrams by Stack 给出输入序列和若干输出序列,求栈的处理过程 stack 1005 JUGS 给两杯子,倒出n升水的最少步骤 搜索 1006 Do the Untwist  字符可加密成数字,指定数字可再加密。给出密文求原文 1007 ...
  • 面试题22:栈的压入、弹出序列:建立一个辅助栈,把push序列的数字依次压入辅助栈,每次压入后,比较辅助栈的栈顶元素和pop序列的首元素是否相等,相等的话就推出pop序列的首元素和辅助栈的栈顶元素,若最后辅助栈为...
  • Leetcode ---- 46. 全排列

    2018-11-29 09:51:42
    给定一个没有重复数字的序列,返回其所有可能全排列。 示例: 输入: [1,2,3] 输出: [ [1,2,3], [1,3,2], [2,1,3], [2,3,1], [3,1,2], [3,2,1] ] 思路: 该题采用回溯方法。 将问题简化,即得到两个...
  • 5.1 栈的应用 94 5.2 哈夫曼树 96 5.3 二叉树 102 5.4 二叉排序树 111 5.5 hash算法 114 5.6 前缀树 115 第六章 搜索 121 6.1 暴力枚举 122 6.2 广度优先搜索(BFS) 124 6.3 递归及其应用 127 6.4 深度...
  • 1.2.5 请计算XILINX公司VU9P芯片算力相当于多少TOPS,给出计算过程与公式 1.2.6 一颗现代处理器,每秒大概可以执行多少条简单MOV指令,有哪些主要影响因素 1.2.7 请分析 MaxCompute 产品与分布式技术...
  • 实例006 编程输出星号组成等腰三角形 9 1.2 开发工具 11 实例007 下载最新Eclipse 11 实例008 为最新Eclipse安装中文语言包 12 实例009 活用Eclipse工作空间 14 实例010 在Eclipse项目中编程输出字符表情 15...
  • 实例006 编程输出星号组成等腰三角形 9 1.2 开发工具 11 实例007 下载最新Eclipse 11 实例008 为最新Eclipse安装中文语言包 12 实例009 活用Eclipse工作空间 14 实例010 在Eclipse项目中编程输出字符表情 15...
  • 实例006 编程输出星号组成等腰三角形 9 1.2 开发工具 11 实例007 下载最新Eclipse 11 实例008 为最新Eclipse安装中文语言包 12 实例009 活用Eclipse工作空间 14 实例010 在Eclipse项目中编程输出字符表情 15...
  • 实例006 编程输出星号组成等腰三角形 9 1.2 开发工具 11 实例007 下载最新Eclipse 11 实例008 为最新Eclipse安装中文语言包 12 实例009 活用Eclipse工作空间 14 实例010 在Eclipse项目中编程输出字符表情 15...
  • 实例006 编程输出星号组成等腰三角形 1.2 开发工具 实例007 下载最新Eclipse 实例008 为最新Eclipse安装中文语言包 实例009 活用Eclipse工作空间 实例010 在Eclipse项目中编程输出字符表情 实例011 ...
  • 实例006 编程输出星号组成等腰三角形 1.2 开发工具 实例007 下载最新Eclipse 实例008 为最新Eclipse安装中文语言包 实例009 活用Eclipse工作空间 实例010 在Eclipse项目中编程输出字符表情 实例011 ...
  • 实例006 编程输出星号组成等腰三角形 1.2 开发工具 实例007 下载最新Eclipse 实例008 为最新Eclipse安装中文语言包 实例009 活用Eclipse工作空间 实例010 在Eclipse项目中编程输出字符表情 实例011 ...
  • 实例006 编程输出星号组成等腰三角形 1.2 开发工具 实例007 下载最新Eclipse 实例008 为最新Eclipse安装中文语言包 实例009 活用Eclipse工作空间 实例010 在Eclipse项目中编程输出字符表情 实例011 ...
  • 实例006 编程输出星号组成等腰三角形 1.2 开发工具 实例007 下载最新Eclipse 实例008 为最新Eclipse安装中文语言包 实例009 活用Eclipse工作空间 实例010 在Eclipse项目中编程输出字符表情 实例011 ...
  • (22) 下列关于栈的叙述中正确的是(D) A. 在栈中只能插入数据 B. 在栈中只能删除数据 C. 栈是先进先出的线性表 D. 栈是先进后出的线性表 (23) 下列关于队列的叙述中正确的是(C) A. 在队列中只能插入数据 B. 在队列中...
  • Java开发技术大全(500个源代码).

    热门讨论 2012-12-02 19:55:48
    notMultipleOfThree.java 把100-200之间不能被3整除输出 outputByDoWhile.java 用while循环随机输出数据 outputByWhile.java 用do~while循环随机输出数据 outputMax.java 求两个数中最大数 ...
  • 第7章Java输入和输出237 7.1文件和输入输出流237 7.2InputStream类和OutputStream类使用238 7.2.1InputStream中方法238 7.2.2OutputStream中方法239 7.2.3文件输入流FileInputStream239 7.2.4文件输出...

空空如也

空空如也

1 2
收藏数 36
精华内容 14
关键字:

栈的输出序列公式