cpp刷题打卡记录26——字母异位词分组 & 最长连续序列 & 盛水最多的容器 & 三数之和
自己尝试：
class Solution {
public:
bool isYiwei(string str1, string str2){
for(int i = 0; i<str1.size(); i++){
if(str2.find(str1[i]) == -1){
return false;
}
}
return true;
}
vector<vector<string>> groupAnagrams(vector<string>& strs) {
vector<vector<string>> finResult;
for(int i = 0; i<strs.size(); i++){
vector<string> result;
result.push_back(strs[i]);
for(int j = i+1; j<strs.size(); j++){
if(result[0].size() == strs[j].size() && isYiwei(result[0], strs[j]) == true){
result.push_back(strs[j]);
strs.erase(strs.begin()+j);
}
}
finResult.push_back(result);
}
return finResult;
}
};这个代码并没有通过全部的测试用例。首先在写的isYiwei函数中逻辑并不完整（我为什么会这样写，感觉只考虑到的题目所给的情况，没有想到全部），比如若str1是aab，str2是abb，这个函数一样会判断为true，这是不对的。其次在for循环索引也有问题，因为不想让其出现重复的，所以我每找到一个符合字母异位的我就把其erase掉，这样可能就会在for循环中出现问题，因为字符串的个数一直在变化。
改进：首先先改进判断异位的方法，用sort对每个字符串进行排序，这样就可以用=进行判断，排序后相等的话那么肯定就是符合字母异位的，避免了我之前自己写的那种情况。然后结合unordered_map，把其key设置成已排序好的字符串，value的类型是vector<string>，是真实的字符串组成的数组。然后依次进行插入，又因unordered_map的key是不允许有重复值的，所以有着相同排序的字符串（也就是符合题目的异位）就放进了同一个vector中。最后再进行输出就好。
需要注意的是：map[k].push_back(strs[i]); 我刚开始写的是map[k] = strs[i]，后面才反应过来value是vector数组，只能用push_back进行插入。这里用insert也是可以的。
class Solution {
public:
vector<vector<string>> groupAnagrams(vector<string>& strs) {
unordered_map<string, vector<string>> map;
for(int i = 0; i<strs.size(); i++){
string k = strs[i];
sort(k.begin(), k.end());
map[k].push_back(strs[i]);
}
vector<vector<string>> result;
for(auto pair : map){
result.push_back(pair.second);
}
return result;
}
};这个方法很巧妙的结合了排序和哈希表，时间复杂度为O(n)，代码也很简洁。
题目要求了时间复杂度为O(n)，所以不能使用sort，sort的时间复杂度为O(nlogn)
class Solution {
public:
int longestConsecutive(vector<int>& nums) {
if(nums.size()==0){
return 0;
}
unordered_set<int> numsSet(nums.begin(), nums.end());
int result = 0;
for(int n : numsSet){
if(numsSet.find(n-1) == numsSet.end()){
int curlong = 1;
while(numsSet.find(n+1) != numsSet.end()){
curlong++;
n++;
}
result = max(result, curlong);
}
}
return result;
}
};把nums都放进set容器里，因为set容易不允许有重复的元素，所以自然就去掉了重复的元素，然后再进行最长连续序列的查找。首先要找出连续序列的第一个元素，是通过判断set里面是否有遍历到的当前元素的值-1的元素，若没有则可以当做连续序列的第一个元素，然后用while来进行寻找后续的连续序列（也是判断当前元素值+1是否在set里面），记录其序列的长度。因为可能会有不止一个元素可以当连续序列的起始元素，所有要记录一下每个连续序列的长度然后max找到最大的。
题目并不难，就是在算长方形的面积，长方形的两条边选择较短的那条。
暴力解法：超出时间限制
class Solution {
public:
int maxArea(vector<int>& height) {
int maxArea = 0;
int curArea = 0;
for(int i = 0; i<height.size(); i++){
for(int j = i+1; j<height.size(); j++){
curArea = (j-i) * min(height[i], height[j]);
maxArea = max(curArea, maxArea);
}
}
return maxArea;
}
};用双指针：
class Solution {
public:
int maxArea(vector<int>& height) {
int maxArea = 0;
int curArea = 0;
int left = 0;
int right = height.size()-1;
while(left < right){
curArea = (right - left)* min(height[left], height[right]);
maxArea = max(curArea, maxArea);
if(height[left] < height[right]){
left++;
}
else{
right--;
}
}
return maxArea;
}
};每次移动要移动较小的那一边，因为刚开始两个指针相距是最远的，移动指针相当于减小宽度，那么只有增加高度来寻找大的面积。例如：height[left] < height[right]，要移动的是left，因为只有移动left才可能遇见高的柱子，才进而可能让长方形高度变成height[right]（可能遇见比height[right]还高的主语），才能从而增加高；假设移动的是right，即使遇见更高的柱子，长方形的高也选取的是height[left]（因为要以较低的那个柱子为高度）。
注意：要输出的是不同的三元组，示例1中找到了三个符合要求的三元组，但要去掉重复的，所以最后答案只有两个。
错误代码:
class Solution {
public:
vector<vector<int>> threeSum(vector<int>& nums) {
vector<vector<int>> result;
sort(nums.begin(), nums.end());
for(int i = 0; i<nums.size(); i++){
if(nums[i]>0){
return result;
}
int left = i+1;
int right = nums.size()-1;
while(left<right){
if(nums[i]+nums[left]+nums[right] > 0){
right--;
}
else if(nums[i]+nums[left]+nums[right] < 0){
left++;
}
else{
result.push_back(vector<int>{nums[i], nums[left], nums[right]});
while(left<right && nums[left] == nums[left+1]){
left++;
}
while(left<right && nums[right] == nums[right-1]){
right--;
}
left++;
right--;
}
}
}
return result;
}
};
此代码有问题，没有做到题目要求的不重复。错误出现在哪里，在每一次固定i（也就是固定第一个数）时，开始找left和right（也就是找第二个和第三个数）是做到去掉重复的步骤了的，while(left<right && nums[left] == nums[left+1])和while(left<right && nums[right] == nums[right+1])。那么就是第一个数的问题，仔细想一下，确实，我们对于第一个数仅仅是遍历，并没有加以限制，所以如下加入
if(i>0 && nums[i]==nums[i-1]){
continue;
}
就正确了。就是让第一个数也避免是重复的。（continue 用于跳过当前循环迭代中剩余的代码，立即进入下一次循环迭代）
改进：
class Solution {
public:
vector<vector<int>> threeSum(vector<int>& nums) {
vector<vector<int>> result;
sort(nums.begin(), nums.end());
for(int i = 0; i<nums.size(); i++){
if(nums[i]>0){
return result;
}
if(i>0 && nums[i]==nums[i-1]){
continue;
}
int left = i+1;
int right = nums.size()-1;
while(left<right){
if(nums[i]+nums[left]+nums[right] > 0){
right--;
}
else if(nums[i]+nums[left]+nums[right] < 0){
left++;
}
else{
result.push_back(vector<int>{nums[i], nums[left], nums[right]});
while(left<right && nums[left] == nums[left+1]){
left++;
}
while(left<right && nums[right] == nums[right-1]){
right--;
}
left++;
right--;
}
}
}
return result;
}
};哈哈这是一道之前做过且分析过的题目，有写不出来了，哈哈。
本集心得：
学了这么久，怎么还是想不到用哈希表或者双指针啊，只会暴力解法，唉，我真服了。
更多推荐
6
0- 0
已为社区贡献1条内容
所有评论(0)