cdsn_Python 2022-09-11 18:08 采纳率: 69%
浏览 18
已结题

关于#leetcode#二分查找的问题,如何解决?

问题遇到的现象和发生背景

做leetcode1712练习题如下:

我们称一个分割整数数组的方案是 好的 ,当它满足:

数组被分成三个 非空 连续子数组,从左至右分别命名为 left , mid , right 。
left 中元素和小于等于 mid 中元素和,mid 中元素和小于等于 right 中元素和。
给你一个 非负 整数数组 nums ,请你返回 好的 分割 nums 方案数目。由于答案可能会很大,请你将结果对 109 + 7 取余后返回。
示例 1:
输入:nums = [1,1,1]
输出:1
解释:唯一一种好的分割方案是将 nums 分成 [1] [1] [1] 。
示例 2:
输入:nums = [1,2,2,2,5,0]
输出:3
解释:nums 总共有 3 种好的分割方案:
[1] [2] [2,2,5,0]
[1] [2,2] [2,5,0]
[1,2] [2,2] [5,0]

问题相关代码,请勿粘贴截图
import bisect
def waysToSplit(nums) -> int:
    cnt = [nums[0]]
    n = len(nums)
    ans = 0
    for i in range(1, n):
        cnt.append(cnt[-1] + nums[i])
    print(cnt)
    for i in range(n - 1):
        m = cnt[-1] - cnt[i]
        if 2 * m >= cnt[i]:
            x = bisect.bisect_right(cnt, cnt[i] // 2)
            y = bisect.bisect_right(cnt, cnt[i] - m)
            ans += x - y
    return ans
运行结果及报错内容

最后单位ans总是不能完全符合全部例子的答案

我的解答思路和尝试过的方法

将数列累加形成新的cnt递增数列,然后打算用二分查找计算可能得种类

尝试过改变二分查找的right和left,或者改变边界值

我想要达到的结果

帮忙看一下哪里出了问题

  • 写回答

2条回答 默认 最新

  • CSDN-Ada助手 CSDN-AI 官方账号 2022-09-11 19:10
    关注
    评论

报告相同问题?

问题事件

  • 已结题 (查看结题原因) 9月14日
  • 创建了问题 9月11日

悬赏问题

  • ¥30 python代码,帮调试
  • ¥15 #MATLAB仿真#车辆换道路径规划
  • ¥15 java 操作 elasticsearch 8.1 实现 索引的重建
  • ¥15 数据可视化Python
  • ¥15 要给毕业设计添加扫码登录的功能!!有偿
  • ¥15 kafka 分区副本增加会导致消息丢失或者不可用吗?
  • ¥15 微信公众号自制会员卡没有收款渠道啊
  • ¥100 Jenkins自动化部署—悬赏100元
  • ¥15 关于#python#的问题:求帮写python代码
  • ¥20 MATLAB画图图形出现上下震荡的线条