数据结构

String

1
2
3
4
5
6
7
8
9
10
11
12
13
String s1 = new String();
String s2 = "lgs";
int s2Len = s2.length();
s2.substring(4, 8); // return "ryan"
StringBuilder s3 = new StringBuilder(s2.substring(4, 8));
s3.append("bill");
String s2New = s3.toString(); // return "ryanbill"
// convert String to char array
char[] s2Char = s2.toCharArray();
// char at index 4
char ch = s2.charAt(4); // return 'r'
// find index at first
int index = s2.indexOf('r'); // return 4. if not found, return -1

Linked List - 链表

链表是线性表的一种。线性表是最基本、最简单、也是最常用的一种数据结构。线性表中数据元素之间的关系是一对一的关系，即除了第一个和最后一个数据元素之外，其它数据元素都是首尾相接的。线性表有两种存储方式，一种是顺序存储结构，另一种是链式存储结构。我们常用的数组就是一种典型的顺序存储结构。

相反，链式存储结构就是两个相邻的元素在内存中可能不是相邻的，每一个元素都有一个指针域，指针域一般是存储着到下一个元素的指针。这种存储方式的优点是定点插入和定点删除的时间复杂度为 O(1)，不会浪费太多内存，添加元素的时候才会申请内存，删除元素会释放内存。缺点是访问的时间复杂度最坏为 O(n)
顺序表的特性是随机读取，也就是访问一个元素的时间复杂度是O(1)，链式表的特性是插入和删除的时间复杂度为O(1)。
链表就是链式存储的线性表。根据指针域的不同，链表分为单向链表、双向链表、循环链表等等。

1
2
3
4
5
6
7
8
9
10
11
12
public class ListNode {
    int val;
    ListNode next;
    public ListNode(int val){
        this.val = val;
    }

    public void add(int val){
        ListNode listNode = new ListNode(val);
        next = listNode;
    }
}

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
private static ListNode reverse(ListNode head) {
    if (head.next == null)
        return head;
    ListNode reversedListNode = reverse(head.next);
    head.next.next = head;
    head.next = null;
    return reversedListNode;
}


/**
 * 反转链表
 * @param node
 */
public static void printListFromTailToHeadByReverseList(ListNode node) {
    ListNode reversedNode = reverse(node);
    while (reversedNode != null) {
        System.out.print(reversedNode.val + ",");
        reversedNode = reversedNode.next;
    }

}

#二叉树
二叉树是每个节点最多有两个子树的树结构，子树有左右之分，二叉树常被用于实现二叉查找树和二叉堆。

二叉树的第i层至多有 2^{i-1}2
​i−1
​​ 个结点；深度为k的二叉树至多有 2^k-12
​k
​​ −1 个结点；对任何一棵二叉树T，如果其终端结点数为 n_0n
​0
​​ , 度为2的结点数为 n_2n
​2
​​ , 则 n_0=n_2+1n
​0
​​ =n
​2
​​ +1。因为度为1的节点对度为0的节点数目不会有影响，而每增加一个度为2的节点总的来说则会相应增加一个度为0的节点。

一棵深度为 kk, 且有 2^k-12
​k
​​ −1 个节点称之为满二叉树；深度为 k k，有 nn 个节点的二叉树，当且仅当其每一个节点都与深度为 kk 的满二叉树中序号为 11 至 nn 的节点对应时，称之为完全二叉树。完全二叉树中重在节点标号对应

1
2
3
4
5
6
7
8
9
10
11
public class TreeNode {
    private int val;

    public TreeNode(int val){
        this.val = val;
        this.left = null;
        this.right = null;
    }
    TreeNode left,right;

}

树的遍历

从二叉树的根节点出发，节点的遍历分为三个主要步骤：对当前节点进行操作（称为“访问”节点，或者根节点）、遍历左边子节点、遍历右边子节点。访问节点顺序的不同也就形成了不同的遍历方式。需要注意的是树的遍历通常使用递归的方法进行理解和实现，在访问元素时也需要使用递归的思想去理解。实际实现中对于前序和中序遍历可尝试使用递归实现。

按照访问根元素(当前元素)的前后顺序，遍历方式可划分为如下几种：

深度优先：先访问子节点，再访问父节点，最后访问第二个子节点。根据根节点相对于左右子节点的访问先后顺序又可细分为以下三种方式。
前序(pre-order)：先根后左再右
中序(in-order)：先左后根再右
后序(post-order)：先左后右再根
广度优先：先访问根节点，沿着树的宽度遍历子节点，直到所有节点均被访问为止。
如下图所示，遍历顺序在右侧框中，红色A为根节点。使用递归和整体的思想去分析遍历顺序较为清晰。

二叉树的广度优先遍历和树的前序/中序/后序遍历不太一样，前/中/后序遍历使用递归，也就是栈的思想对二叉树进行遍历，广度优先一般使用队列的思想对二叉树进行遍历。

如果已知中序遍历和前序遍历或者后序遍历，那么就可以完全恢复出原二叉树结构。其中最为关键的是前序遍历中第一个一定是根，而后序遍历最后一个一定是根，中序遍历在得知根节点后又可进一步递归得知左右子树的根节点。但是这种方法也是有适用范围的：元素不能重复！否则无法完成定位。

Binary Search Tree - 二叉查找树

一颗二叉查找树(BST)是一颗二叉树，其中每个节点都含有一个可进行比较的键及相应的值，且每个节点的键都大于等于左子树中的任意节点的键，而小于右子树中的任意节点的键。

使用中序遍历可得到有序数组，这是二叉查找树的又一个重要特征。

二叉查找树使用的每个节点含有两个链接，它是将链表插入的灵活性和有序数组查找的高效性结合起来的高效符号表实现。

Stack - 栈

Set

1
2
3
Set<String> hash = new HashSet<String>();
hash.add("billryan");
hash.contains("billryan");

Map

图

排序

冒泡排序、选择排序、插入排序、归并排序、堆排序、桶排序、计数排序