Press "Enter" to skip to content

花花酱 LeetCode Weekly Contest 135 (1037, 1038, 1039, 1040)

LeetCode 1037. Valid Boomerang

Solution: Math
Time complexity: O(1)
Space complexity: O(1)

C++

LeetCode 1038. Binary Search Tree to Greater Sum Tree

Solution: Recursion: right, root, left

Time complexity: O(n)
Space complexity: O(n)

C++

1039. Minimum Score Triangulation of Polygon

Solution: DP

Init: dp[i][j] = 0 if 0 <= j – i <= 1
dp[i][j] := min score to triangulate A[i] ~ A[j]
dp[i][j] = min{dp[i][k] + dp[k][j] + A[i]*A[k]*A[j]), i < k < j
answer: dp[0][n – 1]

Time complexity: O(n^3)
Space complexity: O(n^2)

C++/bottom-up

C++/top-down

Python

1040. Moving Stones Until Consecutive II

Solution: Sliding Window

Time complexity: O(nlogn)
Space complexity: O(1)

C++

请尊重作者的劳动成果,转载请注明出处!花花保留对文章/视频的所有权利。
如果您喜欢这篇文章/视频,欢迎您捐赠花花。
If you like my articles / videos, donations are welcome.

Buy anything from Amazon to support our website
您可以通过在亚马逊上购物(任意商品)来支持我们

Paypal
Venmo
huahualeetcode
微信打赏

Be First to Comment

Leave a Reply