5283. 二进制链表转整数
给你一个单链表的引用结点 head。链表中每个结点的值不是 0 就是 1。已知此链表是一个整数数字的二进制表示形式。
请你返回该链表所表示数字的 十进制值
单链表排序的题目没什么好说的
# Definition for singly-linked list.
# class ListNode(object):
# def __init__(self, x):
# self.val = x
# self.next = None
class Solution(object):
def getDecimalValue(self, head):
"""
:type head: ListNode
:rtype: int
"""
cnt = 0
tmp = head
while tmp:
cnt = (cnt<<1) + tmp.val
tmp = tmp.next
return cnt
5124. 顺次数
我们定义「顺次数」为：每一位上的数字都比前一位上的数字大 1 的整数。
请你返回由 [low, high] 范围内所有顺次数组成的 有序 列表（从小到大排序）
提示：
- 10 <= low <= high <= 10^9
范围比较小所以直接构造答案即可
class Solution(object):
def sequentialDigits(self, low, high):
"""
:type low: int
:type high: int
:rtype: List[int]
"""
def check(x):
return x>=low and x<=high
tmp = [ i for i in range(1,10)]
ans = []
now = tmp[-1]
for j in range(9):
tmplist = []
for i in tmp:
if i%10<=8 :
now = i *10 + (i%10+1)
tmplist.append(now)
if check(now):
ans.append(now)
if now > high:
break
tmp = tmplist
return ans
5285. 元素和小于等于阈值的正方形的最大边长
给你一个大小为 m x n 的矩阵 mat 和一个整数阈值 threshold。
请你返回元素总和小于或等于阈值的正方形区域的最大边长；如果没有这样的正方形区域，则返回 0 。
提示：
- 1 <= m, n <= 300
- m == mat.length
- n == mat[i].length
- 0 <= mat[i][j] <= 10000
- 0 <= threshold <= 10^5
初始化用O(1)时间求正方形区域和，然后通过二分边长范围确定答案
class Solution(object):
def maxSideLength(self, mat, threshold):
"""
:type mat: List[List[int]]
:type threshold: int
:rtype: int
"""
m = len(mat)
n = len(mat[0])
cnt = [ [0]*(n+1) for i in range(m+1)]
for i in range(m):
for j in range(n):
cnt[i][j] = mat[i][j]
if i:
cnt[i][j] += cnt[i-1][j]
if j:
cnt[i][j] += cnt[i][j-1]
if i and j:
cnt[i][j] -= cnt[i-1][j-1]
def check(x):
if x==0:
return True
for i in range(x-1,m):
for j in range(x-1,n):
if cnt[i][j] - cnt[i][j-x] - cnt[i-x][j] + cnt[i-x][j-x] <= threshold:
return True
return False
l,r = 0,min(m,n)
ans = 0
while l<=r:
mid = (r+l)//2
if check(mid):
ans = mid
l = mid+1
else:
r = mid -1
return ans
5286. 网格中的最短路径 显示英文描述
给你一个 m * n 的网格，其中每个单元格不是 0（空）就是 1（障碍物）。每一步，您都可以在空白单元格中上、下、左、右移动。
如果您 最多 可以消除 k 个障碍物，请找出从左上角 (0, 0) 到右下角 (m-1, n-1) 的最短路径，并返回通过该路径所需的步数。如果找不到这样的路径，则返回 -1。
分层图的概念吧，想着是深搜，记忆化后还是超时，通过确定k>=(m+n-1)返回一些变态范围的答案后通过
class Solution(object):
def shortestPath(self, grid, k):
"""
:type grid: List[List[int]]
:type k: int
:rtype: int
"""
m = len(grid)
n = len(grid[0])
limit = m*n+1
if k>=(m+n-1):
return m+n-2
cnt = [ [ [limit]*(k+1) for j in range(n) ] for i in range(m) ]
dis = [[0,1],[1,0],[0,-1],[-1,0]]
def dfs(x,y,now,tmp):
# print x,y,now
cnt[x][y][tmp] = now
for i in range(tmp+1,k+1):
if cnt[x][y][i]<=now:
return
for dx,dy in dis:
nx = x+dx
ny = y+dy
if nx<m and nx>=0 and ny>=0 and ny<n \
and tmp-grid[nx][ny] >=0 \
and now+grid[nx][ny]<cnt[nx][ny][tmp-grid[nx][ny]]:
dfs(nx,ny,now+1,tmp-grid[nx][ny])
dfs(0,0,0,k-grid[0][0])
tmp = limit
for i in range(0,k+1):
tmp = min(tmp,cnt[m-1][n-1][i])
return -1 if tmp >= limit else tmp
感想：
- 该优化的一定要优化，第三题少优化了一部分答案就过不去
- 对于越界情况下考虑多申请一列、一行，这样处于-1时不影响答案
