1 4Sum Given an array ? Find all unique quadruplets in the array which gives the sum of target. 利用公式 可以将四数和转化为两数和的问题。
vector<vector<int>> fourSum(vector<int>& nums, int target) {sort(nums.begin(), nums.end());int len= nums.size();vector<vector<int> > res;vector<int> mid;for(int i=0;i<len-3;i++){if (i> 0 && nums[i] == nums[i – 1]) continue;for(int j=i+1;j<len-2;j++){if (j>i+1 && nums[j] == nums[j – 1]) continue;int start= j+1, end = len-1,sum=target-nums[i]-nums[j];while(start<end){if ((nums[start] + nums[end])<sum) start++;else if ((nums[start] + nums[end])>sum) end–;else{mid.push_back(nums[i]);mid.push_back(nums[j]);mid.push_back(nums[start++]);mid.push_back(nums[end–]);res.push_back(mid);mid.clear();while (start<end&&nums[start] == nums[start-1]) start++;while (start<end&&nums[end] == nums[end+1]) end–;}}}}return res;}
2 Generate Parentheses Given pairs of parentheses, write a function to generate all combinations of well-formed parentheses.
For example, given , a solution set is:
“((()))”, “(()())”, “(())()”, “()(())”, “()()()”
该问题可以通过递归解决，使用三个变量分别记录左括号剩余数，右括号剩余数及已使用括号数。当左括号和右括号剩余数都为0时生成一个合法的括号序列。
void generate(int l,int r,vector<char> mid,int count,vector<string>& res){if(l<0||r<l) return;if(l==0&&r==0){string str(mid.begin(),mid.end());res.push_back(str);}else{if(l>0){mid[count]='(‘;generate(l-1,r,mid,count+1,res);}if(r>l){mid[count]=’)’;generate(l,r-1,mid,count+1,res);}}}vector<string> generateParenthesis(int n) {vector<string> res;vector<char> mid(2*n,’\0′);generate(n,n,mid,0,res);return res;}
3 Swap Nodes in Pairs Given a linked list, swap every two adjacent nodes and return its head. For example, Given 1->2->3->4, you should return the list as 2->1->4->3.
同样采用递归的方法，因为每次都是两个相邻节点成对交换，每次递归的头指针为head->next->next, 当head或head->next为空时不用交换。
ListNode* swapPairs(ListNode* head) {if (head == NULL || head->next == NULL) return head;ListNode *grandChild = swapPairs(head->next->next);ListNode *child = head->next;child->next = head;head->next = grandChild;return child;}
4 Divide Two Integers Divide two integers without using multiplication, division and mod operator. If it is overflow, return MAX_INT. 为了方便计算先求两个数的绝对值，为了防止溢出将其用long long 类型表示，，为了减小时间复杂度，对除数实现成倍数累加。
int divide(int dividend, int divisor) {= 0, result = 0;= 0;if (divisor == 0) return INT_MAX;if (dividend == 0) return 0;bool flag = true;if ((dividend<0 && divisor>0) || (dividend>0 && divisor<0)) flag = false;long long middend=dividend;long long midvisor=divisor;long long middividend = abs(middend);long long middivisor = abs(midvisor);while (middividend >= middivisor){count = 1;sum = middivisor;while (sum + sum<=middividend){sum += sum;count += count;}middividend -= sum;result += count;}if (!flag) result = -result;if(result<INT_MIN||result>INT_MAX) result=INT_MAX;return result; }
找回自我，歇够了，再飞回来，继续面对自己的人生。
