LeetCode Hot100 (2、3、4、5、6、8、9、12)

class Solution {
public:
    vector<vector<string>> groupAnagrams(vector<string>& strs) {

      //  一开始的思路是，对于其中的一个单词，遍历所有排序组合，然后判断这些组合是否在哈希表里
      //，在的话就加入数组，然后从哈希表里删掉，问题是如何遍历所有排序组合，dfs？
      //这里学习一种方法，将哈希表中的不同字符串排序，如果排序后是相等的就代表字母一样
      //如果有这种思路，就很简单了，依次遍历数组，看他排序后的字符串是否在哈希表里，在就修改哈希表的值，不在就加入这个key

      unordered_map<string,vector<string>> m;

      for(int i=0;i<strs.size();i++)
      {
      string str=strs[i];
      sort(str.begin(),str.end());
      m[str].emplace_back(strs[i]);
      
      }

vector<vector<string>> s;
 for(auto t:m)
 {
    s.emplace_back(t.second);
 }

return s;

   


    }
};

class Solution {
public:
    int longestConsecutive(vector<int>& nums) {
        //题目要求的是n的复杂度，也就是说在遍历一遍或者几遍数组后就应该得出答案
        //一开始的思路是像前几道哈希表一样，依次遍历每个数，然后看这个数的前一个数和后一个
        //在不在哈希表里，但是涉及到一个问题，比如 1 2 3 4 0，遍历到2的时候可以去更新1的值，遍历到4的时候还能去更新1吗，这样复杂度就说n方了
        //n复杂度不代表遍历一次数组就得出答案，遍历几次也行
        //直接先将所有数放入哈希表，且全部为1（此时没有重复）
        //然后遍历哈希表，只判断这个数的前一个数在不在，然后更新这个数的值，每个数更新后的值代表以这个数结尾的连续序列的长度
        //此时还有一个问题，就是哈希表里是乱序，所以，你便利到当前这个值，你的值取决于你上一个数的值，但是你要去判断，你下一个数的值可能在之前你还没变的时候就变了
        //此时要一直往前判断，不过没关系，这是有限次的，复杂度还是n
unordered_map<int,int> m;

for(int i=0;i<nums.size();++i)m[nums[i]]=1;

for(auto t:m)
{
int a=t.first;
  if(m.find(a-1)!=m.end())m[a]=m[a-1]+1;
while(m.find(a+1)!=m.end())
{
    if(m[a+1]<=m[a]&&m[a+1]!=1){
        m[a+1]=m[a]+1;
            ++a;
    }else
    {
        break;//如果存在且没有被错误更新就直接break，如果没有这一步就全错了，所以有if一定要考虑else
    }
}


}



int u=0;
for(auto t:m)
{
u=max(u,t.second);

}


return u;



    }
};

class Solution {
public:
    int longestConsecutive(vector<int>& nums) {
//每个数都判断一次这个数是不是连续序列的开头那个数。
// 怎么判断呢，就是用哈希表查找这个数前面一个数是否存在，即num-1在序列中是否存在。存在那这个数肯定不是开头，直接跳过。
// 因此只需要对每个开头的数进行循环，直到这个序列不再连续，因此复杂度是O(n)。
// 以题解中的序列举例:
// [100，4，200，1，3，4，2]
// 去重后的哈希序列为：
// [100，4，200，1，3，2]
// 按照上面逻辑进行判断：
// 元素100是开头,因为没有99，且以100开头的序列长度为1
// 元素4不是开头，因为有3存在，过，
// 元素200是开头，因为没有199，且以200开头的序列长度为1
// 元素1是开头，因为没有0，且以1开头的序列长度为4，因为依次累加，2，3，4都存在。
// 元素3不是开头，因为2存在，过，
// 元素2不是开头，因为1存在，过。

//只需要一个set

unordered_set<int> s;

 for(int i=0;i<nums.size();++i) s.insert(nums[i]);
 int v=0;
for(auto t:s)
{
   if(!s.count(t-1)) {
    int u=1;
    int a=t;
    while(s.count(a+1))
        {
            ++u;
            a++;
        }
        v=max(v,u);

}

}

return v;




    }
};

