明日又天涯

作者:三毛

我的朋友,今夜我是跟你告别了,多少次又多少次,你的眼光在默默的问我,Echo,你的将来要怎么过?你一个人这样的走了,你会好好的吗?你会吗?你会吗?

看见你哀怜的眼睛,我的胃马上便绞痛起来,我也轻轻的在对自己哀求——不要再痛了,不要再痛了,难道痛得还没有尽头吗?

明日,是一个不能逃避的东西,我没有退路。我不能回答你眼里的问题,我只知道,我胃痛,我便捂住自己的胃,不说一句话,因为这个痛是真真实实的。

多少次,你说,虽然我是意气飞扬,满含自信若有所思的仰着头,脸上荡着笑,可是,灯光下,我的眼睛藏不住秘密,我的眸子里,闪烁的只是满满的倔强的眼泪,还有,那一个海也似的情深的故事。

你说,Echo,你会一个人过日子吗?我想反问你,你听说过有谁,在这世界上,不是孤独的生,不是孤独的死?有谁?请你告诉我。

你也说,不要忘了写信来,细细的告诉我,你的日子是怎么的在度过,因为有人在挂念你。

我爱的朋友,不必写信,现在就可以告诉你,我是走了,回到我的家里去,在那儿,有海,有空茫的天,还有那永远吹拂着大风的哀愁海滩。

家的后面,是一片无人的田野,左邻右舍,也只有在度假的时候才会出现,这个地方,可以走两小时不见人迹,而海鸥的叫声却是总也不断。

我的日子会怎么过?

我会一样的洗衣服,擦地,管我的盆景,铺我的床。偶尔,我会去小镇上,在买东西的时候,跟人说说话,去邮局信箱里,盼一封你的来信。也可能,在天气晴朗,而又心境安稳的时候,我会坐飞机,去那个最后之岛,买一把鲜花,在荷西长眠的地方坐一个静静的黄昏。

再也没有鬼哭神号的事情了,最坏的已经来过了,再也没有什么。我只是有时会胃痛,会在一个人吃饭的时候,有些食不下咽。

也曾对你说过,暮色来时,我会仔细的锁好门窗,也不再在白日将自己打扮得花枝招展,因为我很明白,昨日的风情,只会增加自己今日的不安全,那么,我的长裙,便留在箱子里吧。

又说过,要养一只大狼狗,买一把猎枪,要是有谁,不得我的允许敢跨入我的花园一步,那么我要他死在我的枪下。说出这句话来,你震惊了,你心疼了,你方才知道,Echo的明日不是好玩的,你说,Echo你还是回来,

我一直是要你回来的。

我的朋友,我想再问你一句已经问过的话,有谁,在这个世界上不是孤独的生,不是孤独的死?

青春结伴,我已有过,是感恩,是满足,没有遗憾。

再说,夜来了,我拉上窗帘,将自己锁在屋内,是安全的,不再出去看黑

夜里满天的繁星了,因为我知道,在任何一个星座上,都找不到我心里呼叫的名字。

我开了温暖的落地灯,坐在我的大摇椅里,靠在软软的红色垫子上,这儿是我的家,一向是我的家。我坐下,擦擦我的口琴,然后,试几个音,然后,在那一屋的寂静里,我依旧吹着那首最爱的歌曲——甜蜜的家庭。

字符串总结

1. 字符串反转问题

牛客最近来了一个新员工Fish,每天早晨总是会拿着一本英文杂志,写些句子在本子上。同事Cat对Fish写的内容颇感兴趣,有一天他向Fish借来翻看,但却读不懂它的意思。例如,“student. a am I”。后来才意识到,这家伙原来把句子单词的顺序翻转了,正确的句子应该是“I am a student.”。Cat对一一的翻转这些单词顺序可不在行,你能帮助他么?

思路:先切割单词,后反转句子。注意意外情况就是句子是” “

