题目

在一个长度为n的数组里的所有数字都在 0 到 n-1 的范围内。 数组中某些数字是重复的，但不知道有几个数字是重复的。也不知道每个数字重复几次。请找出数组中第一个重复的数字。 例如，如果输入长度为7的数组{2 ,3, 1, 0, 2, 5, 3}，那么对应的输出是第一个重复的数字 2。

这个题目在牛客网是请找出数组中第一个重复的数字，书中是“请找出数组中任意一个重复的数字”。如果直接按照书中的代码，那就不能通过牛客网的全部测试用例，这就有点搞了。不过还是先讲一下解题思路吧。

先排序，再扫描

排序后的数组很容易可以找出重复数字，从头到尾扫描一遍，发现相邻两个数相等的情况即找到了重复数字。时间复杂度为 $O(nlogn)$

利用哈希表

从头到尾扫描一遍数组，如果哈希表中没有这个数字，就将它加入哈希表，如果该数字已存在，则找到了重复数字。这个方法可以用 $O(1)$ 的时间来判断哈希表是否包含当前扫描到的数字，整个算法的时间复杂度是 $O(n)$ ，但代价是需要一个 $O(n)$ 大小的哈希表。

利用数组下标

因为数组中所有数字都在0~n-1范围内，如果数组没有重复数字，那么数组排序后里面数字应该与它对应的下标相等。但因为数组中数字有重复，所以某个位置上的数字应该会出现多于一次。其实说的是，某个下标对应着的与下标相等的数字可能出现多次。原书中那句话是，“由于数组中有重复的数字，有些位置可能存在多个数字，同时有些位置可能没有数字。”，当时看到这句话有点懵，难道数组的一个位置还可以挤下两个数字？后来知道他所指的“位置”是指，下标值与数值相等的这种情况。说起位置，就有点想起 PositionalList …

清楚了上面的情况，那么怎么可以找出重复数字？书中也是一段文字描述，按照里边描述的确可以找出重复数字，但看起来有点不直观，所以画个流程图看看。

题目

书中原题目是：

题目：输入一棵二叉树和一个整数，打印出二叉树中节点值的和为输入整数的所有路径。从树的根节点开始往下一直到叶节点所经过的节点形成一条路径。二叉树节点的定义如下：

struct BinaryTreeNode
{
  int               m_nValue;
  BinaryTreeNode    m_pLeft;
  BinaryTreeNode    m_pRight;
}

不过牛客网上的题目，稍微有点不同：

输入一颗二叉树的根节点和一个整数，按字典序打印出二叉树中结点值的和为输入整数的所有路径。路径定义为从树的根结点开始往下一直到叶结点所经过的结点形成一条路径。

题目是要求返回 ArrayList<ArrayList<Integer>>，还有那个按字典序打印。

这道题主要是对树进行前序遍历，访问到某个节点时累加起来，直到叶子节点，判断路径节点值之和是否为要求的整数。思路相对来说比较简单和直接，但是需要注意实现采用的数据结构的细节。
首先，从一个具体例如入手分析，输入下图 1 中二叉树和整数 22

前段时间做了点小东西，随缘记录一下。
在家里日常生活用水是用水塔，通过水泵将水从水井抽到楼顶的水塔用的。通常这些水塔都会有自动液位控制的，一般是一个浮球，机械式的开关。但家里的水塔比较旧没有安装水位控制装置，所以我一直想在水塔添加这样的功能。因为不想用浮球式液位控制，主要是想趁机折腾一下，玩一下技术。最初有些不太实际的脑洞，例如，可不可以通过测量液位变化时水塔的电容反映水位变化；还有根据水压变化计算出液面高度…… 因为不想安装水压测量到水管里，而且还要设法与水泵开关联动，麻烦。大概五年前，上大二的时候，刚学单片机，就想着用 51 做一个东西去根据水塔液位变化自动控制水泵开关。

Spring 单例不是 Java 单例。本文讨论 Spring 的单例与单例模式的区别。

前言

单例是 Spring 当中 bean 的默认范围(Scope)。Spring 容器会为某个 bean 定义对象创建唯一的实例，很多时候我们会将这种设计跟《设计模式》(GoF) 书中定义的单例模式作比较。

1. 单例范围 vs 单例模式

Spring 当中的单例范围跟单例模式不是同一个东西。其中的两点差异如下：

• 单例模式确保某个类加载器的某个类只有一个实例
• 而 Spring 单例范围是每个容器的每个bean

又再开始读 Spring 源码，做一下笔记，方便自己回顾。

最基础的，关于 BeanFactory 接口，可以认为是容器的根基，其它功能更多的接口都是从这里扩展而来。

