第六章部分例题

lan126 lan126     2022-09-11     506

关键词:

 1 #include <iostream>
 2 #include <sstream>
 3 
 4 using namespace std;
 5 
 6 const int maxn=100000;
 7 int n;
 8 int postorder[maxn],inorder[maxn];
 9 int lh[maxn],rh[maxn];
10 
11 
12 bool read_list(int* a)
13 {
14     string line;
15 
16     if(!getline(cin,line)) return false;
17                                 /*利用stringstream来构造字符串流读入一行数据*/
18     stringstream ss(line);
19 
20     n=0;
21     int num;
22     while(ss>>num) a[n++]=num;
23 
24     return n>0;
25 }
26 
27 int built_tree(int l1,int r1,int l2,int r2)
28 {                              /*递归建立二叉树返回数根,用各个节点的值来标志*/
29     if(l1>r1) return 0;
30 
31     int root=postorder[r2];
32 
33     int p=l1;
34 
35     while(inorder[p]!=root) p++;
36 
37     int cnt=p-l1;
38 
39     lh[root]=built_tree(l1,p-1,l2,l2+cnt-1);
40     rh[root]=built_tree(p+1,r1,l2+cnt,r2-1);
41 
42     return root;
43 }
44 
45 int best_sum,best;
46 
47 void dfs(int u,int sum)
48 {                             /*深度优先,如果是叶子节点就进行判断*/
49     sum+=u;
50 
51     if(!lh[u] && !rh[u])
52     {
53         if(sum<best_sum || (sum==best_sum && u<best))
54         {
55             best_sum=sum;
56             best=u;
57         }
58     }
59 
60     if(lh[u]) dfs(lh[u],sum);
61     if(rh[u]) dfs(rh[u],sum);
62 }
63 
64 
65 int main()
66 {
67 
68     while(read_list(inorder))
69     {
70         read_list(postorder);
71         built_tree(0,n-1,0,n-1);
72 
73         int u=0,sum=0;
74 
75         best=u;
76         best_sum=100000000;
77 
78         dfs(postorder[n-1],sum);
79 
80         cout<<best<<endl;
81     }
82 
83     return 0;
84 }

 

第六章部分例题

 6-4自己先敲了一遍虽然可以完成书上的功能但是漏洞百出1#include<iostream>2#include<cstdio>3#include<cstring>45usingnamespacestd;67constintmaxn=100000+100;89chartxt[maxn];10intnext[maxn];1112intmain()13{1 查看详情

第六章部分例题

 没看解答敲了一遍,发现自己题目的理解能力有点差 1#include<iostream>2#include<cstdio>34usingnamespacestd;56structNode7{8charvalue;9Node*ch1;10Node*ch2;11Node*ch3;12Node*ch4;1314Node():ch1(NULL),ch2(NULL 查看详情

第六章部分例题双向bfs邻接表和邻接矩阵实现

Idealpath双向bfs输出颜色,邻接矩阵实现 1#include<iostream>2#include<cstdio>3#include<cstring>4#include<queue>5#include<map>6#include<algorithm>78usingnamespacestd;910consti 查看详情

第六章例题

 1#include<cstdio>2#include<cstring>34usingnamespacestd;56intbtr[1<<20];789intmain()10{11intD,I;1213while(scanf("%d%d",&D,&I)==2)14{15memset(btr,0,sizeof(btr));1617intk; 查看详情

第六章例题二叉树层次遍历

 1.指针实现#include<iostream>#include<vector>#include<queue>#include<cstdio>#include<cstring>usingnamespacestd;#definemaxn100structNode{boolhave_value;intvalue;/*节点结构体*/ 查看详情

机试指南第六章-搜索-例题自解(代码片段)

枚举:枚举是最简单也是最直白的搜索方式,它依次尝试搜索空间中所有的解,测试其是否符合条件,若符合则输出答案,否则继续测试下一组解。例6.1百鸡问题#include<iostream>usingnamespacestd;intmain()intn;while(cin>>n)for(intx=0;x... 查看详情

