记录了初步解题思路 以及本地实现代码;并不一定为最优 也希望大家能一起探讨 一起进步
目录
- 1/9 1806. 还原排列的最少操作步数
- 1/10 753. 破解保险箱
- 1/11 2283. 判断一个数的数字计数是否等于数位的值
- 1/12 1807. 替换字符串中的括号内容
- 1/13 2287. 重排字符形成目标字符串
- 1/14 1819. 序列中不同最大公约数的数目
- 1/15 2293. 极大极小游戏
1/9 1806. 还原排列的最少操作步数
模拟
def reinitializePermutation(n):""":type n: int:rtype: int"""perm = list(range(n))target = list(range(n))step = 0while True:step+=1perm = [perm[n//2+(i-1)//2] if i%2 else perm[i//2] for i in range(n)]if perm==target:return step
1/10 753. 破解保险箱
数学方法
https://leetcode.cn/problems/cracking-the-safe/solutions/393529/po-jie-bao-xian-xiang-by-leetcode-solution/
def crackSafe(n, k):""":type n: int:type k: int:rtype: str"""mod = 10**(n-1)ans = []mem = set()def dfs(node):for i in range(k):num = node*10+iif num not in mem:mem.add(num)dfs(num%mod)ans.append(str(i))dfs(0)return "".join(ans)+"0"*(n-1)
1/11 2283. 判断一个数的数字计数是否等于数位的值
统计各个数字出现次数
遍历检查是否一致
def digitCount(num):""":type num: str:rtype: bool"""m = {}for c in num:m[int(c)] = m.get(int(c),0)+1for i in range(len(num)):if m.get(i,0)!=int(num[i]):return Falsereturn True
1/12 1807. 替换字符串中的括号内容
按序遍历 m存储knowledge一一对应的内容
遇到(时 获取括号内容 在m中查询
def evaluate(s, knowledge):""":type s: str:type knowledge: List[List[str]]:rtype: str"""loc = 0n = len(s)ans = ""m = {}for k,v in knowledge:m[k] = vwhile loc<n:if s[loc]=="(":loc +=1cur = ""while s[loc]!=")":cur +=s[loc]loc+=1if cur in m:ans +=m[cur]else:ans +="?"else:ans +=s[loc]loc+=1return ans
1/13 2287. 重排字符形成目标字符串
统计s,target中各个字符出现的个数 计算target最多能够出现次数
def rearrangeCharacters(s, target):""":type s: str:type target: str:rtype: int"""t = {}for c in target:t[c] = t.get(c,0)+1cur = {}for c in s:cur[c] = cur.get(c,0)+1ans = 100for k,v in t.items():ans = min(ans,cur.get(k,0)//v)return ans
1/14 1819. 序列中不同最大公约数的数目
gcd辗转相除法求最大公约数
最大值为maxv 公约数的取值范围为[1,maxv]
value[num] 记录数组nums中的数值num
遍历所有公约数的可能性 公约数i
检查所有i的倍数j=x*i 如果j存在于nums 记录当前subgcd=j
如果得到当前subgcd=i 说明公约数i可以得到 ans+1
def countDifferentSubsequenceGCDs(nums):""":type nums: List[int]:rtype: int"""def gcd(a,b):if a<b:a,b=b,awhile b>0:a,b = b,a%breturn amaxv = max(nums)value = [False] * (maxv+1)for num in nums:value[num] = Trueans = 0for i in range(1,maxv+1):subgcd = 0for j in range(i,maxv+1,i):if value[j]:if subgcd==0:subgcd = jelse:subgcd = gcd(subgcd,j)if subgcd == i:ans +=1breakif subgcd<i:breakreturn ans
1/15 2293. 极大极小游戏
记录当前长度n 在原有数组内根据规则计算
def minMaxGame(nums):""":type nums: List[int]:rtype: int"""n = len(nums)while n>1:for i in range(0,n,2):if (i//2)%2==0:nums[i//2] = min(nums[i],nums[i+1])else:nums[i//2] = max(nums[i],nums[i+1])n //=2return nums[0]