题目:如何得到一个数据流中的中位数？如果从数据流中读出奇数个数值，那么中位数就是所有数值排序之后位于中间的数值。如果从数据流中读出偶数个数值，那么中位数就是所有数值排序之后中间两个数的平均值。我们使用Insert()方法读取数据流，使用GetMedian()方法获取当前读取数据的中位数。|
class Solution: def __init__(self): self.left = [] self.right = [] self.count = 0 def Insert(self, num): if self.count & 1 == 0: self.left.append(num) else: self.right.append(num) self.count += 1 def GetMedian(self, x): if self.count == 1: return self.left[0] self.MaxHeap(self.left) self.MinHeap(self.right) if self.left[0] > self.right[0]: self.left[0], self.right[0] = self.right[0], self.left[0] self.MaxHeap(self.left) self.MinHeap(self.right) if self.count & 1 == 0: return (self.left[0] + self.right[0])/2.0 else: return self.left[0] def MaxHeap(self, alist): length = len(alist) if alist == None or length <= 0: return if length == 1: return alist for i in range(length//2-1, -1, -1): k = i; temp = alist[k]; heap = False while not heap and 2*k < length-1: index = 2*k+1 if index < length - 1: if alist[index] < alist[index + 1]: index += 1 if temp >= alist[index]: heap = True else: alist[k] = alist[index] k = index alist[k] = temp def MinHeap(self, alist): length = len(alist) if alist == None or length <= 0: return if length == 1: return alist for i in range(length//2-1, -1, -1): k = i; temp = alist[k]; heap = False while not heap and 2 * k < length - 1: index = 2 * k+1 if index < length - 1: if alist[index] > alist[index + 1]: index += 1 if temp <= alist[index]: heap = True else: alist[k] = alist[index] k = index alist[k] = temp so=Solution() so.Insert(1) so.Insert(2) so.Insert(3) so.Insert(4) so.Insert(5) so.GetMedian(0) 3 so=Solution() so.Insert(1) so.Insert(2) so.Insert(3) so.Insert(4) so.Insert(5) so.Insert(6) so.GetMedian(0) 3.5题目:输入一个整型数组，数组里有正数也有负数。数组中一个或连续的多个整数组成一个子数组。求所有子数组的和的最大值。要求时间复杂度为O(n)。
class Solution: def FindGreatestSumOfSubArray(self, array): # write code here if not array: return 0 cur_sum = 0 max_sum = array[0] for i in range(len(array)): if cur_sum <= 0: cur_sum = array[i] else: cur_sum += array[i] if cur_sum > max_sum: max_sum = cur_sum return max_sum so=Solution() so.FindGreatestSumOfSubArray([1,-2,3,10,-4,7,2,-5]) 18题目：输入一个整数n，求从1到n这n个整数的十进制表示中1出现的次数。例如输入12，从1到12这些整数中包含1的数字有1、10、11和12，1一共出现了5次。
# 数学规律 class Solution: def NumberOf1Between1AndN_Solution(self, n): # write code here count, m =0, 1 while m <= n: count += (n // m + 8) // 10 * m + (n // m % 10 == 1) * (n % m + 1) m*=10 return count so=Solution() so.NumberOf1Between1AndN_Solution(12) 5题目:数字以0123456789101112131415…的格式序列化到一个字符序列中。在这个序列中，第5位（从0开始计数）是5，第13位是1，第19位是4，等等。请写一个函数，求任意第n位对应的数字。
def print_num(n): length = 0 for i in range(n): length += len(str(i)) if length >= n: return str(i)[length - n] print_num(19) '4' class Solution(object): def digitAtIndex(self, n): # 如果 n 小于 10 ，直接返回就可以了 if n < 10: return n # 计算前缀部分 base = 9 digits = 1 # 2 位数，从 10 到 99 一共 ( 99 - 10 + 1) * 2 = 90 * 2 = 180 位 # 3 位数，从 100 到 999 一共 ( 999 - 100 + 1) * 2 = 900 * 3 = 2700 位 # 4 位数，从 1000 到 9999 一共 ( 9999 - 1000 + 1) * 2 = 9000 * 4 = 3600 位 while n - base * digits > 0: n -= base * digits base *= 10 digits += 1 index = n % digits if index == 0: # 计算出 num 是多少 # 例如：192，有 1 个位移的偏差 num = 10 ** (digits - 1) + n // digits - 1 # 返回个位就可以了 return num % 10 else: # 不能整除，那个偏移就不用算了 # 例如 194 = 189 + 5 # 100 + 2 = 102 num = 10 ** (digits - 1) + n // digits # 从左边向右边数，第 2 位 for i in range(index, digits): num //= 10 return num % 10 so=Solution() print(so.digitAtIndex(19)) 4题目:输入一个正整数数组，把数组里所有数字拼接起来排成一个数，打印能拼接出的所有数字中最小的一个。例如输入数组{3，32，321}，则打印出这三个数字能排成的最小数字为321323。
class Solution: def PrintMinNumber(self, numbers): # write code here if not numbers: return '' str_num = [str(m) for m in numbers] for i in range(len(numbers)-1): for j in range(i+1,len(numbers)): if str_num[i] + str_num[j] > str_num[j] + str_num[i]: str_num[i],str_num[j] = str_num[j] ,str_num[i] return ''.join(str_num) so=Solution() so.PrintMinNumber([3,32,321]) '321323'题目：给定一个数字，按照如下规则翻译成字符串：0翻译成"a"，1翻译成"b"…25翻译成”z"。一个数字可能有多个翻译。如12258有5种不同的翻译，分别是"bccfi", “bwfi”, “bczi”, “mcfi”, “mzi”。请实现一个函数，用来计算一个数字有多少种不同的翻译方法。
思路。当最初的一个或者两个数字被翻译成一个字符后，我们接着翻译后面剩下的数字。可以用递归来做。但是递归会有重复的出现。比如12258，翻译成1和2258，或12和258，然后2258可以翻译成2和258或22和58，这样258又重复出现了。因此我们选择从最小的子问题开始自下而上解决问题。也就是我们从数字的末尾开始，然后从右到左翻译并计算不同翻译的数目。
class Solution: def GetTranslationCount(self, number): if number<0: return 0 StrNumber = str(number) length = len(StrNumber) count = 0 counts = [0]*length for i in range(length-1, -1, -1): count = 0 if i<length-1: count = counts[i+1] else: count = 1 print(count, counts) if i<length-1: digit1 = int(StrNumber[i]) digit2 = int(StrNumber[i+1]) converted = digit1*10+digit2 if converted>=10 and converted<=25: if i<length-2: count = count+counts[i+2] else: count = count+1 counts[i] = count count = counts[0] return count so=Solution() so.GetTranslationCount(12258) 1 [0, 0, 0, 0, 0] 1 [0, 0, 0, 0, 1] 1 [0, 0, 0, 1, 1] 2 [0, 0, 2, 1, 1] 3 [0, 3, 2, 1, 1] 5 class Solution: def getTranslationCount(self, s): if not s: return 0 if len(s) == 1: return 1 # 判断字符是否为‘0’，避免0X的形式 if s[0] != '0' and int(s[:2]) >= 0 and int(s[:2]) <= 25: return self.getTranslationCount(s[2:]) + self.getTranslationCount(s[1:]) return self.getTranslationCount(s[1:]) so=Solution() so.getTranslationCount("12258") 5题目:在一个 m*n 的棋盘中的每一个格都放一个礼物，每个礼物都有一定的价值（价值大于0）.你可以从棋盘的左上角开始拿各种里的礼物，并每次向左或者向下移动一格，直到到达棋盘的右下角。给定一个棋盘及上面个的礼物，请计算你最多能拿走多少价值的礼物？
class Solution: def getmaxValue(self, values, rows, cols): if not values or rows<=0 or cols <=0: return 0 # 用于存放中间数值的临时数组 temp = [0] * cols for i in range(rows): for j in range(cols): left = 0 up = 0 if i > 0: up = temp[j] if j > 0: left = temp[j-1] temp[j] = max(up,left) + values[i*rows+j] return temp[-1] so = Solution() so.getmaxValue([1,10,3,8,12,2,9,6,5,7,4,11,3,7,16,5],4,4) 53题目:请从字符串中找出一个最长的不包含重复字符的子字符串，计算该最长子字符串的长度。例如在“arabcacfr”中，最长的不包含重复字符的子字符串是“acfr”，长度为4采用字典的方法，最后输出所有最长字符的列表
class Solution: def __init__(self): self.maxString = [] def longestSubString(self, inputString): if inputString == '': return '' dic = {} dic = dic.fromkeys(inputString, 0) self.maxString.append(inputString[0]) for i in range(len(inputString)): for j in range(i, len(inputString)): if dic[inputString[j]] != 0: dic = dic.fromkeys(inputString, 0) break else: if j - i + 1 > len(self.maxString[0]): self.maxString = [] self.maxString.append(inputString[i:j+1]) elif j - i + 1 == len(self.maxString[0]): self.maxString.append(inputString[i:j+1]) dic[inputString[j]] += 1 inputString = 'arabcacfr' sol = Solution() sol.longestSubString(inputString) print(sol.maxString) ['rabc', 'acfr']题目:把只包含质因子2、3和5的数称作丑数（Ugly Number）。例如6、8都是丑数，但14不是，因为它包含质因子7。 习惯上我们把1当做是第一个丑数。求按从小到大的顺序的第N个丑数。
class Solution: def GetUglyNumber_Solution(self, index): if not index: return 0 ugly_number = [1]*index next_index = 1 index2 = 0 index3 = 0 index5 = 0 while next_index < index: minValue = min(ugly_number[index2]*2, ugly_number[index3]*3,ugly_number[index5]*5) ugly_number[next_index] = minValue while ugly_number[index2]*2 <= ugly_number[next_index]: index2 += 1 while ugly_number[index3]*3 <= ugly_number[next_index]: index3 += 1 while ugly_number[index5]*5 <= ugly_number[next_index]: index5 += 1 next_index += 1 return ugly_number[-1] so=Solution() so.GetUglyNumber_Solution(1500) 859963392题目一:字符串中第一个只出现一次的字符
在一个字符串(1<=字符串长度<=10000，全部由字母组成)中找到第一个只出现一次的字符,并返回它的位置
class Solution: def FirstNotRepeatingChar(self, s): # write code here if not s: return -1 store = {} lis = list(s) for i in lis: if i not in store.keys(): store[i] = 0 store[i] += 1 for i in lis: if store[i] == 1: return s.index(i) return -1 so=Solution() print(so.FirstNotRepeatingChar("abacccdeff")) "abacccdeff"[so.FirstNotRepeatingChar("abacccdeff")] 1 'b'题目二：字符流中第一个只出现一次的字符
请实现一个函数用来找出字符流中第一个只出现一次的字符。例如，当从字符流中只读出前两个字符"go"时，第一个只出现一次的字符是"g"。当从该字符流中读出前六个字符“google"时，第一个只出现一次的字符是"l"。如果当前字符流没有存在出现一次的字符，返回#字符。
class Solution: # init def __init__(self): self.dic = {} self.lis = [] # 返回对应char def FirstAppearingOnce(self): # write code here while len(self.lis) > 0 and self.dic[self.lis[0]] == 2: self.lis.pop(0) if len(self.lis) == 0: return '#' else: return self.lis[0] def Insert(self, char): # write code here if char not in self.dic.keys(): self.dic[char] = 1 self.lis.append(char) elif self.dic[char]: self.dic[char] = 2 so=Solution() so.Insert("g") so.Insert("o") so.Insert("o") so.Insert("g") so.Insert("l") so.Insert("e") so.FirstAppearingOnce() 'l'在数组中的两个数字，如果前面一个数字大于后面的数字，则这两个数字组成一个逆序对。输入一个数组,求出这个数组中的逆序对的总数P。
class Solution: def InversePairs(self, data): # write code here count = 0 copy = [] for i in data: copy.append(i) copy.sort() for i in range(len(copy)): count += data.index(copy[i]) data.remove(copy[i]) return count so=Solution() so.InversePairs([7,5,6,4]) 5 count = 0 class Solution: def InversePairs(self, data): global count def MergeSort(lists): global count if len(lists) <= 1: return lists num = int( len(lists)/2 ) left = MergeSort(lists[:num]) right = MergeSort(lists[num:]) r, l=0, 0 result=[] while l<len(left) and r<len(right): if left[l] < right[r]: result.append(left[l]) l += 1 else: result.append(right[r]) r += 1 count += len(left)-l print('count: ', count) result += right[r:] result += left[l:] return result MergeSort(data) return count so=Solution() so.InversePairs([7,5,6,4]) count: 1 count: 2 count: 4 count: 5 5题目:输入两个链表，找出它们的第一个公共结点。
class Solution: def FindFirstCommonNode(self, pHead1, pHead2): if not pHead1 or not pHead2: return None p1,p2 = pHead1,pHead2 len1 = len2 = 0 while p1: len1 += 1 p1 = p1.next while p2: len2 += 1 p2 = p2.next if len1 > len2: while len1 - len2: pHead1 = pHead1.next len1 -= 1 else: while len2 - len1: pHead2 = pHead2.next len2 -= 1 while pHead1 and pHead2: if pHead1 is pHead2: return pHead1 pHead1 = pHead1.next pHead2 = pHead2.next return None def printListFromTailToHead1(head): if head is None: return print(head.val) printListFromTailToHead1(head.next) class ListNode: def __init__(self, x): self.val = x self.next = None llist1 = ListNode(1) pnode1 = llist1 for i in range(2, 11): pnode1.next = ListNode(i) pnode1 = pnode1.next printListFromTailToHead1(llist1) 1 2 3 4 5 6 7 8 9 10 printListFromTailToHead1(llist1.next.next.next) 4 5 6 7 8 9 10 so=Solution() print(so.FindFirstCommonNode(llist1,llist1.next.next.next).val) 4题目一：数字在排序数组中出现的次数
统计一个数字在排序数组中出现的次数
class Solution: def GetNumberOfK(self, data, k): # write code here if not data: return 0 if self.GetLastK(data, k) == -1 and self.GetFirstK(data, k) == -1: return 0 return self.GetLastK(data, k) - self.GetFirstK(data, k) + 1 def GetFirstK(self, data, k): low = 0 high = len(data) - 1 while low <= high: mid = (low + high) // 2 if data[mid] < k: low = mid + 1 elif data[mid] > k: high = mid - 1 else: if mid == low or data[mid - 1] != k: #当到list[0]或不为k的时候跳出函数 return mid else: high = mid - 1 return -1 def GetLastK(self, data, k): low = 0 high = len(data) - 1 while low <= high: mid = (low + high) // 2 if data[mid] > k: high = mid - 1 elif data[mid] < k: low = mid + 1 else: if mid == high or data[mid + 1] != k: return mid else: low = mid + 1 return -1 so=Solution() so.GetNumberOfK([1,2,3,3,3,3,4,5],3) 4题目二：0~n-1中缺失的数字
一个长度为n-1的递增排序数组中的所有数字都是唯一的，并且每个数字都在范围0到n-1之内。
在范围0到n-1的n个数字中有且只有一个数字不在该数组中，请找出这个数字。
#最简单，肯定不是最好的算法 class Solution(object): def getMissingNumber(self, nums): """ :type nums: List[int] :rtype: int """ if not nums: return 0 for i in range(len(nums)): if i!= nums[i]: return i return i+1 so=Solution() so.getMissingNumber([0,1,2,4]) 3 class Solution(object): def getMissingNumber(self, nums): """ :type nums: List[int] :rtype: int """ if not nums: return 0 l = 0 r = len(nums)-1 while l<=r: mid = l+(r-l)//2 if mid!=nums[mid]: if mid==0 or nums[mid-1]==mid-1: return mid r = mid-1 else: l = mid+1 if l == len(nums): return l return -1 so=Solution() so.getMissingNumber([0,1,2,4]) 3题目三：数组中数值和下标相等的元素
假设一个单调递增的数组里的每个元素都是整数并且是唯一的。 请编程实现一个函数找出数组中任意一个数值等于其下标的元素。 例如，在数组{-3, -1, 1, 3, 5}中，数字3和它的下标相等。
''' 假设一个单调递增的数组里的每个元素都是整数并且是唯一的。 请编程实现一个函数找出数组中任意一个数值等于其下标的元素。 例如，在数组{-3, -1, 1, 3, 5}中，数字3和它的下标相等。 ''' class Solution: def GetNumberSameAsIndex(self, data, num): if num < 0 or len(data) <= 0: return "please input right data or number" start = 0 end = len(data) - 1 while start <= end: mid = (start + end) // 2 if data[mid] == num: return mid # 一个元素的值一旦大于他的下标，那么该元素右边的值 # 肯定都大于他的下标。因此从改元素左边找就可以了 elif data[mid] > mid: end = mid - 1 # 同理，一个元素的值如果小于他的下标， # 那么左侧的值也都不满足条件 elif data[mid] < mid: start = mid + 1 return None a = Solution() a.GetNumberSameAsIndex([-3, -1, 1, 3, 5], 3) 3 a = Solution() a.GetNumberSameAsIndex([-3, -1, 1, 4, 5], 3)题目：给定一棵二叉搜索树，请找出其中的第k小的结点。例如， （5，3，7，2，4，6，8） 中，按结点数值大小顺序第三小结点的值为4。
class TreeNode: def __init__(self, x): self.val = x self.left = None self.right = None class Solution: # 返回对应节点TreeNode def KthNode(self, pRoot, k): # write code here if not pRoot or not k: return res = [] def traverse(node): if len(res) >= k or not node: return traverse(node.left) res.append(node) traverse(node.right) traverse(pRoot) if len(res) < k: return return res[k-1] Root = TreeNode(5) Root.left = TreeNode(3) Root.left.left = TreeNode(2) Root.left.right = TreeNode(4) Root.right = TreeNode(7) Root.right.left = TreeNode(6) Root.right.right = TreeNode(8) so=Solution() so.KthNode(Root,3).val 4题目一：二叉树的深度
输入一棵二叉树，求该树的深度。从根结点到叶结点依次经过的结点（含根、叶结点）形成树的一条路径，最长路径的长度为树的深度。
class Solution: def TreeDepth(self, pRoot): if not pRoot: return 0 return max(self.TreeDepth(pRoot.left),self.TreeDepth(pRoot.right)) + 1 Root = TreeNode(5) Root.left = TreeNode(3) Root.left.left = TreeNode(2) Root.left.right = TreeNode(4) Root.right = TreeNode(7) Root.right.left = TreeNode(6) Root.right.right = TreeNode(8) Root.right.right.right = TreeNode(10) Root.right.right.right.right = TreeNode(12) so=Solution() so.TreeDepth(Root) 5题目二：平衡二叉树
输入一棵二叉树，判断该二叉树是否是平衡二叉树。
平衡二叉树的定义是任何节点的左右子树高度差都不超过1的二叉树。
class Solution: def __init__(self): self.flag = True def IsBalanced_Solution(self, pRoot): # write code here self.getDepth(pRoot) return self.flag def getDepth(self, root): if not root: return 0 left = self.getDepth(root.left) + 1 right = self.getDepth(root.right) + 1 if abs(left - right) > 1: self.flag = False return left if left > right else right so=Solution() so.IsBalanced_Solution(Root) False Root = TreeNode(5) Root.left = TreeNode(3) Root.left.left = TreeNode(2) Root.left.right = TreeNode(4) Root.right = TreeNode(7) Root.right.left = TreeNode(6) Root.right.right = TreeNode(8) so=Solution() so.IsBalanced_Solution(Root) True题目一：数组中只出现一次的两个数字
一个整型数组里除了两个数字之外，其他的数字都出现了两次。请写程序找出这两个只出现一次的数字。
要求时间复杂度O(n)，空间复杂度O(1)
# 哈希法 class Solution: # 返回[a,b] 其中ab是出现一次的两个数字 def FindNumsAppearOnce(self, array): # write code here hashmap = {} for i in array: if str(i) in hashmap: hashmap[str(i)] += 1 else: hashmap[str(i)] = 1 result = [] for k in hashmap.keys(): if hashmap[k] == 1: result.append(int(k)) return result so=Solution() so.FindNumsAppearOnce([2,4,3,6,3,2,5,5]) [4, 6] class Solution: # 返回[a,b] 其中ab是出现一次的两个数字 def FindNumsAppearOnce(self, array): if array == None: return [] xor = 0 for i in array: xor ^= i idxOf1 = self.getFirstIdx(xor) num1 = num2 = 0 for j in range(len(array)): if self.IsBit(array[j], idxOf1): num1 ^= array[j] else: num2 ^= array[j] return [num1, num2] def getFirstIdx(self, num): idx = 0 while num & 1 == 0 and idx <= 32: idx += 1 num = num >> 1 return idx def IsBit(self, num, indexBit): num = num >> indexBit return num & 1 so=Solution() so.FindNumsAppearOnce([2,4,3,6,3,2,5,5]) [6, 4]题目二：数组中唯一只出现一次的数字
在一个数组中除了一个数字只出现一次之外，其他数字都出现了三次。O(n)
class Solution: def findNumberAppearingOnce(self,nums): res=0 for i in range(32): count=0 for num in nums: if (num>>i)&1: count+=1 if count%3: res+=1<<i return res so=Solution() so.findNumberAppearingOnce([4,3,4,3,2,3,4]) 2题目一：和为s的两个数字
输入一个递增排序的数组和一个数字S，在数组中查找两个数，是的他们的和正好是S，如果有多对数字的和等于S，输出任意一对即可。
class Solution: def FindNumbersWithSum(self, array, tsum): # write code here if not array or not tsum: return [] start = 0 end = len(array) - 1 while start < end: csum = array[start] + array[end] if csum < tsum: start += 1 elif csum > tsum: end -= 1 else: return [array[start],array[end]] return [] so=Solution() so.FindNumbersWithSum([0,1,2,4,7,11,15],15) [0, 15]题目二：和为s的连续整数序列
输出所有和为S的连续正数序列。序列内按照从小至大的顺序，序列间按照开始数字从小到大的顺序
例如：15=1+2+3+4+5=4+5+6=7+8
class Solution: def FindContinuousSequence(self, tsum): small, big,res = 1, 2, [] csum = small + big while small < big: if csum > tsum: csum -= small small += 1 else: if csum == tsum: res.append([i for i in range(small,big+1)]) big += 1 csum += big return res so=Solution() so.FindContinuousSequence(15) [[1, 2, 3, 4, 5], [4, 5, 6], [7, 8]]题目一：翻转单词顺序
例如，“I am a student.”。翻转后的句子应该是“student. a am I”。
class Solution: def ReverseSentence(self, s): # write code here if not s or len(s) <= 0: return '' lis = list(s) lis = self.Reverse(lis) start = 0 end = 0 res = '' lisTmp = [] while end < len(s): if end == len(s) - 1: lisTmp.append(self.Reverse(lis[start:])) break if lis[start] == ' ': start += 1 end += 1 lisTmp.append(' ') elif lis[end] == ' ': lisTmp.append(self.Reverse(lis[start:end])) start = end else: end += 1 for i in lisTmp: res += ''.join(i) return res def Reverse(self,lis): if not lis or len(lis) <= 0: return '' start = 0 end = len(lis) - 1 while start < end: lis[start], lis[end] = lis[end], lis[start] start += 1 end -= 1 return lis so=Solution() so.ReverseSentence("I am a student.") 'student. a am I'题目二：左旋转字符串
例如，字符序列S=”abcXYZdef”,要求输出循环左移3位后的结果，即“XYZdefabc”。
class Solution: def LeftRotateString(self, s, n): # write code here if len(s) <= 0 or n < 0 or len(s) < n: return '' lis = list(s) self.Reverse(lis) length = len(s) pivot = length - n frontlist = self.Reverse(lis[:pivot]) behindlist = self.Reverse(lis[pivot:]) res = ''.join(frontlist) + ''.join(behindlist) return res def Reverse(self,lis): if not lis or len(lis) <= 0: return '' start = 0 end = len(lis) - 1 while start < end: lis[start], lis[end] = lis[end], lis[start] start += 1 end -= 1 return lis so=Solution() so.LeftRotateString("abcXYZdef",3) 'XYZdefabc'题目一： 滑动窗口的最大值。给定一个数组和滑动窗口的大小，请找出所有滑动窗口里的最大值。例如，如果输入数组{2,3,4,2,6,2,5,1}及滑动窗口的大小3，那么一共存在6个滑动窗口，他们的最大值分别为{4,4,6,6,6,5}； 针对数组{2,3,4,2,6,2,5,1}的滑动窗口有以下6个： {[2,3,4],2,6,2,5,1}， {2,[3,4,2],6,2,5,1}， {2,3,[4,2,6],2,5,1}， {2,3,4,[2,6,2],5,1}， {2,3,4,2,[6,2,5],1}， {2,3,4,2,6,[2,5,1]}。
class Solution: def max_in_sliding_window(self,array, window_width): """ :param array: numbers :param window_width:sliding window size :return: all max number """ if not array or window_width < 1: return None max_i = [] res = [] for i in range(len(array)): while max_i and array[i] >= array[max_i[-1]]: max_i.pop() max_i.append(i) while max_i and i - max_i[0] >= window_width: max_i.pop(0) if window_width - 1 <= i: res.append(array[max_i[0]]) return res so=Solution() so.max_in_sliding_window([2,3,4,2,6,2,5,1],3) [4, 4, 6, 6, 6, 5]题目二： 队列的最大值。请定义一个队列并实现函数max得到队列里的最大值，要求函数max、push_back和 pop_front的时间复杂度都是O(1)。
用队列先进先出的特点，可以免于考虑剔除最大值后，候补最大值不存在于队列的情况，大大减少了计算。
class Queue(object): def __init__(self): self.data = [] self.max_data = [] def pop(self): """ pop out the head element :return: head element """ if not self.data: raise Exception('Empty Queue Cannot Pop') if self.data[0] == self.max_data[0]: self.max_data.pop(0) return self.data.pop(0) def push(self, x): """ push in the back :param x: element :return: None """ self.data.append(x) while self.max_data and self.max_data[-1] < x: self.max_data.pop() self.max_data.append(x) return def max(self): """ get the maximum element :return: max element """ return self.max_data[0] q=Queue() q.push(4) q.push(1) q.push(30) q.push(40) q.push(-2) q.max() 40 q.pop() 4 q.pop() 1题目:把n个骰子扔在地上，所有骰子朝上一面的点数之和为s。输入n，打印出s的所有可能的值的出现概率。
class Solution: def dicesSum(self, n): if n < 1: return [] probability = [] probability.append([0] * (6 * n + 1)) probability.append([0] * (6 * n + 1)) flag = 0 ratio = [] for i in range(1, 7): probability[flag][i] = 1 for k in range(2, n + 1): for i in range(0, k): probability[1 - flag][i] = 0 for i in range(k, 6 * k + 1): probability[1 - flag][i] = 0 for j in range(1, min(i + 1, 7)): probability[1 - flag][i] += probability[flag][i - j] flag = 1 - flag total = pow(6, n) for i in range(n, 6 * n + 1): ratio.append([i, probability[flag][i] / total]) return ratio Solution().dicesSum(3) [[3, 0.004629629629629629], [4, 0.013888888888888888], [5, 0.027777777777777776], [6, 0.046296296296296294], [7, 0.06944444444444445], [8, 0.09722222222222222], [9, 0.11574074074074074], [10, 0.125], [11, 0.125], [12, 0.11574074074074074], [13, 0.09722222222222222], [14, 0.06944444444444445], [15, 0.046296296296296294], [16, 0.027777777777777776], [17, 0.013888888888888888], [18, 0.004629629629629629]]题目：从扑克牌中随机抽5张牌，判断是不是一个顺子， 即这5张牌是不是连续的。2～10为数字本身， A为1。 J为11、Q为12、 K为13。大、小王可以看成任意数字。(为了方便，输入数组中0代表大小王)
class Solution: def IsContinuous(self, numbers): if not numbers or len(numbers) == 0: return False transdict = {'A':1,'J':11,'Q':12,'K':13} for i in range(len(numbers)): if numbers[i] in transdict.keys(): numbers[i] = transdict[numbers[i]] numbers = sorted(numbers) number_0 = 0 number_gap = 0 i = 0 while i < len(numbers) and numbers[i] == 0: number_0 += 1 i += 1 front = number_0 behind = front + 1 while behind < len(numbers): if numbers[front] == numbers[behind]: return False number_gap += numbers[behind] - numbers[front] - 1 front = behind behind += 1 return False if number_gap > number_0 else True so=Solution() so.IsContinuous([9,10,"J","Q","K"]) True题目：有个游戏是这样的:首先,让小朋友们围成一个大圈。然后,他随机指定一个数m,让编号为0的小朋友开始报数。每次喊到m-1的那个小朋友要出列并且不再回到圈中,从他的下一个小朋友开始,继续0…m-1报数….这样下去….直到剩下最后一个小朋友,求最后一个小朋友的编号
有一个不太容易发现的递推关系：
约瑟夫环的公式是：
f(n, m) = 0 (n = 1)
f(n, m) = [f(n-1, m) +m] % n (n > 1)
class Solution: def LastRemaining_Solution(self, n, m): if n < 1 or m < 1: return -1 idx = 0 for i in range(1,n+1): idx = (idx + m ) % i return idx so=Solution() so.LastRemaining_Solution(5,3) 3题目:假设把某股票的价格按照时间先后顺序存储在数组中，请问买卖该股票一次可获得的最大利润是多少？
例如，一只股票在某些时间节点的价格为{9,11,8,5,7,12,16,14}。如果我们能在价格为5的时候买入并在价格为16时卖出，则能获得最大的利润为11.
思路 动态规划， 前i天的最大收益 = max{前i-1天的最大收益，第i天的价格-前i-1天中的最小价格}
class Solution(object): def maxProfit(self, prices): min_p, max_p = 99999, 0 for i in range(len(prices)): min_p = min(min_p, prices[i]) max_p = max(max_p, prices[i]-min_p) return max_p so=Solution() so.maxProfit([9,11,8,5,7,12,16,14]) 11题目:求1+2+3+…+n，要求不能使用乘除法、for、while、if、else、switch、case等关键字及条件判断语句（A?B:C）。
class Solution: def Sum_Solution(self, n): return n and self.Sum_Solution(n - 1) + n so=Solution() so.Sum_Solution(10) 55题目:写一个函数，求两个整数之和，要求在函数体内不得使用+、-、*、/四则运算符号。
class Solution: def Add(self, num1, num2): while num2 != 0: temp = num1 ^ num2 # 相加不进位 num2 = (num1 & num2) << 1 # 进位 num1 = temp & 0xFFFFFFFF return num1 if num1 >> 31 == 0 else num1 - 4294967296 def Add1(self,num1,num2): total=0 carry=0 while num2!=0: total=num1^num2 carry=(num1&num2)<<1 num1=total num2=carry return num1 so=Solution() so.Add(200,10) 210 so.Add(-200,10) -190题目：给定一个数组A[0,1,…,n-1],请构建一个数组B[0,1,…,n-1],其中B中的元素B[i]=A[0]A[1]…*A[i-1]A[i+1]…*A[n-1]。不能使用除法。
class Solution: def multiply(self, A): print(A) if not A or len(A) <= 0: return length = len(A) lis = [1] * length print(lis) for i in range(1,length): lis[i] = lis[i-1] * A[i-1] print(lis) temp = 1 for i in range(length-2,-1,-1): temp = temp * A[i+1] lis[i] *= temp print(lis[i]) return lis so=Solution() so.multiply([1,2,3,4,5,10]) [1, 2, 3, 4, 5, 10] [1, 1, 1, 1, 1, 1] [1, 1, 2, 6, 24, 120] 240 300 400 600 1200 [1200, 600, 400, 300, 240, 120]题目:将一个字符串转换成一个整数，要求不能使用字符串转换整数的库函数。 数值为0或者字符串不是一个合法的数值则返回0
class Solution: def StrToInt(self, s): if not s or len(s) < 1: return 0 num = [] numdict = {'0': 0, '1': 1, '2': 2, '3': 3, '4': 4, '5': 5, '6': 6, '7': 7, '8': 8, '9': 9} for i in s: if i in numdict.keys(): num.append(numdict[i]) elif i == '+' or i == '-': continue else: return 0 ans = 0 if len(num) == 1 and num[0] == 0: return 0 for i in num: ans = ans*10 + i if s[0] == '-': ans = 0 - ans return ans so=Solution() so.StrToInt("-1234") -1234题目:输入两个二叉搜索树的结点，求两个结点的最低公共祖先，所谓的最低公共祖先是指距离两个节点最近的共同祖先
class TreeNode: def __init__(self, x): self.val = x self.left = None self.right = None class Solution: def lowestCommonAncestor(self,root,A,B): if root is None or root==A or root==B: return root left=self.lowestCommonAncestor(root.left,A,B) right=self.lowestCommonAncestor(root.right,A,B) if left is not None and right is not None: return root if left is None: return right if right is None: return left # 按行打印二叉树 def Print(self, pRoot): if pRoot is None: return [] nodes, res = [pRoot], [] while nodes: curStack, nextStack = [], [] for node in nodes: curStack.append(node.val) if node.left: nextStack.append(node.left) if node.right: nextStack.append(node.right) res.append(curStack) nodes = nextStack return res Root = TreeNode(5) Root.left = TreeNode(3) Root.left.left = TreeNode(2) Root.left.right = TreeNode(4) Root.right = TreeNode(7) Root.right.left = TreeNode(6) Root.right.right = TreeNode(8) so=Solution() print(so.Print(Root)) treenode=so.lowestCommonAncestor(Root,Root.left.left,Root.right.right) [[5], [3, 7], [2, 4, 6, 8]] print(treenode.val) 5