0%

Merge k Sorted Lists

Merge k sorted linked lists and return it as one sorted list. Analyze and describe its complexity.

Example:

Input:
[
1->4->5,
1->3->4,
2->6
]
Output: 1->1->2->3->4->4->5->6

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
class Solution {
public ListNode mergeKLists(ListNode[] lists) {
List<Integer> nodes = new ArrayList<>();

for (int i = 0; i < lists.length; i++) {
while (lists[i] != null) {
nodes.add(lists[i].val);
lists[i] = lists[i].next;
}
}

if (nodes.size() == 0)
return null;

nodes.sort(Comparator.naturalOrder());
ListNode res = new ListNode(nodes.remove(0));
ListNode p = res;

for (int i = 0; i < nodes.size(); i++) {
p.next = new ListNode(nodes.get(i));
p = p.next;
}

return res;
}
}

Reference
https://leetcode-cn.com/problems/merge-k-sorted-lists

Static 理解

一. Static关键字的用途

在《Java编程思想》P86页有这样一段话:

  “static方法就是没有this的方法。在static方法内部不能调用非静态方法,反过来是可以的。而且可以在没有创建任何对象的前提下,仅仅通过类本身来调用static方法。这实际上正是static方法的主要用途。”

这段话虽然只是说明了static方法的特殊之处,但是可以看出static关键字的基本作用,简而言之,一句话来描述就是:

方便在没有创建对象的情况下来进行调用(方法/变量)。

很显然,被static关键字修饰的方法或者变量不需要依赖于对象来进行访问,只要类被加载了,就可以通过类名去进行访问。

static可以用来修饰类的成员方法、类的成员变量,另外可以编写static代码块来优化程序性能。

1. static方法

static方法一般称作静态方法,由于静态方法不依赖于任何对象就可以进行访问,因此对于静态方法来说,是没有this的,因为它不依附于任何对象,既然都没有对象,就谈不上this了。并且由于这个特性,在静态方法中不能访问类的非静态成员变量和非静态成员方法,因为非静态成员方法/变量都是必须依赖具体的对象才能够被调用。

但是要注意的是,虽然在静态方法中不能访问非静态成员方法和非静态成员变量,但是在非静态成员方法中是可以访问静态成员方法/变量的。举个简单的例子:

在上面的代码中,由于print2方法是独立于对象存在的,可以直接用过类名调用。假如说可以在静态方法中访问非静态方法/变量的话,那么如果在main方法中有下面一条语句:

MyObject.print2();

此时对象都没有,str2根本就不存在,所以就会产生矛盾了。同样对于方法也是一样,由于你无法预知在print1方法中是否访问了非静态成员变量,所以也禁止在静态成员方法中访问非静态成员方法。

而对于非静态成员方法,它访问静态成员方法/变量显然是毫无限制的。

因此,如果说想在不创建对象的情况下调用某个方法,就可以将这个方法设置为static。我们最常见的static方法就是main方法,至于为什么main方法必须是static的,现在就很清楚了。因为程序在执行main方法的时候没有创建任何对象,因此只有通过类名来访问。

另外记住,关于构造器是否是static方法可参考:http://blog.csdn.net/qq_17864929/article/details/48006835

2. static变量

static变量也称作静态变量,静态变量和非静态变量的区别是:静态变量被所有的对象所共享,在内存中只有一个副本,它当且仅当在类初次加载时会被初始化。而非静态变量是对象所拥有的,在创建对象的时候被初始化,存在多个副本,各个对象拥有的副本互不影响。

static成员变量的初始化顺序按照定义的顺序进行初始化。

3. static代码块

static关键字还有一个比较关键的作用就是 用来形成静态代码块以优化程序性能。static块可以置于类中的任何地方,类中可以有多个static块。在类初次被加载的时候,会按照static块的顺序来执行每个static块,并且只会执行一次。

为什么说static块可以用来优化程序性能,是因为它的特性:只会在类加载的时候执行一次。下面看个例子:

