本周的题目并不太难。第一题5315。最大的数字由6和9道简单题组成。直接遍历，把前面的6改成9就可以了。用python很方便，但是需要注意的是python字符串是不可变的，需要转换成list方便操作（当然我是从int转换成str和然后列出）类解决方案：defmaximum69Number(self,num:int)->int:x=list(str(num))foriinrange(len(x)):ifx[i]=='6':x[i]='9'breakreturnint(''.join(x))在题目评论里看到别人的解法，太强class解法：defmaximum69Number(self,num:int)->int:returnint(str(num).replace('6','9',1))第二题5316.竖排字，难度远低于题库第6题之字形变换。这个问题很高大上。估计很多人都做过。这个题目用python特别方便，甚至还有去除尾随空格的功能。类解决方案：defprintVertically(self,s:str)->List[str]:s=s.split('')max_l=0forwins:max_l=max(max_l,len(w))r=[[]foriinrange(max_l)]forwins:foriinrange(max_l):ifiTreeNode:defdel_t(t):ift.left:ifdel_t(t.left):t.left=Noneift.right:ifdel_t(t.right):t.right=Noneifnott.leftandnott.right:ift.val==target:returnTruereturnFalseifdel_t(root):returnNonereturnroot问题45318.最少要多少个水龙头才能灌溉花园我在实习面试的时候被问到。线段覆盖问题。贪心算法。面试的时候想到了用递归的方法，这次就迭代写了。思路是：先将每个水龙头的范围转化为区间，做成区间数组。比如例子1转换为：[[0,3],[0,5],[1,3],[2,4]]这里做了两个优化：如果长度为0，则超出的值忽略0到n的范围它以区间[0,n]结束，然后我们可以根据区间的左端点进行排序。（上面的数组已经是这个顺序了）其实还有一个优化：如果一个范围完全被另一个范围覆盖了，那么这个范围也是无效的，应该删除，比如[1,3]完全落在[0,3]里面。结果这里只剩下[0,5]:[[0,5]]所以这个例子不好，可以看例子3n=7,ranges=[1,2,1,0,2,1,0,1]经过上面的操作，剩下的区间其实只有三个：[(0,3),(2,6),(6,7)]所以简单去掉之后的方法是：如果数ofintervals为0或者第一个区间覆盖不了0，直接返回-1然后开始贪心：第一个区间必须被选中，ans变量统计选中区间的个数判断是否可以覆盖，如果可以,返回ans从下一个区间开始,在所有可以选择的区间中(如果这个区间的左端点小于等于上一个选择的区间的右端点,可以选择),找到带有最大的右端点，select，如果没有option，返回-1这段代码写的不够精炼class解决方法：defminTaps(self,n:int,ranges:List[int])->int:#rangesconvertedto范围段=[]foriinrange(n+1):ifranges[i]>0:seg.append((max(0,i-ranges[i]),min(n,i+ranges[i])))#移除被其他区间覆盖的区间s2={}forsinseg:ifs[0]notins2:s2[s[0]]=[]s2[s[0]].append(s)seg=[]对于s2中的k：t=s2[k][0]对于s2[k]中的xx：如果xx[1]>t[1]：t=xx段。append(t)s2={}forsinseg:ifs[1]notins2:s2[s[1]]=[]s2[s[1]].append(s)seg=[]forkins2:t=s2[k][0]forxxins2[k]:ifxx[0]
