测试算法与数据结构-动态规划
● 请问有一些数，每次可以插入，或者取出第1/4大的数，应该用什么数据结构？
参考回答：
维护当前数据量1/4大小的 最小堆，插入时被挤出来的数用最大堆保存，取操作从最小堆顶部取，然后把最大堆顶部取出插入最小堆。瞎说的不知道对不对 不过看面试官当时的态度反馈 应该还算满意）by提供面经的同学
● 系统会给定一串数字让玩家选择，如果玩家选中一个数字，比如M，那么玩家获得M分，但同时当前选中的M，以及这串数字中所有的M+1和M-1将会全部消失。玩家可以继续选择得分，直到串为空。最终系统会根据玩家获得的积分发送奖励，积分越高，奖励越丰厚。例如系统给定的数字是[2,3,3,3,4], 如果玩家选定了2，玩家得2分，并且选中的2和所有的1和3会消失，那么数组只剩下[4]，玩家再选择4，数组为空，此时一共获得6分如果玩家首先选中的是3，那么玩家得3分，选中的3，以及2和4都会消失，数字剩下[3,3]，第二次和第三次玩家可以再次选择3，这样选择一共得9分，这也是最优的选择方式。
参考回答：
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 |
|
● 手写代码：给一个英文文本“i have a dream i am a human you can have dream too.”再给一个文本“i you am ”，要求计算出第一个文本中包含第二个文本每个单词的最短文本，比如例子中最短文本就是“i am a human you”。
参考回答：
#!/usr/bin/python
#encoding:utf-8
def lengthCa(arr):
start = arr[0]
end= arr[0]
for i in arr:
if i >start:
start=i
if i < end :
end = i
return start-end
#输入的第一个文本
1 |
|
#输入的第二个文本
keywords='a of'
newtext=text.split(' ')
newkeys = keywords.split(' ')
textLen = len(newtext)
array=[]
#把index计算出来，用做最优路径规划使用
for i in newkeys:
dan=[]
for j in range(textLen):
if i == newtext[j]:
dan.append(j)
array.append(dan)
print(array)
#最优规划开始
caculateArray=[]
for n in array[0]:
temp=[]
temp.append(n)
caculateArray.append(n)
flag = 0
for n in array:
if array.index(n) == 0:
continue
temparr=[]
for m in caculateArray:#遍历当前最短路径
index = caculateArray.index(m)#计算当前路径的index值
tempminlen=1000000
tempminarr=[]
for j in n:#计算当前最短路径，添加下一个节点
if flag ==0:
temparr.append(m)
else:
for x in m:
temparr.append(x)
temparr.append(j)
if lengthCa(temparr)<tempminlen :
tempminlen=lengthCa(temparr)
tempminarr=temparr
temparr=[]
caculateArray[index]=tempminarr
print(caculateArray)
flag+=1
tempminlen=1000000
tempminarr=[]
#找出最终所有解里的最优解，为tempminarr
for n in caculateArray:
if lengthCa(n)<tempminlen :
tempminlen=lengthCa(n)
tempminarr=n
#计算tempminarr的起点和重点，现在发现用min()和max()函数就可以了
start = tempminarr[0]
end = tempminarr[0]
for i in tempminarr:
if start<i:
start=i
if end>i:
end=i
#输出起始位置和终止位置
1 2 3 |
|
● 手写代码：给你一个格子，一个人在格子的左上角，他只能向右走一步，或者向下走一步，他走到右下角共有多少种方法
参考回答：
#include<stdio.h>
int n,m,dp[10005][10005];
int main()
{
while(~scanf("%d%d",&n,&m))
{
dp[0][0]=0;
for(int i=1; i<=n; i++)
dp[i][0]=1;
for(int j=1; j<=m; j++)
dp[0][j]=1;//初始化
for(int i=1; i<=n; i++)
for(int j=1; j<=m; j++)
{
dp[i][j]=dp[i-1][j]+dp[i][j-1];//动态规划转移方程
1 2 3 4 5 |
|
● 请你讲一下动态链表和静态链表的区别
参考回答：
● 请你说一下递归和动态规划的区别?
参考回答：
递归法是算法调用自身，动态规划是将一个问题分解成若干个子问题，对大问题的求解转化为对子问题的求解。动态规划有时可以通过递归实现，通常用在最优问题的求解
● 手写代码：01背包
参考回答：
void FindMax()//动态规划
{
int i,j;
//填表
for(i=1;i<=number;i++)
{
for(j=1;j<=capacity;j++)
{
if(j<w[i])//包装不进
{
V[i][j]=V[i-1][j];
}
else//能装
{
if(V[i-1][j]>V[i-1][j-w[i]]+v[i])//不装价值大
{
V[i][j]=V[i-1][j];
}
else//前i-1个物品的最优解与第i个物品的价值之和更大
{
V[i][j]=V[i-1][j-w[i]]+v[i];
}
}
}
}
}
END
如果你觉得这篇文章有收获，点个“在看”让更多人看到