0630学习

agile Posted on Jun 30 2023

面试 leetcode学习

-   剑指 Offer 09. 用两个栈实现队列

```C#
public class CQueue
{
    private Stack<int> __AppendStack = new Stack<int>();
    private Stack<int> __DeleteStack = new Stack<int>();

public CQueue()
    {
    }

public void AppendTail(int value)
    {
        __AppendStack.Push(value);
    }

public int DeleteHead()
    {
        if (__DeleteStack.Count > 0)
        {
            return __DeleteStack.Pop();
        }

while (__AppendStack.Count > 0)
        {
            __DeleteStack.Push(__AppendStack.Pop());
        }

return __DeleteStack.Count > 0 ? __DeleteStack.Pop() : -1;
    }
}
```

---

-   剑指 Offer 30. 包含min函数的栈

```C#
public class MinStack
{
    private Stack<int> __AppendStack = new Stack<int>();
    private Stack<int> __MinStack = new Stack<int>();

/** initialize your data structure here. */
    public MinStack()
    {
    }

private bool __IsEmpty()
    {
        return __AppendStack.Count == 0;
    }

public void Push(int x)
    {
        var min = x;
        if (!__IsEmpty())
        {
            min = __MinStack.Peek();
            if (x < min)
            {
                min = x;
            }
        }
        __AppendStack.Push(x);
        __MinStack.Push(min);
    }

public void Pop()
    {
        if (__IsEmpty())
        {
            throw new Exception("Is Empty!!!");
        }

__AppendStack.Pop();
        __MinStack.Pop();
    }

public int Top()
    {
        if (__IsEmpty())
        {
            throw new Exception("Is Empty!!!");
        }

return __AppendStack.Peek();
    }

public int Min()
    {
        if (__IsEmpty())
        {
            throw new Exception("Is Empty!!!");
        }

return __MinStack.Peek();
    }
}
```

-   剑指 Offer 06. 从尾到头打印链表

```C#
private int __length = 0;

public int[] ReversePrint(ListNode head)
{
    if (head == null)
    {
        return Array.Empty<int>();
    }

__Traverse(head, out var result);
    return result;
}

private void __Traverse(ListNode r, out int[] result)
{
    if (r == null)
    {
        result = new int[__length];
        return;
    }

__length++;
    var index = __length - 1;
    __Traverse(r.next, out result);
    result[__length - 1 - index] = r.val;
}
```

-   剑指 Offer 24. 反转链表
定义一个函数，输入一个链表的头节点，反转该链表并输出反转后链表的头节点。

---

```C#
//递归(单指针)
public ListNode ReverseList(ListNode head)
{
    if (head == null || head.next == null)
    {
        return head;
    }
    
    // 1,2,3,4,5
    //当head为5的情况走不到这里逻辑
    //当head为4则，head.next为5
    var next = head.next; //暂存下一个节点，也就是暂存5
    var last = ReverseList(next);
    head.next = null; //4指向5的指向应该去掉
    next.next = head;//设置5指向4
    return last;
}

//递归(双指针)
public ListNode ReverseList2(ListNode head)
{
    return __Traverse(head, null);
}

private ListNode __Traverse(ListNode cur, ListNode pre)
{
    if (cur == null)
    {
        return pre;
    }

var last = __Traverse(cur.next, cur);
    cur.next = pre;
    return last;
}

//迭代(双指针)
public ListNode ReverseList3(ListNode head)
{
    var cur = head;
    ListNode pre = null;
    while (cur != null)
    {
        var temp = cur.next; // 暂存下一个节点
        cur.next = pre; //下一个节点指向先前节点
        pre = cur; //先前节点指向当前节点
        cur = temp; //当前节点指向下一个节点
    }

return pre;
}
```

-   剑指 Offer 35. 复杂链表的复制
请实现`copyRandomList`函数，复制一个复杂链表。在复杂链表中，每个节点除了有一个`next`指针指向下一个节点，还有一个`random`指针指向链表中的任意节点或者`null`。

```C#
public Node CopyRandomList(Node head)
{
    if (head == null)
    {
        return null;
    }

var nodes = new Dictionary<Node, Node>();
    var newHead = new Node(head.val);
    nodes.Add(head, newHead);
    var newPre = newHead;
    __TraverseList(nodes, head.next, newPre);
    if (head.random != null)
    {
        var newRandom = nodes[head.random];
        newHead.random = newRandom;
    }

return newHead;
}

private void __TraverseList(Dictionary<Node, Node> nodes, Node node, Node newNodePre)
{
    if (node == null)
    {
        return;
    }

var newNext = new Node(node.val);
    newNodePre.next = newNext;
    nodes[node] = newNext;
    __TraverseList(nodes, node.next, newNext);
    if (node.random != null)
    {
        var newRandom = nodes[node.random];
        newNext.random = newRandom;
    }
}

//A=>CopyA=>B=>CopyB
public Node CopyRandomList2(Node head)
{
    if (head == null)
    {
        return null;
    }

__TraverseList2(head);
    var root = head.next;
    var pre = head;
    var cur = head.next;
    while (cur.next != null)
    {
        pre.next = cur.next;
        pre = cur.next;
        cur.next = pre.next;
        cur = pre.next;
    }

pre.next = null;

return root;
}

private void __TraverseList2(Node n)
{
    if (n == null)
    {
        return;
    }

var nNext = n.next;
    var copy = new Node(n.val)
    {
        next = nNext
    };
    n.next = copy;
    __TraverseList2(nNext);
    n.next.random = n.random == null ? null : n.random.next;
}

private Dictionary<Node, Node> __dic = new Dictionary<Node, Node>();

//递归
public Node CopyRandomList3(Node head)
{
    if (head == null)
    {
        return null;
    }

if (!__dic.TryGetValue(head, out var v))
    {
        v = new Node(head.val);
        __dic[head] = v;
        v.next = CopyRandomList3(head.next);
        v.random = CopyRandomList3(head.random);
    }

return v;
}
```