华为7.9面试题

算法

1.及格线

题目：输入10位同学的分数，要求给出及格线，及格线必须为10的倍数且保证至少6名同学及格。如果所有同学分数大于60分，则及格线取60分。
分析：题目简单，解法粗暴。先按升序排序成数组score，如果score[0]>=60则返回60，否则返回(score[3]/10)*10。

2.开关灯

题目： 总共有n(1<=n<=65536）盏灯，n个同学，灯与同学都编号1,2,3...n。灯最开始都是关着的，n从1开始，编号为n的同学会按编号为n的倍数的灯开关一次，直到第n个同学按完。请问最后有几盏灯亮。
分析：
暴力解法就是模拟整个过程，需要用到长度为n的数组，空间复杂度$\Theta(N)$。每个同学都要走一遍灯，但不是走遍所有的灯，如n=2的同学只要走一半的灯，所以总的时间复杂度是亚二次时间。编号为x的同学只需要按n盏灯中的n/x盏灯，所以总的时间复杂度为$n+\frac{n}{2}+\frac{n}{3}+...+\frac{n}{n}=n(1+\frac{1}{2}+\frac{1}{3}+...+\frac{1}{n})=n(\ln(n)+r)$，r是个常数。$n(\ln(n)+r)$是当n趋于无穷时的收敛结果，所以当n比较大时，时间复杂度为$\Theta(n\ln(n))$。
第二个思路需要认识到第n盏灯被按的次数是n的因子个数，如14的因子为1，2，7，14，因子数为4，所以14号灯的状态为开-关-开-关。因子个数偶数说明灯是关着的。但是要求一个数的因子个数，似乎也不是高效手法。但发现只有平方数，如25，其因子个数才是奇数，否则肯定是偶数。所以整个题目就变成了1～n中平方数的个数有多少个。时间复杂度$\Theta(1)$，空间复杂度$\Theta(1)$，应该说较暴力模拟法有了相当大的提高，核心代码也是短得不能再短。

/*
Filename: LightsOpen.cpp
Function: int GetLightsOpen( int n )
总共有n(1<=n<=65536）盏灯，n个同学，灯与同学都
编号`1,2,3...n`。灯最开始都是关着的，n从1开始，
编号为x的同学会按编号为x的倍数的灯开关一次，直
到第n个同学按完。请问最后有几盏灯亮。
Details:
*/
#include <iostream>
#include <math.h>
using namespace std;
int GetLightsOpen( int n );
int main()
{
    int n;
    cout<<"Please input your parameter: ";
    cin>>n;
    cout<<"Lights opening number: "<<GetLightsOpen( n )<<endl;
}
int GetLightsOpen( int n )
{
    int result = sqrt( n );
    return result;
}

3.地铁换乘最短路

题目：
有两条地铁线路A和B。A是环线，B是东西线路。
A："A1", "A2", "A3", "A4", "A5", "A6", "A7", "A8", "A9", "T1", "A10","A11", "A12", "A13", "T2", "A14", "A15", "A16", "A17" , "A18"
B："B1","B2","B3","B4","B5","T1","B6","B7","B8","B9","B10","T2","B11","B12","B13","B14","B15"
输入任意两个站名（首站和尾站），出两站之间最短的站数（首站和尾站也算一站）。
分析： 思路还是比较清晰的，首先求出输入参数两站所属线路，假设输入首战f，尾站t，那么如果两站同属一条线路（A或B），则求出在本线路上两站的最短站数即可；如果两站属不同线路（一个A一个B），那么一定需要一个换乘点（T1或T2），那么只要求出通过t1换乘和通过t2换乘的线路中较短站数的即可。在本题中可以把T1和T2都当做是A线路的站，因为A线中T1和T2距离更短。所以当输入刚好是T1T2时，那么就可以算在A线路内部两站的距离，而不会产生歧义。当线路更多更复杂时，是不能够这么简单处理的。

#include <string>
#include <iostream>
using namespace std;
#ifndef MIN
#define MIN(a,b)  ((a)-(b))>0?(b):(a)
#endif
struct Station
{
    string name;//站名
    int index;//所属线路label=0 A; label=1 B;
    int label;//在本线路中的索引
};
int FindStation( string s[], string station, int length );
int main( )
{
    string A[20]={ "A1", "A2", "A3", "A4", "A5", "A6", "A7", "A8", "A9", "T1", "A10",
        "A11", "A12", "A13", "T2", "A14", "A15", "A16", "A17" , "A18" };
    string B[17]={ "B1","B2","B3","B4","B5","T1","B6","B7","B8","B9","B10",
        "T2","B11","B12","B13","B14","B15" };
    int result;
    //两条线路的长度
    int len[2]={20,17};
    //输入的站
    Station  station[2];
    //两个中转站的索引，
    //t1_index[0]是t1在A线中的索引号，
    //t1_index[1]是t1在B线中的索引号
    int t1_index[2]={ 9, 5 };
    int t2_index[2]={ 14, 11 };
    //保存首尾两站到t1站距离
    //len_t1[0]是首站到t1的距离
    //len_t1[1]是尾站到t1的距离
    int len_t1[2], len_t2[2];
    cin>>station[0].name>>station[1].name;
    //计算站的所属线路及其索引号
    for( int i=0; i<2; i++ )
    {
        if( ( station[i].index=FindStation( A, station[i].name, len[0] ) ) != -1 )
            station[i].label = 0;
        else if( ( station[i].index=FindStation( B, station[i].name, len[1] ) ) != -1 )
            station[i].label = 1;
        else 
            return -1;
    }
    if( station[0].label==station[1].label )
    {
        //都是A线
        if( station[0].label==0 )
        {
            result = MIN( abs( station[0].index - station[1].index )+1 , 
                len[station[0].label] - abs( station[0].index - station[1].index )+1 );
            cout<< result;
             system("pause"); 
             return 1;
        }
        //都是B线
        else if( station[0].label==1 )
        {
            cout<< abs( station[0].index - station[1].index )+1<<endl;
             system("pause"); 
             return 1;
        }
        else
            return -1;
    }
    //首站为A线，尾站为B线
    if( station[0].label == 0 )
    {
        len_t1[0] = MIN( abs( station[0].index - t1_index[0] )+1, 
            len[0] - abs( station[0].index - t1_index[0] )+1 ) ;
        len_t2[0] = MIN( abs( station[0].index - t2_index[0] )+1, 
            len[0] - abs( station[0].index - t2_index[0] )+1 ) ;
        len_t1[1] = abs( station[1].index - t1_index[1]  ) + 1;
        len_t2[1] = abs( station[1].index - t2_index[1]  ) + 1;
    }
    //首站为B线，尾站为A线
    else if( station[0].label == 1 )
    {
        len_t1[0] = abs( station[0].index - t1_index[1]  ) + 1;
        len_t2[0] = abs( station[0].index - t2_index[1]  ) + 1;
        len_t1[1] = MIN( abs( station[1].index - t1_index[0] )+1, 
            len[0] - abs( station[1].index - t1_index[0] )+1 ) ;
        len_t2[1] = MIN( abs( station[1].index - t2_index[0] )+1, 
            len[0] - abs( station[1].index - t2_index[0] )+1 ) ;
    }
    result = MIN( len_t1[0]+len_t1[1], len_t2[0]+len_t2[1] )-1;
    cout<<result;
    system("pause"); 
    return 1;
}
int FindStation( string s[], string station, int length )
{
    for( int i=0; i<length; i++ )
        if( s[i]==station )
            return i;
    return -1;
}