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

2019-10-26 00:00:00 算法 基础 测验

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 = x070 + x171 + x272 + x373 + … + xi*7i ,其中xi是相同金额的份数。而这个等式和7进制的按权展开很像,我不禁想到如果把1000000转换成7进制的话,那么7进制的每一位就是xi ,相加得出结果。

代码

public class Main {

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

}
    原文作者:星海|universe
    原文地址: https://www.cnblogs.com/huowuyan/p/11739103.html
    本文转自网络文章,转载此文章仅为分享知识,如有侵权,请联系博主进行删除。

相关文章