笔试面试题目7

灰太狼 2022-09-17 13:23 368阅读 0赞

1. 给定一个二叉树，以及一个指定节点(节点的Key值或节点指针皆可)，寻找从根节点到指定节点的路径。  
例如给定二叉树如下图，指定节点为e，那么我们可以得到的路径为 a-b-d-e  
a  
/ \\  
b f  
/ \\ / \\  
c d g k  
 \\ \\  
e l

#include <iostream>
    #include <vector>
    #include <algorithm>
    using namespace std;
    
    typedef struct node
    {
        char data;
        struct node *lchild;
        struct node *rchild;
    } BiNode, *BiTree;
    
    //先序递归创建树，这里注意参数的类型，T的类型是 "*&" ,如果是 "**" 代码稍加改动就OK...
    void createTree(BiTree &T)
    {
    	char ch;
    	cin.get(ch).get();
    	//过滤输入流中每次回车产生的回车符
    	if (ch==' ')
    		T = NULL; //这里首先判断是不是空格，如果是，则为该节点赋NULL
    	else
    	{
    		T = (BiTree)malloc(sizeof(BiNode));
    		T->data = ch;
    		createTree(T->lchild);
    		createTree(T->rchild);
    	}
    }
    // 将数的节点销毁
    void deleteTree( BiTree T)
    {
        if(T == NULL)
            return ;
        deleteTree(T->lchild);
        deleteTree(T->rchild);
        delete T;
    }
    
    // 寻找路径
    bool FindPath(BiNode *root, char ch, vector<char> &path)
    {
        if(root == NULL)
            return false;
    
        if(root->data == ch)
        {
            path.push_back(root->data);
            return true;
        }
        path.push_back(root->data);
        if(FindPath(root->lchild, ch, path))
        {
            return true;
        }
        else if(FindPath(root->rchild, ch, path))
        {
            return true;
        }
    
        path.pop_back();
        return false;
    }
    
    int main()
    {
        cout<<"Enter char one by one"<<endl;
        BiNode *T;
        createTree(T);
        cout<<endl;
    
    
        vector<char> path;
        FindPath(T, 'e', path);
        cout << "The Path is as follow:" << endl;
        for( int i = 0; i < path.size(); i++)
        {
            cout << path[i] << " ";
        }
        cout << endl;
        deleteTree(T);
        return 0;
    }

运行结果：  
Enter char one by one  
a  
b  
c  
  
  
  
  
d  
  
  
e  
  
  
  
  
f  
g  
  
  
  
  
k  
  
  
l  
The Path is as follow:  
a b d e  
  
2. 一个数组，元素为N个整数，范围为1-N，且没有重复元素存在，初始为乱序。现将数组中某一个元素a 修改为 b，其中b也是1-N之间的一个数。  
给定修改后的数组，确定元素 a 和 b

#include <iostream>
    #include <vector>
    #include <algorithm>
    using namespace std;
    
    void FindElement( int A[], int N)
    {
        // 首先找到b
        for( int i = 0; i < N; i++)
        {
            if( A[i] == i)
                continue;
    
            int count = 0;
            while(count < N - 1 && A[i] != i)
            {
                int tmp = A[i];
                if( tmp == A[tmp])
                {
                    cout << "b: " << A[tmp] << endl;
                    break;
                }
                A[i] = A[tmp];
                A[tmp] = tmp;
            }
        }
    
        // 首先找到b
        for( int i = 0; i < N; i++)
        {
            if( A[i] == i)
                continue;
            else
                cout << "a: " << i << endl;
        }
    }
    
    int main()
    {
        int A[] = {0, 1, 2, 3, 3, 5, 6, 7, 8, 9};
        FindElement( A, 10);
    
        return 0;
    }

输出结果：  
b: 3  
a: 4  
  
3. 有一组字符串，查找这一组字符串中相同的字符串。  
方法1：  
逐个字符串两两对比，使用strcmp()进行对比，这个时候时间复杂度为O(n^2)。  
  
方法2:  
使用hash的方法，首先对字符串进行编码，将编码后的字符串进行hash，如果两个字符串的hash值相同。

则再对两个字符串进行一次strcom()对比，确定是否是相同的字符串。

字符串编码采用的方式可以有很多种：  
1. 将每个字符的ASCII码逐个相加，得到对应编码

2. 将字符ASCII码乘字符在字符串中的位置，然后将其相加。

By Andy @ 2013年10月23日