算法很美 java版 一

发表于 阅读次数：
本文字数： 4.2k 阅读时长 ≈ 4 分钟

假象

蓝桥杯 java

算法练习题

位运算的运用

1~1000这1000个数存放在一个1001个元素的数组中 其中只有一个数值是重复的 找出其中重复的元素 不用辅助存储空间

解题思路

将每个数组的每个元素与数组的每个元素做异或 因为相同元素做异或为0 所以重复的元素会多出来 这样就可以找到重复的元素了

不用辅助存储空间

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
public static void main(String[] args) {
        //初始化
        int N = 1001;
        Integer[] arr = new Integer[N];

        //数组赋值
        for(int i = 0; i < arr.length - 1; i++){
            arr[i] = i + 1;
        }

        //随机生成一个数放到最后一个位置
        arr[arr.length - 1] = new Random().nextInt(N - 1) + 1;

        //随机生成一个数组下标
        int index = new Random().nextInt(N);

        //将最后一个位置上的随机数与随机生成的下标数进行交换
        ArrOperate.swap(arr,index,arr.length - 1);

        //显示数组
        ArrOperate.printArr(arr);

        int x1 = 0;

        for (int i = 1; i <= arr.length - 1; i++) {
            //x1为1一直异或到1000
            x1 = (x1 ^ i);
        }

        for (int i = 0; i < arr.length; i++){
            // 上面的x1再同时与随机生成的数组异或得出重复的那个数
            x1 = x1 ^ arr[i];
        }

        System.out.println(x1);
}

使用辅助存储空间

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
public static void main(String[] args) {
        //初始化
        int N = 10;
        Integer[] arr = new Integer[N];

        //数组赋值
        for(int i = 0; i < arr.length - 1; i++){
            arr[i] = i + 1;
        }

        //随机生成一个数放到最后一个位置
        arr[arr.length - 1] = new Random().nextInt(N - 1) + 1;

        //随机生成一个数组下标
        int index = new Random().nextInt(N);

        //将最后一个位置上的随机数与随机生成的下标数进行交换
        ArrOperate.swap(arr,index,arr.length - 1);

        //显示数组
        ArrOperate.printArr(arr);
        //开辟了一块新数组
        int[] arr2 = new int[N];

        for(int i = 0; i < arr2.length; i++){
            //放入到新数组中并对应相对应的位置以及数量
            arr2[arr[i]]++;
        }

        for(int i = 0; i < arr2.length; i++){
            //数量如果为2则便是该数重复
            if(arr2[i] == 2){
                System.out.println(i);
                break;
            }
        }
    }

一个数组除了某一个数字之外 其他的数字都出现了两次 找出落单的那个数

解题思路

因为其他数字都出现两次 所以可连续做异或 因为相同异或为0 任何数与0异或是其本身

1
2
3
4
5
6
7
8
9
10
11
12
public static void main(String[] args) {

        Integer[] arr = new Integer[]{1,2,3,4,5,1,2,4,5};

        int result = 0;

        for(int i = 0; i < arr.length; i++){
            result ^= arr[i];
        }

        System.out.println(result);
    }

一个整数 求出该二进制中1的个数

解题思路

先将整数转换成二进制数 依次判断每个位上的数是否为1

位运算方法

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
public static void main(String[] args) {

        int number = new Random().nextInt(100);
        int qjNumber = number;

        int result = 0;
        while (number != 0){
            if((number & 1) == 1){
                result++;
            }
            number = number >> 1;
        }
        System.out.println(Integer.toString(qjNumber,2));
        System.out.println(qjNumber + "中1的位数为" + result);
    }

普通方法

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
public static void main(String[] args) {

        int number = new Random().nextInt(100);
        int qjNumber = number;
        String result = "";
        int yuShu = 0;

        while (number != 0){
            yuShu = number % 2;
            number = number / 2;
            result += yuShu;
        }
        char[] ejz = result.toCharArray();

        int sum = 0;

        for(int i = 0; i < ejz.length; i++){
            if(ejz[i] == '1'){
                sum++;
            }
        }
        //Integer.toString可直接将十进制转换为相对应的进制
        System.out.println(Integer.toString(qjNumber,2));
        System.out.println(qjNumber + "的二进制中有" + sum + "位是1");
    }

用一条语句判断一个整数是不是2的整数次方

解题思路

因为2的整数次方有个规律 就是当前数减1 与 当前数做与运算总是为0 所以按照这个解题即可

2 -> 0000 0010 2-1= 1 -> 0001

4 -> 0000 0100 4-1=3 -> 0011

8 -> 0000 1000 8-1=7 -> 0111

1
2
3
4
5
6
7
8
9
10
public static void main(String[] args) {

        Scanner scanner = new Scanner(System.in);

        int number = scanner.nextInt();

        System.out.println(((number - 1) & number) == 0
                ?"是2的整数次方" : "不是2的整数次方");

    }

将整数二进制位的奇偶位互换

解题思路

首先将原二进制数用1010 1010 1010 …进行与运算 这时会得到 原二进制数0原二进制数0 原二进制数0原二进制数0 原二进制数0原二进制数0 … 这时再重新将原二进制与 0101 0101 0101 … 进行与运算 这时会得到 0原二进制数0原二进制数 0原二进制数0原二进制数 0原二进制数0原二进制数 … 这时将一个二进制进行左移一位 一个二进制进行右移一位 然后异或即可得到二进制的奇偶位交换

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
public static void main(String[] args) {

        Scanner scanner = new Scanner(System.in);

        int a = scanner.nextInt();

        System.out.println(Integer.toString(a,2));

        //这里实际是 1010 1010 1010 ... 转换成十六进制方便阅读 一共32位 所以就是8个a
        int ou = a & 0xaaaaaaaa;
        //这里实际是 0101 0101 0101 ... 转换成十六进制方便阅读 一共32位 所以就是8个5
        int ji = a & 0x55555555;

        //偶数右移一位 奇数左移一位 然后进行异或即可完成奇偶交换位置
        int b = (ou >> 1) ^ (ji << 1);

        System.out.println(Integer.toString(b,2));

    }

零到一之间浮点实数的二进制表示

解题思路

就是正常的计算小数转换成二进制的计算方法即可

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
public static void main(String[] args) {

        Scanner scanner = new Scanner(System.in);

        double number = scanner.nextDouble();

        StringBuilder stringBuilder = new StringBuilder("0.");

        while (number > 0){

            double r = number * 2;

            if(r >= 1){
                stringBuilder.append("1");
                number = r - 1;
            }else{

                stringBuilder.append("0");
                number = r;
            }
            if(stringBuilder.length() > 34){
                System.out.println("error");
                return;
            }

        }
        System.out.println(stringBuilder);
    }

你知道的越多，你不知道的越多 嘿 我是小博 带你一起看我目之所及的世界……

-------------本文结束 感谢您的阅读-------------

本文标题:算法很美 java版 一

文章作者:小博

发布时间:2022年03月02日 - 16:21

最后更新:2022年03月02日 - 16:27

原始链接:https://codexiaobo.github.io/posts/2593628355/

许可协议: 署名-非商业性使用-禁止演绎 4.0 国际 转载请保留原文链接及作者。