1
2
def ReverseSentence(self, s):
return ' '.join(s.strip().split(' ')[::-1]) or s

2. 求等差数列问题

求1+2+3+…+n,要求不能使用乘除法、for、while、if、else、switch、case等关键字及条件判断语句(A?B:C)。

思路:这道题显然就是要用递归

1
2
def Sum_Solution(self, n):
return 0 if n < 1 else n + self.Sum_Solution(n - 1)

3. 全排列和子集问题

3.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
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
input: {1, 2}
output: {}, {1}, {2}, {1, 2}
{}
↙ ↘
{1} {2}
{1,2}
public List<List<Integer>> subsets(int[] nums) {
List<List<Integer>> result = new ArrayList<List<Integer>>();
if(nums == null || nums.length == 0){
return result;
}
List<Integer> list = new ArrayList<Integer>();
Arrays.sort(nums);
subsetsHelper(result, list, nums, 0);
return result;
}
//这就是搜索的模板,先加一个数,然后撤销数
private void subsetsHelper(List<List<Integer>> result,
List<Integer> list, int[] nums, int pos){
result.add(new ArrayList<Integer>(list));
for(int i = pos; i < nums.length; i++){
*********************************************
* if(i != pos && num[i] == num[i - 1]{ *
* cintinues; *
* } *
* *
* pos i *
* ↓ ↓ *
* 1, 1th_2, 2th_2, 3th_2 *
* ↑ *
* *
* {1, 1th_2} = {1, 2th_2} *
* *
* 只改动上面这句话就可以解决带重复的问题 *
* 复杂度,有n个数,O(2^n) *
*********************************************
list.add(nums[i]);
subsetsHelper(result, list, nums, i+1);
list.remove(list.size() - 1); //回溯,每次把尝试加的那个数撤销掉,尝试加另外一个数。比如从空集出发,先加1,然后删掉1,尝试加2
}
}

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
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
public List<List<Integer>> permute(int[] nums) {
List<List<Integer>> results = new ArrayList();
if(nums == null || nums.length == 0){
return results;
}
List<Integer> list = new ArrayList<Integer>();
Helper(results, list, nums);
return results;
}
// 不带重复的数
private void Helper(List<List<Integer>> results, List<Integer> list, int[] nums)
if(list.size() == nums.length){
results.add(new ArrayList<Integer>(list));
return;
}
for(int i = 0; i < nums.length; i++){
if(list.contains(nums[i])){
continue;
}
list.add(nums[i]);
Helper(results, list, nums);
list.remove(list.size()-1);
}
}
//带重复的数
private void Helper(List<List<Integer>> results, int[] nums,
int[] visited, List<Integer> list){
if(list.size() == nums.length){
results.add(new ArrayList<Integer>(list));
return ; //排列一次结束要返回
}
for(int i = 0; i < nums.length; i++){
if (visited[i] == 1 || (i != 0 && nums[i] == nums[i-1] && visited[i-1] == 0)){
continue;
}
visited[i] = 1;
list.add(nums[i]);
Helper(results, nums, visited, list);
list.remove(list.size() - 1);
visited[i] = 0;
}
}

链表总结

1. 单链表反转问题

1
2
3
4
5
6
7
8
9
10
11
# python 描述
def ReverseList(self, pHead):
# write code here
prev = None
while pHead:
temp = pHead.next
pHead.next = prev
prev = pHead
pHead = temp
return prev
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
//java 描述
public class Solution {
public ListNode ReverseList(ListNode head) {
ListNode prev = null;
ListNode temp = null;
while(head != null){
temp = head.next;
head.next = prev;
prev = head;
head = temp;
}
return prev;
}
}

单链表反转问题,一个循环的流程就是下图所描述的那样。从代码中也可以看到写法也是有规律的,四行赋值表达式在写法上有一个循环,记住这个规律,可以避免写错误,也比较好记。 注意:最后返回的是 prev

图1、链表反转 图2、代码规律

