常见LeetCode-Saw200

用来记录需要知道见过的题型：

LeetCode2-两数相加
说明：以链表的形势给了你每个位的数字，而且是逆序，直接从开头（个位）遍历相加。带上进位即可。有一个为空就直接计算另一个和进位。
LeetCode-3.无重复字符的最长子串
说明不清楚，要求从字符

串总能截取一个子串，要求这个子串中没有出现重复的元素。求子串的最大可能长度。
解题思路：一开始想到的就是和股票收益是一个类题型，每次判断当期那元素是否出现在当前字符串中，如果出现就归零否则，长度加一。后来发现，这是不对的，如果出现过，需要找到他出现的位置，从那里重新截取得到字符串，而不是直接归零。
更优解题思路：滑动窗口，用一个队列来记录当前队列，每次新元素如果没见过就谈入，如果见过就一直弹（leftpop）到没见过。
LeetCode5-最长回文子串
二维动态规划。核心：新增的这个元素是有是否是回文：上一次也是回文，且，此元素和对称位置相等。
但是我相同以为动态规划来解题，有机会试试，这应该是当做二维dp的基础例题。
leetCode6-Z字变形
直接新建N个数组，每个数组用来存储第1,2,3...行，遍历提供的数组，按照蛇形进行append到不同的行。（类似于正态分布！！！）
LeetCode7-整数反转
【这种最好就是按照字符串来！！！！！！】。开头为0的情况再最后处理。训练条件为剩下的字符串还有长度（而不是余数大于0）
LeetCode11-盛水最多的容器（简单半接雨水）
其实也和股票最大值一样，也是需要用双指针从两端开始遍历，记录历史最大成水量。移动两边中较短的那个。
Leetcode15-三数之和（三数之和为0的所有三元组的value情况，输出value的组合）
解题思路先排序，再执行n次求两数之和（外层训练从头到尾，内层使用双指针，从两边到中间。）
LeetCode16-最接近的三数之和（从数组中选出最接近x的三元组，ps假定每组输入只存在恰好一个解）
解题思路：排序+执行n次双指针。
LeetCode17-电话号码的字母组合（给一个包含2~9的数字，返回其所有组合。）
解题思路：往里面放入第一个，后续每次弹出一个元素，再放入这个所有产生的组合。
LeetCode18-四数之和
解题思路：就是在加一层for循环。
LeetCode19-删除链表的倒数第 N 个结点
题解：双指针，一个比两一个游标多走n步。然后一起遍历到前面指针到头，此时删除慢指针节点。
LeetCode22-括号生成（生成有效括号的所有可能）
题解：使用递归，n对括号。一个记录left的个数，一个记录目前right的个数。当前left+right=len(S)，一个可能的结果就造好了就可以append进去了。
说明：带回溯功能的递归（所谓回溯 某个符号可以是左括号，我就所有当前元素是左括号的可能递归append完。然后再pop出来，继续实现“假如当前是右括号”的逻辑）
LeetCode24-两两交换链表中的节点
题解:一开始是想以两个游标来做。
LeetCode29-两数相除（重点）
题解：以2倍递增
LeetCode31-下一个排列（可以做一下）
题解：找下一个能产生的排列。从右侧找一个尽可能小数的大数与右侧数进行交换。如果没有找到则返回数组的升序。
LeetCode33-搜索旋转排序数组（遇到过，有机会把地中方案再写一次。）
题解：方案一：之前面试是先找翻转的位置，确定翻转点，再进行二分查找。这种不容易错！！
方案二：将数组一分为二。（其中有一个一定是有序的；另一个则是有序或部分有序的）此时如果target在有序部分里，改用二分法进行查找。否则进入无序部分继续递归调用。

LeetCode34-在排序数组中查找元素的第一个和最后一个位置

// 两次二分查找，分开查找第一个和最后一个。时间 O(log n), 空间 O(1)// [1,2,3,3,3,3,4,5,9]public int[] searchRange2(int[] nums, int target) {int left = 0;int right = nums.length - 1;int first = -1;int last = -1;    // 找第一个等于target的位置while (left <= right) {int middle = (left + right) / 2;if (nums[middle] == target) {first = middle;right = middle - 1; //重点} else if (nums[middle] > target) {right = middle - 1;} else {left = middle + 1;}}left = 0;     // 最后一个等于target的位置right = nums.length - 1;while (left <= right) {int middle = (left + right) / 2;if (nums[middle] == target) {last = middle;left = middle + 1; //重点} else if (nums[middle] > target) {right = middle - 1;} else {left = middle + 1;}}return new int[]{first, last};}

题解：使用二分法变体，一次查找查找左边界和右边界。二分法之前是如果等于target就返回，二分法变体（找第一个边界）是如果等于target就记下来，继续调整边界直到边界不存在。

LeetCode36-有效的数独（判断一个矩阵是否是数独）

题解：需要新建3个变量，然后从左上角，开始遍历即可。 3个变量（2个二维数组+1个三维数组）分别记录着：每行遇到的每个数出现的次数、每列每个数出现的次数、每个3*3小方块数字出现的次数。如果不为空就更新这三个变量，每次检测 行、列、所在小方块 这个元素后，是否满足规则。（推荐看一下代码图，一眼就懂）

