欢迎您访问程序员文章站本站旨在为大家提供分享程序员计算机编程知识!
您现在的位置是: 首页

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

程序员文章站 2024-03-15 08:38:59
...

前言

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

记忆化搜索

将所有的状态添加到队列中,使用广度遍历。这里可以学习的地方就是使用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种状态.注意不是不会出现这种状态,而是有更简单直接的状态可以考虑,所以不去考虑。

[算法积累] [leetcode] [广搜/数学] [4] 365.水壶问题
因此,现在考虑的就是如果通过多次操作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;
    }
};
相关标签: 算法 数据结构