算法刷题（七）：LC中级算法（数组和字符串）

三数之和

给你一个包含 n 个整数的数组 nums，判断 nums 中是否存在三个元素 a，b，c ，使得 a + b + c = 0 ？请你找出所有和为 0 且不重复的三元组。

注意：答案中不可以包含重复的三元组。

示例 1：

输入：nums = [-1,0,1,2,-1,-4]
输出：[[-1,-1,2],[-1,0,1]]

  

 

  
1
  
2
 

示例 2：

输入：nums = []
输出：[]

  

 

  
1
  
2
 

示例 3：

输入：nums = [0]
输出：[]

  

 

  
1
  
2
 

提示：

0 <= nums.length <= 3000
-10^5 <= nums[i] <= 10^5

  

 

  
1
  
2
 

作者：力扣 (LeetCode)
链接：https://leetcode-cn.com/leetbook/read/top-interview-questions-medium/xvpj16/
来源：力扣（LeetCode） 著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。

思路：
两数和的双指针法熟悉吗？开头一个指针，末尾一个指针，头尾加起来大于0，说明太大，末尾后退；头尾加起来小于0，说明太小，开头前进；加起来刚好等于0，那就存起来，头尾都靠近一位。

那么现在是三指针，其实也好办，开头一个标志位，则以标志位后面一位为两数和中的头，尾不变，一轮走完之后标志位后移一位，以此类推、

这里需要注意去重，如果标志位和前一位一样，则标志位再后移一位。
如果“头指针”的值和前面一位相同，则再前进一位。
如果“尾指针”的值和前面一位相同，则再后退一位。

代码实现：

class Solution {
public: vector<vector<int>> threeSum(vector<int>& nums) { vector<vector<int>> result; int num = nums.size(); sort(nums.begin(),nums.end()); if(nums.empty() || nums.front()>0 || nums.back()<0) return {}; for(int i = 0;i<num-2;i++){ if(nums[i]>0) break; if(i>0&&nums[i] == nums[i-1]) continue; int head = i+1; int tail = num-1; while(head<tail){ if(nums[head]+nums[tail] == -nums[i]){ if(head == i+1 || tail == num-1){ result.push_back(vector<int>{nums[i],nums[head],nums[tail]}); head++;tail--; } else if(nums[head] == nums[head-1]){ head++; } else if(nums[tail] == nums[tail+1]){ tail--; } else{ result.push_back(vector<int>{nums[i],nums[head],nums[tail]}); head++;tail--; } } else if(nums[head]+nums[tail]<-nums[i]){ head ++; } else{ tail--; } } } return result; }
};

  

 

  
1
  
2
  
3
  
4
  
5
  
6
  
7
  
8
  
9
  
10
  
11
  
12
  
13
  
14
  
15
  
16
  
17
  
18
  
19
  
20
  
21
  
22
  
23
  
24
  
25
  
26
  
27
  
28
  
29
  
30
  
31
  
32
  
33
  
34
  
35
  
36
  
37
  
38
  
39
  
40
  
41
 

矩阵置零

给定一个 m x n 的矩阵，如果一个元素为 0 ，则将其所在行和列的所有元素都设为 0 。请使用 原地 算法。

进阶：

一个直观的解决方案是使用  O(mn) 的额外空间，但这并不是一个好的解决方案。
一个简单的改进方案是使用 O(m + n) 的额外空间，但这仍然不是最好的解决方案。
你能想出一个仅使用常量空间的解决方案吗？

  

 

  
1
  
2
  
3
 

示例 1：

输入：matrix = [[1,1,1],[1,0,1],[1,1,1]]
输出：[[1,0,1],[0,0,0],[1,0,1]]

  

 

  
1
  
2
 

示例 2：

输入：matrix = [[0,1,2,0],[3,4,5,2],[1,3,1,5]]
输出：[[0,0,0,0],[0,4,5,0],[0,3,1,0]]

  

 

  
1
  
2
 

提示：

m == matrix.length
n == matrix[0].length
1 <= m, n <= 200
-2^31 <= matrix[i][j] <= 2^31 - 1

  

 

  
1
  
2
  
3
  
4
 

来源：力扣（LeetCode） 链接：https://leetcode-cn.com/problems/set-matrix-zeroes
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

思路：
这个思路相对简单一些，遇到0就把那一行和那一列的非0元素置为INT_MIN，等都处理完之后，就把INT_MIN置为0。

代码实现：

class Solution {
public: void setZeroes(vector<vector<int>>& matrix) { int m = matrix.size(); int n = matrix[0].size(); vector<int> 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; } } } }
};


  

 

  
1
  
2
  
3
  
4
  
5
  
