Question

• 题目描述：

  搬寝室是很累的,xhd深有体会.时间追述2006年7月9号,那天xhd迫于无奈要从27号楼搬到3号楼,因为10号要封楼了.看着寝室里的n件物品,xhd开始发呆,因为n是一个小于2000的整数,实在是太多了,于是xhd决定随便搬2k件过去就行了.但还是会很累,因为2k也不小是一个不大于n的整数.幸运的是xhd根据多年的搬东西的经验发现每搬一次的疲劳度是和左右手的物品的重量差的平方成正比(这里补充一句,xhd每次搬两件东西,左手一件右手一件).例如xhd左手拿重量为3的物品,右手拿重量为6的物品,则他搬完这次的疲劳度为(6-3)^2 = 9.现在可怜的xhd希望知道搬完这2*k件物品后的最佳状态是怎样的(也就是最低的疲劳度),请告诉他吧。

• 输入：

  每组输入数据有两行,第一行有两个数n,k(2<=2*k<=n<2000).第二行有n个整数分别表示n件物品的重量(重量是一个小于2^15的正整数).

• 输出：

  对应每组输入数据,输出数据只有一个表示他的最少的疲劳度,每个一行.

• 样例输入：

  2 1 1 3

• 样例输出：

  4

Unicode与UTF-8的区别

ASCII码

在计算机的世界里，信息的表示方式只有0和1，但是人类信息的表示方式却与之大不相同，很多时候是用语言文字、图像、声音等传递信息的

怎么将其转化为二进制存储到计算机中，这个过程我们称之为编码

在计算机中每八个二进制位组成了一个字节（byte），计算机存储的最小单位就是字节

LCS – Longest Common Subsequence

Question

题目描述：

Find a longest common subsequence of two strings.

输入：

First and second line of each input case contain two strings of lowercase character a…z. There are no spaces before, inside or after the strings. Lengths of strings do not exceed 100.

输出：

For each case, output k – the length of a longest common subsequence in one line.

样例输入：

abcdcxbydz

样例输出：

2

来源：

2008年上海交通大学计算机研究生机试真题

Question

Given an unsorted array of integers, find the length of longest increasing subsequence.

Example:

1
2
3

Input: [10,9,2,5,3,7,101,18]
Output: 4 
Explanation: The longest increasing subsequence is [2,3,7,101], therefore the length is 4.

Note:

• There may be more than one LIS combination, it is only necessary for you to return the length.
• Your algorithm should run in O(n2) complexity.

Follow up: Could you improve it to O(n log n) time complexity?

二叉排序树，二叉查找树，二叉查找树

二叉排序树（Binary Sort Tree），又称二叉查找树（Binary Search Tree），二叉查找树（Binary Search Tree），二叉树的一个变种

定义：

是指一棵空树或者具有下列性质的二叉树：

1. 若左子树非空，则左子树上的所有结点的关键字值均小于根结点的关键字值
2. 若右子树非空，则右子树上的所有结点的关键字值均大于根结点的关键字值
3. 左、右子树本身也分别是一棵二叉查找树（二叉排序树）

二叉查找树是一个递归的数据结构，且对二叉查找树进行中序遍历，可以得到一个递增的有序序列。

在进行搜索，查找的时候是非常有利的，因为它的平均操作时间接近O(h)，h为树的高度，而且，二叉排序树本身是具有动态性的，可以动态地进行节点的删除，插入等的操作，BST的中序遍历必定是严格递增的

Jobdu-二叉搜索树

Question

题目描述：

判断两序列是否为同一二叉搜索树序列

输入：

开始一个数n，(1<=n<=20) 表示有n个需要判断，n= 0 的时候输入结束。接下去一行是一个序列，序列长度小于10，包含(0~9)的数字，没有重复数字，根据这个序列可以构造出一颗二叉搜索树。接下去的n行有n个序列，每个序列格式跟第一个序列一样，请判断这两个序列是否能组成同一颗二叉搜索树。

输出：

如果序列相同则输出YES，否则输出NO

样例输入：

1
2
3
4
5

2
567432
543267
576342
0

样例输出：

YESNO

Jobdu-1201-二叉排序树

Question

题目描述：

输入一系列整数，建立二叉排序数，并进行前序，中序，后序遍历。

输入：

输入第一行包括一个整数n(1<=n<=100)。    接下来的一行包括n个整数。

输出：

可能有多组测试数据，对于每组数据，将题目所给数据建立一个二叉排序树，并对二叉排序树进行前序、中序和后序遍历。    每种遍历结果输出一行。每行最后一个数据之后有一个空格。

样例输入：

51 6 5 9 8

样例输出：

1 6 5 9 8 1 5 6 8 9 5 8 9 6 1

提示：

输入中可能有重复元素，但是输出的二叉树遍历序列中重复元素不用输出。

Jobdu-1078-二叉树遍历

Question

题目描述：

二叉树的前序、中序、后序遍历的定义：前序遍历：对任一子树，先访问跟，然后遍历其左子树，最后遍历其右子树；中序遍历：对任一子树，先遍历其左子树，然后访问根，最后遍历其右子树；后序遍历：对任一子树，先遍历其左子树，然后遍历其右子树，最后访问根。给定一棵二叉树的前序遍历和中序遍历，求其后序遍历（提示：给定前序遍历与中序遍历能够唯一确定后序遍历）。

输入：

两个字符串，其长度n均小于等于26。第一行为前序遍历，第二行为中序遍历。二叉树中的结点名称以大写字母表示：A，B，C….最多26个结点。

输出：

输入样例可能有多组，对于每组测试样例，输出一行，为后序遍历的字符串。

样例输入：

ABCBACFDXEAGXDEFAG

样例输出：

BCAXEDGAF

U-Net

天池肺结节 宜远智能分享

CT图像肺结节检测

3-10mm 较小

10-30mm

数据量少