牛客网左程云BAT课程算法题及解答
第七章二叉树
二叉树1：
-
==请用递归方式实现二叉树的先序，中序和后序的遍历打印。给定一个二叉树的根节点root，请依次返回二叉树的先序，中序和后序遍历。(二维数组的形式)==
//java版本 import java.util.*; /* public class TreeNode { int val = 0; TreeNode left = null; TreeNode right = null; public TreeNode(int val) { this.val = val; } }*/ public class TreeToSequence { public int[][] convert(TreeNode root){ ArrayList<Integer> pre = new ArrayList<Integer>(); ArrayList<Integer> mid = new ArrayList<Integer>(); ArrayList<Integer> back = new ArrayList<Integer>(); preOrder(pre,root); midOrder(mid,root); backOrder(back,root); int[] preArray = pre.stream().mapToInt(Integer::valueOf).toArray(); int[] midArray= mid.stream().mapToInt(Integer::valueOf).toArray(); int[] backArray= back.stream().mapToInt(Integer::valueOf).toArray(); int [][]result = {preArray,midArray,backArray}; return result; } public void preOrder(ArrayList<Integer> pre, TreeNode root){ if (root == null){ return; } pre.add(root.val); preOrder(pre,root.left); preOrder(pre,root.right); return; } public void midOrder(ArrayList<Integer> mid, TreeNode root){ if (root == null){ return; } midOrder(mid,root.left); mid.add(root.val); midOrder(mid,root.right); return; } public void backOrder(ArrayList<Integer> back, TreeNode root){ if (root == null){ return; } backOrder(back,root.left); backOrder(back,root.right); back.add(root.val); return ; } }# python版本 # -*- coding:utf-8 -*- # class TreeNode: # def __init__(self, x): # self.val = x # self.left = None # self.right = None class TreeToSequence: def convert(self,root): pre_seq = [] def preOrder(node): if node is None: return pre_seq.append(node.val) preOrder(node.left) preOrder(node.right) preOrder(root) mid_seq = [] def midOrder(node): if node is None: return midOrder(node.left) mid_seq.append(node.val) midOrder(node.right) midOrder(root) post_seq = [] def postOrder(node): if node is None: return postOrder(node.left) postOrder(node.right) post_seq.append(node.val) postOrder(root) return [pre_seq,mid_seq,post_seq] -
==请用非递归方式实现二叉树的先序、中序和后序的遍历打印。给定一个二叉树的根结点root，请依次返回二叉树的先序，中序和后序遍历(二维数组的形式)。==
//java版本 import java.util.*; /* public class TreeNode { int val = 0; TreeNode left = null; TreeNode right = null; public TreeNode(int val) { this.val = val; } }*/ public class TreeToSequence { public int[][] convert(TreeNode root){ ArrayList<Integer> pre = new ArrayList<Integer>(); ArrayList<Integer> mid = new ArrayList<Integer>(); ArrayList<Integer> back = new ArrayList<Integer>(); preOrder(pre,root); midOrder(mid,root); backOrder(back,root); int[] preArray = pre.stream().mapToInt(Integer::valueOf).toArray(); int[] midArray= mid.stream().mapToInt(Integer::valueOf).toArray(); int[] backArray= back.stream().mapToInt(Integer::valueOf).toArray(); int [][]result = {preArray,midArray,backArray}; return result; } public void preOrder(ArrayList<Integer> pre, TreeNode head){ if (head == null){ return; } //申请一个Stack的结构，将head入栈，弹出时，根据栈的"后进先出"原则，先处理right孩子入栈，再处理left孩子入栈 Stack<TreeNode> resStack = new Stack<TreeNode>(); resStack.push(head); while(!resStack.empty()){ TreeNode top = resStack.pop(); pre.add(top.val); if (top.right != null){ resStack.push(top.right); } if (top.left !=null){ resStack.push(top.left); } } return; } public void midOrder(ArrayList<Integer> mid, TreeNode head){ if (head == null){ return; } //申请一个Stack结构，将head入栈，并将树的左边界节点依次入栈，直到为空，弹出左边界叶子节点，并设置cur节点为弹出节点的right节点，再次进行左边界入栈的后续操作 Stack<TreeNode> resStack = new Stack<TreeNode>(); TreeNode cur = head; while(!resStack.empty() || cur != null){ while(cur != null){ resStack.push(cur); cur = cur.left; } TreeNode leafNode = resStack.pop(); mid.add(leafNode.val); cur = leafNode.right; } return; } //申请一个Stack,压入head,设置RecentNode为head表示最近刚处理过的节点； //设置topNode用来表示每次循环时,栈顶节点, //当栈顶节点的左右孩子都为空(表示该结点为叶子节点,此时弹出该节点,并修改RecentNode) //当栈顶节点的左右孩子都等于过 RecentNode时,表示该节点的左右孩子都被处理过,则根据后续原则,弹出该结点 public void backOrder(ArrayList<Integer> back, TreeNode head){ if (head == null){ return; } Stack<TreeNode> resStack = new Stack<TreeNode>(); resStack.push(head); TreeNode RecentNode = head; TreeNode topNode = null; while(!resStack.empty()){ topNode = resStack.peek(); if(RecentNode != topNode.left && RecentNode != topNode.right && topNode.left != null){ resStack.push(topNode.left); }else if(RecentNode != topNode.right && topNode.right != null){ resStack.push(topNode.right); }else{ TreeNode resNode = resStack.pop(); back.add(resNode.val); RecentNode = resNode; } } return ; } }
# python版本
# -*- coding:utf-8 -*-
# class TreeNode:
# def __init__(self, x):
# self.val = x
# self.left = None
# self.right = None
class TreeToSequence:
def convert(self,root):
pre_seq = []
def preOrder(head):
if head is None:
return
stack = []
stack.append(head)
while (len(stack) > 0):
top = stack.pop()
pre_seq.append(top.val)
if top.right is not None:
stack.append(top.right)
if top.left is not None:
stack.append(top.left)
preOrder(root)
mid_seq = []
def midOrder(head):
if head is None:
return
stack = []
cur = head
while(len(stack) > 0 or cur is not None):
while(cur is not None):
stack.append(cur)
cur = cur.left
top = stack.pop()
mid_seq.append(top.val)
cur = top.right
midOrder(root)
post_seq = []
def postOrder(head):
if head is None:
return
stack = []
stack.append(head)
recentNode = head
while(len(stack) > 0):
top = stack[-1]
if(top.right != recentNode and top.left != recentNode and top.left is not None):
stack.append(top.left)
elif(top.right != recentNode and top.right is not None):
stack.append(top.right)
else:
topNode = stack.pop()
post_seq.append(topNode.val)
recentNode = topNode
postOrder(root)
return [pre_seq,mid_seq,post_seq]
-
==有一棵二叉树，请设计一个算法，按照层次打印这棵二叉树。给定二叉树的根结点root**，请返回打印结果，结果按照每一层一个数组进行储存，所有数组的顺序按照层数从上往下，且每一层的数组内元素按照从左往右排列。保证结点数小于等于500。**==
# -*- coding:utf-8 -*- # class TreeNode: # def __init__(self, x): # self.val = x # self.left = None # self.right = None class TreePrinter: def printTree(self, root): # write code here res =[] # 存储最终结果集 queue = [] # 模拟队列 temp = [] # 存储当前层的结果 last = root # 标识当前层的结束标志 nextLast = root # 标识最新进入的节点，同时表示下一行的结束标志 queue.append(root) while(len(queue) > 0): # 弹出队头 Front = queue[0] temp.append(Front.val) queue.remove(Front) if Front.left is not None: queue.append(Front.left) nextLast = Front.left if Front.right is not None: queue.append(Front.right) nextLast = Front.right # 判断是否到达当前行的结束标志 if last == Front: res.append(temp) last = nextLast # 清空存储当前行的列表 temp = [] return res -
==首先我们介绍二叉树先序序列化的方式，假设序列化的结果字符串为str，初始时str等于空字符串。先序遍历二叉树，如果遇到空节点，就在str的末尾加上“#!”，“#”表示这个节点为空，节点值不存在，当然你也可以用其他的特殊字符，“!”表示一个值的结束。如果遇到不为空的节点，假设节点值为3，就在str的末尾加上“3!”。现在请你实现树的先序序列化。给定树的根结点root，请返回二叉树序列化后的字符串。==
# -*- coding:utf-8 -*-
# class TreeNode:
# def __init__(self, x):
# self.val = x
# self.left = None
# self.right = None
class TreeToString:
def toString(self, root):
# 前序遍历序列化结果
def preSerialize(root):
# write code here
res = "" # 存储序列化结果
if root is None:
return res
treeStack = [] # 使用栈的方式进行先序遍历
treeStack.append(root)
while(len(treeStack) > 0):
top = treeStack.pop()
if top is not None:
# 如果栈顶元素非空 则计入结果集, 并将该结点的右左孩子入栈
res = res + str(top.val) + "!"
treeStack.append(top.right)
treeStack.append(top.left)
else:
# 如果该结点为空 结果进行格式化计入 并且不产生子节点
res = res + "#!"
return res
preRes = preSerialize(root)
return preRes
# 中序遍历序列化结果
def midSerialize(root):
res = "" # 存储序列化结果
if root is None:
return res
cur = root
treeStack = [] # 使用栈的方式进行中序遍历
while(len(treeStack) > 0 or cur is not None):
while(cur is not None):
treeStack.append(cur)
cur = cur.left
res = res + "#!" # 遇到左边界Null的叶子节点
top = treeStack.pop()
res = res + str(top.val) + "!"
cur = top.right # 处理Stack顶部节点的Right节点
res = res + "#!" # 整棵树的最后处理的右边界子节点的right-Null节点
return res
midRes = midSerialize(root)
# 后序遍历序列化结果
def backSerialize(root):
# write code here
res = "" # 存储序列化结果
treeStack = [] # 使用栈进行后续遍历
recentNode = root # 声明一个最近处理过的节点变量：每次res改变时 更新recentNode内容
treeStack.append(root) # 头节点入栈
while (len(treeStack) > 0):
topNode = treeStack[-1] # 获取栈顶节点
# 判断栈顶节点的子节点是否被处理 - 首先判断leftChild节点
if topNode.left != recentNode and topNode.right != recentNode:
if topNode.left is not None:
# 非空入栈到栈顶等待处理
treeStack.append(topNode.left)
else:
# 若leftChild节点为None 考虑rightChild节点情况
res = res + "#!"
# rightChild非空 则recentNode为 topNode.left 且topNode.right入栈
if topNode.right is not None:
recentNode = topNode.left
treeStack.append(topNode.right)
# rightChild为空 则recentNode为 topNode.right：
# 关于rightChild的节点的判断，更新完成需要改变recentNode: 当rightChild孩子节点处理完成后，即当前topNode将在下个循环中pop
else:
res = res + "#!"
recentNode = topNode.right
# topNode的左右节点都为非空且 leftChild入栈时 判断rightChild是否被处理
elif topNode.right != recentNode:
if topNode.right is not None:
treeStack.append(topNode.right)
else:
# 关于rightChild的节点的判断，更新完成需要改变recentNode: 当rightChild孩子节点处理完成后，即当前topNode将在下个循环中pop
res = res + "#!"
recentNode = topNode.right
# 栈顶元素出栈表示：topNode的左右子节点都已经处理完成或 左右孩子节点都为None
else:
popNode = treeStack.pop()
res = res + str(popNode.val) + "!"
recentNode = popNode
return res
==二叉树的子树：在二叉树中以任何一个节点为头的整棵树称作二叉树的子树==
==平衡二叉树：==
- 空树是平衡二叉树
- 如果一棵树不为空，并且其中所有的子树都满足各自的左子树与右子树的高度差都不超过1
==搜索二叉树：==每颗子树的头节点的值都比各自左子树上的所有节点值要大，也都比各自右子树上所有节点值要小。
搜索二叉树按照中序遍历得到的序列，一定是从小到大排列的。红黑树、平衡搜索二叉树（AVL树）等，其实都是搜索二叉树的不同实现。
判断是否是搜索二叉树：->改写二叉树的中序遍历，遍历到每个节点的值时，如果一直比上一个遍历的节点值要大，则是搜索二叉树。否则，不是搜索二叉树。
**满二叉树：**满二叉树是除了最后一层的节点无任何子节点外，剩下每一层上的节点都有两个子节点。==满二叉树的层数记为L，节点树记为N，则N = 2.^L -1， L = log2(N+1)==
**完全二叉树：**完全二叉树是指除了最后一层之外，其他每一层的节点都是满的。最后一层如果也满了，则是一颗满二叉树，也是完全二叉树，最后一层如果不满，缺少的节点也全部的集中在右边，那也是一颗完全二叉树。
**后继节点：**一个节点的后继节点是指，这个节点在中序遍历序列中的下一个节点。现有一种新的二叉树节点类型，定义如下：
public class Node{
public int value;
public Node left;
public Node right;
public Node parent;
public Node(int data){
this.value = data
}
}
该结构比普通二叉树节点结构多了一个指向父节点的parent指针，假设有一颗这种类型的节点组成的二叉树，树中每个节点的parent指针都正确地指向自己的父节点，头节点的parent指向空。只给定在二叉树中的某个节点node，该节点不一定是头节点，可能是书中任何一个节点，请实现返回node的后继节点的函数。
==普通方法：==
-
通过node节点的parent指针不断向上找到头节点。
-
通过找到的头节点，做整棵树的中序遍历，生成中序遍历序列。
-
在中序遍历序列中，node节点的下一个节点，就是其后续节点
普通方法要遍历所有节点，时间复杂度为O(N)，额外空间复杂度为O(N)
==最优解法：==
如果node节点和node后继节点之间的实际距离为L，最优解法只走过L个节点，时间复杂度为O(L)，额外空间复杂度为O(1).
-
情况一：如果node有右子树，那么后继节点就是右子树上最左边的节点
-
情况二：如果node没有右子树，那么先看node是不是node父节点的左孩子，如果是左孩子，那么此时node的父节点就是node的后继节点。如果是有孩子，就向上寻找node的后继节点，假设向上移动到的节点记为s，s的父节点记为p，如果发现s是p的左孩子，那么节点p就是node节点的后继节点，否则就一一直向上移动。
-
情况三：如果一直向上寻找，移动到空节点，仍然没有发现node的后继节点，说明node根本不存在后继节点，返回空即可。
-
==有一棵二叉树，请设计一个算法判断这棵二叉树是否为平衡二叉树。给定二叉树的根结点root，请返回一个bool值，代表这棵树是否为平衡二叉树。==
# -*- coding:utf-8 -*-
# class TreeNode:
# def __init__(self, x):
# self.val = x
# self.left = None
# self.right = None
class CheckBalance:
def check(self, root):
# write code here
def getHeight(head, level,res):
if head is None:
return level
# 获得当前递归层节点的左子树可到达的最大深度
LH = getHeight(head.left,level + 1,res)
if not res[0]:
return level
# 获得当前递归层节点的右子树可到达的最大深度
RH = getHeight(head.right,level + 1,res)
if not res[0]:
return level
# 判断当前递归层节点的左右子树的最大深度差
if abs(LH - RH) > 1:
res[0] = False
# 始终返回当前递归层节点的最大子树深度
return max(LH,RH)
res = []
res.append(True)
# 默认树的头节点深度为 1
getHeight(root, 1, res)
return res[0]
-
==有一棵二叉树,请设计一个算法判断它是否是完全二叉树。给定二叉树的根结点root，请返回一个bool值代表它是否为完全二叉树。树的结点个数小于等于500。==
# -*- coding:utf-8 -*- # class TreeNode: # def __init__(self, x): # self.val = x # self.left = None # self.right = None class CheckCompletion: def chk(self, root): # write code here if root is None: return True # 叶子节点标志是否开启 leafFlag = False # 是否为完全二叉树结果 compFlag = True # 使用队列对二叉树进行按层遍历 queue = [] # 根节点入队 queue.append(root) while (len(queue) > 0): # 头节点出队 front = queue[0] queue.remove(front) if not leafFlag: # 当leaf标志未打开 表示剩余节点可以不是叶子节点 # 若当前出队节点左右节点都为 not None 则都入队 # 若左节点not None 右节点 None: 打开leafFlag # 若左节点为None 且右节点 not None 则返回False # 若左节点None 右节点 None :打开leafFlag if front.left is not None: queue.append(front.left) if front.right is not None: queue.append(front.right) else: leafFlag = True else: if front.right is not None: compFlag = False return compFlag else: leafFlag = True else: # 当leaf标志打开时 front节点存在子节点 则直接返回False if front.left is not None or front.right is not None: compFlag = False return compFlag return compFlag -
==请把纸条竖着放在桌⼦上，然后从纸条的下边向上⽅对折，压出折痕后再展 开。此时有1条折痕，突起的⽅向指向纸条的背⾯，这条折痕叫做“下”折痕 ；突起的⽅向指向纸条正⾯的折痕叫做“上”折痕。如果每次都从下边向上⽅ 对折，对折N次。请从上到下计算出所有折痕的⽅向。给定折的次数n,请返回从上到下的折痕的数组，若为下折痕则对应元素为"down",若为上折痕则为"up"==
# -*- coding:utf-8 -*- class FoldPaper: def foldPaper(self, n): # write code here if n == 1: return ["down"] def my_function(k,strValue): # 递归函数的返回体 if k == 1: return [strValue] # 函数向下递归部分 + 函数递归体中的剩余部分 # 当前层的return 语句： 内容包括了从递归体的第一次返回到当前返回的所有内容 return my_function(k-1, "down") + [strValue] + my_function(k-1,"up") return my_function(n,"down") -
==一棵二叉树原本是搜索二叉树，但是其中有两个节点调换了位置，使得这棵二叉树不再是搜索二叉树，请找到这两个错误节点并返回他们的值。保证二叉树中结点的值各不相同。给定一棵树的根结点，请返回两个调换了位置的值，其中小的值在前。==
# -*- coding:utf-8 -*- # class TreeNode: # def __init__(self, x): # self.val = x # self.left = None # self.right = None import sys class FindErrorNode: def findError(self, root): # write code here def midOrder(head): if head is None: return # 记录当前遍历所有结果中的最大值 minValue = -sys.maxsize -1 # 使用栈结构 + while非递归方式 对tree进行中序遍历 treeStack = [] # 保存结果数值 res = [] cur = head while len(treeStack) > 0 or cur is not None: while cur is not None: treeStack.append(cur) cur = cur.left top = treeStack.pop() # 判断出现降序的次数 if top.val > minValue: minValue = top.val else: if len(res) > 0: # 第二次降序 保存小值到res[1] res[1] = top.val else: # 第一次降序 保存max到res[0] 保存min到res[1] res.append(minValue) res.append(top.val) minValue = top.val cur = top.right # 错误节点数值进行升序排列 return sorted(res) return midOrder(root) -
==从二叉树的节点A出发，可以向上或者向下走，但沿途的节点只能经过一次，当到达节点B时，路径上的节点数叫作A到B的距离。对于给定的一棵二叉树，求整棵树上节点间的最大距离。给定一个二叉树的头结点root，请返回最大距离。保证点数大于等于2小于等于500.==
# -*- coding:utf-8 -*- # class TreeNode: # def __init__(self, x): # self.val = x # self.left = None # self.right = None class LongestDistance: def findLongest(self, root): if root is None: return 0 # 返回以当前节点为根节点的，到达最远叶结点之间的距离 def my_function(root): if root is None: return 0 left = my_function(root.left) right = my_function(root.right) return max(left,right) + 1 # 判断整棵树的左右子树分别到达叶结点的最远距离 # 并与跨过root节点的左右子树的节点之间的距离进行比较，返回最大值 def Longest(root): if root is None: return 0 leftLongest = Longest(root.left) rightLongest = Longest(root.right) crossRoot = my_function(root.left) + my_function(root.right) + 1 return max(leftLongest, rightLongest, crossRoot) # write code here return Longest(root) -
==有一棵二叉树，其中所有节点的值都不一样,找到含有节点最多 的搜索二叉子树,并返回这棵子树的头节点。给定二叉树的头结点root，请返回所求的头结点,若出现多个节点最多的子树，返回头结点权值最大的。==
以节点node为头的树中，最大的搜索二叉树只能来自以下两种情况：
- 来自node左子树上的最大搜索二叉子树是以node左孩子为头的，并且来自node右子树上的最大搜索二叉子树是以node右孩子为头的，node左子树上的最大搜索二叉子树的最大值小于node的节点值，node右子树上的最大搜索二叉子树的最小值大于node的节点值，那么以节点node为头的整棵树都是搜索二叉树。
- 如果不满足第一种情况，说明以节点node为头的树整体不能连成搜索二叉树。这种情况下，以node为头的树上的最大搜索二叉子树是来自node左子树的最大搜索二叉子树和来自node的右子树上的最大搜索二叉树之间，节点数较多的那个。
求解：
-
整体过程是二叉树的后序遍历
-
遍历到当前节点记为cur时，先遍历cur的左子树并收集4个信息，分别是左子树上，==最大搜索二叉子树的头节点==、==节点数==、==树上的最小值和最大值==；再遍历cur的右子树收集4个信息，分别是==右子树上最大搜索二叉子树的头节点==、==节点数==、==最小值==和==最大值==。
-
根据步骤二收集到的信息，判断是否满足第一种情况，也就是是否以cur为头的子树，整体都是搜索二叉树。如果满足第一种情况，就返回cur节点，如果满足第二种情况，就返回左子树和右子树各自的最大搜索二叉树中，节点数较多的那个树的头节点。
-
对于如何返回4个信息，可以使用全局变量更新的方式实现。
# -*- coding:utf-8 -*- # class TreeNode: # def __init__(self, x): # self.val = x # self.left = None # self.right = None class MaxSubtree: def getMax(self, root): # write code here def getM(cur): if cur is None: # 返回： 节点， 子树上的节点个数，子树上的最大值， 子树上的最小值 return [None,0,-0x80000000,0x7fffffff] # 获得cur节点的左右孩子的信息 t1,t2 = getM(cur.left), getM(cur.right) # 得到以cur节点为root节点的子树的 最大值与最小值 _max, _min = max(t1[2],t2[2],cur.val), min(t1[3],t2[3],cur.val) # 得到以cur节点为root节点的子树的 左子树与右子树 头节点以及 子树上所含节点个数 p,q,x1,x2 = t1[0],t2[0],t1[1],t2[1] # 判断是否满足第一种情况： 包含cur的最大搜索二叉树 if cur.left == p and cur.right == q and t1[2] < cur.val < t2[3]: return cur, x1+x2+1, _max, _min # 不满足第一种情况时： 得到当前子树的左右子树的最大二叉搜索树信息 res1, res2 = [p, x1, _max, _min], [q, x2, _max, _min] # 根据节点数返回 if x1 > x2: return res1 if x1 < x2: return res2 # 根据头节点的值大小返回 if p.val >= q.val: return res1 return res2 return getM(root)[0] -
==位运算：算术运算的常见操作符号：+-*/，位运算的常见操作符：& | ^ ~ << >> >>>==
- 不安全网页的黑名单包含100亿个黑名单网页，每个网页的URL最多占用64字节，现在想要实现一种网页过滤系统，可以根据网页的URL判断该网页是否在黑名单上，请设计还系统，要求该系统允许有万分之一以下的判断失误率，并使用的额外空间不要超过30G.==网页黑名单系统、垃圾邮件过滤系统、爬虫的网址判断重复系统、容忍一定程度的失误率，对空间要求严格-> 布隆过滤器。==
- ==布隆过滤器可精确的代表一个集合，可精确判断某一元素是否在此集合中。精确程度由用户的具体设计决定，精确度小于100%==
-
==请编写一个算法，不用任何额外变量交换两个整数的值。给定一个数组num，其中包含两个值，请不用任何额外变量交换这两个值，并将交换后的数组返回。==
# -*- coding:utf-8 -*-
class Swap: def getSwap(self, num): # write code here # 使用异或符号 ^ 完成 a = num[0] b = num[1] a = a ^ b b = a ^ b a = a ^ b num[0] = a num[1] = b return num ```
-
==对于两个32位整数a和b，请设计一个算法返回a和b中较大的。但是不能用任何比较判断。若两数相同，返回任意一个.给定两个整数a和b，请返回较大的数。==
# -*- coding:utf-8 -*- class Compare: def getMax(self, a, b): # write code here # 正数返回 1 负数返回 0 def sign(num): return flip((num >> 31) & 1) def flip(num): return num ^ 1 # 获得a b a-b 的符号 sigA = sign(a) sigB = sign(b) c = a - b sigC = sign(c) # 判断ab是否同号 difab = sigA ^ sigB sameab = flip(difab) # 若ab同号 结果a-b为正：1 则 a大 若a-b结果为负：0 返回b # 若ab异号 则a为正时 返回a a为负时 返回b returnA = difab * sigA + sameab * sigC returnB = flip(returnA) return returnA * a + returnB * b -
==有一个整型数组A，其中只有一个数出现了奇数次，其他的数都出现了偶数次，请打印这个数。要求时间复杂度为O(N)，额外空间复杂度为O(1)。给定整形数组A及它的大小n，请返回题目所求数字。==
# -*- coding:utf-8 -*- class OddAppearance: def findOdd(self, A, n): # write code here # 异或符号的交换律和结合律 res = 0 for i in range(0,n): res = res ^ A[i] return res -
==给定一个整型数组arr，其中有两个数出现了奇数次，其他的数都出现了偶数次，找到这两个数。要求时间复杂度为O(N)，额外空间复杂度为O(1).给定一个整形数组arr及它的大小n，请返回一个数组，其中两个元素为两个出现了奇数次的元素,请将他们按从小到大排列。==
# -*- coding:utf-8 -*- class OddAppearance: def findOdds(self, arr, n): # write code here # 两个不同的数字的异或结果： 32位上一定出现一个1：两个数字的该位：1-0 # location：返回从右往左发现的1的位置 def location(num): rightOffset = 0 if num % 2 == 1: return rightOffset else: rightOffset = rightOffset + 1 num = num >> 1 return rightOffset res = [] # 第一遍异或 得到 两个单独数字num1 与num2的异或结果 # 得到出现相异的位置index resOR = 0 for i in range(0, n): resOR = resOR ^ arr[i] index = location(resOR) # 将所有的index位置上为1的数字与0进行异或 得到两个单独数字的index位为1的数 num1 = 0 for i in range(0, n): if (arr[i] >> index) % 2 == 1: num1 = num1 ^ arr[i] # 通过异或 得到另外一个数字 num2 = num1 ^ resOR res.append(num1) res.append(num2) return sorted(res) -
==在XxY的方格中，以左上角格子为起点，右下角格子为终点，每次只能向下走或者向右走，请问一共有多少种不同的走法。给定两个正整数int x,int y，请返回走法数目。保证x＋y小于等于12。==
class Robot: def countWays(self, x, y): # write code here # 左上角方格移动到右下角终点： 认定从左上角方格的右下角为起始点 x = x - 1 y = y - 1 all = x + y def zuhechangdu(all,x): num1 = 1 for i in range(0, x): num1 = num1 * all all = all - 1 return num1 def jiecheng(x): num2 = 1 for i in range(0, x): num2 = num2 * (x - i) return num2 num1 = zuhechangdu(all,x) num2 = jiecheng(x) return num1 / num2 -
==n个人站队，他们的编号依次从1到n，要求编号为a的人必须在编号为b的人的左边，但不要求一定相邻，请问共有多少种排法？第二问如果要求a必须在b的左边，并且一定要相邻，请问一共有多少种排法？给定人数n及两个人的编号a和b，请返回一个两个元素的数组，其中两个元素依次为两个问题的答案。保证人数小于等于10。==
# -*- coding:utf-8 -*- class StandInLine: def getWays(self, n, a, b): # write code here def jiecheng(x): num = 1 for i in range(0,x): num = num * (x - i) return num res = [] # 不要求一定相邻 res.append(jiecheng(n) / 2) # 要求一定相邻 res.append(jiecheng(n-1)) return res -
==A(A也是他的编号)是一个孤傲的人，在一个n个人(其中编号依次为1到n)的队列中，他于其中的标号为b和标号c的人都有矛盾，所以他不会和他们站在相邻的位置。现在问你满足A的要求的对列有多少种？给定人数n和三个人的标号A,b和c，请返回所求答案，保证人数小于等于11且大于等于3。==
# -*- coding:utf-8 -*- class LonelyA: def getWays(self, n, A, b, c): # write code here def jiecheng(x): num = 1 for i in range(0,x): num = num * (x - i) return num # 一组数n个 a不与b和c相邻的排列数 res = jiecheng(n) - 2 * jiecheng(n-1) - 2 * jiecheng(n-1) + 2 * jiecheng(n-2) return res -
==n颗相同的糖果，分给m个人，每人至少一颗，问有多少种分法。给定n和m，请返回方案数，保证n小于等于12，且m小于等于n。==
# -*- coding:utf-8 -*- class Distribution: def getWays(self, n, m): # write code here def jiecheng(x): num = 1 for i in range(0,x): num = num * (x - i) return num def zuhe(su,x): num = 1 for i in range(0,x): num = num * su su = su - 1 return num # n个东西分给m个人，每人至少1个：隔板问题，返回结果：C(n-1,m-1) return zuhe(n-1, m-1) / jiecheng(m-1)-
卡特兰数
-
==假设有n对左右括号，请求出合法的排列有多少个？合法是指每一个括号都可以找到与之配对的括号，比如n=1时，()是合法的，但是)(为不合法。给定一个整数n，请返回所求的合法排列数。保证结果在int范围内。==
# -*- coding:utf-8 -*- class Parenthesis: def countLegalWays(self, n): # write code here # 卡特兰数问题 结果为 1/n+1 * C(2n,n) if n == 1: return 0 def jiecheng(x): num = 1 for i in range(0, x): num = num * (x - i) return num def zuhe(su, x): num = 1 for i in range(x): num = num * su su = su - 1 return num return (zuhe(2 * n, n) / jiecheng(n)) / (n + 1) -
==n个数进出栈的顺序有多少种？假设栈的容量无限大。给定一个整数n，请返回所求的进出栈顺序个数。保证结果在int范围内==
# -*- coding:utf-8 -*- class Stack: def countWays(self, n): # write code here def jiecheng(x): num = 1 for i in range(0, x): num = num * (x - i) return num def zuhe(su, x): num = 1 for i in range(x): num = num * su su = su - 1 return num return (zuhe(2 * n, n) / jiecheng(n)) / (n + 1) -
==2n个人排队买票，n个人拿5块钱，n个人拿10块钱，票价是5块钱1张，每个人买一张票，售票员手里没有零钱，问有多少种排队方法让售票员可以顺利卖票。给定一个整数n，请返回所求的排队方案个数。保证结果在int范围内。==
# -*- coding:utf-8 -*- class BuyTickets: def countWays(self, n): # write code here def jiecheng(x): num = 1 for i in range(0, x): num = num * (x - i) return num def zuhe(su, x): num = 1 for i in range(x): num = num * su su = su - 1 return num return (zuhe(2 * n, n) / jiecheng(n)) / (n + 1) -
==求n个无差别的节点构成的二叉树有多少种不同的结构？给定一个整数n，请返回不同结构的二叉树的个数。保证结果在int范围内。==
# -*- coding:utf-8 -*- # f(0) = 1; f(1) = 1 ; f(2) = 2; f(3) =5 # f(n) = f(0) *f(n-1) + f(1) *f(n-2) +...+ f(n-1) *f(0) = C(2n,n) *(1/ (n+1)) class TreeCount: def countWays(self, n): # write code here def jiecheng(x): num = 1 for i in range(0, x): num = num * (x - i) return num def zuhe(su, x): num = 1 for i in range(x): num = num * su su = su - 1 return num return (zuhe(2 * n, n) / jiecheng(n)) / (n + 1) -
==12个高矮不同的人，排成两排，每排必须是从矮到高排列，而且第二排比对应的第一排的人高，问排列方式有多少种？给定一个偶数n，请返回所求的排列方式个数。保证结果在int范围内。==
# -*- coding:utf-8 -*- class HighAndShort: def countWays(self, n): # write code here def jiecheng(x): num = 1 for i in range(0, x): num = num * (x - i) return num def zuhe(su, x): num = 1 for i in range(x): num = num * su su = su - 1 return num return (zuhe(n, n / 2) / jiecheng(n / 2)) / (n /2 + 1) -
==有n个信封，包含n封信，现在把信拿出来，再装回去，要求每封信不能装回它原来的信封，问有多少种装法?给定一个整数n，请返回装发个数，为了防止溢出，请返回结果Mod 1000000007的值。保证n的大小小于等于300。==
# -*- coding:utf-8 -*- class CombineByMistake: def countWays(self, n): # write code here # 迭代公式 # D[1] = 0 if n == 1: return 0 # D[2] = 1 elif n == 2: return 1 value = [] # n > 2时, D[n] = (n-1) * (D[n-1] + D[n-2]) value.append(0) value.append(1) for i in range(2,n): res = i * (value[i-1] + value[i-2]) res = res % 1000000007 value.append(res) return value[n-1]
-
-
-
==概率==
-
==有2k只球队，有k-1个强队，其余都是弱队，随机把它们分成k组比赛，每组两个队，问两强相遇的概率是多大？给定一个数k，请返回一个数组，其中有两个元素，分别为最终结果的分子和分母，请化成最简分数==
# -*- coding:utf-8 -*- class Championship: def calc(self, k): # write code here def sumTeam(k): num = 1 for i in range(0, k): num = num * (2 * (k - i - 1) + 1) return num def jiecheng(k): num = 1 for i in range(0, k): num = num * (k - i) return num def zuhe(su, k): num = 1 for i in range(0, k): num = num * su su = su - 1 return num def swTeam(k): suw_u = zuhe(k + 1, k - 1) suw_d = jiecheng(k - 1) pailie = jiecheng(k - 1) return suw_u / suw_d * pailie def commonDivisor(a, b): if a % b == 0: return b else: return commonDivisor(b, a % b) res = [] d_value = sumTeam(k) u_value = d_value - swTeam(k) # 最大公约数不分前后 当k=2时 结果为 [0,1] 此时可以设置取余函数输入(0,1)而不是(1,0) # 因为 0 % 1 = 0 而 1 % 0不合法 commonDivisorValue = commonDivisor(u_value, d_value) res.append(u_value / commonDivisorValue) res.append(d_value / commonDivisorValue) return res -
==n只蚂蚁从正n边形的n个定点沿着边移动，速度是相同的，问它们碰头的概率是多少？给定一个正整数n，请返回一个数组，其中两个元素分别为结果的分子和分母，请化为最简分数。==
# -*- coding:utf-8 -*- class Ants: def collision(self, n): # write code here # 蚂蚁问题 返回 （1/2的n-1次方） def function(n): num = 1 for i in range(0,n): num = num * 2 return num res = [] d_value = function(n-1) u_value = d_value - 1 res.append(u_value) res.append(d_value) return res -
==给定一个等概率随机产生1
5的随机函数，除此之外，不能使用任何额外的随机机制，请实现等概率随机产生17的随机函数。(给定一个可调用的Random5::random()方法,可以等概率地随机产生1～5的随机函数)==# -*- coding:utf-8 -*- import random; class Random5: @staticmethod def randomNumber(): return random.randint(0,1000000) % 5 + 1 class Random7: # 随机产生[1,5] def rand5(self): return Random5.randomNumber() # 请通过self.rand5()随机产生[1,7] def randomNumber(self): # return self.rand5() % 7 # 取等概率连续的 7(7的倍数个数字即可) # 组合产生 0-24之间的数字 value_020 = (self.rand5() - 1) * 5 + self.rand5()-1 # 取0-20一共21个数 :取的值域范围越大 -> 运行时间越短 大于20 等价于 小于4 while value_020 < 4: value_020 = (self.rand5() - 1) * 5 + self.rand5()-1 # 取14个数： 11- 24 # while value_020 < 11: # value_020 = (self.rand5() - 1) * 5 + self.rand5()-1 res = value_020 % 7 + 1 return res -
==给定一个以p概率产生0，以1-p概率产生1的随机函数RandomP::f()，p是固定的值，但你并不知道是多少。除此之外也不能使用任何额外的随机机制，请用RandomP::f()实现等概率随机产生0和1的随机函数。==
# -*- coding:utf-8 -*- import random p = random.random() class RandomP: @staticmethod def f(): return 0 if random.random() < p else 1 class Random01: def random01(self): # 通过randomP.f()来实现01等概率 res = "" + str(RandomP.f()) + str(RandomP.f()) while True: if res == "01": return 0 elif res == "10": return 1 res = "" + str(RandomP.f()) + str(RandomP.f()) -
==假设函数f()等概率随机返回一个在[0,1)范围上的浮点数，那么我们知道，在[0,x)区间上的数出现的概率为x(0<x≤1)。给定一个大于0的整数k，并且可以使用f()函数，请实现一个函数依然返回在[0,1)范围上的数，但是在[0,x)区间上的数出现的概率为x的k次方。==
# -*- coding:utf-8 -*- import random; class RandomSeg: def f(self): return random.random() # 请通过调用f()实现 # 返回k次中最大的数： # 一次实验，产生x0 P{x0 < X} = x; 二次实验，产生x1,x2同时满足P{x1<X} P{x2<X} # 等价于 x1 x2中最大数 <X，此时概率为x^2 def random(self, k, x): res = -1 for i in range(0,k): temp = self.f() if res < temp: res = temp return res -
==给定一个长度为N且没有重复元素的数组arr和一个整数M，实现函数等概率随机打印arr中的M个数。==
# -*- coding:utf-8 -*- import random; class RandomPrint: def rprint(self, arr, N, M): # write code here # 类似于买彩票的等可能概率事件 res = [] random.randint(1, 1) # 循环M次获得 M个结果数字 for i in range(0,M): # 在1 -> N-i 个数中随机取一个值 index = random.randrange(0,N-i) # 加入返回结果列表 res.append(arr[index]) # 将取到的值放入数组末尾 下次取值有效范围不考虑该数字池 temp = arr[N-i-1] arr[N-i-1] = arr[index] arr[index] = temp return res -
==有一个机器按自然数序列的方式吐出球，1号球，2号球，3号球等等。你有一个袋子，袋子里最多只能装下K个球，并且除袋子以外，你没有更多的空间，一个球一旦扔掉，就再也不可拿回。设计一种选择方式，使得当机器吐出第N号球的时候，你袋子中的球数是K个，同时可以保证从1号球到N号球中的每一个，被选进袋子的概率都是K/N。举一个更具体的例子，有一个只能装下10个球的袋子，当吐出100个球时，袋子里有10 球，并且1
100号中的每一个球被选中的概率都是10/100。然后继续吐球，当吐出1000个球时，袋子里有 10 个球，并且11000号中的每一个球被选中的概率都是10/1000。继续吐球，当吐出i个球时，袋子里有10个球，并且1i号中的每一个球被选中的概率都是10/i。也就是随着N的变化，1N号球被选中的概率动态变化成k/N。请将吐出第N个球时袋子中的球的编号返回。==# -*- coding:utf-8 -*- import random; class Bag: selected = [] def __init__(self): self.selected = [] # 每次拿一个球都会调用这个函数，N表示第i次调用 def carryBalls(self, N, k): # 判断k个位置是否已经放满 for i in range(0,min(N,k)): self.selected.append(i) # 对第N个进行处理，若k未满，继续放入 if N < k: self.selected.append(N) # 若已满，则随机去除一个并放入第N个 else: randValue = random.uniform(0, 1) if randValue < (1 / N): index_delete = random.randint(0, k-1) self.selected[index_delete] = N return self.selected
-
-
==有数组penny，penny中所有的值都为正数且不重复。每个值代表一种面值的货币，每种面值的货币可以使用任意张，再给定一个整数aim(小于等于1000)代表要找的钱数，求换钱有多少种方法。给定数组penny及它的大小(小于等于50)，同时给定一个整数aim，请返回有多少种方法可以凑成aim。==
# -*- coding:utf-8 -*- class Exchange: def countWays(self, penny, n, aim): # write code here # 声明一个n * [aim +1] 的dp 数组 dplists = [[0 for i in range(aim + 1)] for i in range(n)] # 填充第一行与第一列 for i in range(0, aim + 1): if i % penny[0] == 0: dplists[0][i] = 1 for i in range(0, n): dplists[i][0] = 1 # 填充剩余位置 for i in range(1, n): for j in range(1, aim + 1): # 判断是否能使用 当前行对应的货币 if penny[i] > j: # 改行货币面值太大无法使用 dplists[i][j] = dplists[i - 1][j] else: # dplists[i][j] = 不使用改行货币值方法数 + 使用改行货币值方法数 dplists[i][j] = dplists[i - 1][j] + dplists[i][j - penny[i]] return dplists[n - 1][aim]-
==有n级台阶，一个人每次上一级或者两级，问有多少种走完n级台阶的方法。为了防止溢出，请将结果Mod 1000000007给定一个正整数int n，请返回一个数，代表上楼的方式数。保证n小于等于100000。==
# -*- coding:utf-8 -*- class GoUpstairs: def countWays(self, n): # write code here # f(1) = 1 f(2) = 2; f(n) = f(n-1) + f(n-2):n >= 3时 # 使用数组存储 #res = [0 for i in range(n)] #res[0] = 1 #res[1] = 2 #for i in range(2,n): #res[i] = (res[i-1] + res[i-2]) % 1000000007 #return res[n-1] # 使用变量返回 if n == 1: return 1 if n == 2: return 2 F1 = 1 F2 = 2 res = 0 for i in range(2,n): res = (F1 + F2) % 1000000007 F1 = F2 F2 = res return res-
==有一个矩阵map，它每个格子有一个权值。从左上角的格子开始每次只能向右或者向下走，最后到达右下角的位置，路径上所有的数字累加起来就是路径和，返回所有的路径中最小的路径和。给定一个矩阵map及它的行数n和列数m**，请返回最小路径和。保证行列数均小于等于100.**==
# -*- coding:utf-8 -*- class MinimumPath: def getMin(self, mmap, n, m): # write code here # 定义dplists保存最小权值 dplists = [ [0 for i in range(m)] for i in range(n)] dplists[0][0] = mmap[0][0] # 处理第一行与第一列数据 for i in range(1,m): dplists[0][i] = dplists[0][i-1] + mmap[0][i] for i in range(1,n): dplists[i][0] = dplists[i-1][0] + mmap[i][0] # 处理剩余空位 for i in range(1,n): for j in range(1,m): #当前位置的最小权值 = min(到达上方格子代价,到达左方格子代价) + 当前格子代价 dplists[i][j] = min(dplists[i-1][j],dplists[i][j-1]) + mmap[i][j] return dplists[n-1][m-1] -
==这是一个经典的LIS(即最长上升子序列)问题，请设计一个尽量优的解法求出序列的最长上升子序列的长度。给定一个序列A及它的长度n**(长度小于等于500)，请返回LIS的长度。**==
# -*- coding:utf-8 -*- class LongestIncreasingSubsequence: def getLIS(self, A, n): # write code here # 方法一： dplists = [1 for i in range(n)] for i in range(1,n): # 记录小于当前值A[i]的所有index对应的dplists的最大值 for j in range(0,i): if A[j] < A[i] and dplists[j] >= dplists[i]: dplists[i] = dplists[j] + 1 # 方法二： # dplists = [1 for i in range(n)] # for i in range(1, n): # dp_max = 0 # 记录小于当前值A[i]的所有index对应的dplists的最大值 # for j in range(0, i): # if A[j] < A[i] and dplists[j] >= dp_max: # dp_max = dplists[j] # dplists[i] = dp_max + 1 return max(dplists) -
==给定两个字符串A和B，返回两个字符串的最长公共子序列的长度。例如，A="1A2C3D4B56”，B="B1D23CA45B6A”，”123456"或者"12C4B6"都是最长公共子序列。给定两个字符串A和B**，同时给定两个串的长度n和m，请返回最长公共子序列的长度。保证两串长度均小于等于300。**==
# -*- coding:utf-8 -*- class LCS: def findLCS(self, A, n, B, m): # write code here # dplists存储动态规划的值 n*m dplists = [[0 for i in range(m)] for i in range(n)] # 处理第一行与第一列的值 if A[0] == B[0]: dplists[0][0] = 1 for i in range(1,m): if A[0] == B[i]: dplists[0][i] = 1 else: dplists[0][i] = max(dplists[0][i-1],0) for i in range(1,n): if A[i] == B[0]: dplists[i][0] = 1 else: dplists[i][0] = max(dplists[i-1][0],0) # 处理其他部分值 # 情况一：i,j时： A的长度大于B,且B[j]为子序列末尾标志： 增加A的长度 dplists[i][j] = dplists[i-1][j] # 情况二：i,j时： B的长度大于A,且A[i]为子序列末尾标志： 增加B的长度 dplists[i][j] = dplists[i][j-1] # 情况三：A[i-1] = B[j-1]为子序列末尾标志且：dplists[i][j] = dplists[i-1][j-1] + 1 # dplists[i][j] = max(情况一，情况二，情况三) for i in range(1,n): for j in range(1,m): dp_1 = dplists[i - 1][j] dp_2 = dplists[i][j - 1] dp_3 = dplists[i - 1][j - 1] + 1 if A[i] == B[j]: dplists[i][j] = max(dp_1,dp_2,dp_3) else: dplists[i][j] = max(dp_1,dp_2) return dplists[n-1][m-1] # 改进版本 def findLCS2(self, A, n, B, m): dp = [[0 for _ in range(m+1)] for _ in range(n+1)] for i in range(1,n+1): for j in range(i,m+1): if A[i-1] == B[j-1]: dp[i][j] = max(dp[i-1][j-1]+1,dp[i-1][j],dp[i][j-1]) else: dp[i][j] = max(dp[i-1][j],dp[i][j-1]) return dp[-1][-1] -
==一个背包有一定的承重cap，有N件物品，每件都有自己的价值，记录在数组v中，也都有自己的重量，记录在数组w中，每件物品只能选择要装入背包还是不装入背包，要求在不超过背包承重的前提下，选出物品的总价值最大。给定物品的重量w价值v及物品数n和承重cap**。请返回最大总价值。**==
# -*- coding:utf-8 -*- class Backpack: def maxValue(self, w, v, n, cap): # write code here dpBack = [[0 for _ in range(cap+1)] for _ in range(n+1)] for i in range(1,n+1): for j in range(1,cap+1): # 如果当前背包容量足够存放当前物品 # 计算 dpBack[i-1][j] 与dpBack[i-1][j-w[i-1]] + v[i-1] if w[i-1] <= j: dpBack[i][j] = max(dpBack[i-1][j],dpBack[i-1][j-w[i-1]] + v[i-1]) # 背包容量不足以存放 else: dpBack[i][j] = dpBack[i-1][j] return dpBack[-1][-1] -
==对于两个字符串A和B，我们需要进行插入、删除和修改操作将A串变为B串，定义c0，c1，c2分别为三种操作的代价，请设计一个高效算法，求出将A串变为B串所需要的最少代价。给定两个字符串A和B**，及它们的长度和三种操作代价，请返回将A串变为B串所需要的最小代价。保证两串长度均小于等于300，且三种代价值均小于等于100。**==
# -*- coding:utf-8 -*- class MinCost: def findMinCost(self, A, n, B, m, c0, c1, c2): # write code here # dplistis : n+1 * m+1 dplists = [[0 for _ in range(m+1)] for _ in range(n+1)] # 第一行"" -> "" +B : 增加代价 for i in range(1,m+1): dplists[0][i] = c0 * i # 第一列"" + A ->"" : 删除代价 for i in range(1,n+1): dplists[i][0] = c1 * i # 处理其他位置： 取四种情况最小值 # 情况一：A->B i->j 长度增加 dplists[i][j] = dplists[i][j-1] + c0 # 情况二：A->B i->j 长度减小 dplists[i][j] = dplists[i-1][j] + c1 # 情况三：A->B i->j 长度不变且 A[i-1] = b[j-1]：则进行替换 dplists[i][j] = dplists[i-1][j-1] + c2 # 情况四：A->B i->j 长度不变且 A[i-1] != B[j-1]: 则dplists[i][j] = dplists[i-1][j-1] for i in range(1,n+1): for j in range(1,m+1): # i < j 长度增加 dp_1 = dplists[i][j-1] + c0 # i > j 长度减小 dp_2 = dplists[i-1][j] + c1 # i == j : 长度不变 if A[i-1] == B[j-1]: dp_3 = dplists[i-1][j-1] else: dp_3 = dplists[i-1][j-1] + c2 dplists[i][j] = min(dp_1,dp_2,dp_3) return dplists[-1][-1] -
==智力题==
-
==你要在一个nxm的格子图上涂色，你每次可以选择一个未涂色的格子涂上你开始选定的那种颜色。同时为了美观，我们要求你涂色的格子不能相邻，也就是说，不能有公共边，现在问你，在采取最优策略的情况下，你最多能涂多少个格子？给定格子图的长n和宽m。请返回最多能涂的格子数目。==
# -*- coding:utf-8 -*- class Paint: def getMost(self, n, m): # write code here return int(n * m / 2.0 + 0.5) -
==作为一个马场的主人，你要安排你的n匹赛马和另一个马场的n匹马比赛。你已经知道了对方马场的出战表，即参加每一场的马的强壮程度。当然你也知道你自己的所有马的强壮程度。我们假定比赛的结果直接由马的强壮程度决定，即更壮的马获胜(若相同则双方均不算获胜)，请你设计一个策略，使你能获得尽量多的场次的胜利。给定对方每场比赛的马的强壮程度oppo及你的所有马的强壮程度horses(强壮程度为整数，且数字越大越强壮)同时给定n，请返回最多能获胜的场次。==
# -*- coding:utf-8 -*- class HorseRace: def winMost(self, oppo, horses, n): # write code here # 双方的马进行排序 oppo.sort() horses.sort() i = 0 j = 0 res = 0 # 保证我方的马胜过对手的马此时 记为一组获胜组合 同时向后移动 while i < n and j < n: if oppo[i] < horses[j]: res = res + 1 i = i + 1 j = j + 1 return res -
==你和你的朋友正在玩棋子跳格子的游戏，而棋盘是一个由n个格子组成的长条，你们两人轮流移动一颗棋子，每次可以选择让棋子跳1-3格，先将棋子移出棋盘的人获得胜利。我们知道你们两人都会采取最优策略，现在已知格子数目，并且初始时棋子在第一格由你操作。请你计算你是否能获胜。给定格子的数目n(n为不超过300的正整数)。返回一个整数，1代表能获胜，0代表不能获胜。==
# -*- coding:utf-8 -*- class Jump: def checkWin(self, n): # write code here # 博弈论 双方补满4个格子 如果可以走的格子为4的倍数 则先走的人必输 if n % 4 == 0: return 0 return 1 -
==A与B做游戏。 在一个n*m的矩阵中的出发点是（1，m），终点是（n,1），规则是只能向左移动一格，向下一格或向左下移动一格，先走到终点的为winner。 A先走。给定两个整数n和m，请返回最后的获胜者的名字(A或B)。==
# -*- coding:utf-8 -*- class Game: def getWinner(self, n, m): # write code here # 当棋盘大小是奇*奇大小时，先出走的人必输（后出的人只需和先出的人动作一样）。所以只需要让对手陷入奇*奇的棋盘就赢 # 开局奇 * 偶，A向下走，变成奇 * 奇 # 开局偶 * 奇，A向左走，变成奇 * 奇 # 开局偶 * 偶，A向左下，变成奇 * 奇 # 开局奇 * 奇，GG # 两个数都为奇数 if (n & 1) and (m & 1): return 'B' return 'A' -
==现在有一个整数数组，其元素值均为1-n范围内的某个整数，现在你和你的朋友在玩一个游戏，游戏的目的是把数组清空，你们轮流操作，你是先手，每次操作你可以删除数组中值为某个数的元素任意多个(当然数组中值为这个数的元素个数应大于等于你删除的个数,且你至少要删除一个数)。最先把数组清空的人获得胜利。假设你们都采取最优策略，请你计算你能否获得胜利。给定一个整数数组A和元素个数n。请返回一个整数，1代表你能获胜，0代表你不能获胜。==
# -*- coding:utf-8 -*- class Clear: def getWinner(self, A, n): # write code here # Nim博弈：如果两种数字每种个数相同，那么先手取一种数字x个，后手就在另一种数字中取x。只要这样，后手就会取得胜利； # 当两种数字个数不同时，先手先取出多的部分，之后情况与上边相同，这时先手获胜。 # 多种数字情况，Nim判断方法：对每种数字个数异或的结果进行判断，当异或结果为0时，称为平衡状态，异或结果为1时称为不平衡状态 # 不平衡时先手胜 平衡时 后手胜利 table = {} for each in A: if each not in table: table[each] = 1 else: table[each] = table[each] + 1 res = 0 for key in table: res = res ^ table[key] # res 为0 表示平衡： 后手胜利 if not res : return 0 else: # res 为1 表示不平衡：先手胜利 return 1
-
-
-
第一章
-
==如果对于一个字符串A，将A的前面任意一部分挪到后边去形成的字符串称为A的旋转词。比如A="12345",A的旋转词有"12345","23451","34512","45123"和"51234"。对于两个字符串A和B，请判断A和B是否互为旋转词。给定两个字符串A和B及他们的长度lena，lenb，请返回一个bool值，代表他们是否互为旋转词。==
# -*- coding:utf-8 -*- class Rotation: def chkRotation(self, A, lena, B, lenb): # write code here model = A + A return B in (A + A) -
==对于两棵彼此独立的二叉树A和B，请编写一个高效算法，检查A中是否存在一棵子树与B树的拓扑结构完全相同。给定两棵二叉树的头结点A和B，请返回一个bool值，代表A中是否存在一棵同构于B的子树。==
# -*- coding:utf-8 -*- # class TreeNode: # def __init__(self, x): # self.val = x # self.left = None # self.right = None class IdenticalTree: def chkIdentical(self, A, B): # write code here strA = self.serializalTree(A) strB = self.serializalTree(B) return strB in strA def serializalTree(self, head): res = "" if head is None: return res # 先序遍历序列化 stack = [] stack.append(head) while len(stack) > 0: top = stack.pop() if top is not None: res = res + str(top.val) + "!" stack.append(top.right) stack.append(top.left) else: res = res + "#!" return res -
==对于两个字符串A和B，如果A和B中出现的字符种类相同且每种字符出现的次数相同，则A和B互为变形词，请设计一个高效算法，检查两给定串是否互为变形词。给定两个字符串A和B及他们的长度，请返回一个bool值，代表他们是否互为变形词。==
# -*- coding:utf-8 -*- class Transform: def chkTransform(self, A, lena, B, lenb): # write code here if lena != lenb: return False # 如果互为转变形词，那么字符种类对应的数目一定为偶数个，检查奇偶使用"异或" resStr = A + B res = 0 for i in range(lena + lenb): res = res ^ ord(resStr[i]) if res == 0: return True else: return False -
==对于一个字符串，请设计一个算法，只在字符串的单词间做逆序调整，也就是说，字符串由一些由空格分隔的部分组成，你需要将这些部分逆序。给定一个原字符串A和他的长度，请返回逆序后的字符串。==
# -*- coding:utf-8 -*- class Reverse: def reverseSentence(self, A, n): # write code here # spilt返回分隔开的单词列表 a = A.split() # join(迭代数据类型) a[::-1]表示，将a中的元素逆序 return " ".join(a[::-1]) -
==对于一个字符串，请设计一个算法，将字符串的长度为len的前缀平移到字符串的最后。给定一个字符串A和它的长度，同时给定len，请返回平移后的字符串。==
# -*- coding:utf-8 -*- class Translation: def stringTranslation(self, A, n, len): # write code here rightStr = A[0:len] leftStr = A[len:n] return leftStr + rightStr -
==对于一个给定的字符串数组，请找到一种拼接顺序，使所有小字符串拼接成的大字符串是所有可能的拼接中字典序最小的。给定一个字符串数组strs，同时给定它的大小，请返回拼接成的串。==
# -*- coding:utf-8 -*- class Prior: def findSmallest(self, strs, n): # write code here # 自定义排序方法： 自定义cmp：a>b返回1 a<b返回-1 # sorted默认按升序进行排列 def cmp(a,b): if a+b > b+a: return 1 elif a+b < b+a: return -1 return 0 resStr = sorted(strs,cmp) return "".join(resStr) -
==请编写一个方法，将字符串中的空格全部替换为“%20”。假定该字符串有足够的空间存放新增的字符，并且知道字符串的真实长度(小于等于1000)，同时保证字符串由大小写的英文字母组成。给定一个string iniString 为原始的串，以及串的长度 int len, 返回替换后的string。==
# -*- coding:utf-8 -*- class Replacement: def replaceSpace(self, iniString, length): # write code here strValues = iniString.split(' ') return '%20'.join(strValues) -
==对于一个字符串，请设计一个算法，判断其是否为一个合法的括号串。给定一个字符串A和它的长度n，请返回一个bool值代表它是否为一个合法的括号串。==
# -*- coding:utf-8 -*- class Parenthesis: def chkParenthesis(self, A, n): # write code here res = 0 for i in range(0,n): if res < 0: return False if A[i] == '(': res = res + 1 elif A[i] == ')': res = res - 1 if res == 0: return True else: return False -
==对于一个字符串,请设计一个高效算法，找到字符串的最长无重复字符的子串长度。给定一个字符串A及它的长度n，请返回它的最长无重复字符子串长度。保证A中字符全部为小写英文字符，且长度小于等于500。==
# -*- coding:utf-8 -*- class DistinctSubstring: def longestSubstring(self, A, n): # write code here # max_len = 0 s = A if s is None or len(s) == 0: return max_len # 定义一个字典hasmap，存储不重复的字符和字符所在的下表 str_dict = {} # 存储每次循环中最长的子串长度 one_max = 0 # 记录最近重复字符所在的位置 start = 0 for i in range(0,n): if s[i] in str_dict and str_dict[s[i]] >= start: start = str_dict[s[i]] + 1 # 本次循环中，最大的不重复子串的长度 one_max = i - start + 1 # 覆盖当前字符的最近出现位置 str_dict[s[i]] = i # 比较此次循环中的最大不重复子串长度和历史循环中的最大不重复子串长度 max_len = max(max_len,one_max) return max_len -
==定义栈的数据结构，请在该类型中实现一个能够得到栈最小元素的min函数。==
# -*- coding:utf-8 -*- class Solution: def __init__(self): self.A = [] self.M = [] def push(self, node): # write code here self.A.append(node) if len(self.M) == 0: self.M.append(node) elif self.A[-1] < self.M[-1]: self.M.append(self.A[-1]) else: self.M.append(self.M[-1]) def pop(self): # write code here self.M.pop() return self.A.pop() def top(self): # write code here return self.A[-1] def min(self): # write code here return self.M[-1] -
==编写一个类,只能用两个栈结构实现队列,支持队列的基本操作(push，pop)。给定一个操作序列ope及它的长度n，其中元素为正数代表push操作，为0代表pop操作，保证操作序列合法且一定含pop操作，请返回pop的结果序列。==
# -*- coding:utf-8 -*- class TwoStack: def twoStack(self, ope, n): # write code here stack1 = [] stack2 = [] res = [] for each in ope: if each != 0: stack1.append(each) else: if stack2 == []: stack2 = stack1[::-1] res.append(stack2.pop()) stack1 = stack1[1:] return res # 第二种方法 def twoStack(self, ope, n): # write code here stack1 = [] res = [] num_0 = 0 for each in ope: if each != 0: stack1.append(each) else: res.append(stack1[num_0]) num_0 += 1 return res -
==有一个整型数组 arr 和一个大小为 w 的窗口从数组的最左边滑到最右边,窗口每次向右边滑一个位置。 返回一个长度为n-w+1的数组res，res[i]表示每一种窗口状态下的最大值。 以数组为[4,3,5,4,3,3,6,7]，w=3为例。因为第一个窗口[4,3,5]的最大值为5，第二个窗口[3,5,4]的最大值为5，第三个窗口[5,4,3]的最大值为5。第四个窗口[4,3,3]的最大值为4。第五个窗口[3,3,6]的最大值为6。第六个窗口[3,6,7]的最大值为7。所以最终返回[5,5,5,4,6,7]。给定整形数组arr及它的大小n，同时给定w，请返回res数组。保证w小于等于n，同时保证数组大小小于等于500。==
# -*- coding:utf-8 -*- class SlideWindow: def slide(self, arr, n, w): # write code here c_max = [] res = [] for i in range(0,n): # 维护窗口最大值的下标队列 # 如果队列中没有值，则插入当前值的下标 if len(c_max) == 0: c_max.append(i) else: # 队尾下标的值若大于当前值arr[i] 则插入当前下表i if arr[i] <arr[c_max[-1]]: c_max.append(i) else: # 队尾下标的值若小于当前值arr[i] 则从队尾下表删除 直到找到一个大于arr[i]的下标 将i插入到该值之后 while len(c_max) > 0: tail = c_max[-1] if arr[tail] > arr[i]: break c_max.pop() c_max.append(i) # 查找结果 res中保存n-w+1个结果 if i >= w - 1: if c_max[0] < i - w + 1: c_max.pop(0) res.append(arr[c_max[0]]) return res -
==对于一个没有重复元素的整数数组，请用其中元素构造一棵MaxTree，MaxTree定义为一棵二叉树，其中的节点与数组元素一一对应，同时对于MaxTree的每棵子树，它的根的元素值为子树的最大值。现有一建树方法，对于数组中的每个元素，其在树中的父亲为数组中它左边比它大的第一个数和右边比它大的第一个数中更小的一个。若两边都不存在比它大的数，那么它就是树根。请设计O(n)的算法实现这个方法。给定一个无重复元素的数组A和它的大小n，请返回一个数组，其中每个元素为原数组中对应位置元素在树中的父亲节点的编号，若为根则值为-1==
# -*- coding:utf-8 -*- class MaxTree: def buildMaxTree(self, A, n): # write code here # 存储左边第一个比该值大的索引 left = [-1 for _ in range(n)] # 存储右边第一个比当前值大的索引 right = [-1 for _ in range(n)] # 存储结果： 左右方比当前值大的里面的较小值的索引 res = [-1 for _ in range(n)] for i in range(0,n): curValue = A[i] for j in range(i,-1,-1): if A[j] > curValue: left[i] = j break for k in range(i,n): if A[k] > curValue: right[i] = k break for i in range(0,n): if left[i] != -1 and right[i] != -1: if A[left[i]] < A[right[i]]: res[i] = left[i] else: res[i] = right[i] elif left[i] == -1 and right[i] != -1: res[i] = right[i] elif left[i] != -1 and right[i] == -1: res[i] = left[i] return res -
==有一个有序数组A和一个整数val，请你用A构造一个结点值有序的无环单链表，并对其插入一个结点值为val的结点，并且保证这个无环单链表依然有序。给定包含链表的所有元素的值（从头结点开始）的数组A，同时给定val，请构造出这个无环单链表，并返回插入该val值后的头结点。==
#coding:utf-8 # class ListNode: # def __init__(self, x): # self.val = x # self.next = None # # 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可 # # # @param A int整型一维数组 # @param val int整型 # @return ListNode类 # class Solution: def insert(self , A , val ): # write code here head = ListNode(-1) p = head for i in range(0,len(A)): curNode = ListNode(A[i]) p.next = curNode p = p.next head = head.next cur = head # 比所有的数都小 if val < cur.val: insertNode = ListNode(val) insertNode.next = cur return insertNode for i in range(0,len(A)-1): if cur.val <= val and val <= cur.next.val: insertNode = ListNode(val) insertNode.next = cur.next cur.next = insertNode return head cur = cur.next # 比所有的数都大 insertNode = ListNode(val) cur.next = insertNode return head -
==实现一个算法，删除单向链表中间的某个结点，假定你只能访问该结点。给定带删除的头节点和要删除的数字，请执行删除操作，返回删除后的头结点。链表中没有重复数字==
# -*- coding:utf-8 -*- # class ListNode: # def __init__(self, x): # self.val = x # self.next = None class Remove: def removeNode(self, pHead, delVal): # write code here if pHead is None: return pHead if pHead.val == delVal: return pHead.next curNode = pHead while curNode is not None: if curNode.next.val == delVal: curNode.next = curNode.next.next return pHead curNode = curNode.next return pHead -
==对于一个链表，我们需要用一个特定阈值完成对它的分化，使得小于等于这个值的结点移到前面，大于该值的结点在后面，同时保证两类结点内部的位置关系不变。给定一个链表的头结点head，同时给定阈值val，请返回一个链表，使小于等于它的结点在前，大于等于它的在后，保证结点值不重复。==
# -*- coding:utf-8 -*- # class ListNode: # def __init__(self, x): # self.val = x # self.next = None class Divide: def listDivide(self, head, val): # write code here # 小于val的nodes的头和尾 leftNodes = ListNode(0) tailLP = leftNodes # 大于val的nodes的头和尾 rightNodes = ListNode(-1) tailRP = rightNodes # 遍历 pHead = head flagEqualNode = None while pHead is not None: valueNode = ListNode(pHead.val) # 如果当前值小于val 插入lelfNodes尾部 if pHead.val < val: tailLP.next = valueNode tailLP = tailLP.next # 如果当前值大于val 插入rightNodes尾部 elif pHead.val > val: tailRP.next = valueNode tailRP = tailRP.next elif pHead.val == val: flagEqualNode = ListNode(pHead.val) pHead = pHead.next # 连接 tailLP.next = rightNodes.next # 如果有等于 if flagEqualNode is not None: flagEqualNode.next = leftNodes.next return flagEqualNode # 如果没有等于 return leftNodes.next -
==有一个单链表，请设计一个算法，使得每K个节点之间逆序，如果最后不够K个节点一组，则不调整最后几个节点。例如链表1->2->3->4->5->6->7->8->null，K=3这个例子。调整后为，3->2->1->6->5->4->7->8->null。因为K=3，所以每三个节点之间逆序，但其中的7，8不调整，因为只有两个节点不够一组。给定一个单链表的头指针head,同时给定K值，返回逆序后的链表的头指针。==
# -*- coding:utf-8 -*- # class ListNode: # def __init__(self, x): # self.val = x # self.next = None class KInverse: def inverse(self, head, k): # write code here rootHead = ListNode(-1) resHead = rootHead resTail = rootHead KNodesHead = None KNodesTail = None lastTeamHead = None index = 0 while head is not None: # 首先将当前遍历到的节点值进行存储到KNodes序列中 采用前插的方式进行插入 cur = ListNode(head.val) cur.next = KNodesHead KNodesHead = cur index += 1 # 如果当前的取值次序 % k ==1 表示该结点为该组节点序列的尾部 if index % k == 1: KNodesTail = cur # 记录每组的第一个值在数据源中的节点位置：若数据源个数不能把k整除，则需要进行后续的连接 lastTeamHead = head # 当前的序列满k个 则将该序列连接到res序列中： resTail.next = KNodesHead 并将KNodesHead置为None 否则链表成环 # 并更新res序列的尾部：为取余得1时得到的节点头部信息 if index % k == 0: # 结果的尾部接上 KNodesHead resTail.next = KNodesHead KNodesHead = None # 结果的尾部变为lastTeamHead resTail = KNodesTail head = head.next # 若数据源将k整除，则序列构建完毕，直接返回头节点 if index % k == 0: return rootHead.next # 若不能整除：利用最后一组得到的头节点对应的数据源中的节点位置 进行补全 else: while lastTeamHead is not None: resTail.next = lastTeamHead resTail = resTail.next lastTeamHead = lastTeamHead .next return rootHead.next -
==现在有一个单链表。链表中每个节点保存一个整数，再给定一个值val，把所有等于val的节点删掉。给定一个单链表的头结点head，同时给定一个值val，请返回清除后的链表的头结点，保证链表中有不等于该值的其它值。请保证其他元素的相对顺序。==
# -*- coding:utf-8 -*- # class ListNode: # def __init__(self, x): # self.val = x # self.next = None class ClearValue: def clear(self, head, val): # write code here if head is None: return head while head.val == val: head = head.next # 寻找到第一个不等于val的值作为返回结果的头节点 resHead = head # 判断head是否为空 while head is not None: # 若head.next不为空且head.next的值等于val 则删除head.next if head.next is not None and head.next.val == val: head.next = head.next.next # 若为空，说明链表遍历完 则循环下次结束； 若head.next不等于val 则遍历下一个节点 else: head = head.next return resHead -
==请编写一个函数，检查链表是否为回文。给定一个链表ListNode* pHead，请返回一个bool，代表链表是否为回文。==
# -*- coding:utf-8 -*- # class ListNode: # def __init__(self, x): # self.val = x # self.next = None class Palindrome: def isPalindrome(self, pHead): # write code here if pHead is None: return True valueList = [] while pHead is not None: valueList.append(pHead.val) pHead = pHead.next # 正反相同 python中对两个列表的内容进行判断 reverseList = valueList[::-1] return valueList == reverseList -
==如何判断一个单链表是否有环？有环的话返回进入环的第一个节点的值，无环的话返回-1。如果链表的长度为N，请做到时间复杂度O(N)，额外空间复杂度O(1)。给定一个单链表的头结点head（注意另一个参数adjust为加密后的数据调整参数，方便数据设置，与本题求解无关)，请返回所求值。==
# -*- coding:utf-8 -*- # class ListNode: # def __init__(self, x): # self.val = x # self.next = None class ChkLoop: def chkLoop(self, head, adjust): # write code here if head is None: return -1 meetNode = None fastP = head slowP = head while fastP is not None: fastP = fastP.next slowP = slowP.next if fastP is not None: fastP = fastP.next else: return -1 if fastP == slowP: meetNode = fastP break if fastP is None: return -1 # 第一次相遇之后 设置两个节点 一个从头开始 一个从相遇节点开始 # 再次相遇时 相遇节点即为环的入口节点 while meetNode != head: meetNode = meetNode.next head = head.next return head.val -
==输入一个复杂链表（每个节点中有节点值，以及两个指针，一个指向下一个节点，另一个特殊指针指向任意一个节点）。==
# -*- coding:utf-8 -*- # class RandomListNode: # def __init__(self, x): # self.label = x # self.next = None # self.random = None class Solution: # 返回 RandomListNode def Clone(self, pHead): # write code here if pHead is None: return None # 复制链表 cur = pHead while cur : node = RandomListNode(cur.label) node.next = cur.next cur.next = node cur = node.next # 复制random ran = pHead while ran: cur = ran.next if ran.random: cur.random = ran.random.next ran = cur.next # 拆链表 newLinkNodes = pHead.next pre = pHead while pre: cur = pre.next pre.next = cur.next pre = pre.next # 如果pre为None 说明该节点为原数据中的最后一个数据节点 if pre is None: cur.next = None return newLinkNodes cur.next = pre.next return newLinkNodes -
==现在有两个无环单链表，若两个链表的长度分别为m和n，请设计一个时间复杂度为O(n + m)，额外空间复杂度为O(1)的算法，判断这两个链表是否相交。给定两个链表的头结点headA和headB，请返回一个bool值，代表这两个链表是否相交。保证两个链表长度小于等于500。==
# -*- coding:utf-8 -*- # class ListNode: # def __init__(self, x): # self.val = x # self.next = None class CheckIntersect: def chkIntersect(self, headA, headB): # write code here if headA == headB: return True # 判断尾节点是否相交 while headA.next: headA = headA.next while headB.next: headB = headB.next return headA == headB -
==如何判断两个有环单链表是否相交？相交的话返回第一个相交的节点，不想交的话返回空。如果两个链表长度分别为N和M，请做到时间复杂度O(N+M)，额外空间复杂度O(1)。给定两个链表的头结点head1和head2(注意，另外两个参数adjust0和adjust1用于调整数据,与本题求解无关)。请返回一个bool值代表它们是否相交。==
# -*- coding:utf-8 -*- # class ListNode: # def __init__(self, x): # self.val = x # self.next = None class ChkIntersection: def chkInter(self, head1, head2, adjust0, adjust1): # write code here def loopNode(pHead): meetNode = None fastNode = pHead slowNode = pHead while fastNode : slowNode = slowNode.next fastNode = fastNode.next if not fastNode : break fastNode = fastNode.next if fastNode == slowNode: meetNode = fastNode break # 没有相交的节点 if fastNode is None: return None # 找到第一次的相遇节点 while pHead != meetNode: pHead = pHead.next meetNode = meetNode.next # 返回loop的入口 return pHead # 获得两个环中的节点 loopNode1 = loopNode(head1) loopNode2 = loopNode(head2) if loopNode1 == loopNode2: return True # 遍历其中一个环 看其中节点是否会碰到另一个节点 curNode = loopNode1 while curNode.next: curNode = curNode.next if curNode == loopNode2: return True elif curNode == loopNode1: return False -
==给定两个单链表的头节点head1和head2，如何判断两个链表是否相交？相交的话返回true，不想交的话返回false。给定两个链表的头结点head1和head2(注意，另外两个参数adjust0和adjust1用于调整数据,与本题求解无关)。请返回一个bool值代表它们是否相交。==
# -*- coding:utf-8 -*- # class ListNode: # def __init__(self, x): # self.val = x # self.next = None class ChkIntersection: def chkInter(self, head1, head2, adjust0, adjust1): # write code here def getLoop(pHead): if pHead is None: return None meetNode = None fastNode = pHead slowNode = pHead while fastNode: fastNode = fastNode.next slowNode = slowNode.next if not fastNode: return None fastNode = fastNode.next if fastNode == slowNode: meetNode = fastNode break # 没有相交节点 if not fastNode: return None # 寻找环节点的入口 while meetNode != slowNode: meetNode = meetNode.next slowNode = slowNode.next return slowNode loopNode1 = getLoop(head1) loopNode2 = getLoop(head2) # 判断两个节点的环节点入口是否相等 if loopNode1 == loopNode2: return True # 判断loop1中是否会出现loop2中的相交节点 if loopNode1 and loopNode2: cur = loopNode1.next while cur : if cur == loopNode2: return True if cur == loopNode1: return False cur = cur.next # 如果两个链表都没有环 则对其尾部进行判断是否相交 elif not loopNode1 and loopNode2: while head1.next and head2.next: head1 = head1.next head2 = head2.next if head1 == head2: return True return False -
==定义局部最小的概念。arr长度为1时，arr[0]是局部最小。arr的长度为N(N>1)时，如果arr[0]<arr[1]，那么arr[0]是局部最小；如果arr[N-1]<arr[N-2]，那么arr[N-1]是局部最小；如果0<i<N-1，既有arr[i]<arr[i-1]又有arr[i]<arr[i+1]，那么arr[i]是局部最小。 给定无序数组arr，已知arr中任意两个相邻的数都不相等，写一个函数，只需返回arr中任意一个局部最小出现的位置即可。==
public class Solution { public int getLessIndex(int[] arr) { if(arr.length == 0)return -1; if(arr.length == 1)return 0; if(arr[0] < arr[ 1])return 0; if(arr[arr.length-1] < arr[arr.length - 2])return arr.length - 1; int l = 1, r = arr.length - 2; while(l <= r){ int mid = (l + r) >> 1; if(arr[mid - 1] > arr[mid] && arr[mid + 1] > arr[mid])return mid; else if(arr[mid - 1] < arr[mid])r = mid - 1; else l = mid + 1; } return -1; } } -
==对于一个有序数组arr，再给定一个整数num，请在arr中找到num这个数出现的最左边的位置。给定一个数组arr及它的大小n，同时给定num。请返回所求位置。若该元素在数组中未出现，请返回-1==
# -*- coding:utf-8 -*- class LeftMostAppearance: def findPos(self, arr, n, num): # write code here res = -1 if n == 0: if arr[0] == num: return 0 else: return -1 l = 0 r = n - 1 while l <= r: mid = (l + r) >> 1 if arr[mid] < num: l = mid + 1 elif arr[mid] > num: r = mid - 1 elif arr[mid] == num: res = mid r = mid -1 return res -
==对于一个有序循环数组arr，返回arr中的最小值。有序循环数组是指，有序数组左边任意长度的部分放到右边去，右边的部分拿到左边来。比如数组[1,2,3,3,4]，是有序循环数组，[4,1,2,3,3]也是。给定数组arr及它的大小n，请返回最小值。==
# -*- coding:utf-8 -*- class MinValue: def getMin(self, arr, n): # write code here if n == 1: return arr[0] l = 0 r = n - 1 while l <= r: if arr[l] < arr[r]: return arr[l] mid = ( l + r ) >>1 # 只可能小于左边 或者大于右边 if arr[mid] > arr[r]: l = mid + 1 elif arr[mid] < arr[l]: r = mid - 0 else: small = arr[0] for each in arr: if each < small: small = each return small #elif arr[l] == arr[mid] and arr[mid] == arr[r]: #break #return min(arr) -
==有一个有序数组arr，其中不含有重复元素，请找到满足arr[i]=i条件的最左的位置。如果所有位置上的数都不满足条件，返回-1。给定有序数组arr及它的大小n，请返回所求值==
# -*- coding:utf-8 -*- class Find: def findPos(self, arr, n): # write code here if arr[0] == 0: return 0 if arr[0] > arr[n-1]: return -1 if arr[-1] < 0: return -1 l = 0 r = n-1 res = -1 # 二分查找的循环判断 while l <= r: # 取中间的Mid mid = (l + r) >> 1 # 判断三种情况 if arr[mid] < mid: l = mid + 1 elif arr[mid] > mid: r = mid - 1 # 要求最左：更新查找的右方范围 elif arr[mid] == mid: res = mid r = mid -1 return arr[res] -
==给定一棵完全二叉树的根节点root，返回这棵树的节点个数。如果完全二叉树的节点数为N，请实现时间复杂度低于O(N)的解法。给定树的根结点root**，请返回树的大小。有问题！！！！！！！！！！！**==
```python
# -*- coding:utf-8 -*-
#class TreeNode:
# def __init__(self, x):
# self.val = x
# self.left = None
# self.right = None
class CountNodes:
def count(self, root):
# write code here
if root is None:
return 0
temp = root
num = 0
while temp is not None:
Lh = 0
node = temp
while node is not None:
node = node.left
Lh += 1
Rh = 1
node = temp.right
while node is not None:
node = node.left
Rh += 1
if Rh == Lh: # 说明左子树是满二叉树
num += 2 **(Lh - 1)
temp = temp.right # 将右子树迭代
elif Rh < Lh:
num += 2 **(Rh - 1)
temp = temp.left
return num
```
31. ==如果更快的求一个整数k的n次方。如果两个整数相乘并得到结果的时间复杂度为O(1)，得到整数k的N次方的过程请实现时间复杂度为O(logN)的方法。给定k和n，请返回k的n次方，为了防止溢出，请返回结果Mod 1000000007的值。==
```python
# -*- coding:utf-8 -*-
class QuickPower:
def getPower(self, k, N):
# write code here
res = 1
base = []
index = 1
while N > 0:
# 与运算符 直接二进制形式的末尾的数
flag = N & 1
if flag:
res = (res * k) % 1000000007
# 右移：除以二
N = N >> 1
k = (k * k) % 1000000007
return res
```
32. ==对于一个int数组，请编写一个基数排序算法，对数组元素排序。给定一个int数组A及数组的大小n，请返回排序后的数组。保证元素均小于等于2000。==
```python
# -*- coding:utf-8 -*-
class RadixSort:
def radixSort(self, A, n):
# write code here
maxValue = max(A)
lenA = len(str(maxValue))
dylist = [[] for _ in range(10)]
temp = []
# 分别按照 个位 十位 等进行排序 0-9位置上的数字 先进先出：最后一次出来的结果为排好的顺序
for k in range(0,lenA):
for i in range(n):
index = int((A[i] / (10 ** k)) % 10)
dylist[index].append(A[i])
for i in range(10):
while len(dylist[i]):
temp.append(dylist[i].pop(0))
A = temp
# 当前十百千 分位的结果得到后 将temp置空
temp = []
return A
```
33. ==有两个从小到大排序以后的数组A和B，其中A的末端有足够的缓冲空容纳B。请编写一个方法，将B合并入A并排序。给定两个有序int数组A和B，A中的缓冲空用0填充，同时给定A和B的真实大小int n和int m，请返回合并后的数组。==
```python
# -*- coding:utf-8 -*-
class Merge:
def mergeAB(self, A, B, n, m):
# write code here
lenA = len(A) - 1
while n > 0 and m > 0:
if B[m-1] > A[n-1]:
A[lenA] = B[m-1]
m -= 1
else:
A[lenA] = A[n-1]
n -= 1
lenA -= 1
# 若B先处理完 则直接返回结果
while n > 0:
return A
# 若A的实际值先处理完，B有可能未处理完
while m > 0:
A[lenA] = B[m-1]
m -= 1
lenA -= 1
return A
```
34. ==有一个只由0，1，2三种元素构成的整数数组，请使用交换、原地排序而不是使用计数进行排序。给定一个只含0，1，2的整数数组A及它的大小，请返回排序后的数组。保证数组大小小于等于500。==
```python
# -*- coding:utf-8 -*-
class ThreeColor:
def sortThreeColor(self, A, n):
# write code here
l = 0
r = n-1
i = 0
while i < r :
# 找到0 往最前面换
if A[i] == 0:
A[l],A[i] = A[i],A[l]
l += 1
# 找到2 往最后面换
elif A[i] == 2:
A[i],A[r] = A[r],A[i]
r -= 1
# 找到1 位置不变 因为0 - 1 - 2 ： 1在中间
else:
i += 1
return A
```
35. ==现在有一个行和列都排好序的矩阵，请设计一个高效算法，快速查找矩阵中是否含有值x。给定一个int矩阵mat，同时给定矩阵大小nxm及待查找的数x，请返回一个bool值，代表矩阵中是否存在x。所有矩阵中数字及x均为int范围内整数。保证n和m均小于等于1000。==
```python
# -*- coding:utf-8 -*-
class Finder:
def findX(self, mat, n, m, x):
# write code here
i,j = 0,m-1
while i < n and j >= 0:
if mat[i][j] == x:
return True
elif mat[i][j] < x:
i += 1
elif mat[i][j] > x:
j -= 1
return False
```
36. ==对于一个数组，请设计一个高效算法计算需要排序的最短子数组的长度。给定一个int数组A和数组的大小n，请返回一个二元组，代表所求序列的长度。(原序列位置从0开始标号,若原序列有序，返回0)。保证A中元素均为正整数。==
```python
# -*- coding:utf-8 -*-
class Subsequence:
def shortestSubsequence(self, A, n):
# write code here
maxValue = A[0]
minValue = A[-1]
forRight = 0
forLeft = n - 1
# 向右记录最大值 以及出现降序的最小的数值的坐标
for i in range(0,n):
if A[i] > maxValue:
maxValue = A[i]
elif A[i] < maxValue:
forRight = i
# 向左记录最小值 以及出现升序的最大的数值的坐标
for i in range(n-1,-1,-1):
if A[i] < minValue:
minValue = A[i]
elif A[i] > minValue:
forLeft = i
# 若记录坐标的值未改变 说明原数组不需要进行排序
if forRight == 0 or forLeft == n-1:
return 0
length = forRight - forLeft + 1
return length
```
37. ==有一个整形数组A，请设计一个复杂度为O(n)的算法，算出排序后相邻两数的最大差值。给定一个int数组A和A的大小n，请返回最大的差值。保证数组元素多于1个。==
```python
# -*- coding:utf-8 -*-
class Gap:
def maxGap( self,A, n):
# write code here
maxValue = max(A)
minValue = min(A)
sequenceLength = (maxValue - minValue) / n
# 最小值设置为区间长度
res = sequenceLength
foreMax = minValue
buckets = [[] for _ in range(n + 1)]
for i in range(0, n):
# 当前值 - 最小值 // 区间大小: 得到存储索引
index = (A[i] - minValue) * n // (maxValue - minValue)
buckets[index].append(A[i])
for i in range(len(buckets)):
if len(buckets[i]) > 0:
# 当前区间的最小值与前方遍历过的区间的最大值进行比较即可
res = max(min(buckets[i]) - foreMax, res)
foreMax = max(foreMax, max(buckets[i]))
return res
```
投递快手等公司10个岗位 >