golang力扣leetcode 第 286 场周赛

前言

难度只能算都是中等题

第一题

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
}