题目描述给定一个数组和一个滑动窗口的大小，请找出所有滑动窗口里的最大值。例如，如果输入数组 {2，3，4，6，2，5，1} 及滑动窗口的大小 3，那么一定存在 6 个滑动窗口，它们的最大值分别为 {4，4，6，6，6，5}。  解题思路这个问题最简单的办法自然是暴力求解，每次从一个窗口的起点开始向后遍历k个数字，然后求出最大值，很容易知道这个解法的时间复杂度为O(n^2)，但是题目给定的要求是线性的时间复杂度，也就是O(n)。所以这里自然不能用暴力求解。 实际上，我们可以用一个双端队列来存储当前窗口的最大值。我们创建一个双端队列，这里队列中存储的是窗口最大值的下标。如果队列为空，那么就将当前元...

输入描述： nums = [2,1,5,2,2,3,2]输出描述： 2思路利用阵地攻守法解决，首先让第一个元素占领阵地，然后让剩余元素轮流进攻，当两个元素相同时，计数器加一；元素不同时，同归于尽 计数器减一 让下一个元素占守阵地代码实现 def moreovernums(nums): master = nums[0] count = 1 for i in range(1,len(nums)): if count == 0: master = nums[i] count = 1 elif nums[i] == master: count += 1 else: count -= 1 return ...

题目描述：从数组中移除零元素，且保证非零元素的顺序不能变。 输入示例 nums = [1,3,0,5,2,0,7] , n = 7输出示例 [1,3,5,2,7]代码示例 class Solution: def removezero(self , nums , n): j = 0 for i in range(n): if nums[i] != 0: nums[i],nums[j] = nums[j],nums[i] j += 1

题目描述给定一个非负整数，求它的开方，向下取整。 输入输出样例输入一个整数，输出一个整数。Input: 8Output: 28 的开方结果是 2.82842...，向下取整即是 2。 代码实现 def mySqrt(x): if x == 0: return 0 if x < 4: return 1 start , end = 2 , x//2 while True: mid = start + (end-start)//2 if mid**2 <= x and (mid+1)**2 > x： return mid if mid**2 < x: start = mid ...

1.1 插入操作  从根节点开始，若插入的值比根节点的值小，则将其插入根节点的左子树；若比根节点的值大，则将其插入根节点的右子树。该操作可使用递归进行实现。 程序代码 def insert(self,root,val): if root is None: root = self.TreeNode(val) elif root.val > val: root.left = self.insert(root.left,val) elif root.val < val: root.right = self.insert(root.right,val) return root1.2 查询操...

问题描述有一个矩阵map，它每个格子有一个权值。从左上角的格子开始每次只能向右或者向下走，最后到达右下角的位置，路径上所有的数字累加起来就是路径和，返回所有的路径中最小的路径和。 问题分析假设，一个矩阵map的行数n和列数m，且矩阵中从左上角出发到达第i行，第j列的最小路径为f(i,j)，则：  对于i=0, j=0, 很显然，f(0,0) = map[0][0] 对于第一行元素，即 来说，最小路径为从矩阵左上角出发到达前一位置（第0行，第j-1列）的最小路径 + 当前位置的权值。即,  同理，对于第一列元素，即 来说，最小路径为从矩阵左上角出发到达前一位置（第0列，第i-1行）的最小路径 +...

输入描述：二叉树的前序遍历列表和中序遍历列表代码实现 class TreeNode: def __init__(self,x,left,right): self.val = x self.left = left self.right = right 重构二叉树 def constructTree(preorder,midorder): if len(preorder) == 0: return None root_data = preorder[0] i = midorder.index(root_data) left = constructTree(preorder[1:i+1],midor...

输入描述：从根节点开始，逐层输入每个节点的值，空树或空节点输入为None，比如10，5,15,3,7,13,18输出描述：是二叉搜索树打印True，否则打印False 代码实现 构建树节点 class TreeNode: def __init__(self,val): self.val = val self.left = None self.right = None 重构二叉树 def buildTree(nums,i): if i >= len(nums) or nums[i] == 'None': return None root = TreeNode(nums[i]) root.l...

前序遍历（递归） class Solution: def preorder(self,root): if not root: return [] return [root.val] + [self.preorder(root.left)] + [self.preorder(root.right)]中序遍历（递归） class Solution: def middleorder(self,root): if not root: return [] return [self.middleorder(root.left)] + [root.val] + [self.middleorder(root....

import sys#输入的无论是什么，都会转成字符和字符串 #sys.stdin.readline() 会读取末尾'\n'，加.strip()，去掉回车符，同时去掉前后的空格 # 一 #输入一个数 n = int(sys.stdin.readline().strip()) #输入一个元素，并转成整型int print(n) # 二 #输入有n行(已知行数n)，用for循环，一行有任意个字符字符串都可以 seq = [ ] for i in range(n): line = sys.stdin.readline().strip() #line此时是字符串列表，不知line有多少个元素 valu...

算法要求将一个按照升序排列的有序数组转换为一颗高度平衡的二叉搜索树 代码实现 定义树节点 class TreeNode: def __init__(self,x): self.val = x self.left = None self.right = None 递归实现 class Solution: def sortedArrayToBST(self,nums): if not nums: return None mid = len(nums)//2 root = TreeNode(nums[mid]) root.left = self.sortedArrayToBST(nums[:mid]...

动态规划算法动态规划算法通常用于求解具有某种最优性质的问题。动态规划算法与分治法类似，其基本思想都是将待求解问题分解成若干个子问题，先求解子问题，然后从这些子问题的解得到原问题的解。与分治法不同的是，适合于用动态规划求解的问题，经分解得到的子问题往往不是互相独立的。如果我们能够保存已解决的子问题的答案，而在需要时再找出已求得的答案，这样就可以避免大量的重复计算，节省时间。用一个表（备用表）来记录所有已解的子问题的答案。不管该子问题以后是否被用到，只要它被计算过，就将其结果填入表中。这就是动态规划法的基本思路。问题描述：现存在若干面值为1,5,11,20,50面值的硬币，问兑换总值为N面值有多少...