# e-algorithm

**Repository Path**: ymcdhr/e-algorithm

## Basic Information

- **Project Name**: e-algorithm
- **Description**: 手写源码、常用数据结构与算法
- **Primary Language**: Unknown
- **License**: Not specified
- **Default Branch**: master
- **Homepage**: None
- **GVP Project**: No

## Statistics

- **Stars**: 0
- **Forks**: 0
- **Created**: 2021-08-29
- **Last Updated**: 2021-12-02

## Categories & Tags

**Categories**: Uncategorized

**Tags**: None

## README

# e-algorithm
## 常用数据结构

#### 数组、字符串
![输入图片说明](https://images.gitee.com/uploads/images/2021/0904/161623_429db0e0_9130428.png "屏幕截图.png")

1. 例：倒叙数组或者字符串
- 双指针解法（最优） => 不占用额外空间
- 栈 => 占用额外空间

2. 例：[有效的字母易位词](https://leetcode-cn.com/problems/valid-anagram/)
- 哈希 MAP 存储字符出现次数
- 考虑 unicode 字符

#### 链表（要画图更好解题）
![输入图片说明](https://images.gitee.com/uploads/images/2021/0904/162255_c39eeda1_9130428.png "屏幕截图.png")

1. 利用快慢指针：
- 例：链表的翻转：利用三个指针

2. 构建一个虚假的（新的）链表头
- 例：两个排序链表，进行整合
- 例：将链表的楸树按照原定顺序分离，生成前半部分为奇数，后半部分为偶数的链表
- 例：[2 个一组翻转链表](https://leetcode-cn.com/problems/swap-nodes-in-pairs/submissions/)
- （1）循环方案
```js
// 使用循环指针，三个指针
var swapPairs = function(head) {
    if(head && head.next){
        let node = head
        let pre = null
        let newHead = null
        while(node && node.next){
            if(!newHead) newHead = node.next
            if(pre) pre.next = node.next

            const temp = node.next.next
            node.next.next = node
            node.next = temp

            pre = node
            node = node.next
        }

        return newHead
    }
    return head
};
```
- （2）递归方案
```js
var swapPairs = function(head) {
    if(head && head.next){
        let newHead = head.next
        const thrirdNode =  swapPairs(head.next.next)

        head.next.next = head
        head.next = thrirdNode

        return newHead
    }

    return head
};
```

- 例：[k 个一组翻转链表](https://leetcode-cn.com/problems/reverse-nodes-in-k-group/)
```
// 反转链表 + 递归写法
var reverseKGroup = function(head, k) {
    const isLonger = (node, k)=>{
        let len = 0
        let pre = null
        while(node && len<k){
            pre = node
            node = node.next
            len ++
        }
        if(len < k)
            return null
        
        return pre
    }

    // 链表长度小于k的情况，保持链表不变
    const reverseList = (node, k) => {
        if(node && node.next){
            let pre = null
            let i = 0
            while(node && i<k){
                const temp = node.next
                node.next = pre
                pre = node
                node = temp
                i++
            }
            return pre
        }

        return node
    }

    // 链表长度大于k，反转链表并递归
    let last = isLonger(head, k)
    if(last){
        let newNext = reverseKGroup(last.next, k)
        let newHead = reverseList(head, k)

        head.next = newNext

        return newHead
    }
    else{
        return head
    }
};
```

#### 栈
1. 单链表实现栈比数组更好一些？
- 插入元素时的时间复杂度更低
- 其它啥原因？

![输入图片说明](https://images.gitee.com/uploads/images/2021/0904/183006_c1ac6443_9130428.png "屏幕截图.png")

2. [有效的括号](https://leetcode-cn.com/problems/valid-parentheses/)
3. [每日温度](https://leetcode-cn.com/problems/daily-temperatures/)

#### 队列
![输入图片说明](https://images.gitee.com/uploads/images/2021/0904/202010_96d2dcc7_9130428.png "屏幕截图.png")
1. [ 至多包含两个不同字符的最长子串](https://leetcode-cn.com/problems/longest-substring-with-at-most-two-distinct-characters/)

#### 双端队列
1. [滑动窗口最大值](https://leetcode-cn.com/problems/sliding-window-maximum/)

![输入图片说明](https://images.gitee.com/uploads/images/2021/0904/225324_f73bb006_9130428.png "屏幕截图.png")

#### 树
![输入图片说明](https://images.gitee.com/uploads/images/2021/0904/230840_c93dd972_9130428.png "屏幕截图.png")

1. [二叉搜索树中第K小的元素](https://leetcode-cn.com/problems/kth-smallest-element-in-a-bst/)
- 二叉搜索树需要学会各种解法
- 二叉搜索树通常是中序遍历

2. 


## 排序



## 递归与回溯
#### 递归力扣实例

1. 自顶向下：
- [解码方法](https://leetcode-cn.com/problems/decode-ways/)
- [中心对称数](https://leetcode-cn.com/problems/strobogrammatic-number-ii/)

2. 自底向上（动态规划）

3. 常见算法
- 二叉树的定义和遍历
- 归并排序、快速排序
- 动态规划
- 二分搜索

#### 递归的特点

![输入图片说明](https://images.gitee.com/uploads/images/2021/0904/092814_5c72fa1f_9130428.png "屏幕截图.png")


#### 递归写法总结（解题模板）：
![输入图片说明](https://images.gitee.com/uploads/images/2021/0904/094202_d258aa3a_9130428.png "屏幕截图.png")

#### 递归算法时间复杂度
1. 迭代法：
T(N) = 2 * T(N-1) + O(1)
![输入图片说明](https://images.gitee.com/uploads/images/2021/0904/094647_a49f7584_9130428.png "屏幕截图.png")

2. 公式法：
![输入图片说明](https://images.gitee.com/uploads/images/2021/0904/094855_d4efece0_9130428.png "屏幕截图.png")
![输入图片说明](https://images.gitee.com/uploads/images/2021/0904/095132_19aeebdb_9130428.png "屏幕截图.png")
![输入图片说明](https://images.gitee.com/uploads/images/2021/0904/095250_ac74433f_9130428.png "屏幕截图.png")
![输入图片说明](https://images.gitee.com/uploads/images/2021/0904/095326_e1d69714_9130428.png "屏幕截图.png")
![输入图片说明](https://images.gitee.com/uploads/images/2021/0904/095405_66c71445_9130428.png "屏幕截图.png")

#### 回溯
![输入图片说明](https://images.gitee.com/uploads/images/2021/0904/095555_48cf2757_9130428.png "屏幕截图.png")
![输入图片说明](https://images.gitee.com/uploads/images/2021/0904/095657_b129bb25_9130428.png "屏幕截图.png")

#### 回溯经典题目
- [组合总和](https://leetcode-cn.com/problems/combination-sum/)
- [N皇后2](https://leetcode-cn.com/problems/n-queens-ii/)


## 图的深度与广度优先搜索
#### 深度优先 => 借助栈
![输入图片说明](https://images.gitee.com/uploads/images/2021/0904/102020_acccbd01_9130428.png "屏幕截图.png")
![输入图片说明](https://images.gitee.com/uploads/images/2021/0904/102620_e3ff3990_9130428.png "屏幕截图.png")

#### 广度优先 => 借助队列
![输入图片说明](https://images.gitee.com/uploads/images/2021/0904/102750_32f23714_9130428.png "屏幕截图.png")

## 动态规划
#### 定义
![输入图片说明](https://images.gitee.com/uploads/images/2021/0904/103348_76083cb2_9130428.png "屏幕截图.png")

![输入图片说明](https://images.gitee.com/uploads/images/2021/0904/104125_41776db7_9130428.png "屏幕截图.png")

#### 递归/动态规划的记忆化
可以使用cache（HashMap）缓存小粒度的计算

#### 动态规划3类题目
1. 线性规划
![输入图片说明](https://images.gitee.com/uploads/images/2021/0904/105008_da8168bc_9130428.png "屏幕截图.png")
![输入图片说明](https://images.gitee.com/uploads/images/2021/0904/105316_410ebedc_9130428.png "屏幕截图.png")

- [最长递增子序列的长度](https://leetcode-cn.com/problems/longest-increasing-subsequence/)
- [爬楼梯](https://leetcode-cn.com/problems/climbing-stairs/)
- [打家劫舍](https://leetcode-cn.com/problems/house-robber/)
- [不同路径](https://leetcode-cn.com/problems/unique-paths/)

2. 区间规划
![输入图片说明](https://images.gitee.com/uploads/images/2021/0904/105341_27ba904a_9130428.png "屏幕截图.png")

- [最长回文子序列](https://leetcode-cn.com/problems/longest-palindromic-subsequence/)


3. 约束规划
![输入图片说明](https://images.gitee.com/uploads/images/2021/0904/105556_57f0d5ba_9130428.png "屏幕截图.png")
- [0-1背包问题]()

## 二分搜索和贪婪
#### 定义
![输入图片说明](https://images.gitee.com/uploads/images/2021/0904/110155_19c6c175_9130428.png "屏幕截图.png")

#### 二分搜索（重点）
![输入图片说明](https://images.gitee.com/uploads/images/2021/0904/110238_02bf4c92_9130428.png "屏幕截图.png")
![输入图片说明](https://images.gitee.com/uploads/images/2021/0904/110319_303e3afa_9130428.png "屏幕截图.png")

#### 二分搜索解题模板（需要掌握两种写法）
![输入图片说明](https://images.gitee.com/uploads/images/2021/0904/110700_7a5d540d_9130428.png "屏幕截图.png")

1. 递归写法
![输入图片说明](https://images.gitee.com/uploads/images/2021/0904/110812_cfaf26d1_9130428.png "屏幕截图.png")
![输入图片说明](https://images.gitee.com/uploads/images/2021/0904/110839_7eb896f7_9130428.png "屏幕截图.png")

2. 循环写法
![输入图片说明](https://images.gitee.com/uploads/images/2021/0904/110911_3888c150_9130428.png "屏幕截图.png")

3. 二分搜索核心
![输入图片说明](https://images.gitee.com/uploads/images/2021/0904/110930_f7a81036_9130428.png "屏幕截图.png")

#### 二分搜索题型变化
1. 找确定的边界
- [在排序数组中查找元素的第一个和最后一个位置](https://leetcode-cn.com/problems/find-first-and-last-position-of-element-in-sorted-array/)
![输入图片说明](https://images.gitee.com/uploads/images/2021/0904/111330_e275f56d_9130428.png "屏幕截图.png")

2. 找模糊的边界
![输入图片说明](https://images.gitee.com/uploads/images/2021/0904/111513_b699e5f8_9130428.png "屏幕截图.png")

- [旋转过的排序数组](https://leetcode-cn.com/problems/search-in-rotated-sorted-array/)
![输入图片说明](https://images.gitee.com/uploads/images/2021/0904/111812_3a694c8e_9130428.png "屏幕截图.png")

3. 不定长的边界
![输入图片说明](https://images.gitee.com/uploads/images/2021/0904/112001_a16bc7ea_9130428.png "屏幕截图.png")
![输入图片说明](https://images.gitee.com/uploads/images/2021/0904/112022_6b7d090e_9130428.png "屏幕截图.png")

#### 贪婪算法（熟悉以下常见题型即可）
![输入图片说明](https://images.gitee.com/uploads/images/2021/0904/112123_8411b263_9130428.png "屏幕截图.png")
![输入图片说明](https://images.gitee.com/uploads/images/2021/0904/112155_676a9e0d_9130428.png "屏幕截图.png")
![输入图片说明](https://images.gitee.com/uploads/images/2021/0904/112326_e984b029_9130428.png "屏幕截图.png")

- [会议室2](https://leetcode-cn.com/problems/meeting-rooms-ii/)
![输入图片说明](https://images.gitee.com/uploads/images/2021/0904/112438_c0748ea4_9130428.png "屏幕截图.png")

## 力扣高频题目

#### 滑动窗口
[3. 无重复字符的最长子串](https://leetcode-cn.com/problems/longest-substring-without-repeating-characters/)：
- 线性法，哈希MAP + 快慢指针：快指针添加Hash，慢指针删除子串
- 线性法，哈希MAP + 快慢指针：哈希表记录字符索引，遇到重复的跳到该字符下一个后

- 滑动窗口解法？

[215. 数组中的第K个最大元素](https://leetcode-cn.com/problems/kth-largest-element-in-an-array/)
- 队列 + 插入元素
- 快速选择：类似于快速排序，然后比较k和随机选择的mid，判断k在左边还是右边
```
// 快速选择算法找到第k大的数
var findKthLargest = function(nums, k) {
    const swap = (arr, a, b)=>{
        const temp = arr[b]
        arr[b] = arr[a]
        arr[a] = temp
    }

    const quickSelectFlag = (arr, k) => {
        if(arr.length <2){
            return arr
        } 

        let flag = 0
        let i= 0
        let j= arr.length - 1
        while(i<j){
            while(i<j && arr[flag]>=arr[j]) j--
            swap(arr, flag, j)
            flag = j
                    
            while(i<j && arr[flag]<=arr[i]) i++
            swap(arr, flag, i)
            flag = i
        }

        return flag
    }

    const quickSelect = (arr, k) => {
        const flag = quickSelectFlag(arr, k)

        if(k === flag){
            return arr[flag]
        }
        else if(k < flag){
            return quickSelect(arr.slice(0,flag), k)
        }
        else{
            return quickSelect(arr.slice(flag+1, arr.length), k-flag-1)
        }
    }

    return quickSelect(nums, k-1)
};


console.log(findKthLargest([3,2,3,1,2,4,5,5,6],2))
```

[4. 寻找两个正序数组的中位数](https://leetcode-cn.com/problems/median-of-two-sorted-arrays/)
[414. 第三大的数](https://leetcode-cn.com/problems/third-maximum-number/)

#### 合并链表 
[23. 合并K个升序链表](https://leetcode-cn.com/problems/merge-k-sorted-lists/)
- 优先队列（最小堆？）
- 分治法，合并两个链表，大于两个就递归

[21. 合并两个有序链表](https://leetcode-cn.com/problems/merge-two-sorted-lists/)

#### 区间重叠
[56. 合并区间](https://leetcode-cn.com/problems/merge-intervals/)
[435. 无重叠区间](https://leetcode-cn.com/problems/non-overlapping-intervals/)


#### 动态规划
[53. 最大子序和（难以想到的题目）](https://leetcode-cn.com/problems/maximum-subarray/)