LeetCode 每日一题 2023/12/18-2023/12/24
记录了初步解题思路 以及本地实现代码；并不一定为最优 也希望大家能一起探讨 一起进步
目录
- 12/18 162. 寻找峰值
- 12/19 1901. 寻找峰值 II
- 12/20 2828. 判别首字母缩略词
- 12/21 2866. 美丽塔 II
- 12/22 1671. 得到山形数组的最少删除次数
- 12/23 1962. 移除石子使总数最小
- 12/24 1954. 收集足够苹果的最小花园周长
12/18 162. 寻找峰值
二分
因为边界为负无穷
只要往高坡移动 必定能找到峰值
def findPeakElement(nums):""":type nums: List[int]:rtype: int"""l,r = 0,len(nums)-1while l<r:mid = l+((r-l)>>1)if nums[mid]<nums[mid+1]:l = mid+1else:r = midreturn l12/19 1901. 寻找峰值 II
按每一行来二分 对于某一行i来说 取其中最大值mat[i][j]
判断该最大值与上下相邻值的关系
如果都大于邻值 说明该位置为峰顶
如果存在大的邻值 说明该方向存在峰顶
def findPeakGrid(mat):""":type mat: List[List[int]]:rtype: List[int]"""l,r = 0,len(mat)-2while l<=r:mid = (l+r)>>1mx = max(mat[mid])j = mat[mid].index(mx)if mx>mat[mid+1][j]:r = mid-1else:l = mid+1i = lreturn [i,mat[i].index(max(mat[i]))]12/20 2828. 判别首字母缩略词
依次判断
def isAcronym(words, s):""":type words: List[str]:type s: str:rtype: bool"""n = len(words)if n!=len(s):return Falsefor i in range(n):if words[i][0]!=s[i]:return Falsereturn True12/21 2866. 美丽塔 II
以i为山顶
计算0~i能够得到的最大和left[i]
计算i~n能够得到的最大和right[i]
left[i]+right[i+1]就是最大和
单调栈来统计
def maximumSumOfHeights(maxHeights):""":type maxHeights: List[int]:rtype: int"""n=len(maxHeights)right = [0]*(n+1)st = [n]s = 0for i in range(n-1,-1,-1):v = maxHeights[i]while len(st)>1 and v<=maxHeights[st[-1]]:j = st.pop()s -= maxHeights[j]*(st[-1]-j)s+=v*(st[-1]-i)right[i]=sst.append(i)ans = sst=[-1]l = 0for i,v in enumerate(maxHeights):while len(st)>1 and v<=maxHeights[st[-1]]:j = st.pop()l -= maxHeights[j]*(j-st[-1])l+=v*(i-st[-1])ans = max(ans,l+right[i+1])st.append(i)return ans12/22 1671. 得到山形数组的最少删除次数
左侧到山顶是递增 山顶到右侧是递减
只考虑一边 即求递增子序列
另一边倒序后 同样求递增子序列
def minimumMountainRemovals(nums):""":type nums: List[int]:rtype: int"""n = 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 i>1 and j>1:ans = max(ans,i+j-1)return n-ans12/23 1962. 移除石子使总数最小
大顶堆 每次取最大一堆石子进行操作
def minStoneSum(piles, k):""":type piles: List[int]:type k: int:rtype: int"""import heapqs = sum(piles)l = [-x for x in piles]heapq.heapify(l)while k>0:v = -heapq.heappop(l)s -= v//2v -= v//2heapq.heappush(l,-v)k-=1return s12/24 1954. 收集足够苹果的最小花园周长
找规律 可以划分为四块数量相同的区域
对于边长2n的正方形
一份区域内元素和n(n+1)(2n+1)/2
所以总和为2n(n+1)(2n+1)
def minimumPerimeter(neededApples):""":type neededApples: int:rtype: int"""n = int((neededApples/4)**(1/3))if 2*n*(n+1)*(2*n+1)<neededApples:n+=1return 8*n