做名片赞机器人电脑网站是多少钱,建一个定制网站要多少钱,python做的网站源码,芙蓉区营销型网站建设定制记录了初步解题思路 以及本地实现代码#xff1b;并不一定为最优 也希望大家能一起探讨 一起进步 目录 12/18 162. 寻找峰值12/19 1901. 寻找峰值 II12/20 2828. 判别首字母缩略词12/21 2866. 美丽塔 II12/22 1671. 得到山形数组的最少删除次数12/23 1962. 移除石子使总数最小…记录了初步解题思路 以及本地实现代码并不一定为最优 也希望大家能一起探讨 一起进步 目录 12/18 162. 寻找峰值12/19 1901. 寻找峰值 II12/20 2828. 判别首字母缩略词12/21 2866. 美丽塔 II12/22 1671. 得到山形数组的最少删除次数12/23 1962. 移除石子使总数最小12/24 12/18 162. 寻找峰值 二分 因为边界为负无穷 只要往高坡移动 必定能找到峰值 def findPeakElement(nums)::type nums: List[int]:rtype: intl,r 0,len(nums)-1while lr:mid l((r-l)1)if nums[mid]nums[mid1]:l mid1else:r midreturn l 12/19 1901. 寻找峰值 II 按每一行来二分 对于某一行i来说 取其中最大值mat[i][j] 判断该最大值与上下相邻值的关系 如果都大于邻值 说明该位置为峰顶 如果存在大的邻值 说明该方向存在峰顶 def findPeakGrid(mat)::type mat: List[List[int]]:rtype: List[int]l,r 0,len(mat)-2while lr:mid (lr)1mx max(mat[mid])j mat[mid].index(mx)if mxmat[mid1][j]:r mid-1else:l mid1i lreturn [i,mat[i].index(max(mat[i]))] 12/20 2828. 判别首字母缩略词 依次判断 def isAcronym(words, s)::type words: List[str]:type s: str:rtype: booln len(words)if n!len(s):return Falsefor i in range(n):if words[i][0]!s[i]:return Falsereturn True 12/21 2866. 美丽塔 II 以i为山顶 计算0~i能够得到的最大和left[i] 计算i~n能够得到的最大和right[i] left[i]right[i1]就是最大和 单调栈来统计 def maximumSumOfHeights(maxHeights)::type maxHeights: List[int]:rtype: intnlen(maxHeights)right [0]*(n1)st [n]s 0for i in range(n-1,-1,-1):v maxHeights[i]while len(st)1 and vmaxHeights[st[-1]]:j st.pop()s - maxHeights[j]*(st[-1]-j)sv*(st[-1]-i)right[i]sst.append(i)ans sst[-1]l 0for i,v in enumerate(maxHeights):while len(st)1 and vmaxHeights[st[-1]]:j st.pop()l - maxHeights[j]*(j-st[-1])lv*(i-st[-1])ans max(ans,lright[i1])st.append(i)return ans 12/22 1671. 得到山形数组的最少删除次数 左侧到山顶是递增 山顶到右侧是递减 只考虑一边 即求递增子序列 另一边倒序后 同样求递增子序列 def minimumMountainRemovals(nums)::type nums: List[int]:rtype: intn len(nums)def getLIS(nums):dp[1]*nfor i in range(n):for j in range(i):if nums[j]nums[i]:dp[i] max(dp[i],dp[j]1)return dpleft getLIS(nums)right getLIS(nums[::-1])[::-1]ans 0for i,j in zip(left,right):if i1 and j1:ans max(ans,ij-1)return n-ans 12/23 1962. 移除石子使总数最小 大顶堆 每次取最大一堆石子进行操作 def minStoneSum(piles, k)::type piles: List[int]:type k: int:rtype: intimport heapqs sum(piles)l [-x for x in piles]heapq.heapify(l)while k0:v -heapq.heappop(l)s - v//2v - v//2heapq.heappush(l,-v)k-1return s 12/24
