代码随想录刷题Day21

哈希表系列刷题小结

哈希表系列的题目做完，感觉似乎应用到的真正和哈希有关的概念，体现的不是很足，当然这种体验也可能和我对哈希表的理解有很大关联。我认为哈希表最关键的部分是哈希冲突，以及哈希表为了避免哈希冲突而采取的减缓机制，这在这之前刷到的题目没有太多体现。

这期题目做完，感觉这些题其实还是在解决数组问题，只是数组问题进阶了，需要融入一些统计的思想。

比如有效的字母异位词、赎金信、两个数组的交集、快乐数这一类比较简单的数组“互异”。

另一类是求N数之和，两数之和，一边遍历并记住值，一边检查已经遍历过的值里是否有和当前遍历到的值和为target的数。

四数之和II分析对象是四个数组，计算四个数组有多少种取值搭配可以使得四个数和为0，由于分析的是四个数组，不涉及到去重操作，以及答案是关于方案的次数，而不是具体的值，可以把原本四层循环遍历求值的题简化为两次的两层循环遍历，依次求出（a+b）并存储下来，求出-(c+d)并查找是否有（a+b） ==  -(c+d），从而进行统计达到要求的次数。

三数之和，以及四数之和，借用排序和双指针来降低一层复杂度。三数之和，是对a逐一遍历，使用双指针来确定b和c的指针，只是要注意，a,b,c的值不能重复，也就是在移动的时候，得是移动到下一个不一样的值才行，而不是沿着数组移动到下一个值就停。四数之和，就是对a和b逐一遍历，双指针确定c,d，这里要注意的点出了这四个数的去重，还有数的越界的可能性，需要进一步分析。

接下来开启字符串类型的题目刷题。

反转字符串

这个题目借用双指针的思路还是很快可以求解出来的。左指针从字符串头部开始遍历，右指针从尾部开始遍历，并交换左右指针的内容，这样实现原地的反转。

代码如下：

class Solution {
public:void reverseString(vector<char>& s) {int left = 0;int right = s.size()-1;char tmp;while(left < right){tmp = s[left];s[left]= s[right];s[right]= tmp;left ++;right--;}}
};

这里我还试过直接使用C++的库函数swap函数，发现swap函数比我这样手动实现两个数的原地交换会占用更多的空间，所以对于比较简单的交换，手动实现比较经济。

反转字符串II

这道题是每隔一个周期2k，前k个字符串对字符串进行反转，后k个字符保持原始位置。要额外处理的细节是，如果不满一个周期k字符串就要结束，则需要反转或者保持原始位置的字符串的数目需要相应地改变。思路大致如下：

代码：

class Solution {
public:string reverseStr(string s, int k) {int i = 0;  //当前遍历s的索引int p = 0;  //sR字符串的索引int cnt = k;    //用于计数的变量char sR[10001];while(1){cnt = s.size()-i < k?s.size()-i:k;p = i + cnt -1;while(cnt >0){  //反转cnt个字符sR[p--] = s[i++];cnt--;}if(i == s.size()) break;p = i;cnt = s.size()-i < k?s.size()-i:k;while(cnt>0){   //cnt个字符保持不变sR[p++]=s[i++];cnt--;}if(i == s.size()) break;}return string(sR);}
};

这两道题都可以直接使用基本的数组操作方法结合双指针来解决，比较顺利完成。