首页 > itarticle > [python] algorithm

[python] algorithm

admin 11月 27, 2020 0

Binary Search

bisect: https://docs.python.org/3/library/bisect.html. Support for maintaining a list in sorted order without having to sort the list after each insertion.

bisect.bisect_left(a, x, lo=0, hi=len(a)) 
lo, hi: # used to specify a subset of the list which should be considered

# if x is in a, the insertion point will be before (to the LEFT of ) any existing entries.
# The returned insetion point i: 
all(val < x for val in a[lo:i]) # for the left side
all(val >= x for val in a[i:hi]) # for the right side
bisect.bisect(a, x, lo=0, hi=len(a)) 
bisect.bisect_right(a, x, lo=0, hi=len(a)) # returns an insertion point which comes after (to the Right of) any existing entries

611. Valid Triangle Number

Leetcode: https://leetcode.com/problems/valid-triangle-number/

def (self, nums):
    """
    :type nums: List[int]
    :rtype: int
    """
    nums.sort()
    cnt = 0
    if len(nums) < 3:
        return cnt
    i = 0
    for i in range(len(nums) - 2):
        for a in range(i + 1, len(nums) - 1):
            tar = nums[i] + nums[a]
            j = bisect.bisect_left(nums, tar, lo = a + 1, hi = len(nums))
            cnt += j - a - 1
    return cnt