文章目录
三数之和
给你一个包含 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;
}
};
先刷到这里,后面两题:最长回文子串,和递增三元组,思路不是很清晰。。。