LeetCode #242 #538 #796 #349 #350 2018-09-10

242. Valid Anagram

https://leetcode.com/problems/valid-anagram/description/

遍历字符串s，同时建立一个字典保存s中所有字符及其数量。再遍历字符串t，字典中有的字符数量减一，没有直接return False. 最后判断字典的values是否都为0即可。
代码如下：

class Solution:
    def isAnagram(self, s, t):
        """
        :type s: str
        :type t: str
        :rtype: bool
        """
        char_dict = {}
        for char in s:
            if char in char_dict:
                char_dict[char] += 1
            else:
                char_dict[char] = 1
        for char in t:
            if char in char_dict:
                char_dict[char] -= 1
            else:
                return False
        return not any(char_dict.values())

538. Convert BST to Greater Tree

https://leetcode.com/problems/convert-bst-to-greater-tree/description/

就是一个变形的中序遍历，当遍历完右子树后，把右子树的和加到当前root的值上继续遍历左子树即可。
代码如下：

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

class Solution:
    value = 0
    def convertBST(self, root):
        """
        :type root: TreeNode
        :rtype: TreeNode
        """
        if not root:
            return None
        self.convertBST(root.right)
        root.val, self.value = root.val + self.value, root.val + self.value
        self.convertBST(root.left)
        return root

796. Rotate String

https://leetcode.com/problems/rotate-string/description/

We can easily see whether it is rotated if B can be found in (A + A).
For example, with A = "abcde", B = "cdeab", we have:
“abcdeabcde” (A + A)
“cdeab” (B)
B is found in (A + A), so B is a rotated string of A.
代码如下：

class Solution:
    def rotateString(self, A, B):
        """
        :type A: str
        :type B: str
        :rtype: bool
        """
        return len(A) == len(B) and B in A + A

349. Intersection of Two Arrays

https://leetcode.com/problems/intersection-of-two-arrays/description/

Python取交集很简单，直接把两个list变成set，利用set特性自动取交集再转换成list即可。
代码如下：

class Solution:
    def intersection(self, nums1, nums2):
        """
        :type nums1: List[int]
        :type nums2: List[int]
        :rtype: List[int]
        """
        return list(set(nums1) & set(nums2))

350. Intersection of Two Arrays II

https://leetcode.com/problems/intersection-of-two-arrays-ii/description/

巧妙利用了Counter类的性质和方法解题。
Counter可以统计出两个list中所包含的数字及出现的次数，还支持类似set的取交集操作，所以可以轻松求出两个list中元素的交集。
同时Counter的elements方法返回一个迭代器。元素被重复了多少次，在该迭代器中就包含多少个该元素。元素排列无确定顺序，个数小于1的元素不被包含。正好符合我们的要求，直接转换成list即可。
代码如下：

class Solution:
    def intersect(self, nums1, nums2):
        """
        :type nums1: List[int]
        :type nums2: List[int]
        :rtype: List[int]
        """
        from collections import Counter
        a = Counter(nums1)
        b = Counter(nums2)
        return list((a & b).elements())