0618学习

agile Posted on Jun 20 2023

面试 leetcode学习

-   链表和数组的区别
链表和数组是两种常见的数据结构，它们在存储和访问数据方面有着不同的特点。

---

存储方式：
数组：数组是一种连续的内存块，用于存储相同类型的元素。在内存中，数组的元素按照索引顺序排列。
链表：链表由节点组成，每个节点包含存储的元素和指向下一个节点的指针。节点在内存中可以是非连续的，它们通过指针链接在一起。

---

插入和删除操作：

数组：在数组中插入或删除元素通常需要移动其他元素来腾出空间或填补空缺。这是因为数组的元素是连续存储的，所以需要进行数据的搬移操作。
链表：链表的插入和删除操作相对简单。插入元素时，只需调整节点的指针即可，不需要移动其他节点。删除元素时，只需更新相邻节点的指针即可。
访问元素：

数组：通过索引可以直接访问数组中的任意元素，因为数组中的元素是按照索引顺序存储的。
链表：链表需要从头节点开始逐个遍历，直到找到目标节点。这意味着在链表中访问元素的时间复杂度是O(n)，其中n是链表的长度。

---
内存空间的使用：

数组：数组在内存中需要一段连续的空间来存储元素，如果数组的大小提前确定，则需要分配一块足够大的连续内存空间。
链表：链表的节点可以在内存中分布在不同的位置，因此链表不需要一块连续的内存空间。每个节点只需要额外的指针来指向下一个节点。
综上所述，数组适合在需要频繁访问元素、已知大小且需要随机访问的情况下使用。链表适用于频繁插入和删除元素的场景，或者在大小不确定且只需按顺序访问元素的情况下使用。选择使用哪种数据结构要根据具体的需求和操作来决定

---

-   List能否替代Array
List<T>为Array的可扩充版本,如果初始化时确定大小，那么就使用Array.如果初始化时不确定大小，那么就使用List。当然，其实完全可以自己去实现List中的数组扩充功能的，也许会更棒，因为我们没有必要去将Array每次都扩充为原来的二倍

---

-   动态数组
```C#
using System.Collections;
using System.Diagnostics;

namespace DynamicArray;

public class DynamicArray<T> : ICollection<T>
{
    private T[] _array;
    private const int DefaultCapacity = 4;
    public int Size { get; private set; }
    public bool IsReadOnly { get; } = false;
    private int _capacity = 0;
    public int Count => Size;

public T this[int index]
    {
        get
        {
            Debug.Assert(index < Size);
            return _array[index];
        }
        set
        {
            Debug.Assert(index < Size);
            _array[index] = value;
        }
    }

public int Capacity
    {
        get => _capacity;
        set
        {
            Debug.Assert(value >= Size);
            _capacity = value;
            if (_capacity == _array.Length) return;
            if (_capacity > 0)
            {
                var t = new T[_capacity];
                if (Size > 0)
                {
                    Array.Copy(_array, t, Size);
                }

_array = t;
            }
            else
            {
                _array = Array.Empty<T>();
            }
        }
    }

public DynamicArray()
    {
        _array = Array.Empty<T>();
    }

private void Grow()
    {
        var newCapacity = _array.Length == 0 ? DefaultCapacity : _array.Length * 2;
        Capacity = newCapacity;
    }

public IEnumerator<T> GetEnumerator()
    {
        for (var i = 0; i < Size; i++)
        {
            yield return _array[i];
        }
    }

IEnumerator IEnumerable.GetEnumerator()
    {
        return GetEnumerator();
    }

public void Add(T item)
    {
        if (Size == _array.Length)
        {
            Grow();
        }

_array[Size++] = item;
    }

public void Clear()
    {
        if (Size <= 0) return;
        Array.Clear(_array, 0, _array.Length);
        Size = 0;
    }

public bool Contains(T item)
    {
        if (Size > 0)
        {
            return Array.IndexOf(_array, item, 0, Size) >= 0;
        }

return false;
    }

public void CopyTo(T[] array, int arrayIndex)
    {
        Array.Copy(_array, 0, array, arrayIndex, Size);
    }

public bool Remove(T item)
    {
        if (Size > 0)
        {
            var index = Array.IndexOf(_array, item, 0, Size);
            if (index >= 0)
            {
                Size--;
                if (index < Size)
                {
                    Array.Copy(_array, index + 1, _array, index, Size - index);
                }
                else
                {
                    _array[index] = default!;
                }
            }
        }

return false;
    }
}
```