【leecode刷题】初级算法-其他

1、位1的个数

class Solution(object): def hammingWeight(self, n): """ :type n: int :rtype: int """ count = 0 for i in '{0:032b}'.format(n): if i=="1": count = count+1 return count

2、汉明距离

class Solution(object): def hammingDistance(self, x, y): """ :type x: int :type y: int :rtype: int """ count = 0 xB = '{0:032b}'.format(x) yB = '{0:032b}'.format(y) for i in range(len(xB)): if xB[i]!=yB[i]: count = count+1 return count

3、颠倒二进制位

class Solution: # @param n, an integer # @return an integer def reverseBits(self, n): ret, power = 0, 31 while n: ret += (n & 1) << power n = n >> 1 power -= 1 return ret

4、杨辉三角

class Solution(object): def generate(self, numRows): """ :type numRows: int :rtype: List[List[int]] """ def generate1(numRows,L): if numRows==1: L[numRows] = [1] return [1] elif numRows==2: L[numRows] = [1,1] return [1,1] elif len(L[numRows])>1: return L[numRows] else: result = [1]*numRows ListBefore = generate1(numRows-1,L) for i in range(1,numRows-1): result[i] = ListBefore[i-1]+ListBefore[i] L[numRows] = result return result if numRows==0: return [] else: L = [[]]*(numRows+1) generate1(numRows,L) L[1] = [1] L.pop(0) return L

5、有效的括号

def matches(open,close): opens = "([{" closers = ")]}" return opens.index(open) == closers.index(close) class Stack: def __init__(self): self.items = [] def isEmpty(self): return self.items == [] def push(self, item): self.items.append(item) def pop(self): return self.items.pop() def peek(self): return self.items[len(self.items)-1] def size(self): return len(self.items) class Solution(object): def isValid(self, symbolString): """ :type s: str :rtype: bool """ s = Stack() balanced = True index = 0 while index < len(symbolString) and balanced: symbol = symbolString[index] if symbol in "([{": s.push(symbol) else: if s.isEmpty(): balanced = False else: top = s.pop() if not matches(top,symbol): balanced = False index = index + 1 if balanced and s.isEmpty(): return True else: return False

6、缺失数字

class Solution(object): def missingNumber(self, nums): """ :type nums: List[int] :rtype: int """ for i in range(len(nums)+1): if i not in nums: return i