寒光博客

[LanQiao]1949牌 组素数 全排列
题目大意 素数就是不能再进行等分的数。比如:2 3 5 7 11 等。 9 = 3 * 3 说明它可以3等分,因而...
扫描右侧二维码阅读全文
03
2019/08

[LanQiao]1949牌 组素数 全排列

题目大意

素数就是不能再进行等分的数。比如:2 3 5 7 11 等。
9 = 3 * 3 说明它可以3等分,因而不是素数。
我们国家在1949年建国。如果只给你 1 9 4 9 这4个数字卡片,
可以随意摆放它们的先后顺序(但卡片不能倒着摆放啊,我们不是在脑筋急转弯!),那么,你能组成多少个4位的素数呢?
比如:1949,4919 都符合要求。
请你提交:能组成的4位素数的个数,不要罗列这些素数!!
注意:不要提交解答过程,或其它的辅助说明文字。

分析

使用交换法 全排列

去重 调用了Set接口

补充知识:

HashSet
Java.util.HashSet类实现了Java.util.Set接口

  • (1)它不允许出现重复元素
    (2)不保证集合中的元素是按顺序存储的
    (3)允许包含值为null的元素,但最多只能有一个null元素
    (4)底层基于hash表实现,放入的对象必须实现hashCode()方法,放入的对象是以hashcode作为标识

代码

package BlueCup;

import java.util.HashSet;
import java.util.Set;

public class _1949牌 {
    public static void main(String[] args) {
        int[] num = {1, 9, 4, 9};
        solve(num, 0);
        System.out.println(res);
    }

    static Set<Integer> res = new HashSet<>();//去重

    //交换法 全排列
    private static void solve(int[] num, int k) {
        if (k == num.length) {//完成k个
            check(num);

        }
        for (int i = k; i < num.length; i++) {
            swap(num, i, k);
            solve(num, k + 1);
            swap(num, i, k);
        }
    }

    private static void check(int[] num) {//素数判断
        int ans = num[0] * 1000 + num[1] * 100 + num[2] * 10 + num[3];
        for (int i = 2; i * i <= ans; i++) {
            if (ans % i == 0) {
                return;
            }
        }
        res.add(ans);//是素数
        return;
    }

    private static void swap(int[] num, int i, int k) {
        int tmp = num[i];
        num[i] = num[k];
        num[k] = tmp;
    }
}
本文作者:Author:     文章标题:[LanQiao]1949牌 组素数 全排列
本文地址:https://dxoca.cn/Algorithm/215.html       百度未收录
版权说明:若无注明,本文皆为“Dxoca's blog (寒光博客)”原创,转载请保留文章出处。
Last modification:August 3rd, 2019 at 05:45 pm
如果觉得我的文章对你有用,请随意赞赏

Leave a Comment