Leetcode 16-20题

最接近的三数之和

给定整数数组和目标值target，从数组中选出三个整数，使得和与target最接近，并返回三数之和。保证恰好存在一个解。

和上一题类似，我们先对整数数组排序，然后固定i，枚举j，找到满足nums[i]+nums[j]+nums[k]>=target的最小的k。

那么显然有nums[i]+nums[j]+nums[k-1]<target，只需要判断两者谁离target最接近即可。

int threeSumClosest(vector<int>& nums, int target) {sort(nums.begin(), nums.end());int delta = INT_MAX, sum = 0;for(int i = 0; i < nums.size() - 2; i ++) {if(i && nums[i] == nums[i - 1]) continue;for(int j = i + 1, k = nums.size() - 1; j < k; j ++) {if(j > i + 1 && nums[j] == nums[j - 1]) continue;while(k - 1 > j && nums[i] + nums[j] + nums[k - 1] >= target)   k --;// 找到固定i和j时满足三数之和大于等于目标值的k,可以保证i,j,k-1三数之和小于目标值int p = nums[i] + nums[j] + nums[k], q = nums[i] + nums[j] + nums[k - 1];if(abs(p - target) < delta) delta = abs(p - target), sum = p;// k-1不能和k相等if(k != j + 1 && abs(q - target) < delta) delta = abs(q - target), sum = q;}}return sum;
}

电话号码的字母组合

数字和字母的映射同电话按键，给定包含数字2-9的字符串，返回能表示的字母组合。

这是一道非常经典的DFS题。每一层只需要枚举这一位填哪个字母，然后到头输出再返回即可。

vector<string> to = {"", "", "abc", "def", "ghi", "jkl", "mno", "pqrs", "tuv", "wxyz"};
vector<string> ans;void dfs(string &digits, int u, string path) {if(path.size() == digits.size()) {      // 若字母串和数字串相同长度则得到答案ans.push_back(path);return ;}for(auto c : to[digits[u] - '0']) {     // 数字为digits[u] - '0'path += c;dfs(digits, u + 1, path);           // 迭代判断第u+1个数字path.pop_back();                    // 恢复现场}
}vector<string> letterCombinations(string digits) {if(!digits.size())  return ans;     // 若空直接返回dfs(digits, 0, "");return ans;
}

四数之和

给定整数数组和目标值，返回四数之和等于目标值且不重复的所有四元组。

数组长度为$[1,200]$，数的大小为$[-10^9,10^9]$。

和三数之和一样，只是多了一重循环而已。

但是这里要注意，可能会爆int，判断的时候要开long long。

vector<vector<int>> fourSum(vector<int>& nums, int target) {vector<vector<int>> ans;sort(nums.begin(), nums.end());for(int i = 0; i < nums.size(); i ++) {if(i && nums[i] == nums[i - 1]) continue;for(int j = i + 1; j < nums.size(); j ++) {if(j > i + 1 && nums[j] == nums[j - 1]) continue;for(int k = j + 1, l = nums.size() - 1; k < l; k ++) {  // 固定i,j,kif(k > j + 1 && nums[k] == nums[k - 1]) continue;// 强转为long long来判断while(l-1 > k && 0ll + nums[i] + nums[j] + nums[k] + nums[l - 1] >= 1ll * target)  l--;if(0ll + nums[i] + nums[j] + nums[k] + nums[l] == target * 1ll)ans.push_back({nums[i], nums[j], nums[k], nums[l]});}}}return ans;
}

删除链表的倒数第N个结点

删除链表的倒数第 n 个结点，并且返回链表的头结点。

先扫描一边链表得到链表长度，然后再正着删除这个节点即可。可以使用虚拟头节点来取消对头节点的特判。

删除第k个节点的方法就是将第k-1个节点的next指针指向第k+1个节点。

ListNode* removeNthFromEnd(ListNode* head, int n) {ListNode* damn = new ListNode(-1, head);    // 虚拟头节点int len = 0;for(auto p = head; p; p = p->next)  len ++; // 原链表的长度// 1 2 3 4 5// len=5,倒数第2个是从实际头节点开始的正数第4个(len-n+1)// 倒数第n个节点就是从虚拟头节点开始正数第len - n + 2个节点// 那么从虚拟头节点要往后走len-n次才能到实际要删的节点的前面一个节点auto p = damn;for(int i = 1; i <= len - n; i ++)  p = p->next;// 要删第k个节点，就将第k-1个节点的next指针指向第k+1个节点p->next = p->next->next;return damn->next;
}

有效的括号

给定只包含()[]{}的字符串，判断是否有效。

有效的标准是左右括号必须相邻且匹配。

一道经典的栈题。遇到左括号则入栈，遇到右括号则判断栈顶的左括号和当前右括号是否匹配。

最后判断栈是否为空，若栈不为空则不匹配。

左括号(的ASCII为40， 右括号)的ASCII码为41。

左括号[的ASCII为91， 右括号]的ASCII码为93。

左括号{的ASCII为123， 右括号}的ASCII码为125。

所以只要左括号和右括号的ASCII码的差的绝对值小于等于2，则可以判断匹配。

bool isValid(string s) {stack<char> st;for(auto c : s) {if(c == '(' || c == '[' || c == '{')    st.push(c);else {// 一定要加abs来判断距离,否则会导致91-123=-32的情况出现if(st.size() && abs(c - st.top()) <= 2)  st.pop();else    return false;}}return st.empty();
}