37： 解数独
唉 其实这道题我觉得我是可以的 但是后来想着这回溯太深了 方法是不是不对 就放弃了 后悔 就是后悔
力扣的全局变量我也不是很会写
全局变量不会写 只能传递了
class Solution(object): def solveSudoku(self, board): """ :type board: List[List[str]] :rtype: None Do not return anything, modify board in-place instead. """ def DFS(pos,valid): #pos表示当前填的是第几个格子 i,j = gap[pos] if pos == len(gap)-1: for num in range(9): if (row[i][num] == False) and (col[j][num] == False) and (block[i//3][j//3][num] == False): board[i][j] = str(num +1) valid = True return valid for num in range(9): if (row[i][num] == False) and (col[j][num] == False) and (block[i//3][j//3][num] == False): board[i][j] = str(num +1) row[i][num] = True col[j][num] = True block[i//3][j//3][num] = True valid = DFS(pos+1,valid) row[i][num] = False col[j][num] = False block[i//3][j//3][num] = False if valid: return valid 作者：yizhu-jia 链接：https://leetcode-cn.com/problems/sudoku-solver/solution/pythonde-quan-ju-bian-liang-zen-yao-xie-36wgn/ 来源：力扣（LeetCode） 著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。
38 ：外观数组
就一个一个推过去
没想到超过大部分人
def nextsay(countstr): nextcountstr ="" count = 0 curnum = countstr[0] for each in countstr: if each == curnum: count += 1 continue else: nextcountstr +=(str(count)+str(curnum)) curnum = each count = 1 nextcountstr += (str(count)+str(curnum)) return nextcountstr count = ‘1‘ for i in range(n-1): count = nextsay(count) return count
39：
组合总和： 不知道是不是自己写出来的第一道回溯
rel = [] currel = [] def DFS(cursum,rel,currel): n = len(candidates) for i in range(n): if len(currel) != 0 : if candidates[i] < currel[-1]: break #这里表示只能往后找 不能往前找 cursum += candidates[i] currel .append(candidates[i]) if cursum == target: rel .append(currel[:]) elif cursum < target: DFS(cursum,rel,currel) currel.pop() cursum -= candidates[i] DFS(0,rel,currel) return rel
40：组合但是不能重复
但是好难 最后看别人的方法...
这种觉得残差还是传剩余值比较好
class Solution(object): def combinationSum2(self, candidates, target): """ :type candidates: List[int] :type target: int :rtype: List[List[int]] """ def DFS(begin,path,residual): if residual == 0: rel.append(path[:]) return for i in range(begin,n): if candidates[i] > residual: break if i > begin and candidates[i-1] == candidates[i]: continue path .append(candidates[i]) DFS(i+1,path,residual-candidates[i]) path.pop() rel = [] candidates = sorted(candidates) n = len(candidates) DFS(0,[],target) return rel 作者：yizhu-jia 链接：https://leetcode-cn.com/problems/combination-sum-ii/solution/bie-wen-liao-chao-de-by-yizhu-jia-8ve9/ 来源：力扣（LeetCode） 著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。
41：
求未出现最小正整数
说是固定长度的空间 本意是原地哈希
但是我： 毅然被所有人击败：：：
class Solution(object): def firstMissingPositive(self, nums): """ :type nums: List[int] :rtype: int """ num = [0] * 5*10**5 for each in nums: if each <= 5*10**5 and each > 0: num[each-1] = 1 for i in range(5*10**5): if num[i] == 0 : return i+1 return 5*10**5 +1 作者：yizhu-jia 链接：https://leetcode-cn.com/problems/first-missing-positive/solution/bei-suo-you-ren-ji-bai-by-yizhu-jia-no8s/ 来源：力扣（LeetCode） 著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。
42：接牙吗么接雨水
单调栈 第一次见 大概懂了 就是栈里只能递减着存 不能出现后面数大的情况 可以处理很多题
class Solution(object): def trap(self, height): """ :type height: List[int] :rtype: int """ stack=[] water = 0 for index,h in enumerate(height): while stack and h > height[stack[-1]]: l = stack.pop() if not stack: break wid = index-stack[-1]-1 hig = min(height[stack[-1]],h) - height[l] water += hig* wid stack.append(index) return water 作者：yizhu-jia 链接：https://leetcode-cn.com/problems/trapping-rain-water/solution/dui-bu-qi-chao-de-by-yizhu-jia-wo6i/ 来源：力扣（LeetCode） 著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。