1
2
3
4
5
6
7
8
9
10
11
12
13
class Person{
private Date birthDate;

public Person(Date birthDate) {
this.birthDate = birthDate;
}

boolean isBornBoomer() {
Date startDate = Date.valueOf("1946");
Date endDate = Date.valueOf("1964");
return birthDate.compareTo(startDate)>=0 && birthDate.compareTo(endDate) < 0;
}
}

isBornBoomer是用来这个人是否是1946-1964年出生的,而每次isBornBoomer被调用的时候,都会生成startDate和birthDate两个对象,造成了空间浪费,如果改成这样效率会更好:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
class Person{
private Date birthDate;
private static Date startDate,endDate;
static{
startDate = Date.valueOf("1946");
endDate = Date.valueOf("1964");
}

public Person(Date birthDate) {
this.birthDate = birthDate;
}

boolean isBornBoomer() {
return birthDate.compareTo(startDate)>=0 && birthDate.compareTo(endDate) < 0;
}
}

因此,很多时候会将一些只需要进行一次的初始化操作都放在static代码块中进行。

二. Static关键字的误区

1. static关键字会改变类中成员的访问权限吗?

有些初学的朋友会将java中的static与C/C++中的static关键字的功能混淆了。在这里只需要记住一点:与C/C++中的static不同,Java中的static关键字不会影响到变量或者方法的作用域。在Java中能够影响到访问权限的只有private、public、protected(包括包访问权限)这几个关键字。static关键字并不会改变变量和方法的访问权限。

2. 能通过this访问静态成员变量吗?

虽然对于静态方法来说没有this,那么在非静态方法中能够通过this访问静态成员变量吗?先看下面的一个例子,这段代码输出的结果是什么?

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
public class Main {  
static int value = 33;

public static void main(String[] args) throws Exception{
new Main().printValue();
}

private void printValue(){
int value = 3;
System.out.println(this.value);
}
}
/**
33
*/

这里面主要考察队this和static的理解。this代表什么?this代表当前对象,那么通过new Main()来调用printValue的话,当前对象就是通过new Main()生成的对象。而static变量是被对象所享有的,因此在printValue中的this.value的值毫无疑问是33。在printValue方法内部的value是局部变量,根本不可能与this关联,所以输出结果是33。在这里永远要记住一点:静态成员变量虽然独立于对象,但是不代表不可以通过对象去访问,所有的静态方法和静态变量都可以通过对象访问(只要访问权限足够)。

3. static能作用于局部变量么?

在C/C++中static是可以作用域局部变量的,但是在Java中切记:static是不允许用来修饰局部变量。不要问为什么,这是Java语法的规定。

具体原因可以参考这篇博文的讨论:http://www.debugease.com/j2se/178932.html

三. 常见笔试面试题

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
31
32
public class Test extends Base{

static{
System.out.println("test static");
}

public Test(){
System.out.println("test constructor");
}

public static void main(String[] args) {
new Test();
}
}

class Base{

static{
System.out.println("base static");
}

public Base(){
System.out.println("base constructor");
}
}

/**
base static
test static
base constructor
test constructor
*/

至于为什么是这个结果,我们先不讨论,先来想一下这段代码具体的执行过程,在执行开始,先要寻找到main方法,因为main方法是程序的入口,但是在执行main方法之前,必须先加载Test类,而在加载Test类的时候发现Test类继承自Base类,因此会转去先加载Base类,在加载Base类的时候,发现有static块,便执行了static块。在Base类加载完成之后,便继续加载Test类,然后发现Test类中也有static块,便执行static块。在加载完所需的类之后,便开始执行main方法。在main方法中执行new Test()的时候会先调用父类的构造器,然后再调用自身的构造器。因此,便出现了上面的输出结果。

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
43
44
45
public class Test {
Person person = new Person("Test");
static{
System.out.println("test static");
}

public Test() {
System.out.println("test constructor");
}

public static void main(String[] args) {
new MyClass();
}
}

class Person{
static{
System.out.println("person static");
}
public Person(String str) {
System.out.println("person "+str);
}
}


class MyClass extends Test {
Person person = new Person("MyClass");
static{
System.out.println("myclass static");
}

public MyClass() {
System.out.println("myclass constructor");
}
}

