leetcode解题思路分析（三）15-21题

本文主要是介绍leetcode解题思路分析（三）15-21题，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

15. 三数求和

最简单的做法就是三重循环判断：

    int length=nums.length;for(int i=0;i<length;i++){for(int j=i+1;j<length;j++){for(int k=j+1;k<length;k++){if(nums(i)+nums[j]+nums[k]==0){...}}}  }      

在此基础上，对第三次查找其实可以做优化：只需要找指定的数字即可，所以可以通过哈希、排序等方式获得，通过二分法降低时间复杂度

更优的做法是将内部二层循环改为首尾双指针滑动判断：因为内层双循环寻找固定的值，而且要求不重复，因此排序之后从首尾开始判断并滑动得出结果即可。时间复杂度NlogN

class Solution {
public:vector<vector<int>> threeSum(vector<int>& nums) {int target = 0, val = 0, begin, end;int size = nums.size();vector<int> tmp;vector<int>::iterator beginIter, endIter;vector<vector<int>> ret;if (size <= 2)return ret;sort(nums.begin(), nums.end());for (int i = 0; i < size - 2; i++){target = 0 - nums[i];if (target < 0)break;beginIter = nums.begin() + i + 1;endIter = nums.end() - 1;while (beginIter < endIter){begin = *beginIter;end = *endIter;val = begin + end;if (val == target){tmp.push_back(nums[i]);tmp.push_back(*beginIter);tmp.push_back(*endIter);ret.push_back(tmp);tmp.clear();while (beginIter < endIter && *beginIter == begin)beginIter++;while (beginIter < endIter && *endIter == end)endIter--;}else if (val < target){beginIter++;}else{endIter--;}}while (i < size - 2 && nums[i] == nums[i + 1])i++;}return ret;}
};

16. 最接近的三数之和
    给定一个包括 n 个整数的数组 nums 和 一个目标值 target。找出 nums 中的三个整数，使得它们的和与 target 最接近。返回这三个数的和。假定每组输入只存在唯一答案。

在做完上题之后这题变得异常简单，只需要增加一个绝对值判断即可。

class Solution {
public:int threeSumClosest(vector<int>& nums, int target) {int val = 0, begin, end, ret = 0, inTarget, gap;int size = nums.size();vector<int>::iterator beginIter, endIter;if (size <= 2)return 0;gap = INT_MAX;sort(nums.begin(), nums.end());for (int i = 0; i < size - 2; i++){inTarget = target - nums[i];beginIter = nums.begin() + i + 1;endIter = nums.end() - 1;while (beginIter < endIter){begin = *beginIter;end = *endIter;val = begin + end;if (val == inTarget){return target;}else if (val < inTarget){beginIter++;}else{endIter--;}if (abs(val - inTarget) < gap){gap = abs(val - inTarget);ret = val + nums[i];}}}return ret; }
};

17. 电话号码的字母组合
    给定一个仅包含数字 2-9 的字符串，返回所有它能表示的字母组合。
    给出数字到字母的映射如下（与电话按键相同）。注意 1 不对应任何字母。

比较便于理解的做法是采用递归，即深度优先的方式解决，代码也比较简洁易懂。先考虑最后的情况，通过递归回溯完成

