恒生电子笔试题

1、给定N张扑克牌和一个随机函数，设计一个洗牌算法

做这道题的时候，开始不太清楚在线编码平台的使用，确实用的比较少，平时做ACM类的题和本地编译器比较熟悉，在线编译器不是很熟悉，所以搞了很多乌龙，最后java没写出来，转战c++编码，好在写出来了，最后仔细读要求意识是需要导包的问题。哈哈哈。敲c++的时候突然意识到这点，没时间改，就直接交了。现在补一下java的代码，实现起来并不难。

package com.lxw.demo;

import java.util.Random;

public class Demo02 {

    /**
     * 初始化数组
     * @param a
     */
    private static void init(int[] a){
        for(int i=0;i<a.length;i++){
            a[i]=i+1;
        }
    }

    /**
     * 输出
     * @param a
     */
    private static void print(int[] a){
        for(int i=0;i<a.length;i++){
            System.out.print(a[i]+" ");
        }
        System.out.println();
    }

    /**
     * 洗牌
     * @param a
     */
    private static void shuffle(int[] a){
        int len=a.length;
        //计算机的随机数并发真正的随机数，而是由一系列的随机函数生成的确定序列
        Random random=new Random(System.currentTimeMillis());
        for(int i=0;i<len-1;i++){
            //生成i后面的随机数
            int pos=random.nextInt(len-i)+i;
            System.out.println("pos="+pos);
            //把a[i]和随机出的排在a[i]后面的a[pos]交换一下
            int tmp=a[i];
            a[i]=a[pos];
            a[pos]=tmp;
        }
    }

    public static void main(String[] args) throws InterruptedException {
        int[] a =new int[5];
        init(a);
        shuffle(a);
        print(a);
        Thread.sleep(2000);
        init(a);
        shuffle(a);
        print(a);
    }
}

2、在n个数字中，找出所有和为SUM的组合

package com.lxw.demo;

import java.util.ArrayList;
import java.util.Arrays;

public class Demo03 {
    public static void main(String[] args) {
        int[] a = {2, 6, 1, 7, 4, 9};
        final int SUM = 20;
        ArrayList<String> x = findAll(a, SUM);
        for(String s:x) {
            System.out.println(s);
        }
    }


    private static ArrayList<String> findAll(int[] a, final int SUM) {
        ArrayList<String> result = new ArrayList<>();    //存放的是所有找到的表达式
        Arrays.sort(a);    //对初始数据进行排序，便于算法的实现
        ArrayList<Integer> l = new ArrayList<>();    //存放的是当前找到的合法的元素(数字)，这些元素的和小于SUM
        find(a, SUM, 0, l, result);    //通过递归的方式进行查找
        return result; //返回所有的表达式
    }


    //递归函数，每一次的动作很简单，
    //在已经找到的n个元素的基础上（原则就是和小于SUM），寻找第n+1个元素，
    private static void find(int[] a, final int SUM, int cur, ArrayList<Integer> l, ArrayList<String> result) {
        int start = l.size() == 0 ? 0 : l.get(l.size()-1) + 1;    //当前元素的查找范围的起始位置,0/获取l的当前元素+1,得比最后一个满足的元素大,不然就会从这个元素开始找，就会出现数据重复
        for(int i=start; i<a.length; i++) {    //从起始位置到结束位置，查找合适的元素
            cur += a[i];    //在前面元素的和的基础上，加上当前元素,cur代表当前和
            if(cur<SUM) {    //如果cur<SUM，证明当前元素(第n+1个)合法，继续寻找第n+2个元素
                l.add(i);
                find(a, SUM, cur, l, result);
                //下面两行：消除第i个元素的影响，为了试验第i+1个元素做准备
                cur -= a[i];
                l.remove(l.size()-1);
            }else if(cur == SUM) {    //如果等于SUM，证明找到了表达式
                // 构造表达式字符串，并存入result
                StringBuilder s = new StringBuilder();
                for(int x:l) {
                    s.append(a[x]);
                    s.append(" + ");
                }
                s.append(a[i]);
                s.append(" = ");
                s.append(SUM);
                result.add(s.toString());

                break;    //回溯到上一个状态
            }else {    //如果大于SUM，也回溯到上一个状态
                break;
            }
        }
    }
}