ARTS

Algorithm: 每周至少做一道LeetCode算法题
Review: 阅读并点评至少一篇英文技术文章
Tip: 学习至少一个技术技巧
Share: 分享一篇有观点和思考的技术文章

Algorithm

给定一个二叉树，返回它的前序遍历。

示例:

输入: [1,null,2,3] 

1
2
3
4
5
1
 \
  2
 /
3

输出: [1,2,3]

迭代

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29

public static List<Integer> preorderTraversal(TreeNode root) {

	List<Integer> result = new ArrayList<>();

	TreeNode tmp = root;
	Stack<TreeNode> stack = new Stack<>();

	while (tmp != null) {
		result.add(tmp.val);

		if (tmp.right != null) {
			stack.push(tmp.right);
		}

		if (tmp.left != null) {
			tmp = tmp.left;
		} else {
			if (stack.isEmpty()) {
				break;
			} else {
				tmp = stack.pop();
			}
		}
	}

	return result;
}

递归

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16

public List<Integer> preorderTraversal(TreeNode root) {
       List<Integer> result = new ArrayList<>();
       loop(root, result);
       return result;
   }

   private void loop(TreeNode root, List<Integer> result) {
       if (root == null) return;

       result.add(root.val);

       loop(root.left, result);
       loop(root.right, result);
   }

给定一个二叉树，返回它的中序遍历。

示例:

输入: [1,null,2,3]

1
2
3
4
5
1
 \
  2
 /
3

输出: [1,3,2]

迭代

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23

public static List<Integer> preorderTraversal(TreeNode root) {

	List<Integer> result = new ArrayList<>();

	Stack<TreeNode> stack = new Stack<>();
	TreeNode tmp = root;

	while (tmp != null || !stack.isEmpty()) {

		if (tmp != null) {
			stack.push(tmp);
			tmp = tmp.left;
		} else {
			tmp = stack.pop();
			result.add(tmp.val);
			tmp = tmp.right;
		}
	}

	return result;
}

给定一个二叉树，返回它的后序遍历。

示例:

输入: [1,null,2,3] 

1
2
3
4
5
1
 \
  2
 /
3

输出: [3,2,1]

迭代

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30

public static List<Integer> postorderTraversal(TreeNode value) {

	List<Integer> result = new ArrayList<>();

	Stack<TreeNode> stack = new Stack<>();
	TreeNode tmp = value, root = null;

	while (tmp != null || !stack.isEmpty()) {
		if (tmp != null) {
			stack.push(tmp);
			tmp = tmp.left;
		} else {
			tmp = stack.peek();
			if (tmp.right == null || tmp.right == root) {
				result.add(tmp.val);
				root = tmp;
				stack.pop();
				tmp = null;
			} else {
				tmp = tmp.right;
			}

		}

	}

	return result;
}

Review

Effective Java 3rd Edition Chapter 2 Item 2: Consider a builder when faced with many constructor parameters

    Static factories and constructors share a limitation: they do not scale well to large
numbers of optional parameters. Consider the case of a class representing the
Nutrition Facts label that appears on packaged foods. These labels have a few
required fields—serving size, servings per container, and calories per serving—
and more than twenty optional fields—total fat, saturated fat, trans fat,
cholesterol, sodium, and so on. Most products have nonzero values for only a
few of these optional fields.

    What sort of constructors or static factories should you write for such a class?
Traditionally, programmers have used the telescoping constructor pattern, in
which you provide a constructor with only the required parameters, another with
a single optional parameter, a third with two optional parameters, and so on,
culminating in a constructor with all the optional parameters. Here’s how it looks
in practice. For brevity’s sake, only four optional fields are shown:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
// Telescoping constructor pattern - does not scale well!
public class NutritionFacts {
  private final int servingSize; // (mL) required
  private final int servings; // (per container) requiredprivate final int calories; // (per serving) optional
  private final int fat; // (g/serving) optional
  private final int sodium; // (mg/serving) optional
  private final int carbohydrate; // (g/serving) optional
  
