记录了初步解题思路 以及本地实现代码并不一定为最优 也希望大家能一起探讨 一起进步目录5/18 1345. 跳跃游戏 IV5/19 2540. 最小公共值5/20 2657. 找到两个数组的前缀公共数组5/21 3043. 最长公共前缀的长度5/22 33. 搜索旋转排序数组5/231752. 检查数组是否经排序和轮转得到5/24 1340. 跳跃游戏 V5/18 1345. 跳跃游戏 IVBFSvalueToloc记录每个值的位置所在对于arr[loc]v他可以到达 loc1,loc-1或者valueToloc[v]中的所有位置第一次搜索到必定是最少次数 visited记录被搜索到的位置同个值的位置搜索过后之后不需要搜索这个地方 删除valueToloc[v]defminJumps(arr): :type arr: List[int] :rtype: int fromcollectionsimportdefaultdict,deque valueTolocdefaultdict(list)forloc,vinenumerate(arr):valueToloc[v].append(loc)nlen(arr)ldeque()l.append((0,0))visitedset()visited.add(0)whilel:loc,stepl[0]iflocn-1:returnstep valuearr[loc]l.popleft()fortmpinvalueToloc[value][::-1]:iftmpnotinvisited:visited.add(tmp)l.append((tmp,step1))valueToloc[value][]ifloc1nandloc1notinvisited:visited.add(loc1)l.append((loc1,step1))ifloc-10andloc-1notinvisited:visited.add(loc-1)l.append((loc-1,step1))arr[100,-23,-23,404,100,23,23,23,3,404]print(minJumps(arr))5/19 2540. 最小公共值双指针 分别指向两个数组如果两个指针指向的值相等 则返回该值如果两个指针指向的值不相等 则移动较小的指针defgetCommon(nums1,nums2): :type nums1: List[int] :type nums2: List[int] :rtype: int i,j0,0whileilen(nums1)andjlen(nums2):ifnums1[i]nums2[j]:returnnums1[i]elifnums1[i]nums2[j]:i1else:j1return-15/20 2657. 找到两个数组的前缀公共数组一共50位 用一个50位的二进制数表示将一个二进制数的第i位设置为1 表示值为i的元素在数组中将两个二进制数相与 得到的结果就是两个数组的前缀公共数组deffindThePrefixCommonArray(A,B): :type A: List[int] :type B: List[int] :rtype: List[int] nlen(A)ba,bb0,0defgetOne(x):ans0whilex:ansx1x1returnans ret[]foriinrange(n):ba|1A[i]bb|1B[i]numgetOne(babb)ret.append(num)returnret5/21 3043. 最长公共前缀的长度将arr1中的所有数字的十进制前缀放入一个集合中遍历arr2中的每个数字 不断去掉末位 直到该数字出现在集合中记录该数字的位数 取最大值即为答案deflongestCommonPrefix(arr1,arr2): :type arr1: List[int] :type arr2: List[int] :rtype: int prefix_setset()fornuminarr1:xnumifx0:prefix_set.add(0)whilex0:prefix_set.add(x)x//10ans0fornuminarr2:xnumifx0and0inprefix_set:ansmax(ans,1)continuewhilex0:ifxinprefix_set:ansmax(ans,len(str(x)))breakx//10returnans5/22 33. 搜索旋转排序数组根据题目 假设升序list[a0…an,b0…bm] a0anb0bm在an进行了旋转 变成了[b0…bm,a0…an] b0bm a0an选取list中间点mid 会出现两种情况1.[b0…mid…bm,a0…an] 此时 midb0an 可知 mid左侧为升序list2.[b0…bm,a0…mid…an] 此时 mid an 可知mid右侧为升序list所以我们可以取中间的一个点 与当前List最右边的点比较 可以得到左边或者右边是升序队列比较查看target是否在升序队列中如果不在 将另外一边队列 重新选点 重复上述操作如果在 则在升序队列中二分defsearch(nums,target): :type nums: List[int] :type target: int :rtype: int left0rightlen(nums)-1whileleftright:midint((leftright)/2)ifnums[mid]target:returnmidifnums[mid]nums[right]:##右边有序ifnums[mid]targetandtargetnums[right]:leftmid1else:rightmid-1elifnums[left]targetandtargetnums[mid]:rightmid-1else:leftmid1return-15/231752. 检查数组是否经排序和轮转得到原数组所有元素非递减排列假设轮转x个位置source[x,…,n-1]source[0,…,x-1] nums找到nums[i-1]nums[i]检查0~i-1 i~n-1是否都非递减defcheck(nums): :type nums: List[int] :rtype: bool nlen(nums)x0foriinrange(1,n):ifnums[i]nums[i-1]:xibreakifx0:returnTrueforiinrange(x1,n):ifnums[i]nums[i-1]:returnFalsereturnnums[0]nums[-1]5/24 1340. 跳跃游戏 V设 dfs(i) 表示「从下标 i 出发最多能访问多少个位置包含 i 自己」。从 i 可以向左/右最多跳 d 步但有两个限制只能跳到更小值arr[j] arr[i]一旦某个方向遇到 arr[k] arr[i]该方向后续位置都不可达被挡住立即停止该方向搜索。状态转移dfs(i) 1 max(dfs(j))其中 j 是 i 在左右两侧可直接跳到的位置若没有可跳位置则 dfs(i) 1。用缓存保存 dfs(i) 的结果避免重复计算。最终答案是 max(dfs(i))。defmaxJumps(arr,d): :type arr: List[int] :type d: int :rtype: int fromfunctoolsimportlru_cache nlen(arr)lru_cache(maxsizeNone)defdfs(i):best1# 向左跳forstepinrange(1,d1):ji-stepifj0:breakifarr[j]arr[i]:breakbestmax(best,1dfs(j))# 向右跳forstepinrange(1,d1):jistepifjn:breakifarr[j]arr[i]:breakbestmax(best,1dfs(j))returnbestreturnmax(dfs(i)foriinrange(n))