2. 合并两个有序链表

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
# python 描述
def Merge(self, pHead1, pHead2):
# write code here
dummy = ListNode(-1)
lastNode = dummy
while pHead1 != None and pHead2 != None:
if pHead1.val < pHead2.val:
lastNode.next = pHead1
pHead1 = pHead1.next
else:
lastNode.next = pHead2
pHead2 = pHead2.next
lastNode = lastNode.next
if pHead1 != None:
lastNode.next = pHead1
else:
lastNode.next = pHead2
return dummy.next
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
// java描述
public ListNode Merge(ListNode list1,ListNode list2) {
ListNode dummy = new ListNode(-1);
ListNode lastNode = dummy;
while(list1 != null && list2 != null){
if(list1.val < list2.val){
lastNode.next = list1;
list1 = list1.next;
}else{
lastNode.next = list2;
list2 = list2.next;
}
lastNode = lastNode.next;
}
if(list1 != null){
lastNode.next = list1;
}else{
lastNode.next = list2;
}
return dummy.next;
}

思路:在链表问题中,使用一个dummyNode是很好的办法。过程分析如下图:

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
list1
1 --> 3 --> 5 --> 7
list2
2 --> 4
初始化: listNode(dummy) --> null
判断: 1 < 2 ? 取1 :取2 <------|
|
listNode |
↓ |
添加结点: dummy --> 1 |
|循环
list1 |
↓ |
3 --> 5 --> 7 |
|
list2 |
↓ |
2 --> 4 --------->|
nextNode
拼接表尾: dummy --> 1 --> 2 --> 3 --> 4
list1 |
↓ |
5<------------------------|
list2
null

3. 复杂链表的赋值

问题描述:输入一个复杂链表(每个节点中有节点值,以及两个指针,一个指向下一个节点,另一个特殊指针指向任意一个节点),返回结果为复制后复杂链表的head。

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
# 递归法
def Clone(self, pHead):
# write code here
if pHead == None:
return None
newNode = RandomListNode(pHead.label)
newNode.random = pHead.random
newNode.next = self.Clone(pHead.next)
return newNode
# 先复制后拆分
def Clone(self, pHead):
# write code here
if pHead == None:
return None
pCur = pHead
while pCur != None:
newNode = RandomListNode(pCur.label)
newNode.next = pCur.next
pCur.next = newNode
pCur = newNode.next
pCur = pHead
while pCur != None:
if pCur.random != None:
pCur.next.random = pCur.random.next
pCur = pCur.next.next
head = pHead.next
tmp = head
pCur = pHead
while pCur.next != None:
tmp = pCur.next
pCur.next = tmp.next
pCur = tmp
return head

4. 删除链表中重复结点

4.1 假如链表是有序的

1 –> 2 –> 3 –> 3–> 4–> 4–> 5

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
#三指针法
def deleteDuplication(self, pHead):
if pHead == None:
return None
dummy = lastNode = ListNode(-1)
lastNode.next = pHead #指向当前结点的前一个结点
p = pHead #指向当前结点
q = p.next #指向下一个结点
while q != None:
if p.val != q.val: #当前结点和后面那个结点不相等,则三个指针都往后移
lastNode = p
p = q
q = q.next
continue
while p.val == q.val and q.next != None: #当前结点和下一个结点相等,写一个节点指针后移,直到找到不相等的点
q = q.next
if p.val == q.val: #没找到下一个不相等的点,说明从p结点到链表末尾都是一样的数
lastNode.next = None
break
else: #跳过中间相等数的结点,上一个结点指针指向找到的不相等的第一个点
p = q
lastNode.next = p
q = q.next
return dummy.next

4.2 假如链表是无序的