  public NutritionFacts(int servingSize, int servings) {
  	this(servingSize, servings, 0);
  } 
  public NutritionFacts(int servingSize, int servings, int calories) {
   this(servingSize, servings, calories, 0);
  } 
  
  public NutritionFacts(int servingSize, int servings, int calories, int fat) {
   this(servingSize, servings, calories, fat, 0);
  } 
  
  public NutritionFacts(int servingSize, int servings, int calories, int fat, int sodium) {
   this(servingSize, servings, calories, fat, sodium, 0);
  } 
  
  public NutritionFacts(int servingSize, int servings, int calories, int fat, int sodium, int carbohydrate) {
    this.servingSize = servingSize;
    this.servings = servings;
    this.calories = calories;
    this.fat = fat;
    this.sodium = sodium;
    this.carbohydrate = carbohydrate;
  }
}

    When you want to create an instance, you use the constructor with the shortest
parameter list containing all the parameters you want to set:

1
2
3
NutritionFacts cocaCola =
new NutritionFacts(240, 8, 100, 0, 35, 27);

    Typically this constructor invocation will require many parameters that you
don’t want to set, but you’re forced to pass a value for them anyway. In this case,
we passed a value of 0 for fat. With “only” six parameters this may not seem
so bad, but it quickly gets out of hand as the number of parameters increases.
In short, the telescoping constructor pattern works, but it is hard to write
client code when there are many parameters, and harder still to read it.

    The reader is left wondering what all those values mean and must carefully countparameters to find out.
Long sequences of identically typed parameters can cause
subtle bugs. If the client accidentally reverses two such parameters, the compiler
won’t complain, but the program will misbehave at runtime (Item 51).
A second alternative when you’re faced with many optional parameters in a
constructor is the JavaBeans pattern, in which you call a parameterless
constructor to create the object and then call setter methods to set each required
parameter and each optional parameter of interest:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
// JavaBeans Pattern - allows inconsistency, mandates mutability
public class NutritionFacts {
  // Parameters initialized to default values (if any)
  private int servingSize = -1; // Required; no default value
  private int servings = -1; // Required; no default value
  private int calories = 0;
  private int fat = 0;
  private int sodium = 0;
  private int carbohydrate = 0;
  
  public NutritionFacts() { }
  // Setters
  public void setServingSize(int val) { servingSize = val; }
  public void setServings(int val) { servings = val; }
  public void setCalories(int val) { calories = val; }
  public void setFat(int val) { fat = val; }
  public void setSodium(int val) { sodium = val; }
  public void setCarbohydrate(int val) { carbohydrate = val; }
}

    This pattern has none of the disadvantages of the telescoping constructor pattern.
It is easy, if a bit wordy, to create instances, and easy to read the resulting code:

1
2
3
4
5
6
NutritionFacts cocaCola = new NutritionFacts();
cocaCola.setServingSize(240);
cocaCola.setServings(8);
cocaCola.setCalories(100);
cocaCola.setSodium(35);
cocaCola.setCarbohydrate(27);

    Unfortunately, the JavaBeans pattern has serious disadvantages of its own.
Because construction is split across multiple calls, a JavaBean may be in an
inconsistent state partway through its construction. The class does not have
the option of enforcing consistency merely by checking the validity of the
constructor parameters. Attempting to use an object when it’s in an inconsistent
state may cause failures that are far removed from the code containing the bug
and hence difficult to debug. A related disadvantage is that the JavaBeanspattern precludes the possibility of
making a class immutable (Item 17) and requires added effort on the part of the programmer to ensure thread safety.

    It is possible to reduce these disadvantages by manually “freezing” the object
when its construction is complete and not allowing it to be used until frozen, but
this variant is unwieldy and rarely used in practice. Moreover, it can cause errors
at runtime because the compiler cannot ensure that the programmer calls the
freeze method on an object before using it.

    Luckily, there is a third alternative that combines the safety of the telescoping
