lintcode 刷题记录··

`class Solution: # @return: The same instance of this class every time __m_Solution=None @classmethod def getInstance(self): # write your code here if self.__m_Solution == None: self.__m_Solution=Solution() return self.__m_Solution def __init__(self): pass`

`class Solution： # @param {int} target an integer # @return {int[][]} all valid paths def binaryTreePathSum(self, root, target): # Write your code here res = [] path = [] import copy def getallpath(current, path, res): if current == None: return path.append(current.val) if current.left != None: getallpath(current.left,copy.deepcopy(path), res) if current.right != None: getallpath(current.right,copy.deepcopy(path),res) if current.left is None and current.right is None: res.append(path) getallpath(root,path,res) ps=[] for p in res: sum=0 for v in p: sum=sum+v if sum==target:ps.append(p) return ps `

三角形计数 给定一个整数数组，在该数组中，寻找三个数，分别代表三角形三条边的长度，问，可以寻找到多少组这样的三个数来组成三角形

`class Solution: # @param S: a list of integers # @return: a integer def triangleCount(self, S): # write your code here def quicksort(a): # 快速排序 if len(a) < 2: return a else: pivot = a[0] less = [i for i in a[1:] if i <= pivot] greator = [i for i in a[1:] if i > pivot] return quicksort(less) + [pivot] + quicksort(greator) n = len(S) if n < 3: return import sys sys.setrecursionlimit(1000000) S = quicksort(S) sum = 0 for i in range(n): for j in range(i + 1, n): l = i + 1 r = j target = S[j] - S[i] while l < r: mid = (l + r) // 2 if S[mid] > target: r = mid else: l = mid + 1 sum = sum + j - l return sum`

Top