LeetCode中级刷题

前言：由于开题好长时间不刷题了，中级的算法题好难啊！一定要再次坚持下去。

• 数组与字符串
• • 1、三数之和
  • 2、矩阵置零
  • 3、字母异位词
  • 4、无重复字符的最长子串
  • 5、最长回文子串

1）题目：

2）解析：排序+双指针（参考官方解法）
注意关键词：不重复。要用三重循环来解决此题
如果我们固定了前两重循环枚举到的元素 a 和 b，那么只有唯一的 c 满足 a+b+c=0。当第二重循环往后枚举一个元素 b’时，由于 b’ > b，那么满足 a+b’+c’=0的 c’ 一定有 c’ < c，即 c’在数组中一定出现在 c的左侧。也就是说，我们可以从小到大枚举 b，同时从大到小枚举 c，即第二重循环和第三重循环实际上是并列的关系。
有了这样的发现，我们就可以保持第二重循环不变，而将第三重循环变成一个从数组最右端开始向左移动的指针，
这个方法就是我们常说的「双指针」，当我们需要枚举数组中的两个元素时，如果我们发现随着第一个元素的递增，第二个元素是递减的，那么就可以使用双指针的方法，将枚举的时间复杂度从 O(N^2) 减少至 O(N)。
总结：
a、把数组排序
b、三重循环，第一重从0 到length-2 遍历数组；第二重从i+1开始遍历；第三重从length-1开始遍历
c、比较nums[left] + nums[right] 与 nums[i]的关系；若相等，推入数组；若小于，left指针右移；若大于，right指针左移。
d、注意两次“去重”，第一次是三重循环，第二重从小到大，第三重从大到小；第二次，若比较相等left右移找到不等的值，right左移。

vector> threeSum(vector& nums) {
		sort(nums.begin(), nums.end());
		int length = nums.size();
		vector> vec;
		for (int i = 0; i < length-2; i++)
		{
			//过滤重复
			if (i > 0 && nums[i] == nums[i - 1])
				continue;
			//第二重循环从小到大枚举
			int left = i + 1; 
			//第三重循环从大到小枚举
			int right = length - 1;
			while (left < right)
			{
				if (nums[left] + nums[right] + nums[i] == 0) {
					vec.push_back(vector());
					vec.back().push_back(nums[left]);
					vec.back().push_back(nums[right]);
					vec.back().push_back(nums[i]);
					//过滤重复
					//注意left与他的下一个left+1比较，不是前一个left-1哦，刚开始想的left-1一直不对，
					while (left < right && nums[left] == nums[left + 1])
					{
						left++;
					}
					//过滤重复
					//注意right与他的上一个right-1比较，不是前一个right+1哦，刚开始想的right+1一直不对，
					while (left < right && nums[right] == nums[right - 1])
					{
						right--;
					}
					left++;
					right--;
				}
				//因为已经排序过了，(-nums[i])作为目标元素，如果nums[left] + nums[right]小于目标值，让left向右移动就会变大
				else if (nums[left] + nums[right] < (-nums[i])) {
					left++;
				}
				else
				{
					//right向左移动相加值就会变小
					right--;
				}
				
			}	
		}
		return vec;

	}

1）题目： 给定一个n*n的矩阵，如果一个元素为0，则将其所在行和列的元素都设为0，请使用“原地”算法。

2)思路一：
第一次循环把是0的位置的行数和列数存在队列里，（pair可以把两个元素合并成一个元素）；第二次循环把对应元素置0。

//空间复杂度：O(m + n)
	void setZeroes2(vector>& matrix) {
		//第一次遍历把0元素的行和列存在队列中
		//pair 将两个数据组合成一个数据
		//当一个函数需要两个数据时，也可以用pair                    
		queue> rot;
		//行数
		int line = matrix.size();
		//列数
		int row = matrix[0].size();
		for (int i = 0; i < line; i++)
		{
			for (int  j = 0; j < row; j++)
			{
				if (matrix[i][j] == 0)
					rot.emplace(i, j);
			}
		}
		//第二次遍历把对应元素改为0
		while (!rot.empty())
		{
			//行
			int h = rot.front().first;
			//列
			int l = rot.front().second;
			rot.pop();
			for (int i = 0; i < line; i++)
			{
				matrix[i][l] = 0;
			}
			for (int j = 0; j < row; j++)
			{
				matrix[h][j] = 0;
			}
		}
	}

3）思路二：
用两个标记数组代替思路一的队列，一个标记行，一个标记列。如果元素为0，就把元素对应的行数和列数标记为true。第二次遍历，再把行数或列数为true的元素置0。

	//空间复杂度：O(m + n)
	//用两个标记数组代替下面的队列
	void setZeroes3(vector>& matrix) {
		int m = matrix.size();
		int n = matrix[0].size();
		vector row(m), col(n);
		for (int i = 0; i < m; i++) {
			for (int j = 0; j < n; j++) {
				if (!matrix[i][j]) {
					row[i] = col[j] = true;
				}
			}
		}
		for (int i = 0; i < m; i++) {
			for (int j = 0; j < n; j++) {
				if (row[i] || col[j]) {
					matrix[i][j] = 0;
				}
			}
		}
	}

