免费注册 查看新帖 |

Chinaunix

  平台 论坛 博客 文库
最近访问板块 发新帖
楼主: Susake_

[算法] 讨论下这几种算法[寻高效的算法] [复制链接]

论坛徽章:
11
巨蟹座
日期:2013-12-23 11:12:14双子座
日期:2014-08-28 09:14:55子鼠
日期:2014-07-25 16:21:22摩羯座
日期:2014-07-23 15:17:47摩羯座
日期:2014-05-30 13:09:05午马
日期:2014-04-30 18:10:00天秤座
日期:2014-04-25 12:12:00申猴
日期:2014-04-22 11:30:15午马
日期:2014-03-07 16:06:40辰龙
日期:2013-12-25 18:36:00摩羯座
日期:2014-09-02 17:00:55
发表于 2014-09-09 15:20 |显示全部楼层
回复 10# ID好难
说到线段树还真想试试(应该算是第一次有这种冲动)~一直都觉得线段树的代码太多!


   

论坛徽章:
1
亥猪
日期:2014-09-10 11:43:17
发表于 2014-09-10 09:53 |显示全部楼层
ID好难 发表于 2014-09-09 15:00
回复 7# Susake_

很显然二分写的不够好。 用线段树也可以解决这个问题吧,如果是动态插入查询,二分就不 ...


回复的是7楼,那你指的应该是第一题吧。何以见得这二分显然不够好呢?烦请好好说明一下。同时很想看看你用线段树怎么解决,最好附上代码。

论坛徽章:
0
发表于 2014-09-10 11:29 |显示全部楼层
回复 2# Susake_

你好楼主,求指点,没想明白为什么可以用二分,因为您题目里面没有说是有序的啊?
   
谢谢。

论坛徽章:
0
发表于 2014-09-10 12:52 |显示全部楼层
Kurosaki_Ichigo 发表于 2014-09-10 09:53
回复的是7楼,那你指的应该是第一题吧。何以见得这二分显然不够好呢?烦请好好说明一下。同时很想看看你 ...

回复 12# Kurosaki_Ichigo

二分可以用STL 里面的lower_bound/upper_bound。
线段树应该比较容易理解吧,在区间 [a,b] 中添加一个count 来记录区间[a,b]中一共有多少个数字, 查询序列中比ai大的有几个,相当于查询区间[ai, 最大上限] 有多少个数。

论坛徽章:
1
亥猪
日期:2014-09-10 11:43:17
发表于 2014-09-10 13:38 |显示全部楼层
ID好难 发表于 2014-09-10 12:52
回复 12# Kurosaki_Ichigo

二分可以用STL 里面的lower_bound/upper_bound。
线段树应该比较容易理解吧,在区间 [a,b] 中添加一个count 来记录区间[a,b]中一共有多少个数字, 查询序列中比ai大的有几个,相当于查询区间[ai, 最大上限] 有多少个数。

呵呵一维数组的查找还用的着线段树?要是你听说过区间树会不会觉得它更适合呢?

这样吧,咱别光停留在嘴上,针对第一题你写段线段树的代码,只要能得出正确的结果,不论效率如何,我把我所有的积分都送你。也不限语言,用你最称手的。

论坛徽章:
11
巨蟹座
日期:2013-12-23 11:12:14双子座
日期:2014-08-28 09:14:55子鼠
日期:2014-07-25 16:21:22摩羯座
日期:2014-07-23 15:17:47摩羯座
日期:2014-05-30 13:09:05午马
日期:2014-04-30 18:10:00天秤座
日期:2014-04-25 12:12:00申猴
日期:2014-04-22 11:30:15午马
日期:2014-03-07 16:06:40辰龙
日期:2013-12-25 18:36:00摩羯座
日期:2014-09-02 17:00:55
发表于 2014-09-10 13:54 |显示全部楼层
本帖最后由 Susake_ 于 2014-09-10 14:51 编辑
qiwei9743 发表于 2014-09-10 11:29
回复 2# Susake_

你好楼主,求指点,没想明白为什么可以用二分,因为您题目里面没有说是有序的啊?

