LeetCode算法一些解答_Csharp
用两个栈实现队列
用两个栈实现一个队列。队列的声明如下，请实现它的两个函数 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函数的栈
定义栈的数据结构，请在该类型中实现一个能够得到栈的最小元素的 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();
*/数组中重复的数字
找出数组中重复的数字。
在一个长度为 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;
}
}替换空格
Link
请实现一个函数，把字符串 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();
}
}从尾到头打印链表
输入一个链表的头节点，从尾到头反过来返回每个节点的值（用数组返回）。
示例 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;
}
}斐波那契数列
写一个函数，输入 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];
}
}青蛙跳台阶问题
一只青蛙一次可以跳上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阶的跳法就可以得到最后一次跳两格的跳法种数，相加即得到跳达终点的跳法数
}删除链表中的节点
给定单向链表的头指针和一个要删除的节点的值，定义一个函数删除该节点。
返回删除后的链表的头节点。
注意：此题对比书本原题有改动
示例 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;
}
}调整数组顺序使奇数位于偶数前面
Link
输入一个整数数组，实现一个函数来调整该数组中数字的顺序，使得所有奇数在数组的前半部分，所有偶数在数组的后半部分，空间复杂度要求O(1)。
示例：
输入：nums = [1,2,3,4]
输出：[1,3,2,4]
注：[3,1,2,4] 也是正确的答案之一。
提示：
0 <= nums.length <= 500000 <= 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;
}
}
