苏州网站建设功能,火车头采集器网站被k,福建微网站建设价格,整站优化cms最接近的三数之和 给定整数数组和目标值target#xff0c;从数组中选出三个整数#xff0c;使得和与target最接近#xff0c;并返回三数之和。保证恰好存在一个解。 和上一题类似#xff0c;我们先对整数数组排序#xff0c;然后固定i#xff0c;枚举j#xff0c;找到满…最接近的三数之和 给定整数数组和目标值target从数组中选出三个整数使得和与target最接近并返回三数之和。保证恰好存在一个解。 和上一题类似我们先对整数数组排序然后固定i枚举j找到满足nums[i]nums[j]nums[k]target的最小的k。
那么显然有nums[i]nums[j]nums[k-1]target只需要判断两者谁离target最接近即可。
int threeSumClosest(vectorint 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题。每一层只需要枚举这一位填哪个字母然后到头输出再返回即可。
vectorstring to {, , abc, def, ghi, jkl, mno, pqrs, tuv, wxyz};
vectorstring 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] - 0path c;dfs(digits, u 1, path); // 迭代判断第u1个数字path.pop_back(); // 恢复现场}
}vectorstring letterCombinations(string digits) {if(!digits.size()) return ans; // 若空直接返回dfs(digits, 0, );return ans;
}四数之和 给定整数数组和目标值返回四数之和等于目标值且不重复的所有四元组。 数组长度为 [ 1 , 200 ] [1,200] [1,200]数的大小为 [ − 1 0 9 , 1 0 9 ] [-10^9, 10^9] [−109,109]。 和三数之和一样只是多了一重循环而已。
但是这里要注意可能会爆int判断的时候要开long long。
vectorvectorint fourSum(vectorint nums, int target) {vectorvectorint 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指针指向第k1个节点。
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// len5,倒数第2个是从实际头节点开始的正数第4个(len-n1)// 倒数第n个节点就是从虚拟头节点开始正数第len - n 2个节点// 那么从虚拟头节点要往后走len-n次才能到实际要删的节点的前面一个节点auto p damn;for(int i 1; i len - n; i ) p p-next;// 要删第k个节点就将第k-1个节点的next指针指向第k1个节点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) {stackchar 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();
}
