免费注册 查看新帖 |

ChinaUnix.net

  平台 论坛 博客 文库 频道自动化运维 虚拟化 储存备份 C/C++ PHP MySQL 嵌入式 Linux系统
最近访问板块 发新帖
楼主: stone531

[C++] 某名互联网面试题,求各位大神给解 [复制链接]

论坛徽章:
131
操作系统版块每日发帖之星
日期:2016-05-11 17:06:57操作系统版块每日发帖之星
日期:2016-05-11 17:06:57数据库技术版块每日发帖之星
日期:2016-05-11 17:07:05操作系统版块每日发帖之星
日期:2016-05-11 17:06:57操作系统版块每日发帖之星
日期:2016-05-11 17:06:57综合交流区版块每日发帖之星
日期:2016-05-11 17:07:052022北京冬奥会纪念版徽章
日期:2015-08-07 17:10:57IT运维版块每日发帖之星
日期:2016-05-11 17:06:49操作系统版块每日发帖之星
日期:2016-05-11 17:06:57综合交流区版块每日发帖之星
日期:2016-05-11 17:07:05操作系统版块每日发帖之星
日期:2016-05-11 17:06:57程序设计版块每日发帖之星
日期:2016-05-11 17:06:57
发表于 2018-01-06 18:25 来自手机 |显示全部楼层
楼主确实没说清楚意思,没找到逻辑关系

论坛徽章:
131
操作系统版块每日发帖之星
日期:2016-05-11 17:06:57操作系统版块每日发帖之星
日期:2016-05-11 17:06:57数据库技术版块每日发帖之星
日期:2016-05-11 17:07:05操作系统版块每日发帖之星
日期:2016-05-11 17:06:57操作系统版块每日发帖之星
日期:2016-05-11 17:06:57综合交流区版块每日发帖之星
日期:2016-05-11 17:07:052022北京冬奥会纪念版徽章
日期:2015-08-07 17:10:57IT运维版块每日发帖之星
日期:2016-05-11 17:06:49操作系统版块每日发帖之星
日期:2016-05-11 17:06:57综合交流区版块每日发帖之星
日期:2016-05-11 17:07:05操作系统版块每日发帖之星
日期:2016-05-11 17:06:57程序设计版块每日发帖之星
日期:2016-05-11 17:06:57
发表于 2018-01-06 18:25 来自手机 |显示全部楼层
楼主确实没说清楚意思,没找到逻辑关系

论坛徽章:
131
操作系统版块每日发帖之星
日期:2016-05-11 17:06:57操作系统版块每日发帖之星
日期:2016-05-11 17:06:57数据库技术版块每日发帖之星
日期:2016-05-11 17:07:05操作系统版块每日发帖之星
日期:2016-05-11 17:06:57操作系统版块每日发帖之星
日期:2016-05-11 17:06:57综合交流区版块每日发帖之星
日期:2016-05-11 17:07:052022北京冬奥会纪念版徽章
日期:2015-08-07 17:10:57IT运维版块每日发帖之星
日期:2016-05-11 17:06:49操作系统版块每日发帖之星
日期:2016-05-11 17:06:57综合交流区版块每日发帖之星
日期:2016-05-11 17:07:05操作系统版块每日发帖之星
日期:2016-05-11 17:06:57程序设计版块每日发帖之星
日期:2016-05-11 17:06:57
发表于 2018-01-06 18:25 来自手机 |显示全部楼层
我还以为我姿势不对,原来楼主自己认了。。。也罢

论坛徽章:
6
数据库技术版块每日发帖之星
日期:2015-11-27 06:20:00程序设计版块每日发帖之星
日期:2015-12-01 06:20:00每日论坛发贴之星
日期:2015-12-01 06:20:0015-16赛季CBA联赛之佛山
日期:2017-03-26 23:38:0315-16赛季CBA联赛之江苏
日期:2017-07-17 10:08:4415-16赛季CBA联赛之北京
日期:2018-03-04 17:01:50
发表于 2018-01-06 21:40 |显示全部楼层
确实没看懂
估计没说清楚

论坛徽章:
36
子鼠
日期:2013-08-28 22:23:29黄金圣斗士
日期:2015-12-01 11:37:51程序设计版块每日发帖之星
日期:2015-12-14 06:20:00CU十四周年纪念徽章
日期:2015-12-22 16:50:40IT运维版块每日发帖之星
日期:2016-01-25 06:20:0015-16赛季CBA联赛之深圳
日期:2016-01-27 10:31:172016猴年福章徽章
日期:2016-02-18 15:30:3415-16赛季CBA联赛之福建
日期:2016-04-07 11:25:2215-16赛季CBA联赛之青岛
日期:2016-04-29 18:02:5915-16赛季CBA联赛之北控
日期:2016-06-20 17:38:50技术图书徽章
日期:2016-07-19 13:54:03程序设计版块每日发帖之星
日期:2016-08-21 06:20:00
发表于 2018-01-06 23:37 |显示全部楼层
回复 8# stone531

