Leetcode刷题第一周汇总

小鸡
阅读910 喜欢3 算法 更新2019-4-20

这两天刷了十几道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