6
  
7
  
8
  
9
  
10
  
11
  
12
  
13
  
14
  
15
  
16
  
17
  
18
  
19
  
20
  
21
  
22
  
23
 

字母异位词分组

给定一个字符串数组，将字母异位词组合在一起。字母异位词指字母相同，但排列不同的字符串。

示例:

输入: ["eat", "tea", "tan", "ate", "nat", "bat"]
输出:
[
  ["ate","eat","tea"],
  ["nat","tan"],
  ["bat"]
]

  

 

  
1
  
2
  
3
  
4
  
5
  
6
  
7
 

说明：

所有输入均为小写字母。
不考虑答案输出的顺序。

  

 

  
1
  
2
 

作者：力扣 (LeetCode)
链接：https://leetcode-cn.com/leetbook/read/top-interview-questions-medium/xvaszc/
来源：力扣（LeetCode） 著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。

思路：
那这个思路其实也很简单的了，将字符串排序之后作为主键，为排序字符串作为值，插入哈希表中。

然后遍历取出。

那这个思路不是很简单的呢？

class Solution {
public: vector<vector<string>> groupAnagrams(vector<string>& strs) { vector<vector<string>> res; map<string,vector<string>> vec; if(strs.empty()) return res; for(int i=0;i<strs.size();i++) { string temp=strs[i]; sort(temp.begin(),temp.end()); vec[temp].push_back(strs[i]); } map<string,vector<string>>::iterator it; for(auto it=vec.begin();it!=vec.end();it++) { res.push_back(it->second); } return res; }
};

  

 

  
1
  
2
  
3
  
4
  
5
  
6
  
7
  
8
  
9
  
10
  
11
  
12
  
13
  
14
  
15
  
16
  
17
  
18
  
19
  
20
  
21
 

无重复字符的最长子串

给定一个字符串，请你找出其中不含有重复字符的 最长子串 的长度。

示例 1:

输入: s = "abcabcbb"
输出: 3 
解释: 因为无重复字符的最长子串是 "abc"，所以其长度为 3。

  

 

  
1
  
2
  
3
 

示例 2:

输入: s = "bbbbb"
输出: 1
解释: 因为无重复字符的最长子串是 "b"，所以其长度为 1。

  

 

  
1
  
2
  
3
 

示例 3:

输入: s = "pwwkew"
输出: 3
解释: 因为无重复字符的最长子串是 "wke"，所以其长度为 3。 请注意，你的答案必须是 子串 的长度，"pwke" 是一个子序列，不是子串。

  

 

  
1
  
2
  
3
  
4
 

示例 4:

输入: s = ""
输出: 0

  

 

  
1
  
2
 

提示：

0 <= s.length <= 5 * 10^4
s 由英文字母、数字、符号和空格组成

  

 

  
1
  
2
 

作者：力扣 (LeetCode)
链接：https://leetcode-cn.com/leetbook/read/top-interview-questions-medium/xv2kgi/
来源：力扣（LeetCode） 著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。

思路：
用一个标志数组来标志当前已遍历到那些字符串，并记录一个当前最长长度，与一个遍历长度。。

当出现重复字符的时候，回溯到上一个出现该字符的地方，将遍历长度减去回溯长度，继续遍历。

看代码吧：

class Solution {
public: int lengthOfLongestSubstring(string s) { if (s.size() == 0) return 0; int max_flag = 0;   //最大字符串长度 int max_new = 0; //本次遍历字符串长度 int keep_site = 0;  //本次字符串开始位置 bool flag[255] = { false }; for (char c : s) { if (!flag[c]) { flag[c] = true; max_new++; } else { int temp = 0; for (;; ) { temp++; if (s[keep_site] == c) { keep_site++; break; } //将途中字符修正回来 if (flag[s[keep_site]]) flag[s[keep_site]] = false; keep_site++; } max_new = max_new - temp + 1; } max_flag = max(max_flag, max_new); } return max_flag;
	}
};

  

 

  
1
  
2
  
3
  
4
  
5
  
6
  
7
  
8
  
9
  
10
  
11
  
12
  
13
  
14
  
15
  
16
  
17
  
18
  
19
  
20
  
21
  
22
  
23
  
24
  
25
  
26
  
27
  
28
  
29
  
30
  
31
  
32
  
33
  
34
  
35
  
36
  
37
  
38
  
39
  
40
  
41
  
42
 

先刷到这里，后面两题：最长回文子串，和递增三元组，思路不是很清晰。。。

文章来源: lion-wu.blog.csdn.net，作者：看，未来，版权归原作者所有，如需转载，请联系作者。

原文链接：lion-wu.blog.csdn.net/article/details/117215176