重庆企业网站建站,公司建站系统,什么叫网站优化,个人证书查询网入口免费1686. 石子游戏 VI
Alice 和 Bob 轮流玩一个游戏#xff0c;Alice 先手。
一堆石子里总共有 n 个石子#xff0c;轮到某个玩家时#xff0c;他可以 移出 一个石子并得到这个石子的价值。Alice 和 Bob 对石子价值有 不一样的的评判标准 。双方都知道对方的评判标准。
给你…1686. 石子游戏 VI
Alice 和 Bob 轮流玩一个游戏Alice 先手。
一堆石子里总共有 n 个石子轮到某个玩家时他可以 移出 一个石子并得到这个石子的价值。Alice 和 Bob 对石子价值有 不一样的的评判标准 。双方都知道对方的评判标准。
给你两个长度为 n 的整数数组 aliceValues 和 bobValues 。aliceValues[i] 和 bobValues[i] 分别表示 Alice 和 Bob 认为第 i 个石子的价值。
所有石子都被取完后得分较高的人为胜者。如果两个玩家得分相同那么为平局。两位玩家都会采用 最优策略 进行游戏。
请你推断游戏的结果用如下的方式表示
如果 Alice 赢返回 1 。 如果 Bob 赢返回 -1 。 如果游戏平局返回 0 。
示例 1
输入aliceValues [1,3], bobValues [2,1] 输出1 解释 如果 Alice 拿石子 1 下标从 0开始那么 Alice 可以得到 3 分。 Bob 只能选择石子 0 得到 2 分。 Alice 获胜。 示例 2
输入aliceValues [1,2], bobValues [3,1] 输出0 解释 Alice 拿石子 0 Bob 拿石子 1 他们得分都为 1 分。 打平。 示例 3
输入aliceValues [2,4,3], bobValues [1,6,7] 输出-1 解释 不管 Alice 怎么操作Bob 都可以得到比 Alice 更高的得分。 比方说Alice 拿石子 1 Bob 拿石子 2 Alice 拿石子 0 Alice 会得到 6 分而 Bob 得分为 7 分。 Bob 会获胜。
提示
n aliceValues.length bobValues.length 1 n 1e5 1 aliceValues[i], bobValues[i] 100
贪心做法
class Solution {
public:int stoneGameVI(vectorint aliceValues, vectorint bobValues) {int n aliceValues.size();vectorpairint, int diff(n);for (int i 0; i n; i) {diff[i] {aliceValues[i] bobValues[i], i};}sort(diff.begin(), diff.end(), greaterpairint, int());int aliceScore 0, bobScore 0;for (int i 0; i n; i) {int idx diff[i].second;if (i % 2 0) {aliceScore aliceValues[idx];} else {bobScore bobValues[idx];}}if (aliceScore bobScore) {return 1;} else if (aliceScore bobScore) {return -1;} else {return 0;}}
};1690. 石子游戏 VII
石子游戏中爱丽丝和鲍勃轮流进行自己的回合爱丽丝先开始 。
有 n 块石子排成一排。每个玩家的回合中可以从行中 移除 最左边的石头或最右边的石头并获得与该行中剩余石头值之 和 相等的得分。当没有石头可移除时得分较高者获胜。
鲍勃发现他总是输掉游戏可怜的鲍勃他总是输所以他决定尽力 减小得分的差值 。爱丽丝的目标是最大限度地 扩大得分的差值 。
给你一个整数数组 stones 其中 stones[i] 表示 从左边开始 的第 i 个石头的值如果爱丽丝和鲍勃都 发挥出最佳水平 请返回他们 得分的差值 。
示例 1
输入stones [5,3,1,4,2] 输出6 解释
爱丽丝移除 2 得分 5 3 1 4 13 。游戏情况爱丽丝 13 鲍勃 0 石子 [5,3,1,4] 。鲍勃移除 5 得分 3 1 4 8 。游戏情况爱丽丝 13 鲍勃 8 石子 [3,1,4] 。爱丽丝移除 3 得分 1 4 5 。游戏情况爱丽丝 18 鲍勃 8 石子 [1,4] 。鲍勃移除 1 得分 4 。游戏情况爱丽丝 18 鲍勃 12 石子 [4] 。爱丽丝移除 4 得分 0 。游戏情况爱丽丝 18 鲍勃 12 石子 [] 。 得分的差值 18 - 12 6 。 示例 2
输入stones [7,90,5,1,100,10,10,2] 输出122
提示
n stones.length 2 n 1000 1 stones[i] 1000
博弈DP 没有思路参考了题解
class Solution {int p[1010], q[1010];int f[1010][1010];public:int stoneGameVII(vectorint a) {int n a.size();for (int i 1; i n; i)p[i] a[i - 1], q[i] q[i - 1] p[i];for (int i 1; i n; i)f[i][i] p[i];for (int i n; i 1; i--) {for (int j i 1; j n; j) {int x q[j] - q[i];int y q[j - 1] - q[i - 1];f[i][j] min(p[i] x - f[i 1][j], p[j] y - f[i][j - 1]);}}return q[n] - f[1][n];}
};292. Nim 游戏
你和你的朋友两个人一起玩 Nim 游戏
桌子上有一堆石头。
你们轮流进行自己的回合 你作为先手 。每一回合轮到的人拿掉 1 - 3 块石头。拿掉最后一块石头的人就是获胜者。假设你们每一步都是最优解。请编写一个函数来判断你是否可以在给定石头数量为 n 的情况下赢得游戏。如果可以赢返回 true否则返回 false 。
示例 1 输入n 4 输出false 解释以下是可能的结果: 移除1颗石头。你的朋友移走了3块石头包括最后一块。你的朋友赢了。移除2个石子。你的朋友移走2块石头包括最后一块。你的朋友赢了。 3.你移走3颗石子。你的朋友移走了最后一块石头。你的朋友赢了。 在所有结果中你的朋友是赢家。 示例 2 输入n 1 输出true 示例 3 输入n 2 输出true 实际上是一个数学题(博弈论)
class Solution {
public:bool canWinNim(int n) {return n % 4 ! 0;}
};1696. 跳跃游戏 VI
给你一个下标从 0 开始的整数数组 nums 和一个整数 k 。
一开始你在下标 0 处。每一步你最多可以往前跳 k 步但你不能跳出数组的边界。也就是说你可以从下标 i 跳到 [i 1 min(n - 1, i k)] 包含 两个端点的任意位置。
你的目标是到达数组最后一个位置下标为 n - 1 你的 得分 为经过的所有数字之和。
请你返回你能得到的 最大得分 。
示例 1
输入nums [1,-1,-2,4,-7,3], k 2 输出7 解释你可以选择子序列 [1,-1,4,3] 上面加粗的数字和为 7 。 示例 2
输入nums [10,-5,-2,4,0,3], k 3 输出17 解释你可以选择子序列 [10,4,3] 上面加粗数字和为 17 。 示例 3
输入nums [1,-5,-20,4,-1,3,-6,-3], k 2 输出0
提示
1 nums.length, k 1e5 -104 nums[i] 1e4
单调队列DP
class Solution {
public:int maxResult(vectorint nums, int k) {dequeint q {0};for (int i 1; i nums.size(); i) {// 1. 出if (q.front() i - k) {q.pop_front();}// 2. 转移nums[i] nums[q.front()];// 3. 入while (!q.empty() nums[i] nums[q.back()]) {q.pop_back();}q.push_back(i);}return nums.back();}
};LCP 30. 魔塔游戏
小扣当前位于魔塔游戏第一层共有 N 个房间编号为 0 ~ N-1。每个房间的补血道具/怪物对于血量影响记于数组 nums其中正数表示道具补血数值即血量增加对应数值负数表示怪物造成伤害值即血量减少对应数值0 表示房间对血量无影响。
小扣初始血量为 1且无上限。假定小扣原计划按房间编号升序访问所有房间补血/打怪为保证血量始终为正值小扣需对房间访问顺序进行调整每次仅能将一个怪物房间负数的房间调整至访问顺序末尾。请返回小扣最少需要调整几次才能顺利访问所有房间。若调整顺序也无法访问完全部房间请返回 -1。
示例 1
输入nums [100,100,100,-250,-60,-140,-50,-50,100,150]
输出1
解释初始血量为 1。至少需要将 nums[3] 调整至访问顺序末尾以满足要求。
示例 2
输入nums [-200,-300,400,0]
输出-1
解释调整访问顺序也无法完成全部房间的访问。
提示
1 nums.length 10^5 -10^5 nums[i] 10^5
参考了题解贪心优先队列
class Solution {
public:int magicTower(vectorint nums) {int numsSize nums.size();long long sum 0;for (int i 0; i numsSize; i) {sum nums[i];}if (sum 0)return -1;int cnt 0;long long hp 1;priority_queueint, vectorint, greaterint que;for (int i 0; i numsSize; i) {que.emplace(nums[i]);while (hp nums[i] 0) {cnt;hp - que.top();que.pop();}hp nums[i];}return cnt;}
};2641. 二叉树的堂兄弟节点 II
给你一棵二叉树的根 root 请你将每个节点的值替换成该节点的所有 堂兄弟节点值的和 。
如果两个节点在树中有相同的深度且它们的父节点不同那么它们互为 堂兄弟 。
请你返回修改值之后树的根 root 。
注意一个节点的深度指的是从树根节点到这个节点经过的边数。
示例 1 输入root [5,4,9,1,10,null,7] 输出[0,0,0,7,7,null,11] 解释上图展示了初始的二叉树和修改每个节点的值之后的二叉树。 值为 5 的节点没有堂兄弟所以值修改为 0 。值为 4 的节点没有堂兄弟所以值修改为 0 。值为 9 的节点没有堂兄弟所以值修改为 0 。值为 1 的节点有一个堂兄弟值为 7 所以值修改为 7 。值为 10 的节点有一个堂兄弟值为 7 所以值修改为 7 。值为 7 的节点有两个堂兄弟值分别为 1 和 10 所以值修改为 11 。 示例 2 输入root [3,1,2] 输出[0,0,0] 解释上图展示了初始的二叉树和修改每个节点的值之后的二叉树。 值为 3 的节点没有堂兄弟所以值修改为 0 。值为 1 的节点没有堂兄弟所以值修改为 0 。值为 2 的节点没有堂兄弟所以值修改为 0 。 提示
树中节点数目的范围是 [1, 1e5] 。 1 Node.val 1e4
菜鸡不会这题读者可以看看灵神题解
class Solution {
public:TreeNode *replaceValueInTree(TreeNode *root) {root-val 0;vectorTreeNode* q {root};while (!q.empty()) {vectorTreeNode* nxt;// 计算下一层的节点值之和int next_level_sum 0;for (auto node : q) {if (node-left) {nxt.push_back(node-left);next_level_sum node-left-val;}if (node-right) {nxt.push_back(node-right);next_level_sum node-right-val;}}// 再次遍历更新下一层的节点值for (auto node : q) {int children_sum (node-left ? node-left-val : 0) (node-right ? node-right-val : 0);if (node-left) node-left-val next_level_sum - children_sum;if (node-right) node-right-val next_level_sum - children_sum;}q move(nxt);}return root;}
};题解BFS算两次
993. 二叉树的堂兄弟节点
在二叉树中根节点位于深度 0 处每个深度为 k 的节点的子节点位于深度 k1 处。
如果二叉树的两个节点深度相同但 父节点不同 则它们是一对堂兄弟节点。
我们给出了具有唯一值的二叉树的根节点 root 以及树中两个不同节点的值 x 和 y 。
只有与值 x 和 y 对应的节点是堂兄弟节点时才返回 true 。否则返回 false。
示例 1 输入root [1,2,3,4], x 4, y 3 输出false 示例 2 输入root [1,2,3,null,4,null,5], x 5, y 4 输出true 示例 3 输入root [1,2,3,null,4], x 2, y 3 输出false 提示
二叉树的节点数介于 2 到 100 之间。 每个节点的值都是唯一的、范围为 1 到 100 的整数。
深度优先搜索DFS:
/*** Definition for a binary tree node.* struct TreeNode {* int val;* TreeNode *left;* TreeNode *right;* TreeNode() : val(0), left(nullptr), right(nullptr) {}* TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}* TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left),* right(right) {}* };*/
class Solution {
public:bool isCousins(TreeNode* root, int x, int y) {bool ans false;int depth 0;TreeNode* father nullptr;functionbool(TreeNode*, TreeNode*, int) dfs [](TreeNode* node, TreeNode* fa, int d) - bool {if (node nullptr) {return false;}if (node-val x || node-val y) {if (depth) {ans depth d father ! fa;return true;}depth d;father fa;}return dfs(node-left, node, d 1) ||dfs(node-right, node, d 1);};dfs(root, nullptr, 1);return ans;}
};236. 二叉树的最近公共祖先
给定一个二叉树, 找到该树中两个指定节点的最近公共祖先。
百度百科中最近公共祖先的定义为“对于有根树 T 的两个节点 p、q最近公共祖先表示为一个节点 x满足 x 是 p、q 的祖先且 x 的深度尽可能大一个节点也可以是它自己的祖先。”
示例 1 输入root [3,5,1,6,2,0,8,null,null,7,4], p 5, q 1 输出3 解释节点 5 和节点 1 的最近公共祖先是节点 3 。 示例 2 输入root [3,5,1,6,2,0,8,null,null,7,4], p 5, q 4 输出5 解释节点 5 和节点 4 的最近公共祖先是节点 5 。因为根据定义最近公共祖先节点可以为节点本身。 示例 3 输入root [1,2], p 1, q 2 输出1 提示
树中节点数目在范围 [2, 1e5] 内。 -1e9 Node.val 1e9 所有 Node.val 互不相同 。 p ! q p 和 q 均存在于给定的二叉树中。
参考了题解递归
/*** Definition for a binary tree node.* struct TreeNode {* int val;* TreeNode *left;* TreeNode *right;* TreeNode(int x) : val(x), left(NULL), right(NULL) {}* };*/
class Solution {
public:TreeNode* lowestCommonAncestor(TreeNode* root, TreeNode* p, TreeNode* q) {if (root nullptr || root p || root q) {return root;}auto left lowestCommonAncestor(root-left, p, q);auto right lowestCommonAncestor(root-right, p, q);if (left right) {return root;}return left ? left : right;}
};94. 二叉树的中序遍历
给定一个二叉树的根节点 root 返回 它的 中序 遍历 。
示例 1 输入root [1,null,2,3] 输出[1,3,2] 示例 2
输入root [] 输出[] 示例 3
输入root [1] 输出[1]
提示
树中节点数目在范围 [0, 100] 内 -100 Node.val 100
进阶: 递归算法很简单你可以通过迭代算法完成吗
数据结构基础
/*** Definition for a binary tree node.* struct TreeNode {* int val;* TreeNode *left;* TreeNode *right;* TreeNode() : val(0), left(nullptr), right(nullptr) {}* TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}* TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left),* right(right) {}* };*/
class Solution {void midorder(TreeNode* cur, vectorint vec) {if (cur NULL) {return;}midorder(cur-left, vec);vec.push_back(cur-val);midorder(cur-right, vec);}public:vectorint inorderTraversal(TreeNode* root) {vectorint vec;midorder(root, vec);return vec;}
};144. 二叉树的前序遍历
给你二叉树的根节点 root 返回它节点值的 前序 遍历。
示例 1
输入root [1,null,2,3] 输出[1,2,3] 示例 2
输入root [] 输出[] 示例 3
输入root [1] 输出[1] 示例 4
输入root [1,2] 输出[1,2] 示例 5
输入root [1,null,2] 输出[1,2]
提示
树中节点数目在范围 [0, 100] 内 -100 Node.val 100
进阶递归算法很简单你可以通过迭代算法完成吗
过年福利数据结构基础
/*** Definition for a binary tree node.* struct TreeNode {* int val;* TreeNode *left;* TreeNode *right;* TreeNode() : val(0), left(nullptr), right(nullptr) {}* TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}* TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left),* right(right) {}* };*/
class Solution {
public:void preorder(TreeNode* root, vectorint vec) {if (root NULL) {return;}vec.push_back(root-val);preorder(root-left, vec);preorder(root-right, vec);}vectorint preorderTraversal(TreeNode* root) {vectorint vec;preorder(root, vec);return vec;}
};145. 二叉树的后序遍历
给你一棵二叉树的根节点 root 返回其节点值的 后序遍历 。
示例 1
输入root [1,null,2,3] 输出[3,2,1] 示例 2
输入root [] 输出[] 示例 3
输入root [1] 输出[1]
提示
树中节点的数目在范围 [0, 100] 内 -100 Node.val 100
进阶递归算法很简单你可以通过迭代算法完成吗
仍然是数据结构基础
/*** Definition for a binary tree node.* struct TreeNode {* int val;* TreeNode *left;* TreeNode *right;* TreeNode() : val(0), left(nullptr), right(nullptr) {}* TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}* TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}* };*/
class Solution {
public:void lastorder(TreeNode *cur,vectorint vec){if(curNULL){return;}lastorder(cur-left,vec);lastorder(cur-right,vec);vec.push_back(cur-val);}vectorint postorderTraversal(TreeNode* root) {vectorint vec;lastorder(root,vec);return vec;}
};987. 二叉树的垂序遍历
给你二叉树的根结点 root 请你设计算法计算二叉树的 垂序遍历 序列。
对位于 (row, col) 的每个结点而言其左右子结点分别位于 (row 1, col - 1) 和 (row 1, col 1) 。树的根结点位于 (0, 0) 。
二叉树的 垂序遍历 从最左边的列开始直到最右边的列结束按列索引每一列上的所有结点形成一个按出现位置从上到下排序的有序列表。如果同行同列上有多个结点则按结点的值从小到大进行排序。
返回二叉树的 垂序遍历 序列。
示例 1 输入root [3,9,20,null,null,15,7] 输出[[9],[3,15],[20],[7]] 解释 列 -1 只有结点 9 在此列中。 列 0 只有结点 3 和 15 在此列中按从上到下顺序。 列 1 只有结点 20 在此列中。 列 2 只有结点 7 在此列中。 示例 2
输入root [1,2,3,4,5,6,7] 输出[[4],[2],[1,5,6],[3],[7]] 解释 列 -2 只有结点 4 在此列中。 列 -1 只有结点 2 在此列中。 列 0 结点 1 、5 和 6 都在此列中。 1 在上面所以它出现在前面。 5 和 6 位置都是 (2, 0) 所以按值从小到大排序5 在 6 的前面。 列 1 只有结点 3 在此列中。 列 2 只有结点 7 在此列中。 示例 3 输入root [1,2,3,4,6,5,7] 输出[[4],[2],[1,5,6],[3],[7]] 解释 这个示例实际上与示例 2 完全相同只是结点 5 和 6 在树中的位置发生了交换。 因为 5 和 6 的位置仍然相同所以答案保持不变仍然按值从小到大排序。
提示
树中结点数目总数在范围 [1, 1000] 内 0 Node.val 1000
菜鸡不会orz 看了大佬们的题解DFS哈希
class Solution {mapint, vectorpairint, int groups;void dfs(TreeNode* node, int row, int col) {if (node nullptr) {return;}groups[col].emplace_back(row, node-val);dfs(node-left, row 1, col - 1);dfs(node-right, row 1, col 1);}public:vectorvectorint verticalTraversal(TreeNode* root) {dfs(root, 0, 0);vectorvectorint ans;for (auto [_, g] : groups) {ranges::sort(g);vectorint vals;for (auto [_, val] : g) {vals.push_back(val);}ans.push_back(vals);}return ans;}
};
102. 二叉树的层序遍历
给你二叉树的根节点 root 返回其节点值的 层序遍历 。 即逐层地从左到右访问所有节点。
示例 1 输入root [3,9,20,null,null,15,7] 输出[[3],[9,20],[15,7]] 示例 2
输入root [1] 输出[[1]] 示例 3
输入root [] 输出[]
提示
树中节点数目在范围 [0, 2000] 内 -1000 Node.val 1000 BFS队列
/**
* Definition for a binary tree node.
* struct TreeNode {
* int val;
* TreeNode *left;
* TreeNode *right;
* TreeNode() : val(0), left(nullptr), right(nullptr) {}
* TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
* TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left),
* right(right) {}
* };
*/
class Solution {
public:vectorvectorint levelOrder(TreeNode* root) {queueTreeNode* que;vectorvectorint result;if (root ! NULL)que.push(root);while (!que.empty()) {int size que.size();vectorint vec;for (int i 0; i size; i) {TreeNode* node que.front();que.pop();vec.push_back(node-val);if (node-left)que.push(node-left);if (node-right)que.push(node-right);}result.push_back(vec);}return result;}
};107. 二叉树的层序遍历 II
给你二叉树的根节点 root 返回其节点值 自底向上的层序遍历 。 即按从叶子节点所在层到根节点所在的层逐层从左向右遍历
示例 1
输入root [3,9,20,null,null,15,7] 输出[[15,7],[9,20],[3]] 示例 2
输入root [1] 输出[[1]] 示例 3
输入root [] 输出[]
提示
树中节点数目在范围 [0, 2000] 内 -1000 Node.val 1000
对比上一道题只需反转最后的result
/*** Definition for a binary tree node.* struct TreeNode {* int val;* TreeNode *left;* TreeNode *right;* TreeNode() : val(0), left(nullptr), right(nullptr) {}* TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}* TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left),* right(right) {}* };*/
class Solution {
public:vectorvectorint levelOrderBottom(TreeNode* root) {queueTreeNode* que;vectorvectorint result;if (root ! NULL)que.push(root);while (!que.empty()) {int size que.size();vectorint vec;for (int i 0; i size; i) {TreeNode* node que.front();que.pop();vec.push_back(node-val);if (node-left)que.push(node-left);if (node-right)que.push(node-right);}result.push_back(vec);} reverse(result.begin(), result.end());return result;}
};
