Intro

Hi, this is a wiki for cs related knowledge. This project is at a very early stage.

Part I. Algorithm

The basic concepts for algorithm learning.

Data Sturcutre

Array
LinkedList
Stack
Queue
HashTable
Tree

Algorithm Thoughts

Recursive
Backtracking
Divide and Conquer
Sort
Search
Greedy
Dynamic Programming

Part II. Software Development

Six subjects for software developing.

Programming Language
Computer Network
Database
Web Development
Distributed System

Part III. System Design

This part will introduce some software principles by small projects.

一、算法

基础数据结构

Array
LinkedList
Stack
Queue
HashTable
Tree

基础算法思想

Recursive
Backtracking
Divide and Conquer
Sort
Search
Greedy
Dynamic Programming

进阶算法

ACM 自动机
匈牙利算法
A*
巴克斯范式解释
l z78 解压算法

数组 Array

一、数组的定义

数组是基础的线性表数据结构，当我们声明一个数组时，计算机在内存中开辟了一段连续的内存用于存储相同类型的数据。

定义中「连续内存空间」和「相同类型的数据结构」这两个特点，使数组拥有随机访问这一特性。
但同时也让数组的很多操作变得低效，例如在数组中插入或删除一个数据，为了维持其连续性的特点，则需要做数据搬移的工作。

二、数组的操作

（1）数组的基本操作

插入 Insert：在数组中插入一个新元素。
删除 Delete：在数组中删除一个已有的元素。
读取（随机访问） Read：读取数组中某个下标的值。
查找 Find：查找数组中值为目标值的元素，并返回其下标。

（2）寻址操作

数组支持以索引访问元素以及对数据进行插入和删除的操作。以索引来访问元素，是其他操作的基础，系统会给每个内存单元分配一个地址，再通过地址来访问内存中的元素。当需要随机访问数组中的某个元素时，会通过寻址公式计算出元素存储的内存地址，由此实现对该元素的访问。

a[i]_address = base_address + i * data_type_size //寻址公式

其中 data_type_size 表示每个元素的大小，例如数组中存储的是整形元素，那么这个值就是 4 字节。

（3）操作的时间复杂度

插入：O(N)，如果是添加到末尾，那只需要 O(1) 的步数，但是如果添加到数组间，异或数组起始位置，那么还涉及到后面元素的移动，因此极限情况下需要的步数是 N+1。
删除：O(N)，删除一个元素也会涉及到元素的移动，因此极限情况下需要的步数是 N+1。
读取：O(1)，计算机知道数组第一个元素的内存地址，以及数组的个数，因此只需要一步就可以得到某个下标的元素。
查找：O(N)，计算机需要先访问到下标后，才能得到对应元素，当查找的元素在最后一个位置时，查找需要的步数是 N +1。

（4）数组操作的优化

优化一：删除操作的优化与 JVM 垃圾回收算法

如同前面介绍的，数组的删除操作会涉及元素的搬运，这也是最耗费时间的操作。
如果当我们需要删除多个元素时，为了避免没被删除的元素搬运多次，我们可以考虑将记录下已经删除的数据。每次的删除操作并不是真正地搬运数据，只是记录数据已经被删除。当数组没有更多的空间存储数据时，我们再触发一次真正的删除操作没这样就大大减少了数据的搬运。
同时这也是 JVM 垃圾回收算法中的核心思想。

优化二：插入操作的优化

如果数组中的元素并非有序，只是作为一个存储数据的集合，那么可以利用一个处理技巧来避免大规模的搬移数据。
例如要在位置 K 插入一个新元素，那么可以讲 K 位置的元素搬移到数组的最后，把新数据直接放到原来 K 的位置。

优化三：对有序数组的优化

当数组这个基本数据结构升级到有序的情况之后，数组的一个操作会有一些变化。读取，添加，删除的操作和普通数组无异，然而查找的操作有了很大的提升，这里我们可以引出二分查找这个算法。
二分查找算法利用有序数组的特性，可以有效降低查找这个操作的时间复杂度：O(N) -> O(logN)。
需对二分查找算法的基本代码非常熟悉

三、常见的数组问题

（1）数组越界问题

