精华内容
下载资源
问答
  • Java实现Fibonacci取余

    2020-12-22 10:13:54
    Description Fibonacci数列的递推公式为:Fn=Fn-1+Fn-2,其中F1=F2=1。 当n比较大时,Fn也非常大,现在我们想知道,Fn除以10007的余数是...import java.util.Scanner; public class Demo12Fibonacci { public static
  • Java集合面试题

    万次阅读 多人点赞 2019-06-25 14:46:19
    Java集合面试题 Java 集合框架的基础接口有哪些? Collection ,为集合层级的根接口。一个集合代表一组对象,这些对象即为它的元素。Java 平台不提供这个接口任何直接的实现。 Set ,是一个不能包含重复元素的集合...

    Java集合面试题

    Java 集合框架的基础接口有哪些?

    • Collection ,为集合层级的根接口。一个集合代表一组对象,这些对象即为它的元素。Java 平台不提供这个接口任何直接的实现。
      • Set ,是一个不能包含重复元素的集合。这个接口对数学集合抽象进行建模,被用来代表集合,就如一副牌。
      • List ,是一个有序集合,可以包含重复元素。你可以通过它的索引来访问任何元素。List 更像长度动态变换的数组。
    • Map ,是一个将 key 映射到 value 的对象。一个 Map 不能包含重复的 key,每个 key 最多只能映射一个 value 。
    • 一些其它的接口有 Queue、Dequeue、SortedSet、SortedMap 和 ListIterator 。

    ? 为何 Collection 不从 Cloneable 和 Serializable 接口继承?

    Collection 接口指定一组对象,对象即为它的元素。

    • 如何维护这些元素由 Collection 的具体实现决定。例如,一些如 List 的 Collection 实现允许重复的元素,而其它的如 Set 就不允许。
    • 很多 Collection 实现有一个公有的 clone 方法。然而,把它放到集合的所有实现中也是没有意义的。这是因为 Collection 是一个抽象表现,重要的是实现。

    当与具体实现打交道的时候,克隆或序列化的语义和含义才发挥作用。所以,具体实现应该决定如何对它进行克隆或序列化,或它是否可以被克隆或序列化。在所有的实现中授权克隆和序列化,最终导致更少的灵活性和更多的限制,特定的实现应该决定它是否可以被克隆和序列化

    为何 Map 接口不继承 Collection 接口?

    尽管 Map 接口和它的实现也是集合框架的一部分,但 Map 不是集合,集合也不是 Map。因此,Map 继承 Collection 毫无意义,反之亦然。

    如果 Map 继承 Collection 接口,那么元素去哪儿?Map 包含 key-value 对,它提供抽取 key 或 value 列表集合( Collection )的方法,但是它不适合“一组对象”规范。

    ? 为何 Map 接口不继承 Collection 接口?

    尽管 Map 接口和它的实现也是集合框架的一部分,但 Map 不是集合,集合也不是 Map。因此,Map 继承 Collection 毫无意义,反之亦然。

    如果 Map 继承 Collection 接口,那么元素去哪儿?Map 包含 key-value 对,它提供抽取 key 或 value 列表集合( Collection )的方法,但是它不适合“一组对象”规范。

    ? Collection 和 Collections 的区别?

    • Collection ,是集合类的上级接口,继承与他的接口主要有 Set 和List 。
    • Collections ,是针对集合类的一个工具类,它提供一系列静态方法实现对各种集合的搜索、排序、线程安全化等操作。

    ? 集合框架里实现的通用算法有哪些?

    Java 集合框架提供常用的算法实现,比如排序和搜索。

    Collections类包含这些方法实现。大部分算法是操作 List 的,但一部分对所有类型的集合都是可用的。部分算法有排序、搜索、混编、最大最小值。

    ? 集合框架底层数据结构总结

    1)List

    • ArrayList :Object 数组。
    • Vector :Object 数组。
    • LinkedList :双向链表(JDK6 之前为循环链表,JDK7 取消了循环)。

    2)Map

    • HashMap :
      • JDK8 之前,HashMap 由数组+链表组成的,数组是HashMap的主体,链表则是主要为了解决哈希冲突而存在的(“拉链法”解决冲突)。
      • JDK8 以后,在解决哈希冲突时有了较大的变化,当链表长度大于阈值(默认为 8 )时,将链表转化为红黑树,以减少搜索时间。
    • LinkedHashMap :LinkedHashMap 继承自 HashMap,所以它的底层仍然是基于拉链式散列结构即由数组和链表或红黑树组成。另外,LinkedHashMap 在上面结构的基础上,增加了一条双向链表,使得上面的结构可以保持键值对的插入顺序。同时通过对链表进行相应的操作,实现了访问顺序相关逻辑。详细可以查看:《LinkedHashMap 源码详细分析(JDK1.8)》
    • Hashtable :数组+链表组成的,数组是 HashMap 的主体,链表则是主要为了解决哈希冲突而存在的。
    • TreeMap :红黑树(自平衡的排序二叉树)。

    3)Set

    • HashSet :无序,唯一,基于 HashMap 实现的,底层采用 HashMap 来保存元素。
    • LinkedHashSet :LinkedHashSet 继承自 HashSet,并且其内部是通过 LinkedHashMap 来实现的。有点类似于我们之前说的LinkedHashMap 其内部是基于 HashMap 实现一样,不过还是有一点点区别的。
    • TreeSet :有序,唯一,红黑树(自平衡的排序二叉树)。

    什么是迭代器(Iterator)?

    Iterator 接口,提供了很多对集合元素进行迭代的方法。每一个集合类都包含了可以返回迭代器实例的迭代方法。迭代器可以在迭代的过程中删除底层集合的元素,但是不可以直接调用集合的 #remove(Object Obj) 方法删除,可以通过迭代器的 #remove() 方法删除。

    ? Iterator 和 ListIterator 的区别是什么?

    • Iterator 可用来遍历 Set 和 List 集合,但是 ListIterator 只能用来遍历 List。
    • Iterator 对集合只能是前向遍历,ListIterator 既可以前向也可以后向。
    • ListIterator 实现了 Iterator 接口,并包含其他的功能。比如:增加元素,替换元素,获取前一个和后一个元素的索引等等。

    ? 快速失败(fail-fast)和安全失败(fail-safe)的区别是什么?

    差别在于 ConcurrentModification 异常:

    • 快速失败:当你在迭代一个集合的时候,如果有另一个线程正在修改你正在访问的那个集合时,就会抛出一个 ConcurrentModification 异常。 在 java.util 包下的都是快速失败。
    • 安全失败:你在迭代的时候会去底层集合做一个拷贝,所以你在修改上层集合的时候是不会受影响的,不会抛出 ConcurrentModification 异常。在 java.util.concurrent 包下的全是安全失败的。

    ? 如何删除 List 中的某个元素?

    有两种方式,分别如下:

    • 方式一,使用 Iterator ,顺序向下,如果找到元素,则使用 remove 方法进行移除。
    • 方式二,倒序遍历 List ,如果找到元素,则使用 remove 方法进行移除。

    ? Enumeration 和 Iterator 接口有什么不同?

    • Enumeration 跟 Iterator 相比较快两倍,而且占用更少的内存。
    • 但是,Iterator 相对于 Enumeration 更安全,因为其他线程不能修改当前迭代器遍历的集合对象。同时,Iterators 允许调用者从底层集合中移除元素,这些 Enumerations 都没法完成。

    对于很多胖友,可能并未使用过 Enumeration 类,所以可以看看 《Java Enumeration 接口》 文章。

    ? 为何 Iterator 接口没有具体的实现?

    Iterator 接口,定义了遍历集合的方法,但它的实现则是集合实现类的责任。每个能够返回用于遍历的 Iterator 的集合类都有它自己的 Iterator 实现内部类。

    这就允许集合类去选择迭代器是 fail-fast 还是 fail-safe 的。比如,ArrayList 迭代器是 fail-fast 的,而 CopyOnWriteArrayList 迭代器是 fail-safe 的。

    Comparable 和 Comparator 的区别?

    • Comparable 接口,在 java.lang 包下,用于当前对象和其它对象的比较,所以它有一个 #compareTo(Object obj) 方法用来排序,该方法只有一个参数。
    • Comparator 接口,在 java.util 包下,用于传入的两个对象的比较,所以它有一个 #compare(Object obj1, Object obj2) 方法用来排序,该方法有两个参数。

    详细的,可以看看 《Java 自定义比较器》 文章,重点是如何自己实现 Comparable 和 Comparator 的方法。

    ? compareTo 方法的返回值表示的意思?

    • 大于 0 ,表示对象大于参数对象。
    • 小于 0 ,表示对象小于参数对象
    • 等于 0 ,表示两者相等。

    ? 如何对 Object 的 List 排序?

    • Object[] 数组进行排序时,我们可以用 Arrays#sort(...) 方法。
    • List<Object> 数组进行排序时,我们可以用 Collections#sort(...) 方法。

    有哪些关于 Java 集合框架的最佳实践?

    • 基于应用的需求来选择使用正确类型的集合,这对性能来说是非常重要的。例如,如果元素的大小是固定的,并且知道优先级,我们将会使用一个 Array ,而不是 ArrayList 。
    • 一些集合类允许我们指定他们的初始容量。因此,如果我们知道存储数据的大概数值,就可以避免重散列或者大小的调整。
    • 总是使用泛型来保证类型安全,可靠性和健壮性。同时,使用泛型还可以避免运行时的 ClassCastException 异常。
    • 在 Map 中使用 JDK 提供的不可变类作为一个 key,这样可以避免 hashcode 的实现和我们自定义类的 equals 方法。
    • 应该依照接口而不是实现来编程。
    • 返回零长度的集合或者数组,而不是返回一个 null ,这样可以防止底层集合是空的。

    区别

    List 和 Set 区别?

    List,Set 都是继承自 Collection 接口。

    • List 特点:元素有放入顺序,元素可重复。
    • Set 特点:元素无放入顺序,元素不可重复,重复元素会覆盖掉。

    注意:元素虽然无放入顺序,但是元素在 Set 中的位置是有该元素的 hashcode 决定的,其位置其实是固定的。

    另外 List 支持 for 循环,也就是通过下标来遍历,也可以用迭代器,但是 Set 只能用迭代,因为他无序,无法用下标来取得想要的值。

    Set 和 List 对比:

    • Set:检索元素效率高,删除和插入效率低,插入和删除不会引起元素位置改变。
    • List:和数组类似,List 可以动态增长,查找元素效率低,插入删除元素效率,因为可能会引起其他元素位置改变。

    List 和 Map 区别?

    • List 是对象集合,允许对象重复。
    • Map 是键值对的集合,不允许 key 重复。

    Array 和 ArrayList 有何区别?什么时候更适合用 Array?

    • Array 可以容纳基本类型和对象,而 ArrayList 只能容纳对象。
    • Array 是指定大小的,而 ArrayList 大小是固定的,可自动扩容。
    • Array 没有提供 ArrayList 那么多功能,比如 addAll、removeAll 和 iterator 等。

    尽管 ArrayList 明显是更好的选择,但也有些时候 Array 比较好用,比如下面的三种情况。

    • 1、如果列表的大小已经指定,大部分情况下是存储和遍历它们
    • 2、对于遍历基本数据类型,尽管 Collections 使用自动装箱来减轻编码任务,在指定大小的基本类型的列表上工作也会变得很慢。
    • 3、如果你要使用多维数组,使用 [][] 比 List 会方便。

    ArrayList 与 LinkedList 区别?

    ? ArrayList

    • 优点:ArrayList 是实现了基于动态数组的数据结构,因为地址连续,一旦数据存储好了,查询操作效率会比较高(在内存里是连着放的)。
    • 缺点:因为地址连续,ArrayList 要移动数据,所以插入和删除操作效率比较低。

    ? LinkedList

    • 优点:LinkedList 基于链表的数据结构,地址是任意的,所以在开辟内存空间的时候不需要等一个连续的地址。对于新增和删除操作 add 和 remove ,LinedList 比较占优势。LinkedList 适用于要头尾操作或插入指定位置的场景。
    • 缺点:因为 LinkedList 要移动指针,所以查询操作性能比较低。

    ? 适用场景分析

    • 当需要对数据进行对随机访问的情况下,选用 ArrayList 。

    • 当需要对数据进行多次增加删除修改时,采用 LinkedList 。

      如果容量固定,并且只会添加到尾部,不会引起扩容,优先采用 ArrayList 。

    • 当然,绝大数业务的场景下,使用 ArrayList 就够了。主要是,注意好避免 ArrayList 的扩容,以及非顺序的插入。

    ? ArrayList 是如何扩容的?

    直接看 《ArrayList 动态扩容详解》 文章,很详细。主要结论如下:

    • 如果通过无参构造的话,初始数组容量为 0 ,当真正对数组进行添加时,才真正分配容量。每次按照 1.5 倍(位运算)的比率通过 copeOf 的方式扩容。
    • 在 JKD6 中实现是,如果通过无参构造的话,初始数组容量为10,每次通过 copeOf 的方式扩容后容量为原来的 1.5 倍。

    重点是 1.5 倍扩容,这是和 HashMap 2 倍扩容不同的地方。

    ArrayList 集合加入 1 万条数据,应该怎么提高效率?

    ArrayList 的默认初始容量为 10 ,要插入大量数据的时候需要不断扩容,而扩容是非常影响性能的。因此,现在明确了 10 万条数据了,我们可以直接在初始化的时候就设置 ArrayList 的容量!

    这样就可以提高效率了~

    ArrayList 与 Vector 区别?

    ArrayList 和 Vector 都是用数组实现的,主要有这么三个区别:

    • 1、Vector 是多线程安全的,线程安全就是说多线程访问同一代码,不会产生不确定的结果,而 ArrayList 不是。这个可以从源码中看出,Vector 类中的方法很多有 synchronized 进行修饰,这样就导致了 Vector 在效率上无法与 ArrayList 相比。

      Vector 是一种老的动态数组,是线程同步的,效率很低,一般不赞成使用。

    • 2、两个都是采用的线性连续空间存储元素,但是当空间不足的时候,两个类的增加方式是不同。

    • 3、Vector 可以设置增长因子,而 ArrayList 不可以。

    适用场景分析:

    • 1、Vector 是线程同步的,所以它也是线程安全的,而 ArrayList 是线程无需同步的,是不安全的。如果不考虑到线程的安全因素,一般用 ArrayList 效率比较高。

      实际场景下,如果需要多线程访问安全的数组,使用 CopyOnWriteArrayList 。

    • 2、如果集合中的元素的数目大于目前集合数组的长度时,在集合中使用数据量比较大的数据,用 Vector 有一定的优势。

      这种情况下,使用 LinkedList 更合适。

    HashMap 和 Hashtable 的区别?

    Hashtable 是在 Java 1.0 的时候创建的,而集合的统一规范命名是在后来的 Java2.0 开始约定的,而当时其他一部分集合类的发布构成了新的集合框架。

    • Hashtable 继承 Dictionary ,HashMap 继承的是 Java2 出现的 Map 接口。
    • 2、HashMap 去掉了 Hashtable 的 contains 方法,但是加上了 containsValue 和 containsKey 方法。
    • 3、HashMap 允许空键值,而 Hashtable 不允许。
    • 【重点】4、HashTable 是同步的,而 HashMap 是非同步的,效率上比 HashTable 要高。也因此,HashMap 更适合于单线程环境,而 HashTable 适合于多线程环境。
    • 5、HashMap 的迭代器(Iterator)是 fail-fast 迭代器,HashTable的 enumerator 迭代器不是 fail-fast 的。
    • 6、HashTable 中数组默认大小是 11 ,扩容方法是 old * 2 + 1 ,HashMap 默认大小是 16 ,扩容每次为 2 的指数大小。

    一般现在不建议用 HashTable 。主要原因是两点:

    • 一是,HashTable 是遗留类,内部实现很多没优化和冗余。
    • 二是,即使在多线程环境下,现在也有同步的 ConcurrentHashMap 替代,没有必要因为是多线程而用 Hashtable 。

    ? Hashtable 的 #size() 方法中明明只有一条语句 “return count;” ,为什么还要做同步?

    同一时间只能有一条线程执行固定类的同步方法,但是对于类的非同步方法,可以多条线程同时访问。所以,这样就有问题了,可能线程 A 在执行 Hashtable 的 put 方法添加数据,线程 B 则可以正常调用 #size() 方法读取 Hashtable 中当前元素的个数,那读取到的值可能不是最新的,可能线程 A 添加了完了数据,但是没有对 count++ ,线程 B 就已经读取 count 了,那么对于线程 B 来说读取到的 count 一定是不准确的。

    而给 #size() 方法加了同步之后,意味着线程 B 调用 #size() 方法只有在线程 A 调用 put 方法完毕之后才可以调用,这样就保证了线程安全性

    HashSet 和 HashMap 的区别?

    • Set 是线性结构,值不能重复。HashSet 是 Set 的 hash 实现,HashSet 中值不能重复是用 HashMap 的 key 来实现的。

    • Map 是键值对映射,可以空键空值。HashMap 是 Map 的 hash 实现,key 的唯一性是通过 key 值 hashcode 的唯一来确定,value 值是则是链表结构。

      因为不同的 key 值,可能有相同的 hashcode ,所以 value 值需要是链表结构。

    他们的共同点都是 hash 算法实现的唯一性,他们都不能持有基本类型,只能持有对象。

    为了更好的性能,Netty 自己实现了 key 为基本类型的 HashMap ,例如 IntObjectHashMap

    HashSet 和 TreeSet 的区别?

    • HashSet 是用一个 hash 表来实现的,因此,它的元素是无序的。添加,删除和 HashSet 包括的方法的持续时间复杂度是 O(1)
    • TreeSet 是用一个树形结构实现的,因此,它是有序的。添加,删除和 TreeSet 包含的方法的持续时间复杂度是 O(logn)

    ? 如何决定选用 HashMap 还是 TreeMap?

    • 对于在 Map 中插入、删除和定位元素这类操作,HashMap 是最好的选择。
    • 然而,假如你需要对一个有序的 key 集合进行遍历, TreeMap 是更好的选择。

    基于你的 collection 的大小,也许向 HashMap 中添加元素会更快,再将 HashMap 换为 TreeMap 进行有序 key 的遍历。

    HashMap 和 ConcurrentHashMap 的区别?

    ConcurrentHashMap 是线程安全的 HashMap 的实现。主要区别如下:

    • 1、ConcurrentHashMap 对整个桶数组进行了分割分段(Segment),然后在每一个分段上都用 lock 锁进行保护,相对 于Hashtable 的 syn 关键字锁的粒度更精细了一些,并发性能更好。而 HashMap 没有锁机制,不是线程安全的。

      JDK8 之后,ConcurrentHashMap 启用了一种全新的方式实现,利用 CAS 算法。

    • 2、HashMap 的键值对允许有 null ,但是 ConCurrentHashMap 都不允许。

    队列和栈是什么,列出它们的区别?

    栈和队列两者都被用来预存储数据。

    • java.util.Queue 是一个接口,它的实现类在Java并发包中。队列允许先进先出(FIFO)检索元素,但并非总是这样。Deque 接口允许从两端检索元素。
    • 栈与队列很相似,但它允许对元素进行后进先出(LIFO)进行检索。
      • Stack 是一个扩展自 Vector 的类,而 Queue 是一个接口。

    原理

    HashMap 的工作原理是什么?

    我们知道在 Java 中最常用的两种结构是数组和模拟指针(引用),几乎所有的数据结构都可以利用这两种来组合实现,HashMap 也是如此。实际上 HashMap 是一个**“链表散列”**。

    HashMap 是基于 hashing 的原理。

    HashMap 图解

    • 我们使用 #put(key, value) 方法来存储对象到 HashMap 中,使用 get(key) 方法从 HashMap 中获取对象。
    • 当我们给 #put(key, value) 方法传递键和值时,我们先对键调用 #hashCode() 方法,返回的 hashCode 用于找到 bucket 位置来储存 Entry 对象。

    ? 当两个对象的 hashCode 相同会发生什么?

    因为 hashcode 相同,所以它们的 bucket 位置相同,“碰撞”会发生。

    因为 HashMap 使用链表存储对象,这个 Entry(包含有键值对的 Map.Entry 对象)会存储在链表中。

    ? hashCode 和 equals 方法有何重要性?

    HashMap 使用 key 对象的 #hashCode()#equals(Object obj) 方法去决定 key-value 对的索引。当我们试着从 HashMap 中获取值的时候,这些方法也会被用到。

    • 如果这两个方法没有被正确地实现,在这种情况下,两个不同 Key 也许会产生相同的 #hashCode()#equals(Object obj) 输出,HashMap 将会认为它们是相同的,然后覆盖它们,而非把它们存储到不同的地方。

    同样的,所有不允许存储重复数据的集合类都使用 #hashCode()#equals(Object obj) 去查找重复,所以正确实现它们非常重要。#hashCode()#equals(Object obj) 方法的实现,应该遵循以下规则:

    • 如果 o1.equals(o2) ,那么 o1.hashCode() == o2.hashCode() 总是为 true 的。
    • 如果 o1.hashCode() == o2.hashCode() ,并不意味 o1.equals(o2) 会为 true

    ? HashMap 默认容量是多少?

    默认容量都是 16 ,负载因子是 0.75 。就是当 HashMap 填充了 75% 的 busket 是就会扩容,最小的可能性是(16 * 0.75 = 12),一般为原内存的 2 倍。

    ? 有哪些顺序的 HashMap 实现类?

    • LinkedHashMap ,是基于元素进入集合的顺序或者被访问的先后顺序排序。
    • TreeMap ,是基于元素的固有顺序 (由 Comparator 或者 Comparable 确定)。

    ? 我们能否使用任何类作为 Map 的 key?

    我们可以使用任何类作为 Map 的 key ,然而在使用它们之前,需要考虑以下几点:

    • 1、如果类重写了 equals 方法,它也应该重写 hashcode 方法。

    • 2、类的所有实例需要遵循与 equals 和 hashcode 相关的规则。

    • 3、如果一个类没有使用 equals ,你不应该在 hashcode 中使用它。

    • 4、用户自定义 key 类的最佳实践是使之为不可变的,这样,hashcode 值可以被缓存起来,拥有更好的性能。不可变的类也可以确保hashcode 和 equals 在未来不会改变,这样就会解决与可变相关的问题了。

      比如,我有一个 类MyKey ,在 HashMap 中使用它。代码如下:

      //传递给MyKey的name参数被用于equals()和hashCode()中
      MyKey key = new MyKey('Pankaj'); //assume hashCode=1234
      myHashMap.put(key, 'Value');
      // 以下的代码会改变key的hashCode()和equals()值
      key.setName('Amit'); //assume new hashCode=7890
      //下面会返回null,因为HashMap会尝试查找存储同样索引的key,而key已被改变了,匹配失败,返回null
      myHashMap.get(new MyKey('Pankaj'));
      
      
      • 那就是为何 String 和 Integer 被作为 HashMap 的 key 大量使用。

    ? HashMap 的长度为什么是 2 的幂次方?

    为了能让 HashMap 存取高效,尽量较少碰撞,也就是要尽量把数据分配均匀,每个链表/红黑树长度大致相同。这个实现就是把数据存到哪个链表/红黑树中的算法。

    这个算法应该如何设计呢?我们首先可能会想到采用 % 取余的操作来实现。但是,重点来了:

    • 取余(%)操作中如果除数是 2 的幂次则等价于与其除数减一的与(&)操作(也就是说 hash % length == hash & (length - 1) 的前提是 length 是 2 的 n 次方;)。
    • 并且,采用二进制位操作 &,相对于 % 能够提高运算效率,

    这就解释了 HashMap 的长度为什么是 2 的幂次方。

    HashSet 的工作原理是什么?

    HashSet 是构建在 HashMap 之上的 Set hashing 实现类。让我们直接撸下源码,代码如下:

    // HashSet.java
    
    private transient HashMap<E,Object> map;
    
    private static final Object PRESENT = new Object();
    
    
    • map 属性,当我们创建一个 HashMap 对象时,其内部也会创建一个 map 对象。后续 HashSet 所有的操作,实际都是基于这个 map 之上的封装。

    • PRESENT 静态属性,所有 map 中 KEY 对应的值,都是它,避免重复创建。

    • OK ,再来看一眼 add 方法,代码如下:

      // HashSet.java
      
      public boolean add(E e) {
          return map.put(e, PRESENT) == null;
      }
      
      
      • 是不是一目了然。

    ? HashSet 如何检查重复?

    艿艿:正如我们上面看到 HashSet 的实现原理,我们自然可以推导出,HashMap 也是如何检查重复滴。

    如下摘取自 《Head First Java》 第二版:

    当你把对象加入 HashSet 时,HashSet会先计算对象的hashcode值来判断对象加入的位置,同时也会与其他加入的对象的hashcode值作比较。

    • 如果没有相符的 hashcode ,HashSet会假设对象没有重复出现。
    • 但是如果发现有相同 hashcode 值的对象,这时会调用 equals 方法来检查 hashcode 相等的对象是否真的相同。
      • 如果两者相同,HashSet 就不会让加入操作成功。
      • 如果两者不同,HashSet 就会让加入操作成功

    【详细可以查看java基础系列】

    展开全文
  • Java模拟汉诺塔移位、阶乘、斐波那契数列操作 1.汉诺塔移位操作 package hanoi; import java.util.Scanner; /** * 汉诺塔 * @author wsz * @date 2018年1月20日 */ public class HanoiDemo { static int ...

    Java模拟汉诺塔移位、阶乘、斐波那契数列操作

    1.汉诺塔移位操作

    package hanoi;
    
    import java.util.Scanner;
    /**
     * 汉诺塔
     * @author wsz
     * @date 2018年1月20日
     */
    public class HanoiDemo {
    
    	static int count = 0;
    	/**
    	 * n=1 a->c
    	 * n=2 
    	 * 		|递归(1,a,c,b):a->b(1次) 结束递归 
    	 *  	|a->c(2次)  
    	 *  	|递归(1,b,a,c):b->c(3次) 结束递归 
    	 *  	|结束
    	 * n=3 
    	 * 		|递归(2,a,c,b) 与n=2一致(共三次)
    	 * 		|a->c(4次)
    	 * 		|递归(2,b,a,c) 与n=2一致(共三次)
    	 * n=*  总次数n^2-1
    	 * @param n 盘子数量
    	 * @param a 源位座
    	 * @param b 辅助座
    	 * @param c 目标座
    	 */
    	static void hanoi(int n, char a, char b, char c) {
    		if(n == 1) {
    			System.out.println("第"+(++count)+"次从"+a+"到"+c);
    		}else {
    			hanoi(n-1,a,c,b);  //将a上的n-1个移到b
    			System.out.println("第"+(++count)+"次从"+a+"到"+c); //将a上的最后一个移到c
    			hanoi(n-1,b,a,c);	//将b上的n-1个移到c
    		}
    	}
    	
    	public static void main(String[] args) {
    		Scanner input = new Scanner(System.in);
    		System.out.println("输入数量:");
    		int num = input.nextInt();
    		hanoi(num,'a','b','c');
    		input.close();
    	}
    
    }
    

    2.阶乘

    package hanoi;
    
    import java.util.Scanner;
    
    /**
     * 递归阶乘 n! = n*(n-1)*(n-2)*(n-3)*...*2*1
     * @author wsz
     * @date 2018年1月20日
     */
    public class Factorial {
    
    	/**
    	 * 递归解决
    	 * @param n
    	 * @return
    	 */
    	static long fact(long n) {
    		if(n <= 1) {
    			print(n);
    			return 1;
    		}else {
    			print(n);
    			return n*fact(n-1);
    		}
    	}
    	
    	/**
    	 * 循环解决
    	 * @param n
    	 */
    	static long fact2(long n) {
    		int i;
    		long res =1L;
    		for(i = 1; i <= n; i++) {
    			res *= i;
    		}
    		return res;
    	}
    	
    	static void print(long n) {
    		if(n <= 1)
    			System.out.print(n);
    		else
    			System.out.print(n+"*");
    	}
    	
    	public static void main(String[] args) {
    		System.out.println("输入需要阶乘的数字:");
    		Scanner input = new Scanner(System.in);
    		int num = input.nextInt();
    		long fact = fact(num);
    		
    		System.out.println("");
    		System.out.println(fact);
    		System.out.println(fact2(num));
    		input.close();
    	}
    
    }
    

    3.斐波那契数列

    package hanoi;
    
    import java.util.Scanner;
    
    /**
     * 菲波那切数列:1+1+2+3+5+8+13+...
     * @author wsz
     * @date 2018年1月20日
     */
    public class Fibonacci {
    
    	/**
    	 * 获取某一下标位置的值
    	 * @param n
    	 * @return
    	 */
    	static long fib(long n) {
    		if(n <= 2 ) {
    			return 1;
    		}else {
    			return fib(n-1)+fib(n-2); //返回之前2个数字的求和
    		}
    	}
    	
    	/**
    	 * 进行求和
    	 * @param n
    	 * @return
    	 */
    	static long fib2(long n) {
    		int i;
    		long res =0L;
    		String str = "";
    		for(i = 1; i <= n; i++) {
    			long fib = fib(i);
    			res += fib;
    			str += String.valueOf(fib)+"+";
    		}
    		System.out.println(str.substring(0, str.length()-1)+"="+res);
    		return res;
    	}
    	
    	public static void main(String[] args) {
    		System.out.println("获取斐波那契数的下标位置:");
    		Scanner input = new Scanner(System.in);
    		int num = input.nextInt();
    		long fib = fib(num);	//获取下标位置的值
    		System.out.println(fib);
    		System.out.println(fib2(num)); //进行求和输出
    		input.close();
    	}
    
    }
    




    展开全文
  • 数据结构和算法(Java)

    千人学习 2018-04-13 16:45:09
    如果说各种编程语言是程序员的招式,那么数据结构和算法就相当于程序员的内功。 想写出精炼、优秀的代码,不通过不断的锤炼,是很难做到的。 开这个系列的目的是为了自我不断积累。不积跬步无以至千里嘛。
  • 2021年 第12届 蓝桥杯 第4次模拟赛真题详解及小结【Java版】

    1. 2013年 第04届 蓝桥杯 Java B组 省赛真题详解及小结
    2. 2014年 第05届 蓝桥杯 Java B组 省赛真题详解及小结
    3. 2015年 第06届 蓝桥杯 Java B组 省赛真题详解及小结
    4. 2016年 第07届 蓝桥杯 Java B组 省赛真题详解及小结
    5. 2017年 第08届 蓝桥杯 Java B组 省赛真题详解及小结
    6. 2018年 第09届 蓝桥杯 Java B组 省赛真题详解及小结
    7. 2019年 第10届 蓝桥杯 Java B组 省赛真题详解及小结
    8. 2020年 第11届 蓝桥杯 第1次模拟赛真题详解及小结【Java版】(校内模拟)// 官方讲解视频
    9. 2020年 第11届 蓝桥杯 第2次模拟赛真题详解及小结【Java版】// 官方讲解视频
    10. 2020年 第11届 蓝桥杯 C/C++ B组 省赛真题详解及小结【第1场省赛 2020.07.05】【Java版】
    11. 2020年 第11届 蓝桥杯 Java B组 省赛真题详解及小结【第1场省赛 2020.07.05】
    12. 2020年 第11届 蓝桥杯 Java B组 省赛真题详解及小结【第2场省赛 2020.10.17】
    13. 2020年 第11届 蓝桥杯 Java C组 省赛真题详解及小结【第1场省赛 2020.07.05】
    14. 2021年 第12届 蓝桥杯 第1次模拟赛真题详解及小结【Java版】
    15. 2021年 第12届 蓝桥杯 第2次模拟赛真题详解及小结【Java版】
    16. 2021年 第12届 蓝桥杯 第3次模拟赛真题详解及小结【Java版】
    17. 2021年 第12届 蓝桥杯 第4次模拟赛真题详解及小结【Java版】
    18. 2021年 第12届 蓝桥杯 Java B组 省赛真题详解及小结

    1. 2015年 第06届 蓝桥杯 Java B组 决赛真题详解及小结
    2. 2016年 第07届 蓝桥杯 Java B组 决赛真题详解及小结
    3. 2017年 第08届 蓝桥杯 Java B组 决赛真题详解及小结
    4. 2018年 第09届 蓝桥杯 Java B组 决赛真题详解及小结
    5. 2019年 第10届 蓝桥杯 Java B组 决赛真题详解及小结
    6. 2020年 第11届 蓝桥杯 Java B组 决赛真题详解及小结

    目录

    模拟赛网页截图

    一、试题A——答案:P

    解法一:ASCII码值对应的字符

    二、试题B——答案:16

    解法一:质数判断

    三、试题C——答案:4042

    解法一:二叉树节点的求解

    四、试题D——答案:25

    解法一:找规律

    解法二:BigInteger数组遍历

    五、试题E——答案:8

    解法一

    六、试题F

    解法一

    七、试题G

    解法一

    八、试题H

    解法一

    九、试题I

    解法一

    十、试题J

    解法一

    小结


    仅供参考,欢迎指正!以下均为个人想法和解题思路,如有错误或不足,欢迎指正。

    模拟赛网页截图

     

    一、试题A——答案:P

    问题描述

      ASCII 码将每个字符对应到一个数值(编码),用于信息的表示和传输。在 ASCII 码中,英文字母是按从小到大的顺序依次编码的,例如:字母 A 编码是 65, 字母 B 编码是 66,字母 C 编码是 67,请编码为 80 的是哪个字母?

    答案提交

      这是一道结果填空的题,你只需要算出结果后提交即可。本题的结果为一个英文字母,在提交答案时只填写这个英文字母,填写多余的内容将无法得分。

    解法一:ASCII码值对应的字符

    【答案】:P

    【解析】:递推,直接 解出 ASCII码值 对应的字符 即可!

    package simulationMatch_12_2021_4;
    
    public class _01A {
    	public static void main(String[] args) {
    		System.out.println('A' - 0); // 65
    		System.out.println('B' - 0); // 66
    		System.out.println('C' - 0); // 67
    		System.out.println('P' - 0); // 80
    		System.out.println('Q' - 0); // 81
    		System.out.println('Q' + 0); // 81
    		System.out.println('Z' - 0); // 90
    	}
    }

    二、试题B——答案:16

    问题描述

      请问在 1900 到 2020 中,有多少个质数。

    答案提交

      这是一道结果填空的题,你只需要算出结果后提交即可。本题的结果为一个整数,在提交答案时只填写这个整数,填写多余的内容将无法得分。

    解法一:质数判断

    【答案】:16

    【解析】:for循环遍历数据[1900, 2020],根据“质数的定义”进行求解,枚举计数。

    package simulationMatch_12_2021_4;
    
    public class _02B {
    	public static void main(String[] args) {
    		int answer = 0;
    		for (int i = 1900; i <= 2020; i++) {
    			if (testIsPrime(i)) {
    				answer++;
    			}
    		}
    		System.out.println(answer);
    	}
    
    	public static boolean testIsPrime(int n) {
    		if (n <= 3) {
    			return n > 1;
    		}
    		for (int i = 2; i < n; i++) {
    			if (n % i == 0)
    				return false;
    		}
    		return true;
    	}
    
    	/* 优化后 */
    	public static boolean testIsPrime2(int n) {
    		if (n <= 3) {
    			return n > 1;
    		}
    		for (int i = 2; i <= Math.sqrt(n); i++) {
    			if (n % i == 0)
    				return false;
    		}
    		return true;
    	}
    }

    三、试题C——答案:4042

    问题描述

      有一棵二叉树,有2021个叶结点。
      请问。这棵树至少有多少个结点?

    答案提交

      这是一道结果填空的题,你只需要算出结果后提交即可。本题的结果为一个整数,在提交答案时只填写这个整数,填写多余的内容将无法得分。

    解法一:二叉树节点的求解

    【答案】:4042

    【解析】:

    • 非空二叉树上的叶子结点数(度为0的节点,称为“叶子结点”)等于度为2的结点数加1,即 n_{0} = n_{2} + 1 。
    • 设度为0、1、2的结点个数分别为n_{0}n_{1}n_{2},二叉树的节点总数 n = n_{0} + n_{1} + n_{2} 。

    二叉树的总结点个数为:n = n_{0} + n_{1} + n_{2} = n_{0} + n_{1} + \left ( n_{0} - 1 \right )

    度为2的结点数 n2 = n0 - 1 = 2021 - 1 = 2020

    叶子节点的数目为2021个(奇数),所以肯定存在度为1的节点,即 n1 = 1 。

    所以,二叉树的总结点个数至少为:n = n_{0} + n_{1} + n_{2} = n_{0} + n_{1} + \left ( n_{0} - 1 \right ) = 2021 + 1 + 2020 = 4042

    对于这棵二叉树,最少的节点数目为只有度数为0和度数为2的节点,但是因为叶子节点的数目为2021个(奇数个),所以肯定存在度为1的节点,那么,最终二叉树总的节点数目为 n = n0 + n1 + n2 = 2021 + 1 + 2020 = 4042个节点。

    四、试题D——答案:25

    问题描述

      Fibonacci序列按照如下公式定义:
      F[1] = 1
      F[2] = 1
      F[i] = F[i-1] + F[i-2] (i>2)
      前几个 Fibonacci 数为 1, 1, 2, 3, 5, 8, 13, 21。
      请问,前100个 Fibonacci 数中,有多少个数是 3 的倍数?

    答案提交

      这是一道结果填空的题,你只需要算出结果后提交即可。本题的结果为一个整数,在提交答案时只填写这个整数,填写多余的内容将无法得分。

    解法一:找规律

    原文链接:百度知道——在斐波那契数列的前100个数中有多少个数是三的倍数?

    多写几个找规律:1、1、2、3、5、8、13、21、34、55、89、144 ...
    会发现每4个数中,会出现一个3的倍数。所以,前100个数中,3的倍数有:100÷4=25个。

    解法二:BigInteger数组遍历

    【答案】:25

    【解析】:遍历Fibonacci序列——Fibonacci序列的第100项数据,会爆“int型数组、long型数组”,所以要使用BigInteger数组。

    package simulationMatch_12_2021_4;
    
    import java.util.Arrays;
    import java.math.BigInteger;
    
    public class _04D {
    
    	public static void main(String[] args) {
    //		test1();
    //		test2();
    		test3();
    	}
    
    	public static void test1() { //测试:fib[100]爆int数组
    		int fib[] = new int[105];
    		fib[0] = 0;
    		fib[1] = fib[2] = 1;
    		for (int i = 3; i <= 102; i++) {
    			fib[i] = fib[i - 1] + fib[i - 2];
    		}
    		int answer = 0;
    		for (int i = 1; i <= 100; i++) {
    			if (fib[i] % 3 == 0) {
    				answer++;
    				System.out.print(i + "、");
    			}
    		}
    		System.out.println("\n" + answer);
    		System.out.println(Arrays.toString(fib));
    	}
    
    	public static void test2() { //测试:fib[100]爆long数组
    		long fib[] = new long[102];
    		fib[0] = 0;
    		fib[1] = fib[2] = 1;
    		for (int i = 3; i < 102; i++) {
    			fib[i] = fib[i - 1] + fib[i - 2];
    			System.out.println(i + ":" + fib[i]);
    		}
    //		System.out.println(Arrays.toString(fib));
    		int answer = 0;
    		for (int i = 1; i <= 100; i++) {
    			if (fib[i] % 3 == 0) {
    				answer++;
    				System.out.print(i + "、");
    			}
    		}
    		System.out.println("\n" + answer);
    	}
    
    	public static void test3() {
    		BigInteger arr[] = new BigInteger[2025]; // int型与long型数据均会爆数组
    		arr[0] = BigInteger.ZERO;
    		arr[1] = arr[2] = BigInteger.ONE;
    		for (int i = 3; i <= 2020; i++) {
    			arr[i] = arr[i - 1].add(arr[i - 2]);
    		}
    		int answer = 0;
    		BigInteger three = new BigInteger("3");
    		for (int i = 1; i <= 100; i++) { // 输出斐波那契数组的元素值 验证
    			System.out.println(i + ": " + arr[i]);
    			if (arr[i].mod(three).equals(arr[0])) {
    				answer++;
    //				System.out.print(i + "、");
    			}
    		}
    		System.out.println("\n" + answer);
    	}
    
    }

    五、试题E——答案:8

    问题描述

      一个身份证号码有 18 位数字或字母组成。其中前17位必须是数字,最后一位可能是数字或字母X。
      身份证号码满足一定的校验规则。
      令身份证号从右到左依次标号为 1 到 18,其中标号为 i 的位的位权设置为 2^(i-1) mod 11 (2的i-1次方除以 11 的余数)。
      将每一位的数值乘以位权相加,得到的结果除以 11 的余数应当为 1。其中最后一位(标号为1)中如果出现字母 X,看成数字 10。
      例如,如果一个人的身份证号为 34052419800101001X,则:
      标号为 1 的位,位权 1,数值 X,即 10,相乘得 10。
      标号为 2 的位,位权 2,数值 1,相乘得 2。
      标号为 3 的位,位权 4,数值 0,相乘得 0。
      标号为 4 的位,位权 8,数值 0,相乘得 0。
      标号为 5 的位,位权 5,数值 1,相乘得 5。
      标号为 6 的位,位权 10,数值 0,相乘得 0。
      标号为 7 的位,位权 9,数值 1,相乘得 9。
      标号为 8 的位,位权 7,数值 0,相乘得 0。
      标号为 9 的位,位权 3,数值 0,相乘得 0。
      标号为 10 的位,位权 6,数值 8,相乘得 48。
      标号为 11 的位,位权 1,数值 9,相乘得 9。
      标号为 12 的位,位权 2,数值 1,相乘得 2。
      标号为 13 的位,位权 4,数值 4,相乘得 16。
      标号为 14 的位,位权 8,数值 2,相乘得 16。
      标号为 15 的位,位权 5,数值 5,相乘得 25。
      标号为 16 的位,位权 10,数值 0,相乘得 0。
      标号为 17 的位,位权 9,数值 4,相乘得 36。
      标号为 18 的位,位权 7,数值 3,相乘得 21。
      将乘积相加,得 199,除以 11 的余数正好为 1。
      小明的身份证号前 17 位为 11010120210221999,请问小明身份证的最后一位是多少?

    答案提交

      这是一道结果填空的题,你只需要算出结果后提交即可。本题的结果为一个字符,可能是数字或者大写字母X,在提交答案时只填写这个字符,填写多余的内容将无法得分。

    解法一

    【答案】:8

    【解析】:1 ≤ i ≤ 18

     

    package simulationMatch_12_2021_4;
    
    public class _05E {
    
    	public static void main(String[] args) {
    //		System.out.println(Integer.MAX_VALUE); // 2147483647
    //		System.out.println(Long.MAX_VALUE); // 9223372036854775807 19位
    //		System.out.println('0' - '0');
    //		System.out.println('1' - '0');
    
    		calculate("34052419800101001X"); // 199 1
    
    		// 将每一位的数值乘以位权后相加,得到的结果除以 11 的余数应当为 1。
    //		calculate("110101202102219990");
    //		calculate("110101202102219991");
    //		calculate("110101202102219992");
    //		calculate("110101202102219993");
    //		calculate("110101202102219994");
    //		calculate("110101202102219995");
    //		calculate("110101202102219996");
    //		calculate("110101202102219997");
    		calculate("110101202102219998"); // 221 1【答案:8】
    //		calculate("110101202102219999");
    //		calculate("11010120210221999X");
    	}
    
    	public static void calculate(String num) {
    		StringBuilder sb = new StringBuilder(num);
    		sb = sb.reverse();
    		char[] charArray = sb.toString().toCharArray(); // 先转String再转字符数组
    		int sum = 0;
    		for (int i = 0; i < 18; i++) {
    			if (i == 0) { // 计算首位
    				if (charArray[0] == 'X') {
    					sum += 10;
    				} else {
    					int place = (int) Math.pow(2, i) % 11;// 标号为 i 的位的位权设置为 2^(i-1) mod 11
    					System.out.println(i + "---" + place + "---" + charArray[i] + "---" + ((int) (charArray[i] - '0') * place));
    					sum += (int) (charArray[i] - '0') * place; // 将每一位的数值乘以位权后相加
    				}
    			} else { // 计算非首位
    				int place = (int) Math.pow(2, i) % 11;// 标号为 i 的位的位权设置为 2^(i-1) mod 11
    				System.out.println(i + "---" + place + "---" + charArray[i] + "---" + ((int) (charArray[i] - '0') * place));
    				sum += (int) (charArray[i] - '0') * place; // 将每一位的数值乘以位权后相加
    			}
    //			System.out.println(sum + "\n\n");
    		}
    		System.out.println(sum);
    		System.out.println(sum % 11);
    	}
    
    }

    六、试题F

    问题描述

    小Hi的公司经常举办回馈社会的爱心活动。这次小Hi作为志愿者带领社区的孩子们参观了青少年天文馆。他发现孩子们对于摩尔斯电码非常感兴趣。

    摩尔斯电码由两种基本的信号组成:短信号"滴"(用字符'.'表示)以及长信号"嗒"(用字符'-'表示)。下图是数字0-9的摩尔斯电码表示,每个数字都由5个字符组成:

    .---- ..--- ...-- ....- ..... -.... --... ---.. ----. -----
    1     2     3     4     5     6     7     8     9     0

    为了让孩子们开心,小Hi决定把每位孩子的生日日期转化为摩尔斯码赠送给他们。例如日期20210101对应的摩尔斯电码是:

    ..--- ----- ..--- .---- ----- .---- ----- .----

    你能写一个程序帮助小Hi吗?

    输入格式

    第一行是一个整数N,代表参加活动的孩子的人数。(1 <= N <= 100)

    以下N行每行一个由0-9组成的字符串,代表一个生日日期。(日期格式:yyyymmdd,日期范围: 20000101至20210101)

    输出格式

    对于每个生日日期,输出一行表示转化后的摩尔斯码,数字之间用一个空格隔开。

    样例输入

    2  
    20161011  
    20000101

    样例输出

    ..--- ----- .---- -.... .---- ----- .---- .----
    ..--- ----- ----- ----- ----- .---- ----- .----

    解法一

    【解析】:最好将‘0’对应的字符串,设置在字符串数组的开头位置!

    package simulationMatch_12_2021_4;
    
    import java.util.Scanner;
    
    public class _06F {
    	public static void main(String[] args) {
    		Scanner sc = new Scanner(System.in);
    		int N = sc.nextInt(); // 1 <= N <= 100
    		String str[] = { "-----", ".----", "..---", "...--", "....-", ".....", "-....", "--...", "---..", "----." }; // 0对应的字符串在开头
    		for (int i = 1; i <= N; i++) { // 由0-9组成的字符串,日期范围:20000101至20210101
    			String s = sc.next();
    			char strArray[] = s.toCharArray();
    			for (int j = 0; j < 8; j++) { // [0, 8] 遍历字符数组,取出每一个字符
    				int index = (int) (strArray[j] - '0'); // 字符串数组的下标
    				if (j == 7) { // 若是输出最后的字符串,则末尾不加空格
    					System.out.print(str[index]);
    				} else {
    					System.out.print(str[index] + " ");
    				}
    			}
    			System.out.println();
    		}
    	}
    }

    七、试题G

    问题描述

      小蓝在商店买文具。
      一支钢笔 x 元,小蓝买了 a 支。
      一个笔记本 y 元,小蓝买了 b 本。
      请问,小蓝一共需要支付多少钱?

    输入格式

      输入四行。
      第一行包含一个整数 x。
      第二行包含一个整数 a。
      第三行包含一个整数 y。
      第四行包含一个整数 b。

    输出格式

      输出一个整数,表示答案。

    样例输入

    5
    2
    1
    6

    样例输出

    16

    样例输入

    2
    0
    2
    1

    样例输出

    2

    数据规模和约定

      对于所有评测用例,0 <= x, a, y, b <= 100。

    解法一

    package simulationMatch_12_2021_4;
    
    import java.util.Scanner;
    
    public class _07G {
    
    	public static void main(String[] args) {
    		Scanner sc = new Scanner(System.in);
    		int x = sc.nextInt();
    		int a = sc.nextInt();
    		int y = sc.nextInt();
    		int b = sc.nextInt();
    		System.out.println(x * a + y * b);
    	}
    
    }

    八、试题H

    问题描述

      给定一个序列 (a_1, a_2, ..., a_n), 定义序列中的一个递增三元组是指三个下标 i, j, k 对应的三个元素 a_i, a_j, a_k,这三个元素满足 a_i < a_j < a_k。
      例如序列 (1, 1, 4, 3, 2, 4) 有以下 4 个递增三元组:
      1. 下标 1, 4, 6 对应的 1, 3, 4;
      2. 下标 1, 5, 6 对应的 1, 2, 4;
      3. 下标 2, 4, 6 对应的 1, 3, 4;
      4. 下标 2, 5, 6 对应的 1, 2, 4。
      注意,可能有下标不同,但对应数值相同的三元组,他们应当算成不同的三元组。
      给定序列,请问序列中一共有多少个不同的递增三元组。

    输入格式

      输入第一行包含一个整数 n,表示序列的长度。
      第二行包含 n 个整数 a_1, a_2, ..., a_n,表示给定的序列。

    输出格式

      输出一行,包含一个整数,表示序列中的递增三元组数量。请注意答案可能很大,可能超过 32 位二进制整数的范围,建议使用 64 位二进制整数。

    样例输入

    6
    1 1 4 3 2 4

    样例输出

    4

    数据规模和约定

      对于 30% 的评测用例,1 <= n <= 20, 0 <= a_i <= 10。
      对于 50% 的评测用例,1 <= n <= 1000, 0 <= a_i <= 100。
      对于 80% 的评测用例,1 <= n <= 10000, 0 <= a_i <= 100。
      对于所有评测用例,1 <= n <= 100000, 0 <= a_i <= 100。

    解法一

    【解析】:三个元素满足 a_i < a_j < a_k

    for (int i = 0; i < n; i++) {
                for (int j = i + 1; j < n; j++) {
                    for (int k = j + 1; k < n; k++) {

    package simulationMatch_12_2021_4;
    
    import java.util.Arrays;
    import java.util.Scanner;
    
    public class _08H {
    
    	public static void main(String[] args) {
    		Scanner sc = new Scanner(System.in);
    		int n = sc.nextInt();
    		int array[] = new int[n + 1];
    		for (int i = 0; i < n; i++) {
    			array[i] = sc.nextInt();
    		}
    //		System.out.println(Arrays.toString(array));
    		Long answer = 0L; // 答案可能很大,建议使用64位二进制整数
    		for (int i = 0; i < n; i++) {
    			for (int j = i + 1; j < n; j++) {
    				for (int k = j + 1; k < n; k++) {
    					if (array[i] < array[j] && array[j] < array[k]) {
    						answer++;
    					}
    				}
    			}
    		}
    		System.out.println(answer);
    	}
    
    }

    九、试题I

    问题描述

      小Hi正在研究一种特殊的栈。这种栈的元素既可以从栈顶出栈,也可以从栈底出栈。(进栈还是只能从栈顶进栈)
      已知入栈的序列是1~N的一个排列,请你判断出栈序列能否是1, 2, 3, ... N?

    输入格式

      输入包含多组数据。
      输入第一行包含一个整数T,代表测试数据的组数。
      以下每组数据占据2行。
      第一行包含一个整数N。
      第二行包含N个整数,整数中由空格隔开。表示入栈序列。

    输出格式

      对于每组数据输出YES或者NO,代表出栈序列能否是1, 2, 3, ... N。

    样例输入

    2
    5
    2 4 1 3 5
    5
    4 3 1 5 2

    样例输出

    YES
    NO

    数据规模和约定

      对于30%的评测用例,1 <= N <= 10
      对于80%的评测用例,1 <= N <= 10000
      对于所有评测用例,1 <= N <= 100000, 1 <= T <= 10。

    解法一

    求巨佬支招!

    十、试题J

    问题描述

      给定两个序列 A=(a_1, a_2, ..., a_n) 和 B=(b_1, b_2, ..., b_m), 它们的一个公共子序列是指从两个序列中分别取出相同个数的元素,按照原来的顺序排列后,对应位置的数值相等。
      例如,对于序列 A=(3, 2, 7, 6, 7) 和 B=(2, 3, 5, 7),可以在序列 A 中取出第 2, 3 个元素,在序列 B 中取出第 1, 4 个元素,值都是 2, 7,因此 2, 7 是一个公共子序列,在 A 中取第 2, 3 个元素和在 B 中取 1, 4 个元素是这个公共子序列的一种取法。
      在这两个序列中,有 4 中取法可以取出长度为 2 的公共子序列,例如
      1. 在 A 中取第 1, 3 个元素,在 B 中取 2, 4 个元素;
      1. 在 A 中取第 1, 5 个元素,在 B 中取 2, 4 个元素;
      1. 在 A 中取第 2, 3 个元素,在 B 中取 1, 4 个元素;
      1. 在 A 中取第 2, 5 个元素,在 B 中取 1, 4 个元素。
      给定两个序列,请问有多少种取法可以取出长度为 k 的公共子序列。

    输入格式

      输入第一行包含三个整数 n, m, k,分别表示序列 A 的长度、序列 B 的长度和公共子序列的长度。
      第二行包含 n 个整数 a_1, a_2, ..., a_n,表示给定的 A 序列。
      第三行包含 m 个整数 b_1, b_2, ..., b_m,表示给定的 B 序列。

    输出格式

      输出一行,包含一个整数,表示长度为 k 的公共子序列的数量,答案可能很大,请输出答案除以 1000007 的余数。

    样例输入

    5 4 2
    3 2 7 6 7
    2 3 5 7

    样例输出

    4

    数据规模和约定

      对于 30% 的评测用例,1 <= n, m <= 20。
      对于 50% 的评测用例,1 <= n, m <= 100。
      对于所有评测用例,1 <= n, m <= 1000, 1 <= k <= 10, 0 <= a_i <= 100。

    解法一

    求巨佬支招!

    小结

    手写计算的题目,可以“编程+计算”进行求解验证。
    蓝桥杯比赛时,时间紧迫,在保证正确率的情况下,写快一些,然后多检查几遍。

    蓝桥杯 斐波那契数列前100项,BigInteger数组模板

    展开全文
  • import java.math.BigDecimal; import java.math.BigInteger; import java.util.ArrayList; import java.util.Date; import java.util.List; public class asd { public static void main(String[] args) { ...
    import java.math.BigDecimal;
    import java.math.BigInteger;
    import java.util.ArrayList;
    import java.util.Date;
    import java.util.List;
    
    public class asd {
    
        public static void main(String[] args) {
            Long t1=new Date().getTime();
            BigDecimal b1 = new BigDecimal(1);//初次参数分母
            BigDecimal b2 = new BigDecimal(1);//不变的分子
            List<BigDecimal> BD=new ArrayList<BigDecimal>();
            BD.add(b1);
            for(int i=0;i<10000;i++){//多次执行,使结果更精确
                //将 (1+1/1) 当作一个对象存到一个集合,每次循环都执行1+(1/上次的对象),然后将这个结果转成新的对象放到集合中
                BD.add(b2.divide(((BD.get(BD.size()-1)).divide(b2)).add(b2),110,BigDecimal.ROUND_DOWN));
            }
            System.out.println((BD.get(BD.size()-1)).setScale(100,BigDecimal.ROUND_DOWN));//设置最后的精确小数点的位数100位
            Long t2=new Date().getTime();
            System.out.println("方法一总用时:"+(t2-t1));
            System.out.println();
    
    
    
    
    
    
            Long ts1=new Date().getTime();
            BigDecimal cZ1 = new BigDecimal(1);//初次参数分子
            BigDecimal cM2 = new BigDecimal(2);//初次参数分母
            List<BigDecimal> BDZ=new ArrayList<BigDecimal>();//分子序列
            List<BigDecimal> BDM=new ArrayList<BigDecimal>();//分母序列
            BDZ.add(cZ1);
            BDM.add(cM2);
            for(int i=0;i<10000;i++){
                BigDecimal upCZ1,upCM1;//历史次序
                if(BDZ.size()==1){
                    upCZ1=new BigDecimal(1);
                    upCM1=new BigDecimal(1);
                }else{
                    upCZ1=BDZ.get(BDZ.size()-2);
                    upCM1=BDM.get(BDM.size()-2);
                }
                BDZ.add(upCZ1.add(BDZ.get(BDZ.size()-1)));
                BDM.add(upCM1.add(BDM.get(BDM.size()-1)));
            }
            System.out.println((BDZ.get(BDZ.size()-1)).divide((BDM.get(BDM.size()-1)),100,BigDecimal.ROUND_DOWN));
            Long ts2=new Date().getTime();
            System.out.println("方法二用时:"+(ts2-ts1));
            System.out.println();
    
    
    
    
    
    
    
            Long t3=new Date().getTime();
            BigInteger firstNum = BigInteger.ONE;//1
            BigInteger secNum = BigInteger.ONE;
            BigInteger res = BigInteger.ZERO;//0
            BigInteger TEN = BigInteger.TEN;//10
            //BigInteger的斐波那契数列
            for (int i = 0; i < 10000; i++) {
                if (i == 0 || i == 1) {
                    res = BigInteger.ONE;
                }
                res = secNum.add(firstNum); //两个BigInteger相加
                firstNum = secNum;
                secNum = res;
            }
            System.out.print("0.");
            //for循环实现了模拟手算除法
            for (int i = 0; i < 101; i++) {
                //选择斐波那契里两个连续的数,小的做被除数,大的做除数
                //每一位是两者的商值
                BigInteger ans = firstNum.divide(secNum);
                //除数不变,被除数=余数*10
                firstNum = (firstNum.mod(secNum)).multiply(TEN);
                if (i!=0) {  //只输出后面的100位小数点
                    System.out.print(ans);
                }
            }
            System.out.println();
            Long t4=new Date().getTime();
            System.out.println("方法三总用时:"+(t4-t3));
        }
    }
    
    结果
    0.6180339887498948482045868343656381177203091798057628621354486227052604628189024497072072041893911374
    方法一总用时:90
    
    0.6180339887498948482045868343656381177203091798057628621354486227052604628189024497072072041893911374
    方法二用时:18
    
    0.6180339887498948482045868343656381177203091798057628621354486227052604628189024497072072041893911374
    方法三总用时:14
    
    展开全文
  • public static int Fibonacci(int num){ if (num < 2){ return num; } return Fibonacci(num - 1) + Fibonacci(num - 2); } public static int FibonacciStack(int num){ Stack<Int
  • 常见的java调用python脚本方式 1.通过Jython.jar提供的类库实现2.通过Runtime.getRuntime()开启进程来执行脚本文件 1.Jython Jpython使用时,版本很重要!大多数坑来源于此。这句话不听的人还得走点弯路 运行...
  • Fibonacci数列的第n项 (模拟加法)

    千次阅读 2018-08-12 11:09:31
    7-45求Fibonacci数列的第n项(30分) 求Fibonacci数列的第n项f[n]. f[0]=1; f[1]=1 ; f[n]=f[n-1]+f[n-2]; 输入格式: 输入一个不超过10000的正整数n。 输出格式: 输出Fibonacci数列的第n项的值。 输入样例: ...
  • 2021年 第12届 蓝桥杯 第3次模拟赛真题详解及小结【Java版】
  • //P } } 三 问题描述 Fibonacci序列按照如下公式定义: F[1] = 1 F[2] = 1 F[i] = F[i-1] + F[i-2] (i>2) 前几个 Fibonacci 数为 1, 1, 2, 3, 5, 8, 13, 21。 请问,前100个 Fibonacci 数中,有多少个数是 3 的倍数...
  • 今天争取每天更新一篇剑指offer的算法题,算是做笔记,也算是督促自己学习,今天先做一个最简单的斐波那契数列。 斐波那契题目大家都很熟悉了,最基本的方法是用递归。但是递归意味着要消耗...一开始,我们用num1模拟
  • 当n=73时,f(n)=f(n-1)+f(n-2)-2 当n>73时,f(n)=f(n-1)+f(n-2)-f(n-72) 具体的数学推导和讨论过程不再赘述,为了从数值上验证通项公式的正确性,我编写了两个程序,通过不同的推算方式来模拟手工推算过程,这是本文...
  • JAVA小白编程题练习 可能有很多刚入门的小白不知道自己如何能快速提升编程技巧与熟练度 其实大佬进阶之路只有一个~ 那就是疯狂码代码!!!实践出真知!!! 所以为了大家能够想练习的时候有素材,泡泡给大家整理了一些练习...
  • java 递归 堆栈 在本文中,摘自《 Java中的函数编程 》一书,我解释了如何使用递归,同时避免了StackOverflow异常的风险。 Corecursion正在使用第一步的输出作为下一步的输入来构成计算步骤。 递归是相同的操作,...
  • Java开发技术大全(500个源代码).

    热门讨论 2012-12-02 19:55:48
    Fibonacci.java 求Fiblnacci数列 GcdAndGcm.java 求最大公约数和最小公倍数 errorInit.java 演示变量初始化错误的程序 integerExample.java 演示各种整型变量的使用 isPrime.java 判断素数 leapYearByIf.java ...
  • Recently I will deliver a ...As Java Spring is already widely used in all other Java development teams in my site, some ABAPers are not well aware of its idea and implementation under the hood. In o
  • within SAP and there is a set of concept Covariance and Contravariance, which has only built-in support by a subset of programming language like Java. For those ABAPers who don’t have c
  • 深入Java虚拟机

    2014-06-28 23:53:10
    10.6 一个模拟:“Fibonacci Forever” 10.7 随书光盘 10.8 资源页 第11章 类型转换 11.1 转换操作码 11.2 一个模拟:“Conversion Diversion” 11.3 随书光盘 11.4 资源页 第12章 整数运算 12.1 ...
  • 斐波那契数,通常用 F(n) 表示,形成的序列称为斐波那契数列。该数列由 0 和 1 开始,后面的每一项数字都是前面两项数字的和。也就是: F(0) = 0, F(1) = 1 F(N) = F(N - 1) + F(N - 2), 其中 N > 1. 给定 N,...

空空如也

空空如也

1 2 3 4 5 ... 20
收藏数 3,388
精华内容 1,355
关键字:

java模拟斐波那契

java 订阅