constructor pattern with the readability of the JavaBeans pattern. It is a form of
the Builder pattern [Gamma95]. Instead of making the desired object directly,
the client calls a constructor (or static factory) with all of the required parameters
and gets a builder object. Then the client calls setter-like methods on the builder
object to set each optional parameter of interest. Finally, the client calls a
parameterless build method to generate the object, which is typically
immutable. The builder is typically a static member class (Item 24) of the class it
builds. Here’s how it looks in practice:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
// Builder Pattern
public class NutritionFacts {
  private final int servingSize;
  private final int servings;
  private final int calories;
  private final int fat;
  private final int sodium;
  private final int carbohydrate;
  
public static class Builder {
  // Required parameters
  private final int servingSize;
  private final int servings;
  // Optional parameters - initialized to default values
  private int calories = 0;
  private int fat = 0;
  private int sodium = 0;
  private int carbohydrate = 0;
  
  public Builder(int servingSize, int servings) {
    this.servingSize = servingSize;
    this.servings = servings;
  } 
  public Builder calories(int val)
  { calories = val; return this; }
  
  public Builder fat(int val)
  { fat = val; return this; }
  
  public Builder sodium(int val)
  { sodium = val; return this; }
  
  public Builder carbohydrate(int val)
  { carbohydrate = val; return this; }
  
  public NutritionFacts build() {
  return new NutritionFacts(this);
  }
} 
  
  private NutritionFacts(Builder builder) {
    servingSize = builder.servingSize;
    servings = builder.servings;
    calories = builder.calories;
    fat = builder.fat;
    sodium = builder.sodium;
    carbohydrate = builder.carbohydrate;
  }
}

    The NutritionFacts class is immutable, and all parameter default values
are in one place. The builder’s setter methods return the builder itself so that
invocations can be chained, resulting in a fluent API. Here’s how the client code
looks:

1
2
NutritionFacts cocaCola = new NutritionFacts.Builder(240, 8)
.calories(100).sodium(35).carbohydrate(27).build();

    This client code is easy to write and, more importantly, easy to read. The
Builder pattern simulates named optional parameters as found in Python and
Scala.

    Validity checks were omitted for brevity. To detect invalid parameters as soon
as possible, check parameter validity in the builder’s constructor and methods.
Check invariants involving multiple parameters in the constructor invoked by the
build method. To ensure these invariants against attack, do the checks on
object fields after copying parameters from the builder (Item 50). If a check
fails, throw an IllegalArgumentException (Item 72) whose detail
message indicates which parameters are invalid (Item 75).

    The Builder pattern is well suited to class hierarchies. Use a parallel
hierarchy of builders, each nested in the corresponding class. Abstract classes
have abstract builders; concrete classes have concrete builders. For example,
consider an abstract class at the root of a hierarchy representing various kinds of
pizza:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
  // Builder pattern for class hierarchies
  public abstract class Pizza {
  public enum Topping { HAM, MUSHROOM, ONION, PEPPER, SAUSAGE }
  final Set<Topping> toppings;
  
  abstract static class Builder<T extends Builder<T>> {
    EnumSet<Topping> toppings = EnumSet.noneOf(Topping.class);
    public T addTopping(Topping topping) {
      toppings.add(Objects.requireNonNull(topping));
      return self();
    } 
  
  	abstract Pizza build();
  
 	 // Subclasses must override this method to return "this"
 	 protected abstract T self();
  }
  
  Pizza(Builder<?> builder) {
  	toppings = builder.toppings.clone(); // See Item 50
  }
}

    Note that Pizza.Builder is a generic type with a recursive type parameter
(Item 30). This, along with the abstract self method, allows method chaining
to work properly in subclasses, without the need for casts. This workaround for
the fact that Java lacks a self type is known as the simulated self-type idiom.
Here are two concrete subclasses of Pizza, one of which represents a
standard New-York-style pizza, the other a calzone. The former has a required
size parameter, while the latter lets you specify whether sauce should be inside
or out:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
public class NyPizza extends Pizza {
  public enum Size { SMALL, MEDIUM, LARGE }
  private final Size size;

