LeetCode 每日一题 2024/6/17-2024/6/23

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

6/17 522. 最长特殊序列 II

check(a,b)判断b是否包含子序列a
较长的序列肯定不是短序列的子序列
将数组内序列从长倒短排序
判断某一序列是否满足独有子序列条件

def findLUSlength(strs):""":type strs: List[str]:rtype: int"""def check(a,b):loca,locb = 0,0while loca<len(a) and locb<len(b):if a[loca]==b[locb]:loca+=1locb+=1return loca==len(a)strs.sort(key=lambda x:len(x),reverse=True)for i,s in enumerate(strs):tag = Truefor j,t in enumerate(strs):if len(t)<len(s):breakif i!=j and check(s,t):tag = Falsebreakif tag:return len(s)return -1

6/18 2288. 价格减免

按空格分词
判断一个单词是否是价格 如果是价格那么打折

def discountPrices(sentence, discount):""":type sentence: str:type discount: int:rtype: str"""l=sentence.split(" ")ans = []for s in l:if s[0]=="$"and s[1:].isdigit():v = float(s[1:])*(100-discount)/100ans.append("$"+format(v,'.2f'))else:ans.append(s)return ' '.join(ans)

6/19 2713. 矩阵中严格递增的单元格数

row,col分别记录每一行 每一列的结果最大值
mp[v]记录数值v出现的位置
将数值v从小打到排序考虑
对于位置i,j 他的值为row[i] col[j]最大值+1
同时更新这个位置的最大值row,col

def maxIncreasingCells(mat):""":type mat: List[List[int]]:rtype: int"""from collections import defaultdictmp=defaultdict(list)m,n=len(mat),len(mat[0])row = [0]*mcol = [0]*nfor i in range(m):for j in range(n):mp[mat[i][j]].append((i,j))for _,pos in sorted(mp.items(),key=lambda x:x[0]):ans = [max(row[i],col[j])+1 for i,j in pos]for (i,j),d in zip(pos,ans):row[i]=max(row[i],d)col[j]=max(col[j],d)return max(row)

6/20 2748. 美丽下标对的数目

gcd得到两数最大公约数
m[x]记录第一个数字为x的元素个数
从前往后依次分析

def countBeautifulPairs(self, nums):""":type nums: List[int]:rtype: int"""def gcd(x,y):if x<y:x,y=y,xwhile True:x,y=y,x%yif y==0:return xans = 0m = [0]*10for num in nums:for v in range(1,10):if gcd(num%10,v)==1:ans += m[v]while num>=10:num//=10m[num]+=1return ans

6/21 LCP 61. 气温变化趋势

使用-1表示下降 0表示平稳 1表示上升
cur 记录变化趋势连续相同的天数

def temperatureTrend(temperatureA, temperatureB):""":type temperatureA: List[int]:type temperatureB: List[int]:rtype: int"""def func(x,y):if x==y:return 0return -1 if x>y else 1n = len(temperatureA)ans = cur = 0for i in range(1,n):a = func(temperatureA[i-1],temperatureA[i])b = func(temperatureB[i-1],temperatureB[i])if a==b:cur +=1ans = max(ans,cur)else:cur = 0return ans

6/22 2663. 字典序最小的美丽字符串

回文串判断s[i]!=s[i-1] s[i]!=s[i-2]即可
字典序最小 尽量改右侧的字符

def smallestBeautifulString(s, k):""":type s: str:type k: int:rtype: str"""k += ord('a')s = list(map(ord,s))n=len(s)i = n-1s[i]+=1while i<n:if s[i]==k:if i==0:return ""s[i]=ord('a')i-=1s[i]+=1elif i and s[i]==s[i-1] or i>1 and s[i]==s[i-2]:s[i]+=1else:i+=1return ''.join(map(chr,s))

6/23 520. 检测大写字母

依次判断三个条件
全是大写;全是小写;首字母大写，后续小写

def detectCapitalUse(word):""":type word: str:rtype: bool"""if word==str.upper(word):return Trueif word==str.lower(word):return Trueif 'A'<=word[0]<='Z' and word[1:]==str.lower(word[1:]):return Truereturn False