递归计算字符串长
def length(self, s):
if s == '\n'：
return 0
else:
return 1 + self.length(s[1:])
Given a 2d array of numbers, write a function that all matching pairs of numbers. Return a structure that contains the value and positions of each pair. Use each location in the array only once.
Example input:
1 3 4 1
6 1 7 8
9 0 5 8
2 2 1 2
Example Return:
[{value:1, x1:0, y1:0, x2:1, y2:1},
{value:1, x1:2, y1:3, x2:3, y2:0},
{value:8, x1:3, y1: 2, x2:3, y2:1},
{value:2, x1:0, y1:3, x2:1, y2:3}]
Product of Array Except Self (LC 238)
Solve it without division and in O(n).
For example, given [1,2,3,4], return [24,12,8,6]
class Solution:
def productExceptSelf(self, nums):
p = 1
n = len(nums)
output = []
for i in range(0,n):
output.append(p)
p = p * nums[i]
p = 1
for i in range(n-1,-1,-1):
output[i] = output[i] * p
p = p * nums[i]
return output
Majority Element (LC169)
return sorted(num)[len(num)/2]
Lowest Common Ancestor of a Binary Tree (LC236)
def lowestCommonAncestor(self, root, p, q):
if root in (None, p, q): return root
left, right = (self.lowestCommonAncestor(kid, p, q)
for kid in (root.left, root.right))
return root if left and right else left or right
Valid Parentheses (LC 20)
class Solution(object):
def isValid(self, s):
rp = [')', ']', '}']
d = {')': '(', ']': '[', '}': '{'}
l = []
if s[0] in rp:
return False
for p in s:
if p in rp and len(l) > 0:
if l.pop() == d[p]:
continue
else:
return False
else:
l.append(p)
return l == []
shuffle a string so that no two ajacent characters are same
Similar to LC 358
Writing your own square root function
(http://stackoverflow.com/questions/1623375/writing-your-own-square-root-function)
Find all subsets of a set. (LC 78)
# Iteratively
def subsets(self, nums):
res = [[]]
for num in sorted(nums):
res += [item+[num] for item in res]
return res
Swap nodes in pairs in a linked list. (LC 24)
def swapPairs(self, head):
pre, pre.next = self, head
while pre.next and pre.next.next:
a = pre.next
b = a.next
pre.next, b.next, a.next = b, a, b.next
pre = a
return self.next
Decision Tree construction
(i.e., how to compute entropy and information gaim)
reverse integer
def reverse(self, x):
s = cmp(x, 0)
r = int(`s*x`[::-1])
return s*r * (r < 2**31)
给一个string input， eg：“appleE”， 统计每个character的个数，然后按照character的字母先后顺序，打印letter和次数， eg： output of “appleE” is “E1a1e1l1p2”. 这里大小写是区分的， 所以更容易些。
string. ascii_letters/string. ascii_lowercase/string.ascii_uppercase
Group Anagrams
LC 49
