Leet Code Python版本持续更新

客官°小女子只卖身不卖艺 2022-04-12 10:46 214阅读 0赞

为什么写这篇博客呢，主要是督促自己能够一直走下去，而不是做一两道题就停止了而已，哈哈。。

1.  Two\_sum  
    此题核心是利用了map key的不重复性方便了查找，比较简单，不在多说

#!/usr/bin/python3
    
    import numpy as np
    
    """
    1. Two Sum
    Given an array of integers, return indices of the two numbers such that they add up to a specific target.
    You may assume that each input would have exactly one solution, and you may not use the same element twice.
    Example:
    Given nums = [2, 7, 11, 15], target = 9,
    Because nums[0] + nums[1] = 2 + 7 = 9,
    return [0, 1].
    """
    class Solution:
    
        A = None
    
        def __init__(self, a):
            self.A = a
    
        def two_sum(self, nums, target):
            dict_result = {}
            dict_map = {}
            for i in range(len(nums)):
                dict_map[nums[i]] = i
            for i in range(len(nums)):
                t = target - nums[i]
                if (t in dict_map) and (t != i):
                    dict_result[i]=i
                    dict_result[dict_map[t]] = dict_map[t]
                    return dict_result
    
    
    solution = Solution([1, 4, 2, 5, 3, 7, 9, 0])
    print(solution.A)
    print(solution.two_sum(solution.A,10))
    np.random

1.  add\_two\_numbers  
    此题是将两个数字序列存于链表中，按从左边开始个数十位顺序存储，求它们相加之后的结果，依然返回一个链表

这个题有两点需要注意：第一点是头节点最好指定一个特殊值-1啥的 ；第二个是满x进制y, 另外最后可能有一位，循环结束后还需要判断是否为1，再往后面插入一个值为1的节点

#!/usr/bin/python3
    
    """
    You are given two non-empty linked lists representing two non-negative integers. The digits are stored in reverse order
    and each of their nodes contain a single digit. Add the two numbers and return it as a linked list.
    You may assume the two numbers do not contain any leading zero, except the number 0 itself.
    
    Input: (2 -> 4 -> 3) + (5 -> 6 -> 4) 即 342+465 = 807 ，都是反序列保存
    Output: 7 -> 0 -> 8
    """
    
    
    class ListNode:
        '''
        定义链表节点对象 val 值 、next下一个节点地址
        '''
        def __init__(self, x):
            self.val = x
            self.next = None
    
    
    class Solution:
        '''
        参数为两个链表保存的数字
        返回相加后的链表
        '''
        def add_two_numbers(self, l1, l2):
    
            if l1 is None:
                return l2
            if l2 is None:
                return l1
            # 初始化第一个头结点
            head_node = ListNode(-1)
            # cur 当前计算节点
            cur = head_node
            # 进位值 满10为1
            carry = 0
            # 从两个链表前端依次取值相加，没有值则为0
            while (l1 is not None) or (l2 is not None):
    
                d1 = 0 if (l1 is None) else l1.val
                d2 = 0 if (2 is None) else l2.val
                # 关键是设置进制数默认为0
                two_sum = d1 + d2 + carry
                carry = 1 if (two_sum >= 10) else 0
                cur.next = ListNode(two_sum % 10)
                cur = cur.next
                if l1 is not None:
                    l1 = l1.next
                if l2 is not None:
                    l2 = l2.next
            # 最后一位如果还能进位，则为1
            if carry == 1:
                cur.next = ListNode(1)
            # 返回结果的第一个个数链表节点
            return head_node.next
    
    
    solution = Solution()
    l1 = ListNode(3)
    l1.next = ListNode(6)
    l2 = ListNode(5)
    l2.next = ListNode(4)
    l3 = solution.add_two_numbers(l1,l2)
    while l3 is not None:
        print(l3.val)
        l3 = l3.next

1.  longest\_substring\_without\_repeating\_characters  
    求给定字符串中 最长字串的长度并返回最大长度，没要求返回最大串，也是可以返回的  
    此题关键点 利用hashset 元素不重复的特性，从左逐渐取出来字符，放到hashset中并每次保存最大长度值，遇到重复时将会清空hashset，从重复位置开始新一轮放置元素到hashset中，如此一直遍历完字符串。

#!/usr/bin/python3
    
    """
    Given a string, find the length of the longest substring without repeating characters.
    
    Examples:
    Given "abcabcbb", the answer is "abc", which the length is 3.
    Given "bbbbb", the answer is "b", with the length of 1.
    Given "pwwkew", the answer is "wke", with the length of 3. Note that the answer must be a substring, "pwke" is a subsequence and not a substring.
    """
    
    class Solution:
        '''
        查找字符串中最长子序列并返回其长度，不需要返回子序列
        '''
        def length_of_longest_substring(self, s):
            # 临时变量记录最大长度
            res = 0
            left = 0
            # 当前遍历的字符串索引
            right = 0
            hash_set = set()
            while right < len(s):
                # 如果当前字符不在hash_set中，则添加，如果存在则把hash_set元素清空
                if s[right] not in hash_set:
                    hash_set.add(s[right])
                    res = max(res,len(hash_set))
                    right += 1
                else:
                    # hash_set.clear() 感觉这句话和下面的完成事情一样
                    hash_set.remove(s[left])
                    left += 1
            return res
    
    
    solution = Solution()
    print(solution.length_of_longest_substring('pwwkew'))

