蓝桥杯算法基础第一章测验

Exam07_TwoSingleNumbers

描述

一个整型数组里除了两个数字（互不相同）之外，其他的数字都出现了两次。请写程序找出这两个只出现一次的数字。要求时间复杂度是O(n)，空间复杂度是O(1)。

输入

第一行：数组的长度N(1<n<100000)
第二行：N个整数，空格隔开

输出

只出现了1次的那两个数，小的在前大的在后，空格隔开

思路

用Map存储数字出现的次数，遍历Map找出只出现一次的数字。

代码

import java.util.Arrays;
import java.util.HashMap;
import java.util.Map;
import java.util.Scanner;

public class Main {

    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        Map<Integer, Integer> map = new HashMap<>();
        int N = sc.nextInt();
        for(int i = 0; i < N; i++) {
            int tmp = sc.nextInt();
            map.put(tmp, map.getOrDefault(tmp, 0) + 1);
        }
        int[] res = new int[2];
        int i = 0;
        for(Map.Entry<Integer, Integer> entry : map.entrySet()) {
            if(entry.getValue() == 1) res[i++] = entry.getKey();
        }
        Arrays.sort(res);
        System.out.println(res[0] + " " + res[1]);
    }
    
}

Exam08_ChangeBit

描述

给定两个整数A和B，需要改变几个二进制位才能将A转为B。

输入

1行：A和B，空格隔开

输出

需要改变的位数

思路

整型值所占位数为32位，将A和B逐位比较，不同则计数器count加一，A和B同时无符号右移一位。

代码

import java.util.Scanner;

public class Main {

    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int A = sc.nextInt();
        int B = sc.nextInt();

        int count = 0;
        int n = 32;
        while (n-- != 0) {
            if ((A & 1) != (B & 1)) {
                count++;
            }
            A >>>= 1;
            B >>>= 1;
        }

        System.out.println(count);
    }

}

Exam09_StrangeDonate

描述

地产大亨Q先生临终的遗愿是：拿出100万元给X社区的居民抽奖，以稍慰藉心中愧疚。
麻烦的是，他有个很奇怪的要求：

1. 100万元必须被正好分成若干份（不能剩余）。每份必须是7的若干次方元。比如：1元, 7元，49元，343元，…

2. 相同金额的份数不能超过5份。

3. 在满足上述要求的情况下，分成的份数越多越好！

请你帮忙计算一下，最多可以分为多少份？

输入

固定输入：1000000

输出

最多可以分为多少份

思路

设1000000 = x₀7⁰ + x₁7¹ + x₂7² + x₃7³ + … + x_i*7ⁱ ，其中x_i是相同金额的份数。而这个等式和7进制的按权展开很像，我不禁想到如果把1000000转换成7进制的话，那么7进制的每一位就是x_i ，相加得出结果。

代码

public class Main {

    public static void main(String[] args) {
        System.out.println(16); //11333311
    }

}