Leetcode刷题第一周汇总

这两天刷了十几道Leetcode的算法题，还是做算法有趣，现在对这周做的源码进行汇总。
算法都比较笨，大佬们见笑了

¶Definition for singly-linked list.

# Definition for singly-linked list.
# 给出两个 非空 的链表用来表示两个非负的整数。
#  其中，它们各自的位数是按照 逆序 的方式存储的，并且它们的每个节点只能存储 一位 数字。
# 如果，我们将这两个数相加起来，则会返回一个新的链表来表示它们的和。
# 您可以假设除了数字 0 之外，这两个数都不会以 0 开头。
class ListNode:
    def __init__(self, x):
        self.val = x
        self.next = None

class Solution:
    def addTwoNumbers(self, l1: ListNode, l2: ListNode) -> ListNode:
        tmp = 0
        s1 = l1
        s2 = l2
        s3 = ListNode(0)
        ss = s3
        while s1 != None and s2 != None:
            n = int((s1.val + s2.val + tmp) % 10)
            tmp = int((s1.val + s2.val + tmp - n) / 10)
            node = ListNode(n)
            ss.next = node
            ss = node
            s1 = s1.next
            s2 = s2.next
        s = None
        if s1 !=None:
            s = s1
        if s2 != None:
            s = s2
        while s != None:
            n = int((s.val + tmp) % 10)
            tmp = int((s.val + tmp - n) / 10)
            node = ListNode(n)
            ss.next = node
            ss = node
            s = s.next
        if tmp >= 1:
            node = ListNode(tmp)
            ss.next = node
            ss = node
        return s3.next

¶two sum

给定一个整数数组 nums 和一个目标值 target，请你在该数组中找出和为目标值的那两个整数，并返回他们的数组下标。
你可以假设每种输入只会对应一个答案。但是，你不能重复利用这个数组中同样的元素。

示例:

给定 nums = [2, 7, 11, 15], target = 9
因为 nums[0] + nums[1] = 2 + 7 = 9
所以返回 [0, 1]

class Solution:
    def twoSum(self, nums, target: int):
        lens = len(nums)
        for i in range(lens):
            if target-nums[i] in nums[i+1:]:
                return [i,nums[i+1:].index(target-nums[i])+i+1]
    def twoSum2(self, nums, target: int):
        maps = {}
        for i in nums:
            maps[i] = 1
        for j in nums:
            if target-j in maps:
                f = nums.index(j)
                if target-j in nums[f+1:]:
                    l = nums[f+1:].index(target-j) + f + 1
                    return [f, l]

¶最短回文串

# 给定一个字符串 s，你可以通过在字符串前面添加字符将其转换为回文串。
# 找到并返回可以用这种方式转换的最短回文串。
# 示例 1:
# 输入: "aacecaaa"
# 输出: "aaacecaaa"
# 示例 2:
# 输入: "abcd"
# 输出: "dcbabcd"

class Solution:
    def shortestPalindrome(self, s: str) -> str:
        if s == "":
            return ""
        le = len(s)
        rs = s[::-1]
        for i in range(le):
            if s[:le-i] == rs[i:]:
                break
        return rs[:i] + s

¶最大面积

给定 n 个非负整数 a1，a2，…，an，每个数代表坐标中的一个点 (i, ai) 。
在坐标内画 n 条垂直线，垂直线 i 的两个端点分别为 (i, ai) 和 (i, 0)。
找出其中的两条线，使得它们与 x 轴共同构成的容器可以容纳最多的水。

说明：你不能倾斜容器，且 n 的值至少为 2。

执行用时 : 80 ms, 在Container With Most Water的Python3提交中击败了80.05% 的用户
内存消耗 : 14.4 MB, 在Container With Most Water的Python3提交中击败了65.81% 的用户


class Solution:
    def maxArea(self, height) -> int:
        h = 0
        maxa = 0
        le = len(height)
        hh = height[::-1]
        for i in range(le):
            if height[i] > h:
                for j in range(le - i):
                    if hh[j] >= height[i]:
                        if (le - j - i - 1) * height[i] > maxa:
                            maxa = (le - j - i - 1) * height[i]
                        break
                    elif (le - j - i -1) * hh[j] > maxa:
                        maxa = (le - j - i - 1) * hh[j]
                h = height[i]
        return maxa

¶正则表达式匹配

给定一个字符串 (s) 和一个字符模式 §。实现支持 ‘.’ 和 ‘*’ 的正则表达式匹配。

‘.’ 匹配任意单个字符。
’*’ 匹配零个或多个前面的元素。
匹配应该覆盖整个字符串 (s) ，而不是部分字符串。

说明:

s 可能为空，且只包含从 a-z 的小写字母。
p 可能为空，且只包含从 a-z 的小写字母，以及字符 . 和 *。

执行用时 : 76 ms, 在Regular Expression Matching的Python3提交中击败了93.59% 的用户
内存消耗 : 13.2 MB, 在Regular Expression Matching的Python3提交中击败了58.15% 的用户

class Solution:
    def __init__(self):
        self.arr = []
    def isMatch(self, s: str, p: str) -> bool:
        self.arr = [[-1 for i in range(len(p)+1)] for j in range(len(s)+1)]
        return self.match(s, p ,0 , 0)
    def match(self, s: str, p: str, i: int, j: int) -> bool:
        if self.arr[i][j] != -1:
            return self.arr[i][j]
        pp ,ss = p[j:], s[i:]
        lp, ls = len(pp), len(ss)
        if lp <= 0:
            return ls <= 0
        if ls <= 0:
            try:
                self.arr[i][j] = lp <= 0 or pp[1] == * and lp >= 2 and self.match(s, p, i , j+2)
                return self.arr[i][j]
            except:
                self.arr[i][j] = False
                return False
        match = (ls > 0 and ss[0] == pp[0]) or pp[0] == .
        if lp > 1 and pp[1] == *:
            self.arr[i][j] = self.match(s, p, i, j+2) or (match and self.match(s, p, i+1, j))
            return self.arr[i][j]
        else:
            if match:
                self.arr[i][j] = self.match(s, p, i+1, j+1)
                return self.arr[i][j]
            self.arr[i][j] = False
            return False

