# Weekly Contest 268
# 2078. Two Furthest Houses With Different Colors
# Solution
from collections import defaultdict
class Solution:
def maxDistance(self, colors: List[int]) -> int:
res = 0
for i in range(len(colors)):
for j in range(len(colors) - 1, i, -1):
if colors[i] != colors[j]:
res = max(res, abs(i - j))
return res
# 2079. Watering Plants
class Solution:
def wateringPlants(self, plants: List[int], capacity: int) -> int:
startIndex = -1
currentIndex = 0
standPoint = -1
cnt = 0
currentCapacity = capacity
while currentIndex < len(plants):
while currentIndex < len(plants) and currentCapacity >= plants[currentIndex]:
cnt += currentIndex - standPoint
currentCapacity -= plants[currentIndex]
standPoint = currentIndex
currentIndex += 1
# print(cnt)
if currentIndex < len(plants):
cnt += standPoint - startIndex
standPoint = startIndex
currentCapacity = capacity
# print('return: ' + str(cnt))
return cnt
# Leetcode 2080. Removing Minimum and Maximum From Array
class RangeFreqQuery:
def __init__(self, arr: List[int]):
self.dict = defaultdict(list)
# self.array = arr
for i, num in enumerate(arr):
self.dict[num].append(i)
# print(self.dict)
def query(self, left: int, right: int, value: int) -> int:
if value not in self.dict:
return 0
indexes = self.dict[value]
# print(indexes)
indexLeft = bisect.bisect_left(indexes, left)
indexRight = bisect.bisect_right(indexes, right)
# print(indexLeft, indexRight)
return indexRight - indexLeft
# for index in indeice:
# if left <= index <= right:
# cnt += 1
# if index > right:
# break
# return cnt
# [1,3,4,8,9]
# 2 5
# 1 3
# Your RangeFreqQuery object will be instantiated and called as such:
# obj = RangeFreqQuery(arr)
# param_1 = obj.query(left,right,value)
# Leetcode 2081 Sum of k-Mirror Numbers
2081. Sum of k-Mirror Numberst
There are two ways to enumerate: using base 10 or using base k. It's obvious that enumerate using base k is a better choice.
Now we take a look at how to generate next palindrome k-based number.
For each k-based number, the first k-mirror number would be from 1 to k - 1. We say that as our base case.
For each k-based palindrome number of length n, we can insert a number in the middle to make it a palindrome number of length n+1.
And there are two cases here:
- n % 2 == 1. We can only insert a number that is the same as the middle one. i.e. 121 -> 1221. otherwise, it won't be palindrome.
- n % 2 == 0. We can insert any number from 0-9. i.e 1221-> 12021, 12121, 12221, ......
After we find the patten here, we can right the code:
class Solution:
def isMirrorBase10(self, temp, k):
num = int(temp, k)
if str(num) == str(num)[::-1]:
return True, num
else:
return False, num
def kMirror(self, k: int, n: int) -> int:
if n < k:
total = 0
for i in range(1, n+1):
total += i
return total
baseCase = [str(i) for i in range(1, k)] #base case from 1 to k - 1
index = 0
total = 0
for i in range(1, k):
total += i
cnt = k - 1
while True:
# current = baseCase.pop(0) #don't use this, lead to TLE, since pop requires O(n)
current = baseCase[index]
midIndex = len(current) // 2
if len(current) % 2 == 1:
temp = current[0:midIndex + 1] + current[midIndex] + current[midIndex + 1:]
baseCase.append(temp)
flag, num = self.isMirrorBase10(temp, k)
if flag:
total += num
cnt += 1
if cnt >= n:
return total
else:
for i in range(0, k):
temp = current[0:midIndex] + str(i) + current[midIndex:]
baseCase.append(temp)
flag, num = self.isMirrorBase10(temp, k)
if flag:
total += num
cnt += 1
if cnt >= n:
return total
index += 1
return total