但并非所有的语言都像 C 一样，把数组越界检查的工作丢给程序员来做，像 Java 本身就会做越界检查，比如下面这几行 Java 代码，就会抛出 java.lang.ArrayIndexOutOfBoundsException。

int[] a = new int[3]; 
a[3] = 10; // 越界操作

（2）容器的使用

ArrayList 的使用

ArrayList 可以将很多数组操作的细节封装起来，例如前面介绍的数组插入、删除数据时，需要搬移其他元素。
ArrayList 支持动态扩容，实现了每次自动扩容 1.5 倍的底层逻辑。
虽然支持动态扩容，但操作仍然是耗时的，所以如果能事先确定需要存储的数据大小，可以在创建 ArrayList 时事先指定好数据大小。

List<String> list = new ArrayList<>(10); // initial capacity

Array 和 ArrayList 的选择对比

数组本身在定义的时候需要预先指定大小，并且由于需要分配连续内存的原因，当起初我们申请了大小为10 的数组，当第 11 个元素需要存储到数组时，我们就需要重新分配一块更大的空间，将原来的数据复制过去，再将新数据插入。
ArrayList 无法存储基本类型，比如 int、long，需要封装为 Integer、Long 类，而 Autoboxing、Unboxing 都会有性能开销，如果是特别底层的开发，例如网络框架，这时候使用数组就有性能优势。
多维数组：选择数组会比容器更加直观。Object[][] array 会比ArrayList<ArrayList<Object> array更加直观。
事先知道数据大小并且对数据的操作特别简单时，数组会更加合适。
实际业务开发，首选 ArrayList，方便使用易维护。

四、相关应用及算法题

（1）二分查找

题目描述

给定一个 n 个元素有序的（升序）整型数组 nums 和一个目标值 target ，写一个函数搜索 nums 中的 target，如果目标值存在返回下标，否则返回 -1。

链接：

Q704 二分查找

解题思路

利用有序数组的特性和双指针，实现每一轮操作都将目标数组的元素数量减半。

代码实现

class Solution {
		public int search(int[] nums, int target) {
        int n = nums.length;
        int l = 0;
        int r = n - 1;
        while (l <= r) {
            int mid = l + (r - l) / 2;
            if (nums[mid] == target) {
                return mid;
            }
            if (nums[mid] < target) {
                l = mid + 1;
            } else {
                r = mid - 1;
            }
        }
        return -1;
    }
}

（2）合并有序数组

题目描述

实现两个有序数组合并为一个有序数组

Q88 合并有序数组

解题思路

由于题目要求合并两个数组的元素到第一个数组中，可以从后往前处理，来避免额外的保存。注意边界条件的处理。

代码实现

class Solution {
    public void merge(int[] nums1, int m, int[] nums2, int n) {
        int index = m + n - 1;
        int i = m - 1;
        int j = n - 1;

        while (i >= 0 || j >= 0) {
            if (i < 0) {
                nums1[index--] = nums2[j--];
            } else if (j < 0) {
                nums1[index--] = nums1[i--];
            } else if (nums1[i] <= nums2[j]) {
                nums1[index--] = nums2[j--];
            } else {
                nums1[index--] = nums1[i--];
            }
        }
    }
}

（3）移动零

题目描述

给定一个数组 nums，编写一个函数将所有 0 移动到数组的末尾，同时保持非零元素的相对顺序。

请注意 ，必须在不复制数组的情况下原地对数组进行操作。

Q283 移动零

解题思路

先通过一次循环把非 0 元素放到数组前面，后面再将数组空余的位置补充数字 0 即可。

从这题我们可以得到一种解题方向，就是可以从题目示意的相反角度来考虑问题。

代码实现

class Solution {
    public void moveZeroes(int[] nums) {

        int index = 0;
        for (int num : nums) {
            if (num != 0) {
                nums[index++] = num;
            }
        }
        while (index < nums.length) {
            nums[index++] = 0;
        }

    }
}

（4）只出现一次的数字

题目描述

给定一个非空整数数组，除了某个元素只出现一次以外，其余每个元素均出现两次。找出那个只出现了一次的元素。说明：你的算法应该具有线性时间复杂度。你可以不使用额外空间来实现吗？

