2018 June 26

leetcode 1-10

为熟悉python，这里选择用它来写LeetCode上的题目练手，在能通过的前提下尽可能地让代码简单清晰。

1.两数之和

给定一个整数数组和一个目标值，找出数组中和为目标值的两个数，输入保证有唯一解。

class Solution:
    def twoSum(self, nums, target):
        """
        :type nums: List[int]
        :type target: int
        :rtype: List[int]
        """
        ans = []
        a = {}
        for i in range(len(nums)):
            k = target - nums[i]
            if k in a:
                ans.extend([a[k], i])
                break
            a[nums[i]] = i
        return ans

2.两数相加

给定两个非空链表来表示两个非负整数，位数按照逆序方式存储，每个节点存一位数字，将两数相加并按该表式法返回结果。注意，数字没有前导0。

# Definition for singly-linked list.
# class ListNode:
#     def __init__(self, x):
#         self.val = x
#         self.next = None

class Solution:
    def addTwoNumbers(self, l1, l2):
        """
        :type l1: ListNode
        :type l2: ListNode
        :rtype: ListNode
        """
        c = 0
        ans = []
        while l1 or l2:
            if l1:
                c += l1.val
                l1 = l1.next
            if l2:
                c += l2.val
                l2 = l2.next
            ans.append(t % 10)
            c = c // 10
        if c: ans.append(c)
        node = None
        for i in ans[::-1]:
            t = ListNode(i)
            t.next = node
            node = t
        return node

3.无重复字符的最长子串

给定一个字符串，找出不含有重复字符的最长子串的长度。

class Solution:
    def lengthOfLongestSubstring(self, s):
        """
        :type s: str
        :rtype: int
        """
        d = {}
        i, j, k = 0, 0, 0
        while j < len(s):
            d[s[j]] = 1 + d.get(s[j], 0)
            while d[s[j]] > 1:
                d[s[i]] -= 1
                i += 1
            k = max(k, j-i+1)
            j += 1
        return k

4.两个排序数组的中位数

给定两个大小分别为m和n的有序数组nums1与nums2，求这两个有序数组合并后的中位数。

class Solution:
    def findMedianSortedArrays(self, nums1, nums2):
        """
        :type nums1: List[int]
        :type nums2: List[int]
        :rtype: float
        """
        nums = nums1 + nums2
        nums.sort()
        l = len(nums)
        return (nums[(l-1)//2] + nums[l//2]) / 2

5.最长回文子串

给定一个字符串s，找到s中任意一个最长的回文子串。

class Solution:
    def longestPalindrome(self, s):
        """
        :type s: str
        :rtype: str
        """
        S = '##'
        for i in s:
            S += i + '#'
        M, R, ans = 0, 0, 0
        p = [0] * len(S)
        for i in range(len(S)):
            if i < M:
                p[i] = max(p[2*M-i], R-i)
            else:
                p[i] = 1
            while i-p[i] >= 0 and i+p[i] < len(S) and S[i-p[i]] == S[i+p[i]]:
                p[i] += 1
            if R < i+p[i]:
                M = i
                R = i+p[i]
            if ans < p[i]-1:
                ans = p[i]-1
                z = i
        ret = ss[z-ans+1:z+ans].replace('#', '')
        return ret

6.Z字形变换

将字符串以Z字形排列成给定的行数，然后从左往右逐行读取字符得到新串，返回该新串。

class Solution:
    def convert(self, s, numRows):
        """
        :type s: str
        :type numRows: int
        :rtype: str
        """
        if numRows < 2: return s
        x, d = 0, 1
        t = [[] for i in range(numRows)]
        for i in s:
            t[x].append(i)
            x = x + d
            if x == numRows - 1:
                d = -1
            elif x == 0:
                d = 1
        ans = ''
        for i in t:
            ans += ''.join(i)
        return ans

7.反转整数

给定一个32位有符号整数，将数字进行反转，如反转后会溢出，则返回0。

class Solution:
    def reverse(self, x):
        """
        :type x: int
        :rtype: int
        """
        s = str(x)
        sign = ''
        if s[0] == '-':
            sign = '-'
            s = s[1:]
        ans = sign + s[::-1]
        ans = int(ans)
        if ans < -2**31 or ans > 2**31-1:
            ans = 0
        return ans

8.字符串转整数

实现类似atoi的功能，将字符串转为整数。要求：

class Solution:
    def myAtoi(self, str):
        """
        :type str: str
        :rtype: int
        """
        s = str.lstrip()
        sign = 0
        ans = 0
        for i, j in enumerate(s):
            if i == 0:
                if j == '-':
                    sign = -1
                elif j == '+':
                    sign = 1
                elif j.isdigit():
                    sign = 1
                    ans = int(j)
                else:
                    return 0
            else:
                if j.isdigit():
                    ans = ans * 10 + int(j)
                else:
                    break
        ans *= sign
        ans = min(ans, 2**31-1)
        ans = max(ans, -2**31)
        return ans

9.回文数

判断一个整数是否是回文数，即正序读和倒序读是一样的。

class Solution:
    def isPalindrome(self, x):
        """
        :type x: int
        :rtype: bool
        """
        s = str(x)
        return s == s[::-1]

10.正则表达式匹配

给定一个字符串s和一个字符模式p，实现支持点号和星号的正则表达式匹配。

class Solution:
    def isMatch(self, s, p):
        """
        :type s: str
        :type p: str
        :rtype: bool
        """
        p = '^' + p + '$'
        ok = re.match(p, s)
        return True if ok else False
Table of Contents