ARTS 打卡 (20.09.21-20.09.27)

用户头像
小王同学
关注
发布于: 2020 年 10 月 11 日

Algorithm:

leetcode NO.16 threeSumClosest

思路:

排序+双指针

1、先将数组排序,既可以方便左右指针的移动,也可以忽略之前计算过的重复数字。

2、数组的元素挨个枚举,然后计算双指针指向的值与枚举值的和与目标值的差的绝对值,计算出最小的绝对值做为结果。

3、如果计算出与目标值的差为0的绝对值,直接返回结果即可。

4、移动指针的过程中,如果发现前一个与后一个的值相等,不必继续计算,直接略过即可。(数组是有序的)

4、双指针移动的区间[i+1,n),i是当前枚举元素的下标。

5、时间复杂度O(N^2),空间复杂度O(N)。

class Solution {
public int threeSumClosest(int[] nums, int target) {
Arrays.sort(nums);
int n = nums.length;
int best = 10000;
for (int i = 0; i < n; i++) {
if(i > 0 && nums[i] == nums[i - 1]) {
continue;
}
int j = i + 1, k = n - 1;
while (j < k) {
int sum = nums[j] + nums[k] + nums[i];
if(sum == target) {
return sum;
}
if(Math.abs(sum - target) < Math.abs(best - target)){
best = sum;
}
if(sum > target) {
int k0 = k - 1;
while (j < k0 && nums[k0] == nums[k]) {
--k0;
}
k = k0;
} else {
int j0 = j + 1;
while (j0 < k && nums[j0] == nums[j]) {
++j0;
}
j = j0;
}
}
}
return best;
}
}



Review:

Effctive Java Item4

Enforce noninstantiability with a private constructor

通过构造函数私有化来强制类的不可实例化



有些类里面的方法都是静态的,比如说java.lang.Math java.util.Arrays,由于有些人滥用这些类中的方法,从而避免了从面向对象的角度思考问题,这种类设计也存在一些不好的名声。这些功能性质的类设计初衷是不可被实例化为对象的,但是编译器会为没有明确声明构造函数的类提供一个共有的、无参的构造函数,有时候我们有意或无意中,会实例化这些类,这时,我们只要将无参构造函数声明为私有即可。



例如:

public class UtilityClass {
// Suppress default constructor for noninstantiability
private UtilityClass() {
throw new AssertionError();
}
... // Remainder omitted
}

抛出AssertionError不是必要的,这样做可以确保类的内部不会去实例化对象

这种做法存在一定的负面影响,这种类是不能被继承的,因为初始化子类时,子类会通过super()调用父类的构造函数,但是该类的构造函数已经不可调用了。



Effctive Java Item5

Perfer dependency injection to hardwiring resources

使用依赖注入(DI)而不是硬编码

书中以拼写检查器依赖字典为例,比如:英语的拼写检查器依赖英语字典,法语拼写检查器依赖法语字典,书中给出一种最简单的依赖注入方式就是在构造器中传递字典

// Dependency injection provides flexibility and testability
public class SpellChecker {
private final Lexicon dictionary;
public SpellChecker(Lexicon dictionary) {
this.dictionary = Objects.requireNonNull(dictionary);
}
public boolean isValid(String word) { ... }
public List<String> suggestions(String typo) { ... }
}



这样以来,就大大提高了拼写检查器的灵活性。

一种非常有用的构造器注入的变体就是我们可以吧资源工厂传递给构造函数,资源工厂是一个可以被重复调用来创建实例的对象。典型的代表就是Java8中的Supplier<T>接口,它是一个完美的工厂代表。

尽管依赖注入大大提高了灵活性,但是它会让大项目搞的十分混乱,这些项目通常会包含数以千计的依赖项,但是这种混乱可以通过依赖注入框架来消除,如:spring IOC 。

总而言之,不要使用单利或者静态的工具类来依赖能够改变类的行为的底层资源,并且不要让类来创建这些资源,而是将资源或者创建资源的工厂传递给构造函数。

Tip:

Review 的过程中提到了Supplier<T>接口,那我们就来研究一下Java8中的Supplier。

@FunctionalInterface
public interface Supplier<T> {
/**
* Gets a result.
*
* @return a result
*/
T get();
}

作用:提前定义可能返回的一个指定类型结果,等需要调用的时候再获取结果。

通常会结合泛型限定边界来使用

如:

Mosaic create(Supplier<? extends Tile> tileFactory) { ... }



Share:

https://coolshell.cn/articles/11609.html

用户头像

小王同学

关注

还未添加个人签名 2019.03.04 加入

还未添加个人简介

评论

发布
暂无评论
ARTS 打卡 (20.09.21-20.09.27)