4.0万

11个月前
class Solution(object):
def isNumber(self, s):
"""
:type s: str
:rtype: bool
"""
s = s.strip()
if not s: return False
dot = False
hasE = False
sign = False
for i in range(len(s)):
if s[i] == ".":
if dot: return False
elif hasE: return False
elif len(s) == 1: return False
elif i and  s[i-1] in ["+", "-"] and i == len(s) - 1: return False
dot = True
elif s[i] in [ "+", "-"]:
if sign:
if i and s[i-1] not in ["E", "e"]: return False
else:
if not hasE and i != 0: return False
sign = True
elif s[i] in ["E", "e"]:
if hasE or i == (len(s)-1) or i == 0: return False
if i and not s[i-1].isdigit():   return False
hasE = True
elif not s[i].isdigit():
return False
return True


11个月前
from collections import deque
class Solution(object):
def movingCount(self, threshold, rows, cols):
"""
:type threshold: int
:type rows: int
:type cols: int
:rtype: int
"""
if rows == cols == 0: return 0

def calc(x, y):
s = 0
while x:
s += x % 10
x /= 10
while y:
s += y % 10
y /= 10
return s
q = deque()
q.append((0, 0))
used = [[False for j in range(cols)] for i in range(rows)]
used[0][0] = True
res = 0
while q:
x, y = q.popleft()
res += 1
dx = [-1, 0, 1, 0]
dy = [0, 1, 0, -1]
for i in range(4):
new_x = x + dx[i]
new_y = y + dy[i]
if new_x < 0 or new_x >= rows or new_y < 0 or new_y >= cols or calc(new_x, new_y) > threshold or used[new_x][new_y] : continue
q.append((new_x, new_y))
used[new_x][new_y] = True
return res


11个月前
class Solution(object):
def isMatch(self, s, p):
"""
:type s: str
:type p: str
:rtype: bool
f[i][j]表示s的前i个是否与p的前j个匹配
f[i][j-1] and p[j] == "*": f[i][j] = True
f[i][j-2] and p[j]  == "*": f[i][j] = True
f[i-1][j-1] and s[i] == p[j]: f[i][j] = True
f[i-1][j-1] and  p[j] = . : f[i][j] = True
需要考虑s为空的情形
"""
n = len(s)
m = len(p)
f = [[False for j in range(m+1)] for i in range(n+1)]
f[0][0] = True

for i in range(0, n+1):
for j in range(1, m+1):
if p[j-1] == "*":
if f[i][j-1]: f[i][j] = True
if j >= 2 :
if f[i][j-2]: f[i][j] = True
if i >= 2 and  f[i-2][j-2] and (s[i-2] == p[j-2] or p[j-2] == '.'): f[i][j] = True
elif i > 0 and p[j-1] == s[i-1] and f[i-1][j-1] : f[i][j] = True
elif i > 0 and p[j-1] == "." and f[i-1][j-1]: f[i][j] = True
return f[n][m]


11个月前
class Solution(object):
def findMin(self, nums):
"""
:type nums: List[int]
:rtype: int
"""
if len(nums) == 0: return -1
if nums[len(nums) - 1]  > nums[0]: return nums[0]
i = len(nums) - 1
while i and nums[i] == nums[i-1]: i -= 1
l = 0
r = i - 1
while l < r:
mid = (l+r) >> 1
if nums[mid] < nums[r]: r = mid
else: l = mid + 1
return nums[l]


11个月前
class Solution(object):
def hasPath(self, matrix, string):
"""
:type matrix: List[List[str]]
:type string: str
:rtype: bool
"""
if not matrix: return False
if not string: return False
n = len(matrix)
m = len(matrix[0])

