数据结构及算法程序设计习题篇（一）_数据结构与程序设计 考题

题目：已知两颗二叉树，将它们合并成一颗二叉树。合并规则是：都存在的结点，就将结点值加起来，否则空的位置就由另一个树的结点来代替。
例如：
两颗二叉树是:
Tree 1
1
/ \
3 2
/
5

Tree 2
2
/
1 3
\
4 7

合并后的树为
3
/
4 5
/ \
5 4 7

思想：
根据题意，可以将问题划分为多个子问题，故使用递归的方法，注意程序的入口和出口是这题的关键。

代码展示：

void MergeTree(struct TreeNode *&T1, struct TreeNode *&T2){
    if(T2==NULL) return;
    if(T1!=NULL && T2!=NULL){
        T1->data = T1->data+T2->data;
    }
    if(T1==NULL && T2!=NULL){
        T1 = T2;
    }
    MergeTree(T1->lchild,T2->lchild);
    MergeTree(T1->rchild,T2->rchild);
}
1
2
3
4
5
6
7
8
9
10
11

题目：判断一个无序数组中是否存在长度为3的递增子序列。
（不要求连续，满足O(n)的时间复杂度和O(1)的空间复杂度。）

思想：由于时间复杂度为O（n），空间复杂度为O（1），所以此题只给了我们遍历一次数组的机会，也不能使用常数级别以外的空间，由于可以是不连续的，所以只需要在当前的元素之前，出现过一个比它还要小的元素，就可以使得到这个元素的递增序列长度+1，故每到一个元素时，就把它和之前的最小元素进行比较，只需要另外使用一个标记一下当前元素之前的最小元素时多少就行，即为下面代码中的Min。

代码展示：