/**
test static
myclass static
person static
person Test
test constructor
person MyClass
myclass constructor
*/

类似地,我们还是来想一下这段代码的具体执行过程。首先加载Test类,因此会执行Test类中的static块。接着执行new MyClass(),而MyClass类还没有被加载,因此需要加载MyClass类。在加载MyClass类的时候,发现MyClass类继承自Test类,但是由于Test类已经被加载了,所以只需要加载MyClass类,那么就会执行MyClass类的中的static块。在加载完之后,就通过构造器来生成对象。而在生成对象的时候,必须先初始化父类的成员变量,因此会执行Test中的Person person = new Person(),而Person类还没有被加载过,因此会先加载Person类并执行Person类中的static块,接着执行父类的构造器,完成了父类的初始化,然后就来初始化自身了,因此会接着执行MyClass中的Person person = new Person(),最后执行MyClass的构造器。

3. 这段代码的输出结果是什么?

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
public class Test {

static{
System.out.println("test static 1");
}
public static void main(String[] args) {

}

static{
System.out.println("test static 2");
}
}

/**
test static 1
test static 2
*/

虽然在main方法中没有任何语句,但是还是会输出,原因上面已经讲述过了。另外,static块可以出现类中的任何地方 只要不是方法内部,记住,任何方法内部都不行 ,并且执行是按照static块的顺序执行的。

java 内部类和静态内部类的区别

下面说一说内部类(Inner Class)和静态内部类(Static Nested Class)的区别:
定义在一个类内部的类叫内部类,包含内部类的类称为外部类。内部类可以声明public、protected、private等访问限制,可以声明 为abstract的供其他内部类或外部类继承与扩展,或者声明为static、final的,也可以实现特定的接口。外部类按常规的类访问方式使用内部 类,唯一的差别是外部类可以访问内部类的所有方法与属性,包括私有方法与属性。

一. 创建实例

OutClass.InnerClass obj = outClassInstance.new InnerClass(); //注意是外部类实例.new,内部类

AAA.StaticInner in = new AAA.StaticInner();//注意是外部类本身,静态内部类

二. 内部类中的this

内 部类中的this与其他类一样是指的本身。创建内部类对象时,它会与创造它的外围对象有了某种联系,于是能访问外围类的所有成员,不需任何特殊条件,可理 解为内部类链接到外部类。 用外部类创建内部类对象时,此内部类对象会秘密的捕获一个指向外部类的引用,于是,可以通过这个引用来访问外围类的成员。

三. 外部类访问内部类

内部类类似外部类的属性,因此访问内部类对象时总是需要一个创建好的外部类对象。内部类对象通过‘外部类名.this.xxx’的形式访问外部类的属性与方法。如:
System.out.println(“Print in inner Outer.index=” + pouter.this.index);
System.out.println(“Print in inner Inner.index=” + this.index);

四. 内部类向上转型

内部类也可以和普通类一样拥有向上转型的特性。将内部类向上转型为基类型,尤其是接口时,内部类就有了用武之地。如果内部类是private的,只可以被它的外部类问,从而完全隐藏实现的细节。

五. 方法内的类

方法内创建的类(注意方法中也能定义类),不能加访问修饰符。另外,方法内部的类也不是在调用方法时才会创建的,它们一样也被事先编译了。

六. 静态内部类

定义静态内部类:在定义内部类的时候,可以在其前面加上一个权限修饰符static。此时这个内部类就变为了静态内部类。

通常称为嵌套类,当内部类是static时,意味着:

[1]要创建嵌套类的对象,并不需要其外围类的对象;

[2]不能从嵌套类的对象中访问非静态的外围类对象(不能够从静态内部类的对象中访问外部类的非静态成员);

嵌 套类与普通的内部类还有一个区别:普通内部类的字段与方法,只能放在类的外部层次上,所以普通的内部类不能有static数据和static字段, 也不能包含嵌套类。但是在嵌套类里可以包含所有这些东西。也就是说,在非静态内部类中不可以声明静态成员,只有将某个内部类修饰为静态类,然后才能够在这 个类中定义静态的成员变量与成员方法。