算法入门经典第六章例题6-5移动盒子

例题6-5移动盒子(BoxesinaLine,UVa127675)问题给定一行盒子,从左到右编号依次为1,2,...,n.可以执行以下命令:1XY 把盒子X移动到Y的左边(如果已经在左边,忽略此命令)2XY 把盒子X移动到Y右边(如果X已经在Y的右边,忽... 查看详情

算法入门经典第六章例题6-15给任务排序

 假设有n个变量,还有m个二元组(u,v),分别表示变量u小于v。那么,所有变量从小到大排列起来应该是什么样子呢?例如,有4个变量a,b,c,d,若已知a<b,c<b,d<c,则这4个变量的排序可能是a<d<c<b。尽管还有其他可能... 查看详情

第六章:循环结构

第六章:循环结构(二)一.for循环1.循环结构的四个组成部分   (1).初始部分:设置循环的初始状态,比如我们设置记录循环次数的变量i为0.   (2).循环体:重复执行的代码.   (3).迭代部分:下一... 查看详情

算法入门经典第六章例题6-14abbott的复仇(abbott'srevenge)bfs算法实现

 SampleInput31N33 11WLNR* 12WLFNRER* 13NLER* 21SLWRNF* 22SLWFELF* 23SFREL* 0SampleOutput(3,1)(2,1)(1,1)(1,2)(2,2)(2,3)(1,3)(1,2)(1,1)(2,1) (2,2)(1,2)(1,3)( 查看详情

《算法》第六章部分程序part7(代码片段)

?书中第六章部分程序,加上自己补充的代码,包括全局最小切分Stoer-Wagner算法,最小权值二分图匹配●全局最小切分Stoer-Wagner算法1packagepackage01;23importedu.princeton.cs.algs4.In;4importedu.princeton.cs.algs4.StdOut;5importedu.princeton.cs.algs4.EdgeWei 查看详情

第六章

盒子模型1.盒子(box)模型内容(content)、填充(padding)、边框(border)、边界(margin)2.不同部分的说明Content(内容):盒子中的内容,显示文本或图片Padding(内边距):清除内容周围的区域,内边距的透明度Border(边框)... 查看详情

第六章习题

本来准备模仿前几题建树来做,但是发现判断部分还是要写出答案那样. 1#include<iostream>2#include<cstdio>345usingnamespacestd;67structNode8{9boolhave_value;10intw;11intd;1213Node*left,*right;1415Node():left(NULL),right( 查看详情

《学习之道》第六章习惯的部分-反应程序

  如果你保护自己的反应程序,它最终也会反过来保护你。  我们大脑接到信号暗示时做出的常规性、习惯性的反应。  习惯可以是无害的或有益的,但在最坏的情况下,它可能会有很强的破坏性,它们会违抗常识。可以... 查看详情

java第六章

for循环语法:for(表达式1;表达式2;表达式3){             //循环体 }  for的运算步骤为 1》2》4》3》1。。。  表达式1:赋值语句>循环结构的初始部分,为循环变量赋... 查看详情

第六章循环结构

一.   for循环语法:for(表达式1;表达式2;表达式3){             //循环体 }表达式1:赋值语句>循环结构的初始部分,为循环变量赋初值,eg:inti=0表达式2:条件语句>循环结构... 查看详情

c和指针(pointersonc)——第六章:指针(上)

第六章指针这一章,就明显触痛刚開始学习的人敏感之处了。我也是在一段时间不用C以后就会对这一部分生疏,好吧,事实上是对高级指针那块生疏。当然这一部分总有非常多借鉴之处。比方数组范围的问题等,要不我也不会... 查看详情

第六章:个人主页和头像

...kMega-TutorialPartVI:ProfilePageandAvatars这是FlaskMega-Tutorial系列的第六部分,我将告诉你如何创建个人主页。本章将致力于为应用添加个人主页。个人主页用来展示用户的相关信息,其个人信息由本人录入。我将为你展示如何动态地生成... 查看详情