我好像没理解错你的意思,你没看懂我的意思。。。你再研究下。。。
No.1  
none就是0,你的a、b、c刚好可以转换成一个三位数作为数组下下标,先生成表,直接取下标查表,不用比较性能是最好的。
如果输入数据没有错误(比如idx超出表下标方位),那连idx合法的判断比较都不需要。
No.2
你的树的思路是错的。
因为aabb不是固定的词组,每两个字母之间是没有联系的。
你的那个树的思路叫trie或者字典树,常见的应用场景比如敏感词过滤算法。



论坛徽章:
6
数据库技术版块每日发帖之星
日期:2015-11-27 06:20:00程序设计版块每日发帖之星
日期:2015-12-01 06:20:00每日论坛发贴之星
日期:2015-12-01 06:20:0015-16赛季CBA联赛之佛山
日期:2017-03-26 23:38:0315-16赛季CBA联赛之江苏
日期:2017-07-17 10:08:4415-16赛季CBA联赛之北京
日期:2018-03-04 17:01:50
发表于 2018-01-07 14:21 |显示全部楼层
本帖最后由 dorodaloo 于 2018-01-07 14:26 编辑

保持好奇心多学习
第NO2题:  判断mode和content是否一致
出正确结果效率创新高峰

一致        aabb        北京 北京 上海 上海
不同        aabb        北京 上海 深圳 北京
一致        aabb        苹果 苹果 橘子 橘子
不同        aabb        苹果 苹果 橘子 橘子 橘子
不同        aabb        苹果 苹果 橘子
不同        aabb        苹果 苹果 橘子 橘子 上海

不同        abca        北京 北京 上海 上海
一致        abca        北京 上海 深圳 北京
不同        abca        苹果 苹果 橘子 橘子
不同        abca        苹果 苹果 橘子 橘子 橘子
不同        abca        苹果 苹果 橘子
不同        abca        苹果 苹果 橘子 橘子 上海

不同        abab        北京 北京 上海 上海
不同        abab        北京 上海 深圳 北京
不同        abab        苹果 苹果 橘子 橘子
不同        abab        苹果 苹果 橘子 橘子 橘子
不同        abab        苹果 苹果 橘子
不同        abab        苹果 苹果 橘子 橘子 上海

不同        aab        北京 北京 上海 上海
不同        aab        北京 上海 深圳 北京
不同        aab        苹果 苹果 橘子 橘子
不同        aab        苹果 苹果 橘子 橘子 橘子
一致        aab        苹果 苹果 橘子
不同        aab        苹果 苹果 橘子 橘子 上海

不同        bbcca        北京 北京 上海 上海
不同        bbcca        北京 上海 深圳 北京
不同        bbcca        苹果 苹果 橘子 橘子
不同        bbcca        苹果 苹果 橘子 橘子 橘子
不同        bbcca        苹果 苹果 橘子
一致        bbcca        苹果 苹果 橘子 橘子 上海


  1. #include <stdbool.h>
  2. #include <stdio.h>
  3. #include <string.h>
  4. #define WORDSIZE 20
  5. #define EQUAL(x, y) (!strcmp(x, y))
  6. #define EMPTY(x) (!(x)[0])

  7. bool equal(const char *, const char *);

  8. int main() {

  9.     char *mode[] = {"aabb", "abca", "abab", "aab", "bbcca"};
  10.     char *content[] = {
  11.         "北京 北京 上海 上海", "北京 上海 深圳 北京",
  12.         "苹果 苹果 橘子 橘子", "苹果 苹果 橘子 橘子 橘子",
  13.         "苹果 苹果 橘子",      "苹果 苹果 橘子 橘子 上海",
  14.     };

  15.     for (int i = 0; i < 5; i++) {
  16.         for (int j = 0; j < 6; j++) {
  17.             char *match = equal(mode[i], content[j]) ? "一致" : "不同";
  18.             printf("%s\t%s\t%s\n", match, mode[i], content[j]);
  19.         }
  20.         printf("\n");
  21.     }
  22. }

  23. bool equal(const char *mode, const char *content) {
  24.     typedef struct {
  25.         char key[WORDSIZE];
  26.         char value;
  27.     } Pair;

  28.     int lenMode = strlen(mode);
  29.     Pair check[lenMode];
  30.     memset(check, 0, sizeof check);
  31.     char word[WORDSIZE] = {0};
  32.     int position = 0;
  33.     const char *pc = content;
  34.     int j = 0;
  35.     while (*pc) {
  36.         sscanf(pc, "%s%n", word, &position);
  37.         for (int i = 0; i < lenMode; i++) {
  38.             if (EMPTY(check[i].key)) {
  39.                 strcpy(check[i].key, word);
  40.                 check[i].value = mode[j];
  41.                 break;
  42.             }
  43.             if (EQUAL(word, check[i].key)) {
  44.                 char value = check[i].value;
  45.                 if (value != mode[j])
  46.                     return false;
  47.                 break;
  48.             }
  49.         }
  50.         pc += position;
  51.         if (++j > lenMode)
  52.             return false;
  53.     }

  54.     return j == lenMode ? true : false;
  55. }
