leetcode

Solution to some Leetcode problems written in C++

git clone git://git.dimitrijedobrota.com/leetcode.git

0365.cpp (1188B)

0 // programming solution 1 class Solution { 2 static int seen[1001][1001]; 3 4 static bool rec(int x, int y, int target, int a = 0, int b = 0) { 5 if (a + b == target) return true; 6 if (seen[a][b]) return false; 7 seen[a][b] = true; 8 9 const int leftx = x - a; 10 const int lefty = y - b; 11 12 if (rec(x, y, target, x, b)) return true; 13 if (rec(x, y, target, a, y)) return true; 14 if (rec(x, y, target, 0, b)) return true; 15 if (rec(x, y, target, a, 0)) return true; 16 if (rec(x, y, target, a - min(a, lefty), b + min(a, lefty))) return true; 17 if (rec(x, y, target, a + min(b, leftx), b - min(b, leftx))) return true; 18 19 return false; 20 } 21 22 public: 23 bool canMeasureWater(int x, int y, int target) const { 24 memset(seen, 0x00, sizeof(seen)); 25 return rec(x, y, target); 26 } 27 }; 28 29 int Solution::seen[1001][1001]; 30 31 // Math solution: Bézout's identity 32 class Solution { 33 public: 34 bool canMeasureWater(int x, int y, int target) const { 35 if (x + y < target) return false; 36 if (x == target || y == target || x + y == target) return true; 37 return target % gcd(x, y) == 0; 38 } 39 };