另外,在创建静态内部类时不需要将静态内部类的实例绑定在外部类的实例上。普通非静态内部类的 对象是依附在外部类对象之中的,要在一个外部类中定义一个静态的内部类,不需要利用关键字new来创建内部类的实例。静态类和方法只属于类本身,并不属于 该类的对象,更不属于其他外部类的对象。

七. 内部类标识符

每个类会产生一个.class文件,文件名即为类名。同样,内部类也会产生这么一个.class文件,但是它的名称却不是内部类的类名,而是有着严格的限制:外围类的名字,加上$,再加上内部类名字。

八. 为何要用内部类?

  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
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
package com.test.xml;
public class OutClassTest {
static int a;

int b;

public static void test() {
System.out.println("outer class static function");
}

public static void main(String[] args) {
OutClassTest oc = new OutClassTest();
// new一个外部类
OutClassTest oc1 = new OutClassTest();
// 通过外部类的对象new一个非静态的内部类
OutClassTest.InnerClass no_static_inner = oc1.new InnerClass();
// 调用非静态内部类的方法
System.out.println(no_static_inner.getKey());

// 调用静态内部类的静态变量
System.out.println(OutClassTest.InnerStaticClass.static_value);
// 不依赖于外部类实例,直接实例化内部静态类
OutClassTest.InnerStaticClass inner = new OutClassTest.InnerStaticClass();
// 调用静态内部类的非静态方法
System.out.println(inner.getValue());
// 调用内部静态类的静态方法
System.out.println(OutClassTest.InnerStaticClass.getMessage());
}

private class InnerClass {
// 只有在静态内部类中才能够声明或定义静态成员
// private static String tt = "0";
private int flag = 0;

public InnerClass() {
// 三.非静态内部类的非静态成员可以访问外部类的非静态变量和静态变量
System.out.println("InnerClass create a:" + a);
System.out.println("InnerClass create b:" + b);
System.out.println("InnerClass create flag:" + flag);
//
System.out.println("InnerClass call outer static function");
// 调用外部类的静态方法
test();
}

public String getKey() {
return "no-static-inner";
}
}

private static class InnerStaticClass {
// 静态内部类可以有静态成员,而非静态内部类则不能有静态成员。
private static String static_value = "0";

private int flag = 0;

public InnerStaticClass() {
System.out.println("InnerClass create a:" + a);
// 静态内部类不能够访问外部类的非静态成员
// System.out.println("InnerClass create b:" + b);
System.out.println("InnerStaticClass flag is " + flag);
System.out.println("InnerStaticClass tt is " + static_value);
}

public int getValue() {
// 静态内部类访问外部类的静态方法
test();
return 1;
}

public static String getMessage() {
return "static-inner";
}
}

public OutClassTest() {
// new一个非静态的内部类
InnerClass ic = new InnerClass();
System.out.println("OuterClass create");
}

}

总结:

  • 1.静态内部类可以有静态成员(方法,属性),而非静态内部类则不能有静态成员(方法,属性)。
  • 2.静态内部类只能够访问外部类的静态成员,而非静态内部类则可以访问外部类的所有成员(方法,属性)。
  • 3.实例化一个非静态的内部类的方法:
  • a.先生成一个外部类对象实例
  • OutClassTest oc1 = new OutClassTest();
  • b.通过外部类的对象实例生成内部类对象
  • OutClassTest.InnerClass no_static_inner = oc1.new InnerClass();
  • 4.实例化一个静态内部类的方法:
  • a.不依赖于外部类的实例,直接实例化内部类对象
  • OutClassTest.InnerStaticClass inner = new OutClassTest.InnerStaticClass();
  • b.调用内部静态类的方法或静态变量,通过类名直接调用
  • OutClassTest.InnerStaticClass.static_value
  • OutClassTest.InnerStaticClass.getMessage()

references:
http://hi.baidu.com/zhumulangma/item/bcd478c140427b2cef466532
http://duqiangcise.iteye.com/blog/697476

Final 理解

一.Final 修饰成员变量的注意事项

