leetcode每日一题-周复盘
前言
该系列文章用于我对一周中leetcode每日一题or其他不会的题的复盘总结。
一方面用于自己加深印象，另一方面也希望能对读者的算法能力有所帮助， 同时也希望能帮助同样坚持刷题的同学加深印象~
该复盘对我来说比较容易的题我会复盘的比较粗糙，反之较为细致
解答语言：Golang
周一：53. 最大子数组和（middle）
题目描述：
给你一个整数数组 nums ，请你找出一个具有最大和的连续子数组（子数组最少包含一个元素），返回其最大和。
子数组 是数组中的一个连续部分。
示例 1：
输入： nums = [-2,1,-3,4,-1,2,1,-5,4]
输出： 6
解释： 连续子数组 [4,-1,2,1] 的和最大，为 6 。
复盘：
很老的题目，直接贪心，维护最大值，最大值变为负数就置为0重新维护
代码：
func maxSubArray(nums []int) int {
ans:=nums[0]
tmpAns:=0
for _,num:=range nums{
tmpAns+=num
ans=max(tmpAns,ans)
if tmpAns<0{
tmpAns=0
}
}
return ans
}
周二：2216. 美化数组的最少删除数（middle）
题目描述：
给你一个下标从 0 开始的整数数组 nums ，如果满足下述条件，则认为数组 nums 是一个 美丽数组 ：
nums.length为偶数- 对所有满足
i % 2 == 0的下标i，nums[i] != nums[i + 1]均成立
注意，空数组同样认为是美丽数组。
你可以从 nums 中删除任意数量的元素。当你删除一个元素时，被删除元素右侧的所有元素将会向左移动一个单位以填补空缺，而左侧的元素将会保持 不变 。
返回使 nums 变为美丽数组所需删除的 最少 元素数目 。
示例 1：
输入： nums = [1,1,2,3,5]
输出： 1
解释： 可以删除 nums[0] 或 nums[1] ，这样得到的 nums = [1,2,3,5] 是一个美丽数组。可以证明，要想使 nums 变为美丽数组，至少需要删除 1 个元素。
复盘：
此题关键点在于当删除了一个不合法的元素时后面的元素下标会动态变化，因此在这里我们特殊处理即可， i为偶数、且满足删除条件的情况下，那么i+1的下标则置为i，依然为偶数，继续判定，否则直接让i+1，继续判定下一个偶数是否满足（跳过奇数）
代码：
func minDeletion(nums []int) int {
ans:=0
if len(nums)==0{
return 0
}
L:=len(nums)
for i:=0;i<L-1;i++{
if nums[i]==nums[i+1]{ // i为偶数、且满足删除条件，那么i+1的下标则置为i，依然为偶数，继续判定
ans+=1
}else{ // 不满足直接跳过下一个，因为下一个i为奇
i+=1
}
}
if (L-ans)&1==1{
ans+=1
}
return ans
}
周三：2304. 网格中的最小路径代价（middle）
题目描述：
给你一个下标从 0 开始的整数矩阵 grid ，矩阵大小为 m x n ，由从 0 到 m * n - 1 的不同整数组成。你可以在此矩阵中，从一个单元格移动到 下一行 的任何其他单元格。如果你位于单元格 (x, y) ，且满足 x < m - 1 ，你可以移动到 (x + 1, 0), (x + 1, 1), ..., (x + 1, n - 1) ****中的任何一个单元格。注意： 在最后一行中的单元格不能触发移动。
每次可能的移动都需要付出对应的代价，代价用一个下标从 0 开始的二维数组 moveCost 表示，该数组大小为 (m * n) x n ，其中 moveCost[i][j] 是从值为 i 的单元格移动到下一行第 j 列单元格的代价。从 grid 最后一行的单元格移动的代价可以忽略。
grid 一条路径的代价是：所有路径经过的单元格的 值之和 加上 所有移动的 代价之和 。从 第一行 任意单元格出发，返回到达 最后一行 任意单元格的最小路径代价 。
示例 1：
输入： grid = [[5,3],[4,0],[2,1]], moveCost = [[9,8],[1,5],[10,12],[18,6],[2,4],[14,3]]
输出： 17
解释： 最小代价的路径是 5 -> 0 -> 1 。
- 路径途经单元格值之和 5 + 0 + 1 = 6 。
- 从 5 移动到 0 的代价为 3 。
- 从 0 移动到 1 的代价为 8 。
路径总代价为 6 + 3 + 8 = 17 。
复盘：
很明显的一个动态规划题目，维护每一层最小代价即可
代码：
func minPathCost(grid [][]int, moveCost [][]int) int {
dp:=make([][]int,len(grid)) // dp[i][j] :到第i行第j列最小代价
for i:=range grid{
dp[i]=make([]int,len(grid[0]))
}
for i:=range grid{
for j:=range grid[0]{
dp[i][j]=1<<32-1
}
}
for i:=range grid[0]{
dp[0][i]=grid[0][i]
}
for i:=1;i<len(grid);i++{
for j:=0;j<len(grid[0]);j++{
tmpSum:=1<<32-1
for k:=0;k<len(grid[0]);k++{
val:=grid[i-1][k]
zhi:=moveCost[val][j]
tmpSum=min(tmpSum,zhi+dp[i-1][k])
}
dp[i][j]=min(dp[i][j],tmpSum+grid[i][j])
}
}
L:=len(grid)-1
ans:=dp[L][0]
for i:=0;i<len(grid[0]);i++{
ans=min(ans,dp[L][i])
}
return ans
}
周四：1410. HTML 实体解析器（middle）
题目描述：
「HTML 实体解析器」 是一种特殊的解析器，它将 HTML 代码作为输入，并用字符本身替换掉所有这些特殊的字符实体。
HTML 里这些特殊字符和它们对应的字符实体包括：
- 双引号： 字符实体为
"，对应的字符是"。 - 单引号： 字符实体为
'，对应的字符是'。 - 与符号： 字符实体为
&，对应对的字符是&。 - 大于号： 字符实体为
>，对应的字符是>。 - 小于号： 字符实体为
<，对应的字符是<。 - 斜线号： 字符实体为
⁄，对应的字符是/。
给你输入字符串 text ，请你实现一个 HTML 实体解析器，返回解析器解析后的结果。
示例 1：
输入： text = "& is an HTML entity but &ambassador; is not."
输出： "& is an HTML entity but &ambassador; is not."
解释： 解析器把字符实体 & 用 & 替换
复盘：
简单模拟题
代码：
func entityParser(text string) string {
d := map[string]string{
""": "\"",
"'": "'",
"&": "&",
">": ">",
"<": "<",
"⁄": "/",
}
var ans strings.Builder
i, n := 0, len(text)
for i < n {
found := false
for l := 1; l < 8; l++ {
j := i + l
if j <= n {
t := text[i:j]
if val, ok := d[t]; ok {
ans.WriteString(val)
i = j
found = true
break
}
}
}
if !found {
ans.WriteByte(text[i])
i++
}
}
return ans.String()
}
周五：2824. 统计和小于目标的下标对数目(easy)
题目描述:
给你一个下标从 0 开始长度为 n 的整数数组 nums 和一个整数 target ，请你返回满足 0 <= i < j < n 且 nums[i] + nums[j] < target 的下标对 (i, j) 的数目。
示例 1：
输入： nums = [-1,1,2,3,1], target = 2
输出： 3
解释： 总共有 3 个下标对满足题目描述：
- (0, 1) ，0 < 1 且 nums[0] + nums[1] = 0 < target
- (0, 2) ，0 < 2 且 nums[0] + nums[2] = 1 < target
- (0, 4) ，0 < 4 且 nums[0] + nums[4] = 0 < target
注意 (0, 3) 不计入答案因为 nums[0] + nums[3] 不是严格小于 target
复盘：
这个题虽然是easy题，但是其实是很巧妙的，感觉比前面几个middle会难一些。因为此题描述答案是满足条件的下标对的数目，我下意识的认为就不能够先排序然后再查找，然后就没想到什么特别好的办法，但是其实这个题是可以先进行排序的，因为即便是排序了，虽然下标对会不同，但是总数是不影响的
代码：
func countPairs(nums []int, target int) (ans int) {
sort.Ints(nums)
for j, x := range nums {
i := sort.SearchInts(nums[:j], target-x)
ans += i
}
return
}
周六：1457. 二叉树中的伪回文路径（middle）
题目描述：
给你一棵二叉树，每个节点的值为 1 到 9 。我们称二叉树中的一条路径是 「伪回文」的，当它满足：路径经过的所有节点值的排列中，存在一个回文序列。
请你返回从根到叶子节点的所有路径中 伪回文 路径的数目。
示例 1：
输入： root = [2,3,1,3,1,null,1]
输出： 2
解释： 上图为给定的二叉树。总共有 3 条从根到叶子的路径：红色路径 [2,3,3] ，绿色路径 [2,1,1] 和路径 [2,3,1] 。
在这些路径中，只有红色和绿色的路径是伪回文路径，因为红色路径 [2,3,3] 存在回文排列 [3,2,3] ，绿色路径 [2,1,1] 存在回文排列 [1,2,1] 。
复盘：
此题一个难点就是如何快速的去判断一个数组是否满足伪回文路径，一开始我想的是通过数组or字典去维护状态，但是这样空间复杂度和时间复杂度都太高了。 一个比较巧妙地办法就是通过位运算进行判断，有个结论：当一个数字m是2的n次方时，此时它的二进制仅一个位为1，因此m-1的二进制除了为一的那一位为0，低位全为1，因此m&m-1==0.
代码：
func pseudoPalindromicPaths(root *TreeNode) int {
// 使用dfs进行枚举所有路径，通过位运算，如果二进制只有一位为1那么显然是符合回文排列。
var dfs func(*TreeNode,int)int
dfs=func(root *TreeNode,n int)int{
if root==nil{
return 0
}
n^=1<<root.Val
if root.Left==nil&&root.Right==nil{
if n&(n-1)==0{
return 1
}
return 0
}
return dfs(root.Left,n)+dfs(root.Right,n)
}
return dfs(root,0)
}
周日：828. 统计子串中的唯一字符（hard）
题目描述：
我们定义了一个函数 countUniqueChars(s) 来统计字符串 s 中的唯一字符，并返回唯一字符的个数。
例如：s = "LEETCODE" ，则其中 "L", "T","C","O","D" 都是唯一字符，因为它们只出现一次，所以 countUniqueChars(s) = 5 。
本题将会给你一个字符串 s ，我们需要返回 countUniqueChars(t) 的总和，其中 t 是 s 的子字符串。输入用例保证返回值为 32 位整数。
注意，某些子字符串可能是重复的，但你统计时也必须算上这些重复的子字符串（也就是说，你必须统计 s 的所有子字符串中的唯一字符）。
示例 1：
输入: s = "ABC"
输出: 10
解释: 所有可能的子串为："A","B","C","AB","BC" 和 "ABC"。
其中，每一个子串都由独特字符构成。
所以其长度总和为：1 + 1 + 1 + 2 + 2 + 3 = 10
复盘：
刚开始读这个题就理解错了意思，主要是样例给的毫无代表性，只能说leetcode特色呵呵呵。。。。。。
后面提交不通过再读了一遍才发现是找出没有重复字符的子串的长度和。。
其实这种题如果做多了就知道是通过计算每个字符的价值去得出答案。。。。
比如ABC这个样例。B这个字符在多个满足条件的子串都会出现，那我们只有得出这个字符出现的次数就能得出它贡献的价值。。那观察发现一个字符的贡献在左边和右边都会有，B左边字符有A,'',右边有C,'';那么组合数可以为
AC、''C、A''、''。因此此B的贡献度就为4.
这里借用图片：
同样组合数为A、'' 与C、D、''，也就是2*3；那么贡献值的计算公式显然可以推出为：(元素下标位置 - (-1)) * (数组长度 - 元素下标位置)
代码：
func uniqueLetterString(s string) (ans int) {
d := make([][]int, 26)
for i := range d {
d[i] = []int{-1}
}
for i, c := range s {
d[c-'A'] = append(d[c-'A'], i)
}
fmt.Println(d)
for _, v := range d {
v = append(v, len(s))
for i := 1; i < len(v)-1; i++ {
ans += (v[i] - v[i-1]) * (v[i+1] - v[i])
}
}
return
}
总结：
本周题目大多为偏简单的middle题，hard也是偏简单的hard，，不过通过这七个题收获了些许技巧。。