• 设为首页
  • 点击收藏
  • 手机版
    手机扫一扫访问
    迪恩网络手机版
  • 关注官方公众号
    微信扫一扫关注
    公众号

[Swift]LeetCode410.分割数组的最大值|SplitArrayLargestSum

原作者: [db:作者] 来自: [db:来源] 收藏 邀请

★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★
➤微信公众号:为敢(WeiGanTechnologies)
➤博客园地址:山青咏芝(https://www.cnblogs.com/strengthen/
➤GitHub地址:https://github.com/strengthen/LeetCode
➤原文地址: https://www.cnblogs.com/strengthen/p/10330269.html
➤如果链接不是山青咏芝的博客园地址,则可能是爬取作者的文章。
➤原文已修改更新!强烈建议点击原文地址阅读!支持作者!支持原创!
★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★

热烈欢迎,请直接点击!!!

进入博主App Store主页,下载使用各个作品!!!

注:博主将坚持每月上线一个新app!!!

Given an array which consists of non-negative integers and an integer m, you can split the array into m non-empty continuous subarrays. Write an algorithm to minimize the largest sum among these m subarrays.

Note:
If n is the length of array, assume the following constraints are satisfied:

  • 1 ≤ n ≤ 1000
  • 1 ≤ m ≤ min(50, n

Examples:

Input:
nums = [7,2,5,10,8]
m = 2

Output:
18

Explanation:
There are four ways to split nums into two subarrays.
The best way is to split it into [7,2,5] and [10,8],
where the largest sum among the two subarrays is only 18.

给定一个非负整数数组和一个整数 m,你需要将这个数组分成 个非空的连续子数组。设计一个算法使得这 个子数组各自和的最大值最小。

注意:
数组长度 满足以下条件:

  • 1 ≤ n ≤ 1000
  • 1 ≤ m ≤ min(50, n)

示例:

输入:
nums = [7,2,5,10,8]
m = 2

输出:
18

解释:
一共有四种方法将nums分割为2个子数组。
其中最好的方式是将其分为[7,2,5] 和 [10,8],
因为此时这两个子数组各自的和的最大值为18,在所有情况中最小。

12ms
 1 class Solution {
 2     func splitArray(_ nums: [Int], _ m: Int) -> Int {
 3         var nums = nums
 4         var left:Int = 0
 5         var right:Int = 0
 6         for i in 0..<nums.count
 7         {
 8             left = max(left, nums[i])
 9             right += nums[i]
10         }
11         while (left < right)
12         {
13             var mid:Int = left + (right - left) / 2
14             if canSplit(&nums, m, mid)
15             {
16                 right = mid
17             }
18             else
19             {
20                 left = mid + 1
21             }
22         }
23         return left
24     }
25     
26     func canSplit(_ nums:inout [Int], _ m: Int, _ sum: Int) -> Bool
27     {
28         var cnt:Int = 1
29         var curSum:Int = 0
30         for i in 0..<nums.count
31         {
32             curSum += nums[i]
33             if curSum > sum
34             {
35                 curSum = nums[i]
36                 cnt += 1
37                 if cnt > m
38                 {
39                     return false
40                 }
41             }
42         }
43         return true
44     }
45 }

 


鲜花

握手

雷人

路过

鸡蛋
该文章已有0人参与评论

请发表评论

全部评论

专题导读
上一篇:
Swift中的类型属性(静态变量)发布时间:2022-07-13
下一篇:
Swift入门篇-HelloWorldSwift入门篇-swift简介发布时间:2022-07-13
热门推荐
热门话题
阅读排行榜

扫描微信二维码

查看手机版网站

随时了解更新最新资讯

139-2527-9053

在线客服(服务时间 9:00~18:00)

在线QQ客服
地址:深圳市南山区西丽大学城创智工业园
电邮:jeky_zhao#qq.com
移动电话:139-2527-9053

Powered by 互联科技 X3.4© 2001-2213 极客世界.|Sitemap