分治法，分而治之。
面试题26：复杂链表的复制
请实现函数ComplexListNode* Clone(ComplexListNode*pHead)复制一个复杂链表。在复杂链表中，每个节点除了一个m_pNext指针指向下一节点，还有一个m_pSibling指向链表中的任意节点或者NULL。结点的c++定义如下：
struct ComplexListNode{ int m_nValue; ComplexListNode* m_pNext; ComplexListNode* m_pSibling; }leetcode链接 https://leetcode-cn.com/problems/copy-list-with-random-pointer/
/* // Definition for a Node. class Node { public: int val; Node* next; Node* random; Node(int _val) { val = _val; next = NULL; random = NULL; } }; */ class Solution { public: Node* copyRandomList(Node* head) { if (head == NULL) { return NULL; } Node* tmp = head; // 用于遍历的临时指针 // 第一步，先复制链表，同时将新节点依次插到其复制节点后面 while(tmp != NULL) { // cout << tmp->val << " "; Node* node = new Node(tmp->val); node->next = tmp->next; // 新建节点next转化为原节点next，实现插入 tmp->next = node; // 原节点next转化为当前新建节点 tmp = node->next; } // tmp = head; /* 验证下复制完的对不对 while(tmp != NULL) { cout << tmp->val << " "; tmp = tmp->next; } */ // 第二步：开始复制随机指针 tmp = head; while(tmp != NULL) { // cout << tmp->val << " "; if (tmp->random == NULL) { tmp = tmp->next->next; continue; } tmp->next->random = tmp->random->next; tmp = tmp->next->next; } // 第三步，进行拆分 Node* newHead = head->next; tmp = head; Node* tmp2 = newHead; while(tmp != NULL && tmp2 != NULL) { tmp->next = tmp2->next; tmp = tmp2->next; if (tmp == NULL) { break; } tmp2->next = tmp->next; tmp2 = tmp2->next; } tmp2->next = NULL; return newHead; } };
解题思路：简单想法是将复制过程分为两步：第一步，从前往后创建节点，完成next指针复制。第二步，完成sibling指针复制，因为sibling指向可能在该节点前面也可能在改节点后面，因此每个节点复制时都需要遍历链表，找到其指向节点，时间复杂度为n^2。这个思路是很简单，写起来发现，还需要用辅助hash表存上原始节点和当前节点对应关系，不然在找随机指向节点时无法判断相等。已经建立hash表，就不用循环判断了，取随机指向节点直接从表中拿就行了。
/*
// Definition for a Node.
class Node {
public:
int val;
Node* next;
Node* random;
Node(int _val) {
val = _val;
next = NULL;
random = NULL;
}
};
*/
class Solution {
public:
Node* copyRandomList(Node* head) {
if (head == NULL)
{
return NULL;
}
map<Node*, Node*> oldToNew;
Node* tmp = head; // 用于遍历的临时指针
Node* cur = new Node(head->val);
oldToNew[tmp] = cur;
Node* newHead = cur; // 保存新的头结点，用于返回
// 第一步，先复制链表next
tmp = tmp->next;
while(tmp != NULL)
{
Node* node = new Node(tmp->val);
cur->next = node;
oldToNew[tmp] = cur;
cur = cur->next;
oldToNew[tmp] = cur;
tmp = tmp->next;
}
cur->next = NULL;
// 第二步：复制随机指针
cur = newHead;
tmp = head;
Node* search = newHead;
while(cur != NULL)
{
if (tmp->random == NULL)
{
cur->random = NULL;
tmp = tmp->next;
cur = cur->next;
continue;
}
// 循环找判断不了，直接用hash表
cur->random = oldToNew[tmp->random];
/*
search = newHead;
while(search != NULL)
{
if (search == oldToNew[tmp->random] )
{
break;
}
search = search->next;
}
cur->random = search;
*/
tmp = tmp->next;
cur = cur->next;
}
return newHead;
}
};
接下来，我们换一种思路，在不用辅助空间情况下实现o(n)时间效率。现在主要问题是不用辅助空间，就不能判断原始节点和当前节点对应关系，因此无法找到随机指针指向节点对应的复制节点。因此思路为将新建复制节点插入原始链表中，并与原始其复制节点保持一定相对关系，这样就可以通过原始节点找到当前新复制的节点了。
第一步复制链表节点并插入原链表中
第二步：随机指针指向原始指向位置的next，即为原始指向节点的复制节点
第二步新节点随机指针指向原指向位置next节点
第三步：进行链表拆分，偶数位置拆分出来构建的链表就是新链表
新链表
/*
// Definition for a Node.
class Node {
public:
int val;
Node* next;
Node* random;
Node(int _val) {
val = _val;
next = NULL;
random = NULL;
}
};
*/
class Solution {
public:
Node* copyRandomList(Node* head) {
if (head == NULL)
{
return NULL;
}
Node* tmp = head; // 用于遍历的临时指针
// 第一步，先复制链表，同时将新节点依次插到其复制节点后面
while(tmp != NULL)
{
// cout << tmp->val << " ";
Node* node = new Node(tmp->val);
node->next = tmp->next; // 新建节点next转化为原节点next，实现插入
tmp->next = node; // 原节点next转化为当前新建节点
tmp = node->next;
}
// tmp = head;
/* 验证下复制完的对不对
while(tmp != NULL)
{
cout << tmp->val << " ";
tmp = tmp->next;
}
*/
// 第二步：开始复制随机指针
tmp = head;
while(tmp != NULL)
{
// cout << tmp->val << " ";
if (tmp->random == NULL)
{
tmp = tmp->next->next;
continue;
}
tmp->next->random = tmp->random->next;
tmp = tmp->next->next;
}
// 第三步，进行拆分
Node* newHead = head->next;
tmp = head;
Node* tmp2 = newHead;
while(tmp != NULL && tmp2 != NULL)
{
tmp->next = tmp2->next;
tmp = tmp2->next;
if (tmp == NULL)
{
break;
}
tmp2->next = tmp->next;
tmp2 = tmp2->next;
}
tmp2->next = NULL;
return newHead;
}
};
面试题27：二叉搜索树和双向链表
输入一棵二叉搜索树，将该二叉搜索树转化为有序的双向链表。要求不能创建任何新节点，只能调整树中结点指针的指向。
leetcode链接 https://leetcode-cn.com/problems/er-cha-sou-suo-shu-yu-shuang-xiang-lian-biao-lcof//* // Definition for a Node. class Node { public: int val; Node* left; Node* right;> Node() {}> Node(int _val) { val = _val; left = NULL; right = NULL; }> Node(int _val, Node* _left, Node* _right) { val = _val; left = _left; right = _right; } }; */ class Solution { public: void treeToDoublyList(Node* root, Node** last) { if (root == NULL) { return; } Node* cur = root; if (cur->left != NULL) { treeToDoublyList(cur->left, last); } if (*last != NULL) { // cout << (*last)->val << " "; cur->left = *last; (*last)->right = cur; } else { cur->left = NULL; } *last = cur; if (cur->right != NULL) { treeToDoublyList(cur->right, last); } return; } Node* treeToDoublyList(Node* root) { if (root == NULL) { return NULL; } Node* last = NULL; treeToDoublyList(root, &last); Node* begin = last; while(begin != NULL && begin->left != NULL) { begin = begin->left; } begin->left = last; last->right = begin; // 注意连接头尾指针，不然leetcode报莫名其妙的错误，报有调用空指针，找了半天，无语 return begin; } };
解题思路：中序遍历转化成双向链表
按照中序遍历的顺序，当我们遍历到根节点时，其左子树已经遍历完并转换为有序链表，且当前链表最后一个节点就是左子树中最大节点。将根节点链接到当前返回有序链表即完成与左子树合并。然后遍历右子树，右子树遍历完链表头节点为其最小节点，将根节点与链表头节点相连，即完成其与右子树合并。通过递归，最终完成整棵树的合并。
面试题28：字符串的排列
输入一个字符串，打印出该字符串中字符的所有排列。例如输入字符串是abc，则打印出其所有排列是abc，acb，bac，bca，cab，cba，注意这个题是可能有重复字符的
leetcode链接 https://leetcode-cn.com/problems/zi-fu-chuan-de-pai-lie-lcof/ https://leetcode-cn.com/problems/permutation-ii-lcci/class Solution { public: void permutation(string s, int index, vector<string>& result) { if (index >= s.length() - 1) { result.push_back(s); return; } vector<char> his; // 记录替换过的char，遇到重复的，直接continue for(int i = index + 1; i < s.length(); i++) { string tmp = s; if (find(his.begin(), his.end(), s[i]) == his.end()) { his.push_back(s[i]); } else { continue; } char ctmp = tmp[index + 1]; tmp[index + 1] = tmp[i]; tmp[i] = ctmp; permutation(tmp, index + 1, result); } return; } vector<string> permutation(string s) { vector<string> result; if (s.length() == 0) { return result; } vector<char> his; // 记录替换过的char，遇到重复的，直接continue for(int i = 0; i < s.length(); i++) { // 交换，得到新字符串snew string sNew = s; if (find(his.begin(), his.end(), s[i]) == his.end()) { his.push_back(s[i]); } else { continue; } char tmp = sNew[0]; sNew[0] = s[i]; sNew[i] = tmp; permutation(sNew, 0, result); } return result; } };
解题思路：无重复字符串排列思路：
先求第一位可能出现的情况，将第一位固定后，求后面各位可能出现的情况，一位一位固定，递归调用，直到达到预期长度，则为一种情况。跟“面试题12：打印1到最大n位的所有数”中的全排列法，思路有点相似。
参考链接 https://blog.csdn.net/volcano1995/article/details/89705689
第一步求所有可能出现在第一个位置的字符（即把第一个字符和后面的所有字符交换[相同字符不交换]）；
第二步固定第一个字符，求后面所有字符的排列。这时候又可以把后面的所有字符拆成两部分（第一个字符以及剩下的所有字符），依此类推。这样，我们就可以用递归的方法来解决。
递归过程
无重复字符串的排列组合。https://leetcode-cn.com/problems/permutation-i-lcci/
class Solution {
public:
void permutation(string s, int index, vector<string>& result)
{
if (index >= s.length() - 1)
{
result.push_back(s);
return;
}
for(int i = index + 1; i < s.length(); i++)
{
string tmp = s;
char ctmp = tmp[index + 1];
tmp[index + 1] = tmp[i];
tmp[i] = ctmp;
permutation(tmp, index + 1, result);
}
return;
}
vector<string> permutation(string s) {
vector<string> result;
if (s.length() == 0)
{
return result;
}
for(int i = 0; i < s.length(); i++)
{
// 交换，得到新字符串snew
string sNew = s;
char tmp = sNew[0];
sNew[0] = s[i];
sNew[i] = tmp;
// cout << sNew << endl;
// permutation(s, 0, s[i], result);
permutation(sNew, 0, result);
}
return result;
}
};
有重复字符串的排列组合。 https://leetcode-cn.com/problems/permutation-ii-lcci/
解题思路：当有重复字符，需要保证相同字符只重复一次。
class Solution {
public:
void permutation(string s, int index, vector<string>& result)
{
if (index >= s.length() - 1)
{
result.push_back(s);
return;
}
vector<char> his; // 记录替换过的char，遇到重复的，直接continue
for(int i = index + 1; i < s.length(); i++)
{
string tmp = s;
if (find(his.begin(), his.end(), s[i]) == his.end())
{
his.push_back(s[i]);
}
else
{
continue; // 保证相同元素不会再重新交换一次
}
char ctmp = tmp[index + 1];
tmp[index + 1] = tmp[i];
tmp[i] = ctmp;
permutation(tmp, index + 1, result);
}
return;
}
vector<string> permutation(string s) {
vector<string> result;
if (s.length() == 0)
{
return result;
}
vector<char> his; // 记录替换过的char，遇到重复的，直接continue
for(int i = 0; i < s.length(); i++)
{
// 交换，得到新字符串snew
string sNew = s;
if (find(his.begin(), his.end(), s[i]) == his.end())
{
his.push_back(s[i]);
}
else
{
continue; // 保证相同元素不会再重新交换一次
}
char tmp = sNew[0];
sNew[0] = s[i];
sNew[i] = tmp;
permutation(sNew, 0, result);
}
return result;
}
};
本题扩展，求字符所有组合。例如输入还是abc，组合有a，b，c，ab，ac，bc，abc，注意交换位置的算一个，譬如ac和ca只记录为一个
// // Created by Xue,Lin on 2020/6/28. // #ifndef UNTITLED_COMBINE_NUM_H #define UNTITLED_COMBINE_NUM_H # include<iostream> # include<vector> # include "string" using namespace std; void combination(string alpa, int length, vector<char>& tmp, vector<string>& result) { if (length <= 0) { string a = ""; for(int i = 0; i < tmp.size(); i++) { a += tmp[i]; } // cout << a << endl; result.push_back(a); return; } if (alpa == "") { return; } tmp.push_back(alpa[0]); // 当选中当前第一个元素 // cout << "begin: " << tmp.size() << endl; // cout << length -1 << endl; // 从剩余元素中选取m-1个 combination(alpa.substr(1, alpa.length()-1), length-1, tmp, result); // 将第一个元素弹出vector tmp.pop_back(); // cout << "end: " << tmp.size() << endl; // 从剩余元素中选取m个 combination(alpa.substr(1, alpa.length()-1), length, tmp, result); return; } vector<string> combination(string alpa) { vector<string> result; if (alpa == "") { return result; } vector<char> tmp; for(int i = 1; i < alpa.length(); i++) { combination(alpa, i, tmp, result); } return result; } #endif //UNTITLED_COMBINE_NUM_H
解题思路：
输入是n个字符，则这n个字符能构成长度为1，长度为2，长度为n的组合。在求n个字符的长度为m的组合是，我们把n个字符分为两部分，第一个字符和其余的所有字符。如果组合中包含第一个字符，则下一步在剩余的字符中选取m-1个字符。如果组合中不包含第一个字符，则下一步在剩余n-1个字符中选择m个字符。也就是说，我们可以把求n个字符组成长度为m的组合问题分解成两个子问题，分别求n-1个字符中长度为m-1的组合，以及求n-1个字符长度为m的组合。这两个问题都用递归来实现。
相关题目：输入一个含有8个数字的数组，判断有没有可能把这8个数字分别放在正方体的8个顶点上，使得正方体上三组相对的面上4个顶点和都相等。
立方体示意图// // Created by Xue,Lin on 2020/6/28. // #ifndef UNTITLED_CHECK_CUBE_H #define UNTITLED_CHECK_CUBE_H bool check(int* data, int n) { return (data[0]+data[1]+data[2]+data[3]) == (data[4]+data[5]+data[6]+data[7]) && \ (data[0] + data[2] + data[4] + data[6]) == (data[1] + data[3] + data[5] + data[7]) && \ (data[0] + data[1] + data[4] + data[5]) == (data[2] + data[3] + data[4] + data[7]); } bool Permutation(int data[], int* change, int begin, int n) { if (begin >= n) { return check(change, n); } bool result = false; for(int i = begin; i < n; i++) { int* arr = change; int tmp = change[begin]; change[begin] = change[i]; change[i] = tmp; if (Permutation(data, change, begin+1, n)) { return true; } } return result; } bool Permutation(int data[], int n) { for(int i = 0; i < n; i++) { int* change = data; int tmp = change[0]; change[0] = change[i]; change[i] = tmp; if (Permutation(data, change, 0, n)) { return true; } } return false; } #endif //UNTITLED_CHECK_CUBE_H
解题思路：相当于a1，a2，a3，a4，a5，a6，a7，a8这8个数字的排列组合，然后判断这个组合是不是符合题意，即a1+a2+a3+a4=a5+a6+a7+a8，a1+a3+a5+a7=a2+a4+a6+a8，a1+a2+a5+a6=a3+a4+a7+a8。全排列思路与面试题28相同。
相关题目：在8*8的国际象棋上摆8个皇后，使其不能相互攻击，即任意两个皇后不能在同一行，同一列或同一对角线上。请问一共有多少种摆法。 leetcode链接 https://leetcode-cn.com/problems/eight-queens-lcci/ 别人写的回溯法，自己写的超时，有时间再回来研究
class Solution { public: vector<vector<string>> res; /* 输入棋盘边长 n，返回所有合法的放置 */ vector<vector<string>> solveNQueens(int n) { // '.' 表示空，'Q' 表示皇后，初始化空棋盘。 vector<string> board(n, string(n, '.')); backtrack(board, 0); return res; } // 路径：board 中小于 row 的那些行都已经成功放置了皇后 // 选择列表：第 row 行的所有列都是放置皇后的选择 // 结束条件：row 超过 board 的最后一行 void backtrack(vector<string>& board, int row) { // 触发结束条件 if (row == board.size()) { res.push_back(board); return; } int n = board[row].size(); for (int col = 0; col < n; col++) { // 排除不合法选择 if (!isValid(board, row, col)) continue; // 做选择 board[row][col] = 'Q'; // 进入下一行决策 backtrack(board, row + 1); // 撤销选择 board[row][col] = '.'; } } bool isValid(vector<string>& board, int row, int col) { int n = board.size(); // 检查列是否有皇后互相冲突 for (int i = 0; i < n; i++) { if (board[i][col] == 'Q') return false; } // 检查右上方是否有皇后互相冲突 for (int i = row - 1, j = col + 1; i >= 0 && j < n; i--, j++) { if (board[i][j] == 'Q') return false; } // 检查左上方是否有皇后互相冲突 for (int i = row - 1, j = col - 1; i >= 0 && j >= 0; i--, j--) { if (board[i][j] == 'Q') return false; } return true; }> };
解题思路：按上面思路全排列之后，再判断。测试用例能过，但是会超时。。参考链接，讲了回溯法。
class Solution {
public:
bool checkok(vector<int> change, int n)
{
if (n == 0 || n == 1)
{
return true;
}
if (n == 2)
{
return false;
}
vector<int> sub;
vector<int> add;
for(int i = 0; i < n; i++)
{
int tmp = change[i] - i;
if (find(sub.begin(), sub.end(), tmp) == sub.end())
{
sub.push_back(tmp);
} else
{
return false;
}
tmp = change[i] + i;
if (find(add.begin(), add.end(), tmp) == add.end())
{
add.push_back(tmp);
} else
{
return false;
}
}
return true;
}
void solveNQueens(vector<int> arr, vector<int>& change, int index, int length, vector<vector<int>>& result1)
{
// cout << index << endl;
if (index >= length - 1)
{
if (checkok(change, length))
{
result1.push_back(change);
}
/*
for(int j = 0; j < change.size(); j++)
{
cout << change[j] << " ";
}
cout << endl;
*/
return;
}
for(int i = index + 1; i < length; i++)
{
vector<int> tmpArr = change;
int tmp = tmpArr[index+1];
tmpArr[index+1] = tmpArr[i];
tmpArr[i] = tmp;
solveNQueens(arr, tmpArr, index+1, length, result1);
}
return;
}
vector<vector<string>> solveNQueens(int n) {
vector<vector<string>> result;
vector<vector<int>> result1;
if (n == 0)
{
return result;
}
vector<int> arr;
for (int i = 0; i < n; i++)
{
arr.push_back(i);
}
for(int i = 0; i < n; i++)
{
vector<int> change = arr;
int tmp = change[0];
change[0] = change[i];
change[i] = tmp;
// cout << "1" << endl;
solveNQueens(arr, change, 0, n, result1);
}
for(int i = 0; i < result1.size(); i++)
{
vector<string> sinVec;
for(int j = 0; j < result1[i].size(); j++)
{
// cout << result1[i][j] << " ";
string tmp = "";
for(int z = 0; z < n; z++)
{
if (z == result1[i][j])
{
tmp += 'Q';
continue;
}
tmp += '.';
}
sinVec.push_back(tmp);
}
// cout << endl;
result.push_back(sinVec);
}
return result;
}
};
c++【拾遗】 回溯算法
参考链接 https://leetcode-cn.com/problems/n-queens/solution/hui-su-suan-fa-xiang-jie-by-labuladong/
回溯法的核心就是递归调用的过程，在递归调用之前「做选择」，在递归调用之后「撤销选择」def backtrack(路径, 选择列表): if 满足结束条件: result.add(路径) return for 选择 in 选择列表: 做选择 backtrack(路径, 选择列表) 撤销选择例如字符全排列实现,比上面那种交换的要好理解，但是增加了遍历情况，性能会差些
/* 主函数，输入一组不重复的数字，返回它们的全排列 */ List<List<Integer>> permute(int[] nums) { // 记录「路径」 LinkedList<Integer> track = new LinkedList<>(); backtrack(nums, track); return res; }> // 路径：记录在 track 中 // 选择列表：nums 中不存在于 track 的那些元素 // 结束条件：nums 中的元素全都在 track 中出现 void backtrack(int[] nums, LinkedList<Integer> track) { // 触发结束条件 if (track.size() == nums.length) { res.add(new LinkedList(track)); return; } for (int i = 0; i < nums.length; i++) { // 排除不合法的选择 if (track.contains(nums[i])) continue; // 做选择 track.add(nums[i]); // 进入下一层决策树 backtrack(nums, track); // 取消选择 track.removeLast(); } }
