题意:
如果射出的球击中球链,且此时生成的新链中相同颜色的球大于等于3个。则这些球可以被消除。
例如,你有一串链是:。此时你射出一个2的球,球击中了链中的第一个2(第3个球),此时链变成:
因为中间的2有3个,满足消除的条件,他们会被消除,于是你获得:
1133
消除可以连击,例如:,射出2还是击中第一个2。此时链变成,消除2后,链变成:
前后两串1拼接在一起后,形成四个1,又满足消除条件,继续消除,得到:
33
注意连击只能发生在重新拼接的场合,如果原来的链就可以消除,不是通过拼接达到消除条件,则不能消除。
举例来说:
当前链是,射出2击中第一个2,此时中间形成3个2:,2个2被消除,得到。
尽管此时前后的1和3都满足消除条件,但他们不是拼接之后达到消除条件的,因此不能产生连击,最后的结果就是:
基于上述的要求,我们将球组织成带头节点的双向循环链表的形式。请你编写消除的函数完成消除工作。
思路:
①创建两个指针分别指向与插入点相同数字的最前与最后处。若与插入球相同的球≥3则消除相同的球,否则直接退出。
②第一步删除相同球后,如果p,n指针重合,说明已经无球,退出;或者p的数字不等于n的数字,说明无法消除,也退出。若没进上述情况,则将node更新为p或n(若p没指向头节点则更新为p否则更新为n)。
源码:
//struct DUAL_NODE { // DUAL_NODE* prev; // DUAL_NODE* next; // int color; //}; void hit_zuma_chain(DUAL_NODE* head, DUAL_NODE* node) { while (1) { int num = 0; DUAL_NODE* p = node->prev; DUAL_NODE* n = node->next; while (node->color == p->color && p != head) { //指向与插入点相同的最前面一个球 p = p->prev; num++; } while (node->color == n->color && n != head) { //指向与插入点相同的最后面一个球 n = n->next; num++; } if (num > 1) { //若能消除 while (p->next != n) { //消除相同球 DUAL_NODE* t = p->next; p->next = t->next; t->next->prev = p; delete t; } p->next = n; //更新p与n指针 n->prev = p; if (n == p || n->color != p->color) //判断循环能否继续 break; if (p != head) //更新插入点指针 node = p; else node = n; } else break; } }
讯享网
ps:无

版权声明:本文内容由互联网用户自发贡献,该文观点仅代表作者本人。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如发现本站有涉嫌侵权/违法违规的内容,请联系我们,一经查实,本站将立刻删除。
如需转载请保留出处:https://51itzy.com/kjqy/78097.html