LeetCode 每日一题 2023/1/23-2023/1/29

记录了初步解题思路 以及本地实现代码；并不一定为最优 也希望大家能一起探讨 一起进步

---

1/23 2303. 计算应缴税款总额

根据收入依次查看每个层级

def calculateTax(brackets, income):""":type brackets: List[List[int]]:type income: int:rtype: float"""ans = 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)**2<=r*r:num+=1ans.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 diff>0:if diff<26:ans[loc]=chr(ord("a")+diff)diff = 0else:ans[loc] = "z"diff-=25loc-=1return "".join(ans)

---

1/27 2309. 兼具大小写的最好英文字母

l记录26个字母是否出现
从头遍历所有字母 记录所有出现的小写字母
第二次遍历 搜索所有大写字母 查看是否出现过小写字母
如果有则比较

def greatestLetter(s):""":type s: str:rtype: str"""l = [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 c>ans:ans = creturn ans

---

1/28 1664. 生成平衡数组的方案数

对于坐标i
分别使用odd1,odd2记录i之前奇数位之和 与i之后奇数位之和
同理even1,even2记录i前后偶数位之和
需要寻找odd1+even2=odd2+even1的i

def waysToMakeFair(nums):""":type nums: List[int]:rtype: int"""ans = 0odd1=odd2=even1=even2=0for i,num in enumerate(nums):if i%2:odd2+=numelse:even2+=numfor i,num in enumerate(nums):if i%2:odd2-=numelse:even2-=numif odd1+even2==odd2+even1:ans +=1if i%2:odd1+=numelse:even1+=numreturn ans

---

1/29 2315. 统计星号

标记是否在竖线对内

def countAsterisks(s):""":type s: str:rtype: int"""ans = 0tag = Falsefor c in s:if c=="|":tag = tag^1elif c=="*" and not tag:ans +=1return ans

---