前言
该系列文章用于我对一周中leetcode每日一题or其他不会的题的复盘总结。
一方面用于自己加深印象，另一方面也希望能对读者的算法能力有所帮助。
该复盘对我来说比较容易的题我会复盘的比较粗糙，反之较为细致
解答语言：Golang
周一：2678. 老人的数目（easy）
题目描述：
给你一个下标从 0 开始的字符串 details 。details 中每个元素都是一位乘客的信息，信息用长度为 15 的字符串表示，表示方式如下：
- 前十个字符是乘客的手机号码。
- 接下来的一个字符是乘客的性别。
- 接下来两个字符是乘客的年龄。
- 最后两个字符是乘客的座位号。
请你返回乘客中年龄 严格大于 60 岁 的人数。
示例 1：
输入： details = ["7868190130M7522","5303914400F9211","9273338290F4010"]
输出： 2
解释： 下标为 0 ，1 和 2 的乘客年龄分别为 75 ，92 和 40 。所以有 2 人年龄大于 60 岁。复盘：
该题就语法题了，对编程语言语法不陌生就没问题。
代码：
func countSeniors(details []string) int {
ans:=0
for _,v:=range details{
age,_:=strconv.Atoi(v[11:13])
if age>60{
ans+=1
}
}
return ans
}周二：1155. 掷骰子等于目标和的方法数（middle）
题目描述：
这里有 n 个一样的骰子，每个骰子上都有 k 个面，分别标号为 1 到 k 。
给定三个整数 n , k 和 target ，返回可能的方式(从总共 kn 种方式中)滚动骰子的数量，使正面朝上的数字之和等于 **target 。
答案可能很大，你需要对 109 + 7 取模 。
示例 ：
输入： n = 2, k = 6, target = 7
输出： 6
解释： 你扔两个骰子，每个骰子有 6 个面。
得到 7 的和有 6 种方法：1+6 2+5 3+4 4+3 5+2 6+1。复盘：
在做这个题的时候，其实若对完全背包比较熟悉，是比较容易能够将此题转化为完全背包的模板的。
不过能分析出如何去遍历并不是特别容易，我在做题时在这一步卡了比较久。
1.首先初始化dp函数 dp[i][j](用i个骰子掷出总数为j的组合数）
2.确定遍历步骤：由于每个骰子都有k面，所以价值j在每轮的范围应当是(0,ik)但由于价值大于target没有意义了，因此可以进行剪枝操作min（target，ik），此外还需要一层遍历去遍历当前骰子数掷出各个数字的情况进行dp状态转移
for i:=1;i<n+1;i++{
for j:=1;j<=min(target,i*k);j++{
for z:=1;z<=min(j,k);z++{
//dp
}
}
}
```
3 . 确定状态转移方程，这个是比较容易的，跟完全背包一个模板
`dp[i][j]=(dp[i][j]+dp[i-1][j-z])%(1e9+7)`
4. 根据该状态方程显然dp[0][0]-dp[0][target]是需要提前初始化的
dp[0][0]=1
## 代码：
```go
func numRollsToTarget(n int, k int, target int) int {
dp:=make([][]int,n+1)
for i:=0;i周三：2698. 求一个整数的惩罚数（middle）
题目描述：
给你一个正整数 `n` ，请你返回 `n` 的 惩罚数 。
`n` 的 惩罚数 定义为所有满足以下条件 `i` 的数的平方和： `1 <= i <= n`
`i * i` 的十进制表示的字符串可以分割成若干连续子字符串，且这些子字符串对应的整数值之和等于 `i` 。
示例 1：
输入： n = 10
输出： 182
解释： 总共有 3 个整数 i 满足要求：
- 1 ，因为 1 * 1 = 1
- 9 ，因为 9 * 9 = 81 ，且 81 可以分割成 8 + 1 。
- 10 ，因为 10 * 10 = 100 ，且 100 可以分割成 10 + 0 。
因此，10 的惩罚数为 1 + 81 + 100 = 182复盘：
这个题是比较容易的，直接去遍历所有数字去check是否符合惩罚数的定义再进行求和得出ans
在check的时候显然可以使用使用深搜去搜查所有的符合的情况
因为例如36*36=1296 而1296可以分为1+29+6 （符合） 12+9+6（不符合）
因此我们需要深搜得到符合的所有情况
代码：
func punishmentNumber(n int) int {
res:=0
for i:=1;i<=n;i++{
s:=strconv.Itoa(i*i)
if check(s,0,i){
res+=i*i
}
}
return res
}
//s:需要深搜的乘积 i深搜的位置 want预期结果
func check(s string,i int,want int)bool{
// 利用深搜去看每种情况是否符合
res:=0
l:=len(s)
if i>=l{
return want==0
}
for j:=i;jwant{
break
}
if check(s,j+1,want-res){
return true
}
}
return false
}周四：2520. 统计能整除数字的位数（easy）
题目描述：
给你一个整数 `num` ，返回 `num` 中能整除 `num` 的数位的数目。
如果满足 `nums % val == 0` ，则认为整数 `val` 可以整除 `nums` 。
示例 3：
输入： num = 1248
输出： 4
解释： 1248 可以被它每一位上的数字整除，因此答案是 4 。复盘
与周一.一致
代码：
func countDigits(num int) int {
cnt:=0
numStr:=strconv.Itoa(num)
for _,v:=range numStr{
if num%int(v-'0')==0{
cnt+=1
}
}
return cnt
}周五：1465. 切割后面积最大的蛋糕(middle)
题目描述：
矩形蛋糕的高度为 `h` 且宽度为 `w`，给你两个整数数组 `horizontalCuts` 和 `verticalCuts`，其中：
- `horizontalCuts[i]` 是从矩形蛋糕顶部到第 `i` 个水平切口的距离
- `verticalCuts[j]` 是从矩形蛋糕的左侧到第 `j` 个竖直切口的距离
请你按数组 `horizontalCuts` 和 `verticalCuts` 中提供的水平和竖直位置切割后，请你找出 面积最大 的那份蛋糕，并返回其 面积 。由于答案可能是一个很大的数字，因此需要将结果 对 `109 + 7` 取余 后返回。
示例 1：
输入： h = 5, w = 4, horizontalCuts = [1,2,4], verticalCuts = [1,3]
输出： 4
解释： 上图所示的矩阵蛋糕中，红色线表示水平和竖直方向上的切口。切割蛋糕后，绿色的那份蛋糕面积最大。复盘：
把长宽的切口距离最大值枚举出来相乘就是最大值，难度中等属实名不副实
代码：
func maxArea(h int, w int, horizontalCuts []int, verticalCuts []int) int {
ans:=0
maxH:=0
maxW:=0
sort.Ints(horizontalCuts)
sort.Ints(verticalCuts)
horizontalCuts=append([]int{0},append(horizontalCuts,h)...)
verticalCuts=append([]int{0},append(verticalCuts,w)...)
for i:=1;imaxW{
maxW=verticalCuts[i]-verticalCuts[i-1]
}
}
for i:=1;imaxH{
maxH=horizontalCuts[i]-horizontalCuts[i-1]
}
}
ans=maxH*maxW
return ans%1000000007
}周六：2558. 从数量最多的堆取走礼物（easy）
题目描述：
给你一个整数数组 `gifts` ，表示各堆礼物的数量。每一秒，你需要执行以下操作：
- 选择礼物数量最多的那一堆。
- 如果不止一堆都符合礼物数量最多，从中选择任一堆即可。
- 选中的那一堆留下平方根数量的礼物（向下取整），取走其他的礼物。
返回在 `k` 秒后剩下的礼物数量 。
示例 1：
输入： gifts = [25,64,9,4,100], k = 4
输出： 29
解释：
按下述方式取走礼物：
- 在第一秒，选中最后一堆，剩下 10 个礼物。
- 接着第二秒选中第二堆礼物，剩下 8 个礼物。
- 然后选中第一堆礼物，剩下 5 个礼物。
- 最后，再次选中最后一堆礼物，剩下 3 个礼物。
最后剩下的礼物数量分别是 [5,8,9,4,3] ，所以，剩下礼物的总数量是 29 。复盘：
每次去处最大值处理后放回，显然使用大根堆的数据结构去存储礼物每次pop出最大值即可
代码：
func pickGifts(gifts []int, k int) int64 {
hp:=&hp{}
heap.Init(hp)
for _,gift:=range gifts{
heap.Push(hp,gift)
}
for k>0{
a:=heap.Pop(hp).(int)
a=sqrt(a)
heap.Push(hp,a)
k-=1
}
ans:=0
for hp.Len()>0{
ans+=hp.Pop().(int)
}
return int64(ans)
}
type hp []int
func(h hp)Len()int{
return len(h)
}
func(h hp)Less(i,j int)bool{
return h[i]>h[j]
}
func (h *hp)Pop()interface{}{
l:=h.Len()
res:=(*h)[l-1]
*h=(*h)[:l-1]
return res
}
func (h *hp)Push(n interface{}){
*h=append(*h,n.(int))
}
func (h hp)Swap(i,j int){
h[i],h[j]=h[j],h[i]
}
func sqrt(n int)int{
ans:=0
for{
if ans*ans>n{
return ans-1
}
if ans*ans==n{
return ans
}
ans+=1
}
return ans
}周日：274. H 指数（middle）
题目描述：
给你一个整数数组 `citations` ，其中 `citations[i]` 表示研究者的第 `i` 篇论文被引用的次数。计算并返回该研究者的 `h` 指数**。
根据维基百科上 h 指数的定义：`h` 代表“高引用次数” ，一名科研人员的 `h` 指数 是指他（她）至少发表了 `h` 篇论文，并且每篇论文 至少 被引用 `h` 次。如果 `h` 有多种可能的值，`h` 指数** 是其中最大的那个。
示例 1：
输入： citations = [3,0,6,1,5]
输出： 3
解释： 给定数组表示研究者总共有 5 篇论文，每篇论文相应的被引用了 3, 0, 6, 1, 5 次。
由于研究者有 3 篇论文每篇 至少 被引用了 3 次，其余两篇论文每篇被引用 不多于 3 次，所以她的 h 指数是 3。复盘：
这个题也是比较容易，当时看到题目就感觉可以直接二分法做就行，右边界为论文的最大引用数，左边界为0，去二分h指数就容易得出答案
不过当时感觉时间复杂度O(logn)可能稍微有点慢，若把每个引用数的数量都记录下来直接从大到小遍历h指数，看多少能够符合，只需要O(n)
代码：
func hIndex(citations []int) (h int) {
n := len(citations)
counter := make([]int, n+1)
for _, citation := range citations {
if citation >= n {
counter[n]++
} else {
counter[citation]++
}
}
for i, tot := n, 0; i >= 0; i-- {
tot += counter[i]
if tot >= i {
return i
}
}
return 0
}总结
本周的题目都比较简单，easy题居多，唯一需要多花心思的是周二的骰子题目
推荐精刷（1155. 掷骰子等于目标和的方法数）
