/**
*
*/

/**找钱币游戏。有面额为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);
            }
        }
       
    }
   
    /**自己实现的递归快速排序法
     * 就地排序
     * @param s
     * @return
     */
    private int[] quickSort(int l, int h, int[] s) {
        // TODO Auto-generated method stub
       
        if(l >= h)
            return s;
        else
        {
            int low = l+1; int high = h;
            int pivot = l;
            while(true)
            {
                //找到比pivot bigger的元素，位置low
                while(s[pivot]>s[low] && low < high)
                    low++;
                while(s[pivot]<s[high] && low < high)
                    high–;
                if(low < high)
                {
                    int temp = s[low];
                    s[low] = s[high];
                    s[high] =temp;
                }
                else //如果low 和high有交叠(low >= high)，则分区结束
                {
                    break;
               
                }
               
            }
            int temp = s[pivot];
            s[pivot] = s[high];
            s[high] = temp;
           
            quickSort(l,high-1,s);
            quickSort(high+1,h,s);
           
        }
        return s;
    }

    private int getIndex(int[] s, Integer i) {
        int k = i.intValue();
        int l=0,h=s.length-1, m;
        while(l<=h)
        {
            m = (l+h )/ 2;
            if(s[m]>k)
            {
                l = m +1;
            }
            else if(s[m]<k)
            {
                h = m-1;       
            }
               
            else
            {
                return m;
            }
               
        }
       
       
        // TODO Auto-generated method stub
        System.out.println(“No such element:”+k+” in Array:”);
        return OUTBOUND;
    }

    /**
     * @param args
     */
    public static void main(String[] args) {
        // TODO Auto-generated method stub
        MoneyProblem MP = new MoneyProblem();
        int S[] = {20,10,5,2,1};
        int amount = 7;
        //MP.getOptimalSolution(S, amount);
        //MP.getNext(S, new Integer(13));
        /*MP.getNext(S, new Integer(1));
        MP.getNext(S, new Integer(2));
        */
    }

}

* @author caicono
*
*/
public class TestQ {

   
    void m_print(int [][]data,int N)
    {
        N = 3;
       
//        di :表示对角线diagonal，对于N的矩阵，有2N-1条对角线
        for(int di =0; di< 2*N-1; di++)
        {
            if(di%2 ==0) //
            {
                int sum = 0;               
                for(int j=0;j<N;j++)
                      for(int i=0;i<N;i++)
                  {
                   
                    if(i+j == di)
                    {
                        System.out.println(data[i][j]);
                        sum++;
                        if(sum == di+1) //已经将所有符合条件的i，j找到，第di条对角线有di+1个元素符合条件。
                            break;
                    }
                    else
                       ;
                  }
            }
            else //将ij的位置对调，即可实现反向输出
            {
               int sum = 0;
               for(int i=0;i<N;i++)
                   for(int j=0;j<N;j++)
              
                {
                    if(i+j == di)
                    {
                        System.out.println(data[i][j]);
                        sum++;
                        if(sum == di+1) //已经将所有符合条件的i，j找到，第di条对角线有di+1个元素符合条件。
                            break;
                    }

                }
            }
           
        }
    }
   
    public static void  main(String args[])
    {
        TestQ t = new TestQ();
        int a[][] = {{0,1,2},{3,4,5},{6,7,8}};
        int N = 3;
        t.m_print(a, N);
    }
}

public class RegExp {
   
   
    /**给定两个字符串，后者带有*号正则表达，表示1个或者多个字符。
     * 判别前后两个字符串是否相等。比如：
     * 1.cabbca/*ab*
     * 2.accbca/a**b*a
     * 3.abca/a*ca
     *
     * @param src
     * @param des
     * @return
     */
    boolean isSame(char src[], char des[])
    {
        int dIndex = 0, sIndex = 0;
        int dPre = -1; //前向指针
        int count = 0; //src串遍历时增加的距离
        boolean goonFlag = false;
        while (dIndex < des.length)
        {
            while(des[dIndex] == ‘*’)
            {
                System.out.println(“discard * at des["+dIndex+"]“);
                dIndex++;
                dPre++;
                if(dIndex == des.length) //到头了
                {
                    return true;
                }
            }

            count = 0;
            //找源串中的字符位置
            for( ; sIndex < src.length; sIndex++)
            {           
                System.out.println(“find in src string:src["+sIndex+"]“+src[sIndex]+“,des["+dIndex+"]“+des[dIndex]);
                if(src[sIndex] == des[dIndex])
                {
                    if(count > 0)
                    {
                        //还有一种情况，就是des的首字母与src偏移后某个字母相等。此时匹配也是失败
                        if(dPre == -1)
                            return false;
                        else if(des[dPre]==‘*’) //只要des之前的元素为*，则这一次判别就成功,继续des串的判别
                        {
                            goonFlag = true;
                        }
                        else
                            return false;
                    }
                    else //既然找到了src位置，而且正常偏移，则跳出循环，继续des串下一位的判别
                    {
                        goonFlag = true;
                    }   
                }
                else //如果src目前的字符元素不等于des的元素，则src指针自加
                {
                    count++;
                    System.out.println(“not equalls, goon. sIndex inc:”+(sIndex+1));
                }
            }
           
            if(goonFlag)
            {
                sIndex++; //src串前进到下一次比较的位置
                break;
            }
           
            dIndex++;
            dPre++;
        }
       
        if(sIndex < src.length)    return false; //des已经遍历完，而src尚未完成，则显然不匹配
       
        return true;
    }

    /**
     * @param args
     */
    public static void main(String[] args) {
        // TODO Auto-generated method stub
        RegExp re = new RegExp();
//        char src[] = {‘a’,'c’,'c’,'b’,'c’,'a’};
//        char des[] = {‘a’,'*’,'*’,'b’,'*’,'a’};
       
        char src[] = {‘a’,‘c’,‘c’,‘b’,‘c’,‘a’};
        char des[] = {‘c’,‘*’,‘*’,‘*’};        
        boolean b = re.isSame(src, des);
        System.out.println(“Result is :” + b);
    }

}

本文固定链接: http://www.caicono.cn/wordpress/2009/11/2010-algorithm-test.html | caicono的自由世界