1093 A Statistics from a Large Sample

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}}"))