【六月算法集训 】第五天之双指针

《算法集训传送门》   👉引言

	铭记于心
	🎉✨🎉我唯一知道的，便是我一无所知🎉✨🎉

---

💖 ❄️我们的算法之路❄️💖

   众所周知，作为一名合格的程序员，算法 能力 是不可获缺的，并且在class="superseo">算法学习的过程中我们总是能感受到算法的✨魅力✨。
               ☀️🌟短短几行代码，凝聚无数前人智慧；一个普通循环，即是解题之眼🌟☀️
   💝二分，💝贪心，💝并查集，💝二叉树，💝图论，💝深度优先搜索(dfs)，💝宽度优先搜索（bfs），💝数论，💝动态规划等等， 路漫漫其修远兮，吾将上下而求索！ 希望在此集训中与大家共同进步，有所收获！！！🎉🎉🎉

---

今日主题：双指针

---

 👉⭐️第一题💎    ✨题目

      2000. 反转单词前缀

   ✨思路：

遍历字符串找到该索引，然后反转（我这里用到STL的reverse函数，还可以用双指针i,n-i-1，或者开辟个新字符串，将原字符串逆序存储其中，进行反转）

   ✨代码：

class Solution {
public:
   string reversePrefix(string word, char ch) {
	string::iterator it = find(word.begin(), word.end(), ch);
	int po = it==word.end()?-1: it- word.begin();
	if (po == -1)return word;
	reverse(word.begin(), word.begin() + po + 1);
	return word;
}
};

 👉⭐️第二题💎    ✨题目

      917. 仅仅反转字母

将非字母字符隔离开来，剩余的进行反转

   ✨代码：

class Solution {
public:
string reverseOnlyLetters(string s) {
	string d1="";
	for (char ch : s) {
		if (!isalpha(ch))continue;
		d1 += ch;
	}
	reverse(d1.begin(), d1.end());
	int j = 0;
	for (int i = 0; i < s.size(); i++) {
		if (!isalpha(s[i]))continue;
		s[i] = d1[j++];
	}
	return s;
}
};

 👉⭐️第三题💎💎💎    ✨题目

      475. 供暖器

   ✨思路：

遍历第一个数组中每一个值，然后找heaters数组中距离该数组最近的一个值，然后取这些值中的最大，便得到最小半径

   ✨代码：

class Solution {
public:
int findRadius(vector<int>& houses, vector<int>& heaters) {
	sort(houses.begin(), houses.end());
	sort(heaters.begin(), heaters.end());
	int dist0 = 0;
	for (int i = 0; i < houses.size(); i++) {
		vector<int>::iterator it = lower_bound(heaters.begin(), heaters.end(), houses[i]);
		if (it != heaters.end() && *it == houses[i]) { continue; }
		int temp = it - heaters.begin() - 1;
		if (it == heaters.end()) { temp = (heaters.size() - 1);
		}
		int dist =  temp < 0 ? heaters[temp + 1] - houses[i] : houses[i] - heaters[(temp)];
		dist = min(temp + 1 == heaters.size() ? houses[i] - heaters[(temp)] : heaters[temp + 1] - houses[i], dist);
		dist0 = max(dist0, dist);
	}
	return dist0;
}
};

😉

 👉⭐️第四题💎💎💎    ✨题目

      面试题 16.06. 最小差

   ✨思路：

在上题的基础上更改一下数值范围即可，需注意如果找到两个数组中存在相同的值直接返回0即可

   ✨代码：

class Solution {
public:
int smallestDifference(vector<int>& houses, vector<int>& heaters) {
	sort(houses.begin(), houses.end());
	sort(heaters.begin(), heaters.end());
	long long dist0 = 2147483647;
	for (int i = 0; i < houses.size(); i++) {
		vector<int>::iterator it = lower_bound(heaters.begin(), heaters.end(), houses[i]);
		if (it != heaters.end() && *it == houses[i]) { return 0; }
		long long dist =0;
		if (it == heaters.end())dist = (long long)houses[i] - (long long)heaters.back();
		else if (!(it - heaters.begin()))dist = (long long)heaters[0] - (long long)houses[i];
		else {
			int temp = it - heaters.begin() - 1;
			dist = min(((long long)houses[i] - (long long)heaters[temp]), (long long)heaters[temp+1] - (long long)houses[i]);
		}
		dist0 = min(dist0, dist);
	}
	return dist0;
}
};

---

  ⭐️总结⭐️

对于双指针，需要注意的就是边界以及移动时机，有时候一个边界把握的不好就会得出千奇百怪的结果

写在最后：
相信大家对今天的集训内容的理解与以往已经有很大不同了吧，或许也感受到了算法的魅力,当然这是一定的，路漫漫其修远兮，吾将上下而求索！伙伴们，明天见！