今晚吃得有点撑：排骨汤，花池鱼，红烧羊肉和炒青菜。

除了第一题WA了一次之外，其他三题都一次过了！

第一题K-diff Pairs in an Array。

题目大意：给定一个数组和一个数k，求数组中所有不同的差值绝对值为k的二元对的数目。

思路比较简单：首先用哈希表统计所有数出现的频率。对于k＝0的情况，我们返回所有出现次数大于1的数的数目，对于k>0的情况，我们只要统计所有n+k也出现的数n的数目。对于k<0的情况，直接返回0。我第一次提交忘记考虑k<0的情况了。

class Solution(object):
    def findPairs(self, nums, k):
        """
        :type nums: List[int]
        :type k: int
        :rtype: int
        """
        if k < 0:
            return 0
        ans = 0
        d = {}
        for n in nums:
            d[n] = d.get(n, 0) + 1
        if k == 0:
            for a, b in d.items():
                if b > 1:
                    ans += 1
        else:
            for a in d.keys():
                if a+k in d:
                    ans += 1
        return ans

第二题Lonely Pixel I。

题目大意：给定一个只含有字符B和W的二维数组，统计满足以下条件的B：
在其出现的行和列除它本身外其他都是W

没有什么犀利的做法，直接暴力统计。

class Solution(object):
    def findLonelyPixel(self, picture):
        """
        :type picture: List[List[str]]
        :rtype: int
        """
        n = len(picture)
        if n == 0:
            return 0
        m = len(picture[0])
        if m == 0:
            return 0
        ans = 0
        for row in picture:
            if sum(1 for c in row if c == 'B') != 1:
                continue
            j = 0
            while row[j] != 'B':
                j += 1
            if sum(1 for i in xrange(n) if picture[i][j] == 'B') == 1:
                ans += 1
        return ans

第三题Lonely Pixel II。

题目大意：给定一个只包含字符B和W的二维数组和一个数N，统计满足以下条件的B（假设B出现在R行C列）： 1. 第R行和第C列都包含N个B； 2. 对于第C列包含B的所有行，都与第R行一样。

思路：由这二个条件我们可以知道，每一列的所有B要么同时满足条件，要么同时不满足。所以，我们可以一列列枚举。

class Solution(object):
    def findBlackPixel(self, picture, N):
        """
        :type picture: List[List[str]]
        :type N: int
        :rtype: int
        """
        n = len(picture)
        if n == 0:
            return 0
        m = len(picture[0])
        if m == 0:
            return 0
        if N <= 0:
            return 0

        row_sum = []
        for row in picture:
            row_sum.append(sum(1 for c in row if c == 'B'))

        ans = 0
        for j in xrange(m):
            unique = set()
            c = 0
            for i in xrange(n):
                if picture[i][j] == 'B':
                    c += 1
                    unique.add((''.join(picture[i]), row_sum[i]))
            unique = list(unique)
            if c == N and len(unique) == 1 and unique[0][1] == N:
                ans += c
        return ans

第四题Freedom Trail是一道dp题。

题目大意：给定两个字符串ring和key，初始是指标在ring的第0个位置。指标可以向左向右移动（想象ring是一个首尾相连的圈）。每次移动指标花费移动距离加1，问最小花费多少能拼出key。

动态规划思路：假设dp(i, j)表示当前指标在ring的第i个位置，从key第j个位置开始拼写的最小花费。假设n=len(ring)，m=len(key)。状态转移方程是：

{% raw %}

$$\mathrm{dp}(i, j) = \min\left\{ \begin{array}{l} \mathrm{dp}((i+k)\% n, j+1)+k+1 \text{ if }\mathrm{ring}[(i+k)\% n] = \mathrm{key}[j]\text{ for } k = 0, 1, \dots, n/2 \\ \mathrm{dp}((i+n-k)\% n, j+1)+k+1 \text{ if }\mathrm{ring}[(i+n-k)\% n] = \mathrm{key}[j]\text{ for } k = 1, 2, \dots, n/2 \end{array} \right.$$


边界条件是：dp(i, m) = 0。

class Solution(object):
    def findRotateSteps(self, ring, key):
        """
        :type ring: str
        :type key: str
        :rtype: int
        """
        n, m = len(ring), len(key)

        def dp(i, j, memo):
            if j == m:
                return 0
            if (i, j) in memo:
                return memo[i, j]
            ans = 2 ** 31
            for k in xrange(n/2+1):
                ni = (i+k) % n
                if ring[ni] == key[j]:
                    ans = min(ans, k+1+dp(ni, j+1, memo))
            for k in xrange(1, n/2+1):
                ni = (i+n-k) % n
                if ring[ni] == key[j]:
                    ans = min(ans, k+1+dp(ni, j+1, memo))
            memo[i, j] = ans
            return ans

        return dp(0, 0, {})
contest leetcode