From dbcd0c269014100b7d4cc421c5ab518f275cca09 Mon Sep 17 00:00:00 2001 From: chai Date: Thu, 24 Jun 2021 19:55:26 +0800 Subject: *misc --- Assets/Algorithms/Algebra/Linear.cs | 13 +- Assets/Algorithms/Algebra/MatrixUtils.cs | 13 ++ Assets/Algorithms/Algebra/MatrixUtils.cs.meta | 11 ++ Assets/Algorithms/Algebra/Vector3Utils.cs | 13 ++ Assets/Algorithms/Algebra/Vector3Utils.cs.meta | 11 ++ Assets/Algorithms/Algorithms.cs | 13 +- Assets/Algorithms/Algorithms_Utils.cs | 31 ++++ Assets/Algorithms/Algorithms_Utils.cs.meta | 11 ++ Assets/Algorithms/Geometry/GeometryHelper.cs | 19 +-- Assets/Algorithms/PathFinding/AStarPathfinding.cs | 31 ++-- .../Algorithms/PathFinding/DijkstraPathfinding.cs | 13 ++ .../PathFinding/DijkstraPathfinding.cs.meta | 11 ++ Assets/Algorithms/Recursion/Recursion_DP.cs | 2 + Assets/Algorithms/Recursion/Recursion_Greedy.cs | 15 ++ .../Algorithms/Recursion/Recursion_Greedy.cs.meta | 11 ++ Assets/Algorithms/Searching/SearchingHelper.cs | 4 +- Assets/CollectionsExt.meta | 8 + Assets/CollectionsExt/BinarySearchTree.cs | 18 +++ Assets/CollectionsExt/BinarySearchTree.cs.meta | 11 ++ Assets/CollectionsExt/GraphUtility.cs | 13 ++ Assets/CollectionsExt/GraphUtility.cs.meta | 11 ++ Assets/CollectionsExt/IndexedSet.cs | 162 +++++++++++++++++++++ Assets/CollectionsExt/IndexedSet.cs.meta | 11 ++ Assets/CollectionsExt/MaxHeap.cs | 158 ++++++++++++++++++++ Assets/CollectionsExt/MaxHeap.cs.meta | 11 ++ Assets/CollectionsExt/MinHeap.cs | 160 ++++++++++++++++++++ Assets/CollectionsExt/MinHeap.cs.meta | 11 ++ Assets/CollectionsExt/SkipList.cs | 18 +++ Assets/CollectionsExt/SkipList.cs.meta | 11 ++ Assets/Common.meta | 8 - Assets/Test/04_Pathfinding/AStarPathfinding.cs | 18 --- .../Test/04_Pathfinding/AStarPathfinding.cs.meta | 11 -- Assets/Test/05_Recursion/Test_Recursion.cs | 22 ++- 33 files changed, 807 insertions(+), 77 deletions(-) create mode 100644 Assets/Algorithms/Algebra/MatrixUtils.cs create mode 100644 Assets/Algorithms/Algebra/MatrixUtils.cs.meta create mode 100644 Assets/Algorithms/Algebra/Vector3Utils.cs create mode 100644 Assets/Algorithms/Algebra/Vector3Utils.cs.meta create mode 100644 Assets/Algorithms/Algorithms_Utils.cs create mode 100644 Assets/Algorithms/Algorithms_Utils.cs.meta create mode 100644 Assets/Algorithms/PathFinding/DijkstraPathfinding.cs create mode 100644 Assets/Algorithms/PathFinding/DijkstraPathfinding.cs.meta create mode 100644 Assets/Algorithms/Recursion/Recursion_Greedy.cs create mode 100644 Assets/Algorithms/Recursion/Recursion_Greedy.cs.meta create mode 100644 Assets/CollectionsExt.meta create mode 100644 Assets/CollectionsExt/BinarySearchTree.cs create mode 100644 Assets/CollectionsExt/BinarySearchTree.cs.meta create mode 100644 Assets/CollectionsExt/GraphUtility.cs create mode 100644 Assets/CollectionsExt/GraphUtility.cs.meta create mode 100644 Assets/CollectionsExt/IndexedSet.cs create mode 100644 Assets/CollectionsExt/IndexedSet.cs.meta create mode 100644 Assets/CollectionsExt/MaxHeap.cs create mode 100644 Assets/CollectionsExt/MaxHeap.cs.meta create mode 100644 Assets/CollectionsExt/MinHeap.cs create mode 100644 Assets/CollectionsExt/MinHeap.cs.meta create mode 100644 Assets/CollectionsExt/SkipList.cs create mode 100644 Assets/CollectionsExt/SkipList.cs.meta delete mode 100644 Assets/Common.meta delete mode 100644 Assets/Test/04_Pathfinding/AStarPathfinding.cs delete mode 100644 Assets/Test/04_Pathfinding/AStarPathfinding.cs.meta 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/Algorithms/Algebra/MatrixUtils.cs.meta b/Assets/Algorithms/Algebra/MatrixUtils.cs.meta new file mode 100644 index 0000000..1ac378e --- /dev/null +++ b/Assets/Algorithms/Algebra/MatrixUtils.cs.meta @@ -0,0 +1,11 @@ +fileFormatVersion: 2 +guid: bb506f4381cf42643a1d968c52ec0bae +MonoImporter: + externalObjects: {} + serializedVersion: 2 + defaultReferences: [] + executionOrder: 0 + icon: {instanceID: 0} + userData: + assetBundleName: + assetBundleVariant: 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 v1, T v2) where T : IComparable + { + return v1.CompareTo(v2) > 0 ? v1 : v2; + } + public static string ListToString(List 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 lut = new Dictionary(); + 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(List data, T value) where T : IComparable, IEquatable { 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/CollectionsExt.meta b/Assets/CollectionsExt.meta new file mode 100644 index 0000000..73f47c5 --- /dev/null +++ b/Assets/CollectionsExt.meta @@ -0,0 +1,8 @@ +fileFormatVersion: 2 +guid: 82a401f8a530ccd4d9e3eb3bf23bf708 +folderAsset: yes +DefaultImporter: + externalObjects: {} + userData: + assetBundleName: + assetBundleVariant: diff --git a/Assets/CollectionsExt/BinarySearchTree.cs b/Assets/CollectionsExt/BinarySearchTree.cs new file mode 100644 index 0000000..ef6118a --- /dev/null +++ b/Assets/CollectionsExt/BinarySearchTree.cs @@ -0,0 +1,18 @@ +using System.Collections; +using System.Collections.Generic; +using UnityEngine; + +public class BinarySearchTree : MonoBehaviour +{ + // Start is called before the first frame update + void Start() + { + + } + + // Update is called once per frame + void Update() + { + + } +} 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 : IList + { + //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 m_List = new List(); + Dictionary m_Dictionary = new Dictionary(); + + 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 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 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 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 + { + private const int InitialCapacity = 4; + + private T[] _arr; + private int _lastItemIndex; + private IComparer _comparer; + + public MaxHeap() + : this(InitialCapacity, Comparer.Default) + { + } + + public MaxHeap(int capacity) + : this(capacity, Comparer.Default) + { + } + + public MaxHeap(Comparison comparison) + : this(InitialCapacity, Comparer.Create(comparison)) + { + } + + public MaxHeap(IComparer comparer) + : this(InitialCapacity, comparer) + { + } + + public MaxHeap(int capacity, IComparer 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 + { + private const int InitialCapacity = 4; + + private T[] _arr; + private int _lastItemIndex; + private IComparer _comparer; + + public MinHeap() + : this(InitialCapacity, Comparer.Default) + { + } + + public MinHeap(int capacity) + : this(capacity, Comparer.Default) + { + } + + public MinHeap(Comparison comparison) + : this(InitialCapacity, Comparer.Create(comparison)) + { + } + + public MinHeap(IComparer comparer) + : this(InitialCapacity, comparer) + { + } + + public MinHeap(int capacity, IComparer 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/Common.meta b/Assets/Common.meta deleted file mode 100644 index ab81fd0..0000000 --- a/Assets/Common.meta +++ /dev/null @@ -1,8 +0,0 @@ -fileFormatVersion: 2 -guid: 5629771d46311c14e9adb024edfab837 -folderAsset: yes -DefaultImporter: - externalObjects: {} - userData: - assetBundleName: - assetBundleVariant: diff --git a/Assets/Test/04_Pathfinding/AStarPathfinding.cs b/Assets/Test/04_Pathfinding/AStarPathfinding.cs deleted file mode 100644 index 80ba51d..0000000 --- a/Assets/Test/04_Pathfinding/AStarPathfinding.cs +++ /dev/null @@ -1,18 +0,0 @@ -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() - { - - } -} diff --git a/Assets/Test/04_Pathfinding/AStarPathfinding.cs.meta b/Assets/Test/04_Pathfinding/AStarPathfinding.cs.meta deleted file mode 100644 index 5cd6112..0000000 --- a/Assets/Test/04_Pathfinding/AStarPathfinding.cs.meta +++ /dev/null @@ -1,11 +0,0 @@ -fileFormatVersion: 2 -guid: 66158ef978f1a7540addceae83d08239 -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 lcs = new List(); + 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); + } + } -- cgit v1.1-26-g67d0