复制代码

论坛徽章:
36
子鼠
日期:2013-08-28 22:23:29黄金圣斗士
日期:2015-12-01 11:37:51程序设计版块每日发帖之星
日期:2015-12-14 06:20:00CU十四周年纪念徽章
日期:2015-12-22 16:50:40IT运维版块每日发帖之星
日期:2016-01-25 06:20:0015-16赛季CBA联赛之深圳
日期:2016-01-27 10:31:172016猴年福章徽章
日期:2016-02-18 15:30:3415-16赛季CBA联赛之福建
日期:2016-04-07 11:25:2215-16赛季CBA联赛之青岛
日期:2016-04-29 18:02:5915-16赛季CBA联赛之北控
日期:2016-06-20 17:38:50技术图书徽章
日期:2016-07-19 13:54:03程序设计版块每日发帖之星
日期:2016-08-21 06:20:00
发表于 2018-01-08 00:23 |显示全部楼层
本帖最后由 cokeboL 于 2018-01-08 00:29 编辑

No.2试下这个吧,我假定模式长度只有4,北京上海之类的都是两个中文,uint64够用了,如果实际场景更多更长,
稍微扩展下就好了,对比那块放到循环里更好些,困了懒得写了
  1. #include <stdio.h>
  2. #include <stdint.h>

  3. bool modeEqualConten(const char* mode, const char* content)
  4. {
  5.         uint64_t mc4[4] = { 0 };
  6.         char *pcontent = (char *)content, *tmpmc = 0;
  7.         for (int i = 0; i < 4; i++) {
  8.                 tmpmc = ((char*)&mc4[i]);
  9.                 *tmpmc++ = mode[i];
  10.                 while (*pcontent && *pcontent != ' ') {
  11.                         *tmpmc++ = *pcontent++;
  12.                 }
  13.                 pcontent++;
  14.         }

  15. #if 1
  16.         return
  17.                 ((*(char*)&mc4[1] == *(char*)&mc4[0]) == (mc4[1] >> 8 == mc4[0] >> 8)) &&

  18.                 ((*(char*)&mc4[2] == *(char*)&mc4[0]) == (mc4[2] >> 8 == mc4[0] >> 8)) &&
  19.                 ((*(char*)&mc4[2] == *(char*)&mc4[1]) == (mc4[2] >> 8 == mc4[1] >> 8)) &&

  20.                 ((*(char*)&mc4[3] == *(char*)&mc4[0]) == (mc4[3] >> 8 == mc4[0] >> 8)) &&
  21.                 ((*(char*)&mc4[3] == *(char*)&mc4[1]) == (mc4[3] >> 8 == mc4[1] >> 8)) &&
  22.                 ((*(char*)&mc4[3] == *(char*)&mc4[2]) == (mc4[3] >> 8 == mc4[2] >> 8));
  23. #else
  24.         if ((*(char*)&mc4[1] == *(char*)&mc4[0]) != (mc4[1] >> 8 == mc4[0] >> 8)) return false;

  25.         if ((*(char*)&mc4[2] == *(char*)&mc4[0]) != (mc4[2] >> 8 == mc4[0] >> 8)) return false;
  26.         if ((*(char*)&mc4[2] == *(char*)&mc4[1]) != (mc4[2] >> 8 == mc4[1] >> 8)) return false;

  27.         if ((*(char*)&mc4[3] == *(char*)&mc4[0]) != (mc4[3] >> 8 == mc4[0] >> 8)) return false;
  28.         if ((*(char*)&mc4[3] == *(char*)&mc4[1]) != (mc4[3] >> 8 == mc4[1] >> 8)) return false;
  29.         if ((*(char*)&mc4[3] == *(char*)&mc4[2]) != (mc4[3] >> 8 == mc4[2] >> 8)) return false;
  30. #endif
  31.         return true;
  32. }


  33. int main() {
  34.         printf("%d\n", modeEqualConten("aabb", "北京 北京 上海 上海"));
  35.         printf("%d\n", modeEqualConten("abca", "北京 上海 深圳 北京"));
  36.         printf("%d\n", modeEqualConten("acbb", "北京 北京 上海 上海"));
  37.         printf("%d\n", modeEqualConten("aaca", "北京 上海 深圳 北京"));
  38.         printf("%d\n", modeEqualConten("abcb", "北京 上海 深圳 北京"));
  39.         getchar();
  40. }
