蓝桥杯砝码称重案例改善：使用Java集合框架来提高效率与准确性

短命女 2024-03-24 16:10 37阅读 0赞

#### 文章目录 ####

*  前言
 *   *  一、Java集合框架的组成
     *  二、HashSet 集合
     *  三、蓝桥杯省赛（砝码称重）
 *  总结

## 前言 ##

如果您是Java开发人员，那么Java集合框架就是您必须掌握的基础知识。Java集合框架提供了一组接口和实现类，用于存储和处理数据。它们使开发人员能够轻松地处理复杂的数据结构，从而使代码更加简化和易于维护。

### 一、Java集合框架的组成 ###

Java集合框架由接口和类组成，这些接口和类属于以下几个主要接口：

*  Collection：这是一个接口，它定义了一组通用的方法。许多其他类都实现了这个接口。一些常见的实现类包括 List、Set 和 Queue。
 *  List：这是集合框架中最常用的接口之一。它表示一个元素按照一定顺序存储，并且允许重复的集合。常见的实现类包括 ArrayList 和 LinkedList。
 *  Set：这个接口代表一个元素不允许重复的集合。常见的实现类包括 HashSet 和TreeSet。
 *  Queue：这是一个接口，它代表一组元素，排成一条线。常见的实现类包括 LinkedList 和 PriorityQueue。
 *  Map：这个接口代表了一组键值对。Map 中的键是唯一的，值可以重复。常见的实现类包括 HashMap 和 TreeMap。

### 二、HashSet 集合 ###

HashSet 是 Java 集合框架中的一个集合。它由哈希表支持，该哈希表用于存储集合中的元素。

如果您想创建一个 HashSet，请使用以下代码：

HashSet<String> names = new HashSet<String>();

上面的代码创建了一个类型为 String 的 HashSet，可以存储字符串。您可以更改泛型的类型，以便存储不同类型的元素。

下面是 HashSet 常用的方法：

*  add(E e)：将指定的元素添加到该集合中。
 *  addAll(Collection<? extends E> c)：将指定集合中的所有元素添加到此集合中。
 *  clear()：从 this 集合中删除所有的元素。
 *  remove(Object o)：从此集合中删除指定元素的单个实例（如果存在）。
 *  contains(Object o)：如果此集合包含指定的元素，则返回 true。
 *  iterator()：返回在此集合元素上进行迭代的迭代器。

下面是一个使用 HashSet 的例子：

//创建一个 Integer 类型的 HashSet，可以存储整数
    HashSet<Integer> set = new HashSet<>();
    
    //将整数添加到 HashSet 中
    set.add(10);
    set.add(20);
    set.add(30);
    
    //遍历 HashSet 中的元素
    Iterator<Integer> iterator = set.iterator();
    while (iterator.hasNext()) {
        
        System.out.println(iterator.next());
    }

上面的代码创建了一个 HashSet 类型的集合，然后将三个整数添加到集合中。最后，使用 iterator() 方法遍历该集合中的所有元素并将它们打印到控制台。

### 三、蓝桥杯省赛（砝码称重） ###

> **问题描述**
> 
> 你有一架天平和 N 个砝码，这 N 个砝码重量依次是 W\_1, W\_2, · · · , W\_N。
> 
> 请你计算一共可以称出多少种不同的重量？ 注意砝码可以放在天平两边。  
> **输入格式**
> 
> 输入的第一行包含一个整数 N。
> 
> 第二行包含 N 个整数：W\_1, W\_2, W\_3, · · · , W\_N。  
> **输出格式**
> 
> 输出一个整数代表答案。

java代码如下

package lanqiao;
    import java.util.HashSet;
    import java.util.LinkedList;
    import java.util.Scanner;
    
    public class Main {
        
        
        public static void main(String[] args) {
        
            Scanner scan = new Scanner(System.in);
            int n = scan.nextInt();
            int[] arr = new int[n];
            for (int i = 0; i < arr.length; i++) {
        
                arr[i] = scan.nextInt();
            }
            scan.close();
            HashSet<Integer> set = new HashSet<>(); //使用存储有序的 set 集合
            LinkedList<Integer> queue = new LinkedList<>(); //存储产生新的砝码值
            set.add(0); //赋予初始值,放 0 砝码的目的是为了存单个砝码的重量
            for (int i = 0; i < arr.length; i++) {
         //每次都放入一个砝码就和 set 中的所有元素：相加和相减的值再存入队列中
                for (Integer nextValue : set) {
        
                    queue.offer(arr[i] + nextValue);
                    queue.offer(Math.abs(arr[i] - nextValue));
                }
                while (! queue.isEmpty()) {
         //提取再放回set集合，以此反复
                    set.add(queue.poll());
                }
            }
            System.out.println(set.size() - 1); //- 1 去除 0 重量砝码
        }
    
    }

**解释**

1.  输入一个整数 n，表示接下来将输入 n 个整数。
2.  读取 n 个整数，存储到一个数组中。
3.  创建一个 HashSet 集合和一个 LinkedList 队列。在 HashSet 中存储所有可能的砝码重量。
4.  队列用于存储新计算得到的砝码重量。初始将 0 值存储在 HashSet 中，表示单个砝码的重量。
5.  遍历数组中的每个元素，对于 HashSet 中的每个值，它们与数组中的当前元素相加和相减的值也需要存储到队列中。
6.  遍历队列中的所有元素，并将它们存储到 HashSet 中。
7.  最终输出 HashSet 的大小减去 1，即为所有可能砝码的数量。
8.  这样做的时间复杂度是 O(n \* 2^n)，因为每个元素都会计算它与前面的所有元素的和与差，所以有 2^n 种可能性。但是由于  
    HashSet 的查询、插入操作都是 O(1) 的，因此总时间复杂度是可接受的。

**知识点补充**

*  HashSet 集合是一个不允许有重复元素的集合，其中的元素没有顺序。LinkedList 队列是一种先进先出（FIFO）的数据结构，即新元素被加入队列的尾部，而从队列中获取元素时从队列的头部开始弹出。
 *  在本代码中，HashSet 集合用于存储所有可能的砝码重量，LinkedList 队列用于存储产生新的砝码重量。在后续代码中，每次将HashSet中的元素和新的砝码重量相加或相减，并将结果存储到LinkedList队列中。

## 总结 ##

Java 集合框架提供了一组接口和实现类，用于存储和处理数据。使用集合框架能够轻松处理复杂的数据结构，从而使代码更加简化和易于维护。在集合框架中，HashSet 是一种常用的集合，使用哈希表支持存储集合中的元素。