## 剑指Offer 面试题 34

### 二叉树中和为某一值的路径  2020年12月3日

#### 题目

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


## Spring单例与单例模式

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

### 1. 单例范围 vs 单例模式

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

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

## Spring001

@Test
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?

## 回顾OCP 1Z0-816认证考试

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.

## Java笔试题1

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

1. 访问修饰符作用范围由大到小是（ ）。

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

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.

## OCP-1Z0-816模拟测试2回顾

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);

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.

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$