16. 最接近的三数之和

题目:https://leetcode-cn.com/problems/3sum-closest/

解法一:双指针 $O(n^2)$

  1. 思路基本同三数之和
class Solution {
public:
    int threeSumClosest(vector<int>& nums, int target) {
        sort(nums.begin(),nums.end());
        if(nums.size()<3) return 0;
        int res = nums[0] + nums[1] + nums[2];
        for(int i=0;i<nums.size();i++){
            int left = i + 1;
            int right = nums.size() - 1;
            while(left < right){
                int tmp = nums[i] + nums[left] + nums[right];
                if(tmp < target) left++;
                else if(tmp > target) right--;
                else return tmp; // 正中靶心

                if(abs(res-target) > abs(tmp-target)) res = tmp;
            }
        }
        return res;
    }
};

20. 有效的括号

题目:https://leetcode-cn.com/problems/valid-parentheses/

解法一:栈 $O(n)$

  1. 经典面试题,对于给定字符串,遍历时我们希望遇到任意一个左括号(,[,{时,在后续的遍历中都可以优先有其对应的右括号进行闭合操作。
  2. 数据结构中的栈可以完美匹配这一过程。
class Solution {
public:
    bool isValid(string s) {
        stack<char> st;
        for(char c : s){
            if(c == '(' || c == '[' || c == '{') st.push(c);
            else{
                if(st.empty()) return false;
                if((c == ')' && st.top() == '(') || 
									 (c == ']' && st.top() == '[') ||
									 (c == '}' && st.top() == '{')) st.pop();
                else return false;
            }
        }
        return st.empty();
    }
};

21. 合并两个有序链表

题目:https://leetcode-cn.com/problems/merge-two-sorted-lists/

解法一:递归

/**
 * 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) {
        if(l1==nullptr) return l2;
        if(l2==nullptr) return l1;
        if(l1->val <= l2->val){
            l1->next = mergeTwoLists(l1->next,l2);
            return l1;
        }else{
            l2->next = mergeTwoLists(l1,l2->next);
            return l2;
        }
    }
};

解法二:非递归

/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     struct ListNode *next;
 * };
 */

struct ListNode* mergeTwoLists(struct ListNode* l1, struct ListNode* l2){
    if(l1==NULL){return l2;}
    if(l2==NULL){return l1;}
    struct ListNode* new_head = (struct ListNode*)malloc(sizeof(struct ListNode));
    struct ListNode* b = new_head;
    while(l1!=NULL && l2!=NULL){
        if(l1->val <= l2->val){
            new_head->next = l1;
            new_head = l1;
            l1 = l1->next;
        }else{
            new_head->next = l2;
            new_head = l2;
            l2 = l2->next;
        }
    }
    if(l1==NULL && l2!=NULL){
        new_head->next = l2;
    }else if(l1!=NULL && l2==NULL){
        new_head->next = l1;
    }
    return b->next;
}