头像

福如东海


访客:17407

离线:3小时前



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



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



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]



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]


活动打卡代码 AcWing 23. 矩阵中的路径

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



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



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


活动打卡代码 AcWing 50. 序列化二叉树

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()



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



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