单例模式，用C#实现过单例模式，python区别就是类里边的静态方法写法不一样，python叫类方法,函数之前加@classmethod
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
三角形计数 给定一个整数数组，在该数组中，寻找三个数，分别代表三角形三条边的长度，问，可以寻找到多少组这样的三个数来组成三角形
直接遍历会提示超过时间限制
选择排序加二分查找的方法来提高效率，python默认的递归有上线，需要设置， 还有二分查找的方法是先确认最大最小边然后找第三边，这样条件就变成一个
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
将一个二叉查找树按照中序遍历转换成双向链表。
"""
Definition of TreeNode:
class TreeNode:
def __init__(self, val):
this.val = val
this.left, this.right = None, None
Definition of Doubly-ListNode
class DoublyListNode(object): def __init__(self, val, next=None):
self.val = val
self.next = self.prev = next
""" class Solution:
"""
@param root, the root of tree
@return: a doubly list node
"""
def bstToDoublyList(self, root):
# Write your code here
l=[]
if root is None:return
stack=[]
current=root
dlist=None
cur=None
last=None
while len(stack)> 0 or current is not None:
while current is not None:
stack.append(current)
current=current.left
current=stack.pop()
l.append(current.val)
cur=DoublyListNode(current.val)
cur.prev=last
if last is not None: last.next=cur
last=cur
if dlist is None :dlist=cur
current=current.right
return dlist