int Judge(){
    int arr[] = {4,2,5,1,7};//测试用例：4，5，3，2，1，返回0（false）
    int length = sizeof(arr)/ sizeof(int);
    if(length<3) return false;
    int Min = arr[0];//Min代表当前元素之前最小的元素的值，先将第一个元素假设成最小的
    int count = 1;
    for(int i=1; i<length; i++){
        if(arr[i]>Min){
            count++;
        }
        else{
            Min = arr[i];
        }
        if(count>=3) return true;
    }
    return false;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17

题目：
代码实现二叉树的后续遍历。
要求：1、不可以用递归；2、不可以用栈；3、自定义树节点的结构；4、给出测试用例；
注意：你的方法的输入为根节点
参考方法：定义树结构体如下：
struct TreeNode {
int value;
TreeNode* parent;
TreeNode* lchild;
TreeNode* rchild;
}

思想：借助父指针，抓住后序遍历的特点是先访问左孩子再访问右孩子，最后访问父结点，可以借用一个新的指针来保存已访问的结点帮助实现。

代码展示：

void newPostOrder(struct ListNode* root)
{
    if (!root) return;
    ListNode* last = NULL;
    ListNode* now = root;
    while (now)
    {
        if (last == now->left)
        {
            if (now->right)
            {
                now = now->right;
            }
            else
            {
                printf("%d ",now->val);
                last = now;
                now = now->father;
                continue;
            }
        }
        else if (last == now->right)
        {
            printf("%d ",now->val);
            last = now;
            now = now->father;
            continue;
        }

        while (now->left){
            now = now->left;
        }
        printf("%d ",now->val);
        last = now;
        now = now->father;
    }
}

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38

------------------------------------分界线--------------------------------------
题目：
给定两个字符串。
定义三种操作：
1.插入一个字符
2.修改一个字符
3.删除一个字符
求最少几步操作使得第一个字符串变成第二个字符串。
例如：第一个字符串lighten,第二个字符串fighting
fighten (l->f) 修改
fightin (e->i) 修改
fighting (->g) 插入
一共三步

思想：
根据一顿骚操作，找规律，分析得出，最少的次数实际上就等于较长的数组长度减去两个数组按顺序出现的重复出现的字母个数。（注意，本来我以为是只要减去重复出现的元素个数就行，但是实际上并不是这样，比如cat和tac，这两个里面的元素是完全一样的，并不代表它们不经过上述任何操作就能实现一个向另一个的转变，而正确的结果应该是两次。不过好在自己发现的早吧，同时，在这个错误的想法中，我也学到了一些新的东西。我们都知道，异或运算符^，可以用来判断两个位上面的数值是否相同，借此可以用来解决“去重的问题”，但是得注意，它是按位进行去重，如果输入1异或2的话，结果返回的是3，而不是想当然的以为会返回0，因为01+10=11=3。同时，如果想要交换两个数但是又不借助额外的空间的话，我们也可以借助异或运算符（不要说用加减抵消法也行，效率来说不如异或来得快）
好了，言归正传，我们的主要目的是先找出按顺序出现的重复的元素个数，也就是我们通常听说过的那个熟悉的问题——找出最长公共子序列（LCS）。下面，我们针对这一问题来进行分析和解答。

首先，要明确什么是最长公共子序列，千万不要把它和最长公共子串相混淆！！！

最长公共子序列，英文缩写为LCS（Longest Common Subsequence）。其定义是，一个序列 S ，如果分别是两个或多个已知序列的子序列，且是所有符合此条件序列中最长的，则 S 称为已知序列的最长公共子序列。

   如果觉得抽象不好理解，那么咱们还是采用学习LIS的时候的方式。首先，让我们先来看一下子串、子序列还有公共子序列的概念(在上篇LIS中也曾涉及过) ，我们以字符子串和字符子序列为例，更为形象，也能顺带着理解字符的子串和子序列：

 （1）字符子串：指的是字符串中连续的n个字符，如abcdefg中，ab，cde，fg等都属于它的字串。

 （2）字符子序列：指的是字符串中不一定连续但先后顺序一致的n个字符，即可以去掉字符串中的部分字符，但不可改变其前后顺序。如abcdefg中，acdg，bdf属于它的子序列，而bac，dbfg则不是，因为它们与字符串的字符顺序不一致。

   (3)  公共子序列：如果序列C既是序列A的子序列，同时也是序列B的子序列，则称它为序列A和序列B的公共子序列。如对序列 1,3,5,4,2,6,8,7和序列 1,4,8,6,7,5 来说，序列1,8,7是它们的一个公共子序列。

   那么现在，我们再通俗的总结一下最长公共子序列（LCS）：就是A和B的公共子序列中长度最长的（包含元素最多的）
1
2
3
4
5
6
7
8
9

仍然用序列1,3,5,4,2,6,8,7和序列1,4,8,6,7,5为例，它们的最长公共子序列有1,4,8,7和1,4,6,7两种，但最长公共子序列的长度是4。由此可见，最长公共子序列（LCS）也不一定唯一。

  请大家用集合的观点来理解这些概念，子序列、公共子序列以及最长公共子序列都不唯一，所以我们通常特判取一个最长公共子序列，但很显然，对于固定的两个数组，虽然最LCS不一定唯一，但LCS的长度是一定的。查找最长公共子序列与查找最长公共子串的问题不同的地方在于：子序列不需要在原序列中占用连续的位置。最长公共子串（要求连续）和最长公共子序列是不同的。
1

那么该如何求出两个序列的最长公共子序列长度呢？请继续往下看～

你首先能想到的恐怕是暴力枚举？那我们先来看看：序列A有 2^n 个子序列，序列B有 2^m 个子序列，如果任意两个子序列一一比较，比较的子序列高达 2^(n+m) 对，这还没有算具体比较的复杂度。或许你说，只有长度相同的子序列才会真正进行比较。那么忽略空序列，我们来看看：对于A长度为1的子序列有C(n,1)个，长度为2的子序列有C(n,2)个，……长度为n的子序列有C(n,n)个。对于B也可以做类似分析，即使只对序列A和序列B长度相同的子序列做比较，那么总的比较次数高达：C(n,1)*C(m,1)*1 + C(n,2) * C(m,2) * 2+ …+C(n,p) * C(m,p)*p，其中p = min(m, n)。

   吓着了吧？怎么办？我们试试使用动态规划算法！

   我们用Ax表示序列A的连续前x项构成的子序列，即Ax= a1,a2,……ax, By= b1,b2,……by, 我们用LCS(x, y)表示它们的最长公共子序列长度，那原问题等价于求LCS(m,n)。为了方便我们用L(x, y)表示Ax和By的一个最长公共子序列。让我们来看看如何求LCS(x, y)。我们令x表示子序列考虑最后一项
1
2
3

（1） Ax ＝ By

     那么它们L(Ax, By)的最后一项一定是这个元素！

   为什么呢？为了方便，我们令t = Ax = By, 我们用反证法：假设L(x,y)最后一项不是t，则要么L(x,y)为空序列（别忘了这个），要么L(x,y)的最后一项是Aa＝Bb ≠ t, 且显然有a < x, b < y。无论是哪种情况我们都可以把t接到这个L(x,y)后面,从而得到一个更长的公共子序列。矛盾！
   如果我们从序列Ax中删掉最后一项ax得到Ax-1,从序列By中也删掉最后一项by得到By-1，(多说一句角标为0时，认为子序列是空序列)，则我们从L(x,y)也删掉最后一项t得到的序列是L(x – 1, y - 1)。为什么呢？和上面的道理相同，如果得到的序列不是L(x - 1, y - 1)，则它一定比L(x - 1, y - 1)短（注意L（，）是个集合！），那么它后面接上元素t得到的子序列L(x,y)也比L(x - 1, y - 1)接上元素t得到的子序列短，这与L(x, y)是最长公共子序列矛盾。因此L(x, y) = L(x - 1, y - 1) 最后接上元素t，LCS(Ax, By) = LCS(x - 1, y - 1) + 1。
1
2
3
4

（2） Ax ≠ By

    仍然设t = L(Ax, By), 或者L(Ax, By)是空序列（这时t是未定义值不等于任何值）。则t  ≠ Ax和t  ≠ By至少有一个成立，因为t不能同时等于两个不同的值嘛！
1

（2.1）如果t ≠ Ax，则有L(x, y)= L(x - 1, y)，因为根本没Ax的事嘛。

        LCS(x,y) = LCS(x – 1, y)
1

（2.2）如果t ≠ By,l类似L(x, y)= L(x , y - 1)

        LCS(x,y) = LCS(x, y – 1)
   可是，我们事先并不知道t，由定义，我们取最大的一个，因此这种情况下,有LCS(x,y) = max(LCS(x – 1, y) , LCS(x, y – 1))。看看目前我们已经得到了什么结论：
1
2

LCS(x,y) =
(1) LCS(x - 1,y - 1) + 1 （Ax ＝ By）
(2) max(LCS(x – 1, y) , LCS(x, y – 1)) （Ax ≠ By）

这时一个显然的递推式，光有递推可不行，初值是什么呢？显然，一个空序列和任何序列的最长公共子序列都是空序列！所以我们有:
LCS(x,y) =
(1) LCS(x - 1,y - 1) + 1 如果Ax ＝ By
(2) max(LCS(x – 1, y) , LCS(x, y – 1)) 如果Ax ≠ By
(3) 0 如果x = 0或者y = 0

到此我们求出了计算最长公共子序列长度的递推公式。我们实际上计算了一个(n + 1)行(m + 1)列的表格（行是0…n，列是0…m)，也就这个二维度数组LCS(,)。

