0%

三数之和(Unsolved)

给定一个包含 n 个整数的数组 nums,判断 nums 中是否存在三个元素 a,b,c ,使得 a + b + c = 0 ?找出所有满足条件且不重复的三元组。

注意:答案中不可以包含重复的三元组。

示例

给定数组 nums = [-1, 0, 1, 2, -1, -4],

满足要求的三元组集合为:
[
[-1, 0, 1],
[-1, -1, 2]
]

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
class Solution {
public List<List<Integer>> threeSum(int[] nums) {
if (nums == null || nums.length <= 2) {
return Collections.emptyList();
}
List<List<Integer>> result = new LinkedList<>();

Arrays.sort(nums);
for (int i = 0; i < nums.length - 2; i++) {
// 加速1:c为非负数,就不能满足a+b+c=0了
if (nums[i] > 0) {
return result;
}
// 加速2:跳过计算过的数据,同时防止结果重复
if (i != 0 && nums[i] == nums[i-1]) {
continue;
}
int head = i + 1;
int tail = nums.length - 1;
while (head < tail) {
int sum = -(nums[head] + nums[tail]);
if (sum == nums[i]) {
result.add(Arrays.asList(nums[i], nums[head], nums[tail]));
// 加速3:跳过计算过的数据,同时防止结果重复
while (head < tail && nums[head] == nums[head+1]) {
head++;
}
while (head < tail && nums[tail] == nums[tail-1]) {
tail--;
}
}
if (sum <= nums[i]) {
tail--;
} else {
head++;
}
}
}

return result;
}
}

Reference
https://leetcode-cn.com/problems/3sum/solution/san-shu-zhi-he-javajian-ji-ti-jie-by-wang-zi-hao-z/

面向切面编程

Summary

在软件业,AOP为Aspect Oriented Programming的缩写,意为:面向切面编程,通过预编译方式和运行期间动态代理实现程序功能的统一维护的一种技术。AOP是OOP的延续,是软件开发中的一个热点,也是Spring框架中的一个重要内容,是函数式编程的一种衍生范型。利用AOP可以对业务逻辑的各个部分进行隔离,从而使得业务逻辑各部分之间的耦合度降低,提高程序的可重用性,同时提高了开发的效率。

Description

Aspect Oriented Programming(AOP)是较为热门的一个话题。AOP,国内大致译作“面向切面编程”。

“面向切面编程”,这样的名字并不是非常容易理解,且容易产生一些误导。有些人认为“OOP/OOD11即将落伍,AOP是新一代软件开发方式”。显然,发言者并没有理解AOP的含义。Aspect,的确是“方面”的意思。不过,汉语传统语义中的“方面”,大多数情况下指的是一件事情的不同维度、或者说不同角度上的特性,比如我们常说:“这件事情要从几个方面来看待”,往往意思是:需要从不同的角度来看待同一个事物。这里的“方面”,指的是事物的外在特性在不同观察角度下的体现。而在AOP中,Aspect的含义,可能更多的理解为“切面”比较合适。

可以通过预编译方式和运行期动态代理实现在不修改源代码的情况下给程序动态统一添加功能的一种技术。AOP实际是GoF设计模式的延续,设计模式孜孜不倦追求的是调用者和被调用者之间的解耦,提高代码的灵活性和可扩展性,AOP可以说也是这种目标的一种实现。

在Spring中提供了面向切面编程的丰富支持,允许通过分离应用的业务逻辑与系统级服务(例如审计(auditing)和事务(transaction)管理)进行内聚性的开发。应用对象只实现它们应该做的——完成业务逻辑——仅此而已。它们并不负责(甚至是意识)其它的系统级关注点,例如日志或事务支持。

主要功能

日志记录,性能统计,安全控制,事务处理,异常处理等等。

主要意图

将日志记录,性能统计,安全控制,事务处理,异常处理等代码从业务逻辑代码中划分出来,通过对这些行为的分离,我们希望可以将它们独立到非指导业务逻辑的方法中,进而改变这些行为的时候不影响业务逻辑的代码。

控制反转

Summary

控制反转(Inversion of Control,缩写为IoC),是面向对象编程中的一种设计原则,可以用来减低计算机代码之间的耦合度。其中最常见的方式叫做依赖注入(Dependency Injection,简称DI),还有一种方式叫“依赖查找”(Dependency Lookup)。通过控制反转,对象在被创建的时候,由一个调控系统内所有对象的外界实体将其所依赖的对象的引用传递给它。也可以说,依赖被注入到对象中。

Description

Class A中用到了Class B的对象b,一般情况下,需要在A的代码中显式的new一个B的对象。

采用依赖注入技术之后,A的代码只需要定义一个私有的B对象,不需要直接new来获得这个对象,而是通过相关的容器控制程序来将B对象在外部new出来并注入到A类里的引用中。而具体获取的方法、对象被获取时的状态由配置文件(如XML)来指定。

设计模式

