1. (22. 括号生成)这里只讨论第二种做法回溯法。在回溯法的函数void backtrack(vector<string>& ans, string& current, int open, int close, int n); 中,可分为三个if条件判断,分别判断当current.size() == 2*n,open < n以及 ________ 的情况。首先当current.size() == 2*n时,可直接将当前字符串current入到ans当中;接着当open < n时,将'('入到当前字符串current当中,然后继续再调用回溯函数bactrack(ans, current, ____, close, n),值得注意的是,当调用完毕之后,还应该让当前字符串current pop出来一个字符。如果backtrack函数的原型变成void backtrack(vector<string>& ans, string current, int open, int close, int n); 其它的地方做一些适当的修改之后,那么在调用完毕之后还需要再让当前字符串current pop出来一个字符嘛?__________;最后当close < n时,将')'入到当前字符串current当中,然后继续再调用回溯函数backtrack(ans, current, open, _____, n)。同样在调用完毕之后,也还应该让当前字符串current再pop出来一个字符。我们会发现,回溯法的结构很类似于____________,即类似于下面的三部分代码:
void Traverse(TreeNode* pnode) {
printf("%d", pnode->val);
if(pnode->lchild) Traverse(pnode->lchild);
_________________________________________;
}
void Traverse(TreeNode* pnode) {
if(pnode->lchild) Traverse(pnode->lchild);
_______________________;
if(pnode->rchild) Traverse(pnode->rchild);
}
void Traverse(TreeNode* pnode) {
_________________________________________;
if(pnode->rchild) Traverse(pnode->rchild);
printf("%d", pnode->val);
}
2. (23. 合并K个有序链表)为了完成合并K个有序链表的任务,可以将这个任务拆分成两部分。首先编写合并两个有序链表的函数,接着再去编写合并K个有序链表的任务。在这里合并两个有序链表的方法可分为两种:递归法与哨兵结点法。递归法的函数为:
ListNode* mergeTwoLists(ListNode* l1, ListNode* l2) {
if(l1 == nullptr && l2 != nullptr) {
return l2;
}else if(_____________________) {
return l1;
}else if(l1->val < l2->val) {
l1->next = mergeTwoLists(____, ____);
return __;
}else{
l2->next = mergeTwoLists(l1, ______);
return l2;
}
}
哨兵结点法的函数为:
ListNode* mergeTwoLists(ListNode* l1, ListNode* l2) {
ListNode* preHead = new ListNode(-1);
ListNode* prev = preHead;
while(l1 != nullptr && l2 != nullptr) {
if(l1->val < l2->val){
prev->next = l1;
______________;
}else{
prev->next = l2;
______________;
}
___________________;
}
if(l1 == nullptr){prev->next = l2;}
else{prev->next = l1;}
ListNode* ans = preHead->next;
delete preHead; return ans;
}
编写完合并两个有序链表的函数之后,开始编写合并K个有序链表的函数,在这里讨论三种方法。第一种方法就是顺序合并,即使用一个循环,依次将ans(ListNode*类型)与下一条链表进行合并;第二种方法是分治合并,即两两链表合并,合并完成之后再两两链表合并... ...顺序合并的代码是:
ListNode* mergeKLists(vector<ListNode*>& lists) {
ListNode* ans = ________;
for(int i = 0; i < lists.size(); i++) {
ans = mergeTwoLists(lists[i], ___);
}
return ans;
}
在顺序合并的代码中,必须让ans的初值为nullptr,而让i从0开始循环,这样做的原因是,如果ans初值为lists[0],i初值为0,则首轮循环时合并的两个链表是lists[0]与lists[0],这会导致程序卡死在合并两个有序链表上,具体表现是_________________。而如果ans初值为lists[0],i初值为1,则有可能出现K=0,即合并K个有序链表实质上就只是合并一个有序链表,这样子就会将不合适的lists[1]传给mergeTwoLists函数,进而导致错误。分治合并的代码是:
ListNode* mergeKLists(vector<ListNode*>& lists) {
return merge(lists, 0, lists.size()-1);
}
ListNode* merge(vector<ListNode*>& lists, int l, int r) {
if(l == r) return _______;
else if(l > r) return ________;
else{
int min = (l+r)>>1;
ListNode* lnode = merge(lists, l, mid);
ListNode* rnode = ____________________;
return mergeTwoLists(lnode, rnode);
}
}
3. (17. 电话号码的字母组合)这道题使用的是回溯算法。首先创建一个<char, string>类型的unordered_map类型的变量pairs,分别存储9个数字按键与26个英文字母之间的对应关系。接着编写主要的函数vector<string> letterCombinations(string digits)。在这个主要的函数中,先vector<string> ans;来保存结果,以及string combination来保存一次的字符串,接着如果digits的大小为0的话,直接返回空的ans,否则当调用backtrack函数之后,就会让一个空字符串进入到ans中,而这与我们的目标是不相符的。而如果digits的大小不为0,则调用backtrack函数,调用完backtrack函数之后,再return ans。因此主要的函数letterCombinations的结构为:
vector<string> letterCombinations(string digits) {
vector<string> ans;
__________________;
if(digits.size() == 0) {
__________;
}else{
backtrack(vector<string>& ans, string& combination, string& digits, int num);
return ans;
}
}
编写完成主要的函数letterCombinations之后,就该编写回溯函数backtrack了。回忆括号生成问题中使用到的回溯函数backtrack,会发现回溯函数的主体依然为几个大的条件判断。括号生成问题中使用到的回溯函数backtrack分为三个if,分别处理:括号总数等于2*n,左括号数小于n,以及右括号数小于左括号数这三种情况。因此letterCombinations的主体也可以分为几个条件判断:combination字符串的长度等于digits长度、combination字符串长度小于digits长度。在括号生成的backtrack中,括号总数等于2*n时,通过push_back将当前字符串保存在ans中,所以在字母组合问题中当combination与digits长度相等时,也应该通过push_back将当前字符串保存在ans中。而在括号生成问题中,如果左括号数小于n,那么左括号入当前字符串,然后调用backtrack函数,调用完之后再从当前字符串中出一个括号。至于右括号数小于左括号数,也是类似的做法。所以在字母组合问题中,当combination长度小于digits长度时,应该通过for循环,将每一种数字对应的多个字母都尝试一次,将字母入字符串,然后调用backtrack函数,调用完之后从字符串出一个... ...因此,编写backtrack函数为:
void backtrack(vector<string>& ans, string& combination, string& digits, int num) {
if(___________________________) {
ans.push_back(combination);
}else{
for(char ch:_______________) {
combination.push_back(ch);
backtrack(ans, combination, digits, ____);
combination.pop_back();
}
}
}
4. (16. 最接近的三数之和)方法仍然是使用双指针。在处理之前,要先_______,以保证双指针的移动是逻辑上合理的。接着使用一个for循环外加判重,遍历第一个数字。在第一个数字已被确定的某一种情况之下,设置双指针,当三数之和sum减去target的差的绝对值比已有记录的差的最小绝对值还要小,就更新这个记录的差。接着移动双指针,如果sum大于target,那么左移右指针,如果sum小于target,那么右移左指针,而如果sum等于target,那么毫无疑问此时record已经为target,直接return返回即可。
5. (15. 三数之和)方法还是使用双指针。在处理之前,要先______,以保证双指针的移动在逻辑上是合理的。接着使用一个for循环外加判重,遍历第一个数字。在这里如果不判重,那么假如第一个数两次都是相同的,而双指针无法解决第一个数的重复问题,所以就会导致答案中出现两个一模一样的结果。另外除了判重之外,还可以仿照四数之和中的做法,如果第一个数和紧随其后的三个数还是大于0,那考虑到这时已经是从小排到大的已经排好的序列,再往后走已经没有意义,所以break即可,而如果第一个数和倒数第一、二个数的和还是小于0,那就说明第一个数还应该再往后走,即continue。在某一次的for循环之内,就要开始双指针的移动了。设置左指针为第一个数右边那个数,右指针为倒数第一个数,三数之和记作sum。如果sum等于0,就把此时三个数保存下来,然后左指针右移到与上一个数不同的地方,且右指针左移到与上一个数不同的地方。在这里如果只有一侧指针移动的话,显然是不合适的。而如果sum大于0或者小于0,只需要相应的左移右指针,与右移左指针即可,这时虽然会有重复,但是解决重复的目的是为了防止答案重复,而不是主要为了节省开销,所以不需要像for循环判重,以及像sum==0时那样解决掉判重问题。
6. (14. 最长公共前缀)有三种方法。第一种方法是,先找到前两个字符串的公共前缀,将其记录为commonprefix,接着再去找commonprefix和第__个字符串的公共前缀,再去找commonprefix和第__个字符串的公共前缀... ...具体是如何实现的呢?这里使用了函数__的概念。当传给函数longestCommonPrefix的参数只有一个vector<string>类型的变量strs时,其函数体的内容为:定义一个字符串commonprefix为strs[0],如果strs的大小为1,那么直接返回commonprefix,而如果strs的大小大于1,则通过一个for循环来依次求出来最长公共前缀,for(int i = 0; i < len; i++)循环,依次让commonprefix = longestCommonPrefix(commonprefix, strs[i]); 最终返回commonprefix,其中len为______。当传给函数longestCommonPrefix的参数是两个string类型的变量str1与str2时,其函数体的内容为:定义一个字符串commonprefix,它是空串,求出两个串的最小长度len,for(int i = 0; i < len; i++),循环体的内容是:___________________。
7. (14. 最长公共前缀)三种方法里面的第二种方法。依次比较所有字符串的第一个字符是否相同、第二个字符是否相同、第三个字符是否相同... ...代码如下,补全代码:
class Solution {
public:
string longestCommonPrefix(vector<string>& strs) {
int strslen = strs.size();
int minlen = strs[0].size();
string commonprefix =_____;
for(int i = 0; i < strslen; i++) {
minlen = minlen < strs[i].size()?______:______;
}
for(int i = 0; i < minlen; i++) {
char ch =_____;
int j = 0;
for(; j < strslen; j++) {
if(strs[_][_] != ch) {
return _________;
}else{
continue;
}
}
if(j == _______) commonprefix.push_back(ch);
}
return commonprefix;
}
};