面试题选（3）

算法

1.在从 1 到 n 的正数中 1 出现的次数(数组)

题目:输入一个整数 n,求从 1 到 n 这 n 个整数的十进制表示中 1 出现的次数。
例如输入 12, 1 到 12 这些整数中包含 1 的数字有 1,
从10,11 和 12, 一共出现了 5 次。
分析:这是一道广为流传的 google 面试题。

2.蜂窝结构最短路径搜索

题目：一类似于蜂窝的结构的图,进行搜索最短路径(要求 5 分钟)
分析：华为面试题，要求5分钟。

3.交换数组元素使得数组之和相差最小

题目：有两个序列 a,b,大小都为 n,序列元素的值任意整数,无序;
要求:通过交换 a,b 中的元素,使[序列 a 元素的和]与[序列 b 元素的和]之间的差最小。
分析： 暴力解法，耗费$\Theta(N^2)$时间。从a中第一个元素开始，从b中找到一个元素，通过调换使得两数列之差减小最多。一趟下来要走$N^2$次，而且可能不止一趟，当第n趟与第n-1趟没有差别，说明已达最优，则返回。求更好的解法。

/*
Filename: LeastSumDiff.cpp
Function: void LeastSumDiff( int A[], int B[], int length )
有两个序列 a,b,大小都为 n,序列元素的值任意
整数,无序;要求:通过交换 a,b 中的元素,使序
列 a 元素的和与序列 b 元素的和之间的差最小
Details: 暴力解法，期待更好的解法
*/
#ifndef ABS
#define ABS( a, b )  ((a)-(b))>0?((a)-(b)):((b)-(a))
#endif
#include <iostream>
using namespace std;
void LeastSumDiff( int A[], int B[], int length );
void Swap( int *a, int *b );
int main()
{
    int a[] = { 1,3,5,9,10};
    int b[] = { 2,4,6,8,10};
    int length = sizeof(a)/sizeof(int);
    LeastSumDiff( a, b, length );
    for( int i=0; i<length; i++)
    {
        cout<<a[i]<<" "<<b[i]<<endl;
    }
}
void LeastSumDiff( int A[], int B[], int length )
{
    int diff = 0;
    int sum_a=0, sum_b=0;
    for( int i=0; i<length; i++ )
    {
        sum_a += A[i];
        sum_b += B[i];
    }
    int diff_min = ABS( sum_a, sum_b );
    while( diff != diff_min )
    {
        diff = diff_min;
        int tmp=0;
        for( int i=0; i<length; i++ )
            for( int j=0; j<length; j++ )
            {
                tmp = ABS( sum_a-A[i]+B[j], sum_b+A[i]-B[j] );
                if( tmp < diff_min )
                {
                    Swap( &A[i], &B[j] );
                    diff_min = tmp;
                }
                if( diff_min==0 )
                    return;
            }
    }
}
void Swap( int *a, int *b )
{
    int tmp;
    tmp = *a;
    *a = *b;
    *b = tmp;
}

4.实现一个字符匹配算法:

题目：给一串很长字符串,要求找到符合要求的字符串,例如目的串:123，则1******3***2,12*****3这些都要找出来其实就是类似一些和谐系统。

5.求一个矩阵中最大的二维矩阵(元素和最大).

题目：如:
1 2 0 3 4
2 3 4 5 1
1 1 5 3 0
中最大的是:
4 5
5 3
要求:(1)写出算法;(2)分析时间复杂度;(3)用 C 写出关键代码
分析： 给出的矩阵没有排序信息，也没有其它规律，只能暴力解决。从左到右，从上到下遍历矩阵，保存最大二维矩阵和的左上角值索引即可。

6.二叉树中和为某一值的路径

题目：输入一颗二叉树和一个整数，打印出二叉树中结点值的和为输入整数的所有路径。路径定义为从树的根结点开始往下一直到叶结点所经过的结点形成一条路径。
分析：

7.树的子结构

题目： 输入两棵二叉树A 和B，判断B是否为A的子结构。
分析： 思路还是比较清晰的。如果B是A的子结构，那么B的根节点必须在A中，而且B根节点的左子树和右子树也该和A中对应的一样。算法步骤为：判断B的根节点值和A的根节点值是否相等，如果相等，则递归判断；如果B更大，则B和A的右子树比较，如果小于等于，则和左子树比较（假设允许存在重复数，且相等值均在左子树）。

8.二叉搜索树转有序双向链表

题目： 输入一棵二叉搜索树，现在要将该二叉搜索树转换成一个排序的双向链表。而且在转换的过程中，不能创建任何新的结点，只能调整树中的结点指针的指向来实现。
分析：