华为的一道面试题--活跃气氛，顺便散分 - C语言论坛

第 11 楼

得分:6

收藏了。。

第 12 楼

得分:0

以下是引用specilize在2012-6-15 09:21:28的发言：

首先将所有的时间转换为整数，然后使用堆排序排为从小到大，然后确定g_sleep_time所属区间，为两种情况:若在g_tab_time[min]-----g_tab_time[max],则使用折半查找，通过比较绝对值查找最接近时间,若不在区间g_tab_time[min]-----g_tab_time[max]，则首先对g_sleep_time进行取模运算g_sleep_time%（g_tab_time[min]+g_tab_time[max]），然后将结果与g_tab_time[min]和g_tab_time[max]进行比较即可,例如g_tab_time[min]=00:03（整数3),g_tab_time[max]=23:45(整数1425),g_sleep_time=23:59(整数1439),g_sleep_time取模后为11，经过比较，与3最接近，代码略。。。。。。。。

思路不错，但是有几个问题。
1. 字符转化成整数，这个问题不难。
2. 堆排序，这个问题也不难。
3. 如果g_tab_time[min] = 00:05（整数5）， g_tab_time[max] = 23:59（整数1439），若现在g_sleep_time = 00:01（整数1），显然，1不在区间内，那用1对5+1439取模，得到1，将1与g_tab_time[min]和g_tab_time[max]进行比较，发现离5最近，这时候真是应该是选00:05么？

第 13 楼

得分:0

回复 10楼 lonmaor

版主V587啊膜拜一个

第 14 楼

得分:6

不需要做数值转换的，字符串比较即可，但最好先排序。

授人以渔，不授人以鱼。

第 15 楼

得分:7

数据量不是问题，最多不过1440而已。如果是我去参加面试，我会问考官这个要求我写的函数的使用频率有多高。

如果频率低，那怎么实现都无所谓。如果频率高，我会用查表法。

重剑无锋，大巧不工

第 16 楼

得分:0

回复 12楼 demonleer

哦，计算方法有点问题（反正我对这种循环问题的第一反应就是取模），实际上应该改为,若不在区间g_tab_time[min]-----g_tab_time[max],则(g_tab_time[min]-g_sleep_time+1440)%1440为到最小值的真实距离，(g_sleep_time-g_tab_time[max]+1440)%1440为到最大值的真实距离

第 17 楼

得分:0

回复 15楼 beyondyf

版主说的太有道理了，

哎，我看到的第一反应就是要提高查找效率，（从数据量角度来看），而不是首先分析实际情况。。。。。

第 18 楼

得分:17

程序代码：

#include <stdio.h>
#define TIME_TAB_MAX 10

int abs(int x)
{
    return x < 0 ? -x : x;
}

int ToSeconds(char* time)
{
    return ((time[0] - '0') * 10 + (time[1] - '0')) * 60 + (time[3] - '0') * 10 + (time[4] - '0');
}

int Difference(char* time1, char* time2)
{
    int sec1 = ToSeconds(time1), sec2 = ToSeconds(time2);
    int d1 = abs(sec1 - sec2), d2 = 1440 - d1;
    return d1 < d2 ? d1 : d2;
}

char* Find(char (*g_tab_time)[6], char* g_sleep_time, int time_tab_max)
{
    int min = Difference(g_tab_time[0], g_sleep_time), i, j;
    char* addr = g_tab_time[0];
    for (i = 1; i < time_tab_max; ++i) {
        j = Difference(g_tab_time[i], g_sleep_time);
        if (j < min) {
            min = j;
            addr = g_tab_time[i];
        }
    }
    return addr;
}

int main(void)
{
    char g_tab_time[TIME_TAB_MAX][6] = { "22:08", "08:31", "18:25", "21:35", "01:35", "23:45", "00:03", "09:34", "07:23", "09:59" };
    char g_sleep_time[6] = { "21:30" };
    printf("%s\n", Find(g_tab_time, g_sleep_time, TIME_TAB_MAX));
    return 0;
}

My life is brilliant

第 19 楼

得分:17

我写个查表的吧，看大家还没有用这种方法实现过。

也是把时间换算成分钟。先把 1440 种情况的答案提前算出来，存在一个表里。之后简单的查一下就行了。
找最近时间的方法好像和 10楼差不多。把前一天的最后一个时间和后一天的第一个时间前后续到今天来(在我这表现为负数和大于1440，所以那个分钟转字符串的函数也特殊处理了一下这两个时间)，然后在各个区间上和端点时间的中点比大小就行了。排序 TIME_TAB_MAX 个时间用的插入排序(没有改变原始表)，一是方便实现，二是考虑到这个基数比较小，n^2 也不慢。

代码的自明性很强，应该不用注释了：

程序代码：

#include <stdio.h>

#define TIME_TAB_MAX 10
char g_tab_time[TIME_TAB_MAX][6] =
{
    "22:08",
    "08:31",
    "18:25",
    "21:35",
    "01:35",
    "23:45",
    "00:03",
    "09:34",
    "07:23",
    "09:59"
};

char g_sleep_time[6] = {
  "23:59"
};

int lookup_tbl[1440];

int insert(int a[], int idx, int x)
{
    int i;
    for (i = idx; i > 0; i--)
    {
        if (a[i-1] > x)
            a[i] = a[i-1];
        else {
            a[i] = x;
            break;
        }
    }
    return i;
}

int t2m(char time[6])
{
    int h = (time[0]-'0') * 10 + (time[1]-'0');
    int m = (time[3]-'0') * 10 + (time[4]-'0');

    return h * 60 + m;
}

char m2t_res[6];
char *m2t(int m)
{
    int daymins = t2m("24:00"), h;
    if (m < 0)
        m += daymins;
    else if (m > daymins)
        m -= daymins;

    h = m / 60;
    m = m % 60;

    m2t_res[0] = h/10 + '0';
    m2t_res[1] = h%10 + '0';
    m2t_res[2] = ':';
    m2t_res[3] = m/10 + '0';
    m2t_res[4] = m%10 + '0';
    m2t_res[5] = '\0';
    return m2t_res;
}

void init_table()
{
    int i, interval[TIME_TAB_MAX + 2] = {0,};
    for (i = 1; i <= TIME_TAB_MAX; i++) {
        insert(interval, i, t2m(g_tab_time[i-1]));
    }
    interval[0] = interval[TIME_TAB_MAX] - t2m("24:00");
    interval[TIME_TAB_MAX+1] = t2m("24:00") + interval[1];

    int j = 0;
    for (i = 0; i < 1440 && j < TIME_TAB_MAX+1; i++)
    {
        if (i < (interval[j] + interval[j+1]) / 2 )
        {
            lookup_tbl[i] = interval[j];
        }
        else
        {
            lookup_tbl[i] = interval[j+1];
            j++;
        }
    }
    for (; i < 1440; i++)
        lookup_tbl[i] = interval[TIME_TAB_MAX+1];
}

char *lookup(char time[6])
{
    return m2t( lookup_tbl[t2m(time)] );
}

int main(int argc, char *argv[])
{
    init_table();
    printf("%s\n", lookup(g_sleep_time));

    return 0;
}

[ 本帖最后由 pangding 于 2012-6-16 01:33 编辑 ]

第 20 楼

得分:0

18楼、19楼的代码写的都很棒啊，膜拜版主。

各位高手给点评下啊。