Re: [閒聊] 每日LeetCode已回收

看板Marginalman作者Rushia (みけねこ的鼻屎)時間2年前 (2023/03/22 00:14)推噓2(2推 0噓 1→)

留言3則, 3人參與討論串268/719 (看更多)

2348. Number of Zero-Filled Subarrays 給你一個陣列表示的序列，求出元素連續為0的子序列總數共有多少個。 Example: Input: nums = [0,0,0,2,0,0] Output: 9 Explanation: [0]子序列共有5個 [0,0]共有3個， [0,0,0]共有1個總共有9個思路： 1.觀察[0] -> [0,0] 、[0,0] -> [0,0,0] 產生的子序列數量變化，我們發現每多出一個0，都可以和先前的子序列成為一個新的子序列。 2.因為1的關係我們得知這個問題有最佳子結構，所以可以用動態規劃來求解，狀態轉移方程：dp[i] = dp[i - 1] + i ，dp[i]表示連續i個0可以組成的子序列數量。 3.遇到連續0就不斷的累加，否則把0的數量重置，遍歷一遍之後就可以得到解了。 Java Code： -------------------------------------------- class Solution { public long zeroFilledSubarray(int[] nums) { long ans = 0; int count = 0; for (int num : nums) { if (num == 0) { count++; ans += count; } else { count = 0; } } return ans; } } -------------------------------------------- -- https://i.imgur.com/CBMFmWk.jpg