def dfs(x, y, cur,s):
if cur == len(string) :
return True
dx = [-1, 0, 1, 0]
dy = [0, 1, 0, -1]
for i in range(4):
new_x = x + dx[i]
new_y = y + dy[i]
if new_x < 0 or new_x >=n or new_y < 0 or new_y >= m  or used[new_x][new_y]: continue
if matrix[new_x][new_y] == string[cur]:
used[new_x][new_y] = True
if dfs(new_x, new_y, cur + 1, s+string[cur]): return True
used[new_x][new_y] = False
return False

for i in range(n):
for j in range(m):
if matrix[i][j] == string[0]:
used = [[False for a in range(m)] for b in range(n)]
used[i][j] = True
rs = dfs(i, j, 1, string[0])
if rs: return True
return False


11个月前
class Solution(object):
def convert(self, root):
"""
:type root: TreeNode
:rtype: TreeNode
"""
if not root: return None
self.pre = TreeNode(-1)
dummy = self.pre
def dfs(root):
if not root:
return None
dfs(root.left)
self.pre.right = root
root.left = self.pre
self.pre = root
dfs(root.right)
dfs(root)
dummy.right.left = None
return dummy.right


11个月前
import heapq
class Solution:
def __init__(self):
self.max_stack = []
self.min_stack = []

def insert(self, num):
"""
:type num: int
:rtype: void
"""
heapq.heappush(self.min_stack, num)
if len(self.min_stack) > len(self.max_stack) + 1:
e = heapq.heappop(self.min_stack)
heapq.heappush(self.max_stack, -e)
elif self.min_stack and self.max_stack:
emax = - self.max_stack[0]
emin = self.min_stack[0]
if emin < emax:
heapq.heappop(self.min_stack)
heapq.heappop(self.max_stack)
heapq.heappush(self.max_stack, -emin)
heapq.heappush(self.min_stack, emax)

def getMedian(self):
"""
:rtype: float
"""
if (len(self.min_stack) + len(self.max_stack)) & 1:
return self.min_stack[0]
return (self.min_stack[0] - self.max_stack[0]) / 2.0


11个月前
class Solution:

def serialize(self, root):
"""Encodes a tree to a single string.

:type root: TreeNode
:rtype: str
"""
def dfs(root):
return ["#"] if not root else [str(root.val)] + dfs(root.left) + dfs(root.right)
res = " ".join(dfs(root))
return res

def deserialize(self, data):
"""Decodes your encoded data to tree.

:type data: str
:rtype: TreeNode
"""
if not data : return None
rs = iter(data.split())
def dfs():
val = next(rs)
if val == "#": return None
root = TreeNode(val)
root.left = dfs()
root.right = dfs()
return root
return dfs()


11个月前
class Solution(object):
def inversePairs(self, nums):
"""
:type nums: List[int]
:rtype: int
"""
self. res = 0

def merge(nums1, nums2):
c = []
i = j = 0
while (i < len(nums1) or j < len(nums2)):
if i == len(nums1):
c.append(nums2[j])
j += 1
continue
if j == len(nums2):
c.append(nums1[i])
i += 1
continue
if nums1[i]<=nums2[j]:
c.append(nums1[i])
i+=1
else:
c.append(nums2[j])
self.res +=  (len(nums1) -i)
j += 1
return c
def gbpx(nums):
if len(nums) <= 1: return nums
l = 0
r = len(nums) - 1
mid = (l+r) >> 1
nums1 = gbpx(nums[0:mid+1])
nums2 = gbpx(nums[mid+1:])
return merge(nums1, nums2)
gbpx(nums)
return self.res


11个月前
class Solution:
def getTranslationCount(self, s):
"""
:type s: str
:rtype: int
"""
fy = dict()
for i in range(26):
fy[str(i)] = chr(ord('a') + i)
self. res = 0
def dfs(s, rs):
if s == "":
self.res += 1
return
if len(s)  > 2:
if s[:2] in fy:
dfs(s[2:], rs + fy[s[:2]])
dfs(s[1:], rs + fy[s[0]])
dfs(s, "")
return self.res