# @lc app=leetcode.cn id=39 lang=python3
#
# [39] 组合总和
#
# @lc code=start
class Solution:
def combinationSum(self,candidates, target: int):
nums=list()
nums.append(-1)
length=len(candidates)
rev=[target-i for i in candidates]
nums.extend([target-i for i in candidates])
while [i for i in rev if i>=min(candidates)]!=[]:
mid=list()
for i in rev:
if i<=0:
mid.extend([-1]*length)
nums.extend([-1]*length)
continue
else:
mid.extend([i-j for j in candidates])
nums.extend([i-j for j in candidates])
rev=mid
result=list()
mids=list()
for i in range(1,len(nums)):
if nums[i]!=0:
continue
else:
j=i
while 1:
if j<=length:
mids.append(candidates[j-1])
mids.sort()
print(mids)
if mids not in result :
result.append(mids)
break
elif j//length==j/length:
j=int((j-length)/length)
mids.append(candidates[-1])
else:
mids.append(candidates[j-(j//length)*length-1])
j=int(j//length)
mids=[]
return result
# @lc code=end
显示超时了…..
其实大致反方向对的，但是有些地方不太正确
尝试用回溯的方法（递归调用）
from typing import List
class Solution:
def combinationSum(self, candidates: List[int], target: int) -> List[List[int]]:
def dfs(candidates, begin, size, path, res, target):
if target < 0:
return
if target == 0:
res.append(path)
return
for index in range(begin, size):
dfs(candidates, index, size, path + [candidates[index]], res, target - candidates[index])
size = len(candidates)
if size == 0:
return []
path = []
res = []
dfs(candidates, 0, size, path, res, target)
return res
def firstMissingPositive(nums):
lens=len(nums)
for i in range(lens):
if nums[i]<0:
nums[i]=lens+1
for i in range(lens):
num = abs(nums[i])
if num <= lens:
nums[num - 1] = -abs(nums[num - 1])
print(nums)
for i in range(lens):
if nums[i]>=0:
return i+1
return lens+1
# [37] 解数独
#
#回溯法
"""
回溯法（探索与回溯法）是一种选优搜索法，又称为试探法，
按选优条件向前搜索，以达到目标。但当探索到某一步时，
发现原先选择并不优或达不到目标，就退回一步重新选择，
这种走不通就退回再走的技术为回溯法，
而满足回溯条件的某个状态的点称为“回溯点”。
"""
# @lc code=start
class Solution:
def solveSudoku(self, board)->None:
"""
Do not return anything, modify board in-place instead.
"""
#判断改行、列、3*3小格子是否满足数独规则：
def isRowSafe(row,value):
for i in range(9):
if board[row][i]==value:
return False
return True
def isColSafe(col,value):
for i in range(9):
if board[i][col]==value:
return False
return True
def isSmallboxSafe(row,col,value):
inirow=row//3*3
inicol=col//3*3
for i in range(3):
for j in range(3):
if board[i+inirow][j+inicol]==value:
return False
return True
#判断该位置是否可行
def isSafe(row,col,value):
return isRowSafe(row,value) and isColSafe(col,value) and isSmallboxSafe(row,col,value)
#解数独，结束条件
def solve(row,col):
if row==8 and col ==9:
return True
if col ==9:
col=0
row+=1
if board[row][col]!=".":
return solve(row,col+1)
for i in range(1,10):
if isSafe(row,col,str(i)):
i=str(i)
board[row][col] = i
if solve(row, col+1):
return board
#回溯到上一个状态（也就是前一个solve）
board[row][col]="."
return False
solve(0,0)
print(board)
#思路：遍历一遍数组，就要完成该目标，行和列简单，对于方格：[int(i/3)][int(j/3)]
class Solution:
def isValidSudoku(self, board: List[List[str]]) -> bool:
# 1、先生成三个数组
rows = [[0] * 9 for _ in range(9)]
columns = [[0] * 9 for _ in range(9)]
subboxes = [[[0] * 9 for _ in range(3)] for _ in range(3)]
# 遍历行
for i in range(9):
for j in range(9):
c = board[i][j]
if c != '.':
c = int(c) - 1
rows[i][c] += 1
columns[j][c] += 1
subboxes[int(i/3)][int(j/3)][c] += 1
if rows[i][c] > 1 or columns[j][c]>1 or subboxes[int(i/3)][int(j/3)][c]>1:
return False
return True
