C++ python 用Prefix Sum速解Leetcode 2270 Number of Ways to Split Array

An-Wen Deng
4粉絲
5 次觀看·2025年1月3日
各位好,我們來看今天Decode的問題
2270題,所謂Number of ways to split a break
就是分割陣列的二種類的次數
我們看一下它的一個題目
這邊它就給一個從0開始編號的整數的array
名字就叫做Numbers
長度假設是n
基本上它的一個問題就是
我們要將這個Numbers這個陣列分割
分割在它index i的地方
那基本上也就是說
它前面所謂i加1個
也就是從第0個到第i個
這些元素的和
它是大於等於後面的
後面的這些陣列元素的和
第二項這個很重要
它的左右都必須要有至少一個元素
不能是沒有的
所以它的分割這邊要特別留意
特別在撰寫程式的時候
比較不小心的話就會錯誤
請返回有效分割的次數
所謂有效分割
那我們看一下它相關的立體
我們看它的立體部分
首先我們先看它所謂立體的部分
立體的部分我們就直接考慮
它的陣列是10 4-8 7
那我們怎麼去考慮這樣的問題呢
所以它基本上分割當然就是
有三個位置
那我們看一下它大概的情況
我們第一件事情可能先做一件事情
就是先將它的總和把它加起來
所以 10 加 4-8 加 7 是 13
那我們先看
我們看一下它的分割
如果 i 是等於 0 的時候
所以我們就計算前面這個
我們就用另外一個邊數名稱來表示
假設叫做 ACC
所以這時候 ACC 當然就是 10
10 呢
它當然是大於後面的
這些邊數的和
13-10
剩下的當然就是
加起來當然是 3
所以這一項是 OK 的
再來我們看 i 等於 1 的時候
也就是分割到這邊
所以這時候 ACC 當然是
延續著前面
10 再加 4 等於 14
那 14 呢
當然是會大於後面
-8 加 7
所以大於-1
所以這一項也 OK
好 再來最後一個
最後一個當然是 i 等於 2 的部分
i 等於 2 的部分當然就是
這時候 ACC 呢
14 再減 8
所以就是變成 6
這個時候呢
它後面的這一項是 7 嘛
所以 7 當然是大於 6
所以這一項就沒有了
所以基本上它的分割
三個分割裡面有兩個分割是有效的
所以這一題的答案當然是 2
那我們再看第二個例題
第二個例題呢
其實因為它都是正的
都是正的當然就比較簡單
就比第一個例題要簡單一些
那所以原則上
它的有效分割
一個是在 1 的部分
那另外一個是在 2 的部分
那這兩個是為有效的一個分割
那我們看一下
在接下來我們來看一下
它相關的 constraint
我們看它有關 constraint 的一個部分
constraint 部分當然是跟我們的一個
解答部分會有一些關聯性
那基本上我們看一下
那在這邊它的
numbers 的它的長度
它是可以到 10 萬
那它每一個相關數字
它是
它的範圍是負 10 萬到 10 萬之間
所以以這樣的情況來講
如果說我們是用 C
C++
來考慮這樣的問題
這個時候你可能就要用 64 位元的整數
基本上也就是用所謂的 long-long
來解這樣一個問題
不然的話
在你的程式當中
有可能就造成 overflow
所以這一部分要特別小心
接下來我們看一下
我們解題的一個概要
那我們這邊先看
我們到底要怎麼解的
首先我們先看這個不等式
兩個等價的不等式
那在這邊上
當然就是指的是
這些元素的總和
所以我們當然
因為它切割是在到 i 的部分
然後後面當然是從 i 加 1 開始到最後
最後當然就是 n 減 1
它的 index
所以如果說你前面
前面的 i 加 1 項
要大於後面的
這些項次呢
實際上來講的話
我們就直接透過
這樣一個不等式其實就可以解了
也就是說
兩倍的前面的
prefix 上
它會大於
等於
全部的總和
我們基本上可以透過這樣的方式
可以將我們裡面的算式稍微簡化一些
所以我們的一個做法
第一步當然就是
先將它的總和把它加起來
如果是在 c++ 的話
我們當然只用 accumulate
就可以了
如果你要用迴圈
這也不成問題
然後
根據我們剛剛解說的時候
我們是用一個變數
叫做 ACC
ACC 的話當然一開始是 0
那因為你要考慮到
可能會有
overflow 的問題
所以原則上我們
將它宣告為
none
那你要計算
多少次數
所以我們就先
將
變數
CNT 先設為 0
然後透過一個迴圈
大概
也就是透過這樣的一個不等式
我們其實
就可以算出它有多少次數
所以你的
ACC 呢
基本上透過每次
numbers 在 i 的值去累加
基本上也就是我們
prefix 上的一個概念
然後只要兩倍的 ACC 呢
是大於等於上
我們就
加 1
否則的話就加 0
所以基本上這邊就是用到
這樣的一個
等價的一個不等式
然後
CNT 當然就是
我們的答案
接下來我們看
我們的其中一個解答
那我們其中一個
細項的解答我們在
這邊的話我們是用
前面在這裡
我們就是用
accumulate 去計算
它的一個總和
然後將它總和呢
用 sum 這樣的一個變數去存
然後接下來我們就
當然你可以根據我們剛剛的
說明用你的 for 迴圈
for loop 那也可以
用所謂的
count if
這樣的一個函數
那因為
你要注意到它在
它的右邊
那一項它至少要
有一個
所以你在迭代的部分
這邊在 end
的地方你必須要減 1
然後
因為我們這邊是採用
λ 所以
acc 一開始當然設為
0 但是呢它當然
在這裡這裡我們要設
所謂 long long 的
一個型態
那另外我們還要
一個變數 sum
基本上用這邊
然後它的每一項是 x
那因為 acc 它
會變可變的
所以這邊要加上 mutable
所以 acc 加
等於 x
所以兩倍的 xcc
如果是單人上
它就去
加 1
所以原則上我們也可以
透過這樣比較簡化的方式
將
這個解答
這樣做出來 接下來我們看我們在
Liql 實作的一個情況
好
我們在 Liql 這邊我們看
Python 的部分
這個就比較
寫法就
比較單純一些
那這邊的 sum
我們 x 改為大寫
不要跟函數的名稱一致
所以我們讓它
執行一次
好 我們 submit 看看
好 OK
那另外我們
還有另外
的解答
應該是 C++ 的
解答
在這邊也是剛剛
所呈現的
讓它執行一次
好 submit
好 在這邊的話
當然毫無問題的是
我們就直接
打到 0 毫秒
好
Python 的部分
好 那我們大概就先
談到這裡