def isValidSudoku(board):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 != '.':index = int(c) - 1rows[i][index] += 1columns[j][index] += 1subboxes[i // 3][j // 3][index] += 1if rows[i][index] > 1 or columns[j][index] > 1 or subboxes[i // 3][j // 3][index] > 1:return Falsereturn True
board =[["8","3",".",".","7",".",".",".","."]
,["6",".",".","1","9","5",".",".","."]
,[".","9","8",".",".",".",".","6","."]
,["8",".",".",".","6",".",".",".","3"]
,["4",".",".","8",".","3",".",".","1"]
,["7",".",".",".","2",".",".",".","6"]
,[".","6",".",".",".",".","2","8","."]
,[".",".",".","4","1","9",".",".","5"]
,[".",".",".",".","8",".",".","7","9"]]
s = isValidSudoku(board) #False
print(s)

LeetCode38-外观数列（‘外观’是指每次迭代f(x)做的事情是描述上一项结果，输出新结果）

和菲波那切数列很像（这个是由前一项得到，斐波那契是由前两项得到）。

前两个数是特征情况，把第2个数当做初始状态，从第3个数开始项开始迭代，依次计算得到3,4,5...n项的输出，得到结果后就继续把结果当做已知条件进行下一次迭代。直到n再输出。

LeetCode39-组合总和（列举取数组中和为target的所有组合）

个人思路：想搬数组分成两类，基础元素和非基础元素（能由其他元素组成），先计算target能有多少基础元素组合。回溯法应该也是必备

解题思路：搜索回溯？？？

LeetCode49-字母异位词分组（把字符串数组分组，同一组的字符串的每个字母次数相同）

个人理解：这个题一旦把异位词换成括号的说法就明朗很多。

排序法：所有异位词排序后结果是相同的，对所有元素排序，key当做排序后结果，value是异位词list。时间复杂度：O(nklogk)  k是子字符串长度。

哈希法：把每个词转成26位数字的数组，元素值为改元素初见的次数。拼成一个key后当做key，value是异位词list。空间复杂度： O(n(k+26))

def groupAnagrams(self, strs: List[str]) -> List[List[str]]:mp = collections.defaultdict(list)for st in strs:counts = [0] * 26for ch in st:counts[ord(ch) - ord("a")] += 1# 需要将 list 转换成 tuple 才能进行哈希mp[tuple(counts)].append(st)return list(mp.values())

LeetCode56-合并区间（合并多个子数组的区间）

def merge(self, intervals: List[List[int]]) -> List[List[int]]:res = []intervals = sorted(intervals)current_array = intervals[0]for array in intervals[1:]:if array[0]<=current_array[1]:current_array = [current_array[0],max(array[1],current_array[1])]else:res.append(current_array)current_array = arrayres.append(current_array) #注意别忘了return  res示例：输入[[1,3],[2,6],[8,10]]  ->  输出[[1,6],[8,10]]

说明：这个题是真贱，是否有序也不说。由于可能出现[[2,5],[1,4]]，需要先按第一个元素排序。然后把第一个数组拿出来，从左向右合并（要么调整cur_array边界，要么append再重置cur_array）。最后别忘了把cur_array再append进去。

LeetCode57-插入区间（把一个区间插入(合并)到一个有序且不重叠的区间数组中）

这个题只会插入一次。①先找到要插入的位置，②开始修改待插入、合并的左右边界。直到右侧不连续③把右侧剩下的元素放进来。 当然也可以用二分查找寻找边界。  这个题主要是分成【找插入位置，定插入边界、追加剩下元素】三步。需要left和right变量。注意这个题可以直接append进去然后用56题来解🤣只背56，能解两道题。

def insert(intervals: List[List[int]], newInterval: List[int]) -> List[List[int]]:res = list()left = newInterval[0]right = newInterval[1]index = 0while index < len(intervals) and intervals[index][1] < left:res.append(intervals[index])index += 1while index < len(intervals) and (intervals[index][0] <= right):left = min(left, intervals[index][0])right = max(right, intervals[index][1])index += 1res.append([left, right])while index < len(intervals):res.append(intervals[index])index += 1return res

LeetCode77-组合（从[1,n]中无放回抽取k个数））

说明：回溯法的入门必备题，题目非常简单，但是透露着杀气。

def combine(self, n: int, k: int) -> List[List[int]]:res =[]def backtrack(l,r,k,cur_array):if len(cur_array)==k: # 先写递归终止条件res.append(list(cur_array))returnfor i in range(l,n+1):cur_array.append(i)backtrack(i+1,n,k,cur_array)cur_array.pop()backtrack(1,n,k,[])return res

• 回溯法的四个参数意思：①所有可以加入元素的左边界 ②所有可以加入元素的右边界 ③ 终止条件（期望的数组长度） ④当前结果。
• 回溯法采用递归，先写递归的终止条件，注意是新建一个list放进去。
• 回归法由两部分组成：【终止条件】+【把当前可能元素放到当前结果再继续递归】（三步）

！LeetCode94-二叉树中序遍历（左中右）

记录：中序可用递归、栈；递归需要新建一个全局变量；

def inorderTraversal(self, root: Optional[TreeNode]) -> List[int]:res  = []        def my_fun(root):if root is None:passelif root.left is None:res.append(root.val)my_fun(root.right)else:my_fun(root.left)res.append(root.val)my_fun(root.right)my_fun(root)return res

解题思路：本来想直接递归调用自己，但是发现必须有一个全局的数组，因此只能新建一个全局变量，然后递归去append。（半夜写出来的，耗时秒杀100%，树的问题都优先用递归解决）

LeetCode100:相同的树
题解：直接递归； 如果不让用递归的话，就先判断当前节点，如果没有就吧子树放到list中。这样两个树遍历是一样的。遇到不相同的就直接返回了。
Leetcode129-求根节点到叶节点数字之和
题目描述不清晰，应该是所有到叶子节点按位组成的数字的和。肯定是递归，就是把所有子树*10+当前树。
LeetCode103-二叉树的锯齿形层序遍历
给了你数组了。直接for循环，每次计算出当前层的个数和是奇偶性，然后进行打印。