[Algorithm][综合训练][打怪][判断是不是平衡二叉树][最大子矩阵]详细讲解

本文主要是介绍[Algorithm][综合训练][打怪][判断是不是平衡二叉树][最大子矩阵]详细讲解，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

1.打怪

1.题目链接

打怪

2.算法原理详解 && 代码实现

自己的版本：暴力模拟

#include <iostream>
using namespace std;int main()
{int t = 0;cin >> t;int h, a, H, A;while(t--){cin >> h >> a >> H >> A;if(a >= H){cout << -1 << endl;continue;}int cnt = 0, tmpH = H;while(h > 0){if((tmpH -= a) <= 0){cnt++;tmpH = H;continue;}h -= A;}cout << cnt << endl;}return 0;
}

优化版本：数学

遇到一只怪物，怪物能抗几次?
- m = H / a + (H % a != 0 ? 1 : 0)
杀死一只怪物的时候，玩家被攻击几次
- n = m - 1
杀死一只怪物的时候，玩家掉几点血
- x = n * A
玩家一共能杀死多少怪物
- ret = h / x - (h % x == 0 ? 1 : 0)

#include <iostream>
using namespace std;int h, a, H, A;int Check()
{if(a >= H){return -1;}int m = (H / a) + (H % a != 0 ? 1 : 0); // 怪物能抗⼏次int n = m - 1; // 玩家被攻击⼏次int x = n * A; // 杀死⼀只怪物的时候，玩家会掉多少⾎int ret = h / x - (h % x == 0 ? 1 : 0);return ret;
}int main()
{int t = 0;cin >> t;while(t--){cin >> h >> a >> H >> A;cout << Check() << endl;}return 0;
}

2.判断是不是平衡二叉树

1.题目链接

判断是不是平衡二叉树

2.算法原理详解 && 代码实现

优化版本：

class Solution 
{
public:bool IsBalanced_Solution(TreeNode* pRoot) {return DFS(pRoot) != -1;}// 返回值不是-1的话，其余的返回值表示的是树高int DFS(TreeNode* root){if(root == nullptr){return 0;}int left = DFS(root->left);if(left == -1){return -1; // 剪枝}int right = DFS(root->right);if(right == -1){return -1;}return abs(left - right) <= 1 ? max(left, right) + 1 : -1;}
};

3.最大子矩阵

1.题目链接

最大子矩阵

2.算法原理详解 && 代码实现

解法：二维前缀和
- 初始化⼆维前缀和矩阵
- 枚举所有的⼦矩阵，求出最⼤⼦矩阵

如何枚举所有的子矩阵？

for(0 ~ n - 1) -> x1for(0 ~ m - 1) -> y1for(x1 ~ mn - 1) -> x2for(y1 ~ m - 1) -> y2

如何计算矩阵中所有元素的和？ --> 二位前缀和 --> 动态规划

初始化二维dp表
使用二维dp表

#include <iostream>
#include <vector>
using namespace std;int main()
{int n = 0, x = 0;cin >> n;// 动态规划 --> 求二维前缀和数组vector<vector<int>> dp(n + 1, vector<int>(n + 1, 0));for(int i = 1; i <= n; i++){for(int j = 1; j <= n; j++){cin >> x;dp[i][j] = dp[i - 1][j] + dp[i][j - 1] - dp[i - 1][j - 1] + x;}}int ret = -0x3f3f3f3f;for(int x1 = 1; x1 <= n; x1++){for(int y1 = 1; y1 <= n; y1++){for(int x2 = x1; x2 <= n; x2++){for(int y2 = y1; y2 <= n; y2++){ret = max(ret, dp[x2][y2] - dp[x1 - 1][y2] - dp[x2][y1 - 1] + dp[x1 - 1][y1 - 1]);}}}}cout << ret << endl;return 0;
}