是无序的!
可能你是单单就一次查询看的,而我考虑的是动态查询~
顺便试了试你说的upper_bound

  1. #include <bits/stdc++.h>

  2. std::vector <int> A(5);

  3. int main(int argc, char *argv[])
  4. {
  5.     A[0] = 1;A[1] = 2;A[2] = 3;A[3] = 3;A[4] = 5;
  6.     for(int i = 0; i < A.size(); i++)
  7.         std::cout << A.size() - (upper_bound(A.begin(), A.end(), A[i]) - A.begin()) << "\n";
  8.         return 0;
  9. }
复制代码

论坛徽章:
11
巨蟹座
日期:2013-12-23 11:12:14双子座
日期:2014-08-28 09:14:55子鼠
日期:2014-07-25 16:21:22摩羯座
日期:2014-07-23 15:17:47摩羯座
日期:2014-05-30 13:09:05午马
日期:2014-04-30 18:10:00天秤座
日期:2014-04-25 12:12:00申猴
日期:2014-04-22 11:30:15午马
日期:2014-03-07 16:06:40辰龙
日期:2013-12-25 18:36:00摩羯座
日期:2014-09-02 17:00:55
发表于 2014-09-10 15:10 |显示全部楼层
感觉第一题还能将难度提升,那就是将操作改为   (动态插入,删除,查询)~^_^

论坛徽章:
0
发表于 2014-09-10 15:13 |显示全部楼层
回复 15# Kurosaki_Ichigo


    我说的是可以用线段树,并且它可以处理动态插入查询的情况。这个问题应该也可以用树状数组来写
    呵呵,成约架了。。。不至于,你太认真了。。。

