阿里巴巴在线测试题

比眉伴天荒 2022-05-17 12:21 263阅读 0赞

前几天做了一个阿里巴巴关于小猴子摘桃子的问题，现在我整理一下我的思路，希望各位大神给予指教。

1、根据每棵树的桃子的数量以及该树的位置，计算该树的权重，计算公式如下：

w=v\*i

其中：v为每棵树的价值，i为每棵树的位置。

v是根据每棵树桃子的数量排序计算出来的。

2、权重计算出来后，将权重进行排序；

3、首先从权重最大的进行摘取，然后接着比较剩余的树，如果该树的价值大于当前的价值，并且该树的位置大于当前的位置，则摘取，否则不摘取。

通过以上思路的整理，代码如下：

public class Monkey \{  
  
  
public static void main(String\[\] args) \{  
int\[\] datas=\{10,4,5,12,8\};  
int\[\] flags=new int\[5\];  
int\[\]\[\] wights=comoute(datas);//计算权重  
for(int i=0;i<wights.length;i++)\{  
System.out.print("权重："+wights\[i\]\[0\]+", 价值： "+wights\[i\]\[1\]+", 位置： "+wights\[i\]\[2\]);  
System.out.print("\\n");  
\}  
  
  
selPeach(wights,flags);  
int count=0;  
System.out.println("摘取的位置： ");  
for(int i=0;i<flags.length;i++)\{  
if(flags\[i\]==1)\{  
count++;  
System.out.println(i);  
\}  
\}  
System.out.println("摘取总量："+count);  
  
  
\}  
  
/\*\*  
\* 计算权重  
\* @param datas  
\* @return  
\*/  
private static int\[\]\[\] comoute(int\[\] datas)\{  
int\[\] datasTemp=new int\[datas.length\];  
for(int i=0;i<datas.length;i++)\{  
datasTemp\[i\]=datas\[i\];  
\}  
sort(datas,0,datas.length-1);  
int\[\]\[\] wights=new int\[datas.length\]\[3\];  
for(int i=0;i<datasTemp.length;i++)\{  
int index=look(datas, datasTemp\[i\]);  
wights\[i\]\[0\]=(index+1)\*(datasTemp.length-i);//通过树的位置和价值计算权重  
wights\[i\]\[1\]=datasTemp\[i\];  
wights\[i\]\[2\]=i;  
\}  
  
return wights;  
\}  
/\*\*  
\* 快速排序  
\* @param datas  
\* @param low  
\* @param high  
\* @return  
\*/  
private static int\[\] sort(int\[\] datas, int low, int high)\{  
int lo=low;  
int hi=high;  
if(lo<hi)\{  
int key=datas\[lo\];  
while(lo<hi)\{  
while(datas\[hi\]<=key && lo<hi)\{  
hi--;  
\}  
datas\[lo\]=datas\[hi\];  
while(datas\[lo\]>=key && lo<hi)\{  
lo++;  
\}  
datas\[hi\]=datas\[lo\];  
\}  
datas\[hi\]=key;  
sort(datas,low,hi-1);  
sort(datas,hi+1,high);  
\}  
  
return datas;  
\}  
/\*\*  
\* 折半查找  
\* @param datas  
\* @param key  
\* @return  
\*/  
private static int look(int\[\] datas, int key)\{  
int low=0;  
int high=datas.length-1;  
int mid=0;  
while(low<=high)\{  
mid=(low+high)/2;  
if(datas\[mid\]>key)\{  
low=mid+1;  
\}else if(datas\[mid\]<key)\{  
high=mid-1;  
\}else\{  
break;  
\}  
\}  
return mid;  
\}  
/\*\*  
\* 选择树  
\* @param wights  
\* @param flags  
\* @return  
\*/  
private static int\[\] selPeach(int\[\]\[\] wights, int\[\] flags)\{  
sortrows(wights,0,wights.length-1,0);//将权重进行排序  
System.out.println("\#\#\#\#\#\#\#\#\#\#\#\#\#\#\#\#\#\#\#\#\#\#\#\#\#\#\#\#\#\#\#\#");  
for(int i=0;i<wights.length;i++)\{  
System.out.print("权重："+wights\[i\]\[0\]+", 价值： "+wights\[i\]\[1\]+", 位置： "+wights\[i\]\[2\]);  
System.out.print("\\n");  
\}  
int currentValue=wights\[0\]\[1\];  
int currentIndex=wights\[0\]\[2\];  
for(int i=0;i<wights.length;i++)\{  
if(wights\[i\]\[1\]>=currentValue && wights\[i\]\[2\]>=currentIndex)\{  
flags\[wights\[i\]\[2\]\]=1;  
currentValue=wights\[i\]\[1\];  
currentIndex=wights\[i\]\[2\];  
\}  
\}  
return flags;  
\}  
/\*\*  
\* 快速排序，并更新其他列  
\* @param wights  
\* @param low  
\* @param high  
\* @param col  
\* @return  
\*/  
private static int\[\]\[\] sortrows(int\[\]\[\] wights, int low, int high, int col)\{  
int lo=low;  
int hi=high;  
if(lo<hi)\{  
int\[\] keys=new int\[wights\[0\].length\];  
for(int i=0;i<wights\[0\].length;i++)\{  
keys\[i\]=wights\[lo\]\[i\];  
\}  
while(lo<hi)\{  
while(wights\[hi\]\[col\]<=keys\[col\] && lo<hi)\{  
hi--;  
\}  
for(int i=0;i<wights\[0\].length;i++)\{  
wights\[lo\]\[i\]=wights\[hi\]\[i\];  
\}  
while(wights\[lo\]\[col\]>=keys\[col\] && lo<hi)\{  
lo++;  
\}  
for(int i=0;i<wights\[0\].length;i++)\{  
wights\[hi\]\[i\]=wights\[lo\]\[i\];  
\}  
\}  
for(int i=0;i<wights\[0\].length;i++)\{  
wights\[hi\]\[i\]=keys\[i\];  
\}  
sortrows(wights, low, hi-1, col);  
sortrows(wights, hi+1, high, col);  
\}  
  
return wights;  
\}  
  
  
\}