class Solution
{vector<string> result;string digits;unordered_map<char, string> store;public:vector<string> letterCombinations(string digits){if (digits.empty()){return result;}this->digits = digits;//储存字典store = unordered_map<char, string>{{'2', "abc"}, {'3', "def"}, {'4', "ghi"}, {'5', "jkl"}, {'6', "mno"}, {'7', "pqrs"}, {'8', "tuv"}, {'9', "wxyz"}};dfs("", 0);return result;}void dfs(string resultStr, int index){int digitsSize = int(this->digits.size());if (digitsSize == index){result.push_back(resultStr);return;}char targetChar = this->digits[index];string targetStr = store[targetChar];for (auto tmpChar : targetStr){dfs(resultStr + tmpChar, index + 1);//递归调用}return;}
};

另一种做法当然就是广度优先，从第一位开始顺序向后判断，直至输入结束

class Solution
{vector<string> result;string digits;unordered_map<char, string> store;public:vector<string> letterCombinations(string digits){if (digits.empty()){return result;}this->digits = digits;//储存字典store = unordered_map<char, string>{{'2', "abc"}, {'3', "def"}, {'4', "ghi"}, {'5', "jkl"}, {'6', "mno"}, {'7', "pqrs"}, {'8', "tuv"}, {'9', "wxyz"}};queue<string> workQueue;workQueue.push("");for (auto targetChar : digits){string targetStr = store[targetChar];int queueSize = int(workQueue.size());//当前层，进行添加字符for (int i = 0; i < queueSize; ++i){string tmpStr = workQueue.front();workQueue.pop();for (auto tmpChar : targetStr){workQueue.push(tmpStr + tmpChar);}}}while (!workQueue.empty()){string tmpStr = workQueue.front();workQueue.pop();result.push_back(tmpStr);}return result;}
};

18. 四数之和
    给定一个包含 n 个整数的数组 nums 和一个目标值 target，判断 nums 中是否存在四个元素 a，b，c 和 d ，使得 a + b + c + d 的值与 target 相等？找出所有满足条件且不重复的四元组。

注意：

答案中不可以包含重复的四元组。

在前面做完三数之和后，本题显得简单无比，只要在外面再加一层循环嵌套即可

class Solution {
public:vector<vector<int>> fourSum(vector<int>& nums, int target) {if (nums.size() < 4) return {};sort(nums.begin(), nums.end());int N = nums.size();int maxSum3 = nums[N - 3] + nums[N - 2] + nums[N - 1];int maxSum2 = nums[N - 2] + nums[N - 1];vector<vector<int> > res;for (int i = 0; i < N - 3; ++i) {if (4 * nums[i] > target) break;if (i > 0 && nums[i] == nums[i - 1]) continue;if (nums[i] + maxSum3 < target) continue;for (int j = i + 1;j < N - 2; ++j) {if (2 * (nums[i] + nums[j]) > target) break;if (j > i + 1 && nums[j - 1] == nums[j]) continue;if (nums[i] + nums[j] + maxSum2 < target) continue;int t = target - nums[i] - nums[j];int l = j + 1;int r = N - 1;while (l < r) {if (nums[l] + nums[r] > t) {--r;} else if (nums[l] + nums[r] < t) {++l;} else {res.push_back({nums[i], nums[j], nums[l], nums[r]});while (l < r && nums[l] == nums[++l]);while (l < r && nums[r] == nums[--r]);}}}}return res;}
};

19. 删除链表的倒数第N个节点
    给定一个链表，删除链表的倒数第 n 个节点，并且返回链表的头结点。

很简单的一种做法是采用一个vector存储每个节点的指针，然后去掉第N个指针即可

/*** Definition for singly-linked list.* struct ListNode {*     int val;*     ListNode *next;*     ListNode(int x) : val(x), next(NULL) {}* };*/
class Solution {
public:ListNode* removeNthFromEnd(ListNode* head, int n) {vector<ListNode*> list;ListNode *ptr = head;while (ptr != NULL){list.push_back(ptr);ptr = ptr->next;}int locate = list.size() - n;if (locate == 0){return head->next;}ptr = list[locate - 1];if (n == 0)ptr->next = NULL;  else    ptr->next = ptr->next->next;return head;}
};

更巧妙的做法是采用双指针的方式：两个指针相距为n，则尾指针到底了就表示首指针是要删除的那个节点

/*** Definition for singly-linked list.* struct ListNode {*     int val;*     ListNode *next;*     ListNode(int x) : val(x), next(NULL) {}* };*/
class Solution{
public:ListNode* removeNthFromEnd(ListNode* head, int n) {ListNode *front = head;ListNode *rear = head;if(head->next == NULL) return NULL;while(n >= 0){if(rear == NULL) return head -> next;rear = rear->next;n --;}while(rear){rear = rear -> next;front = front -> next;}front->next = front->next->next;return head;}
};

20. 有效的括号
    给定一个只包括 ‘(’，’)’，’{’，’}’，’[’，’]’ 的字符串，判断字符串是否有效。
    有效字符串需满足：
    左括号必须用相同类型的右括号闭合。
    左括号必须以正确的顺序闭合。
    注意空字符串可被认为是有效字符串。

本题采用栈比较容易解决：对左半边括号采取入栈操作，右半边括号和栈顶进行对比，如果不一致则说明有问题

class Solution {
public:bool isValid(string s) {if (s.size() == 0) return true;char *stack = (char*)malloc(s.size()); int top =0;for (int i = 0; s[i]; ++i) {if (s[i] == '(' || s[i] == '[' || s[i] == '{') stack[top++] = s[i];else {if ((--top) < 0) //先减减，让top指向栈顶元素             return false;if (s[i] == ')' && stack[top] != '(') return false;if (s[i] == ']' && stack[top] != '[') return false;if (s[i] == '}' && stack[top] != '{') return false;}}free(stack);return (!top);}
};

21. 合并两个有序链表
    将两个有序链表合并为一个新的有序链表并返回。新链表是通过拼接给定的两个链表的所有节点组成的。

本题相对容易，仅需要一个前置指针用于返回，一个滑动指针用于指向目前位置，然后依次判断l1和l2的val大小来赋值即可

/*** Definition for singly-linked list.* struct ListNode {*     int val;*     ListNode *next;*     ListNode(int x) : val(x), next(NULL) {}* };*/
class Solution {
public:ListNode* mergeTwoLists(ListNode* l1, ListNode* l2) {ListNode *preHead, *ptr;preHead = new ListNode(-1);ptr = preHead;while (l1 != NULL && l2 != NULL){if (l1->val <= l2->val){         ptr->next = l1;    l1 = l1->next;                                 }else{ptr->next = l2;l2 = l2->next;}ptr = ptr->next;}ptr->next = (l1 == NULL? l2 : l1);return preHead->next;}
};

这篇关于leetcode解题思路分析（三）15-21题的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！

---