[算法积累] [leetcode] [广搜/数学] [4] 365.水壶问题

标签: 算法  数据结构  

前言

花了一个半小时,还是没做出来,果然太菜了。说实话,自己还是有点不明白,但是尽力把这个讲清楚把。希望对你有点帮助。

记忆化搜索

将所有的状态添加到队列中,使用广度遍历。这里可以学习的地方就是使用hash值的方式来存储状态,这个我个人感觉是深搜,广搜的福星。几乎可以匹敌dp了。

using PII = pair<int,int>;
class Solution {  
public:

    PII hash_func(int type,const pair<int, int> &front, int x, int y){
        switch(type){
            case 0: return make_pair(x,front.second);
            case 1: return make_pair(front.first,y);
            case 2: return make_pair(0,front.second);
            case 3: return make_pair(front.first,0);
            
            case 4: {
                int minOne = min(front.first,y-front.second);
                return make_pair(front.first-minOne,front.second+minOne);
            }
            case 5: {
                int minOne = min(front.second,x-front.first);
                return make_pair(front.first+minOne,front.second-minOne);
            }
                
        }
        return make_pair(0,0);
        
    }

    struct HashPair {
        size_t operator()(const pair<int, int> &key) const noexcept
	    {
		    return size_t (key.first)*100000007 + key.second;
	    }
    };

    bool canMeasureWater(int x, int y, int z) {
        queue<PII> q;
        unordered_set<pair<int,int>, HashPair> mark;
        q.push(make_pair(0,0));
        while(!q.empty()){
            PII front = q.front();
            q.pop();
            if(front.first + front.second == z) return true;
            for(int i = 0;i<6;i++){
                PII tmp = hash_func(i,front,x,y);
                if(mark.find(tmp) != mark.end()) {
                    continue;
                }
                 mark.insert(tmp);
                q.push(tmp);
            }
           
        }

        return false;
    }
};

数学方法

作为一个计算机人,这些数学定理只要会用就行(欺骗自己🐶).
该题使用了裴蜀定理,即对于整数x,y, 必存在ax+by为d的倍数,其中d为a,b的最大公约数.
在本题当中,对于两壶水的总量,只有可能出现+x,-x,+y,-y.0,这5种情况。将非空的壶加入水,倒掉的状态与直接全部倒掉的状态相同,所以不做考虑。只考虑上面5种状态.注意不是不会出现这种状态,而是有更简单直接的状态可以考虑,所以不去考虑。

在这里插入图片描述
因此,现在考虑的就是如果通过多次操作ax+by = z,那么由上述结论,z必定为x,y最大公约数的倍数。因此,只需检查z%gcd(x,y) == 0,即可.代码如下:

class Solution {
public:
    bool canMeasureWater(int x, int y, int z) {
        if(x + y < z) return false;
        if(x == 0 || y == 0) return z == 0||x+y == z;
        return z % gcd(x,y) == 0;
    }
};
版权声明:本文为weixin_43146002原创文章,遵循 CC 4.0 BY-SA 版权协议,转载请附上原文出处链接和本声明。
本文链接:https://blog.csdn.net/weixin_43146002/article/details/105006506

智能推荐

Reflect反射的基础知识

写个父类: 写个子类: 利用反射获得该子类中的属性,方法,构造,父类及接口: 运行结果:...

spring cloud netflix (07) 服务的消费者(feign)

前言 完整知识点:spring cloud netflix 系列技术栈 Feign (同步通信 HTTP通信) feign是基于接口完成服务与服务之间的通信的 搭建Feign服务 项目结构 项目搭建 pom.xml application类 application.yml 使用feign完成服务与服务之间的通信 feign是基于接口完成服务与服务之间的通信的...

AtCoder Beginner Contest 174 E.Logs

AtCoder Beginner Contest 174 E.Logs 题目链接 到最后才发现是二分,菜菜的我/(ㄒoㄒ)/~~ 我们直接二分 [1,max{a[i]}][1,max\lbrace a[i]\rbrace][1,max{a[i]}] 即可,对每一个 midmidmid,每个数 a[i]a[i]a[i] 只需要切 a[i]−1mid\frac{a[i]-1}{mid}mi...

小程序基础与实战案例

小程序开发工具与基础 小程序开发准备: 申请小程序账号( appid ) 下载并安装微信开发者工具 具体步骤如下: 先进入 微信公众平台 ,下拉页面,把鼠标悬浮在小程序图标上 然后点击 小程序开发文档 照着里面给的步骤,就可以申请到小程序账号了。 然后就可以下载 开发者工具 了 下载完打开后的界面就是这个样子 下面让我们来新建一个小程序开发项目: 在AppID输入自己刚刚注册的AppID就可以,或...

VMware centOS7 下通过minikube部署Kubernetes

1、环境准备: VMware CentOS-7-x86_64 CPU:2*2core 内存:8G 宿主机和虚拟机需网络互通,虚拟机外网访问正常 Centos发行版版本查看:cat /etc/centos-release root用户操作 2、禁用swap分区 Kubernetes 1.8开始要求关闭系统的Swap,可暂时关闭或永久禁用, 使用 $ free -m 确认swap是否为开启状态 $ s...

猜你喜欢

逻辑回归与scikit-learn

欢迎关注本人的微信公众号AI_Engine LogisticRegression 算法原理 一句话概括:逻辑回归假设数据服从伯努利分布,通过极大化似然函数(损失函数)的方法,运用梯度下降或其他优化算法来求解参数,来达到将数据二分类的目的。 定义:逻辑回归(Logistic Regression)是一种用于解决二分类(0 or 1)问题的机器学习方法,用于估计某种事物的可能性(不是概率)。比如某用户...

指针OR数组?用他们来表达字符串又有何不同?

cocowy的编程之旅 在学习C语言的过程中我们经常可以看到或者听到这样一句话:数组其实等价于指针,例如: 在这里可以轻松的看出输出后他们的值相等,其实在计算机内存里面,p为本地变量,有着他自己的作用域。而指针变量q保存着这个数组的首地址,通过*号指向这个地址保存的变量值。 然而我们再看一个例子: 这个时候计算机报错,这是为什么呢? 其实原因很简单,指针说指向的这个字符串的地址是位于计算机代码段地...

广度搜索

广度搜索的基本使用方法 广度搜索不同于深度搜索,是一种一步一步进行的过程,每一个点只记录一遍。需要用到队列记录每一步可以走到的位置,找到目标位置输出步数即可。 用到的知识:结构体、队列 如图 首先我们需要定义一个结构体来存储每个遍历到的点和步数 广搜不会用到递归,所以可以直接在主函数里写,这里需要定义一个结构体队列 初始化队列并将起始点入列 遍历 完整代码...

NIO Socket 编程实现tcp通信入门(二)

1、NIO简介 NIO面向通道和缓冲区进行工作,数据总是从通道读取到缓冲区中,或者从缓冲区写入到通道中。可以双向传输数据,是同步非阻塞式IO。NIO还引入了选择器机制,从而实现了一个选择器监听多个底层通道,减少了线程并发数。用NIO实现socket的Tcp通信需要掌握下面三个知识点: Buffer 缓冲区 Channel 通道 Selector 选择器   2、java.nio.Buff...

[字节码系列]ObjectWeb ASM构建Method Monitor

      在前面的篇章中,我们看到Java Instrutment的强大能力,本篇,我们将介绍如何使用ObjectWeb ASM的字节码增强能力构建Method Monitor       1.什么是ObjectWeb ASM      ObjectWeb ...