## Leetcode Weekly Contest 142 Solution

This problem is very simple, probably means the array count counting a given array, the array represents the i-th item has a count in the count array [i] a i, returns a list, this array are the minimum, maximum, average , median, mode

This question is then no difficulty understanding the problem, you need to pay attention to is the need to return floating-point, and given the title are integers, need to remember where a conversion

```import math
class Solution:
def sampleStats(self, count: List[int]) -> List[float]:
for i in range(256):
if count[i]:
minimum = i
break
for i in range(255, -1, -1):
if count[i]:
maximum = i
break
sum = 0
square_sum = 0
total_count = 0
mode = 0
mode_index = 0
for i in range(256):
sum += i * count[i]
square_sum += i * i * count[i]
total_count += count[i]
if count[i] > count[mode_index]:
mode_index = i
mean = sum / total_count
mode = mode_index

if total_count % 2 == 0:
less_index = total_count // 2
bigger_index = less_index + 1
less = 0
bigger = 0
for i in range(256):
if count[i] > 0:
if less_index <= count[i]:
less = i
break
less_index -= count[i]
for i in range(256):
if count[i] > 0:
if bigger_index <= count[i]:
bigger = i
break
bigger_index -= count[i]
median = (less + bigger) / 2
else:
index = total_count // 2
for i in range(256):
if count[i] > 0:
if index <= count[i]:
median = i
break
index -= count[i]

return [float(minimum), float(maximum), float(mean), float(median), float(mode)]
```

### 1094. Car Pooling

There is a car subject to the effect of n passengers, then there are some passengers, each passenger has a boarding section, asked from the beginning to the end, whether the car can pack all passengers .

Solution: respectively passenger departure station and arrival station sorting, and then followed through the array departure, has been let off before the arrival of passengers on the train, and then check the car is enough space in this Station, if not, then returns False, down through to the end, returns True. require a secondary index record passengers get off. sorting complexity O (nlogn), check the complexity O (n), the total complexity of O (nlogn)

```class Solution:
def carPooling(self, trips: List[List[int]], capacity: int) -> bool:
sort_by_start = sorted(trips, key = lambda x : x[1])
sort_by_target = sorted(trips, key = lambda x : x[2])

index_of_sort_by_target = 0
for trip in sort_by_start:
capacity -= trip[0]
while index_of_sort_by_target < len(sort_by_target) and sort_by_target[index_of_sort_by_target][2] <= trip[1]:
capacity += sort_by_target[index_of_sort_by_target][0]
index_of_sort_by_target += 1
if capacity < 0:
return False

return True
```

### 1095. Find in Mountain Array

Title effect: a front half of the array of monotonically increasing, monotonically decreasing half, if there is the specified array logarithmically

Solution: Use the rule of thirds to find the largest element in the array, and then divided into two sections were used to find whether there is a difference dichotomy specified element at the time to pay attention to the rule of thirds, if the left and right boundaries adjacent to need extra. to handle it, otherwise I might be wrong. dichotomy and trichotomy complexity is O (logn)

```# """
# This is MountainArray's API interface.
# You should not implement it, or speculate about its implementation
# """
#class MountainArray:
#    def get(self, index: int) -> int:
#    def length(self) -> int:

class Solution:
def findInMountainArray(self, target: int, mountain_arr: 'MountainArray') -> int:
highest_index = 0
l = 0
r = mountain_arr.length()
while l < r:
m = (l + r) // 2
m2 = (m + r) // 2
if mountain_arr.get(m) < mountain_arr.get(m2):
l = m + 1
higher = m2
else:
r = m2
higher = m
if r - l <= 1:
break
highest_index = higher
print(highest_index)
# find target in left
l = 0
r = highest_index
while l < r:
m = (l + r) // 2
value = mountain_arr.get(m)
if value < target:
l = m + 1
elif value > target:
r = m
else:
return m
if l < mountain_arr.length() and mountain_arr.get(l) == target:
return l
# find target in right
l = highest_index
r = mountain_arr.length()
while l < r:
m = (l + r) // 2
value = mountain_arr.get(m)
if value > target:
l = m + 1
elif value < target:
r = m
else:
return m
if l < mountain_arr.length() and mountain_arr.get(l) == target:
return l
return -1
```

### 1096. Brace Expansion II

Title effect: seeking string Cartesian product

Solution: recursive method to convert the problem into sub {} in question, and finally returns Cartesian product, the python treated directly with I itertools.product here, remember to re

```from typing import *
import itertools
class Solution:
def braceExpansionII(self, expression: str) -> List[str]:
return self.expand(expression)

def expand(self, expression):
if not expression:
return []
pos = 0
word = []
word_set = set()
while pos <= len(expression):
if pos == len(expression):
c = ','
else:
c = expression[pos]
if c == '{':
end_pos = self.findMatchedBracket(expression, pos)
word.append(self.expand(expression[pos + 1:end_pos]))
pos = end_pos
elif c == ',':
word_set |= set(map(''.join, itertools.product(*word)))
word = []
else:
word.append()
pos += 1
print("expand" , expression, list(word_set))
return sorted(word_set)

def findMatchedBracket(self, expression, start_pos):
bracketCount = 0
pos = start_pos + 1
while pos < len(expression):
if expression[pos] == '{':
bracketCount += 1
elif expression[pos] == '}':
if bracketCount == 0:
return pos
bracketCount -= 1
pos += 1
return None

print(Solution().expand("{a,b}{c{d,e}}"))
print(Solution().expand("{{a,z},a{b,c},{ab,z}}"))
```