很久没有写代码了，重新回顾一下代码的味道。
亚马逊的题目采用贪婪+回溯
思想可解决，不过考场上时间紧迫，有个continue的代码写成了break，败笔啊。
联想的题目主要需要理顺数字下标与对角线的关系即可作对。当时编了30多分钟，时间还是长了点。、
网易有道面试题也不太难，可惜当时做得不好，效率很低。也没有完成全部实现。有道基本没戏了。
/**找钱币游戏。有面额为1，2，5，10，20各五种钱币，给定数额，
* 1. 输出最优解决方案
* 2. 输出所有解决方案
* @author caicono
* S= {1，2，5，10，20）比如 4元有以下组合。
* {1,1,1,1} {1,1,2,} {2,2}
*/
import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;
/**
*
*/
/**找钱币游戏。有面额为1，2，5，10，20各五种钱币，给定数额，
* 1. 输出最优解决方案
* 2. 输出所有解决方案
* @author caicono
* S= {1，2，5，10，20）比如 4元有以下组合。
* {1,1,1,1} {1,1,2,} {2,2}
*/
public class MoneyProblem {
final int OUTBOUND = 999;
void getOptimalSolution(int S[],int amount)
{
//首先将S[]排序 由大到小。插入排序
int NS[] = S;
int kinds = NS.length;
int sum = 0;
List solution = new ArrayList();
for(int i = 0;i<kinds; i++)
{
while(sum + NS[i] < amount)
{
sum += NS[i];
System.out.println("add "+NS[i]+" ");
solution.add(new Integer(NS[i]));
}
if(sum + NS[i] > amount)
{
System.out.println("discard "+NS[i]+" ");
continue;
}
else
{
System.out.println("sum :"+sum+",NS[i]"+NS[i]+",ready to add it");
sum += NS[i];
solution.add(new Integer(NS[i]));
System.out.println("Solution is :");
for(int j =0; j<solution.size(); j++)
{
if(j!=solution.size() -1)
System.out.print(""+solution.get(j)+",");
else
System.out.println(""+solution.get(j));
}
break;
}
}
}
void getAllSolutions(int S[],int amount)
{
//首先将S[]排序 由大到小。简单的插入或者快速排序
//int NS[] = quickSort(S);
int NS[] = S;
int kinds = NS.length;
int sum = 0;
ArrayList solution = new ArrayList();
int snum =0;
for(int i = 0;i<kinds; i++)
{
while(sum + NS[i] < amount)
{
sum += NS[i];
System.out.println("add "+NS[i]+" ");
solution.add(new Integer(NS[i]));
}
if(sum + NS[i] > amount)
{
continue;
}
else //得到一个解。
{
sum += NS[i];
solution.add(new Integer(NS[i]));
System.out.println("&&&&&Solution["+(++snum)+"] is :");
for(int j =0; j<solution.size(); j++)
{
if(j!=solution.size() -1)
System.out.print(""+solution.get(j)+",");
else
System.out.println(""+solution.get(j));
}
//得到解之后，回溯解空间，求解其它可能解。
Integer topElem ; //解向量的最后一个元素，也可以看做栈顶元素。
while(solution.size()!=0)
{
topElem = ((Integer)solution.get(solution.size()-1));
sum -= topElem.intValue();
//删除栈顶元素
int k = solution.lastIndexOf(topElem);
Integer removedElem =(Integer)solution.remove(k);
//如果栈顶元素是S中最小元素(本题中S中最小元素为1)，则直接继续弹出栈顶元素。
if(removedElem == 1)
{
continue;
}
//否则，得到该元素在S集合中比他小的元素index，从这个位置开始，重新开始新一轮的累加遍历
else
{
i = getIndex(S,removedElem);
break;
}
}
System.out.println("next iterator i="+i+",tem Sum:"+sum);
}
}
}
