用两个栈实现队列

Link

用两个栈实现一个队列。队列的声明如下,请实现它的两个函数 appendTail 和 deleteHead ,分别完成在队列尾部插入整数和在队列头部删除整数的功能。(若队列中没有元素,deleteHead 操作返回 -1 )

示例 1:

输入:
[“CQueue”,”appendTail”,”deleteHead”,”deleteHead”]
[[],[3],[],[]]
输出:[null,null,3,-1]

示例 2:

输入
[“CQueue”,”deleteHead”,”appendTail”,”appendTail”,”deleteHead”,”deleteHead”]
[[],[],[5],[2],[],[]]
输出:[null,-1,null,null,5,2]

提示:

  • 1 <= values <= 10000
  • 最多会对 appendTail、deleteHead 进行 10000 次调用

代码实现

public class CQueue 
{
    //一个队列为插入数据,一个队列为弹出数据作为删除操作
    private Stack<int> stack1;
    private Stack<int> stack2;

    public CQueue() 
    {
        stack1 = new Stack<int>();
        stack2 = new Stack<int>();
    }
    
    public void AppendTail(int value) 
    {
        stack1.Push(value);
    }
    
    public int DeleteHead() 
    {
        if(stack2.Count != 0)
        {
            return stack2.Pop();
        }
        else
        {
            while(stack1.Count != 0)
            {
                stack2.Push(stack1.Pop());
            }
            return stack2.Count == 0 ? -1 : stack2.Pop();
        }
    }
}

/**
 * Your CQueue object will be instantiated and called as such:
 * CQueue obj = new CQueue();
 * obj.AppendTail(value);
 * int param_2 = obj.DeleteHead();
 */

包含min函数的栈

Link

定义栈的数据结构,请在该类型中实现一个能够得到栈的最小元素的 min 函数在该栈中,调用 min、push 及 pop 的时间复杂度都是 O(1)。

示例:

MinStack minStack = new MinStack();
minStack.push(-2);
minStack.push(0);
minStack.push(-3);
minStack.min(); –> 返回 -3.
minStack.pop();
minStack.top(); –> 返回 0.
minStack.min(); –> 返回 -2.

提示:

各函数的调用总次数不超过 20000 次

代码实现:

public class MinStack 
{
    private Stack<int> A;
    //难点:B为辅助栈作为存放最小元素
    private Stack<int> B;

    /** initialize your data structure here. */
    public MinStack() 
    {
        A = new Stack<int>();
        B = new Stack<int>();
    }
    
    public void Push(int x) {
        A.Push(x);
        //辅助栈空或辅助栈栈顶元素大于等于x
        if(B.Count == 0 || B.Peek()>=x)
        {
            B.Push(x);
        }
    }
    
    public void Pop() 
    {
        var y = A.Pop();
        if(y == B.Peek())
        {
            B.Pop();
        }
    }
    
    public int Top() 
    {
        return A.Peek();
    }
    
    public int Min() 
    {
        return B.Peek();
    }
}

/**
 * Your MinStack object will be instantiated and called as such:
 * MinStack obj = new MinStack();
 * obj.Push(x);
 * obj.Pop();
 * int param_3 = obj.Top();
 * int param_4 = obj.Min();
 */

数组中重复的数字

Link

找出数组中重复的数字。

在一个长度为 n 的数组 nums 里的所有数字都在 0~n-1 的范围内。数组中某些数字是重复的,但不知道有几个数字重复了,也不知道每个数字重复了几次。请找出数组中任意一个重复的数字。

示例 :

输入:
[2, 3, 1, 0, 2, 5, 3]
输出:2 或 3

限制:

2 <= n <= 100000

时间复杂度为O(n),题中仅需找出任意数字,则使用HashSet的特性:不重复,当检测到HashSet里面有重复数字则返回重复数字,否则就加入到HashSet中。如没有重复则返回-1

代码实现:

public class Solution 
{
    public int FindRepeatNumber(int[] nums) 
    {
        HashSet<int> dic = new HashSet<int>();
        foreach(int num in nums)
        {
            if(dic.Contains(num))
            {
                return num;
            }
            dic.Add(num);
        }
        return -1;
    }
}

替换空格

请实现一个函数,把字符串 s 中的每个空格替换成”%20”。

示例 :

输入:s = “We are happy.”
输出:”We%20are%20happy.”

限制:

0 <= s 的长度 <= 10000

string为不可变字符串。

通过StringBuilder建立为一个可变的字符串。通过char的形式检验string中的字符,并加入到可变的字符串中,时间复杂度为O(n)。

代码实现:

public class Solution {
    public string ReplaceSpace(string s) 
    {
        StringBuilder str = new StringBuilder();
        foreach(char i in s.ToCharArray())
        {
            if(i == ' ')
            {
                str.Append("%20");
            }
            else
            {
                str.Append(i);
            }
        }
        return str.ToString();
    }
}

从尾到头打印链表

Link

输入一个链表的头节点,从尾到头反过来返回每个节点的值(用数组返回)。

示例 1:

输入:head = [1,3,2]
输出:[2,3,1]

限制:

0 <= 链表长度 <= 10000

使用栈的先进后出特性实现,将链表每一个存在节点都压住栈中,并在最后以数组形式出栈。

代码实现:

