LeetCode究极刷题班( 四 )

< s.size(); i++) {if(i + 1 < s.size() && heap[s[i]] < heap[s[i + 1]]) res -= heap[s[i]];else res += heap[s[i]];}return res;}};
14. 最长公共前缀
思想
通过暴力做法:第一层循环遍历每一位 , 第二层循环遍历i位置的每一个字符串是否相等
class Solution {public:string longestCommonPrefix(vector>& strs) {string res;if(strs.empty()) return res;for(int i = 0; i < strs[0].size(); i++) {char c = strs[0][i];for(auto stri : strs) {if(i > stri.size() || c != stri[i]) return res;}res += c;}return res;}};
启发:增强for循环这里第二层循环就很好用 , 可以快速取出strs中的每一个字符串
15. 三数之和
思想
这题目和后面一些题目都是类似的方法 , 都会用到双指针算法 , 而双指针算法需要明确的第一件事——数组是有序的 。因为这个题目里面一共有三个变量 , 定义 i,j,k三个指针 , 没有三指针算法 , 所以需要先固定一个指针i , 默认三个指针大小顺序是 i < j < k , 可以减少一部分重复 , 固定了i指针 , j从i后面开始遍历 , k从尾部倒序遍历 , 目标是找出满足 nums[i] + nums[j] + nums[k] >= 0 的最小的k  , 这样能够简化时间复杂度的运用是排完序以后 , 如果j增加 , 那么k一定只能往左走 , 因为nums[i]是固定的 。
重复的问题怎么解决?从i入手 , 每一次先判断i位置的数值和上个是否相同 , 相同就跳过 。
class Solution {public:vector> threeSum(vector& nums) {vector> res;sort(nums.begin(), nums.end());//第一个指针i遍历整个集合for(int i = 0; i < nums.size(); i++) {//i 不等于0 并且 第i个数和i - 1相同的时候是重复的情况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;//试探性查看k - 1是不是最小能取到的值while(j < k - 1 && nums[i] + nums[j] + nums[k - 1] >= 0) k--;if(nums[i] + nums[j] + nums[k] == 0) res.push_back({nums[i], nums[j], nums[k]});}}return res;}};
16. 最接近的三数之和
思想
这题和上面的题目解法是类似的 , 并且这个问题最后只需要返回结果数值 , 所以可以省去去重的过程 , 但是需要注意的一个问题是最终结果可能是nums[i] + nums[j] + nums[k] (大于)或者nums[i] + nums[j] + nums[k - 1](小于)
class Solution {public:int threeSumClosest(vector& nums, int target) {//第一步先排序sort(nums.begin(), nums.end());//pair数组first存放和target的插值 , second存放实际数值pair res(INT_MAX, INT_MAX);for(int i = 0; i < nums.size(); i++) {for(int j = i + 1, k = nums.size() - 1; j < k; j++) {while(j < k - 1 && nums[i] + nums[j] + nums[k - 1] >= target) k--;int s = nums[i] + nums[j] + nums[k];res = min(res, make_pair(abs(s - target), s));//这个特判不可少if(j < k - 1) {int n = nums[i] + nums[j] + nums[k - 1];res = min(res, make_pair(target - n, n));}}}return res.second;}};
17. 电话号码的字母组合
思想
需要找出所有的排序方式 , 这个问题是典型的DFS暴搜问题 , 这里我们先来回顾一下DFS知识点 。DFS中比较重要的两个概念是回溯和剪枝 。
例题:给定一个整数n , 将数字1~n排成一排 , 请你按照字典序将所有的排列方法输出 。这就是一个最经典的DFS问题 , 思考DFS问题我们首先需要画出搜索树 , 这样能够帮助我们理解DFS过程 , DFS就是从第一个位置开始一直往下搜索知道没有路可以走 , 再回溯 。