解题思路： 1. 构建并查集 2. 判断区域是否重叠 3. 合并， 人数相加，新冠传递，坐标叠加 4. 返回新冠集合中的人数 class Pos: def __init__(self, x, y): self.x = x self.y = y def __repr__(self): return "x={},y={}".format(self.x, self.y) class Node: def __init__(self, pos, has_COV19): s...

解题思路： 1. 01背包问题 2. 背包容量为总额的一半 class Solution: def maxPresent(self , presentVec ): """ 01 背包 """ if len(presentVec) == 0: return 0 sum_pre = sum(presentVec) sum_vec = int(sum_pre // 2) + 1 # 背包的容量 # 初始化 ...

解题思路： 1. 边界条件，长度小于等于2，就返回数组长度 2. 单调递增子序列的长度 3. 反向单调递减子序列长度 class Solution: def __get_dp_up(self, numberList): """ 获取单调递增的最长子序列（可以不连续） """ dp_up = [1 for i in range(len(numberList))] for i in range(1, len(numberList)): for...

解题思路（参考爬楼梯的例子）： 1. 障碍物记录，用字典，方便查找 2. 障碍物在同一列超过3个，就返回0 3. 动态转移方程 dp[0][i] = 0 if "有障碍" else int((dp[0][i-1] + dp[1][i-1]) % base_num) dp[1][i] = 0 if "有障碍" else int((dp[0][i-1] + dp[1][i-1] + dp[2][i-1]) % base_num) dp[2][i] = 0 if "有障碍" els...

解题思路： 1. 判断ip是否合法 2. 判断掩码是否合法 3. 判断ip属于哪一类（A~E类和私有不冲突，即有ip即为A类也为私有，就各统计一次） # -*- coding: utf-8 -*- # 开发者 : QSheng # 代码文件 : HJ18 识别有效的IP地址和掩码并进行分类统计.py # 创建时间 : 2021/7/29 9:58 class Solution: def __judge_ip_is_legal(self, ip_list): """ 判断IP是否合法 ""&...

解题思路： 字符串匹配 正则中无*号，直接匹配长度，长度一致再匹配内容 正则中只有*号，直接返回True 正则中有号也有其他符号，按号切割 注意的点： 1. 正则头和尾有的情况和无号的情况，需要单独考虑 2. 判断两个字符串相等（细节 "?"号 只能匹配字母和数字） # -*- coding: utf-8 -*- # 开发者 : QSheng # 代码文件 : HJ71 字符串通配符.py # 创建时间 : 2021/7/28 11:13 class Solution(): def __is_equal(self, str_1, str...

解题思路： 1. 一个队列（待入站），一个栈（模拟火车站），一个列表（存放结果） 2. 深度优先搜索，遍历所有情况（两个方向，一个出站，一个入站） 结束递归条件（全部出站），保存结果 3. 对结果进行排序（普通冒泡排序会超时，可以用快排，或者在深搜时用插入排序） 4. 一个小细节，因为n<10, 可以把火车出站序列转为一个整数（用于排序比较） # -*- coding: utf-8 -*- # 开发者 : QSheng # 代码文件 : HJ77 火车进站.py # 创建时间 : 2021/7/28 9:07 class Solutio...

解题思路： 1.广度优先搜索 2. 细节： 移动方向，走过标记，前缀记录，终点判断 3. 输出结果，采用栈 # -*- coding: utf-8 -*- # 开发者 : QSheng # 代码文件 : HJ43 迷宫问题.py # 创建时间 : 2021/7/27 17:06 class Solution: def solve(self, matrix, row, col): dir_list = [[-1,0], [1,0], [0,1], [0,-1]] # 四个方向 use...

解题思路： 1. 把3，5的倍数挑出来，分别计算和 2. 采用二进制，表示分组策略（这样可以不采用递归） # -*- coding: utf-8 -*- # 开发者 : QSheng # 代码文件 : HJ93 数组分组.py # 创建时间 : 2021/7/27 10:39 class Solution: def __judge(self, num_oth_list, num_list_len, bin_num, sum_1, sum_2): """ :param num_oth_list: ...

解题思路： 模拟栈 字符串转表达式元素列表 处理基本的运算问题 运算符优先级比较 考虑特殊情况（有括号，有些是负号） 暴力提交，找到出错的用例，不断改进优化（以下代码不是最优的，但是能过所有用例，能力有限，惭愧。。。） class Solution: def __init__(self): self._ch_list = list("+-*/()") self._oper_list = list("+-*/") self._digits_list = list("0123456789&...

解题思路： 1. 将分数拆分成分子和分母，模拟分数运算 1.1 化简分数 (只化简到分子为1的形式) 1.2 比较两个分数的大小 1.3 两个分数做差 2. 遍历因子（分子为1， 分母2~n） 2.1 对待分解的分数，减去因子，如果结果大于0，就记录该因子 2.2 如果结果==0，除了记录该因子，跳出循环 2.3 因子分母+1 class Solution: def _gcd(self, fz, fm): """ 化简分数 (只化简到分子为1的形式...

解题思路: 逆向思维， 判断不可能组成顺子的牌面，其余就是可能顺子 class Solution: def IsContinuous(self, numbers): # write code here numbers_not_zero = list() max_num, min_num = -1, 14 for number in numbers: if number != 0: numbers_not_zero.append(number) ...

解题思路： 1. 分情况讨论即可 1.1 找到对应j的位置 1.2 j上下左右是否有B或J 2.3 j上下左右四个方向是否有C，且无遮挡物 3.4 j上下左右四个方向是否有P，且有一个遮挡物 class Solution: def playchess(self , chessboard ): # write code here row, col = len(chessboard), len(chessboard[0]) # 1. 定位小j location_j = (0, 0) ...

解题思路： 1. 边界条件1，数组长度为1，输出1 边界条件2，数组不重复，输出数组长度 2. 双指针，起始指针start_i, 和结尾指针end_i, arr[start_i: end_i] 保证不重复 且 arr[start_i: end_i+1] 重复 3. 更新的双指针，找出最大长度 class Solution: def _find_end_idx(self, arr, start_i, end_i, curr_i): """找到终点""" ...