IoC可以认为是一种全新的设计模式,但是理论和时间成熟相对较晚,并没有包含在GoF中。
Interface Driven Design接口驱动,接口驱动有很多好处,可以提供不同灵活的子类实现,增加代码稳定和健壮性等等,但是接口一定是需要实现的,也就是如下语句迟早要执行:AInterface a = new AInterfaceImp(); 这样一来,耦合关系就产生了,如:

1
2
3
4
5
6
7
8
9
10
11
classA
{
AInterface a;

A(){}

AMethod()//一个方法
{
a = new AInterfaceImp();
}
}

Class A与AInterfaceImp就是依赖关系,如果想使用AInterface的另外一个实现就需要更改代码了。当然我们可以建立一个Factory来根据条件生成想要的AInterface的具体实现,即:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
InterfaceImplFactory
{
AInterface create(Object condition)
{
if(condition == condA)
{
return new AInterfaceImpA();
}
else if(condition == condB)
{
return new AInterfaceImpB();
}
else
{
return new AInterfaceImp();
}
}
}

表面上是在一定程度上缓解了以上问题,但实质上这种代码耦合并没有改变。通过IoC模式可以彻底解决这种耦合,它把耦合从代码中移出去,放到统一的XML 文件中,通过一个容器在需要的时候把这个依赖关系形成,即把需要的接口实现注入到需要它的类中,这可能就是“依赖注入”说法的来源了。

IoC模式,系统中通过引入实现了IoC模式的IoC容器,即可由IoC容器来管理对象的生命周期、依赖关系等,从而使得应用程序的配置和依赖性规范与实际的应用程序代码分离。其中一个特点就是通过文本的配置文件进行应用程序组件间相互关系的配置,而不用重新修改并编译具体的代码。

当前比较知名的IoC容器有:Pico Container、Avalon 、Spring、JBoss、HiveMind、EJB等。

在上面的几个IoC容器中,轻量级的有Pico Container、Avalon、Spring、HiveMind等,超重量级的有EJB,而半轻半重的有容器有JBoss,Jdon等。

可以把IoC模式看作工厂模式的升华,把IoC容器看作是一个大工厂,只不过这个大工厂里要生成的对象都是在XML文件中给出定义的。利用Java 的“反射”编程,根据XML中给出的类定义生成相应的对象。从实现来看,以前在工厂模式里写死了的对象,IoC模式改为配置XML文件,这就把工厂和要生成的对象两者隔离,极大提高了灵活性和可维护性。

IoC中最基本的Java技术就是“反射”编程。通俗的说,反射就是根据给出的类名(字符串)来生成对象。这种编程方式可以让应用在运行时才动态决定生成哪一种对象。反射的应用是很广泛的,像Hibernate、Spring中都是用“反射”做为最基本的技术手段。

在过去,反射编程方式相对于正常的对象生成方式要慢10几倍,这也许也是当时为什么反射技术没有普遍应用开来的原因。但经SUN改良优化后,反射方式生成对象和通常对象生成方式,速度已经相差不大了(但依然有一倍以上的差距)。

设计模式

Summary

设计模式是面向对象设计中反复出现的问题的解决方案。这个术语在1990年代由Erich Gamma等人从建筑设计领域引入到计算机科学中来。算法不是设计模式因为算法致力于解决问题而非设计问题。设计模式通常提供一种讨论软件设计的公共语言,使得熟练设计者的设计经验可以被初学者和其他设计者掌握。*设计模式还为软件重构提供了目标。

History

Erich Gamma与Richard Helm, Ralph Johnson ,John Vlissides合作出版了Design Patterns - Elements of Reusable Object-Oriented Software 一书,在此书中共收录了23个设计模式。这四位作者在软件开发领域里也以他们的匿名著称Gang of Four(四人帮,简称GoF),并且是他们在此书中的协作导致了软件设计模式的突破。

Pattern Format

尽管名称和顺序在不同的资料中各有不同,描述模式的格式大致分为以下四个主要部分:
模式名称(Pattern Name):每一个模式都有自己的名字,模式的名字使得我们可以讨论我们的设计。
问题(Problem):在面向对象的系统设计过程中反复出现的特定场合,它导致我们采用某个模式。
解决方案(Solution):上述问题的解决方案,其内容给出了设计的各个组成部分,它们之间的关系、职责划分和协作方式。
效果(Consequence):采用该模式对软件系统其他部分的影响,比如对系统的扩充性、可移植性的影响。影响也包括负面的影响。
别名(Also Known As):一个模式可以有超过一个以上的名称。这些名称应该要在这一节注明。
动机(Motivation):该模式应该利用在哪种情况下是本节提供的方案(包括问题与来龙去脉)的责任。
应用(Applicability)
结构(Structure):这部分常用类图与互动图阐述此模式。
参与者(Participants):这部分提供一份本模式用到的类与物件清单,与它们在设计下扮演的角色。
合作(Collaboration):描述在此模式下,类与物件间的互动。
结果(Consequences):这部分应描述使用本模式後的结果、副作用、与交换(trade-off)
实现(Implementaion):这部分应描述实现该模式、该模式的部分方案、实现该模式的可能技术、或者建议实现模式的方法。
例程(Sample Code):示范程式。
已知应用(Known Uses):业界已知的实做范例。
相关模式(Related Patterns):这部分包括其他相关模式,以及与其他类似模式的不同。

