# Algorithm

**Repository Path**: JimmyYangMJ/algorithm

## Basic Information

- **Project Name**: Algorithm
- **Description**: 算法刷题记录
- **Primary Language**: Java
- **License**: Not specified
- **Default Branch**: master
- **Homepage**: None
- **GVP Project**: No

## Statistics

- **Stars**: 0
- **Forks**: 0
- **Created**: 2021-09-17
- **Last Updated**: 2024-04-16

## Categories & Tags

**Categories**: Uncategorized

**Tags**: None

## README

# 最新语雀文档
https://www.yuque.com/jimmyyang-ytsnb/qlqifp/iwitcf9vbyta31pd?singleDoc#
# ACWin
# ACWing
# CSP
# leetcode

## 1. Array （数组）

### 1.1 difference （差分数组）
* leetcode 1109. 航班预订统计
    - 差分数组
    - 差分数组是一个辅助数组，从侧面来表示给定某一数组的变化，一般用来对数组进行区间修改的操作
    - [算法] 在 diff[from] + value， 在 diff[to+1] - value
### 1.2 排序思想
* leetcode 215.  数组中的第K个最大元素
    - 快排思想
* leetcode Offer 40. 最小的k个数
* Offer 51. 数组中的逆序对
  - 归并排序思想
### 1.3 Others
- leetcode 15. 三数之和
- leetcode 457. 环形数组是否存在循环
- leetcode 628. 三个数的最大乘积
## 2. binarySearch （二分搜索）
1539. 第 k 个缺失的正整数
2141. 同时运行 N 台电脑的最长时间
    - 二分答案法
## 3. Bit operation （位操作）
136. 只出现一次的数字
Offer 15. 二进制中1的个数
Offer 65. 不用加减乘除做加法
## 4. divide and conquer （分治）
53 最大子列和
169 多数元素 Majority Element 
    - （超级水王问题）
## 5. DP （动态规划）
### knapsack （背包）
322. 零钱兑换
983. 最低票价
### sequence （序列问题）
- leetcode 5. 最长回文子串
  * 时间复杂度 O(n^2)，RemoveBlock[s.len][s.len] （右上三角）
  注意 RemoveBlock[start][end] 依赖于 RemoveBlock[start+1][end-1]， 
    所以在两层循环中注意 start 和 end 遍历的先后顺序 
- leetcode 647. 回文子串
  * 和 leetcode 5 类似
* leetcode 53. 最大子数组和
* leetcode 97. 交错字符串
* leetcode 300. 最长递增子序列
* leetcode 516. 最长回文子序列
* leetcode 673. 最长递增子序列的个数
* leetcode 1143. 最长公共子序列 (LCS)
    - 子问题：两个String分别以i,j下标结尾的字串的"最长公共序列"
    - DP: 二维[i][j] ->（优化） 一维
* leetcode 583. 两个字符串的删除操作
    - 1143 LCS 的变式 
    - 子问题：两个String分别以i,j下标结尾的字串的"最小删除次数"
    - DP
* leetcode 1035. 不相交的线
    - 1143 LCS 的变式
- leetcode Offer 48. 最长不含重复字符的子字符串

### Others
264. 丑数 II 
198. 打家劫舍 
213. 打家劫舍 II
337. 打家劫舍 III
343. 整数拆分
473. 火柴拼正方形
940. 不同的子序列 II 
     Offer 10- II. 青蛙跳台阶问题
     Offer 47. 礼物的最大价值
     Offer 63. 股票的最大利润
## 6. Graph （图）

## 7. greedy （贪心算法）
* leetcode 55. 跳跃游戏
* leetcode 45. 跳跃游戏 II
    - 贪心算法：O(n)
    - 在 起点时（i） 记录 能到的最远距离（m）， 则遍历 起点 到这个最远距离(i - m )的 所有点中可以跳的的最远的 那个点k作为下一跳
    - (也可以 dp和递归，但是时间 和 空间 不如 O(n))
## 8. Hash

## 9. Heap

## 10. LinkedList 链表

## 11.math

## 12. queue (队列)
### 常见解法：
  - 优先队列，
  - 单调队列：
    - 原数组依次入队（双向队列），当栈内不满足单调性时，不满足的元素从队尾出栈。单调队列保证：
    当最大值/最小值 max 出队列（从队头）时，原数组 max下标之后范围的 第二大的值为单调队列的下一个出队元素
    - 即，比最大值小的元素，（从队尾出栈的元素），会在最大值出栈之前出栈
### 例题
- leetcode 239. 滑动窗口的最大值
  - 方法1：优先队列（大根堆）
  - 方法2：单调队列（双端队列）

## 13. stack （栈）
常见解法/题型：
    - 单调栈: 可找出每一个元素左侧和右侧第一个比它大的元素所在的位置（记录局部最值）
    - 双栈模拟队列
### 例题
- leetcode 739. 每日温度
    - 单调栈，注意栈内存放是温度的下标
  
- leetcode 496 下一个更大元素 I
    - 单调栈，从后往前遍历 nums[]
    
- leetcode 530 下一个更大元素 II
    - 单调栈，由于是循环数组，需要两次循环遍历 从 [len*2-1, 0]

- leetcode 654. 最大二叉树
    - 递归构造
    - 单调栈
## research （搜索算法）

## slidingWindow （滑动窗口）
- leetcode 3. 无重复字符的最长子串
   - 通过 Map<char, int> 保存无重复字串，同时记录滑动窗口的边界
    通过比较 map 的 value 和 滑动窗口的边界 判断 字符是否在窗口内
- leetcode 567. 字符串的排列 
     - 通过 int[26] 判断两个子串是否是同一排列

## Tree (树)
### path （路径）
### searchTree（搜索树）
- leetcode 95. 不同的二叉搜索树 II
- leetcode 814. 二叉树剪枝
    - 递归遍历，返回子树1的个数
  
- 几个二叉搜索树转化为AVL平衡树的题，一般最优解是获取中序序列后构造AVL树，如果采用旋转调整太复杂
    1382. 将二叉搜索树变平衡
    108. 将有序数组转换为二叉搜索树
    109. 有序链表转换二叉搜索树

## TwoPointer （双指针）
61. 旋转链表
11. 盛最多水的容器 
    Offer 22. 链表中倒数第k个节点
## UnionFind （并查集）
128. 最长连续序列
## multiThread （多线程）
* leetcode 1115. 交替打印 FooBar
  - CyclicBarrier 控制先后
  - synchronized + 标志位(volatile) + 唤醒(notifyAll)
  - 自旋 + 让出CPU(Thread.yield())  
  - 信号量 Semaphore
* leetcode 1114. 按序打印
  - 阻塞队列 BlockingQueue， SynchronousQueue
  - Java Lock（ReentrantLock）+自旋实现
  - 信号量 Semaphore
  - AtomicInteger
# luogu
··· ···
# POJ
··· ···
# PTA
··· ···


# PTA