Python using hashmap with explanation


  • 0
    W

    def lengthOfLIS(self, nums):
    """
    :type nums: List[int]
    :rtype: int
    """
    # hashmap key:the max subsequence before this number / value:list of the nums with this step read before
    # if this number bigger than anyone number with the max steps of subsequence, it will add one key +1 to the hashmap
    # for example: [10, 9, 2, 5, 3, 7, 101, 18]
    # when it comes to 7, hashmap before: {1: [10, 9, 2], 2: [5, 3]} | hashmap after: {1: [10, 9, 2], 2: [5, 3], 3: [7]}
    l = len(nums)
    if l == 0:
    return 0
    hash = {1:[]}
    bigkey = 1
    for i in range(l):
    # print hash
    key = bigkey
    while(key>=1):
    if len(list(filter(lambda x:x<nums[i],hash[key]))) >0:
    key = key +1
    if key>bigkey: bigkey = key
    if key in hash:
    hash[key].append(nums[i])
    else:
    hash[key] = [nums[i]]
    break
    else:
    key = key-1
    if key == 0:
    hash[1].append(nums[i])
    return bigkey


  • 0
    O

    Please, update your example as it is not possible to read your code


  • 0
    W

    Sorry for that.

    class Solution(object):
        def lengthOfLIS(self, nums):
            """
            :type nums: List[int]
            :rtype: int
            """
            # hashmap key:the max subsequence before this number /  value:list of the nums with this step read before
            # if this number bigger than anyone number with the max steps of subsequence, it will add one key +1 to the hashmap
            # for example: [10, 9, 2, 5, 3, 7, 101, 18]
            # when it comes to 7, hashmap before: {1: [10, 9, 2], 2: [5, 3]} | hashmap after: {1: [10, 9, 2], 2: [5, 3], 3: [7]}
            l = len(nums)
            if l == 0:
                return 0
            hash = {1:[]}
            bigkey = 1
            for i in range(l):
                print hash
                key = bigkey
                while(key>=1):
                    if len(list(filter(lambda x:x<nums[i],hash[key]))) >0:
                        key = key +1
                        if key>bigkey:  bigkey = key
                        if key in hash:
                            hash[key].append(nums[i])
                        else:
                            hash[key] = [nums[i]]
                        break
                    else:
                        key = key-1
                if key == 0:
                    hash[1].append(nums[i])
            return bigkey
    

    And an example running result is attached:
    Your input

    [10,9,2,5,3,7,101,18]

    Your stdout

    {1: []}
    {1: [10]}
    {1: [10, 9]}
    {1: [10, 9, 2]}
    {1: [10, 9, 2], 2: [5]}
    {1: [10, 9, 2], 2: [5, 3]}
    {1: [10, 9, 2], 2: [5, 3], 3: [7]}
    {1: [10, 9, 2], 2: [5, 3], 3: [7], 4: [101]}


Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.