final修饰成员变量,该成员变量必须在创建对象之前进行赋值,否则编译失败
final修饰成员变量,固定的不是成员变量拥有的默认值,如果固定的是默认值,那么将导致被final修饰的成员变量的值永远无法修改,只能是默认值,这也不符合语法规则

成员变量的赋值有三种实现方式:

  • 定义成员变量的时候手动赋值
  • 利用构造器对成员变量进行赋值
  • 利用set函数进行赋值(也即利用一般的方法进行赋值)

注意
被final修饰的成员变量,只能拥有3中所描述的赋值方法的1,2。3为什么不行?

解释:如1所描述,被final修饰的成员变量必须在对象创建之前进行赋值,如果方法3可以,那么我们知道对象创建后,才能调用方法3,也就是说成员变量利用方法3进行赋值,会导致成员变量的赋值发生在对象创建之后

二. 为什么被Final修饰的成员变量必须在对象创建之前进行赋值?

理解:
被final关键字修饰的东西有一个特点,那就是一旦被修饰,那么它的值也就终生不变,可见final关键字起到了固定的作用,既然起到固定那么,你就要提前告诉final固定的是谁,如果允许被final修饰的成员变量赋值发生在对象创建之后,那么对象创建完成后final固定的值还是未可知的

三. final修饰成员变量和final修饰局部变量的区别与联系:

  1. 被final修饰的成员变量与局部变量均具有:一旦赋值,该值就终身不变
  2. 被final修饰的成员变量必须要在创建对象之前进行赋值,否则会编译失败,但是局部变量可以不赋值,但是没有被赋值的局部变量不能够被使用,一旦被使用就会编译失败
  3. 综上:一旦决定使用final关键字来修饰成员变量或者局部变量,一定要做到提前赋值

四.Final修饰成员方法:

  1. final修饰成员方法,该成员方法就不能被子类重写,但是仍然可以被子类继承并可以通过子类对象调用该方法

五.Final修饰类

1.final修饰类,该类便不能被其他类继承,但是该类仍然能够创建对象,并且,可以利用该对象调用该类的成员变量或者成员方法

六.Final使用范围:

Final关键字可以修饰类,类的成员变量,类的成员方法,成员方法的局部变量,等等,

但是final关键字不能用来修饰构造方法?
理解:
final修饰普通方法,将导致子类无法重写该方法,而构造方法本身就不能够被子类重写,故如果用final修饰,如同多此一举

Reference
https://blog.csdn.net/xichengfengyulou/article/details/81155290

Remove Nth Node From End of List

Given a linked list, remove the n-th node from the end of list and return its head.

Example:

Given linked list: 1->2->3->4->5, and n = 2.

After removing the second node from the end, the linked list becomes 1->2->3->5.

Note:

Given n will always be valid.

Solution One

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
class Solution {
public ListNode removeNthFromEnd(ListNode head, int n) {
ListNode p = head;
ListNode temp = head;
int len = 1;

if (p == null)
return null;

while (p.next != null) {
len++;
p = p.next;
}

int loc = len - n;

if (loc == 0) {
return head.next;
}

for (int i = 1; i < loc; i++) {
temp = temp.next;
}

temp.next = temp.next.next;

return head;
}
}

Pass one time and get the length of LinkedList, so just count length - n - 1 times we can find the pre pointer. All we need to do is point pre pointer.next equal the next of which pointer we should delete.

Solution Two

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
class Solution {
public ListNode removeNthFromEnd(ListNode head, int n) {
List<ListNode> stack = new LinkedList<>();
ListNode temp = head;

while (temp != null) {
stack.add(temp);
temp = temp.next;
}

ListNode[] list = stack.toArray(new ListNode[stack.size()]);

if ((list.length - n - 1) < 0) return head.next;

list[list.length - n - 1].next = list[list.length - n].next;

return head;
}
}

Just let the List structure give a help, we can transfer a LinkedList to an Array. So all we need to do is let list[list.length - n - 1].next equals list[list.length - n].next.

Base case: if delete the head node we just need to return head.next.

Reference
https://leetcode-cn.com/problems/remove-nth-node-from-end-of-list