成都 广告公司网站建设,网站建设培训机构,郑州小程序设计外包,网站制作是怎样做的记录了初步解题思路 以及本地实现代码#xff1b;并不一定为最优 也希望大家能一起探讨 一起进步 目录1/23 2303. 计算应缴税款总额1/24 1828. 统计一个圆中点的数目1/25 1632. 矩阵转换后的秩1/26 1663. 具有给定数值的最小字符串1/27 2309. 兼具大小写的最好英文字母1/28 16…记录了初步解题思路 以及本地实现代码并不一定为最优 也希望大家能一起探讨 一起进步 目录1/23 2303. 计算应缴税款总额1/24 1828. 统计一个圆中点的数目1/25 1632. 矩阵转换后的秩1/26 1663. 具有给定数值的最小字符串1/27 2309. 兼具大小写的最好英文字母1/28 1664. 生成平衡数组的方案数1/29 2315. 统计星号1/23 2303. 计算应缴税款总额 根据收入依次查看每个层级 def calculateTax(brackets, income)::type brackets: List[List[int]]:type income: int:rtype: floatans 0.0pre 0for up,p in brackets:if income up:ans (up-pre)*p*0.01else:ans (income-pre)*p*0.01breakpre upreturn ans 1/24 1828. 统计一个圆中点的数目 对于每个圆 跟每个点比较 点与圆心的距离小于等于半径 就在园内 def countPoints(points, queries)::type points: List[List[int]]:type queries: List[List[int]]:rtype: List[int]ans []for x,y,r in queries:num 0for i,j in points:if (i-x)**2(j-y)**2r*r:num1ans.append(num)return ans 1/25 1632. 矩阵转换后的秩 并查集 拓扑排序 官解 https://leetcode.cn/problems/rank-transform-of-a-matrix/solutions/2075052/ju-zhen-zhuan-huan-hou-de-zhi-by-leetcod-biw0/ class Solution:def matrixRankTransform(self, matrix: List[List[int]]) - List[List[int]]:m, n len(matrix), len(matrix[0])uf UnionFind(m, n)for i, row in enumerate(matrix):num2indexList defaultdict(list)for j, num in enumerate(row):num2indexList[num].append([i, j])for indexList in num2indexList.values():i1, j1 indexList[0]for k in range(1, len(indexList)):i2, j2 indexList[k]uf.union(i1, j1, i2, j2)for j in range(n):num2indexList defaultdict(list)for i in range(m):num2indexList[matrix[i][j]].append([i, j])for indexList in num2indexList.values():i1, j1 indexList[0]for k in range(1, len(indexList)):i2, j2 indexList[k]uf.union(i1, j1, i2, j2)degree Counter()adj defaultdict(list)for i, row in enumerate(matrix):num2index {}for j, num in enumerate(row):num2index[num] (i, j)sortedArray sorted(num2index.keys())for k in range(1, len(sortedArray)):i1, j1 num2index[sortedArray[k - 1]]i2, j2 num2index[sortedArray[k]]ri1, rj1 uf.find(i1, j1)ri2, rj2 uf.find(i2, j2)degree[(ri2, rj2)] 1adj[(ri1, rj1)].append([ri2, rj2])for j in range(n):num2index {}for i in range(m):num matrix[i][j]num2index[num] (i, j)sortedArray sorted(num2index.keys())for k in range(1, len(sortedArray)):i1, j1 num2index[sortedArray[k - 1]]i2, j2 num2index[sortedArray[k]]ri1, rj1 uf.find(i1, j1)ri2, rj2 uf.find(i2, j2)degree[(ri2, rj2)] 1adj[(ri1, rj1)].append([ri2, rj2])rootSet set()ranks {}for i in range(m):for j in range(n):ri, rj uf.find(i, j)rootSet.add((ri, rj))ranks[(ri, rj)] 1q deque([[i, j] for i, j in rootSet if degree[(i, j)] 0])while q:i, j q.popleft()for ui, uj in adj[(i, j)]:degree[(ui, uj)] - 1if degree[(ui, uj)] 0:q.append([ui, uj])ranks[(ui, uj)] max(ranks[(ui, uj)], ranks[(i, j)] 1)res [[1] * n for _ in range(m)]for i in range(m):for j in range(n):ri, rj uf.find(i, j)res[i][j] ranks[(ri, rj)]return resclass UnionFind:def __init__(self, m, n):self.m mself.n nself.root [[[i, j] for j in range(n)] for i in range(m)]self.size [[1] * n for _ in range(m)]def find(self, i, j):ri, rj self.root[i][j]if [ri, rj] [i, j]:return [i, j]self.root[i][j] self.find(ri, rj)return self.root[i][j]def union(self, i1, j1, i2, j2):ri1, rj1 self.find(i1, j1)ri2, rj2 self.find(i2, j2)if [ri1, rj1] ! [ri2, rj2]:if self.size[ri1][rj1] self.size[ri2][rj2]:self.root[ri2][rj2] [ri1, rj1]self.size[ri1][rj1] self.size[ri2][rj2]else:self.root[ri1][rj1] [ri2, rj2]self.size[ri2][rj2] self.size[ri1][rj1] 1/26 1663. 具有给定数值的最小字符串 字典序最小则开头尽量多的a 结尾尽量多的z 初始设置n个a 如果达不到k 则在最后改一个为z 以此类推 def getSmallestString(n, k)::type n: int:type k: int:rtype: str ans [a]*ndiff k-nloc n-1while diff0:if diff26:ans[loc]chr(ord(a)diff)diff 0else:ans[loc] zdiff-25loc-1return .join(ans) 1/27 2309. 兼具大小写的最好英文字母 l记录26个字母是否出现 从头遍历所有字母 记录所有出现的小写字母 第二次遍历 搜索所有大写字母 查看是否出现过小写字母 如果有则比较 def greatestLetter(s)::type s: str:rtype: strl [0]*26ans for c in s:if c.islower():ind ord(c)-ord(a)l[ind] 1for c in s:if c.isupper():ind ord(c)-ord(A)if l[ind]1 and cans:ans creturn ans 1/28 1664. 生成平衡数组的方案数 对于坐标i 分别使用odd1,odd2记录i之前奇数位之和 与i之后奇数位之和 同理even1,even2记录i前后偶数位之和 需要寻找odd1even2odd2even1的i def waysToMakeFair(nums)::type nums: List[int]:rtype: intans 0odd1odd2even1even20for i,num in enumerate(nums):if i%2:odd2numelse:even2numfor i,num in enumerate(nums):if i%2:odd2-numelse:even2-numif odd1even2odd2even1:ans 1if i%2:odd1numelse:even1numreturn ans 1/29 2315. 统计星号 标记是否在竖线对内 def countAsterisks(s)::type s: str:rtype: intans 0tag Falsefor c in s:if c|:tag tag^1elif c* and not tag:ans 1return ans
