当前位置：首页 > article >正文

力扣题31~40

article 2024/10/12 7:14:19

题31（中等）：

分析：

其实这题题目比较难懂，题目还是挺简单的

我们可以从后面末尾开始，如果前一个大于后面的，说明后面不用动，如果小于，那就找仅仅大于它的数字放前面，其他数字重新排序放后面，前面不用动

python代码：

class Solution:

def nextPermutation(self, nums: List[int]) -> None:

res_list = []

# 获取长度

nums_len = len(nums)

if nums_len==0 or nums_len==1:

return

# 从后面算要不要换

for i in range(nums_len - 1):

a = nums[nums_len - i - 1] # 去已经确定的头

b = nums[nums_len - i - 2] # 取新加的

if a > b:

res_list = nums[nums_len - i - 2:]

res_list = sorted(res_list)

index = res_list.index(b)

while 1:

index += 1

if res_list[index] != b:

break

res_list = nums[:nums_len - i - 2] + res_list[index:index + 1] + res_list[0:index] + res_list[index + 1:]

break

else:

if i==nums_len-2:

res_list = sorted(nums)

continue

nums.clear()

nums.extend(res_list)

题32（困难）：

分析：

其实就是遍历一遍，我的思路就是每一项为前两项的和+2，且将前两项去了

python代码：

class Solution:

def longestValidParentheses(self, s: str) -> int:

tmp_list=[]

s_stack=[]

for i in s:

if i=="(":

s_stack.append(i)

tmp_list.append(0)

else:

if len(s_stack)!=0 and s_stack[-1]=='(':

s_stack.pop()

if tmp_list!=[]:

a1=tmp_list.pop()

else:

a1=0

if tmp_list!=[]:

a2=tmp_list.pop()

else:

a2=0

next=a1+a2+2

tmp_list.append(next)

else:

tmp_list.append(0)

return max(tmp_list) if tmp_list!= [] else 0

题33（中等）：

分析：

这个和折半查找应该差不多吧

python代码：

class Solution:

def search(self, nums: List[int], target: int) -> int:

if nums[0]<nums[-1]:

nums=nums[:]+[nums[0]-abs(target)]

num_len=len(nums)

left = 0

right = num_len - 1

notice1=target>=nums[0]

notice2=target<=nums[-1]

if notice1==0 and notice2==0:

return -1

while left<=right:

mid=(left+right)//2

if notice1:

if nums[mid]==target:

return mid

elif nums[mid]<=nums[-1] or nums[mid]>target:

right=mid-1

else:

left=mid+1

continue

if notice2:

if nums[mid]==target:

return mid

elif nums[mid]>=nums[0] or nums[mid]<target:

left=mid+1

else:

right=mid-1

continue

return -1

题34（中等）：

分析：

没什么好分析的，这波也是折半查找

python代码：

class Solution:

def searchRange(self, nums: List[int], target: int) -> List[int]:

left=0

right=len(nums)-1

min_target=-1

while left<=right:

mid=(left+right)//2

if nums[mid]==target:

if mid-1>=0 and nums[mid-1]==target:

right=mid-1

else:

min_target=mid

break

elif nums[mid]<target:

left=mid+1

elif nums[mid]>target:

right=mid-1

max_target = -1

left = 0

right = len(nums) - 1

while left<=right:

mid=(left+right)//2

if nums[mid]==target:

if mid + 1 <= len(nums)-1 and nums[mid + 1] == target:

left = mid+1

else:

max_target = mid

break

elif nums[mid]<target:

left=mid+1

elif nums[mid]>target:

right=mid-1

return [min_target,max_target]

题35（简单）：

python代码：

class Solution:

def searchInsert(self, nums: List[int], target: int) -> int:

left=0

right=len(nums)-1

min_target=-1

while left<=right:

mid=(left+right)//2

if nums[mid]==target:

min_target=mid

break

elif nums[mid]<target:

left=mid+1

elif nums[mid]>target:

right=mid-1

return min_target if min_target!=-1 else right+1

题36（中等）：

分析：

自己定义一个检查列表的函数，每次将一堆传过去检测

python代码：

class Solution:

def isValidSudoku(self, board: List[List[str]]) -> bool:

def isValidUnit(unit):

# 检查一个行、列或宫格是否有效

seen = set()

for num in unit:

if num != '.':

if num in seen:

return False

seen.add(num)

return True

for i in range(9):

if not isValidUnit(board[i]):

return False

for j in range(9):

column = [board[i][j] for i in range(9)]

if not isValidUnit(column):

return False

for i in range(0, 9, 3):

for j in range(0, 9, 3):

square = [board[x][y] for x in range(i, i+3) for y in range(j, j+3)]

if not isValidUnit(square):

return False

return True

题37（困难）：

python代码：

class Solution:

def solveSudoku(self, board: List[List[str]]) -> None:

def Conflict(board):

def isValidUnit(unit):

# 检查一个行、列或宫格是否有效

seen = set()

for num in unit:

if num != '.':

if num in seen:

return False

seen.add(num)

return True

for i in range(9):

if not isValidUnit(board[i]):

return False

for j in range(9):

column = [board[i][j] for i in range(9)]

if not isValidUnit(column):

return False

for i in range(0, 9, 3):

for j in range(0, 9, 3):

square = [board[x][y] for x in range(i, i + 3) for y in range(j, j + 3)]

if not isValidUnit(square):

return False

return True

def run(n):

for i in range(n,81):

x = i // 9

y = i % 9

if board[x][y]!='.':

continue

for j in range(1,10):

board[x][y]=str(j)

if Conflict(board) and run(i+1):

return True

board[x][y]='.'

return False

return True

run(0)