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


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


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 = list(unique)
if c == N and len(unique) == 1 and unique[0][1] == N:
ans += c
return ans


{% 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.$$

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, {})