相交链表

相交链表

解题思路

首先计算两个链表的长度len1和len2，对于较长的链表，其指针先向后移动|len1-len2|步，接着两个链表的指针同步向后移动，当两个指针相等时，说明到达了相交链表的第一个节点。

合并两个有序链表

合并两个有序链表

解题思路

利用归并的思想，两个指针分别指向两个有序链表，不断将两个指针指向的节点较小者加入到新链表的结尾。

两数之和

两数之和

解题思路

1. 暴力破解，遍历数组中所有的两数之和，得到和为目标值的两个数组元素，时间复杂度达O(n^2)

2. 本题是要找到数组中的两个数，使它们的和为目标值。可以利用Hash表记录已经访问过的元素，在遍历时去查找Hash表中是否已经有访问过的元素，使得它加上当前访问元素的和为目标值。这样的算法时间复杂度为O(n)，空间复杂度为O(n)

关系型数据库

E-R (entity-relationship) 模型

E-R模型主要有三个概念：

• 实体集：一个实体集对应一张表，表中的一行（记录）对应一个实体
• 属性：对应于表的一列
• 联系集

1
2
3
4

ORM思想（Object Relational Mapping，对象关系映射）
数据库中的一个表 <---> 一个类
表中的一条数据 <---> 类的一个对象
表中的一个列 <---> 类中的一个字段（field）

数组中的第K大元素

数组中的第K个最大元素

解题思路

1. 利用快速排序的思想，对数组进行划分。则一趟划分完成后有以下情况：
   • 若枢轴最终就是第K大的元素，则直接返回
   • 若枢轴大于第K大的元素，则对枢轴元素左侧的部分进行划分
   • 若枢轴小于第K大的元素，则对枢轴元素右侧的部分进行划分

链表反转

链表反转

解题思路

1. 采用链表原地逆置的思想，设立两个指针pre和cur，初始时pre=nil, cur=head。每次循环时，都使cur和pre向后移动的同时，使得cur.Next指向pre
2. 采用头插法的思想，设立一个头节点，将原链表中的各节点依次插入到头节点后
3. 借助辅助栈实现，从前向后遍历链表并压入栈中，遍历完成后依次将栈中元素弹出构建新链表（空间辅助度达O(n)）

基本介绍

os.File封装所有的文件相关操作，File是一个结构体。File代表一个打开文件的对象。

文件基本操作

打开/关闭文件

os.Open

1
2
3
4
5
6
7

// 打开文件
// Open打开一个文件用于读取。如果操作成功，返回的文件对象的方法可用于读取数据。如果出错，错误底层类型是*PathError。
func Open(name string) (file *File, err error)

// 关闭文件
// Close关闭文件f，使文件不能用于读写。它返回可能出现的错误。
func (f *File) Close() error

Open返回的是File结构体指针

继承

继承实现方法

在Go中，继承采用匿名结构体实现。

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

type Student struct{
    Name string
    Age int
}

type Graduate struct{
    Student  // 继承Student
    id int
}

type PostGraduates struct{
    Student  // 继承Student
    Tutor string
}