第一题Can Place Flowers

给定一个01数组代表一排花盆，0代表是可以种花，1代表不可以。种花的时候我们要确保左右两边的花盆是空的。问能不能种n株花。

简单的贪心。

class Solution(object):
    def canPlaceFlowers(self, flowerbed, n):
        """
        :type flowerbed: List[int]
        :type n: int
        :rtype: bool
        """
        cnt = 0
        for i in xrange(len(flowerbed)):
            if flowerbed[i] == 1:
                continue
            if i-1>=0 and flowerbed[i-1]==1:
                continue
            if i+1<len(flowerbed) and flowerbed[i+1]==1:
                continue
            flowerbed[i] = 1
            cnt += 1
        return cnt>=n

第二题Construct String from Binary Tree

将一颗二叉树按照前序遍历的格式转化成字符串。

直接DFS。

# Definition for a binary tree node.
# class TreeNode(object):
#     def __init__(self, x):
#         self.val = x
#         self.left = None
#         self.right = None

class Solution(object):
    def tree2str(self, t):
        """
        :type t: TreeNode
        :rtype: str
        """
        if not t:
            return ''
        left = self.tree2str(t.left)
        right = self.tree2str(t.right)
        if left and right:
            return '{}({})({})'.format(t.val, left, right)
        if left:
            return '{}({})'.format(t.val, left)
        if right:
            return '{}()({})'.format(t.val, right)
        return '{}'.format(t.val)

第三题Find Duplicate File in System

题目比较长，请去leetcode看详细描述。大意是给定一个文件系统（路径以及文件的内容），将重复出现的文件（按内容）分组返回。

关键是建立一个内容：路径的哈希表。

class Solution(object):
    def findDuplicate(self, paths):
        """
        :type paths: List[str]
        :rtype: List[List[str]]
        """
        files = {}
        for path in paths:
            fs = path.split(' ')
            for name in fs[1:]:
                p = name.find('(')
                fn = name[:p]
                c = name[p+1:-1]
                if c not in files:
                    files[c] = []
                files[c].append('{}/{}'.format(fs[0], fn))
        ans = []
        for v in files.values():
            if len(v) >= 2:
                ans.append(v)
        return ans

第四题Tag Validator

题目很长，请去leetcode看详细描述。大意是判断一段类似html的代码是否正确。

其实不难，不过倒是挺繁琐的。首先是处理cdata，然后用一个栈来配对标签。

class Solution(object):
    def isValid(self, code):
        """
        :type code: str
        :rtype: bool
        """
        if not self.is_enclosed(code):
            return False
        try:
            code = self.remove_cdata(code)
        except:
            return False
        tags = []
        b = code.find('<')
        while b!=-1:
            e = b+1
            while e<len(code) and code[e]!='>':
                e += 1
            if e==len(code):
                return False
            tag = code[b+1:e]
            if len(tag)==0 or tag=='/':
                return False
            if tag[0]!='/':
                if len(tag) > 9 or not all('A'<=c<='Z' for c in tag):
                    return False
                tags.append(tag)
            else:
                tag = tag[1:]
                if len(tag) > 9 or not all('A'<=c<='Z' for c in tag):
                    return False
                if not tags or tags[-1]!=tag:
                    return False
                tags.pop()
            b = code.find('<', e+1)
        return not tags

    def is_enclosed(self, code):
        if not code or code[0] != '<':
            return False
        e = code.find('>')
        if e==-1:
            return False
        tag = code[1:e]
        if len(tag) < 1 or len(tag) > 9 or not all('A'<=c<='Z' for c in tag):
            return False
        return code.endswith('</{}>'.format(tag))

    def remove_cdata(self, code):
        b = code.find('<![CDATA[')
        while b!=-1:
            e = code.find(']]>', b)
            if e==-1:
                raise 'error'
            code = code[:b]+code[e+3:]
            b = code.find('<![CDATA[')
        return code
leetcode contest