（愿努力的我们都能达到梦想的彼岸！加油！一起打卡，互相关注！）
一、比较含退格的字符串
给定 s 和 t 两个字符串，当它们分别被输入到空白的文本编辑器后，请你判断二者是否相等。# 代表退格字符。
如果相等，返回 true ；否则，返回 false 。
注意：如果对空文本输入退格字符，文本继续为空。
示例 1：
输入：s = "ab#c", t = "ad#c"
输出：true
解释：S 和 T 都会变成 “ac”。
示例 2：
输入：s = "ab##", t = "c#d#"
输出：true
解释：s 和 t 都会变成 “”。
示例 3：
输入：s = "a##c", t = "#a#c"
输出：true
解释：s 和 t 都会变成 “c”。
示例 4：
输入：s = "a#c", t = "b"
输出：false
解释：s 会变成 “c”，但 t 仍然是 “b”。
来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/backspace-string-compare
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。
class Solution:
def backspaceCompare(self, s: str, t: str) -> bool:
list1=[]
list2=[]
for i in range(len(s)):
c=s[i]
if c != '#':
list1.append(c)
elif len(list1)>0:
list1.pop()
for j in range(len(t)):
c=t[j]
if c != '#':
list2.append(c)
elif len(list2)>0:
list2.pop()
return str(list1)==str(list2)
二、数组中重复的数字
找出数组中重复的数字。
在一个长度为 n 的数组 nums 里的所有数字都在 0～n-1 的范围内。数组中某些数字是重复的，但不知道有几个数字重复了，也不知道每个数字重复了几次。请找出数组中任意一个重复的数字。
示例 1：
输入：
[2, 3, 1, 0, 2, 5, 3]
输出：2 或 3
来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/shu-zu-zhong-zhong-fu-de-shu-zi-lcof
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。
代码1
class Solution:
def findRepeatNumber(self, nums: List[int]) -> int:
tmp = set()
for num in nums:
if num in tmp:
return num
break
tmp.add(num)
代码2
class Solution:
def findRepeatNumber(self, nums: List[int]) -> int:
dic={}
for i in nums:
if i%len(nums) not in dic:
dic[i%len(nums)]=1
else:
return i
二、二维数组中的查找
在一个 n * m 的二维数组中，每一行都按照从左到右递增的顺序排序，每一列都按照从上到下递增的顺序排序。请完成一个高效的函数，输入这样的一个二维数组和一个整数，判断数组中是否含有该整数。
示例:
现有矩阵 matrix 如下：
[
[1, 4, 7, 11, 15],
[2, 5, 8, 12, 19],
[3, 6, 9, 16, 22],
[10, 13, 14, 17, 24],
[18, 21, 23, 26, 30]
]
给定 target = 5，返回 true。
给定 target = 20，返回 false。
来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/er-wei-shu-zu-zhong-de-cha-zhao-lcof
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。
代码1
class Solution:
def findNumberIn2DArray(self, matrix: List[List[int]], target: int) -> bool:
if matrix==[[]]:
return False
for i in matrix:
r=len(i)
l=0
if i[-1]target:
r=mid-1
elif i[mid]
代码2
class Solution:
def findNumberIn2DArray(self, matrix: List[List[int]], target: int) -> bool:
if len(matrix)==0:
return False
k=len(matrix[0])-1
i=0
while True:
if i>len(matrix)-1 or k<0 :
return False
u=matrix[i][k]
if u==target:
return True
elif u
代码3
class Solution:
def findNumberIn2DArray(self, matrix: List[List[int]], target: int) -> bool:
h,l=len(matrix)-1,0
while h>=0 and ltarget:
h-=1
elif matrix[h][l]
三、替换空格
请实现一个函数，把字符串 s 中的每个空格替换成"%20"。
示例 1：
输入：s = "We are happy."
输出："We%20are%20happy."
来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/ti-huan-kong-ge-lcof
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。
代码1
class Solution:
def replaceSpace(self, s: str) -> str:
s=s.replace(' ','%20')
return s
代码2
class Solution:
def replaceSpace(self, s: str) -> str:
l = ""
for i in s:
if i == " ":
l = l + "%20"
else:
l = l + i
return l
四、从尾到头打印链表
输入一个链表的头节点，从尾到头反过来返回每个节点的值（用数组返回）。
示例 1：
输入：head = [1,3,2]
输出：[2,3,1]
代码1
# Definition for singly-linked list.
# class ListNode:
# def __init__(self, x):
# self.val = x
# self.next = None
class Solution:
def reversePrint(self, head: ListNode) -> List[int]:
return self.reversePrint(head.next)+[head.val] if head else []
代码2
# Definition for singly-linked list.
# class ListNode:
# def __init__(self, x):
# self.val = x
# self.next = None
class Solution:
def reversePrint(self, head: ListNode) -> List[int]:
l=[]
while head:
l.append(head.val)
head=head.next
return l[::-1]
五、用两个栈实现队列
用两个栈实现一个队列。队列的声明如下，请实现它的两个函数 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]
来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/yong-liang-ge-zhan-shi-xian-dui-lie-lcof
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。
代码1
class CQueue:
def __init__(self):
self.list_lk1=[]
self.list_lk2=[]
def appendTail(self, value: int) -> None:
self.list_lk1.append(value)
def deleteHead(self) -> int:
if self.list_lk2:
return self.list_lk2.pop()
else:
while self.list_lk1:
self.list_lk2.append(self.list_lk1.pop())
return self.list_lk2.pop() if self.list_lk2 else -1
代码2
class CQueue:
def __init__(self):
self.A = []
def appendTail(self, value: int) -> None:
self.A.append(value)
def deleteHead(self) -> int:
try:
return self.A.pop(0)
except Exception as e:
return -1
代码3
class CQueue:
def __init__(self):
self.A = []
def appendTail(self, value: int) -> None:
self.A.append(value)
def deleteHead(self) -> int:
if self.A:
return self.A.pop(0)
else:
return -1
六、斐波那契数列
写一个函数，输入 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
来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/fei-bo-na-qi-shu-lie-lcof
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。
class Solution:
def fib(self, n: int) -> int:
if n==0 or n==1 or n==2:
return 0 if n==0 else 1
a=0
b=1
for _ in range(n):
a,b=b,a+b
return a%1000000007
七、青蛙跳台阶问题
一只青蛙一次可以跳上1级台阶，也可以跳上2级台阶。求该青蛙跳上一个 n 级的台阶总共有多少种跳法。
答案需要取模 1e9+7（1000000007），如计算初始结果为：1000000008，请返回 1。
示例 1：
输入：n = 2
输出：2
示例 2：
输入：n = 7
输出：21
示例 3：
输入：n = 0
输出：1
来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/qing-wa-tiao-tai-jie-wen-ti-lcof
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。
代码1
class Solution:
def numWays(self, n: int) -> int:
tmp=sum=1
for _ in range(n):
sum,tmp=tmp,tmp+sum
return sum%1000000007
代码2
class Solution:
def numWays(self, n: int) -> int:
res=[1,1]
if n<2:
return 1
for i in range(2,n+1):
res.append((res[i-1]+res[i-2])%1000000007)
return res[n]
八、旋转数组的最小数字
把一个数组最开始的若干个元素搬到数组的末尾，我们称之为数组的旋转。输入一个递增排序的数组的一个旋转，输出旋转数组的最小元素。例如，数组 [3,4,5,1,2] 为 [1,2,3,4,5] 的一个旋转，该数组的最小值为1。
示例 1：
输入：[3,4,5,1,2]
输出：1
示例 2：
输入：[2,2,2,0,1]
输出：0
来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/xuan-zhuan-shu-zu-de-zui-xiao-shu-zi-lcof
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。
class Solution:
def minArray(self, numbers: List[int]) -> int:
head=numbers[0]
l=[]
for i in range(len(numbers)-1,0,-1):
if head<=numbers[i]:
continue
else:
l.append(numbers[i])
if len(l)==0:
return head
else:
return l[-1]
九、删除链表的节点
给定单向链表的头指针和一个要删除的节点的值，定义一个函数删除该节点。
返回删除后的链表的头节点。
注意：此题对比原题有改动
示例 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.
来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/shan-chu-lian-biao-de-jie-dian-lcof
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。
代码1
# Definition for singly-linked list.
# class ListNode:
# def __init__(self, x):
# self.val = x
# self.next = None
class Solution:
def deleteNode(self, head: ListNode, val: int) -> ListNode:
if not head:
return None
if head.val==val:
return head.next
cur=ListNode(-1)
tmp=head
cur.next=tmp
while tmp:
if tmp.val==val:
cur.next=cur.next.next
break
cur=tmp
tmp=tmp.next
return head
代码2
# Definition for singly-linked list.
# class ListNode:
# def __init__(self, x):
# self.val = x
# self.next = None
class Solution:
def deleteNode(self, head: ListNode, val: int) -> ListNode:
if head.val == val:
return head.next
cur = head
tmp = cur
while cur:
if cur.val != val:
tmp = cur
cur = cur.next
else:
tmp.next = cur.next
break
return head
十、链表中倒数第k个节点
输入一个链表，输出该链表中倒数第k个节点。为了符合大多数人的习惯，本题从1开始计数，即链表的尾节点是倒数第1个节点。
例如，一个链表有 6 个节点，从头节点开始，它们的值依次是 1、2、3、4、5、6。这个链表的倒数第 3 个节点是值为 4 的节点。
示例：
给定一个链表: 1->2->3->4->5, 和 k = 2.
返回链表 4->5.
来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/lian-biao-zhong-dao-shu-di-kge-jie-dian-lcof
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。
代码1
# Definition for singly-linked list.
# class ListNode:
# def __init__(self, x):
# self.val = x
# self.next = None
class Solution:
def getKthFromEnd(self, head: ListNode, k: int) -> ListNode:
cur=head
count=0
while cur:
count+=1
cur=cur.next
res=count-k
while res:
res-=1
head=head.next
return head
代码2
# Definition for singly-linked list.
# class ListNode:
# def __init__(self, x):
# self.val = x
# self.next = None
class Solution:
def getKthFromEnd(self, head: ListNode, k: int) -> ListNode:
li=[]
while head:
li.append(head)
head=head.next
return li[len(li)-k]