1 –> 2 –> 3 –> 4 –>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
def deleteDuplication(self, pHead):
#建立一个字典统计每个值的频率
curNode = pHead
resDict = {}
while curNode != None:
if not resDict.has_key(curNode.val):
resDict[curNode.val] = 1
else:
resDict[curNode.val] += 1
curNode = curNode.next
#把字典中不重复的数取出来
resList = []
for key, value in resDict.items():
if value == 1:
resList.append(key)
#建立链表
dummy = ListNode(-1)
curNode = dummy
for num in resList:
node = ListNode(num)
curNode.next = node
curNode = curNode.next
return dummy.next

5. 找出两个链表中的第一个公共结点

5.1 借助栈

思路:分别把两个链表中的结点压入栈中,然后一对一对比较并弹出栈,直到第一对不一样的出现,那么公共结点就是上一对。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
def FindFirstCommonNode(self, pHead1, pHead2):
# write code here
list1, list2 = [],[]
while pHead1 != None:
list1.append(pHead1)
pHead1 = pHead1.next
while pHead2 != None:
list2.append(pHead2)
pHead2 = pHead2.next
tmp = None
while len(list1) != 0 and len(list2) != 0 and list1[-1] == list2[-1]:
a = list1.pop()
tmp = list2.pop()
return tmp

5.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
public static boolean HaveCross(Node head1, Node head2){
int len1 = 0;
int len2 = 0;
Node temp1 = head1;
Node temp2 = head2;
while (temp1.next != null){
len1 += 1;
temp1 = temp1.next;
}
while (temp2.next != null){
len2 += 1;
temp2 = temp2.next;
}
int len_diff = Math.abs(len1 - len2);
Node temp_long = null;
Node temp_short = null;
if(len1 >= len2){
temp_long = head1;
temp_short = head2;
}else{
temp_long = head2;
temp_short = head1;
}
for(int i = 0; i < len_diff; i++){
temp_long = temp_long.next;
}
while (temp_long.next != null){
if(temp_long.equals(temp_short)){
return true;
}else{
temp_long = temp_long.next;
temp_short = temp_short.next;
}
}
return false;
}

