[数据结构与算法]【深度优先+重写hash(C++)】365. 水壶问题

题目描述

有两个水壶，容量分别为 x 和 y 升。水的供应是无限的。确定是否有可能使用这两个壶准确得到 target 升。
如果可以得到 target 升水，最后请用以上水壶中的一或两个来盛放取得的 target 升水。
你可以：

1. 装满任意一个水壶；
2. 清空任意一个水壶；
3. 从一个水壶向另外一个水壶倒水，直到装满或者倒空；

示例：

输入: jug1Capacity = 3, jug2Capacity = 5, targetCapacity = 4
输出: true

解题思路

说是深度优先其实感觉有回溯的味道，简单来说，每次行动也就这么有限个操作，暴力遍历所有排列组合，遇到满足条件的立即返回。

考虑递归函数的返回值与形参。根据题目要求返回类型，递归返回类型取bool，每层递归都需要借助上层递归的状态值，故形参有remain_x, remain_y表示x, y壶当前存量。

返回条件。满足合法条件即返回，x壶或y壶装target，抑或x、y壶之和装够target。为防止状态成环进而陷入死循环，考虑visited[][]数组防止重复访问。因此，递归形参也需添加visited[][]。

单层逻辑。递归所有操作状态，只要有一个为真即可返回，故用||连接各子递归函数。考虑可操作的状态：

1. 装满x，即(x, remain_y)；
2. 装满y，即(remain_x, y)；
3. 清空x，即(0, remain_y)；
4. 清空x，即(remain_x, 0)；
5. 用x装满y，即(remain_x - min(y - remain_y, remain_x), remain_y + min(y - remain_y, remain_x));
6. 用y装满x，即(remain_x + min(x - remain_x, remain_y), remain_y - min(x - remain_x, remain_y));

深度优先，递归实现：

class Solution {
    int x, y, target;
public:
    bool canMeasureWater(int jug1Capacity, int jug2Capacity, int targetCapacity) {
        x = jug1Capacity;
        y = jug2Capacity;
        target = targetCapacity;
        vector<vector<bool>> visited(x + 1, vector<bool>(y + 1));
        return dfs(0, 0, visited);
    }

    bool dfs(int remain_x, int remain_y, vector<vector<bool>>& visited){
        if(visited[remain_x][remain_y]) return false;
        if(remain_x == target || remain_y == target || remain_x + remain_y == target) return true;
        visited[remain_x][remain_y] = true;
        return dfs(0, remain_y, visited) || dfs(remain_x, 0, visited) || dfs(x, remain_y, visited) || dfs(remain_x, y, visited) || dfs(remain_x - min(remain_x, y - remain_y), remain_y + min(remain_x, y - remain_y), visited) || dfs(remain_x + min(remain_y, x - remain_x), remain_y - min(remain_y, x - remain_x), visited);
    }
};

随着壶的容量提高，创建visited[][]的成本变得不可接受，时间复杂度O(mn)。

考虑利用栈模拟递归，hashset去重。

代码实现

使用unordered_set<pair<int, int>>，需要重写hash_function。
两种方式，

1. 函数指针；
2. 函数对象(仿函数)。

函数指针

相较于函数对象的方式，实现起来稍有点复杂。先看unordered_set源码：

  template<typename _Value,
	   typename _Hash = hash<_Value>,
	   typename _Pred = equal_to<_Value>,
	   typename _Alloc = allocator<_Value>>
    class unordered_set{
	/*  ...   */
	unordered_set(size_type __n,
		    const hasher& __hf = hasher(),
		    const key_equal& __eql = key_equal(),
		    const allocator_type& __a = allocator_type())
      : _M_h(__n, __hf, __eql, __a)
      { }
	/*  ...   */
}   

考虑到使用函数class类型作为模板参数，使用构造函数时需传入函数指针，同时也需将前面的__n赋值，作为容器的初始大小，可以赋随意值，就显得很鸡肋。

	auto hash_function = [](const pair<int, int>& p) {return hash<int>()(p.first) ^ hash<int>()(p.second);};
	unordered_set<pair<int, int>, decltype(hash_function)> uset(0, hash_function);

函数对象

