最接近的三數(shù)之和

給定整數(shù)數(shù)組和目標(biāo)值target，從數(shù)組中選出三個(gè)整數(shù)，使得和與target最接近，并返回三數(shù)之和。保證恰好存在一個(gè)解。

和上一題類似，我們先對(duì)整數(shù)數(shù)組排序，然后固定i，枚舉j，找到滿足nums[i]+nums[j]+nums[k]>=target的最小的k。

那么顯然有nums[i]+nums[j]+nums[k-1]<target，只需要判斷兩者誰(shuí)離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時(shí)滿足三數(shù)之和大于等于目標(biāo)值的k,可以保證i,j,k-1三數(shù)之和小于目標(biāo)值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;
}

電話號(hào)碼的字母組合

數(shù)字和字母的映射同電話按鍵，給定包含數(shù)字2-9的字符串，返回能表示的字母組合。

這是一道非常經(jīng)典的DFS題。每一層只需要枚舉這一位填哪個(gè)字母，然后到頭輸出再返回即可。

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()) {      // 若字母串和數(shù)字串相同長(zhǎng)度則得到答案ans.push_back(path);return ;}for(auto c : to[digits[u] - '0']) {     // 數(shù)字為digits[u] - '0'path += c;dfs(digits, u + 1, path);           // 迭代判斷第u+1個(gè)數(shù)字path.pop_back();                    // 恢復(fù)現(xiàn)場(chǎng)}
}vector<string> letterCombinations(string digits) {if(!digits.size())  return ans;     // 若空直接返回dfs(digits, 0, "");return ans;
}

四數(shù)之和

給定整數(shù)數(shù)組和目標(biāo)值，返回四數(shù)之和等于目標(biāo)值且不重復(fù)的所有四元組。

數(shù)組長(zhǎng)度為$[1,200]$，數(shù)的大小為$[?10^9,10^9]$。

和三數(shù)之和一樣，只是多了一重循環(huán)而已。

但是這里要注意，可能會(huì)爆int，判斷的時(shí)候要開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;// 強(qiáng)轉(zhuǎn)為long long來(lái)判斷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;
}

刪除鏈表的倒數(shù)第N個(gè)結(jié)點(diǎn)

刪除鏈表的倒數(shù)第 n 個(gè)結(jié)點(diǎn)，并且返回鏈表的頭結(jié)點(diǎn)。

先掃描一邊鏈表得到鏈表長(zhǎng)度，然后再正著刪除這個(gè)節(jié)點(diǎn)即可?？梢允褂?strong>虛擬頭節(jié)點(diǎn)來(lái)取消對(duì)頭節(jié)點(diǎn)的特判。

刪除第k個(gè)節(jié)點(diǎn)的方法就是將第k-1個(gè)節(jié)點(diǎn)的next指針指向第k+1個(gè)節(jié)點(diǎn)。

ListNode* removeNthFromEnd(ListNode* head, int n) {ListNode* damn = new ListNode(-1, head);    // 虛擬頭節(jié)點(diǎn)int len = 0;for(auto p = head; p; p = p->next)  len ++; // 原鏈表的長(zhǎng)度// 1 2 3 4 5// len=5,倒數(shù)第2個(gè)是從實(shí)際頭節(jié)點(diǎn)開始的正數(shù)第4個(gè)(len-n+1)// 倒數(shù)第n個(gè)節(jié)點(diǎn)就是從虛擬頭節(jié)點(diǎn)開始正數(shù)第len - n + 2個(gè)節(jié)點(diǎn)// 那么從虛擬頭節(jié)點(diǎn)要往后走len-n次才能到實(shí)際要?jiǎng)h的節(jié)點(diǎn)的前面一個(gè)節(jié)點(diǎn)auto p = damn;for(int i = 1; i <= len - n; i ++)  p = p->next;// 要?jiǎng)h第k個(gè)節(jié)點(diǎn)，就將第k-1個(gè)節(jié)點(diǎn)的next指針指向第k+1個(gè)節(jié)點(diǎn)p->next = p->next->next;return damn->next;
}

有效的括號(hào)

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

有效的標(biāo)準(zhǔn)是左右括號(hào)必須相鄰且匹配。

一道經(jīng)典的棧題。遇到左括號(hào)則入棧，遇到右括號(hào)則判斷棧頂?shù)淖罄ㄌ?hào)和當(dāng)前右括號(hào)是否匹配。

最后判斷棧是否為空，若棧不為空則不匹配。

左括號(hào)(的ASCII為40， 右括號(hào))的ASCII碼為41。

左括號(hào)[的ASCII為91， 右括號(hào)]的ASCII碼為93。

左括號(hào){的ASCII為123， 右括號(hào)}的ASCII碼為125。

所以只要左括號(hào)和右括號(hào)的ASCII碼的差的絕對(duì)值小于等于2，則可以判斷匹配。

bool isValid(string s) {stack<char> st;for(auto c : s) {if(c == '(' || c == '[' || c == '{')    st.push(c);else {// 一定要加abs來(lái)判斷距離,否則會(huì)導(dǎo)致91-123=-32的情況出現(xiàn)if(st.size() && abs(c - st.top()) <= 2)  st.pop();else    return false;}}return st.empty();
}