大概的伪代码如下：
输入序列A, B长度分别为n，m,计算二维表 LCS(int,int):

//伪代码如下：
for x = 0 to n do
    for y = 0 to m do
        if (x == 0 || y == 0) then 
            LCS(x, y) = 0
        else if (Ax == By) then
            LCS(x, y) =  LCS(x - 1,y - 1) + 1
        else 
            LCS(x, y) = ) max(LCS(x – 1, y) , LCS(x, y – 1))
        endif
    endfor
endfor
1
2
3
4
5
6
7
8
9
10
11
12

（此处不适用递归的原因：递归会导致问题子问题被重复计算，动态规划显然是为了避免这一问题，用数表进行记录即可）

LCS(x,y)的值来源的三种情况：
（1） LCS(x – 1, y – 1) + 1如果Ax ＝ By
这对应L(x,y) = L(x,- 1 y- 1)末尾接上Ax
（2.1） LCS(x – 1, y) 如果Ax ≠ By且LCS(x – 1, y) ≥LCS(x, y – 1)
这对应L(x,y)= L(x – 1, y)
（2.2） LCS(x, y – 1) 如果Ax ≠ By且LCS(x – 1, y) <LCS(x, y – 1)
这对应L(x,y) = L(x, y – 1)
（3） 0 如果 x =0或者y = 0
这对应L(x,y)=空序列

注意(2.1)和(2.2) ，当LCS(x – 1, y) ＝ LCS(x, y – 1)时，其实走哪个分支都一样，虽然长度时一样的，但是可能对应不同的子序列，所以最长公共子序列并不唯一。

时间复杂度时O(n * m)，空间也是O(n * m)

------------------------------------分界线--------------------------------------
（看完此题是不是耗费了很多时间呢，没关系，下一题更精彩）

题目：
请实现有重复数字的有序数组的二分查找。
输出在数组中第一个大于等于查找值的位置，如果数组中不存在这样的数，则输出数组长度加一

思想：略微改动原有的二分查找，注意只有两个元素时候可能会出现的死循环情况！！！

代码展示：

int mid;
//找最左边的一个
int halfFind0(int *arr, int i, int j, int x){
    while(i<j){
        mid = (i+j)/2;
        if(arr[mid]>=x){
            j = mid;
        }
        if(arr[mid]<x){
            i = mid+1;
        }

    }
    if(arr[mid]==x){
        return j;
    }
    return -1;
}

//找最右边的一个
int halfFind1(int *arr, int i, int j, int x){
    while(i<j){
        mid = (i+j)/2+1;
        if(arr[mid]<=x){
            i = mid;
        }
        if(arr[mid]>x){
            j = mid-1;
        }

    }
    if(arr[mid]==x){
        return j;
    }
    return -1;
}

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37