5.3 构造环形链表

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
public static boolean HaveCross(Node head1, Node head2){
int len2 = 0;
Node temp2 = head2;
while (temp2.next != null){
len2 += 1;
temp2 = temp2.next;
}
temp2.next = head1;
Node fast = head2;
Node slow = head2;
while (fast.next.next != null && slow.next != null){
fast = fast.next.next;
slow = slow.next;
if(fast.equals(slow)){
return true;
}
}
return false;

6. 一个链表中含有环,请找出该链表的环的入口结点

思路:快慢指针判断有环,把相遇之后的快指针移到链表头,都变为慢指针。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
public ListNode EntryNodeOfLoop(ListNode pHead){
        ListNode fast = pHead;
        ListNode slow = pHead;
        while(fast != null && fast.next !=null){
            fast = fast.next.next;
            slow = slow.next;
            if(fast == slow)
                break;
        }
        if(fast == null || fast.next == null)
            return null;
        fast = pHead;
        while(fast != slow){
            fast = fast.next;
            slow = slow.next;
        }
        return fast;
    }

快速排序

快速排序算法

算法思路:快速排序目前我见到两种版本,两种版本的区别就是哨兵位置的不同,有人喜欢使用数组的最后一位做哨兵位置,有人喜欢用数组的中间位置作为哨兵。
下面这份代码是以中间位置作为哨兵。主要思路就是,使用两个指针,分别从最左边和最右边往中间滑,分别找到左边的第一个大于哨兵的数和右边第一个小于哨兵
的数,然后交换这两个数的位置。然后继续滑动两个指针,一趟过完以后,会发现,哨兵左边的数都小于哨兵,哨兵右边的数都大于哨兵。于是就可以用递归分别继续
对左右两边的两段进行同样思路的快排。

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
static int[] numbers = {4, 10,14,11,17,8,13,15,12,2,6,9};
private static void quicksort(int low, int high) {
int i = low, j = high;
int pivot = numbers[low + (high-low)/2];
while (i <= j) {
while (numbers[i] < pivot) {
i++;
}
while (numbers[j] > pivot) {
j--;
}
if (i <= j) {
exchange(i, j);
i++;
j--;
}
}
if (low < j)
quicksort(low, j);
if (i < high)
quicksort(i, high);
}
private static void exchange(int i, int j) {
int temp = numbers[i];
numbers[i] = numbers[j];
numbers[j] = temp;
}

JVM简介

1. JVM的体系架构

举个栗子:JVM就像是一台柴油机,Java就像是柴油,JVM需要Java才能跑起来。柴油可以在汽车、飞机、坦克中使用,这就是跨平台特性。

Java编译器针对不同的平台将Java文件源文件编译成字节码,JVM把字节码文件中的命令翻译成不同平台的机器码。
Java技术体系可以分为四个平台:

  1. Java Card: 支持小程序,用于智能卡等
  2. Java ME: 支持Java运行于移动终端, Android
  3. Java SE: 支持桌面级应用
  4. Java EE: 支持多层架构的企业级应用
图1、Java体系结构

从上面这张图中我可以看到JDK与JRE的区别与联系:
JRE:Java Runtime Environment
JDK: Java Development Kit
顾名思义,JRE是Java程序运行时必须的环境,包含了Java虚拟机和Java类库,是运行Java编程程序的环境,是给想运行Java程序的人使用的。
JDK是Java开发工具包,它包含了JRE和Java程序开发所需要的工具包,是提供给程序员使用的。

Java的物理结构:
图2、Java物理结构

Java编译和执行的过程

Java的编译过程由Java编译器执行,Java的运行过程由JVM执行引擎执行。

Java编译

Java执行

Java的编译和执行过程主要包含三个机制

  1. Java源码编译机制
  2. 类加载机制
  3. 类执行机制

Java源码编译机制

Java源码编译机制由一下三个过程组成:

  1. 分析和输入到符号表
  2. 注解处理
  3. 语法分析和生成class文件

流程图如下图所示:

1
2
3
4
5
6
7
8
9
10
11
*.java --------> 分析和注入 ---------> 注解处理 ---------> 语法分析 ---------> *.class
| | |
|______________________________________| |
|
---------------------------------------------|
\1. 结构信息。包含class文件结构版本号各部分信息;\
\2. 元数据。声明与常量的信息,类、超类、接口的声 \
\ 明信息、域和方法声明的信息和常量池; \
\3. 方法信息。语句和源码表达式的信息。 \
\---------------------------------------------

类加载机制

JVM类的加载是通过ClassLoader及其子类来完成的,类的层次关系和记载顺序可以用一下图来进行描述。

类加载机制

BootStrap ClassLoader

负责加载$JAVA_HOME中jre/lib/rt.jar里所有的 class,由 C++ 实现,不是 ClassLoader 子类。

Extension ClassLoader

负责加载Java平台中的扩展功能的一些jar包

App ClassLoader

负责加载classpath中指定的jar包及目录中的class

Custom ClassLoader

应用程序根据自身需要定义的ClassLoader。

加载过程会先检查自底向上检测类是否被加载,而检查过程是自顶向下的。

类执行机制

JVM执行字节码,线程创建,产生计数器(PC)和栈(Stack),程序计数器存放下一条指令在方法内的偏移量,栈中存放一个个栈帧。每个栈帧对应着每个方法的每次调用,而栈帧又是有局部变量和操作数栈两部分组成,局部变量区用于存放方法中的局部变量和参数,操作数栈中用于存放方法执行过程中产生的中间结果。
栈的结构如下图所示:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
------------------------
| |
---------------------- |
| | |
--------------------- | |
| ------------- | | |
| | 局部变量区 | | | |
| ------------- | | |
| | | |
| ------------- | | |
| | 操作数栈 | | |------
| ------------- | |
| |-----
| 栈帧 |
---------------------