最接近的三数之和
给定整数数组和目标值
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,k
if(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();
}