【124. 二叉树中的最大路径和】
两个水壶，容量分别为 x 和 y 升。水的供应是无限的。确定是否有可能使用这两个壶准确得到 target 升。
链接：https://leetcode.cn/problems/binary-tree-maximum-path-sum/
helper(TreeNode* root)表示以root为始的路径最大值。
可以是root + left、root + right、root。
最后的路径最大值还包括root + right + left的情况。
class Solution {public:int maxVal = INT_MIN;int helper(TreeNode* root) {if (!root) return 0;int l = helper(root->left);int r = helper(root->right);int tmp = max(l, r);int res = max(tmp + root->val, root->val);maxVal = max(maxVal, max(res, l + r + root->val));return res;}int maxPathSum(TreeNode* root) {helper(root);return maxVal;}};
【79. 单词搜索】
给定一个 m x n 二维字符网格 board 和一个字符串单词 word 。如果 word 存在于网格中，返回 true ；否则，返回 false 。
单词必须按照字母顺序，通过相邻的单元格内的字母构成，其中“相邻”单元格是那些水平相邻或垂直相邻的单元格。同一个单元格内的字母不允许被重复使用。
链接：https://leetcode.cn/problems/word-search/description/
struct Node{int x;int y;};class Solution {public:vector<vector<int>> dir = {{1, 0}, {-1, 0}, {0, 1}, {0, -1}};bool isBounded(int x, int y, vector<vector<char>> &board) {int n = board.size();int m = board[0].size();return x >= 0 && x < n && y >= 0 && y < m;}bool dfs(vector<vector<char>>& board, string word, int idx, int x, int y, vector<vector<bool>>& visited) {if (idx == word.length()) return true;if (!isBounded(x, y, board)) return false;if (visited[x][y] || board[x][y] != word[idx]) return false;visited[x][y] = true;for (int i = 0; i < 4; ++i) {if (dfs(board, word, idx + 1, x + dir[i][0], y + dir[i][1], visited))return true;}visited[x][y]= false;return false;}bool exist(vector<vector<char>>& board, string word) {if (board.empty()) {return word == "";}int n = board.size();int m = board[0].size();for (int i = 0; i < n; ++i) {for (int j = 0; j < m; ++j) {vector<vector<bool>> visited(n, vector<bool>(m, false));if (dfs(board, word, 0, i, j, visited)) return true;}}return false;}};
【汉诺塔问题】
在经典汉诺塔问题中，有 3 根柱子及 N 个不同大小的穿孔圆盘，盘子可以滑入任意一根柱子。一开始，所有盘子自上而下按升序依次套在第一根柱子上(即每一个盘子只能放在更大的盘子上面)。移动圆盘时受到以下限制:(1) 每次只能移动一个盘子;(2) 盘子只能从柱子顶端滑出移到下一根柱子;(3) 盘子只能叠在比它大的盘子上。
请编写程序，用栈将所有盘子从第一根柱子移到最后一根柱子。
你需要原地修改栈。
链接：https://leetcode.cn/problems/hanota-lcci/description/
class Solution {public:void helper(vector<int>& A, vector<int>& B, vector<int>& C, int n) {if (n < 1) return;helper(A, C, B, n - 1);C.push_back(A.back());A.pop_back();helper(B, A, C, n - 1);}void hanota(vector<int>& A, vector<int>& B, vector<int>& C) {helper(A, B, C, A.size());}};
【365. 水壶问题】
有两个水壶，容量分别为 x 和 y 升。水的供应是无限的。确定是否有可能使用这两个壶准确得到 target 升。
你可以：
装满任意一个水壶
清空任意一个水壶
将水从一个水壶倒入另一个水壶，直到接水壶已满，或倒水壶已空。
链接：https://leetcode.cn/problems/water-and-jug-problem/description/
在任意一个时刻，我们可以且仅可以采取以下几种操作：把 X 壶的水灌进 Y 壶，直至灌满或倒空；把 Y 壶的水灌进 X 壶，直至灌满或倒空；把 X 壶灌满；把 Y 壶灌满；把 X 壶倒空；把 Y 壶倒空。
class Solution {public:bool canMeasureWater(int x, int y, int target) {stack<pair<int, int>> stk;stk.emplace(0, 0);unordered_set<string> seen;while (!stk.empty()) {if (seen.find(to_string(stk.top().first) + "#" + to_string(stk.top().second)) != seen.end()) {stk.pop();continue;}seen.emplace(to_string(stk.top().first) + "#" + to_string(stk.top().second));int remain_x, remain_y;tie(remain_x, remain_y) = stk.top();stk.pop();if (remain_x == target || remain_y == target || remain_x + remain_y == target) {return true;}stk.emplace(x, remain_y);stk.emplace(remain_x, y);stk.emplace(0, remain_y);stk.emplace(remain_x, 0);stk.emplace(remain_x - min(remain_x, y - remain_y), remain_y + min(remain_x, y - remain_y));stk.emplace(remain_x + min(remain_y, x - remain_x), remain_y - min(remain_y, x - remain_x));}return false;}}