1.  reverse integer  
    解题思路是需要知道如何取一个整数的个数数字，与10取模即可，取出来之后每次乘以10，即向左进位，然后再加上下一个取出来的数字，循环一遍即可。  
    需要注意的是python没有明确类型，因此除以10后为小数，需要int(n)函数取整。

#!/usr/bin/python3
    
    
    import sys
    
    """
    You are given two non-empty linked lists representing two non-negative integers. The digits are stored in reverse order
    and each of their nodes contain a single digit. Add the two numbers and return it as a linked list.
    You may assume the two numbers do not contain any leading zero, except the number 0 itself.
    
    Input: (2 -> 4 -> 3) + (5 -> 6 -> 4)
    Output: 7 -> 0 -> 8
    """
    
    
    class Solution:
        '''
         输出一个整数的反序列
        '''
        def reverse_integer(self, x):
            # 是否为负数标识
            positive = True
            if x < 0:
                positive = False
                x = abs(x)
            res = 0
            while x != 0:
                # 每次对各位数字取整
                print('x % 10=', x % 10)
                # 取出来后提升一位进制
                print('10 * res=', 10 * res)
                res = 10 * res + x % 10
                # 取整去除小数点后面值
                x = int(x/10)
            if res > sys.maxsize:
                return 0
            if not positive:
                return -1*res
    
    
    solution = Solution()
    print(solution.reverse_integer(-1234))

1.  14.longest\_common\_prefix  
    求多个字符串的最长公共前缀串，解决这一问题比较简单，让m个字符串左边对齐，依次向右比较（纵向）即可，如果遇到不一样的或有比较完的字符串则停止比较。如下代码：

"""
    Write a function to find the longest common prefix string amongst an array of strings.
    """
    
    class Solution:
        '''
         查找多个字符串的最长公共前缀
        '''
        def longest_common_prefix(self, strs):
            # 如果为空则返回
            if strs is None or len(strs) == 0:
                return "";
    
            res = ""
            # 取出来第一个字符串遍历
            for i in range(len(strs[0])):
                # 依次取出来字符
                c = strs[0][i]
                # 取出来的字符同其他字符串相同位置比较即纵向比较
                for j in range(len(strs)):
                    if i > len(strs[j]) or c != strs[j][i]:
                        return res
                # 与其它字符串相等则增加
                res += c
            return res
    
    solution = Solution()
    print(solution.longest_common_prefix(["nihaoma","nihao","nihma","nih"]))

1.  20.valid\_arentheses  
    该题是为了验证成对出现的括号，在一个字符串中如果成对出现则字符串是对的，如果有单着的括号则返回False

解题技巧在于这种括号对称性利用栈数据结构，栈是后进先出，例如字符"\{(\[\])\}"，第一个字符"\{“先进栈，依次“（”、“\[” ，这时“”\[”在栈顶，让栈顶元素和第四个字符”\]"比较即可，如果相等说明对称，不想当说明部队称返回false,这样遍历一遍字符串即可。

我们要熟练掌握每种数据结构特性解决实际问题才会方便，代码如下：

"""
    Given a string containing just the characters \'(\', \')\', \'{\', \'}\', \'[\' and \']\', determine if the input string is valid.
    The brackets must close in the correct order, "()" and "()[]{}" are all valid but "(]" and "([)]" are not.
    
    """
    
    class Stack:
        """模拟栈"""
    
        def __init__(self):
            self.items = []
    
        def isEmpty(self):
            return len(self.items) == 0
    
        def push(self, item):
            self.items.append(item)
    
        def pop(self):
            return self.items.pop()
    
        def peek(self):
            if not self.isEmpty():
                return self.items[len(self.items) - 1]
    
        def size(self):
            return len(self.items)
    
    
    class Solution:
        '''
         判断一个字符串包含的括号是否成对
        '''
        def is_valid(self, str):
            parentheses = Stack()
            # 遍歷字符串
            for i in range(len(str)):
                # 遇到左边括号则推送到栈里
                if str[i] == '[' or str[i] == '{' or str[i] == '(':
                    parentheses.push(str[i])
                else:
                    # 如果遇到右边括号则和栈顶元素比较（利用了每个括号对称出现特性）
                    if parentheses.isEmpty():
                        return False
                    if str[i] == ')' and parentheses.peek() != '(':
                        return False
                    if str[i] == ']' and parentheses.peek() != '[':
                        return False
                    if str[i] == '}' and parentheses.peek() != '{':
                        return False
                    parentheses.pop()
            return parentheses.isEmpty()
    solution = Solution()
    print(solution.is_valid("[([)]"))