4）思路三：
把矩阵的第一行和第一列作为标记数组。
第一次遍历所有元素，如果matrix[i][j]是0就把第一行第一列对应的行和列（matrix[i][0] matrix[0][j]）置0，如果第一行或第一列原本就有0，用flag_row或flag_col标记一下。
第二次遍历除第一行第一列以外的其他元素，如果他所在对应的matrix[i][0] matrix[0][j]为0，则把该元素置为0。
如果第一行或第一列原本就有0（flag_row或flag_col为true），就把第一行或第一列置0。

//我们可以用矩阵的第一行和第一列代替方法一中的两个标记数组，以达到 O(1) 的额外空间。
	void setZeroes(vector>& matrix) {
		int m = matrix.size();
		int n = matrix[0].size();
		//标记第一行是否有数字0
		int flag_row = false;
		//标记第一列是否有数字0
		int flag_col = false; 
		for (int i = 0; i < m; i++)
		{
			//如果matrix[i][j]是0就把第一行第一列对应的行和列（matrix[i][0] matrix[0][j]）置0
			for (int j = 0; j < n; j++) {
				if (matrix[i][j] == 0) {
					//如果第一行或第一列原本就有0，标记一下
					if (i == 0)
						flag_row = true;
					if (j == 0)
						flag_col = true;
					matrix[i][0] = matrix[0][j] = 0;
				}
			}
		}
		//遍历除第一行第一列以外的其他元素，如果他所在对应的matrix[i][0] matrix[0][j]为0，则把该元素置为0
		for (int i = 1; i < m; i++)
		{
			for (int j = 1; j < n; j++) {
				if (!matrix[i][0] || !matrix[0][j]) {
					matrix[i][j] = 0;
				}
			}
		}
		//如果第一行原本就有0，就把第一行置0
		if (flag_row)
		{
			for (int i = 0; i < n; i++)
			{
				matrix[0][i] = 0;
			}
		}
		//如果第一列原本就有0，就把第一列置0
		if (flag_col)
		{
			for (int j = 0; j < m; j++)
			{
				matrix[j][0] = 0;
			}
		}

	}

1）题目：

2）思路：由于互为字母异位词的两个字符串包含的字母相同，因此对两个字符串分别进行排序之后得到的字符串一定是相同的，故可以将排序之后的字符串作为哈希表的键。

	vector> groupAnagrams(vector& strs) {
		//对字符串数组中的每一个字符串排序，排序结果相同的就是字母异位词
		//键值是源字符串，键是排序后的字符串。妙妙妙！！!
		//unordered_map 哈希映射 无序  map是有序容器
		unordered_map> stp;
		vector> res;
		int length = strs.size();
		//注意是 string& 不是 string
		for (string& str : strs) {
			string key = str;
			sort(key.begin(), key.end());
			stp[key].emplace_back(str);//stp[key]表示key这组异位词的集合
			
		}
		//unordered_map 前向迭代期
		for (auto it = stp.begin(); it != stp.end(); ++it) {
			res.emplace_back(it->second);//遍历哈希表，将字母异位词的集合存入结果集中
		}
		return res;
	}

1）题目：

2）思路：
定义一个bool型的标记数组str[255]，字母s[i]出现以后，对应的str[s[i]]=true；当字母再次出现时，追溯到第一次出现的位置j，无重复字符的长度就是 i-j+1;

int lengthOfLongestSubstring(string s) {
		//双指针，i指针是遍历字符串，j指针回溯
		int length = s.size();
		bool nums[255] = { false };
		int j = 0,maxnum=0;
		for (int i = 0; i < length; i++)
		{
			//2、访问到重复字符，将其推移,直到找到第一个重复字符
			while (nums[s[i]])
			{
				nums[s[j]] = false;
				++j;
			}
			//1、每访问一个新的字符，就将其进行标记
			nums[s[i]] = true;
 			maxnum = max(maxnum, i - j + 1);
		}
		return maxnum;
	}

1）题目：

2）思路：中心扩散法
回文子串中心互为镜像，因此，回文可以从他的中心展开，奇数有一个中心点，偶数有两个中心点。

//最长回文串（毫无头绪啊！！！！！！）
	//中心扩展法
	string longestPalindrome(string s) {
		int length = s.size();
		if (length < 2)
			return s;
		int start = 0;//最长回文串起始位置
		int end = 0;//终止位置
		int maxlength = 0;
		for (int i = 0; i < length; i++)
		{
			int odd = strlength(s, i, i);//奇数中心
			int even = strlength(s, i, i + 1);//偶数中心
			maxlength = max(max(odd, even), maxlength);
			if (maxlength > (end - start + 1)) {
				start = i - (maxlength - 1) / 2;
				end = i + maxlength / 2;
			}
		}
		return s.substr(start, maxlength); //该函数的意思是获取从start开始长度为mlen长  度的字符串
	}
	//以left和right为中心的回文串长度
	int strlength(string s, int left, int right) {
	//注意left可以取到0
		while ( left>=0 &&  right