@Test
public void testSimpleLoad() {
    BeanFactory bf = new XmlBeanFactory(new ClassPathResource("spring.xml"));
    MyTestBean bean = (MyTestBean) bf.getBean("myTestBean");
    Assertions.assertEquals("testString", bean.getTestStr());
}

上面代码就是最基本的使用。

15.5 Exercises

Reinforcement

R-15.1 Julia just bought a new computer that uses 64-bit integers to address memory cells. Argue why Julia will never in her life be able to upgrade the main memory of her computer so that it is the maximum-size possible, assuming that you have to have distinct atoms to represent different bits.

R-15.2 Consider an initially empty memory cache consisting of four pages. How many page misses does the LRU algorithm incur on the following page request sequence: (2,3,4,1,2,5,1,3,5,4,1,2,3)?

R-15.3 Consider an initially empty memory cache consisting of four pages. How many page misses does the FIFO algorithm incur on the following page request sequence: (2,3,4,1,2,5,1,3,5,4,1,2,3)?

R-15.4 Consider an initially empty memory cache consisting of four pages. What is the maximum number of page misses that the random algorithm incurs on the following page request sequence: (2,3,4,1,2,5,1,3,5,4,1,2,3)? Show all of the random choices the algorithm made in this case.

R-15.5 Describe, in detail, algorithms for adding an item to, or deleting an item from, an $(a,b)$ tree.

R-15.6 Suppose T is a multiway tree in which each internal node has at least five and at most eight children. For what values of a and b is $T$ a valid $(a,b)$ tree?

R-15.7 For what values of d is the tree $T$ of the previous exercise an order-d B-tree?

R-15.8 Draw the result of inserting, into an initially empty order-7 B-tree, entries with keys (4,40,23,50,11,34,62,78,66,22,90,59,25,72,64,77,39,12), in this order.

1.10 Exercises

Reinforcement

R-1.1 Write a short Java method, inputAllBaseTypes, that inputs a different value of each base type from the standard input device and prints it back to the standard output device.

R-1.2 Suppose that we create an array A of GameEntry objects, which has an integer scores field, and we clone A and store the result in an array B. If we then immediately set A[4].scores equal to 550, what is the score value of the GameEntry object referenced by B[4]?

R-1.3 Write a short Java method, isMultiple, that takes two long values, n and m, and returns true if and only if n is a multiple of m, that is, $n = mi$ for some integer i.

R-1.4 Write a short Java method, isEven, that takes an int i and returns true if and only if i is even. Your method cannot use the multiplication, modulus, or division operators, however.

R-1.5 Write a short Java method that takes an integer n and returns the sum of all positive integers less than or equal to n.

R-1.6 Write a short Java method that takes an integer n and returns the sum of all the odd positive integers less than or equal to n.
R-1.7 Write a short Java method that takes an integer n and returns the sum of the squares of all positive integers less than or equal to n.

R-1.8 Write a short Java method that counts the number of vowel in a given character string.

R-1.9 Write a short Java method that uses a StringBuilder instance to remove all the punctuation from a string s storing a sentence, for example, transforming the string “Let’s try, Mike!” to “Lets try Mike”.

R-1.10 Write a Java class, Flower, that has three instance variables of type String, int, and float, which respectively represent the name of the flower, its number of petals, and price. Your class must include a constructor method that initializes each variable to an appropriate value, and your class should include methods for setting the value of each type, and getting the value of each type.

R-1.11 Modify the CreditCard class from Code Fragment 1.5 to include a method that updates the credit limit.

R-1.12 Modify the CreditCard class from Code Fragment 1.5 so that it ignores any request to process a negative payment amount.

R-1.13 Modify the declaration of the first for loop in the main method in Code Fragment 1.6 so that its charges will cause exactly one of the three credit cards to attempt to go over its credit limit. Which credit card is it?

群 OCA/OCP 考试交流QQ群 157563860
其实这篇文章起源于 Twitter 上以为委瑞内拉小哥问我关于 OCP 考试的问题，我只好写这个作为回应。但中英夹杂，如果是国内读者看起来可能有点难受，改天再更新整理一下。 注意，现在 1Z0-816 考试已经没有了，只有 1Z0-819 考试。 另外前段时间我录了个视频，放在B站小号这里，讲了一些关于考试的。