Mode

模式列表

  • 基础模式
  • 委托模式
  • 接口模式
  • 代理模式

创建模式

  • 抽象工厂模式(Abstract Factory) ,提供一个创建一系列相关或相互依赖对象的接口,而无需指定它们具体的类。
  • 生成器模式 (Builder),将一个复杂对象的构建与它的表示分离,使得同样的构建过程可以创建不同的表示。
  • 工厂方法模式(Factory Method) ,定义一个用于创建对象的接口,让子类决定将哪一个类实例化。Factory Method使一个类的实例化延迟到其子类。
  • 原型模式 (Prototype) ,用原型实例指定创建对象的种类,并且通过拷贝这个原型来创建新的对象。
  • 单例模式(Singleton),保证一个类仅有一个实例,并提供一个访问它的全局访问点。

结构模式

  • 适配器模式 (Adapter) ,将一个类的接口转换成客户希望的另外一个接口。Adapter模式使得原本由于接口不兼容而不能一起工作的那些类可以一起工作。
  • 桥接模式(Bridge) ,将抽象部分与它的实现部分分离,使它们都可以独立地变化。
  • 组合模式(Composite) ,将对象组合成树形结构以表示“部分-整体”的层次结构。它使得客户对单个对象和复合对象的使用具有一致性。
  • 容器模式
  • 修饰模式 (Decorator) ,动态地给一个对象添加一些额外的职责。就扩展功能而言, 它比生成子类方式更为灵活。
  • 扩展性模式
  • 外观模式
  • 享元模式
  • 管道与过滤器模式
  • 代理模式(Proxy) ,为其他对象提供一个代理以控制对这个对象的访问。

行为模式

  • 责任链模式 (Chain of Responsibility) ,为解除请求的发送者和接收者之间耦合,而使多个对象都有机会处理这个请求。将这些对象连成一条链,并沿着这条链传递该请求,直到有一个对象处理它。
  • 命令模式 (Command) ,将一个请求封装为一个对象,从而使你可用不同的请求对客户进行参数化;对请求排队或记录请求日志,以及支持可取消的操作。
  • 柯里化模式
  • 事件监听器模式
  • 解释器模式
  • 迭代器模式
  • 中介者模式
  • 备忘录模式 (Memento) ,在不破坏封装性的前提下,捕获一个对象的内部状态,并在该对象之外保存这个状态。这样以后就可将该对象恢复到保存的状态。
  • 观察者模式(Observer) ,定义对象间的一种一对多的依赖关系,以便当一个对象的状态发生改变时,所有依赖于它的对象都得到通知并自动刷新。
  • 状态模式 (State) ,允许一个对象在其内部状态改变时改变它的行为。对象看起来似乎修改了它所属的类。
  • 策略模式 (Strategy) ,定义一系列的算法,把它们一个个封装起来, 并且使它们可相互替换。本模式使得算法的变化可独立于使用它的客户。
    模板方法模式
  • 访问者模式 (Visitor),表示一个作用于某对象结构中的各元素的操作。它使你可以在不改变各元素的类的前提下定义作用于这些元素的新操作。
  • 层次访问者模式

并发模式

  • 模式 Action at a distance
  • 模式 Balking
  • 模式 Guarded suspension
  • 模式 Scheduler
  • 模式 Read write lock
  • 模式 Double checked locking
  • 模式 Disable job requests while running job

实时模式

  • 模式 Scheduled task
  • 模式 User interface
  • 模式 Disable job requests while running job

其他

  • 模型—视图—控制器模式

Day03 - 移除元素

给定一个数组 nums 和一个值 val,你需要原地移除所有数值等于 val 的元素,返回移除后数组的新长度。

不要使用额外的数组空间,你必须在原地修改输入数组并在使用 O(1) 额外空间的条件下完成。

元素的顺序可以改变。你不需要考虑数组中超出新长度后面的元素。

示例 1:

给定 nums = [3,2,2,3], val = 3,函数应该返回新的长度 2, 并且 nums 中的前两个元素均为 2。你不需要考虑数组中超出新长度后面的元素.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
class Solution {
public int removeElement(int[] nums, int val) {
int res = 0;

for (int i = 0; i < nums.length; i++) {
if (nums[i] != val) {
nums[res] = nums[i];
res++;
}
}

return res;
}
}

/**
执行用时 :0 ms, 在所有 Java 提交中击败了100.00%的用户
内存消耗 :38.1 MB, 在所有 Java 提交中击败了5.05%的用户
*/

res记录新数组长度,遍历一遍数组满足条件则在相应位置赋值。

Reference
https://leetcode-cn.com/problems/remove-element