Q136 只出现一次的数字

解题思路

运算符中的亦或运算，具有一下特性

0 ^ 任意数字= 数字本身。
两个数字相等时的亦或操作，结果为0；两个值不相等时，结果为 1。
亦或操作满足交换定律。

代码实现

class Solution {
    public int singleNumber(int[] nums) {
        
        int result =0;
        for (int num : nums) {
            result ^= num;
        }
        return result;
    }
}

（5）多数元素

题目描述

给定一个大小为 n 的数组，找到其中的多数元素。多数元素是指在数组中出现次数大于 ⌊ n/2 ⌋ 的元素。你可以假设数组是非空的，并且给定的数组总是存在多数元素。

Q169 多数元素

解题思路

代码实现

class Solution {
    public int majorityElement(int[] nums) {

        int major = nums[0];
        int cnt = 1;
        
        for (int i = 1; i < nums.length; i++) {
            if (cnt == 0) {
                major = nums[i];
            }
            if (nums[i] == major) {
                cnt++;
            } else {
                cnt--;
            } 
        }
        
        return major;
    }
}

（6）删除排序数组的重复项

题目描述

给你一个升序排列的数组 nums ，请你原地删除重复出现的元素，使每个元素只出现一次，返回删除后数组的新长度。元素的相对顺序应该保持一致。

由于在某些语言中不能改变数组的长度，所以必须将结果放在数组nums的第一部分。更规范地说，如果在删除重复项之后有 k 个元素，那么 nums 的前 k 个元素应该保存最终结果。

将最终结果插入 nums 的前 k 个位置后返回 k 。

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

Q26 Remove Duplicates from Sorted Array

解题思路

双指针，我们并不真正的去删除某个元素，而是用下标 i 来统计不同数字的个数。

代码实现

class Solution {
    public int removeDuplicates(int[] nums) {

        int i = 1;
        for (int j = 1; j < nums.length ; j++) {
            if (nums[j] != nums[j - 1]) {
                nums[i++] = nums[j];
            }
        }
        return i  ;
    }
}

（7）加一

题目描述

给定一个由整数组成的非空数组所表示的非负整数，在该数的基础上加一。最高位数字存放在数组的首位，数组中每个元素只存储单个数字。

你可以假设除了整数 0 之外，这个整数不会以零开头。

Q66 Plus One

解题思路

我们从后往前遍历，在循环中判断是直接加一还是处理进位的情况。如果在循环中没有返回结果，则说明是 99，999 等这类特殊数字，则单独处理。

代码实现

class Solution {
    public int[] plusOne(int[] digits) {

        int n = digits.length;
        for (int i = n - 1; i >= 0; i--) {
            if (digits[i] < 9) {
                digits[i] = digits[i] + 1;
                return digits;
            }
            digits[i] = 0;
        }
        
        digits = new int[n + 1];
        digits[0] = 1;
        return digits;
    }
}

（8）三数之和

题目描述

给你一个包含 n 个整数的数组 nums，判断 nums 中是否存在三个元素 a，b，c ，使得 a + b + c = 0 ？请你找出所有和为 0 且不重复的三元组。（注意：答案中不可以包含重复的三元组）

Q15 3 Sum

解题思路

代码稍显复杂，实际逻辑很简单，先对数组做一次排序，然后用二分查找的思路做比较即可。

代码实现

    /**
     * Time: O(N^2): 排序是 N*logN，循环内是 N^2，结合起来取最大值，结果即 O(N^2)
     * Space: O(1)
     */
    public static List<List<Integer>> threeSumWithSorted(int[] nums) {

        if (nums == null || nums.length == 0) {
            return new ArrayList<>();
        }

        //Time: O(N*logN)
        Arrays.sort(nums);
        List<List<Integer>> result = new ArrayList<>();
        int index = 0;

        // Time: O(N^2)
        while (index < nums.length - 2) {
            // 如果第一个数就 > 0， 那后面的数都大于 0 了，直接 break。
            if (nums[index] > 0) {
                break;
            }
            // 不能包含重复的三元组，所以如果当前 index 的和上一个 index 值相同时，跳过当前循环
            if (index >= 1 && nums[index] == nums[index - 1]) {
                index++;
                continue;
            }

            int dif = -nums[index];
            int l = index + 1;
            int r = nums.length - 1;

            while (l < r) {
                int sum = nums[l] + nums[r];
                if (sum == dif) {
                    result.add(Arrays.asList(nums[index], nums[l], nums[r]));
                    l++;
                    r--;
                    // 下面两个循环，同样是为了处理「不能包含重复三元素」的问题
                    while (l < r && nums[l] == nums[l - 1]) {
                        l++;
                    }
                    while (l < r && nums[r] == nums[r + 1]) {
                        r--;
                    }
                } else if (sum < dif) {
                    l++;
                } else {
                    r--;
                }
            }
            index++;
        }

        return result;
    }

