Datawhale 12月组队学习 leetcode基础 day1 枚举

2023-12-13 07:49:18

这是一个新的专栏,主要是一些算法的基础,对想要刷leedcode的同学会有一定的帮助,如果在算法学习中遇到了问题,也可以直接评论或者私信博主,一定倾囊相助


进入正题,今天咱们要说的枚举算法,这是个很简单的算法哈,先说一下原理然后就看几道题练一下,算是很好学的算法了

枚举算法简介

这里简单的和大家分享一下什么是枚举,简单来说,就是一一列举可能出现的情况,和我们要满足的目标状况进行比对,得到满足条件的解答,举个例子:目标状况是找出值>5的数,数的范围是[0,10]这时候我们是不是只需要写一个很简单的循环,遍历0到10这11个数就可以了

for(int i = 0 ; i <= 10 ; ++i)
{
	if(i>5)
	{
	printf("%d",i);
	}
}

因为这是一种很容易想到的思路,而且不容易出错,所以我们在做题想不出来很优秀的解法的时候,就可以考虑使用枚举的方法来做。

枚举算法解题思路

根据上面的例子,我们可以总结一下枚举算法的解题思路:
首先,确定枚举的范围,枚举的对象,判断条件。
其次遍历范围中的样例进行判断,看是否是问题的解。
最后,可以考虑优化枚举的范围,提高效率(主要就是时间复杂度)

例题

那么,根据枚举算法的解题思路,我们来做几道题,熟悉一下:

例题1

两数之和
在这里插入图片描述

这道题是一个非常简单的小题,只是让我们找出数组中两数之和等于目标值的数字组合的下标,并且只会有一个有效的答案,那么看第一个样例是[2,7,11,15] 目标值是9, 那么数字组合就是2,7 下标就是0,1。
那么用代码我们如何实现呢?
我们根据枚举的思路来分析,首先确定枚举的范围 那就是数组的大小了,枚举的目标就是数组里面的数字,目标条件就是数字组合相加等于目标值,
那么我们就可以写出以下遍历所有目标情况的代码:

    vector<int> twoSum(vector<int>& nums, int target) {
        int i = 0, j = 0;
        vector<int> res;
        //枚举答案 i外层循环j内层循环
        for(i = 0;i < nums.size();++i)
        {
            for(j = i+1;j<nums.size();++j)
            {
                if(nums[i]+nums[j] == target)
                {
                res.push_back(i);
                res.push_back(j);
                return res;
                }
            }
          
        }
        return res;
    }

nums是题里的已知条件 也是我们要遍历的数组,target就是目标值
在这里我们写了两层的for循环来解决这问题 第一个for循环是让i 从0开始一直遍历到数组末尾 j是从i的下一位开始(题目中不允许重复的数字组合)用枚举条件进行判断 如果符合条件 那么就把数组组合返回,达成题目要求,如果编程基础比较薄弱,或者感觉博主说的很模糊 那么可以看下面张图
在这里插入图片描述
下面再看一道题:

例题2

计算质数
在这里插入图片描述
这里先说一下什么是质数 质数就是除了1和本身以外,不能被其他的数整除的数字 就叫做质数 。
这题我们还是按照枚举的方法做,首先确定枚举范围,那就是从2开始一直到n的数(1不是质数),遍历的对象就是2到n的数字,判断条件就是这个数是不是质数 是质数我们就统计他的数目 不是就不用。
那么根据枚举的思路我们可以先写一段伪代码:

for(int i = 2;i<n;++i)
{
	if(isprime(n))
		cnt++;
}

这就是一个标准的枚举解决方法的思路,这题的主要难点在哪里呢,就是计算这个数是不是质数 这个问题我们还是可以用枚举解决:
枚举的范围可以先定成 小于n/2的数 这是显然的 因为数字不可能整除比他的一半还大的数吧 ,枚举的对象就是 0-n/2的数字,目标就是看 n能不能整除我们枚举的对象 可以那就说明不是质数。所以代码如下

bool isPrime(int n)
{
    for(int i = 2;i<=n/2;++i)
    {
        if( n%i == 0)
        return false;
    }
    return true;
}

代码写到这,这题可以结束了 但是还有一个小的问题 我们提交答案看一下:
在这里插入图片描述

可以看到对于一般的例子,我们是可以通过的,这说明代码的逻辑没问题,但是:
在这里插入图片描述
会超出时间限制 这就是问题所在,所以我们要进行枚举的第三步 缩减枚举的范围:
在这里提供两种思路 一种是把isprime函数里面的i<n/2变成i<根号2 也就是i × i<2 为什么可以这么写呢,简单证明如下:
在这里插入图片描述
再接下来一种思路就是埃氏筛或者线性筛 这两种方法和枚举其实关系不大,感兴趣的同学可以去查一下。

通过缩小枚举的范围 我们就可以达到缩小时间复杂度的目的。

练习

统计格内点的数目
这是一道大家回去自己练习的小题 ,在这里我给出其中一种解法 大家可以自由发挥。

class Solution {
public:
        bool incircle(vector<vector<int>>& circles, int x, int y)
    {
        for (int i = 0; i < circles.size(); ++i)
        {
            int a = circles[i][0];
            int b = circles[i][1];
            int r = circles[i][2];
            if ((x - a) * (x - a) + (y - b) * (y - b)
                <= r * r)
                return true;
        }
        return false;
    }
    int countLatticePoints(vector<vector<int>>& circles) {
        //确定区间 区间为上下左右 
        int cnt = 0;
        int up, down, left, right;
        up = -1;
        down = 101;
        left = 101;
        right = -1;
        for (int i = 0; i < circles.size(); ++i)
        {
            int   r = circles[i][2];
            int   x = circles[i][0];
            int   y = circles[i][1];
            if (y-r < down)
                down = y - r;
            if (y + r > up)
                up = y + r;
            if (x - r < left)
                left = x - r;
            if (r + x > right)
                right = r + x;
        }
        //确定区间以后枚举遍历
        for (int i = left; i <= right; ++i)
        {
            for (int j = down; j <= up; ++j)
            {
                if (incircle(circles, i, j))
                    cnt++;
            }
        }
        return cnt;
    }
};

有啥问题都可以提出来 ,博主有啥问题也恳请斧正,谢谢。

文章来源:https://blog.csdn.net/Pythoniiiiii/article/details/134953765
本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。