剑指offer 算法 （分解让复杂问题简单）

题目描述

输入一个复杂链表（每个节点中有节点值，以及两个指针，一个指向下一个节点，另一个特殊指针指向任意一个节点）。

解析：
分三步：
第一步：cloneList(pHead);复制链表，每个节点后新连接一个复制的自己的节点，random先置空；
第二步：connectRandom(pHead);依次给每个新节点的random连接
第三步：return apartList(pHead);把新建的结点按链表分离出来

/* struct RandomListNode {int label;struct RandomListNode *next, *random;RandomListNode(int x) :label(x), next(NULL), random(NULL) {} }; */ class Solution { public:RandomListNode* Clone(RandomListNode* pHead){cloneList(pHead);connectRandom(pHead);return apartList(pHead);}void cloneList(RandomListNode* pHead){RandomListNode* node;node=pHead;while(node!=NULL){RandomListNode* newNode;newNode=(RandomListNode*)malloc(sizeof(RandomListNode));newNode->label=node->label;newNode->random=NULL;newNode->next=node->next;node->next=newNode;node=newNode->next;}}void connectRandom(RandomListNode* pHead){RandomListNode* node;node=pHead;while(node!=NULL){RandomListNode* newNode;newNode=(RandomListNode*)malloc(sizeof(RandomListNode));newNode=node->next;if(node->random!=NULL){newNode->random=node->random->next;}node=newNode->next;}}RandomListNode* apartList(RandomListNode* pHead){RandomListNode* node=pHead;RandomListNode* cloneNode=NULL;RandomListNode* cloneList=NULL;if(node!=NULL){cloneNode=node->next;cloneList=cloneNode;node->next=cloneList->next;node=node->next;}while(node!=NULL){cloneNode->next=node->next;cloneNode=cloneNode->next;node->next=cloneNode->next;node=node->next;}return cloneList;} };
题目描述

输入一棵二叉搜索树，将该二叉搜索树转换成一个排序的双向链表。要求不能创建任何新的结点，只能调整树中结点指针的指向。

解析：根据二叉搜索树的特点，中序遍历正好由树的最小值搜到最大值；每当搜到一个点，加入链表；用lastNode保存当前的链表尾。

/* struct TreeNode {int val;struct TreeNode *left;struct TreeNode *right;TreeNode(int x) :val(x), left(NULL), right(NULL) {} };*/ class Solution { public:TreeNode* Convert(TreeNode* pRootOfTree){TreeNode* lastNode=NULL;//链表尾convertList(pRootOfTree,&lastNode);//递归完lastHead为链表尾 so向左不断搜索直到链表头TreeNode* listHead=lastNode;while(listHead!=NULL&&listHead->left!=NULL)listHead=listHead->left;return listHead;}void convertList(TreeNode* pRootOfTree,TreeNode** lastNode){if(pRootOfTree==NULL)return;TreeNode* current=pRootOfTree;if(current->left)convertList(current->left,lastNode);current->left=*lastNode;if(*lastNode!=NULL)(*lastNode)->right=current;*lastNode=current;//更新lastNodeif(current->right)convertList(current->right,lastNode);} };
题目描述

输入一个字符串,按字典序打印出该字符串中字符的所有排列。例如输入字符串abc,则打印出由字符a,b,c所能排列出来的所有字符串abc,acb,bac,bca,cab和cba。
输入描述:
输入一个字符串,长度不超过9(可能有字符重复),字符只包括大小写字母。]

解析：字符串逐个逐个字母替换，每个字母替换时逐个循环未使用的字符

class Solution { public:vector<string> Permutation(string str) {vector<string> v;if(str.empty())return v;Permutation(v,str,0);return v;}void Permutation(vector<string> &v,string str,int cnt){int size=str.size();if(cnt==str.size()-1)v.push_back(str);else{Permutation(v,str,cnt+1);for(int i=cnt+1;i<size;i++){if(str[i]!=str[cnt]){char ch=str[i];str[i]=str[cnt];str[cnt]=ch;Permutation(v,str,cnt+1);}}}} };

总结

以上是生活随笔为你收集整理的剑指offer 算法 （分解让复杂问题简单）的全部内容，希望文章能够帮你解决所遇到的问题。

如果觉得生活随笔网站内容还不错，欢迎将生活随笔推荐给好友。