I started with OCA Java SE 8 Programmer I exam last year, it took me 12 days to prepare the OCA exam. It was relatively easy to pass the OCA exam, but it was much harder to pass the OCP 11 exam. It took me roughly 3 months to get fully prepared for the ultimate 1Z0-816, namely Java SE 11 Programmer II exam, for which response to the Oracle Certified Professional: Java SE 11 Developer certification. This is by far the most difficult Java certification exam from Oracle/Sun, not just because it covers topics such as modules, functional programming, concurrent programming, IO. But also it includes some new objectives, like Java Secure Coding Guideline. For those who plan on taking the Oracle Java Certification exam, I strongly recommend you take a look at the official exam objectives before you start your study plan. Buy a good book, I think Selikoff’s book is great, I use that book for my exam preparation. Study the book chapter by chapter, or by topic, or whatever you want. Be sure to do the exercises, it will help you to consolidate your knowledge. It is also helpful to use flashcards to aid the memorization process, for example, some core APIs or some syntax rules. Don’t go directly into the quiz without studying the materials thoroughly, that will be just a waste of time and energy. Because that’s very frustrating to see lots of errors. Take your time, start slowly, and gradually level up the difficulty. Below are some useful references.

真题1 某知名互联网下载服务提供商软件工程师笔试题

一、选择题
1. 访问修饰符作用范围由大到小是（ ）。

A.private-protected-default-public
B.public-protected-default-private
C.private-default-protected-public
D.public-default-protected-private

这题没什么好说，当然是选择 B 啦，初学的时候可能有点难记住，不过习惯了就记住了。后来越了解就更容易记住，根本不需要死记硬背。 default 关键字，表示访问权限的时候，其实新的规范（8以上？）改称为 ‘package private’ 可以理解为包内私有访问权限，所以限制程度就是仅次于私有。接着protected和public容易，因为public肯定是范围最宽（大）的。
关于类的访问修饰符的作用范围，Java语言规范的 8.1.1 节有：
The access modifier public pertains only to top level classes and member classes, not to local classes or anonymous classes.
The access modifier protected and private pertain only to member classes within a directly enclosing class declaration.

1. Given

class Booby {
}
class Dooby extends Booby {
}
class Tooby extends Dooby {
}

public class TestClass {
  Booby b = new Booby();
  Tooby t = new Tooby();
  public void do1(List<? super Dooby> dataList) {
    //1 INSERT CODE HERE
  }
  public void do2(List<? extends Dooby> dataList) {
    //2 INSERT CODE HERE
  }
}

and the following four statements:

1. b = dataList.get(0);
2. t = dataList.get(0);
3. dataList.add(b);
4. dataList.add(t);

What can be inserted in the above code?

• Statements 1 and 3 can inserted at //1 and Statements 2 and 4 can be inserted at //2.
• Statement 4 can inserted at //1 and Statement 1 can be inserted at //2.
• Statements 3 and 4 can inserted at //1 and Statements 1 and 2 can be inserted at //2.
• Statements 1 and 2 can inserted at //1 and Statements 3 and 4 can be inserted at //2.
• Statement 1 can inserted at //1 and Statement 4 can be inserted at //2.

Explanation

1. addData1(List<? super Dooby> dataList)
   This means that dataList is a List whose elements are of a class that is either Dooby or a super class of Dooby. We don’t know which super class of Dooby. Thus, if you try to add any object to dataList, it has to be a assignable to Dooby.
   Thus, dataList.add(b); will be invalid because b is not assignable to Dooby.
   Further, if you try to take some object out of dataList, that object will be of a class that is either Dooby or a Superclass of Dooby. Only way you can declare a variable that can be assigned the object retrieved from dataList is Object obj. Thus, t = dataList.get(0); and b = dataList.get(0); are both invalid.

2. addData2(List<? extends Dooby> dataList)
   This means that dataList is a List whose elements are of a class that is either Dooby or a subclass of Dooby. Since we don’t know which subclass of Dooby is the list composed of, there is no way you can add any object to this list.
   If you try to take some object out of dataList, that object will be of a class that is either Dooby or a subclass of Dooby and thus it can be assigned to a variable of class Dooby or its superclass.. Thus, t = dataList.get(0); is invalid.

泛型规则（JLS）
A type argument $T_1$ is said to contain another type argument $T_2$, written $T_2 <= T_1$, is the set of types denoted by $T_2$ is provably a subset of the set of types denoted by $T_1$ under the reflexive and transitive closure of the following rules(where $<:$ denotes subtyping($\S4.10$)):

• $?\space extends\space T<=\space ?\space extends \space S$ if $T <: S$
• $?\space extends \space T<=\space ?$
• $?\space super \space T<=\space ?\space super \space S$ if $T <: S$
• $?\space super \space T<=\space ?$
• $?\space super \space T<=\space ? \space extends \space Object$
• $ T<=\space T$
• $T <= \space ? \space extends \space T$
• $T <= \space ? \space super \space T$