题目：最长公共前缀
-
编写一个函数来查找字符串数组中的最长公共前缀。如果不存在公共前缀，返回空字符串
""。 -
class Solution { public: string longestCommonPrefix(vector<string>& strs) { string res=""; int index = 0; for(int i=0;i<strs[0].size();i++){ char temp = strs[0][i]; for(int j=1;j<strs.size();j++){ if(strs[j][i] != temp ){ return strs[0].substr(0,i); } } } return strs[0]; } }; -
纵向扫描时，从前往后遍历所有字符串的每一列，比较相同列上的字符是否相同，如果相同则继续对下一列进行比较，如果不相同则当前列不再属于公共前缀，当前列之前的部分为最长公共前缀。
-
时间复杂度：O(mn)，其中 m 是字符串数组中的字符串的平均长度，n 是字符串的数量。最坏情况下，字符串数组中的每个字符串的每个字符都会被比较一次。空间复杂度：O(1)。使用的额外空间复杂度为常数。
-
对于问题 LCP(Si⋯Sj)，可以分解成两个子问题 LCP(Si…Smid) 与 LCP(Smid+1…Sj)，其中 m i d = i + j 2 mid=\frac{i+j}{2} mid=2i+j。对两个子问题分别求解，然后对两个子问题的解计算最长公共前缀，即为原问题的解。
-
class Solution { public: string pr(const vector<string> &s,int start,int end){ if(start==end){ return s[start]; }else{ int mid = start+(end-start)/2; string left = pr(s,start,mid); string right = pr(s,mid+1,end); cout<<left<<" "<<right<<endl; return camp(left,right); } } string camp(const string &left,const string &right){ int min_len = min(left.size(),right.size()); for(int i=0;i<min_len;i++){ if(left[i]!=right[i]){ return left.substr(0,i); } } return left.substr(0,min_len); } string longestCommonPrefix(vector<string>& strs) { if(!strs.size()){ return ""; }else{ return pr(strs,0,strs.size()-1); } } };
题目：最接近的三数之和
-
给你一个长度为
n的整数数组nums和 一个目标值target。请你从nums中选出三个整数，使它们的和与target最接近。返回这三个数的和。假定每组输入只存在恰好一个解。 -
借助双指针，我们就可以对枚举的过程进行优化。我们用 pb 和 pc 分别表示指向 b 和 c 的指针，初始时，pb 指向位置 i+1，即左边界；pc 指向位置 n−1，即右边界。在每一步枚举的过程中，我们用 a+b+c 来更新答案，并且：
- 如果 a+b+c≥target，那么就将 pc 向左移动一个位置；
- 如果 a+b+c<target，那么就将 pb 向右移动一个位置。
-
如果 a+b+c≥target，并且我们知道 pb 到 pc 这个范围内的所有数是按照升序排序的，那么如果 pc 不变而 pb 向右移动，那么 a+b+c 的值就会不断地增加，显然就不会成为最接近 target 的值了。因此，我们可以知道在固定了 pc 的情况下，此时的 pb 就可以得到一个最接近 target 的值，那么我们以后就不用再考虑 pc 了，就可以将 pc 向左移动一个位置。
-
class Solution { public: int threeSumClosest(vector<int>& nums, int target) { sort(nums.begin(),nums.end()); int len_nums=nums.size(); int res = 1e7; // 根据差值的绝对值来更新答案 auto update=[&](int cur){ if(abs(cur-target)<abs(res-target)){ res=cur; } }; for(int i=0;i<len_nums;i++){ if(i>0 && nums[i]==nums[i-1]){ continue; } int pb=i+1,pc=len_nums-1; while(pb<pc){ int sum=nums[i]+nums[pb]+nums[pc]; if(sum==target){ return target; } update(sum); if(sum>target){ int newpc = pc-1; while(pb<newpc && nums[newpc] == nums[pc]){ newpc--; } pc = newpc; }else{ int newpb = pb+1; while(newpb<pc && nums[newpb] == nums[pb]){ newpb++; } pb=newpb; } } } return res; } }; -
时间复杂度：O(N2)，其中 N 是数组 nums 的长度。我们首先需要 O(NlogN) 的时间对数组进行排序，随后在枚举的过程中，使用一重循环 O(N) 枚举 a，双指针 O(N) 枚举 b 和 c，故一共是 O(N2)。空间复杂度：O(logN)。排序需要使用 O(logN) 的空间。然而我们修改了输入的数组 nums，在实际情况下不一定允许，因此也可以看成使用了一个额外的数组存储了 nums 的副本并进行排序，此时空间复杂度为 O(N)。
题目：合并两个有序链表
-
将两个升序链表合并为一个新的 升序 链表并返回。新链表是通过拼接给定的两个链表的所有节点组成的。
-
-
/** * Definition for singly-linked list. * struct ListNode { * int val; * ListNode *next; * ListNode() : val(0), next(nullptr) {} * ListNode(int x) : val(x), next(nullptr) {} * ListNode(int x, ListNode *next) : val(x), next(next) {} * }; */ class Solution { public: ListNode* mergeTwoLists(ListNode* list1, ListNode* list2) { ListNode *res =new ListNode(); ListNode *head = res; while(list1 && list2){ if(list1->val<list2->val){ ListNode *temp1 = new ListNode(list1->val); res->next = temp1; list1 = list1->next; }else{ ListNode *temp2 = new ListNode(list2->val); res->next = temp2; list2 = list2->next; } res = res->next; } if(list1){ res->next = list1; } if(list2){ res->next = list2; } return head->next; } }; -
时间复杂度：O(n+m)，其中 n 和 m 分别为两个链表的长度。因为每次循环迭代中，l1 和 l2 只有一个元素会被放进合并链表中， 因此 while 循环的次数不会超过两个链表的长度之和。所有其他操作的时间复杂度都是常数级别的，因此总的时间复杂度为 O(n+m)。空间复杂度：O(1)。我们只需要常数的空间存放若干变量。
-
如果 l1 或者 l2 一开始就是空链表 ，那么没有任何操作需要合并，所以我们只需要返回非空链表。否则，我们要判断 l1 和 l2 哪一个链表的头节点的值更小，然后递归地决定下一个添加到结果里的节点。如果两个链表有一个为空，递归结束。
-
/** * Definition for singly-linked list. * struct ListNode { * int val; * ListNode *next; * ListNode() : val(0), next(nullptr) {} * ListNode(int x) : val(x), next(nullptr) {} * ListNode(int x, ListNode *next) : val(x), next(next) {} * }; */ class Solution { public: ListNode* mergeTwoLists(ListNode* list1, ListNode* list2) { if(!list1){ return list2; }else if(!list2){ return list1; }else if(list1->val < list2->val){ list1->next = mergeTwoLists(list1->next,list2); return list1; }else{ list2->next = mergeTwoLists(list1,list2->next); return list2; } } }; -
时间复杂度：O(n+m)，其中 n 和 m 分别为两个链表的长度。因为每次调用递归都会去掉 l1 或者 l2 的头节点（直到至少有一个链表为空），函数 mergeTwoList 至多只会递归调用每个节点一次。因此，时间复杂度取决于合并后的链表长度，即 O(n+m)。
-
空间复杂度：O(n+m)，其中 n 和 m 分别为两个链表的长度。递归调用 mergeTwoLists 函数时需要消耗栈空间，栈空间的大小取决于递归调用的深度。结束递归调用时 mergeTwoLists 函数最多调用 n+m 次，因此空间复杂度为 O(n+m)。
题目：括号生成
-
数字
n代表生成括号的对数，请你设计一个函数，用于能够生成所有可能的并且 有效的 括号组合。 -
为了生成所有序列，我们可以使用递归。长度为 n 的序列就是在长度为 n−1 的序列前加一个 ‘(’ 或 ‘)’。为了检查序列是否有效，我们遍历这个序列，并使用一个变量 balance 表示左括号的数量减去右括号的数量。如果在遍历过程中 balance 的值小于零，或者结束时 balance 的值不为零，那么该序列就是无效的，否则它是有效的。
-
class Solution { public: bool valid(const string &str){ int temp=0; for(char c:str){ if(c=='('){ temp++; }else{ temp--; } if(temp<0){ return false; } } return temp==0; } void generate(string &curr,int n,vector<string> &res){ if(n==curr.size()){ if(valid(curr)){ res.push_back(curr); } return ; } curr += '('; generate(curr,n,res); curr.pop_back(); curr += ')'; generate(curr,n,res); curr.pop_back(); } vector<string> generateParenthesis(int n) { vector<string> res; string curr; generate(curr,n*2,res); return res; } }; -
时间复杂度： O ( 2 2 n n ) O(2^{2n}n) O(22nn)，对于 2 2 n 2^{2n} 22n 个序列中的每一个，我们用于建立和验证该序列的复杂度为 O(n)。空间复杂度：O(n)，除了答案数组之外，我们所需要的空间取决于递归栈的深度，每一层递归函数需要 O(1) 的空间，最多递归 2n 层，因此空间复杂度为 O(n)。
-
如果左括号数量不大于 n，我们可以放一个左括号。如果右括号数量小于左括号的数量，我们可以放一个右括号。
-
class Solution { public: void track(vector<string> &res,string &cur,int n ,int open,int close){ if(cur.size()==2*n){ res.push_back(cur); return ; } if(open<n){ cur.push_back('('); track(res,cur,n,open+1,close); cur.pop_back(); } if(close < open){ cur.push_back(')'); track(res,cur,n,open,close+1); cur.pop_back(); } } vector<string> generateParenthesis(int n) { vector<string> res; string curr; track(res,curr,n,0,0); return res; } }; -
时间复杂度： O ( 4 n n ) O(\dfrac{4^n}{\sqrt{n}}) O(n4n)，在回溯过程中，每个答案需要 O(n) 的时间复制到答案数组中。空间复杂度：O(n)，除了答案数组之外，我们所需要的空间取决于递归栈的深度，每一层递归函数需要 O(1) 的空间，最多递归 2n 层，因此空间复杂度为 O(n)。
题目：合并 K 个升序链表
-
给你一个链表数组，每个链表都已经按升序排列。请你将所有链表合并到一个升序链表中，返回合并后的链表。
-
可以想到一种最朴素的方法：用一个变量 res 来维护以及合并的链表，第 i 次循环把第 i 个链表和 ans 合并，答案保存到 res 中。
-
/** * Definition for singly-linked list. * struct ListNode { * int val; * ListNode *next; * ListNode() : val(0), next(nullptr) {} * ListNode(int x) : val(x), next(nullptr) {} * ListNode(int x, ListNode *next) : val(x), next(next) {} * }; */ class Solution { public: ListNode* mergeTwo(ListNode *a,ListNode *b){ if((!a) || (!b)){ return a?a:b; } ListNode head,*tail = &head,*ap=a,*bp=b; while(ap && bp){ if(ap->val < bp->val){ tail->next = ap; ap = ap->next; }else{ tail->next =bp; bp = bp->next; } tail = tail->next; } tail->next = (ap?ap:bp); return head.next; } ListNode* mergeKLists(vector<ListNode*>& lists) { ListNode *res=nullptr; for(size_t i=0;i<lists.size();i++){ res = mergeTwo(res,lists[i]); } return res; } }; -
使用优先队列合并:需要维护当前每个链表没有被合并的元素的最前面一个，k 个链表就最多有 k 个满足这样条件的元素，每次在这些元素里面选取 val 属性最小的元素合并到答案中。在选取最小元素的时候，我们可以用优先队列来优化这个过程。
-
/** * Definition for singly-linked list. * struct ListNode { * int val; * ListNode *next; * ListNode() : val(0), next(nullptr) {} * ListNode(int x) : val(x), next(nullptr) {} * ListNode(int x, ListNode *next) : val(x), next(next) {} * }; */ class Solution { public: struct sta{ int val; ListNode *ptr; bool operator < (const sta &r) const{ return val >r.val; } }; priority_queue <sta> q; ListNode* mergeKLists(vector<ListNode*>& lists) { for(auto node:lists){ if(node){ q.push({node->val,node}); } } ListNode head,*tail = &head; while(!q.empty()){ auto temp = q.top(); q.pop(); tail->next = temp.ptr; tail = tail->next; if(temp.ptr->next){ q.push({temp.ptr->next->val,temp.ptr->next}); } } return head.next; } }; -
时间复杂度：考虑优先队列中的元素不超过 k 个，那么插入和删除的时间代价为 O(logk)，这里最多有 kn 个点，对于每个点都被插入删除各一次，故总的时间代价即渐进时间复杂度为 O(kn×logk)。空间复杂度：这里用了优先队列，优先队列中的元素不超过 k 个，故渐进空间复杂度为 O(k)。
-
将 k 个链表配对并将同一对中的链表合并；第一轮合并以后， k 个链表被合并成了$ \frac{k}{2} $ 个链表，平均长度为 2 n k \frac{2n}{k} k2n ，然后是 k 4 \frac{k}{4} 4k 个链表，$ \frac{k}{8}$ 个链表等等；重复这一过程，直到我们得到了最终的有序链表。
-
/** * Definition for singly-linked list. * struct ListNode { * int val; * ListNode *next; * ListNode() : val(0), next(nullptr) {} * ListNode(int x) : val(x), next(nullptr) {} * ListNode(int x, ListNode *next) : val(x), next(next) {} * }; */ class Solution { public: ListNode* merge(ListNode *a,ListNode *b){ if((!a) || (!b)){ return a?a:b; } ListNode head,*tail=&head,*ap=a,*bp=b; while(ap && bp){ if(ap->val < bp->val){ tail->next = ap; ap = ap->next; }else{ tail->next = bp; bp = bp->next; } tail = tail->next; } tail->next = (ap?ap:bp); return head.next; } ListNode* opt(vector<ListNode*> &ls,int l,int r){ if(l==r){ return ls[l]; } if(l>r){ return nullptr; } int mid = l+(r-l)/2; return merge(opt(ls,l,mid),opt(ls,mid+1,r)); } ListNode* mergeKLists(vector<ListNode*>& lists) { return opt(lists,0,lists.size()-1); } }; -
时间复杂度：考虑递归「向上回升」的过程——第一轮合并 k 2 \frac{k}{2} 2k 组链表，每一组的时间代价是 O(2n)；第二轮合并 $\frac{k}{4} $ 组链表，每一组的时间代价是 O(4n)…所以总的时间代价是 O ( ∑ i = 1 ∞ k 2 i × 2 i n ) = O ( k n × log k ) O(\sum_{i = 1}^{\infty} \frac{k}{2^i} \times 2^i n) = O(kn \times \log k) O(∑i=1∞2ik×2in)=O(kn×logk)，故渐进时间复杂度为 O ( k n × log k ) O(kn \times \log k) O(kn×logk)。空间复杂度：递归会使用到$ O(\log k) $空间代价的栈空间。
