leetcode热门100题1-4

第一天

两数之和

//暴力枚举
class Solution {
public:
    vector<int> twoSum(vector<int>& nums, int target) {
        int n = nums.size();
        for (int i = 0; i < n; ++i) {
            for (int j = i + 1; j < n; ++j) {
                if (nums[i] + nums[j] == target) {
                    return {i, j};
                }
            }
        }
        return {};
    }
};
# python
class Solution:
    def twoSum(self, nums: List[int], target: int) -> List[int]:
        n = len(nums)
        for i in range(n):
            for j in range(i + 1, n):
                if nums[i] + nums[j] == target:
                    return [i, j]
        
        return []

2. 字母异位词分组

class Solution:
    def groupAnagrams(self, strs: List[str]) -> List[List[str]]:
        mp={}
        for st in strs:
            key=''.join(sorted(st)) #  str 字符串型
            print(type(key))
            print(type(sorted(st)))
            if key not in mp:
                mp[key]=[]
            mp[key].append(st)
        return list(mp.values())

//  排序 哈希
class Solution {
public:
    vector<vector<string>> groupAnagrams(vector<string>& strs) {
        unordered_map<string ,vector<string> > mp;
        for(string &str: strs){
            string key=str;
            sort(key.begin(),key.end() );// 排序
             mp[key].push_back(str);
        }

        vector<vector<string> >ans;
        for(auto it=mp.begin(); it!=mp.end();++it){
            ans.push_back( it->second);// it 是 map(key,value)  first second
        }
        return ans;
    }
    
};

3. 最长连续序列

对于匹配的过程，暴力的方法是 O(n)
遍历数组去看是否存在这个数，但其实更高效的方法是用一个哈希表存储数组中的数，这样查看一个数是否存在即能优化至 O(1) 的时间复杂度。

# python 前一个数字没有 即可看下一个
class Solution:
    def longestConsecutive(self, nums: List[int]) -> int:
        longest = 0
        num_set = set(nums)
        for num in num_set:
            if num - 1 not in num_set:  # 前一个数字
                current_num = num
                current_streak = 1

                while current_num + 1 in num_set:
                    current_streak += 1
                    current_num += 1
                longest = max(longest, current_streak)
        return longest

        

//c++
class Solution {
public:
    int longestConsecutive(vector<int>& nums) 
    {
        // 去重
        unordered_set<int> num_set;
        for (const int& num : nums) {
            num_set.insert(num);
        }

        int longest=0;
        for (const int &num:num_set)
        {
            if(!num_set.count(num-1))
            {
                int currentnum=num;
                int current=1;

                while(num_set.count(currentnum+1)) {
                    currentnum+=1;
                    current+=1;
                }
                longest=max(longest,current);
            }
        
        }
        return longest;
    }
};

std::unordered_set 的默认迭代器是一个常量迭代器，因此不能绑定到 int&
num_set 的迭代器类型是 const int（默认行为）
std::unordered_set 中的元素是不可修改的，因为哈希值依赖于元素的值。

4. 移动零
   右指针一直走 左指针非零时与左指针交换

class Solution {
public:
    void moveZeroes(vector<int>& nums) {
        int n = nums.size(), left = 0, right = 0;
        while (right < n) {
            if (nums[right]) {
                swap(nums[left], nums[right]);
                left++;
            }
            right++;
        }
    }
};