[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;
  }
  

这篇关于[Algorithm][综合训练][打怪][判断是不是平衡二叉树][最大子矩阵]详细讲解的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！

---