C/C++教程
算法刷题（七）：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]]
示例 2：
输入：nums = [] 输出：[]
示例 3：
输入：nums = [0] 输出：[]
提示：
0 <= nums.length <= 3000 -10^5 <= nums[i] <= 10^5
作者：力扣 (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;
}
};
矩阵置零
给定一个 m x n 的矩阵，如果一个元素为 0 ，则将其所在行和列的所有元素都设为 0 。请使用 原地 算法。
进阶：
一个直观的解决方案是使用 O(mn) 的额外空间，但这并不是一个好的解决方案。 一个简单的改进方案是使用 O(m + n) 的额外空间，但这仍然不是最好的解决方案。 你能想出一个仅使用常量空间的解决方案吗？
示例 1：
输入：matrix = [[1,1,1],[1,0,1],[1,1,1]] 输出：[[1,0,1],[0,0,0],[1,0,1]]
示例 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]]
提示：
m == matrix.length n == matrix[0].length 1 <= m, n <= 200 -2^31 <= matrix[i][j] <= 2^31 - 1
来源：力扣（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;
}
}
}
}
};
字母异位词分组
给定一个字符串数组，将字母异位词组合在一起。字母异位词指字母相同，但排列不同的字符串。
示例:
输入: ["eat", "tea", "tan", "ate", "nat", "bat"] 输出: [ ["ate","eat","tea"], ["nat","tan"], ["bat"] ]
说明：
所有输入均为小写字母。 不考虑答案输出的顺序。
作者：力扣 (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:
输入: s = "abcabcbb" 输出: 3 解释: 因为无重复字符的最长子串是 "abc"，所以其长度为 3。
示例 2:
输入: s = "bbbbb" 输出: 1 解释: 因为无重复字符的最长子串是 "b"，所以其长度为 1。
示例 3:
输入: s = "pwwkew"
输出: 3
解释: 因为无重复字符的最长子串是 "wke"，所以其长度为 3。
请注意，你的答案必须是 子串 的长度，"pwke" 是一个子序列，不是子串。
示例 4:
输入: s = "" 输出: 0
提示：
0 <= s.length <= 5 * 10^4 s 由英文字母、数字、符号和空格组成
作者：力扣 (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;
}
};
先刷到这里，后面两题：最长回文子串，和递增三元组，思路不是很清晰。。。
-
在 Objective-C 中strong 和 retain有什么区别-icode9专业技术文章分享11-02
-
NSString 中的 hasPrefix 有什么作用-icode9专业技术文章分享11-02
-
在 C 和 Objective-C 中inline的用法是什么-icode9专业技术文章分享11-02
-
文件掩码什么意思？-icode9专业技术文章分享11-02
-
在 Git 提交之前运行 composer cs-fix 命令怎么实现-icode9专业技术文章分享11-02
-
为 Composer 的 cs-fix 命令指定一个目录怎么实现-icode9专业技术文章分享11-02
-
微信公众号开发中怎么获取用户的 unionid-icode9专业技术文章分享11-02
-
lip-sync公司指南：一文读懂主要玩家和技术11-01
-
Anthropic的新RAG方法——提升大型语言模型在特定领域的表现11-01
-
UniApp 中组件的生命周期是多少-icode9专业技术文章分享11-01
-
如何使用Svg Sprite Icon简化网页图标管理11-01
-
Excel数据导出课程：新手从入门到精通的实用教程10-31
-
Excel数据导入课程：新手入门指南10-31
-
RBAC的权限课程：新手入门教程10-31
-
Svg Sprite Icon课程：新手入门必备指南10-31