复制代码

评分

参与人数 1信誉积分 +9 收起 理由
dorodaloo + 9 偶像!偶像!

查看全部评分

论坛徽章:
6
数据库技术版块每日发帖之星
日期:2015-11-27 06:20:00程序设计版块每日发帖之星
日期:2015-12-01 06:20:00每日论坛发贴之星
日期:2015-12-01 06:20:0015-16赛季CBA联赛之佛山
日期:2017-03-26 23:38:0315-16赛季CBA联赛之江苏
日期:2017-07-17 10:08:4415-16赛季CBA联赛之北京
日期:2018-03-04 17:01:50
发表于 2018-01-08 19:36 |显示全部楼层
保持好奇心多学习
第NO1题:  
根据传参数,最后出正确结果。不使用比较,效率创新高。

NO1:

135        send to 上海
279        send to 北京
103        send to 上海
282        send to 深圳
284        send to 未知
333        send to 未知


  1. #include <stdio.h>
  2. #define CITY 10
  3. char *sendTo[CITY * CITY * CITY];
  4. const char *sendToCity(int a, int b, int c);
  5. void initSendTo(void);
  6. typedef struct {
  7.     int a;
  8.     int b;
  9.     int c;
  10. } Prouct;
  11. int main() {
  12.     initSendTo();
  13.     Prouct p[] = {{1, 3, 5}, {2, 7, 9}, {1, 0, 3},
  14.                   {2, 8, 2}, {2, 8, 4}, {3, 3, 3}};

  15.     int test = sizeof(p) / sizeof(Prouct);
  16.     for (int i = 0; i < test; i++) {
  17.         Prouct *t = &p[i];
  18.         const char *c = sendToCity(t->a, t->b, t->c);
  19.         printf("%d%d%d\tsend to %s\n", t->a, t->b, t->c, c);
  20.     }
  21. }

  22. const char *sendToCity(int a, int b, int c) {
  23.     char *city = sendTo[a * CITY * CITY + b * CITY + c];
  24.     return city ? city : "未知";
  25. }

  26. void initSendTo(void) {
  27.     // rule 1:
  28.     // rule 2
  29.     for (int i = 200; i <= 299; i++)
  30.         if (i % 10 == 9)
  31.             sendTo[i] = "北京";
  32.     // rule 3
  33.     for (int i = 100; i <= 199; i++)
  34.         sendTo[i] = "上海";
  35.     // rule 4
  36.     sendTo[282] = "深圳";
  37. }
复制代码

论坛徽章:
0
发表于 2018-01-10 22:09 |显示全部楼层
回复 17# cokeboL

估计是想要一个通用的办法,mode 和content的长度都不限制。只是按照空格来区分。还是很有难度的。

论坛徽章:
0
发表于 2018-01-10 22:13 |显示全部楼层
回复 18# dorodaloo

第一道题应该可以这么弄
您需要登录后才可以回帖 登录 | 注册

本版积分规则 发表回复

数据风云,十年变迁
DTCC 第十届中国数据库技术大会已启航!

2019年5月8日~5月10日,由IT168旗下ITPUB企业社区平台主办的第十届中国数据库技术大会(DTCC2019),将在北京隆重召开。大会将邀请百余位行业专家,就热点技术话题进行分享,是广大数据领域从业人士的又一次年度盛会和交流平台。与SACC2018类似,本届大会将采用“3+2”模式:3天传统技术演讲+2天深度主题培训。大会不仅提供超100场的主题演讲,还会提供连续2天的深度课程培训,深化数据领域的项目落地实践方案。
DTCC2019,一场值得期待的数据技术盛会,殷切地希望您报名参与!

活动入口>>
  

北京盛拓优讯信息技术有限公司. 版权所有 16024965号-6 北京市公安局海淀分局网监中心备案编号:11010802020122
中国互联网协会会员  联系我们:huangweiwei@it168.com
感谢所有关心和支持过ChinaUnix的朋友们 转载本站内容请注明原作者名及出处

清除 Cookies - ChinaUnix - Archiver - WAP - TOP