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就是从第一个位置开始一直往下搜索知道没有路可以走，再回溯。