声明实现仿函数，指定模板参数时只需传入仿函数实现类的类名即可，相较于函数指针突出一个简洁。

	//仿函数
    class Myhash{
    public:
        size_t operator() (const pair<int, int>& o) const{
            return hash<int>()(o.first) ^ hash<int>()(o.second);
        }
    };
	//创建hashset
	unordered_set<pair<int, int>, Myhash> uset;

坑坑坑!!!

1. 函数对象：重写hash函数，返回值类型为size_t，形参类型必须为const修饰的引用，且该函数必须为常函数，即参数列表后需要const关键字修饰；
2. 函数指针：形参类型必须为const修饰的引用。

不满足上述条件，编译都过不去！

下面给出本题的完整代码。

函数对象：

class Solution {
public:
    class Myhash{
    public:
        size_t operator() (const pair<int, int>& o) const{
            return hash<int>()(o.first) ^ hash<int>()(o.second);
        }
    };
    bool canMeasureWater(int jug1Capacity, int jug2Capacity, int targetCapacity) {
        stack<pair<int, int>> st;
        st.push({0, 0});
        unordered_set<pair<int, int>, Myhash> uset;
        while(!st.empty()){
            auto [remain_x, remain_y] = st.top();
            st.pop();
            if(uset.count({remain_x, remain_y})) continue;
            uset.insert({remain_x, remain_y});
            if(remain_x + remain_y == targetCapacity || remain_x == targetCapacity || remain_y == targetCapacity) return true;
            st.push({jug1Capacity, remain_y});

            st.push({remain_x, jug2Capacity});

            st.push({0, remain_y});

            st.push({remain_x, 0});

            st.push({remain_x + min(remain_y, jug1Capacity - remain_x), remain_y - min(remain_y, jug1Capacity - remain_x)});

            st.push({remain_x - min(remain_x, jug2Capacity - remain_y), remain_y + min(remain_x, jug2Capacity - remain_y)});

        }

        return false;
    }
};

函数指针：

class Solution {
public:
    bool canMeasureWater(int jug1Capacity, int jug2Capacity, int targetCapacity) {
        stack<pair<int, int>> st;
        st.push({0, 0});
        auto hash_function = [](const pair<int, int>& p) {return hash<int>()(p.first) ^ hash<int>()(p.second);};
	    unordered_set<pair<int, int>, decltype(hash_function)> uset(0, hash_function);
        while(!st.empty()){
            auto [remain_x, remain_y] = st.top();
            st.pop();
            if(uset.count({remain_x, remain_y})) continue;
            uset.insert({remain_x, remain_y});
            if(remain_x + remain_y == targetCapacity || remain_x == targetCapacity || remain_y == targetCapacity) return true;
            st.push({jug1Capacity, remain_y});

            st.push({remain_x, jug2Capacity});

            st.push({0, remain_y});

            st.push({remain_x, 0});

            st.push({remain_x + min(remain_y, jug1Capacity - remain_x), remain_y - min(remain_y, jug1Capacity - remain_x)});

            st.push({remain_x - min(remain_x, jug2Capacity - remain_y), remain_y + min(remain_x, jug2Capacity - remain_y)});

        }

        return false;
    }
};

运行结果：

数学

前置知识裴蜀定理

简介：任何整数a、b和它们的最大公约数d，关于未知数x和y的线性不定方程（称为裴蜀等式）：若a,b是整数,且gcd(a,b)=d，那么对于任意的整数x,y,ax+by都一定是d的倍数，特别地，一定存在整数x,y，使ax+by=d成立。

逻辑上，每次操作总储水改变量为(+/-)x, (+/-)y。也就是说本体的核心为，是否存在整数a, b使ax+by= target。由裴蜀定理可得，当target为x, y的最大公约数的倍数时，一定存在a, b使上式成立。

代码：

class Solution {
public:
    bool canMeasureWater(int jug1Capacity, int jug2Capacity, int targetCapacity) {
        if(jug1Capacity + jug2Capacity < targetCapacity) return false;
        if(jug1Capacity == 0 || jug2Capacity == 0) return targetCapacity == jug2Capacity + jug1Capacity || targetCapacity == 0;
        return targetCapacity % gcd(jug1Capacity, jug2Capacity) == 0;
    }
};

运行结果：