# AlgoDS

**Repository Path**: dungang/AlgoDS

## Basic Information

- **Project Name**: AlgoDS
- **Description**: 镜像
- **Primary Language**: Unknown
- **License**: MIT
- **Default Branch**: master
- **Homepage**: None
- **GVP Project**: No

## Statistics

- **Stars**: 0
- **Forks**: 0
- **Created**: 2021-03-19
- **Last Updated**: 2021-03-19

## Categories & Tags

**Categories**: Uncategorized

**Tags**: None

## README

[English](https://github.com/yunshuipiao/AlgoDS) | 简体中文
# 算法与数据结构

这是 一份 **算法和数据结构** 和 **面试题目**（附解答）的集合。
该仓库包含了我对常见算法的解答和用 `Java`实现的数据结构。 
创建该仓库用于学习更多的算法，并持续添加问题和解答。
到目前为止，已经包含了 **算法和数据结构** 和 **超过250个问题和答案**。


### 简述
  
根据困难程度将问题分为三个等级：

1) [简单问题](https://github.com/sherxon/AlgoDS/blob/master/src/problems/Easy.txt) -- [答案](https://github.com/sherxon/AlgoDS/blob/master/src/problems/easy)  
2) [中等问题](https://github.com/sherxon/AlgoDS/blob/master/src/problems/Medium.txt) -- [答案](https://github.com/sherxon/AlgoDS/blob/master/src/problems/medium)  
3) [困难问题](https://github.com/sherxon/AlgoDS/blob/master/src/problems/Hard.txt) -- [答案](https://github.com/sherxon/AlgoDS/blob/master/src/problems/hard)  
       


## 问题
  
### 数组
1) [Rotate Array：旋转数组](https://github.com/sherxon/AlgoDS/blob/master/src/problems/easy/RotateArray.java)      
2) [Contains Duplicate：包含重复值](https://github.com/sherxon/AlgoDS/blob/master/src/problems/easy/ContainsDuplicate.java)  
3) [Find Peak Element：寻找最大值](https://github.com/sherxon/AlgoDS/blob/master/src/problems/medium/FindPeakElement.java)  
4) [Maximum Subarray：最大子数列（子串和）](https://github.com/sherxon/AlgoDS/blob/master/src/problems/medium/MaximumSubarray.java)  
5) [Kth Largest Element in an Array：数组中的第K大元素](https://github.com/sherxon/AlgoDS/blob/master/src/problems/medium/KthLargestElementinanArray.java)  
6) [Find All Duplicates in an Array：寻找数组中的全部重复元素](https://github.com/sherxon/AlgoDS/blob/master/src/problems/medium/FindAllDuplicatesinanArray.java)  
7) [Longest Increasing Subsequence：最长递增子序列](https://github.com/sherxon/AlgoDS/blob/master/src/problems/medium/MaxIncreasingSubsequence.java)  
8) [Rotate Image, matrix：旋转图像，矩阵](https://github.com/sherxon/AlgoDS/blob/master/src/problems/medium/RotateImage.java)  
9) [Shuffle an Array：数组洗牌](https://github.com/sherxon/AlgoDS/blob/master/src/problems/medium/ShuffleanArray.java)  
10) [Find Min in Rotated Array：寻找旋转排序数组中的最小值](https://github.com/sherxon/AlgoDS/blob/master/src/problems/medium/FindMinimuminRotatedSortedArray.java)  
11) [Search in Rotated Array：在旋转数组中查找](https://github.com/sherxon/AlgoDS/blob/master/src/problems/medium/SearchinRotatedSortedArray.java)  
  

### 链表

1) [Singly Linked List Implementation： 单向链表实现](https://github.com/sherxon/AlgoDS/blob/master/src/ds/LinkedList.java)  
1) [Doubly Linked List Implementation：双向链表实现](https://github.com/sherxon/AlgoDS/blob/master/src/ds/DoublyLinkedList.java)  
3) [Delete Node in a Linked List：删除链表节点](https://github.com/sherxon/AlgoDS/blob/master/src/problems/easy/DeleteNodeSingleLinkedList.java)  
4) [Palindrome Linked List：回文链表](https://github.com/sherxon/AlgoDS/blob/master/src/problems/easy/PalindromeLinkedList.java)  
5) [Reverse Linked List：反转链表](https://github.com/sherxon/AlgoDS/blob/master/src/problems/easy/ReverseLinkedList.java)  
6) [Intersection of Two Linked Lists：两链表的交叉点](https://github.com/sherxon/AlgoDS/blob/master/src/problems/easy/IntersectionofTwoLinkedLists.java)  
7) [Linked List Cycle：带环链表](https://github.com/sherxon/AlgoDS/blob/master/src/problems/easy/LinkedListCycle.java)  
8) [Remove Nth Node From End of List：删除链表中倒数第n个节点](https://github.com/sherxon/AlgoDS/blob/master/src/problems/easy/RemoveNthNodeFromEndofList.java)   
9) [Merge Sort List：合并有序链表](https://github.com/sherxon/AlgoDS/blob/master/src/problems/medium/SortList.java)  
10) [Find Linked List Cycle：寻找带环链表](https://github.com/sherxon/AlgoDS/blob/master/src/problems/medium/LinkedListCycle2.java)  
11) [Merge k Sorted Lists： 合并k个排序链表](https://github.com/sherxon/AlgoDS/blob/master/src/problems/medium/MergekSortedLists.java)   
 [And many other Linked list problems：其余有关链表的题目](https://github.com/sherxon/AlgoDS/tree/master/src/problems)
 
### 二叉树
1) [Binary Tree Level Order Traversal：二叉树的层次遍历](https://github.com/sherxon/AlgoDS/blob/master/src/problems/easy/BinaryTreeLevelOrderTraversal.java)  
2) [Sum of Left Leaves：左叶子节点的和](https://github.com/sherxon/AlgoDS/blob/master/src/problems/easy/SumofLeftLeaves.java)  
3) [Invert Binary Tree：反转二叉树](https://github.com/sherxon/AlgoDS/blob/master/src/problems/easy/InvertBinaryTree.java)  
4) [Binary Search Tree Iterator：二叉搜索树迭代器](https://github.com/sherxon/AlgoDS/blob/master/src/problems/medium/BinarySearchTreeIterator.java)  
5) [Binary Tree Postorder Traversal：二叉树后续遍历](https://github.com/sherxon/AlgoDS/blob/master/src/problems/hard/PostOrderTraversalTree.java)  
6) [Binary Tree Preorder Traversal：二叉树前序遍历](https://github.com/sherxon/AlgoDS/blob/master/src/problems/medium/BinaryTreePreorderTraversal.java)  
7) [Flatten Binary Tree to Linked List：二叉树转换成链表](https://github.com/sherxon/AlgoDS/blob/master/src/problems/medium/FlattenBinaryTreetoLinkedList.java)  
8) [Symmetric Tree：对称树](https://github.com/sherxon/AlgoDS/blob/master/src/problems/easy/SymmetricTree.java)  
9) [Binary Tree Inorder Traversal：二叉树中序遍历](https://github.com/sherxon/AlgoDS/blob/master/src/problems/medium/BinaryTreeInorderTraversal.java)  
10) [Same Tree：相同树](https://github.com/sherxon/AlgoDS/blob/master/src/problems/easy/SameTree.java)  
11) [Maximum Depth of Binary Tree：二叉树的最大深度](https://github.com/sherxon/AlgoDS/blob/master/src/problems/easy/MaximumDepthofBinaryTree.java)  
12) [Balanced Binary Tree：平衡二叉树](https://github.com/sherxon/AlgoDS/blob/master/src/problems/easy/BalancedBinaryTree.java)  
13) [Minimum Depth of Binary Tree：二叉树的最小深度](https://github.com/sherxon/AlgoDS/blob/master/src/problems/easy/MinimumDepthofBinaryTree.java)     
14) [Sorted List to Balanced Binary Search Tree：有序链表转换平衡二叉查找树](https://github.com/sherxon/AlgoDS/blob/master/src/problems/medium/ConvertSortedListtoBinarySearchTree.java)   
15) [Validate Binary Search Tree：验证二叉搜索树](https://github.com/sherxon/AlgoDS/blob/master/src/problems/medium/ValidateBinarySearchTree.java)  
16) [Sorted Array to Balanced BST ：有序数组转换二叉查找树](https://github.com/sherxon/AlgoDS/blob/master/src/problems/medium/ConvertSortedArraytoBinarySearchTree.java)  
17) [Kth Smallest Element in a BST：二叉搜索树的第k小元素](https://github.com/sherxon/AlgoDS/blob/master/src/problems/medium/KthSmallestElementinaBST.java)  
18) [Binary Tree Zigzag Level Order Traversal：二叉树的锯齿形层次遍历](https://github.com/sherxon/AlgoDS/blob/master/src/problems/medium/ZigZagOrderLevelTraversalBST.java)  
19) [Delete Node in a BST：删除二叉查找树的节点](https://github.com/sherxon/AlgoDS/blob/master/src/problems/medium/DeleteNodeinaBST.java)  
20) [Lowest Common Ancestor of BST：二叉查找树最近公共祖先](https://github.com/sherxon/AlgoDS/blob/master/src/problems/easy/LowestCommonAncestorBST.java)  
21) [Binary Tree Left Side View：二叉树的左侧视图](https://github.com/sherxon/AlgoDS/blob/master/src/problems/medium/BinaryTreeLeftSIdeView.java)  
22) [Binary Tree Right Side View：二叉树的右侧视图](https://github.com/sherxon/AlgoDS/blob/master/src/problems/medium/BinaryTreeRightSideView.java)  
23) [Mode in BST：二叉查找树的模式](https://github.com/sherxon/AlgoDS/blob/master/src/problems/easy/FindModeinBST.java)   
24) [Most Frequent Subtree Sum：最常出现的子树和](https://github.com/sherxon/AlgoDS/blob/master/src/problems/medium/MostFrequentSubtreeSum.java)  
25) [ Find Largest Element in Each Row：寻找每行的最大元素](https://github.com/sherxon/AlgoDS/blob/master/src/problems/medium/FindLargestElementinEachRow.java)   
26) [Serialize and Deserialize BT：二叉树的序列化和反序列化](https://github.com/sherxon/AlgoDS/blob/master/src/problems/hard/SerializeAndDeserializeBT.java)   
 [And many other tree problems：其余有关树的问题](https://github.com/sherxon/AlgoDS/tree/master/src/problems)  

### 数学
1) [Integer Break：整数分解](https://github.com/sherxon/AlgoDS/blob/master/src/problems/medium/IntegerBreak.java)  
2) [Reverse Bits：反转位](https://github.com/sherxon/AlgoDS/blob/master/src/problems/easy/ReverseBits.java)   
3) [Palindrome Number：回文数](https://github.com/sherxon/AlgoDS/blob/master/src/problems/easy/PalindromeNumber.java)  
4) [Math.pow：幂](https://github.com/sherxon/AlgoDS/blob/master/src/problems/medium/Pow.java)  
5) [Jug and Water Problem：水罐问题](https://github.com/sherxon/AlgoDS/blob/master/src/problems/medium/WaterAndJugProblem.java)  
6) [Sieve of Eratosthenes：埃拉托斯特尼筛法](https://github.com/sherxon/AlgoDS/blob/master/src/algo/numerals/SieveofEratosthenes.java)  
7) [Fermat's primality：费马素数](https://github.com/sherxon/AlgoDS/blob/master/src/algo/numerals/FermatPrimality.java)     
8) [Evaluate Reverse Polish Notation：计算逆波兰波表达式](https://github.com/sherxon/AlgoDS/blob/master/src/problems/medium/EvaluateReversePolishNotation.java)  


### 栈和队列
1) [Min Stack：最小栈](https://github.com/sherxon/AlgoDS/blob/master/src/problems/easy/MinStack.java)  
2) [Min Queue：最小队列](https://github.com/sherxon/AlgoDS/blob/master/src/problems/easy/QueuewithMinimum.java)  
3) [Implement Stack Using Queue：用队列实现栈](https://github.com/sherxon/AlgoDS/blob/master/src/problems/easy/ImplementStackUsingQueues.java)  
4) [Implement Queue Using Stack：用栈实现队列](https://github.com/sherxon/AlgoDS/blob/master/src/problems/easy/ImplementQueueusingStacks.java)
5) [Sort Stack：有序栈](https://github.com/sherxon/AlgoDS/blob/master/src/problems/medium/SortStack.java)  


### 动态规划问题
1) [Fibonacci Numbers：斐波那契数列](https://github.com/sherxon/AlgoDS/blob/master/src/algo/dp/FibonacciNumber.java)  
2) [Word Break：单词分割](https://github.com/sherxon/AlgoDS/blob/master/src/problems/medium/WordBreak.java)  
3) [Subset Sum：子集和问题](https://github.com/sherxon/AlgoDS/blob/master/src/algo/dp/SubsetSum.java)     
4) [0/1 Knapsack Problem：0/1背包问题](https://github.com/sherxon/AlgoDS/blob/master/src/algo/dp/Knapsack01.java)     
5) [Shortest Palindrome (KMP)：最短回文串](https://github.com/sherxon/AlgoDS/blob/master/src/problems/hard/ShortestPalindrome.java) 
6) [Minimum Square Sum：最小平方和](https://github.com/sherxon/AlgoDS/blob/master/src/algo/dp/MinimumSquareSum.java)
7) [Maximum weight transformation of a String：字符串的最大重量转换](https://github.com/sherxon/AlgoDS/blob/master/src/algo/dp/MaxWeightTransformation.java)
8) [Coin Change：硬币找零](https://github.com/sherxon/AlgoDS/blob/master/src/problems/medium/CoinChange.java)  


### 混合问题
1) [Union Find：并查集](https://github.com/sherxon/AlgoDS/blob/master/src/algo/UnionFind.java)  
2) [Permutations：排列组合](https://github.com/sherxon/AlgoDS/blob/master/src/problems/medium/Permutations.java)  
3) [Subsets：子集问题](https://github.com/sherxon/AlgoDS/blob/master/src/problems/medium/SubSets.java)     


 ## 算法
 
### 排序和查找   
1) [Bubble Sort：冒泡排序](https://github.com/sherxon/AlgoDS/blob/master/src/algo/sortingandsearching/BubbleSort.java)  
2) [Insertion Sort：插入排序](https://github.com/sherxon/AlgoDS/blob/master/src/algo/sortingandsearching/InsertionSort.java)  
3) [Selection Sort：选择排序](https://github.com/sherxon/AlgoDS/blob/master/src/algo/sortingandsearching/SelectionSort.java)  
4) [Counting Sort：计数排序](https://github.com/sherxon/AlgoDS/blob/master/src/algo/sortingandsearching/CountingSort.java)  
5) [Binary Search , Lower & Upper Bounds：二分查找，上下界](https://github.com/sherxon/AlgoDS/blob/master/src/algo/sortingandsearching/BinarySearch.java)  
6) [MergeSort：归并排序](https://github.com/sherxon/AlgoDS/blob/master/src/algo/sortingandsearching/MergeSort.java)  
7) [QuickSort：快速排序](https://github.com/sherxon/AlgoDS/blob/master/src/algo/sortingandsearching/QuickSort.java)  

 
### 图 
1) [Breadth First Search (BFS)：广度优先遍历](https://github.com/sherxon/AlgoDS/blob/master/src/algo/graph/BFS.java)  
2) [Depth First Search (DFS)：深度优先遍历](https://github.com/sherxon/AlgoDS/blob/master/src/algo/graph/DFS.java)  
3) [Prim's Minimum Spanning Tree (MST)：最小生成树(Prim's算法)](https://github.com/sherxon/AlgoDS/blob/master/src/algo/graph/PrimsMST.java)  
4) [KrusKal's Minimum Spanning Tree (MST)：最小生成树(KrusKal's算法)](https://github.com/sherxon/AlgoDS/blob/master/src/algo/graph/KruskalsMST.java)  
5) [Topological Sorting：拓扑排序](https://github.com/sherxon/AlgoDS/blob/master/src/algo/graph/TopologicalSorting.java)      
6) [Shortest Path Dijsktra：Dijsktra最短路径](https://github.com/sherxon/AlgoDS/blob/master/src/algo/graph/Dijsktra.java)  
7) [Shortest Path Bellman-Ford：Bellman-Ford最短路径](https://github.com/sherxon/AlgoDS/blob/master/src/algo/graph/BellmanFord.java)  
8) [A* Heuristic Path Finding：启发式搜索A*算法](https://github.com/sherxon/AlgoDS/blob/master/src/algo/graph/AStar.java)  
9) [Is Graph Bipartite：二分图判断](https://github.com/sherxon/AlgoDS/blob/master/src/algo/graph/IsBipartite.java)    
10) [Is Graph Connected：连通图判断](https://github.com/sherxon/AlgoDS/blob/master/src/algo/graph/IsConnected.java)  
11) [Cycle Detection：周期检测](https://github.com/sherxon/AlgoDS/blob/master/src/algo/graph/CycleDetection.java)  
12) [Undirected Graph Bridge Detection：无向图的桥梁检测](https://github.com/prafful1/AlgoDS/blob/master/src/algo/graph/BridgeUndirectedGraph.java)


### 字符串
1) [Rabin Karp Subsequence search：Rabin Karp子序列搜索](https://github.com/sherxon/AlgoDS/blob/master/src/algo/string/RabinKarpSubsequenceSearch.java)   
2) [Ransom Note：勒索信](https://github.com/sherxon/AlgoDS/blob/master/src/problems/easy/RansomNote.java)  
3) [Reverse String：反转字符串](https://github.com/sherxon/AlgoDS/blob/master/src/problems/easy/ReverseString.java)  
4) [Longest Common Prefix：最长公共前缀](https://github.com/sherxon/AlgoDS/blob/master/src/problems/easy/LongestCommonPrefix.java)  
5) [Is Anagram：回文字符串](https://github.com/sherxon/AlgoDS/blob/master/src/problems/easy/ValidAnagram.java)  
6) [Needle and Haystack：针和草堆](https://github.com/sherxon/AlgoDS/blob/master/src/problems/easy/ImplementstrSt.java)  
7) [Word Break：单词分割](https://github.com/sherxon/AlgoDS/blob/master/src/problems/medium/WordBreak.java)  
8) [Meta Strings：元字符串](https://github.com/sherxon/AlgoDS/blob/master/src/problems/medium/MetaStrings.java)  


## 数据结构      


### 树
1) [Binary Search Tree (recursive)：二叉查找树(递归)](https://github.com/sherxon/AlgoDS/blob/master/src/ds/BST.java)  
2) [Binary Search Tree (iterative)：二叉查找树(迭代)](https://github.com/sherxon/AlgoDS/blob/master/src/ds/BSTIterative.java)  
3) [AVL Tree：平衡二叉查找树(BBST)](https://github.com/sherxon/AlgoDS/blob/master/src/ds/AVLTree.java)    
4) [Trie (Prefix tree)：字典树、前缀树（Prefix Tree）、单词查找树 或 键树](https://github.com/sherxon/AlgoDS/blob/master/src/algo/string/Trie.java)  
5) [Hashed Array Tree：散列数组树](https://github.com/sherxon/AlgoDS/blob/master/src/ds/HashedArrayTree.java)  
6) [LRU Cache：最近最少使用缓存](https://github.com/sherxon/AlgoDS/blob/master/src/problems/hard/LRUCache.java)  


## 贡献

发现bug？另一种更好的方法？请提交PR。