目录
  1. 1. 日常警醒
  2. 2. 剑指offer06-从尾到头 打印链表
    1. 2.1. 题目
    2. 2.2. 题解
  3. 3. 剑指offer09-用两个栈实现队列
    1. 3.1. 题目
    2. 3.2. 题解
  4. 4. 剑指offer13-机器人的运动范围
    1. 4.1. 题目
    2. 4.2. 题解
每日一刷3

日常警醒

菜就要刷题,不要偷懒!

剑指offer06-从尾到头 打印链表

题目

  • 难度:简单

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

示例1:

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

限制:

0 <= 链表长度 <= 10000

题解

1.遍历一遍链表,存入数组中,然后反转数组输出。

  • 时间复杂度:O(n)
  • 空间复杂度:O(n)
class ListNode(object):
def __init__(self, x):
self.val = x
self.next = None

def reversePrint(head):
if not head:
return []

stack = []

while head:
stack.append(head.val)
head = head.next

return stack[::-1]

if __name__ == '__main__':

head1 = ListNode(1)
head2 = ListNode(3)
head3 = ListNode(2)
head1.next = head2
head2.next = head3
print(reversePrint(head1))

2.将链表反转,然后遍历反转后的链表,依次将结点的值存入数组输出。

  • 时间复杂度:O(n)
  • 空间复杂度:O(n)
class ListNode(object):
def __init__(self, x):
self.val = x
self.next = None

def reversePrint(head):
if not head:
return []

pre = None
cur = head
res = []

while cur:
temp = cur.next
cur.next = pre
pre = cur
cur = temp

while pre:
res.append(pre.val)
pre = pre.next

return res


if __name__ == '__main__':

head1 = ListNode(1)
head2 = ListNode(3)
head3 = ListNode(2)
head1.next = head2
head2.next = head3
print(reversePrint(head1))

3.一行递归法,先走至链表末端,回溯时依次将节点值加入列表 ,这样就可以实现链表值的倒序输出。(参考别人解法)

  • 递归阶段:每次传入 head.next ,以 head == None(即走过链表尾部节点)为递归终止条件,此时返回空列表 []
  • 回溯阶段: 利用 Python 语言特性,递归回溯时每次返回 当前 list + 当前节点值 [head.val],即可实现节点的倒序输出。
  • 时间复杂度:O(n)
  • 空间复杂度:O(n)
class ListNode(object):
def __init__(self, x):
self.val = x
self.next = None

def reversePrint(head):
return reversePrint(head.next) + [head.val] if head else []

if __name__ == '__main__':

head1 = ListNode(1)
head2 = ListNode(3)
head3 = ListNode(2)
head1.next = head2
head2.next = head3
print(reversePrint(head1))

剑指offer09-用两个栈实现队列

题目

  • 难度:简单

用两个栈实现一个队列。队列的声明如下,请实现它的两个函数 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 次调用`

题解

  • 定义两个栈、appendTail和deleteHead函数,一个栈用来完成入队,一个栈用来完成出队(假设一个栈为stack1,另一个栈为stack2)
  • appendTail函数:往stack1添加元素
  • deleteHead函数:
    • 如果stack2不为空,就stack.pop数据
    • 如果stack1为空,说明队列没有元素,返回-1
    • 如果stack1不为空,就将stack1.pop的值加入stack2
  • 返回stack2.pop
  • 时间复杂度:O(n)
  • 空间复杂度:O(n)
class CQueue(object):

def __init__(self):
self.stack1 = []
self.stack2 = []

def appendTail(self, val):
self.stack1.append(val)

def deleteHead(self):
if self.stack2:
return self.stack2.pop()
if not self.stack1:
return -1
if self.stack1:
self.stack2.append(self.stack1.pop())
return self.stack2.pop()

if __name__ == '__main__':

queue = CQueue()
arr = [1,2,3,4,5]
for i in range(len(arr)):
queue.appendTail(arr[i])
for i in range(5):
print(queue.deleteHead(), ',', end = '')

剑指offer13-机器人的运动范围

题目

  • 难度:中等

地上有一个m行n列的方格,从坐标 [0,0] 到坐标 [m-1,n-1] 。一个机器人从坐标 [0, 0] 的格子开始移动,它每次可以向左、右、上、下移动一格(不能移动到方格外),也不能进入行坐标和列坐标的数位之和大于k的格子。例如,当k为18时,机器人能够进入方格 [35, 37] ,因为3+5+3+7=18。但它不能进入方格 [35, 38],因为3+5+3+8=19。请问该机器人能够到达多少个格子?

示例1:

输入:m = 2, n = 3, k = 1
输出:3

示例2:

输入:m = 3, n = 1, k = 0
输出:1

提示:

  • 1 <= n,m <= 100
  • 0 <= k <= 20

题解

  • 类似矩阵搜索问题,通常可以采用深度优先搜索(DFS)或广度优先搜索(BFS)。 两者目标都是遍历整个矩阵,不同点在于搜索顺序不同。DFS 是朝一个方向走到底,再回退,以此类推;BFS 则是按照“平推”的方式向前搜索。BFS 实现: 通常利用队列实现广度优先遍历。

1.DFS

  • 矩阵行列索引,i和j,两者数位和,si和sj
  • 终止条件:
    • 行列索引出界
    • si + sj > k
    • 当前元素访问过,返回0,代表不计入可达解
  • 递推条件:
    • 标记当前单元格,将索引存入set(),代表已经访问过
    • 搜索下一个单元格,计算当前元素,下和右两个方向的行列索引数位和,开始下一层递归
    • 回溯返回值:返回 1 + 右方搜索的可达解总数 + 下方搜索的可达解总数,代表从本单元格递归搜索的可达解总数。
def movingCount(m, n, k):

visited = set()

def dfs(i, j, si, sj):
if i > m or j > n or si + sj > k or (i, j) in visited:
return 0
visited.add((i,j))
return 1 + dfs(i + 1, j, si + 1 if (i + 1) % 10 else si - 8, sj) + dfs(i, j + 1, si, sj + 1 if(j + 1) % 10 else sj - 8)

return dfs(0, 0, 0, 0)

if __name__ == "__main__":

m = 2
n = 3
k = 1
print(movingCount(m,n,k))
文章作者: Lesy
文章链接: https://lesylin.com/2020/08/03/%E6%AF%8F%E6%97%A5%E4%B8%80%E5%88%B73/
文章声明: 转载请注明文章链接
打赏
  • 微信
  • 支付宝

Comment