做网站布为网,建设玩偶网站最终目的,达内教育,南宁自助建站模板下载记录了初步解题思路 以及本地实现代码#xff1b;并不一定为最优 也希望大家能一起探讨 一起进步 目录 3/18 303. 区域和检索 - 数组不可变3/19 1793. 好子数组的最大分数3/20 1969. 数组元素的最小非零乘积3/21 2671. 频率跟踪器3/22 2617. 网格图中最少访问的格子数3/23 254…记录了初步解题思路 以及本地实现代码并不一定为最优 也希望大家能一起探讨 一起进步 目录 3/18 303. 区域和检索 - 数组不可变3/19 1793. 好子数组的最大分数3/20 1969. 数组元素的最小非零乘积3/21 2671. 频率跟踪器3/22 2617. 网格图中最少访问的格子数3/23 2549. 统计桌面上的不同数字3/24 3/18 303. 区域和检索 - 数组不可变 前缀和 nums[x]记录0~x的元素和 计算i~j之间的元素和为nums[j]-nums[i-1]即可 class NumArray(object):def __init__(self, nums)::type nums: List[int]pre 0self.nums [0]for n in nums:prenself.nums.append(pre)def sumRange(self, i, j)::type i: int:type j: int:rtype: intreturn self.nums[j1]-self.nums[i] 3/19 1793. 好子数组的最大分数 双指针 为了确定l,r 两个都从k开始向左向右移动 比较哪一边的数值较大则往哪边移动 minv记录当前区间最小值 def maximumScore(nums, k)::type nums: List[int]:type k: int:rtype: intn len(nums)minv nums[k]ans nums[k]l r kfor _ in range(n-1):if r n-1 or l0 and nums[l-1]nums[r1]:l-1minv min(minv,nums[l])else:r1minv min(minv,nums[r])ans max(ans,minv*(r-l1))return ans 3/20 1969. 数组元素的最小非零乘积 每一次操作 并不会改变元素的和 而在元素和不变的情况下 要想使得乘积最小应该尽可能最大化元素的差值 最大的元素为 2p-1 无论怎么交换 差值不会变大 不考虑 剩余元素可以首尾配对 x与2p-1-x配对 一个数只保留最低位1 剩余的给另一个 可以得到 1 和 2**p-2 两个值相乘 最后乘积为(2p-1)*(2p-2)(2(p-1)-1) def minNonZeroProduct(p)::type p: int:rtype: intMOD10**97if p1:return 1def power(x,n):x_init xb []while n0:r n%2b.insert(0,r)n n//2for i in range(1,len(b)):x x*x%MODif b[i]1:x x*x_init%MODreturn xbase 2**pnum base//2-1x (base-2)%MODans 1ans power(x,num)%MODans (ans*((base-1)%MOD))%MODreturn ans 3/21 2671. 频率跟踪器 hash表记录次数 num[i]记录数字i出现的次数 cnt[q]记录频率为q的数字个数 class FrequencyTracker(object):def __init__(self):self.num {}self.cnt {}def add(self, number)::type number: int:rtype: Noneself.cnt[self.num.get(number,0)] self.cnt.get(self.num.get(number,0),0)-1self.num[number] self.num.get(number,0)1self.cnt[self.num.get(number,0)] self.cnt.get(self.num.get(number,0),0)1def deleteOne(self, number)::type number: int:rtype: Noneif self.num.get(number,0)0:returnself.cnt[self.num.get(number,0)] self.cnt.get(self.num.get(number,0),0)-1self.num[number] self.num.get(number,0)-1self.cnt[self.num.get(number,0)] self.cnt.get(self.num.get(number,0),0)1def hasFrequency(self, frequency)::type frequency: int:rtype: boolreturn self.cnt.get(frequency,0)0 3/22 2617. 网格图中最少访问的格子数 对于grid[i][j] 已知到这个位置最少需要f步 向右走 最远到达该行的grid[i][j]j 向下走 最远到达该列的grid[i][j]i 在这一行 维持一个最小堆 保存rowh(f,grid[i][j]j) 表示上一步走了f的最远可以到达位置 列同理colh 接下来考虑 如何得到grid[i][j]最少需要f 分别处理rowh,colh 对于堆顶最小f 它的距离如果到不了当前的位置i/j 则将其弹出 最后可以得到行、列分别能够到达当前位置的两个最小f 即rowh[0][0],colh[0][0] 对于当前的最小步数f min(rowh[0][0],colh[0][0])1 def minimumVisitedCells(grid)::type grid: List[List[int]]:rtype: intimport heapqm,nlen(grid),len(grid[0])if m1 and n1:return 1colhs [[] for _ in range(m)]for i,row in enumerate(grid):rowh[]for j,(g,colh) in enumerate(zip(row,colhs)):while rowh and rowh[0][1]j:heapq.heappop(rowh)while colh and colh[0][1]i:heapq.heappop(colh)f float(inf) if i or j else 1if rowh:f rowh[0][0]1if colh:f min(f,colh[0][0]1)if g and ffloat(inf):heapq.heappush(rowh,(f,gj))heapq.heappush(colh,(f,gi))return f if ffloat(inf) else -1 3/23 2549. 统计桌面上的不同数字 n100 最差的情况 对于已有数字x 下一天x-1必定会出现在桌面上 x,x-1,x-2…,2 所以在10^9内 如果n1则2~n都会出现在桌面上 如果n1 则只有1 def distinctIntegers(n)::type n: int:rtype: intreturn 1 if n1 else n-1 3/24
