老虎笔试9/30

1.开放地址方法

（1）线性探测

按顺序决定值时，如果某数据的值已经存在，则在原来值的基础上往后加一个单位，直至不发生哈希冲突。

（2）再平方探测

按顺序决定值时，如果某数据的值已经存在，则在原来值的基础上先加1的平方个单位，若仍然存在则减1的平方个单位。随之是2的平方，3的平方等等。直至不发生哈希冲突。

（3）伪随机探测

按顺序决定值时，如果某数据已经存在，通过随机函数随机生成一个数，在原来值的基础上加上随机数，直至不发生哈希冲突。

2.链式地址法（HashMap的哈希冲突解决方法）

对于相同的值，使用链表进行连接。使用数组存储每一个链表。

优点：

（1）拉链法处理冲突简单，且无堆积现象，即非同义词决不会发生冲突，因此平均查找长度较短；

（2）由于拉链法中各链表上的结点空间是动态申请的，故它更适合于造表前无法确定表长的情况；

（3）开放定址法为减少冲突，要求装填因子α较小，故当结点规模较大时会浪费很多空间。而拉链法中可取α≥1，且结点较大时，拉链法中增加的指针域可忽略不计，因此节省空间；

（4）在用拉链法构造的散列表中，删除结点的操作易于实现。只要简单地删去链表上相应的结点即可。
缺点：

指针占用较大空间时，会造成空间浪费，若空间用于增大散列表规模进而提高开放地址法的效率。

3.建立公共溢出区

建立公共溢出区存储所有哈希冲突的数据。

4.再哈希法

对于冲突的哈希值再次进行哈希处理，直至没有哈希冲突。

public class Solution {
    /**
     * 交换数组里n和0的位置
     *
     * @param array
     *            数组
     * @param len
     *            数组长度
     * @param n
     *            和0交换的数
     */
    // 不要修改以下函数内容
    public void swapWithZero(int[] array, int len, int n) {
       // Main.SwapWithZero(array, len, n);
    }
    // 不要修改以上函数内容


    /**
     * 通过调用swapWithZero方法来排
     *
     * @param array
     *            存储有[0,n)的数组
     * @param len
     *            数组长度
     */
    public void sort(int[] array, int len) {
        // 完成这个函数
    swapWithZero(array,len,array[0]);
for (int i = 1; i < array.length; i++) {
            int i1 = array[i];
            if (i1!=i) {
                  int temp=array[i1];
                swapWithZero(array, len, array[i1]);
                swapWithZero(array, len, i1);//还少了一步
                    swapWithZero(array,len,temp);
            }
        }
        // 完成这个函数
        // 将0移动到第一位
        }
    }
}

import java.util.*;

/**
 * Created by brayden on 2020/9/30 16:30
 */
//多少种不同的幸运的袋子。
//这个代码没有剪切和去重。会超时。只能过20%。
public class Main {
    public static void main(String[] args) {
        Scanner sc=new Scanner(System.in);
        int n=sc.nextInt();
        int[] arr=new int[n];
        List<Integer> list=new ArrayList<Integer>();
        for (int i = 0; i < n; i++) {
            arr[i]=sc.nextInt();
            list.add(arr[i]);
        }
        Collections.sort(list);//先排序，不然会乱序
        HashSet<Integer> set=new HashSet<>();
        List<Integer> n1=new LinkedList<>();
        getLukyNum(list,n1,set);
        System.out.println(set.size());
        for (Integer integer : set) {
            System.out.println(integer);
        }

    }
    public static void getLukyNum(List<Integer> list, List<Integer> n,HashSet<Integer> set){
        if (list.size()==0)return ;
        int count=0,ji=1;
        int num=0;
        String nums="";
        for (int i = 0; i < list.size(); i++) {
            count+=list.get(i);
            ji*=list.get(i);
            nums=nums+list.get(i);
        }
        num=Integer.parseInt(nums);
        if (count>ji){
            set.add(num);
        }
        for (int i = 0; i < list.size(); i++) {

            int aa=list.remove(i);
            n.add(aa);
            getLukyNum(list,n,set);
            list.add(i,aa);//放回原位
            n.remove(n.size()-1);
        }


    }


}