前言
难度只能算都是中等题
第一题
2215.找出两数组的不同
2215.找出两数组的不同
题解
easy题,太简单,不解释了
代码
func findDifference(nums1, nums2 []int) [][]int { mp1, mp2 := map[int]bool{}, map[int]bool{} for _, v := range nums1 { mp1[v] = true } for _, v := range nums2 { mp2[v] = true } var a, b []int for v := range mp1 { if !mp2[v] { a = append(a, v) } } for v := range mp2 { if !mp1[v] { b = append(b, v) } } return [][]int{a, b} }
第二题
2216.美化数组的最少删除数
2216.美化数组的最少删除数
题解
贪心:通过题目给的数组,我们来构造美化数组stack
- 如果当前位置是偶数,那么直接添加进stack
- 如果当前位置是奇数,并且当前数组的值与数组stack的最新值不相等,则直接添加进stack,否则跳过
遍历完数组后,如果数组stack的奇数个,则直接删去最后一个即可
代码
func minDeletion(nums []int) int { stack := make([]int, 0) cnt := 0 for i := 0; i < len(nums); i++ { if cnt%2 != 0 { if nums[i] != stack[cnt-1] { cnt++ stack = append(stack, nums[i]) } } else { cnt++ stack = append(stack, nums[i]) } } if len(stack)%2 != 0 {//如果是奇数个,去掉最后一个 cnt-- stack = stack[:len(stack)-1] } ans := len(nums) - cnt return ans }
第三题
2217.找到指定长度的回文数
2217.找到指定长度的回文数
题解
思路:
- 首先构造回文数的左半边,那么最终的回文数通过左半边翻转就能得到了
- 题目给定了要找第几个回文数,那么就是half := base + q - 1
- 例如三位数,第16个,10+16-1=25,翻转,252就是第16个回文数,这里-1是因为101是第一个回文数,而如果q是1的话,10+1=11,111是第二个回文数,所有要减1
- 例如四位数,第8个,10+8-1=17,翻转,1771就是第8个回文数
- 如果是奇数的话,翻转时把左半边的最后一位去掉即可
- 对于一位数的回文数来说,最多1 * 9个,对于二位数,最多1 * 9个,对于三位数,最多10 * 9个,对于四位数,最多10 * 9个。可以发现最多的数量是左半边的base * 9,所以如果q大于base * 9的话,一定找不到
代码
func kthPalindrome(queries []int, intLength int) []int64 { ans := make([]int64, len(queries)) n := (intLength - 1) / 2 base := int(math.Pow10(n)) for i, q := range queries { if q > base*9 { ans[i] = -1 continue } half := base + q - 1 cnt := half if intLength%2 != 0 { cnt /= 10 } for cnt != 0 { half = half*10 + cnt%10 cnt /= 10 } ans[i] = int64(half) } return ans }
第四题
2218.从栈中取出K个硬币的最大面值和
2218.从栈中取出K个硬币的最大面值和
题解
分组背包,用dp来做,又因为取硬币是栈操作,用前缀和来化简取硬币的操作
- 因为每组只能取一次物品(题目中栈的关系),所以可以先看作是01背包
- 那么取一次物品,取多少呢?用前缀和来选择,pile[ i ],即取前 i+1 个,因为下标从0开始,所以是i+1
- 用滚动数组来优化,二维降一维
- 到了该取这一组物品的一次物品的时候了,到底取几个呢?
- 遍历一遍前缀和数组即可,会自动滚动到每个容量的最优价值
代码
func maxValueOfCoins(piles [][]int, k int) int { dp := make([]int, k+1) for _, pile := range piles { //计算前缀和 //这里的外层循环每一层可以看作是一件物品 //下面的for range是将这一件物品变成一组物品 //每一组,最多只能取一次前缀和物品 n := len(pile) for i := 1; i < n; i++ { pile[i] += pile[i-1] } //滚动数组 for j := k; j > 0; j-- { //这里的w+1可以看作01背包中的重量,v是价值。w是从零开始的,所以真正的是w+1 //pile[:min(n, j)]的原因是,如果index(重量)> j(容量),那就没有意义了 for w, v := range pile[:min(n, j)] { dp[j] = max(dp[j], dp[j-w-1]+v) } } } return dp[k] } func max(i, j int) int { if i > j { return i } return j } func min(i, j int) int { if i < j { return i } return j }