代码练习

日期内容
27日上午数字统计P1179 、接水问题P1190、乘阶之和P1009、约瑟夫问题P1996、三连击P1008、校门外的树P1047、最大子段和P1115
下午计数问题  P1980、旅行家的预算  P1016
28日上午二分法:P1571、泛洪算法:P1162 、排列组合:P1157、 DP-背包问题:P1048
下午二叉树的遍历1:P1827 、先序排列:P1030、二叉树遍历0:B3642
29日上午1、计算数学表达式的值,详见表后题目描述
2、哈夫曼树-荷马史诗:P2168
3、倍增法-最近公共祖先 T3(P3379)
下午4、字典树-阅读理解 P3879
30上午1、二叉树深搜 P4913
2、树的路径  P3252
3、对称二叉树 P5018
3、二叉堆-堆 P3378
4、二叉搜索树:见表后题目描述 P1864
下午拓扑排序-家谱树:B3644
线段树讲解 ,区间: P1712
31上午二叉索引树(树状数组)讲解 P3368
笛卡尔树讲解 P5854
二叉平衡树讲解 3369
下午图的单源最短路径:P4779
图的最小生成树:P3366



题目:计算表达式的值

给定一个表达式,其中运算符仅包含 +,-,*,/(加 减 乘 整除),可能包含括号,请你求出表达式的最终值。

注意:

  • 数据保证给定的表达式合法。
  • 题目保证符号 - 只作为减号出现,不会作为负号出现,例如,-1+2(2+2)*(-(1+1)+2) 之类表达式均不会出现。
  • 题目保证表达式中所有数字均为正整数。
  • 题目保证表达式在中间计算过程以及结果中,均不超过 2^31−1。
  • 题目中的整除是指向 0 取整,也就是说对于大于 0 的结果向下取整,例如 5/3=1,对于小于 0 的结果向上取整,例如 5/(1−4)=−1。

输入格式

共一行,为给定表达式。

输出格式

共一行,为表达式的结果。

数据范围

表达式的长度不超过 10^5。

输入样例:

(12/3+2)*(13-2*3)

输出样例:

42

题目:判断二叉搜索树

二叉搜索树 (BST) 递归定义为具有以下属性的二叉树:

  • 若它的左子树不空,则左子树上所有结点的值均小于它的根结点的值
  • 若它的右子树不空,则右子树上所有结点的值均大于或等于它的根结点的值
  • 它的左、右子树也分别为二叉搜索树

我们将二叉搜索树镜面翻转得到的树称为二叉搜索树的镜像。

现在,给定一个整数序列,请你判断它是否可能是某个二叉搜索树或其镜像进行前序遍历的结果。

输入格式

第一行包含整数 N,表示节点数量。

第二行包含 N个整数。

输出格式

如果给定整数序列是某个二叉搜索树或其镜像的前序遍历序列,则在第一行输出 YES,否则输出 NO

如果你的答案是 YES,则还需要在第二行输出这棵树的后序遍历序列。

数据范围

1≤N≤1000

输入样例1:

7
8 6 5 7 10 8 11

输出样例1:

YES
5 7 6 8 11 10 8

输入样例2:

7
8 10 11 8 6 7 5

输出样例2:

YES
11 8 10 7 5 6 8

输入样例3:

7
8 6 8 5 10 9 11

输出样例3:

NO
Scroll to Top