剑指Offer（数据结构与算法面试题精讲）C++版——day10

题目一：展平多级双向链表

    分析可知，这里需要使用到递归，因为孩子节点中可能还包含有需要展平的子链。这里的关键在于确定好每一次unfoldList调用之后的最后节点，因为将多级链表合并成一个链之后，还需要补充维护最后一个节点的指向。比如这里示例中的第二级链表，将567三个节点插入到2和3节点之间需要补充修改2节点和3节点的指向，2与5节点构成前后关系，7和3节点构成前后关系。对边界分析，我们这里记录的最后节点有两种情况：（1）第一级链表的最后节点；（2）第二级链表的最后节点。并且第二种情况的最后节点的优先级更大，也就是说第一级链表的最后节点恰好有需要展开的子链，那么最后的tail应该是第二季的最后节点（当然这里是存在递归向后一级展开的关系），因此将tail=unfoldList(p->child)的赋值后移。这里可能稍微有一点绕，但是其实还是好理解的。

linkList unfoldList(linkList head) {linkNode * p=head,*next=nullptr,*tail=nullptr;while(p) {next=p->next;if(!p->next) {//收集最后一个元素，修改最后一个节点指针指向 tail=p;}if(p->child) {tail=unfoldList(p->child);//在下一层级继续展开 p->next=p->child;p->child->pre=p;tail->next=next;next->pre=tail;}p=next;}return tail;
}

题目二：排序的循环链表

    这道题其实重点是边界处理，观察这里循环链表可以发现，我们插入4节点的时候只需要去找到链表中的节点值满足，pre<=cur<=next 这样的一对节点即可，然后将新节点插入到其中。但是需要兼顾到边界，比如这里插入一个节点是100或者0，那么找不到这样的一对定界节点。这种情况依旧可以标识，因为我们可以发现，节点在遍历一次循环链之后又回到了原始头节点，因此这两种都可以统一成一种情况，那就是tail<=cur<=head，其中这里的cur表示的是当前遍历的节点，head表示的是重复遍历到的头节点。于是可以得到如下代码：

void addLinkNode(linkList head,int data) {linkNode *cur=new linkNode(data),*p=head,*next=nullptr;if(!head) {//处理边界情况，可能循环链表一开始为空head=cur;head->next=head;return ;} else {while(!(p->data<=data&&data<=p->next->data)&&(p->next!=head)) {p=p->next;}next=p->next;p->next=cur;cur->next=next;}
}

题目三：变位词组

    这是一道关于hash表的题目，前面也出现过类似的变位词题目，但要求不同，要么判断是否含有变位词，要么找到字符串中所有变位词的下标，但是采用的是hash表记录每个字母出现的次数和个数，然后借助于双指针法来处理的。如果还是使用前面的hash表+双指针法有些复杂。
    这里给出两种新方法：（1）直接对每个单词排序，然后映射，比如"eat"和"tea"映射之后变成了"aet"=>[“eat”,“tea”]；（2）使用映射，将26个字母都映射成最小的26个质数，然后将每个字符串相乘，作为这个字符串的值，比如说arr[‘a’-‘z’]={2, 3, 5, …, 89, 97, 101}，比如"eat"和"tea"映射之后变成了"aet"=>21171=1562=>[“eat”,“tea”]，需要注意的是，这种方法存在一定缺陷。若字符串较长，乘积结果会非常大，很可能超出long long int的表示范围。或许有人会考虑使用小数，但这同样不可行，因为会出现精度丢失的问题。
    因此，这里还是使用排序+hasd表的方式，得到如下代码：

# include <iostream>
# include <unordered_map>
# include <algorithm>
using namespace std;
vector<vector<string>>groupWords(vector<string> strs) {unordered_map<string,vector<string>> strMap;vector<vector<string>> result;for(const string& str : strs) {string strSort=str;sort(strSort.begin(),strSort.end());strMap[strSort].push_back(str);}for(const auto& pair:strMap) {result.push_back(pair.second);}return result;
}
void printGroupWords(vector<vector<string>> result) {for(const vector<string> & vec:result) {for(const string str:vec) {cout<<str<<" ";}cout<<endl;}
}
int main() {vector<string> words= {"eat", "tea", "tan", "ate", "nat", "bat"};vector<vector<string>>result= groupWords(words);printGroupWords(result);return 0;
}

附录：源码gitee仓库

    考虑到有些算法需要模拟数据，如果全部放进来代码显得过长，不利于聚焦在算法的核心思路上。于是把所有的代码整理到了开源仓库上，如果想要看详细模拟数据，可在开源仓库自取：【凌空暗羽/剑指offer-C++版手写代码】。

    我是【Jerry说前后端】，本系列精心挑选的算法题目全部基于经典的《剑指 Offer（数据结构与算法面试题精讲）》。在如今竞争激烈的技术求职环境下，算法能力已成为前端开发岗位笔试考核的关键要点。通过深入钻研这一系列算法题，大家能够系统地积累算法知识和解题经验。每一道题目的分析与解答过程，都像是一把钥匙，为大家打开一扇通往高效编程思维的大门，帮助大家逐步提升自己在数据结构运用、算法设计与优化等方面的能力。
    无论是即将踏入职场的应届毕业生，还是想要进一步提升自己技术水平的在职开发者，掌握扎实的算法知识都是提升竞争力的有力武器。希望大家能跟随我的步伐，在这个系列中不断学习、不断进步，为即将到来的前端笔试做好充分准备，顺利拿下心仪的工作机会！快来订阅吧，让我们一起开启这段算法学习之旅！