Leetcode Weekly Contest 142 Solution

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

Leave a Reply

Your email address will not be published.