区块链技术博客
www.b2bchain.cn

[LeetCode 周赛186] 3. 分割字符串的最大得分(数学规律、常规解法)

这篇文章主要介绍了[LeetCode 周赛186] 3. 分割字符串的最大得分(数学规律、常规解法)的讲解,通过具体代码实例进行19748 讲解,并且分析了[LeetCode 周赛186] 3. 分割字符串的最大得分(数学规律、常规解法)的详细步骤与相关技巧,需要的朋友可以参考下https://www.b2bchain.cn/?p=19748

本文实例讲述了2、树莓派设置连接WiFi,开启VNC等等的讲解。分享给大家供大家参考文章查询地址https://www.b2bchain.cn/7039.html。具体如下:

文章目录

    • 1. 题目来源
    • 2. 题目说明
    • 3. 题目解析
      • 方法一:数学规律+常规解法

1. 题目来源

链接:5394. 对角线遍历 II

2. 题目说明

[LeetCode 周赛186] 3. 分割字符串的最大得分(数学规律、常规解法)
[LeetCode 周赛186] 3. 分割字符串的最大得分(数学规律、常规解法)

3. 题目解析

方法一:数学规律+常规解法

感觉就是考了一个数学知识…就矩阵的性质来讲,正对角线上的所有元素其行、列和为定值,反对角线即差为定值。若是采用模拟来做的话很可能会 TLE 啊,毕竟会达到 1e10 的复杂度了,不知道有什么优化点没。对角线性质解法如下:

  • 定义一个 以 vector 作为元素的数组,用以存放对角线的所有元素,这个数组的大小为 1e5 + 1e5 这就是行列和的最大值了,所有数组开到这个大小就行了
  • 遍历二维数组 nums 这个得按照行从大到小进行遍历,这样才能符合对角线正确的输出顺序。或者行从小到大完了之后再排序也是可以的
  • 将遍历到的 nums 元素的行列值相加,作为数组的索引值,也就是对角线分组,将这个元素尾插进数组即可
  • 最后就顺序输出这个数组中的各个元素到一个一维数组,最后返回这个一维数组即可

参见代码如下:

// 执行用时 :600 ms, 在所有 C++ 提交中击败了100.00%的用户 // 内存消耗 :81.3 MB, 在所有 C++ 提交中击败了100.00%的用户  const int MAXN = 1e5 + 50; vector<int> arr[MAXN * 2];  class Solution { public:     vector<int> findDiagonalOrder(vector<vector<int>>& nums) {         int n = nums.size(), m = 0;         for (auto e : nums) m = max(m, (int)(e.size()));         for (int i = 0; i <= n + m; ++i) arr[i].clear();         for (int i = n - 1; i >= 0; --i) {             for (int j = 0, col = nums[i].size(); j < col; ++j) {                 arr[i + j].push_back(nums[i][j]);             }         }         vector<int> vt;         for (int i = 0; i<= n + m; ++i) {             for (auto e : arr[i]) vt.push_back(e);         }         return vt;     } }; 

本文转自互联网,侵权联系删除[LeetCode 周赛186] 3. 分割字符串的最大得分(数学规律、常规解法)

赞(0) 打赏
部分文章转自网络,侵权联系删除b2bchain区块链学习技术社区 » [LeetCode 周赛186] 3. 分割字符串的最大得分(数学规律、常规解法)
分享到: 更多 (0)

评论 抢沙发

  • 昵称 (必填)
  • 邮箱 (必填)
  • 网址

b2b链

联系我们联系我们