（9）数组中第 K 大的元素

题目描述

给定整数数组 nums 和整数 k，请返回数组中第 k 个最大的元素。

请注意，你需要找的是数组排序后的第 k 个最大的元素，而不是第 k 个不同的元素。

你必须设计并实现时间复杂度为 O(n) 的算法解决此问题。

Q215 Kth Largest Element in An Array

解题思路

可以使用小根堆来解决。

代码实现

class Solution {
    public int findKthLargest(int[] nums, int k) {
        PriorityQueue<Integer> pq = new PriorityQueue<>();
        for (int num : nums) {
            pq.offer(num);
            if (pq.size() > k) {
                pq.poll();
            }
        }
        
        return pq.peek();
    }
}

链表 LinkedList

循环链表的特点是指尾节点的指针指向链表的头节点
双向链表则是在工作中更常用的结构，在这个结构中，节点不仅存储了后继指针 next，还有一个指向前面节点的 prev。
双向循环链表则结合了前面两者的特点。

由于双向链表是在实际工作中应用更多的结构，我们更加深入的介绍下这个结构。

双向链表的特点

存储同样多的数据，双向链表会比单项链表占用更多的内存空间。
相比单向链表，更高效的可操作性。
- 这里的更加高效是指：在实际情况中，链表的删除并不是理论中的 O(1)，例如两个删除场景：1. 删除结点中“值等于某个给定值”的结点；2. 删除给定指针指向的结点。
- 在场景1中，我们必须遍历到某个节点，判断到该节点的值之后，才能真正的删除操作，而遍历查找的操作时间复杂度是O(N)，再结合删除操作O(1)，实际的时间复杂度是O(N)。
- 在场景2中，我们已经找到了要删除的结点，但是删除某个结点 q 需要知道其前驱结点，而单链表并不支持直接获取前驱结点，所以，为了找到前驱结点，我们还是要从头结点开始遍历链表，直到 p->next=q，说明 p 是 q 的前驱结点。
- 同理，如果我们希望在链表的某个指定结点前面插入一个结点，双向链表比单链表有很大的优势。双向链表可以在 O(1) 时间复杂度搞定，而单向链表需要 O(n) 的时间复杂度。
- 除了插入、删除操作有优势之外，对于一个有序链表，双向链表的按值查询的效率也要比单链表高一些。因为，我们可以记录上次查找的位置 p，每次查询时，根据要查找的值与 p 的大小关系，决定是往前还是往后查找，所以平均只需要查找一半的数据。
上面的几点具体情景，也解释了为什么在实际的软件开发中，双向链表尽管消耗了更多的内存，但还是比单链表的应用更加广泛的原因。
Java 语言中的 LinkedHashMap 便是用到了双向链表。

HashMap<Integer,Integer> map = new LinkedHashMap<>();

（3）链表的操作

基本操作

插入 Insert： O(1)
删除 Delete：O(1)
随机访问 Read：O(N)
查找 Find：O(N)

（4）链表与数组的比较

