力扣刷题(自用)

哈希

128.最长连续序列

128. 最长连续序列 - 力扣(LeetCode)

这个题要求O(n)的时间复杂度,我一开始想的是双指针算法(因为我并不是很熟悉set容器的使用),但是双指针算法有小部分数据过不了。

题解给的哈希算法太妙了,简单来说就是通过unordered_set来去重,然后对于序列中的每一个元素num,使用count操作来查找序列中是否存在num-1,不存在的话,说明这个元素num是连续序列的首元素,最后比较得到最大值就行。

 set、multiset、map、multimap
特点:底层是红黑树,键值有序,set 、 map 键不可重复,multiset 和 multimap 可重复;
复杂度:插入、删除、查找都为O(logN);

unordered_set,unordered_map,unordered_multiset,unordered_multimap
特点:底层实现是哈希表,键值无序,unordered_set 和 unordered_map 键不可重复,而另外两个可以重复;
复杂度:插入、删除、查找平均为O(1),最坏为O(N),空间换时间;

C++代码 

class Solution {
public:
    int longestConsecutive(vector<int>& nums) {
        unordered_set<int>num_set;
        for(auto &num:nums)num_set.insert(num);

        int ans=0;
        for(auto &num:num_set){
            if(num_set.count(num-1)==0){
                int cur=num;
                int curans=1;

                while(num_set.count(cur+1)){
                    cur+=1;
                    curans+=1;
                }
                ans=max(ans,curans);
            }
        }
        return ans;
    }
};

python代码

class Solution:
    def longestConsecutive(self, nums: List[int]) -> int:
        ans=0
        num_set=set(nums)

        for num in num_set:
            if num-1 not in num_set:
                cur_num=num
                cur_ans=1

                while cur_num+1 in num_set:
                    cur_num+=1
                    cur_ans+=1
                ans=max(ans,cur_ans)
        return ans

 双指针

283.移动零

283. 移动零 - 力扣(LeetCode)

方法一:用双指针算法把非0的元素移动到前面去,最后补0

class Solution {
public:
    void moveZeroes(vector<int>& nums) {
        int j=0;
        for(int i=0;i<nums.size();i++){
            if(nums[i]){
                nums[j++]=nums[i];
            }
        }
        for(int i=j;i<nums.size();i++){
            nums[i]=0;
        }
    }
};

 方法二:我也不知道题解怎么想出来的

class Solution {
public:
    void moveZeroes(vector<int>& nums) {
        int j=0;
        for(int i=0;i<nums.size();i++){
            if(nums[i]){
                int temp=nums[i];
                nums[i]=nums[j];
                nums[j]=temp;
                j++;
            }
        }
    }
};

python代码

class Solution:
    def moveZeroes(self, nums: List[int]) -> None:
        """
        Do not return anything, modify nums in-place instead.
        """
        j=0
        for i in range(len(nums)):
            if nums[i]:
                nums[j],nums[i]=nums[i],nums[j]
                j+=1

11.盛最多水的容器 

11. 盛最多水的容器 - 力扣(LeetCode)

 这道题的最优解法是左右双指针法。双指针法的难点在于难于想到,难以证明。

 AcWing 1575. 从暴力优化到双指针,明明白白(图解) - AcWing

 移动短的一边是因为:如果移动长的一边,宽已经由短的一边固定了,长度在不断缩减,所以以后的面积只会比现在小;如果移动短的一边,即使长度变短了,但是宽度和长度的乘积可能会变大;最后就是将最大值返回

class Solution {
public:
    int maxArea(vector<int>& height) {
        int ans=-1;
        int i=0,j=height.size()-1;
        while(i!=j){
            ans=max(ans,(j-i)*min(height[i],height[j]));
            if(height[i]<height[j])i++;
            else j--;
        }
        return ans;
    }
};

python

class Solution:
    def maxArea(self, height: List[int]) -> int:
        ans=-1
        i=0
        j=len(height)-1
        while(i!=j):
            ans=max(ans,(j-i)*min(height[i],height[j]))
            if(height[i]<height[j]):
                i+=1
            else:
                j-=1
        return ans

 15.三数之和

15. 三数之和 - 力扣(LeetCode)

  1. 排序:使用std::sort对数组进行排序。
  2. 外层循环:从第一个元素开始,每次选择一个元素作为三元组的第一个数。
  3. 内层循环:使用两个指针leftright从中间开始向两边扩展,寻找和为0的三元组。
  4. 跳过重复元素:在添加三元组到结果数组之前,检查当前元素是否与前一个元素相同,如果是,则跳过当前元素,避免重复。

定一找二,变双指针

class Solution {
public:
    vector<vector<int>> threeSum(vector<int>& nums) {
        std::sort(nums.begin(), nums.end());
        vector<vector<int>> ans;
        int n = nums.size();

        for (int i = 0; i < n - 2; i++) {
            if (i && nums[i] == nums[i - 1]) continue; // 跳过重复的元素

            int left = i + 1, right = n - 1;
            while (left < right) {
                long long sum = nums[i] + nums[left] + nums[right];
                if (sum == 0) {
                    ans.push_back({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--;
                } else if (sum < 0) {
                    left++;
                } else {
                    right--;
                }
            }
        }

        return ans;
    }
};

上一篇:C Prinmer Plus笔记第1-6章


下一篇:React学习笔记02-----React基本使用