2024.03.04——2024.03.10 力扣练习总结及专项巩固（二）

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;}
};