class Solution {
public:
    void moveZeroes(vector<int>& nums) {
        //我的想法是双指针，一个找0，一个找非0（最左边的）
//从第一个0的位置开始，j找到右边第一个数字，然后和这个0交换，i往右边遍历继续找第一个0
//此时第一个0的位置一定在j上或者j前面，然后j往后走继续找数字，这样就能保证两个指针都是往后走
//数字的顺序不会变
int n=nums.size();
int i=0;
while(i<n&&nums[i]!=0)++i;
if(i>=n)return;

int j=i;


while(j<n)
{
  while(j<n&&nums[j]==0)
  {
    ++j;
    } 
  if(j>=n)return ;

  swap(nums[i],nums[j]);
  while(i<n&&nums[i]!=0)++i;


}




    }
};

class Solution {
public:
    int maxArea(vector<int>& height) {
        
//对于左边界，右边的比他矮的垂线都可以排除，无法威胁到他
//对于右边界，左边比他矮的也可以排除
//如果暴力，复杂度是n方
//题解思路
//答案来自于两个边界里，长度最短的一个垂线和这两个边界的距离
//所以如何确定左右边界呢，一开始我们让左右边界的距离最大
//这个时候决定因素就是短的那一边，此时移动长的那一边毫无意义，只有移动短的才可能得到更大的值
//相当于是一开始我选择最大边界，在这个基础上，我朝着可能变得更大的方向上探索

int i=0,j=height.size()-1;
int m=(j-i)*min(height[i],height[j]);

while(i<j)
{
if(height[i]<height[j])i++;
else j--;

m=max(m,(j-i)*min(height[i],height[j]));


}


return m;


    }
};

class Solution {
public:
    vector<vector<int>> threeSum(vector<int>& nums) {
        
        //为了不重复，我们可以先将数组排序
        //我们需要在排序后的数组中选出三个数字，满足相加为0
        //此时还有重复的可能，比如数组为0 0 0 0
        //所以在for循环时，无论是外层循环还是内层循环，下一个数如果和上一个相等就跳过
        //不需要三层for循环，当第一个数确定时，剩下两个数因为数组已经排好序，相当于
        //在有序数组里求两数之和，由于第一个数从前往后遍历，所以不会重复，列举出的数列都是递增数列
        sort(nums.begin(),nums.end());
        vector<vector<int>> v;
        for(int i=0;i<nums.size()-2;i++)
        {
           if(i>=1&&nums[i]==nums[i-1]) continue;
           
           int k=nums.size()-1;
           for(int j=i+1;j<nums.size()-1;j++)
           {    
                if(j>=i+2&&nums[j]==nums[j-1])continue ;
                while(k>j&&nums[j]+nums[k]>(0-nums[i]))k--;
                 if(k>j&&nums[j]+nums[k]==(0-nums[i]))
                 {
                    v.push_back({nums[i],nums[j],nums[k]});
                 }
                 
           }


        }


return v;




    }
};

class Solution {
public:
    vector<vector<int>> threeSum(vector<int>& nums) {
        
        //为了不重复，我们可以先将数组排序
        //我们需要在排序后的数组中选出三个数字，满足相加为0
        //此时还有重复的可能，比如数组为0 0 0 0
        //所以在for循环时，无论是外层循环还是内层循环，下一个数如果和上一个相等就跳过
        //不需要三层for循环，当第一个数确定时，剩下两个数因为数组已经排好序，相当于
        //在有序数组里求两数之和，由于第一个数从前往后遍历，所以不会重复，列举出的数列都是递增数列
        sort(nums.begin(),nums.end());
        vector<vector<int>> v;
        for(int i=0;i<nums.size()-2;++i)
        {
           if(i>0&&nums[i]==nums[i-1]) continue;
           
           int k=nums.size()-1;
           for(int j=i+1;j<nums.size()-1;++j)
           {    
                if(j>i+1&&nums[j]==nums[j-1])continue ;
                while(k>j&&nums[j]+nums[k]>(0-nums[i]))--k;
                if(j==k)break;
                 if(k>j&&nums[j]+nums[k]==(0-nums[i]))
                 {
                    v.push_back({nums[i],nums[j],nums[k]});
                 }
                 
           }


        }


return v;



    }
};

class Solution {
public:
    int lengthOfLongestSubstring(string s) {
        
    unordered_map<char,int> m;

int ans=0;
    for(int right=0,left=0;right<s.size();right++)
    {
       m[s[right]]++;
    
           while(m[s[right]]>1)//加入当前字母后发现哈希表中字母数大于1，说明当前字母就是重复字母
           {
              m[s[left]]--;
              left++;
           }

   ans=max(ans,right-left+1);




    }



return ans;






    }
};