论坛徽章:
2
2015年辞旧岁徽章
日期:2015-03-03 16:54:152015年迎新春徽章
日期:2015-03-04 09:56:11
发表于 2014-09-10 15:15 |显示全部楼层
算法5没有发现在哪里。算法4有问题。
  1. /* number.c */

  2. #include <ctype.h>
  3. #include <stdio.h>
  4. #include <stdlib.h>
  5. #include <string.h>

  6. #define ALEN(a) (sizeof(a)/sizeof((a)[0]))

  7. int get_line(char *buf, int buf_len, int *o_len)
  8. {
  9.         if (fgets(buf, buf_len, stdin) != NULL) {
  10.                 if (o_len != NULL) {
  11.                         *o_len = strlen(buf);
  12.                 }
  13.                 return 0;
  14.         }
  15.         return -1;
  16. }

  17. int get_number(const char *s, int off, int lmt, int *o_off, int *o_val)
  18. {
  19.         const char *pstart;
  20.         char *pend;
  21.         int len;
  22.         long value;

  23.         if (off < lmt) {
  24.                 pstart = s + off;
  25.                 pend = (char *)pstart;
  26.                 value = strtol(pstart, &pend, 10);
  27.                 if (pend != pstart) {
  28.                         len = pend - s;
  29.                         if (len <= lmt) {
  30.                                 *o_off = len;
  31.                                 *o_val = value;
  32.                                 return 0;
  33.                         }
  34.                 }
  35.         }
  36.         return -1;
  37. }

  38. int get_numbers(const char *text, int *o_array, int a_len, int *o_len)
  39. {
  40.         char line_buf[256];
  41.         int lmt;
  42.         int off;
  43.         int i;

  44.         printf("%s: ", text == NULL ? "" : text);
  45.         if (get_line(line_buf, sizeof(line_buf), &lmt) == 0) {
  46.                 off = 0;
  47.                 for (i = 0; i < a_len; ++i) {
  48.                         if (get_number(line_buf, off, lmt, &off, &o_array[i]) == 0) {
  49.                                 continue;
  50.                         }
  51.                         break;
  52.                 }
  53.                 if (i > 0) {
  54.                         if (o_len != NULL) {
  55.                                 *o_len = i;
  56.                         }
  57.                         return 0;
  58.                 }
  59.         }
  60.         return -1;
  61. }

  62. int select_menu(void)
  63. {
  64.         const char *menu_text[] = {
  65.                 "1 input numbers and query greater numbers",
  66.                 "2 input double column numbers and query greater numbers",
  67.                 "3 input triple column numbers and query greater numbers",
  68.                 "4 input numbers and do operations",
  69.                 "5",
  70.                 "6 quit",
  71.         };
  72.         int i;
  73.         int val;

  74.         for (;;) {
  75.                 for (i = 0; i < ALEN(menu_text); ++i) {
  76.                         puts(menu_text[i]);
  77.                 }
  78.                 if (get_numbers("Please input the menu number", &val, 1, NULL) == 0) {
  79.                         if (val >= 1 && val <= ALEN(menu_text)) {
  80.                                 return val;
  81.                         }
  82.                 }
  83.                 puts("ERROR: invalid input, input again");
  84.         }
  85. }

  86. int compare_numbers(const int *num1, const int *num2, int cnt)
  87. {
  88.         int i;

  89.         for (i = 0; i < cnt; ++i) {
  90.                 if (num1[i] <= num2[i]) {
  91.                         return 0;
  92.                 }
  93.         }
  94.         return 1;
  95. }

  96. int query_123(const int *ai, int n, const int *num, int cnt)
  97. {
  98.         int i;
  99.         int counter;
  100.        
  101.         counter = 0;
  102.         for (i = 0; i < n; ++i) {
  103.                 if (compare_numbers(ai + i * cnt, num, cnt)) {
  104.                         ++counter;
  105.                 }
  106.         }
  107.         return counter;
  108. }

  109. int do_menu_123(int cnt)
  110. {
  111.         int n;
  112.         int m;
  113.         int num[3];
  114.         int i;
  115.         int len;
  116.         int *ai;
  117.         int *result;

  118.         if (get_numbers(NULL, &n, 1, NULL) == 0 && n > 0) {
  119.                 ai = (int *)malloc(n * sizeof(int) * cnt);
  120.                 if (ai != NULL) {
  121.                         memset(ai, 0, n * sizeof(int) * cnt);
  122.                         if (cnt == 1) {
  123.                                 for (;;) {
  124.                                         if (get_numbers(NULL, ai, n, &len) == 0 && len == n) {
  125.                                                 break;
  126.                                         }
  127.                                 }
  128.                         }else {
  129.                                 for (i = 0; i < n;) {
  130.                                         if (get_numbers(NULL, ai + i * cnt, cnt, &len) == 0 && len == cnt) {
  131.                                                 ++i;
  132.                                         }
  133.                                 }
  134.                         }
  135.                         if (get_numbers(NULL, &m, 1, NULL) == 0 && m > 0) {
  136.                                 result = (int *)malloc(m * sizeof(int));
  137.                                 if (result != NULL) {
  138.                                         memset(result, 0, sizeof(int) * m);
  139.                                         for (i = 0; i < m;) {
  140.                                                 if (get_numbers(NULL, num, cnt, NULL) == 0) {
  141.                                                         result[i++] = query_123(ai, n, num, cnt);
  142.                                                 }
  143.                                         }
  144.                                         for (i = 0; i < m; ++i) {
  145.                                                 printf("%d\n", result[i]);
  146.                                         }
  147.                                         free(result);
  148.                                 }
  149.                         }
  150.                         free(ai);
  151.                 }
  152.         }
  153.         return 0;
  154. }

  155. int get_identifier(const char *s, int off, int lmt, int *o_off)
  156. {
  157.         if (isalpha(s[off])) {
  158.                 do {
  159.                         ++off;
  160.                 }while (isalpha(s[off]) || isdigit(s[off]));
  161.                 *o_off = off;
  162.                 return 0;
  163.         }
  164.         return -1;
  165. }

  166. int get_space(const char *s, int off, int lmt, int *o_off)
  167. {
  168.         if (isspace(s[off])) {
  169.                 do {
  170.                         ++off;
  171.                 }while (isspace(s[off]));
  172.                 *o_off = off;
  173.                 return 0;
  174.         }
  175.         return -1;
  176. }

  177. int compare_text(const char *s, int off, int lmt, const char *tab[], int tab_len)
  178. {
  179.         int len;
  180.         int i;

  181.         for (i = 0; i < tab_len; ++i) {
  182.                 len = strlen(tab[i]);
  183.                 if (off + len == lmt && strncmp(s + off, tab[i], len) == 0) {
  184.                         return i;
  185.                 }
  186.         }
  187.         return -1;
  188. }

  189. int do_menu_4(void)
  190. {
  191.         char line_buf[256];
  192.         const char *cmd[] = {"a", "d", "q"};
  193.         const char *var[] = {"a1", "a2"};
  194.         int a1, a2;
  195.         int lmt;
  196.         int off;
  197.         int next;
  198.         int cmd_id;
  199.         int p1;
  200.         int p2;
  201.         int val;
  202.         int n;
  203.         int i;

  204.         a1 = 0;
  205.         a2 = 0;
  206.         if (get_numbers(NULL, &n, 1, NULL) == 0) {
  207.                 for (i = 0; i < n; ++i) {
  208.                         if (get_line(line_buf, sizeof(line_buf), &lmt) == 0) {
  209.                                 off = 0;
  210.                                 get_space(line_buf, off, lmt, &off);
  211.                                 if (get_identifier(line_buf, off, lmt, &next) == 0) {
  212.                                         cmd_id = compare_text(line_buf, off, next, cmd, ALEN(cmd));
  213.                                         if (cmd_id != -1) {
  214.                                                 off = next;
  215.                                                 switch (cmd_id) {
  216.                                                 case 0:
  217.                                                         get_space(line_buf, off, lmt, &off);
  218.                                                         if (get_identifier(line_buf, off, lmt, &next) == 0) {
  219.                                                                 cmd_id = compare_text(line_buf, off, next, var, ALEN(var));
  220.                                                                 if (cmd_id != -1) {
  221.                                                                         off = next;
  222.                                                                         if (get_number(line_buf, off, lmt, &off, &val) == 0) {
  223.                                                                                 switch (cmd_id) {
  224.                                                                                 case 0:
  225.                                                                                         a1 += val;
  226.                                                                                         break;
  227.                                                                                 case 1:
  228.                                                                                         a2 += val;
  229.                                                                                         break;
  230.                                                                                 }
  231.                                                                         }
  232.                                                                 }
  233.                                                         }
  234.                                                         break;
  235.                                                 case 1:
  236.                                                         get_space(line_buf, off, lmt, &off);
  237.                                                         if (get_identifier(line_buf, off, lmt, &next) == 0) {
  238.                                                                 cmd_id = compare_text(line_buf, off, next, var, ALEN(var));
  239.                                                                 if (cmd_id != -1) {
  240.                                                                         off = next;
  241.                                                                         if (get_number(line_buf, off, lmt, &off, &val) == 0) {
  242.                                                                                 switch (cmd_id) {
  243.                                                                                 case 0:
  244.                                                                                         a1 -= val;
  245.                                                                                         break;
  246.                                                                                 case 1:
  247.                                                                                         a2 -= val;
  248.                                                                                         break;
  249.                                                                                 }
  250.                                                                         }
  251.                                                                 }
  252.                                                         }
  253.                                                         break;
  254.                                                 case 2:
  255.                                                         get_space(line_buf, off, lmt, &off);
  256.                                                         if (get_identifier(line_buf, off, lmt, &next) == 0) {
  257.                                                                 p1 = compare_text(line_buf, off, next, var, ALEN(var));
  258.                                                                 if (p1 != -1) {
  259.                                                                         off = next;
  260.                                                                         get_space(line_buf, off, lmt, &off);
  261.                                                                         if (get_identifier(line_buf, off, lmt, &next) == 0) {
  262.                                                                                 p2 = compare_text(line_buf, off, next, var, ALEN(var));
  263.                                                                                 if (p2 != -1) {
  264.                                                                                 }
  265.                                                                         }else {
  266.                                                                                 switch (p1) {
  267.                                                                                 case 0:
  268.                                                                                         printf("%d\n", a1);
  269.                                                                                         break;
  270.                                                                                 case 1:
  271.                                                                                         printf("%d\n", a2);
  272.                                                                                         break;
  273.                                                                                 }
  274.                                                                         }
  275.                                                                 }
  276.                                                         }
  277.                                                         break;
  278.                                                 }
  279.                                         }
  280.                                 }
  281.                         }
  282.                 }
  283.         }
  284.         return 0;
  285. }

  286. int main(void)
  287. {
  288.         int menu_do;

  289.         for (;;) {
  290.                 menu_do = select_menu();
  291.                 switch (menu_do) {
  292.                 case 1:
  293.                         do_menu_123(1);
  294.                         break;
  295.                 case 2:
  296.                         do_menu_123(2);
  297.                         break;
  298.                 case 3:
  299.                         do_menu_123(3);
  300.                         break;
  301.                 case 4:
  302.                         do_menu_4();
  303.                 case 5:
  304.                         break;
  305.                 case 6:
  306.                         return 0;
  307.                 }
  308.         }
  309. }