数组和链表是两种截然不同的内存组织方式。但是数组和链表的对比，并不能局限于时间复杂度。我们实际的开发中，要根据具体情况，权衡究竟是选择数组还是链表。
数组简单易用，在实现上使用的是连续的内存空间，可以借助 CPU 的缓存机制，预读数组中的数据，所以访问效率更高。而链表在内存中并不是连续存储，所以对 CPU 缓存不友好，没办法有效预读。
数组的缺点是大小固定，一经声明就要占用整块连续内存空间。如果声明的数组过大，系统可能没有足够的连续内存空间分配给它，导致“内存不足（out of memory）”。如果声明的数组过小，则可能出现不够用的情况。这时只能再申请一个更大的内存空间，把原数组拷贝进去，非常费时。
- ArrayList 虽然支持自动扩容，但是扩容是会出现数据拷贝，而数据拷贝是非常耗时的。
- 如果你的代码对内存的使用非常苛刻，那数组就更适合你
链表本身没有大小的限制，天然地支持动态扩容，这也是它与数组最大的区别。
- 因为链表中的每个结点都需要消耗额外的存储空间去存储一份指向下一个结点的指针，所以内存消耗会更多。
- 而且，对链表进行频繁的插入、删除操作，还会导致频繁的内存申请和释放，容易造成内存碎片，如果是 Java 语言，就有可能会导致频繁的 GC（Garbage Collection，垃圾回收）。

（5）空间换时间的设计思想

在上面两个数据结构的比较中，有个更加重要的知识点需要掌握，即「空间换时间」的设计思想。

内存空间充足的时候，如果我们更加追求代码的执行速度，我们就可以选择空间复杂度相对较高、但时间复杂度相对很低的算法或者数据结构。相反，如果内存比较紧缺，比如代码跑在手机或者单片机上，这个时候，就要反过来用时间换空间的设计思路。
缓存实际上就是利用了空间换时间的设计思想。如果我们把数据存储在硬盘上，会比较节省内存，但每次查找数据都要询问一次硬盘，会比较慢。但如果我们通过缓存技术，事先将数据加载在内存中，虽然会比较耗费内存空间，但是每次数据查询的速度就大大提高了。
总结一下，对于执行较慢的程序，可以通过消耗更多的内存（空间换时间）来进行优化；而消耗过多内存的程序，可以通过消耗更多的时间（时间换空间）来降低内存的消耗。

class Solution {
  // Iteratice
    public ListNode reverseList(ListNode head) {  
        ListNode pre = null;
        
        while (head != null) {
            ListNode next = head.next;
            head.next = pre;
            pre = head;
            head = next;
        }
        return pre;
    }
  // Recursive
      public ListNode reverse(ListNode head) {
        if (head == null || head.next == null) {
            return head;
        }
        ListNode last = reverse(head.next);
        head.next.next = head;
        head.next = null;
        return last;
    }
}

class Solution {
    public ListNode mergeTwoLists(ListNode list1, ListNode list2) {
        ListNode pre = new ListNode();
        ListNode head = pre;

        while (list1 != null && list2 != null) {
            if (list1.val <= list2.val) {
                head.next = list1;
                list1 = list1.next;
            } else {
                head.next = list2;
                list2 = list2.next;
            }
            head = head.next;
        }
      
        head.next = list1 == null ? list2 : list1;  
        return pre.next;
    }
}

（3）链表的中间节点

题目描述

给定一个头结点为 head 的非空单链表，返回链表的中间结点。

如果有两个中间结点，则返回第二个中间结点。

Q876 链表的中间节点

解题思路

使用双指针的方法解决。

代码实现

class Solution {
    public ListNode middleNode(ListNode head) {
        ListNode slow = head;
        ListNode fast = head;
        while (fast != null && fast.next != null) {
            fast = fast.next.next;
            slow = slow.next;
        }
        return slow;
    }
}

class Solution {
    public ListNode removeNthFromEnd(ListNode head, int n) {
				ListNode pre = new ListNode(0, head);
        ListNode slow = pre;
        ListNode fast = head;

        for (int i = 0; i < n; i++) {
            fast = fast.next;
        }
        while (fast != null) {
            fast = fast.next;
            slow = slow.next;
        }
        slow.next = slow.next.next;

        return pre.next;
    }
}

class Solution {
    public boolean hasCycle(ListNode head) {
        if (head == null) {
            return false;
        }
        ListNode fast = head;
        ListNode slow = head;
        while (fast != null && fast.next !=null) {
            fast = fast.next.next;
            slow = slow.next;
            if (fast == slow) {
                return true;
            }
        }
        return false;
    }
}