leetcode刷题记录（六）

class Solution(object):
    def partitionLabels(self, S):
        “””
        :type S: str
        :rtype: List[int]
        “””
        size = []
        while S:
            I = 1
            while set(S[I:])&set(S[:I]):
                I+=1
            size.append(i)
            S=S[I:]
        return size

def numberOfLines(self, widths, S):
        “””
        :type widths: List[int]
        :type S: str
        :rtype: List[int]
        “””
        res, cur = 1, 0
        for I in S:
            width = widths[ord(i) - ord(‘a’)]
            res += 1 if cur + width > 100 else 0
            cur = width if cur +width > 100 else cur + width
        return [res, cur]

def complexNumberMultiply(self, a, b):
        “””
        :type a: str
        :type b: str
        :rtype: str
        “””
        a, ai, b, bi = map(int, re.findall(‘-?d+’, a+b))
        return ‘%d+%di’ % (a*b - ai*bi, a*bi + ai*b)

def countBattleships(self, board):
        “””
        :type board: List[List[str]]
        :rtype: int
        “””
        total = 0
        for I in range(len(board)):
            for j in range(len(board[0])):
                if board[I][j] == ‘X’:
                    flag = 1
                    if j>0 and board[I][j-1] == ‘X’:
                        flag = 0
                    if I>0 and board[i-1][j] == ‘X’:
                        flag = 0
                    total += flag
        return total

### def shortestToChar(self, S, C):
###         “””
###         :type S: str
###         :type C: str
###         :rtype: List[int]
###         “””
###         return [min(abs(I - j) for j, e in enumerate(S) if e == C) for I in range(len(S))]

def getMinimumDifference(self, root):
        “””
        :type root: TreeNode
        :rtype: int
        “””
        def dsf(node, l = []):
            if node.left: dsf(node.left, l)
            l.append(node.val)
            if node.right: dsf(node.right, l)
            return l
        
        l = [1,2,3,4,5]
        return zip(l,l[1:])

    def trimBST(self, root, L, R):
        “””
        :type root: TreeNode
        :type L: int
        :type R: int
        :rtype: TreeNode
        “””
        if not root:
            return None
        if L > root.val:
            return self.trimBST(root.right, L, R)
        elif R < root.val:
            return self.trimBST(root.left, L, R)
        root.left = self.trimBST(root.left, L, R)
        root.right = self.trimBST(root.right, L, R)
        return root

def findBottomLeftValue(self, root):
        “””
        :type root: TreeNode
        :rtype: int
        “””
        q = [root]
        for node in q:
            q+=filter(None, (node.right, node.left))
        return q

def dfs(node, depth = 0):
            if node:
                if len(info) <= depth:
                    info.append([0,0])
                info[depth][0] += node.val
                info[depth][1] += 1
                dfs(node.left, depth + 1)
                dfs(node.right, depth + 1)
        dfs(root)
        return [s/float(c) for s,c in info]