复制代码

论坛徽章:
11
巨蟹座
日期:2013-12-23 11:12:14双子座
日期:2014-08-28 09:14:55子鼠
日期:2014-07-25 16:21:22摩羯座
日期:2014-07-23 15:17:47摩羯座
日期:2014-05-30 13:09:05午马
日期:2014-04-30 18:10:00天秤座
日期:2014-04-25 12:12:00申猴
日期:2014-04-22 11:30:15午马
日期:2014-03-07 16:06:40辰龙
日期:2013-12-25 18:36:00摩羯座
日期:2014-09-02 17:00:55
发表于 2014-09-10 15:51 |显示全部楼层
前段时间,听说一个流言,不知道是不是真的?
线段树一般能解决树状数组的问题(这个是树状数组百度百科上说的)
伸展树能解决线段树部分线段树的功能和某些线段树不能完成的功能(至于啥功能不太确定,没真正用过splay)
为此我翻扩展库里面的树结构(没有线段树,但有伸展树,红黑树这些),发现里面有一个,但至今没用上过,也不知道那个作者写来用什么用的?贴出来分享下~
以下是几个简单的操作,其他的也可以套STL里面的那些insert,erase什么
  1. #include <bits/stdc++.h>
  2. #include <ext/pb_ds/assoc_container.hpp>
  3. #include <ext/pb_ds/priority_queue.hpp>
  4. #include <ext/pb_ds/tree_policy.hpp>
  5. #include <ext/pb_ds/trie_policy.hpp>

  6. std::priority_queue <int> pr_q;__gnu_pbds::trie <std::string, int> trie_t;
  7. __gnu_pbds::tree <int, int, std::less<int>, __gnu_pbds::splay_tree_tag, __gnu_pbds::tree_order_statistics_node_update> sp_t;
  8. __gnu_pbds::priority_queue<std::pair <int, int>,std::greater<std::pair <int, int> >, __gnu_pbds::pairing_heap_tag > pa_h;

  9. int main(int argc, char *argv[])
  10. {
  11.     for(int i = 0; i < 3; i++) sp_t[i] = i + 5;
  12.     for(int i = 0; i < 3; i++)
  13.         printf("%d %d\n", sp_t.find_by_order(i) -> first, sp_t.find_by_order(i) -> second);
  14.         return 0;
  15. }
复制代码
您需要登录后才可以回帖 登录 | 注册

本版积分规则 发表回复

SACC2019中国系统架构师大会

【数字转型 架构演进】SACC2019中国系统架构师大会
2019年10月31日~11月2日第11届中国系统架构师大会(SACC2019)将在北京隆重召开。四大主线并行的演讲模式,1个主会场、20个技术专场、超千人参与的会议规模,100+来自互联网、金融、制造业、电商等领域的嘉宾阵容,将为广大参会者提供一场最具价值的技术交流盛会。




----------------------------------------

大会官网>>
  

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

清除 Cookies - ChinaUnix - Archiver - WAP - TOP