1020. Partition Array Into Three Parts With Equal Sum
Return true if there is a 2/3*sum prefix sum after a 1/3 prefix sum
|
1 2 |
[---- 1/3 ----][-----1/3-----][-----1/3-----] [------------2/3-------------][-----1/3-----] |
Time complexity: O(n)
Space complexity: O(1)
Python
|
1 2 3 4 5 6 7 8 9 10 11 |
class Solution: def canThreePartsEqualSum(self, A: List[int]) -> bool: s = sum(A) if s % 3 != 0: return False c = 0 found = False for a in A: c += a if c == s // 3 * 2 and found: return True if c == s // 3: found = True return False |
1021. Best Sightseeing Pair
Greedy, only keep the best A[i] + i so far and pair with A[j] – j, i < j
Time complexity: O(n)
Space complexity: O(1)
C++
|
1 2 3 4 5 6 7 8 9 10 11 12 |
class Solution { public: int maxScoreSightseeingPair(vector<int>& A) { int ans = 0; int left = 0; for (int i = 0; i < A.size(); ++i) { ans = max(ans, left + A[i] - i); left = max(left, A[i] + i); } return ans; } }; |
1022. Smallest Integer Divisible by K
Math
Time complexity: O(K)
Space complexity: O(1)
C++
|
1 2 3 4 5 6 7 8 9 10 11 12 |
class Solution { public: int smallestRepunitDivByK(int K) { if (K % 2 == 0 || K % 5 == 0) return -1; int r = 0; for (int l = 1; l <= K; ++l) { r = (r * 10 + 1) % K; if (r == 0) return l; } return -1; } }; |
1023. Binary String With Substrings Representing 1 To N
Brute Force, try all possible substrings and convert them into decimals.
Time complexity: O(|S|*log(N)^2)
Python
|
1 2 3 4 5 6 7 8 9 10 11 |
class Solution: def queryString(self, S: str, N: int) -> bool: s = set() c = 0 for l in range(1, 32): for i in range(0, len(S) - l + 1): n = int(S[i:i+l], 2) if n == 0 or n > N or n in s: continue s.add(n) c += 1 return c == N |
请尊重作者的劳动成果，转载请注明出处！花花保留对文章／视频的所有权利。
如果您喜欢这篇文章／视频，欢迎您捐赠花花。
If you like my articles / videos, donations are welcome.
Paypal
Venmo
huahualeetcode
huahualeetcode
微信打赏
Be First to Comment