diff options
| author | chai <chaifix@163.com> | 2021-06-24 19:55:26 +0800 |
|---|---|---|
| committer | chai <chaifix@163.com> | 2021-06-24 19:55:26 +0800 |
| commit | dbcd0c269014100b7d4cc421c5ab518f275cca09 (patch) | |
| tree | 6564ca8a58b6921d4782bba3feae0ea787f9e1f4 | |
| parent | 2749e059084b99737d79aadd92521023b0f65f56 (diff) | |
30 files changed, 773 insertions, 43 deletions
diff --git a/Assets/Algorithms/Algebra/Linear.cs b/Assets/Algorithms/Algebra/Linear.cs index 5448b50..29584ce 100644 --- a/Assets/Algorithms/Algebra/Linear.cs +++ b/Assets/Algorithms/Algebra/Linear.cs @@ -2,17 +2,12 @@ using System.Collections.Generic;
using UnityEngine;
-public class Linear : MonoBehaviour
+
+namespace AlgorithmCollection.Algebra
{
- // Start is called before the first frame update
- void Start()
+ public static class Linear
{
-
- }
- // Update is called once per frame
- void Update()
- {
-
+
}
}
diff --git a/Assets/Algorithms/Algebra/MatrixUtils.cs b/Assets/Algorithms/Algebra/MatrixUtils.cs new file mode 100644 index 0000000..84c12c3 --- /dev/null +++ b/Assets/Algorithms/Algebra/MatrixUtils.cs @@ -0,0 +1,13 @@ +using System.Collections;
+using System.Collections.Generic;
+using UnityEngine;
+
+
+namespace AlgorithmCollection.Algebra
+{
+ public static class MatrixUtils
+ {
+
+
+ }
+}
diff --git a/Assets/Test/04_Pathfinding/AStarPathfinding.cs.meta b/Assets/Algorithms/Algebra/MatrixUtils.cs.meta index 5cd6112..1ac378e 100644 --- a/Assets/Test/04_Pathfinding/AStarPathfinding.cs.meta +++ b/Assets/Algorithms/Algebra/MatrixUtils.cs.meta @@ -1,5 +1,5 @@ fileFormatVersion: 2 -guid: 66158ef978f1a7540addceae83d08239 +guid: bb506f4381cf42643a1d968c52ec0bae MonoImporter: externalObjects: {} serializedVersion: 2 diff --git a/Assets/Algorithms/Algebra/Vector3Utils.cs b/Assets/Algorithms/Algebra/Vector3Utils.cs new file mode 100644 index 0000000..d77030f --- /dev/null +++ b/Assets/Algorithms/Algebra/Vector3Utils.cs @@ -0,0 +1,13 @@ +using System.Collections;
+using System.Collections.Generic;
+using UnityEngine;
+
+
+namespace AlgorithmCollection.Algebra
+{
+ public static class Vector3Utils
+ {
+
+
+ }
+}
diff --git a/Assets/Algorithms/Algebra/Vector3Utils.cs.meta b/Assets/Algorithms/Algebra/Vector3Utils.cs.meta new file mode 100644 index 0000000..856cdea --- /dev/null +++ b/Assets/Algorithms/Algebra/Vector3Utils.cs.meta @@ -0,0 +1,11 @@ +fileFormatVersion: 2 +guid: 5550f49c26a0d8e4c8d014b7e7b530a5 +MonoImporter: + externalObjects: {} + serializedVersion: 2 + defaultReferences: [] + executionOrder: 0 + icon: {instanceID: 0} + userData: + assetBundleName: + assetBundleVariant: diff --git a/Assets/Algorithms/Algorithms.cs b/Assets/Algorithms/Algorithms.cs index a6005d3..7d51606 100644 --- a/Assets/Algorithms/Algorithms.cs +++ b/Assets/Algorithms/Algorithms.cs @@ -49,10 +49,21 @@ namespace AlgorithmCollection return v1.CompareTo(v2) < 0 ? v1 : v2;
}
+ public static T Max<T>(T v1, T v2) where T : IComparable
+ {
+ return v1.CompareTo(v2) > 0 ? v1 : v2;
+ }
+
public static string ListToString<T>(List<T> data)
{
string content = "";
- data.ForEach((T v) => { content += v.ToString(); });
+ //data.ForEach((T v) => { content += v.ToString(); });
+ for(int i = 0; i < data.Count; ++i)
+ {
+ content += data[i];
+ if (i != data.Count - 1)
+ content += ",";
+ }
return content;
}
diff --git a/Assets/Algorithms/Algorithms_Utils.cs b/Assets/Algorithms/Algorithms_Utils.cs new file mode 100644 index 0000000..6eee42f --- /dev/null +++ b/Assets/Algorithms/Algorithms_Utils.cs @@ -0,0 +1,31 @@ +using System;
+using System.Collections;
+using System.Collections.Generic;
+using UnityEngine;
+
+namespace AlgorithmCollection
+{
+ public static partial class Algorithms
+ {
+ // 两数之和，在nums中找到和为target的两个数
+ public static int[] TwoSum(int[] nums, int target)
+ {
+ int a = 0, b = 0;
+ Dictionary<int, int> lut = new Dictionary<int, int>();
+ for (int i = 0; i < nums.Length; ++i)
+ {
+ if (lut.ContainsKey(target - nums[i]))
+ {
+ a = i;
+ b = lut[target - nums[i]];
+ break;
+ }
+ lut.Add(nums[i], i);
+ }
+ return new int[] { a, b };
+ }
+
+ //
+
+ }
+}
\ No newline at end of file diff --git a/Assets/Algorithms/Algorithms_Utils.cs.meta b/Assets/Algorithms/Algorithms_Utils.cs.meta new file mode 100644 index 0000000..350781c --- /dev/null +++ b/Assets/Algorithms/Algorithms_Utils.cs.meta @@ -0,0 +1,11 @@ +fileFormatVersion: 2 +guid: 325a82332ec4d724685daa5e2e076443 +MonoImporter: + externalObjects: {} + serializedVersion: 2 + defaultReferences: [] + executionOrder: 0 + icon: {instanceID: 0} + userData: + assetBundleName: + assetBundleVariant: diff --git a/Assets/Algorithms/Geometry/GeometryHelper.cs b/Assets/Algorithms/Geometry/GeometryHelper.cs index 6da1503..da74944 100644 --- a/Assets/Algorithms/Geometry/GeometryHelper.cs +++ b/Assets/Algorithms/Geometry/GeometryHelper.cs @@ -2,17 +2,18 @@ using System.Collections.Generic;
using UnityEngine;
-public class GeometryHelper : MonoBehaviour
+
+namespace AlgorithmCollection.Geometry
{
- // Start is called before the first frame update
- void Start()
+ public static class GeometryHelper
{
-
- }
- // Update is called once per frame
- void Update()
- {
-
+ // 多边形最佳剖分，将多边形划分为权重最小的三角形
+ public delegate int SubdivisionWeight(int v1, int v2, int v3);
+ public static void SubdividePolygon(int[] verticies, SubdivisionWeight weight)
+ {
+
+ }
+
}
}
diff --git a/Assets/Algorithms/PathFinding/AStarPathfinding.cs b/Assets/Algorithms/PathFinding/AStarPathfinding.cs index 88d3e94..312ec41 100644 --- a/Assets/Algorithms/PathFinding/AStarPathfinding.cs +++ b/Assets/Algorithms/PathFinding/AStarPathfinding.cs @@ -1,18 +1,13 @@ -//using System.Collections; -//using System.Collections.Generic; -//using UnityEngine; - -//public class AStarPathfinding : MonoBehaviour -//{ -// // Start is called before the first frame update -// void Start() -// { - -// } - -// // Update is called once per frame -// void Update() -// { - -// } -//} +using System.Collections;
+using System.Collections.Generic;
+using UnityEngine;
+
+
+namespace AlgorithmCollection.PathFinding
+{
+ public static class AStarPathfinding
+ {
+
+
+ }
+}
diff --git a/Assets/Algorithms/PathFinding/DijkstraPathfinding.cs b/Assets/Algorithms/PathFinding/DijkstraPathfinding.cs new file mode 100644 index 0000000..87f0074 --- /dev/null +++ b/Assets/Algorithms/PathFinding/DijkstraPathfinding.cs @@ -0,0 +1,13 @@ +using System.Collections;
+using System.Collections.Generic;
+using UnityEngine;
+
+
+namespace AlgorithmCollection.PathFinding
+{
+ public static class DijkstraPathfinding
+ {
+
+
+ }
+}
diff --git a/Assets/Algorithms/PathFinding/DijkstraPathfinding.cs.meta b/Assets/Algorithms/PathFinding/DijkstraPathfinding.cs.meta new file mode 100644 index 0000000..cf1299a --- /dev/null +++ b/Assets/Algorithms/PathFinding/DijkstraPathfinding.cs.meta @@ -0,0 +1,11 @@ +fileFormatVersion: 2 +guid: 8acbcdf276956c145a32df50596952cb +MonoImporter: + externalObjects: {} + serializedVersion: 2 + defaultReferences: [] + executionOrder: 0 + icon: {instanceID: 0} + userData: + assetBundleName: + assetBundleVariant: diff --git a/Assets/Algorithms/Recursion/Recursion_DP.cs b/Assets/Algorithms/Recursion/Recursion_DP.cs index a0205ba..f672ebc 100644 --- a/Assets/Algorithms/Recursion/Recursion_DP.cs +++ b/Assets/Algorithms/Recursion/Recursion_DP.cs @@ -102,5 +102,7 @@ namespace AlgorithmCollection.Recursion return max;
}
+
+
}
}
\ No newline at end of file diff --git a/Assets/Algorithms/Recursion/Recursion_Greedy.cs b/Assets/Algorithms/Recursion/Recursion_Greedy.cs new file mode 100644 index 0000000..f332640 --- /dev/null +++ b/Assets/Algorithms/Recursion/Recursion_Greedy.cs @@ -0,0 +1,15 @@ +using System;
+using System.Collections;
+using System.Collections.Generic;
+using AlgorithmCollection;
+using UnityEngine;
+
+// 贪心算法
+namespace AlgorithmCollection.Recursion
+{
+
+ public static partial class RecursionHelper
+ {
+
+ }
+}
\ No newline at end of file diff --git a/Assets/Algorithms/Recursion/Recursion_Greedy.cs.meta b/Assets/Algorithms/Recursion/Recursion_Greedy.cs.meta new file mode 100644 index 0000000..3f00ca9 --- /dev/null +++ b/Assets/Algorithms/Recursion/Recursion_Greedy.cs.meta @@ -0,0 +1,11 @@ +fileFormatVersion: 2 +guid: b56f042655312d44388ead1823593284 +MonoImporter: + externalObjects: {} + serializedVersion: 2 + defaultReferences: [] + executionOrder: 0 + icon: {instanceID: 0} + userData: + assetBundleName: + assetBundleVariant: diff --git a/Assets/Algorithms/Searching/SearchingHelper.cs b/Assets/Algorithms/Searching/SearchingHelper.cs index 191ff5e..d177957 100644 --- a/Assets/Algorithms/Searching/SearchingHelper.cs +++ b/Assets/Algorithms/Searching/SearchingHelper.cs @@ -34,7 +34,7 @@ namespace AlgorithmCollection.Searching public static int BinarySearch<T>(List<T> data, T value) where T : IComparable, IEquatable<T>
{
int index = -1;
- RecursionHelper.DNC(
+ RecursionHelper.DC(
() =>
{
DivisionDescriptor div = new DivisionDescriptor();
@@ -116,7 +116,7 @@ namespace AlgorithmCollection.Searching { bool suc = false; T v = default(T); - RecursionHelper.DNC( + RecursionHelper.DC( ()=> {
DivisionDescriptor div = new DivisionDescriptor();
diff --git a/Assets/Common.meta b/Assets/CollectionsExt.meta index ab81fd0..73f47c5 100644 --- a/Assets/Common.meta +++ b/Assets/CollectionsExt.meta @@ -1,5 +1,5 @@ fileFormatVersion: 2 -guid: 5629771d46311c14e9adb024edfab837 +guid: 82a401f8a530ccd4d9e3eb3bf23bf708 folderAsset: yes DefaultImporter: externalObjects: {} diff --git a/Assets/Test/04_Pathfinding/AStarPathfinding.cs b/Assets/CollectionsExt/BinarySearchTree.cs index 80ba51d..ef6118a 100644 --- a/Assets/Test/04_Pathfinding/AStarPathfinding.cs +++ b/Assets/CollectionsExt/BinarySearchTree.cs @@ -2,7 +2,7 @@ using System.Collections.Generic;
using UnityEngine;
-public class AStarPathfinding : MonoBehaviour
+public class BinarySearchTree : MonoBehaviour
{
// Start is called before the first frame update
void Start()
diff --git a/Assets/CollectionsExt/BinarySearchTree.cs.meta b/Assets/CollectionsExt/BinarySearchTree.cs.meta new file mode 100644 index 0000000..7dd1f7c --- /dev/null +++ b/Assets/CollectionsExt/BinarySearchTree.cs.meta @@ -0,0 +1,11 @@ +fileFormatVersion: 2 +guid: 40581e5f59b91df409fbdb0ed8ac6a61 +MonoImporter: + externalObjects: {} + serializedVersion: 2 + defaultReferences: [] + executionOrder: 0 + icon: {instanceID: 0} + userData: + assetBundleName: + assetBundleVariant: diff --git a/Assets/CollectionsExt/GraphUtility.cs b/Assets/CollectionsExt/GraphUtility.cs new file mode 100644 index 0000000..f0f9dfb --- /dev/null +++ b/Assets/CollectionsExt/GraphUtility.cs @@ -0,0 +1,13 @@ +using System.Collections;
+using System.Collections.Generic;
+using UnityEngine;
+
+namespace CollectionsExt
+{
+
+ public static class GraphUtility
+ {
+
+ }
+
+}
diff --git a/Assets/CollectionsExt/GraphUtility.cs.meta b/Assets/CollectionsExt/GraphUtility.cs.meta new file mode 100644 index 0000000..90acebd --- /dev/null +++ b/Assets/CollectionsExt/GraphUtility.cs.meta @@ -0,0 +1,11 @@ +fileFormatVersion: 2 +guid: 3f941530f721cda449eab3504920060e +MonoImporter: + externalObjects: {} + serializedVersion: 2 + defaultReferences: [] + executionOrder: 0 + icon: {instanceID: 0} + userData: + assetBundleName: + assetBundleVariant: diff --git a/Assets/CollectionsExt/IndexedSet.cs b/Assets/CollectionsExt/IndexedSet.cs new file mode 100644 index 0000000..9a9d865 --- /dev/null +++ b/Assets/CollectionsExt/IndexedSet.cs @@ -0,0 +1,162 @@ +using System; +using System.Collections; +using System.Collections.Generic; + +namespace CollectionsExt +{
+ // ҪƵʵIJ롢ɾеΨһݣʹṹȵListЧʸߣΪ
+ // ϣķʱO(1)ҪڱListȷΨһԵʱO(n) + + // ռ任ʱ䣬ۺlist飩ֵ䣨ϣŵ㣬֧ + // 1. ٵ + // 2. ٵIJɾ + // 3. Ψһֵ + // 4. ˳ + // 5. + internal class IndexedSet<T> : IList<T> + { + //This is a container that gives: + // - Unique items + // - Fast random removal + // - Fast unique inclusion to the end + // - Sequential access + //Downsides: + // - Uses more memory + // - Ordering is not persistent + // - Not Serialization Friendly. + + //We use a Dictionary to speed up list lookup, this makes it cheaper to guarantee no duplicates (set) + //When removing we move the last item to the removed item position, this way we only need to update the index cache of a single item. (fast removal) + //Order of the elements is not guaranteed. A removal will change the order of the items. + + readonly List<T> m_List = new List<T>(); + Dictionary<T, int> m_Dictionary = new Dictionary<T, int>(); + + public void Add(T item) + { + m_List.Add(item); + m_Dictionary.Add(item, m_List.Count - 1); + } + + public bool AddUnique(T item) + { + if (m_Dictionary.ContainsKey(item)) + return false; + + m_List.Add(item); + m_Dictionary.Add(item, m_List.Count - 1); + + return true; + } + + public bool Remove(T item) + { + int index = -1; + if (!m_Dictionary.TryGetValue(item, out index)) + return false; + + RemoveAt(index); + return true; + } + + public IEnumerator<T> GetEnumerator() + { + throw new System.NotImplementedException(); + } + + IEnumerator IEnumerable.GetEnumerator() + { + return GetEnumerator(); + } + + public void Clear() + { + m_List.Clear(); + m_Dictionary.Clear(); + } + + public bool Contains(T item) + { + return m_Dictionary.ContainsKey(item); + } + + public void CopyTo(T[] array, int arrayIndex) + { + m_List.CopyTo(array, arrayIndex); + } + + public int Count { get { return m_List.Count; } } + public bool IsReadOnly { get { return false; } } + public int IndexOf(T item) + { + int index = -1; + m_Dictionary.TryGetValue(item, out index); + return index; + } + + public void Insert(int index, T item) + { + //We could support this, but the semantics would be weird. Order is not guaranteed.. + throw new NotSupportedException("Random Insertion is semantically invalid, since this structure does not guarantee ordering."); + } + + public void RemoveAt(int index) + { + T item = m_List[index]; + m_Dictionary.Remove(item); + if (index == m_List.Count - 1) + m_List.RemoveAt(index); + else + { + // + int replaceItemIndex = m_List.Count - 1; + T replaceItem = m_List[replaceItemIndex]; + m_List[index] = replaceItem; + m_Dictionary[replaceItem] = index; + m_List.RemoveAt(replaceItemIndex); + } + } + + public T this[int index] + { + get { return m_List[index]; } + set + { + T item = m_List[index]; + m_Dictionary.Remove(item); + m_List[index] = value; + m_Dictionary.Add(item, index); // ⣬Ӧvalue + } + } + + public void RemoveAll(Predicate<T> match) + { + //I guess this could be optmized by instead of removing the items from the list immediatly, + //We move them to the end, and then remove all in one go. + //But I don't think this is going to be the bottleneck, so leaving as is for now. + int i = 0; + while (i < m_List.Count) + { + T item = m_List[i]; + if (match(item)) + Remove(item); + else + i++; + } + } + + //Sorts the internal list, this makes the exposed index accessor sorted as well. + //But note that any insertion or deletion, can unorder the collection again. + public void Sort(Comparison<T> sortLayoutFunction) + { + //There might be better ways to sort and keep the dictionary index up to date. + m_List.Sort(sortLayoutFunction); + //Rebuild the dictionary index. + for (int i = 0; i < m_List.Count; ++i) + { + T item = m_List[i]; + m_Dictionary[item] = i; + } + } + } +} diff --git a/Assets/CollectionsExt/IndexedSet.cs.meta b/Assets/CollectionsExt/IndexedSet.cs.meta new file mode 100644 index 0000000..1f6bc6d --- /dev/null +++ b/Assets/CollectionsExt/IndexedSet.cs.meta @@ -0,0 +1,11 @@ +fileFormatVersion: 2 +guid: 4c58c0d2f281bac479b6b45c68043671 +MonoImporter: + externalObjects: {} + serializedVersion: 2 + defaultReferences: [] + executionOrder: 0 + icon: {instanceID: 0} + userData: + assetBundleName: + assetBundleVariant: diff --git a/Assets/CollectionsExt/MaxHeap.cs b/Assets/CollectionsExt/MaxHeap.cs new file mode 100644 index 0000000..09066f1 --- /dev/null +++ b/Assets/CollectionsExt/MaxHeap.cs @@ -0,0 +1,158 @@ +using System; +using System.Collections.Generic; + +namespace CollectionsExt +{ + // 最大堆 + public class MaxHeap<T> + { + private const int InitialCapacity = 4; + + private T[] _arr; + private int _lastItemIndex; + private IComparer<T> _comparer; + + public MaxHeap() + : this(InitialCapacity, Comparer<T>.Default) + { + } + + public MaxHeap(int capacity) + : this(capacity, Comparer<T>.Default) + { + } + + public MaxHeap(Comparison<T> comparison) + : this(InitialCapacity, Comparer<T>.Create(comparison)) + { + } + + public MaxHeap(IComparer<T> comparer) + : this(InitialCapacity, comparer) + { + } + + public MaxHeap(int capacity, IComparer<T> comparer) + { + _arr = new T[capacity]; + _lastItemIndex = -1; + _comparer = comparer; + } + + public int Count + { + get + { + return _lastItemIndex + 1; + } + } + + public void Add(T item) + { + if (_lastItemIndex == _arr.Length - 1) + { + Resize(); + } + + _lastItemIndex++; + _arr[_lastItemIndex] = item; + + MaxHeapifyUp(_lastItemIndex); + } + + public T Remove() + { + if (_lastItemIndex == -1) + { + throw new InvalidOperationException("The heap is empty"); + } + + T removedItem = _arr[0]; + _arr[0] = _arr[_lastItemIndex]; + _lastItemIndex--; + + MaxHeapifyDown(0); + + return removedItem; + } + + public T Peek() + { + if (_lastItemIndex == -1) + { + throw new InvalidOperationException("The heap is empty"); + } + + return _arr[0]; + } + + public void Clear() + { + _lastItemIndex = -1; + } + + // 堆顶是最小值 + private void MaxHeapifyUp(int index) + { + if (index == 0) + { + return; + } + + int childIndex = index; + int parentIndex = (index - 1) / 2; + + // 堆顶是最小值 + if (_comparer.Compare(_arr[childIndex], _arr[parentIndex]) > 0) + { + // swap the parent and the child + T temp = _arr[childIndex]; + _arr[childIndex] = _arr[parentIndex]; + _arr[parentIndex] = temp; + + // 递归 + MaxHeapifyUp(parentIndex); + } + } + + private void MaxHeapifyDown(int index) + { + int leftChildIndex = index * 2 + 1; + int rightChildIndex = index * 2 + 2; + int biggestItemIndex = index; // The index of the parent + + if (leftChildIndex <= _lastItemIndex && + _comparer.Compare(_arr[leftChildIndex], _arr[biggestItemIndex]) > 0) + { + biggestItemIndex = leftChildIndex; + } + + if (rightChildIndex <= _lastItemIndex && + _comparer.Compare(_arr[rightChildIndex], _arr[biggestItemIndex]) < 0) + { + biggestItemIndex = rightChildIndex; + } + + if (biggestItemIndex != index) + { + // swap the parent with the biggest of the child items + T temp = _arr[index]; + _arr[index] = _arr[biggestItemIndex]; + _arr[biggestItemIndex] = temp; + + MaxHeapifyDown(biggestItemIndex); + } + } + + private void Resize() + { + T[] newArr = new T[_arr.Length * 2]; + for (int i = 0; i < _arr.Length; i++) + { + newArr[i] = _arr[i]; + } + + _arr = newArr; + } + } +} diff --git a/Assets/CollectionsExt/MaxHeap.cs.meta b/Assets/CollectionsExt/MaxHeap.cs.meta new file mode 100644 index 0000000..b15e928 --- /dev/null +++ b/Assets/CollectionsExt/MaxHeap.cs.meta @@ -0,0 +1,11 @@ +fileFormatVersion: 2 +guid: 807a3d1c83110494bb638cb588b062b2 +MonoImporter: + externalObjects: {} + serializedVersion: 2 + defaultReferences: [] + executionOrder: 0 + icon: {instanceID: 0} + userData: + assetBundleName: + assetBundleVariant: diff --git a/Assets/CollectionsExt/MinHeap.cs b/Assets/CollectionsExt/MinHeap.cs new file mode 100644 index 0000000..68ddabb --- /dev/null +++ b/Assets/CollectionsExt/MinHeap.cs @@ -0,0 +1,160 @@ +using System; +using System.Collections.Generic; + +namespace CollectionsExt +{ + // 最小堆，堆顶是最小值。 + // 如果需要维护一个优先队列，用堆结构，调堆的效率是O(logn)快于遍历的O(n) + public class MinHeap<T> + { + private const int InitialCapacity = 4; + + private T[] _arr; + private int _lastItemIndex; + private IComparer<T> _comparer; + + public MinHeap() + : this(InitialCapacity, Comparer<T>.Default) + { + } + + public MinHeap(int capacity) + : this(capacity, Comparer<T>.Default) + { + } + + public MinHeap(Comparison<T> comparison) + : this(InitialCapacity, Comparer<T>.Create(comparison)) + { + } + + public MinHeap(IComparer<T> comparer) + : this(InitialCapacity, comparer) + { + } + + public MinHeap(int capacity, IComparer<T> comparer) + { + _arr = new T[capacity]; + _lastItemIndex = -1; + _comparer = comparer; + } + + public int Count + { + get + { + return _lastItemIndex + 1; + } + } + + public void Add(T item) + { + if (_lastItemIndex == _arr.Length - 1) + { + Resize(); + } + + _lastItemIndex++; + _arr[_lastItemIndex] = item; + + MinHeapifyUp(_lastItemIndex); + } + + public T Remove() + { + if (_lastItemIndex == -1) + { + throw new InvalidOperationException("The heap is empty"); + } + + T removedItem = _arr[0]; + _arr[0] = _arr[_lastItemIndex]; + _lastItemIndex--; + + MinHeapifyDown(0); + + return removedItem; + } + + public T Peek() + { + if (_lastItemIndex == -1) + { + throw new InvalidOperationException("The heap is empty"); + } + + return _arr[0]; + } + + public void Clear() + { + _lastItemIndex = -1; + } + + // 调堆,O(logn) + private void MinHeapifyUp(int index) + { + if (index == 0) + { + return; + } + + int childIndex = index; + int parentIndex = (index - 1) / 2; + + // 堆顶是最小值 + if (_comparer.Compare(_arr[childIndex], _arr[parentIndex]) < 0) + { + // swap the parent and the child + T temp = _arr[childIndex]; + _arr[childIndex] = _arr[parentIndex]; + _arr[parentIndex] = temp; + + // 递归 + MinHeapifyUp(parentIndex); + } + } + + // 调堆,O(logn) + private void MinHeapifyDown(int index) + { + int leftChildIndex = index * 2 + 1; + int rightChildIndex = index * 2 + 2; + int smallestItemIndex = index; // The index of the parent + + if (leftChildIndex <= _lastItemIndex && + _comparer.Compare(_arr[leftChildIndex], _arr[smallestItemIndex]) < 0) + { + smallestItemIndex = leftChildIndex; + } + + if (rightChildIndex <= _lastItemIndex && + _comparer.Compare(_arr[rightChildIndex], _arr[smallestItemIndex]) < 0) + { + smallestItemIndex = rightChildIndex; + } + + if (smallestItemIndex != index) + { + // swap the parent with the smallest of the child items + T temp = _arr[index]; + _arr[index] = _arr[smallestItemIndex]; + _arr[smallestItemIndex] = temp; + + MinHeapifyDown(smallestItemIndex); + } + } + + private void Resize() + { + T[] newArr = new T[_arr.Length * 2]; + for (int i = 0; i < _arr.Length; i++) + { + newArr[i] = _arr[i]; + } + + _arr = newArr; + } + } +} diff --git a/Assets/CollectionsExt/MinHeap.cs.meta b/Assets/CollectionsExt/MinHeap.cs.meta new file mode 100644 index 0000000..d06ef93 --- /dev/null +++ b/Assets/CollectionsExt/MinHeap.cs.meta @@ -0,0 +1,11 @@ +fileFormatVersion: 2 +guid: 7957fc1b317c31b4f94f56d48073da22 +MonoImporter: + externalObjects: {} + serializedVersion: 2 + defaultReferences: [] + executionOrder: 0 + icon: {instanceID: 0} + userData: + assetBundleName: + assetBundleVariant: diff --git a/Assets/CollectionsExt/SkipList.cs b/Assets/CollectionsExt/SkipList.cs new file mode 100644 index 0000000..5320f0b --- /dev/null +++ b/Assets/CollectionsExt/SkipList.cs @@ -0,0 +1,18 @@ +using System.Collections;
+using System.Collections.Generic;
+using UnityEngine;
+
+public class SkipList : MonoBehaviour
+{
+ // Start is called before the first frame update
+ void Start()
+ {
+
+ }
+
+ // Update is called once per frame
+ void Update()
+ {
+
+ }
+}
diff --git a/Assets/CollectionsExt/SkipList.cs.meta b/Assets/CollectionsExt/SkipList.cs.meta new file mode 100644 index 0000000..0caa332 --- /dev/null +++ b/Assets/CollectionsExt/SkipList.cs.meta @@ -0,0 +1,11 @@ +fileFormatVersion: 2 +guid: a6e7d17f852ca7444869bdd26f25d4d0 +MonoImporter: + externalObjects: {} + serializedVersion: 2 + defaultReferences: [] + executionOrder: 0 + icon: {instanceID: 0} + userData: + assetBundleName: + assetBundleVariant: diff --git a/Assets/Test/05_Recursion/Test_Recursion.cs b/Assets/Test/05_Recursion/Test_Recursion.cs index 9399bc3..830d2df 100644 --- a/Assets/Test/05_Recursion/Test_Recursion.cs +++ b/Assets/Test/05_Recursion/Test_Recursion.cs @@ -16,7 +16,9 @@ public class Test_Recursion : MonoBehaviour //TestMergeSort();
//TestQuickSort();
//TestBubbleSort();
- TestSelect();
+ //TestSelect();
+ //TestLCS();
+ TestMaxSum();
}
void TestPermutations()
@@ -154,4 +156,22 @@ public class Test_Recursion : MonoBehaviour }
}
+ void TestLCS()
+ {
+ List<char> lcs = new List<char>();
+ RecursionHelper.FindLCSP("acbcbcef".ToCharArray(), "abcbced".ToCharArray(), ref lcs);
+ Debug.Log(Algorithms.ListToString(lcs));
+
+ lcs.Clear();
+ RecursionHelper.FindLCSS("acbcbcef".ToCharArray(), "abcbced".ToCharArray(), ref lcs);
+ Debug.Log(Algorithms.ListToString(lcs));
+ }
+
+ void TestMaxSum()
+ {
+ int[] n = new int[] { -2, 11, -4, 13, -5, -2};
+ int max = RecursionHelper.CalMaxSum(n);
+ Debug.Log("最大子段和=" + max);
+ }
+
}
|