¶回文数

判断一个整数是否是回文数。回文数是指正序（从左向右）和倒序（从右向左）读都是一样的整数。

示例 1:

输入: 121
输出: true
示例 2:

输入: -121
输出: false
解释: 从左向右读, 为 -121 。从右向左读, 为 121- 。因此它不是一个回文数。
示例 3:

输入: 10
输出: false
解释: 从右向左读, 为 01 。因此它不是一个回文数。

emmmmm一行代码解决，没想到效率还不错

执行用时 : 104 ms, 在Palindrome Number的Python3提交中击败了99.58% 的用户
内存消耗 : 13.2 MB, 在Palindrome Number的Python3提交中击败了82.83% 的用户

class Solution:
    def isPalindrome(self, x: int) -> bool:
        return str(x)[::-1] == str(x)

¶字符提取数字

请你来实现一个 atoi 函数，使其能将字符串转换成整数。
首先，该函数会根据需要丢弃无用的开头空格字符，直到寻找到第一个非空格的字符为止。
当我们寻找到的第一个非空字符为正或者负号时，则将该符号与之后面尽可能多的连续数字组合起来，作为该整数的正负号；假如第一个非空字符是数字，则直接将其与之后连续的数字字符组合起来，形成整数。
该字符串除了有效的整数部分之后也可能会存在多余的字符，这些字符可以被忽略，它们对于函数不应该造成影响。
注意：假如该字符串中的第一个非空格字符不是一个有效整数字符、字符串为空或字符串仅包含空白字符时，则你的函数不需要进行转换。
在任何情况下，若函数不能进行有效的转换时，请返回 0。

说明：
假设我们的环境只能存储 32 位大小的有符号整数，那么其数值范围为 [−231, 231 − 1]。如果数值超过这个范围，qing返回 INT_MAX (231 − 1) 或 INT_MIN (−231) 。

示例 1:
输入: " -42"
输出: -42
解释: 第一个非空白字符为 ‘-’, 它是一个负号。
我们尽可能将负号与后面所有连续出现的数字组合起来，最后得到 -42 。

示例 3:
输入: "4193 with words"
输出: 4193
解释: 转换截止于数字 ‘3’ ，因为它的下一个字符不为数字。

示例 4:
输入: "words and 987"
输出: 0
解释: 第一个非空字符是 ‘w’, 但它不是数字或正、负号。
因此无法执行有效的转换。

示例 5:
输入: "-91283472332"
输出: -2147483648
解释: 数字 “-91283472332” 超过 32 位有符号整数范围。
因此返回 INT_MIN (−231) 。

执行用时 : 64 ms, 在String to Integer (atoi)的Python3提交中击败了88.66% 的用户
内存消耗 : 13.1 MB, 在String to Integer (atoi)的Python3提交中击败了94.70% 的用户


class Solution:
    def myAtoi(self, s: str) -> int:
        try:
            s = s.split()[0]
            t = ""
            if s[0] == -:
                t = -
                s = s[1:]
            if s[0] == + and t == "":
                s = s[1:]
            out = 0
            for i in range(len(s)):
                try:
                    out = int(t+s[:i+1])
                except:
                    break

            if out < -2147483648:
                out = -2147483648
            elif  out > 2147483647:
                out = 2147483647
            return out
        except:
            return 0

¶反转数

给出一个 32 位的有符号整数，你需要将这个整数中每位上的数字进行反转。

示例 1:
输入: 123
输出: 321

示例 2:
输入: -123
输出: -321

示例 3:
输入: 120
输出: 21

注意:
假设我们的环境只能存储得下 32 位的有符号整数，则其数值范围为 [−2^31, 2^31 − 1]。
请根据这个假设，如果反转后整数溢出那么就返回 0。

执行用时 : 56 ms, 在Reverse Integer的Python3提交中击败了98.64% 的用户
内存消耗 : 13.3 MB, 在Reverse Integer的Python3提交中击败了48.60% 的用户

class Solution:
    def reverse(self, x: int) -> int:
        s = str(x)
        flag = ""
        if s[0] == -:
            flag = s[0]
            s = s[1:]
        ls = int(flag + s[::-1])
        if ls < -2147483648 or ls >2147483647:
            ls = 0
        return ls

¶Z字形排列

# 将一个给定字符串根据给定的行数，以从上往下、从左到右进行 Z 字形排列。

# 比如输入字符串为 "LEETCODEISHIRING" 行数为 3 时，排列如下：

# L   C   I   R
# E T O E S I I G
# E   D   H   N
# 之后，你的输出需要从左往右逐行读取，产生出一个新的字符串
# 比如："LCIRETOESIIGEDHN"。

class Solution:
    def convert(self, s: str, numRows: int) -> str:
        if numRows == 1:
            return s
        rel = ""
        step = numRows * 2 - 2
        le = len(s)
        for i in range(numRows):
            f = i
            while f < le:
                rel += s[f]
                f += step
                mid = f-i*2
                if i != numRows - 1 and i != 0 and mid < le:
                    rel += s[mid]
        return rel