Press "Enter" to skip to content

花花酱 LeetCode Weekly Contest 133

LeetCode 1029 Two City Scheduling

Solution1: DP

dp[i][j] := min cost to put j people into city A for the first i people
dp[0][0] = 0
dp[i][0] = dp[i -1][0] + cost_b
dp[i][j] = min(dp[i – 1][j] + cost_b, dp[i – 1][j – 1] + cost_a)
ans := dp[n][n/2]

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

C++

Solution 2: Greedy

Sort by cost_a – cost_b

Choose the first n/2 people for A, rest for B

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

C++

1030. Matrix Cells in Distance Order

Solution: Sorting

Time complexity: O(RC*log(RC))
Space complexity: O(RC)

C++

1031. Maximum Sum of Two Non-Overlapping Subarrays

Solution: Prefix sum

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

C++

1032. Stream of Characters

Solution: Trie

Time complexity:

  • build O(sum(len(w))
  • query O(max(len(w))

Space complexity: O(sum(len(w))

C++

Java

请尊重作者的劳动成果,转载请注明出处!花花保留对文章/视频的所有权利。
如果您喜欢这篇文章/视频,欢迎您捐赠花花。
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