  public static class Builder extends Pizza.Builder<Builder> {
    private final Size size;
    public Builder(Size size) {
      this.size = Objects.requireNonNull(size);
   } 
    @Override 
    public NyPizza build() {
      return new NyPizza(this);
    } 
    @Override 
    protected Builder self() { 
      return this; 
   }
  } 

  private NyPizza(Builder builder) {
    super(builder);
    size = builder.size;
  }
} 

public class Calzone extends Pizza {
  private final boolean sauceInside;
  public static class Builder extends Pizza.Builder<Builder> {
    private boolean sauceInside = false; // Default
    public Builder sauceInside() {
        sauceInside = true;
        return this;
    } 
    @Override 
    public Calzone build() {
        return new Calzone(this);
     } 
    @Override 
    protected Builder self() { 
        return this; 
    }
  } 
 private Calzone(Builder builder) {
  super(builder);
  sauceInside = builder.sauceInside;
 }
}

    Note that the build method in each subclass’s builder is declared to return
the correct subclass: the build method of NyPizza.Builder returns
NyPizza, while the one in Calzone.Builder returns Calzone. This
technique, wherein a subclass method is declared to return a subtype of the
return type declared in the super-class, is known as covariant return typing. It
allows clients to use these builders without the need for casting.

    The client code for these “hierarchical builders” is essentially identical to the
code for the simple NutritionFacts builder. The example client code
shown next assumes static imports on enum constants for brevity:

1
2
3
4
NyPizza pizza = new NyPizza.Builder(SMALL)
.addTopping(SAUSAGE).addTopping(ONION).build();
Calzone calzone = new Calzone.Builder()
.addTopping(HAM).sauceInside().build();

    A minor advantage of builders over constructors is that builders can havemultiple
varargs parameters because each parameter is specified in its own
method. Alternatively, builders can aggregate the parameters passed into
multiple calls to a method into a single field, as demonstrated in the
addTopping method earlier.

    The Builder pattern is quite flexible. A single builder can be used repeatedly
to build multiple objects. The parameters of the builder can be tweaked between
invocations of the build method to vary the objects that are created. A builder
can fill in some fields automatically upon object creation, such as a serial
number that increases each time an object is created.

    The Builder pattern has disadvantages as well. In order to create an object,
you must first create its builder. While the cost of creating this builder is unlikely
to be noticeable in practice, it could be a problem in performance-critical
situations. Also, the Builder pattern is more verbose than the telescoping
constructor pattern, so it should be used only if there are enough parameters to
make it worthwhile, say four or more. But keep in mind that you may want to
add more parameters in the future. But if you start out with constructors or static
factories and switch to a builder when the class evolves to the point where the
number of parameters gets out of hand, the obsolete constructors or static
factories will stick out like a sore thumb. Therefore, it’s often better to start with
a builder in the first place.

    In summary, the Builder pattern is a good choice when designing classes
whose constructors or static factories would have more than a handful of
parameters, especially if many of the parameters are optional or of identical
type. Client code is much easier to read and write with builders than with
telescoping constructors, and builders are much safer than JavaBeans.

总结

    Builder 模式非常灵活。 单个 builder 可以重复使用来构建多个对象。 builder
的参数可以在构建方法的调用之间进行调整，以改变创建的对象。 builder 可以在创建对象时自动填充一些属性，例如每次创建对象时增加的序列号。
Builder 模式也有缺点。为了创建对象，首先必须创建它的 builder。虽然创建这个 builder 的成本在实践中不太可
能被注意到，但在性能关键的情况下可能会出现问题。而且，builder 模式比伸缩构造方法模式更冗长，因此只有在
有足够的参数时才值得使用它，比如四个或更多,而且最好从一开始就创建一个 builder。

Tips&Share

     我认为这俩个环节有时候可以合在一起

【原创】关于Spring中的参数校验的一点思考– JavaGuide