/**
 * Definition for singly-linked list.
 * public class ListNode {
 *     public int val;
 *     public ListNode next;
 *     public ListNode(int x) { val = x; }
 * }
 */
public class Solution 
{
    //FILO 先进后出,当然是使用栈实现
    private Stack<int> stack;
    public int[] ReversePrint(ListNode head) 
    {
        stack = new Stack<int>();
        while(head != null)
        {
            stack.Push(head.val);
            head = head.next;
        }
        int[] res = new int[stack.Count];
        for(int i=0;stack.Count!=0;i++)
        {
            res[i] = stack.Pop();
        }
        return res;
    }
}

斐波那契数列

Link

写一个函数,输入 n ,求斐波那契(Fibonacci)数列的第 n 项(即 F(N))。斐波那契数列的定义如下:

F(0) = 0, F(1) = 1
F(N) = F(N - 1) + F(N - 2), 其中 N > 1.
斐波那契数列由 0 和 1 开始,之后的斐波那契数就是由之前的两数相加而得出。

答案需要取模 1e9+7(1000000007),如计算初始结果为:1000000008,请返回 1。

示例 1:

输入:n = 2
输出:1

示例 2:

输入:n = 5
输出:5

提示:

0 <= n <= 100

public class Solution
{
    //Fibonacci 递归法,超时
    public int Fib1(int n) 
    {
        if(n<2)
        {
            return n;
        }
        else
        {
            return Fib(n-1) + Fib(n-2);
        }
    }

    //空间换效率
    public int Fib(int n) 
    {
        if(n < 2) return n;
        int[] nums = new int[n + 1];
        nums[0] = 0;
        nums[1] = 1;
        for(int i = 2;i <= n;i++) {
            nums[i] = (nums[i - 1] + nums[i - 2]) % 1000000007;
        }
        return nums[n];
    }
}

青蛙跳台阶问题

Link

一只青蛙一次可以跳上1级台阶,也可以跳上2级台阶。求该青蛙跳上一个 n 级的台阶总共有多少种跳法。

答案需要取模 1e9+7(1000000007),如计算初始结果为:1000000008,请返回 1。

示例 1:

输入:n = 2
输出:2

示例 2:

输入:n = 7
输出:21

示例 3:

输入:n = 0
输出:1

提示:

0 <= n <= 100

这道题的思想和斐波那契很相似。

代码实现:

public class Solution 
{
    public int NumWays(int n) 
    {
        if(n<=1)
        {
            return 1;
        }
        int[] res = new int[n+1];
        res[0]=1;
        res[1]=1;

        for(int i=2;i<n+1;i++)
        {
            res[i] = (res[i-1]+res[i-2])%1000000007;
        }
        return res[n];
    }
    //由于青蛙每次只能跳一格或者两格,那么最后跳的这次确定了,
    //只需要得到第n-1阶的跳法可以得到最后一次跳一部跳到终点的种数,
    //得到第n-2阶的跳法就可以得到最后一次跳两格的跳法种数,相加即得到跳达终点的跳法数
}

删除链表中的节点

Link

给定单向链表的头指针和一个要删除的节点的值,定义一个函数删除该节点。

返回删除后的链表的头节点。

注意:此题对比书本原题有改动

示例 1:

输入: head = [4,5,1,9], val = 5
输出: [4,1,9]
解释: 给定你链表中值为 5 的第二个节点,那么在调用了你的函数之后,该链表应变为 4 -> 1 -> 9.

示例 2:

输入: head = [4,5,1,9], val = 1
输出: [4,5,9]
解释: 给定你链表中值为 1 的第三个节点,那么在调用了你的函数之后,该链表应变为 4 -> 5 -> 9.

说明:

题目保证链表中节点的值互不相同

/**
 * Definition for singly-linked list.
 * public class ListNode {
 *     public int val;
 *     public ListNode next;
 *     public ListNode(int x) { val = x; }
 * }
 */
public class Solution 
{
    public ListNode DeleteNode(ListNode head, int val) 
    {
        //送入为null
        if(head==null) return null;
        if(head.val==val) return head.next;
        var cur = head;
        while(cur!=null&&cur.next!=null)
        {
            if(cur.next.val==val)
            {
                //节点的next改为next的next
                cur.next=cur.next.next;
                break;
            }
            //接入当前节点
            cur=cur.next;
        }
        return head;
    }
}

调整数组顺序使奇数位于偶数前面

输入一个整数数组,实现一个函数来调整该数组中数字的顺序,使得所有奇数在数组的前半部分,所有偶数在数组的后半部分,空间复杂度要求O(1)。

示例:

输入:nums = [1,2,3,4]
输出:[1,3,2,4]
注:[3,1,2,4] 也是正确的答案之一。

提示:

0 <= nums.length <= 50000
0 <= nums[i] <= 10000

代码实现:时间复杂度为O(N),空间复杂度为O(1)。

public class Solution {
    public int[] Exchange(int[] nums) {
        //辅助数组?一种解法

        //双指针。优化解法
        int head = 0;
        int tail = nums.Count()-1;
        while(head<tail)
        {
            while((nums[head]%2!=0)&&head<tail)
            {
                head++;
            }
            while((nums[tail]%2==0)&&head<tail)
            {
                tail--;
            }
            int tmp = nums[head];
            nums[head] = nums[tail];
            nums[tail] = tmp;
        }
        return nums;
    }
}