Leetcode 第 98 场双周赛

第一题：替换一个数字后的最大差值

题目

给你一个整数 num 。你知道 Danny Mittal 会偷偷将 0 到 9 中的一个数字 替换 成另一个数字。

请你返回将 num 中 恰好一个 数字进行替换后，得到的最大值和最小值的差位多少。

注意

当 Danny 将一个数字 d1 替换成另一个数字 d2 时，Danny 需要将 nums 中所有 d1 都替换成 d2 。
Danny 可以将一个数字替换成它自己，也就是说 num 可以不变。
Danny 可以将数字分别替换成两个不同的数字分别得到最大值和最小值。
替换后得到的数字可以包含前导 0 。
Danny Mittal 获得周赛 326 前 10 名，让我们恭喜他。  

示例 1

输入：num = 11891
输出：99009
解释：
为了得到最大值，我们将数字 1 替换成数字 9 ，得到 99899 。
为了得到最小值，我们将数字 1 替换成数字 0 ，得到 890 。
两个数字的差值为 99009 。

示例 2

输入：num = 90
输出：99
解释：
可以得到的最大值是 99（将 0 替换成 9），最小值是 0（将 9 替换成 0）。
所以我们得到 99 。  

提示

• 1 <= num <= 108

分析

• 得到最大值，就是从左往右找到第一个非0的数字，将它变成9，并且其他所有相同的数字都变成9
• 得到最小值，就是从左往右找到第一个非0的数字，将它变成0，并且其他所有相同的数字都变成0

答案

func MinMaxDifference(num int) int {
	// 1.得到最大值
	max := getMax(num)
	// 2.得到最小值
	min := getMin(num)
	// 3.返回结果
	return max - min
}

func getMax(num int) int {
	nums := getAllNumber(num)
	target := 0
	find := false
	for i := len(nums) - 1; i >= 0; i-- {
		if !find {
			if nums[i] == 9 {
				continue
			} else {
				find = true
				// 将后面所有的target都变成9
				target = nums[i]
				nums[i] = 9
			}
		} else if nums[i] == target {
			nums[i] = 9
		}
	}

	return getNumber(nums)
}

func getMin(num int) int {
	nums := getAllNumber(num)
	target := 0
	find := false
	for i := len(nums) - 1; i >= 0; i-- {
		if !find {
			if nums[i] == 0 {
				continue
			} else {
				find = true
				// 将后面所有的target都变成9
				target = nums[i]
				nums[i] = 0
			}
		} else if nums[i] == target {
			nums[i] = 0
		}
	}

	return getNumber(nums)
}

func getAllNumber(num int) []int {
	nums := []int{}
	for num > 0 {
		x := num % 10
		nums = append(nums, x)

		num = num / 10
	}
	return nums
}

func getNumber(nums []int) int {
	num := 0
	x := 1
	findFirst := false
	for i := len(nums) - 1; i >= 0; i-- {
		if !findFirst && nums[i] == 0 {
			continue
		}

		findFirst = true
		num *= 10
		num += nums[i]
		// num += nums[i] * x
		x *= 10
	}
	return num
}

第二题： 修改两个元素的最小分数

题目

给你一个下标从 0 开始的整数数组 nums 。

nums 的 最小 得分是满足 0 <= i < j < nums.length 的 |nums[i] - nums[j]| 的最小值。
nums的 最大 得分是满足 0 <= i < j < nums.length 的 |nums[i] - nums[j]| 的最大值。
nums 的分数是 最大 得分与 最小 得分的和。
我们的目标是最小化 nums 的分数。你 最多 可以修改 nums 中 2 个元素的值。

请你返回修改 nums 中 至多两个 元素的值后，可以得到的 最小分数 。

|x| 表示 x 的绝对值。

 

示例 1

输入：nums = [1,4,3]
输出：0
解释：将 nums[1] 和 nums[2] 的值改为 1 ，nums 变为 [1,1,1] 。|nums[i] - nums[j]| 的值永远为 0 ，所以我们返回 0 + 0 = 0 。

示例 2

输入：nums = [1,4,7,8,5]
输出：3
解释：
将 nums[0] 和 nums[1] 的值变为 6 ，nums 变为 [6,6,7,8,5] 。
最小得分是 i = 0 且 j = 1 时得到的 |nums[i] - nums[j]| = |6 - 6| = 0 。
最大得分是 i = 3 且 j = 4 时得到的 |nums[i] - nums[j]| = |8 - 5| = 3 。
最大得分与最小得分之和为 3 。这是最优答案。  

提示

• 3 <= nums.length <= 105
• 1 <= nums[i] <= 109

分析

• 最小得分：很明显可以将某个数字改成已有的数字，这样最小得分就是0
• 最大得分：也就是修改之后，数字内最大值减去最小值

总结，这个问题可以简化成，最多修改数组内任意2个数，使得数组内最大值、最小值相差最小，并给出这个最小差。

我们将最大值改小一点，或者将最小值改大一点，既然可以改2个数字，那就有3种情况：

• 要修改的2个数字都在最小值这边，即将最小的2个数字改成第3小的那个数字。这种情况，求出最大值和第3小的数字即可。
• 要修改的2个数字都在最大值这边，即将最大的2个数字改成第3大的那个数字。这种情况，求出最小值和第3大的数字即可。
• 要修改的2个数字都在最大值这边，即将最大的数字改成第2大的那个数字，将最小的数字改成第2小的那个数字。这种情况，求出第2大和第2小的数字即可。
• 最终的结果是上述三种情况中值最小的那种。

答案

const (
	Max = 10 << 40
)

func MinimizeSum(nums []int) int {
	max1, max2, max3, min1, min2, min3 := 0, 0, 0, Max, Max, Max
	for i := range nums {
		if nums[i] > max1 {
			max3 = max2
			max2 = max1
			max1 = nums[i]
		} else if nums[i] > max2 {
			max3 = max2
			max2 = nums[i]
		} else if nums[i] > max3 {
			max3 = nums[i]
		}

		if nums[i] < min1 {
			min3 = min2
			min2 = min1
			min1 = nums[i]
		} else if nums[i] < min2 {
			min3 = min2
			min2 = nums[i]
		} else if nums[i] < min3 {
			min3 = nums[i]
		}
	}

	x1 := max2 - min2
	x2 := max3 - min1
	x3 := max1 - min3

	result := x1
	if result > x2 {
		result = x2
	}
	if result > x3 {
		result = x3
	}
	return result
}

第三题： 最小无法得到的或值

题目

给你一个下标从 0 开始的整数数组 nums 。

如果存在一些整数满足 0 <= index1 < index2 < … < indexk < nums.length ，得到 nums[index1] | nums[index2] | … | nums[indexk] = x ，那么我们说 x 是 可表达的 。换言之，如果一个整数能由 nums 的某个子序列的或运算得到，那么它就是可表达的。

请你返回 nums 不可表达的 最小非零整数 。

 

示例 1

输入：nums = [2,1]
输出：4
解释：1 和 2 已经在数组中，因为 nums[0] | nums[1] = 2 | 1 = 3 ，所以 3 是可表达的。由于 4 是不可表达的，所以我们返回 4 。

示例 2

输入：nums = [5,3,2]
输出：1
解释：1 是最小不可表达的数字。  

提示

• 1 <= nums.length <= 105
• 1 <= nums[i] <= 109

分析

如果 1不是答案，说明 1在 nums 中。

继续枚举，如果2 不是答案，说明2 在 nums 中，因为 2 只有一个比特是 1。

那么 3肯定不是答案，因为 1∣2=3，同时根据已知信息，1 和 2 都在 nums 中。

继续枚举，如果 4 不是答案，说明 4 在 nums 中，因为
4 只有一个比特是1。

那么 5,6,7肯定不是答案，因为 1,2,4 都在 nums 中，它们可以通过或运算组成 1到7 中的任意数字。

因此，我们只需要从小到大挨个判断 2的x次方 是否在 nums 中，第一个不在 nums 中的就是答案。

答案1

var (
	EmptyValue = struct{}{}
)

func MinImpossibleOR(nums []int) int {
	numMap := make(map[int]struct{})
	for i := range nums {
		numMap[nums[i]] = EmptyValue
	}

	nums = sort(nums)
	max := nums[len(nums)-1] * 3
	i := 1
	j := 0
	for ; i < max; i *= 2 {
		find := false
		for ; j < len(nums); j++ {
			if nums[j] == i {
				find = true
				break
			}
		}

		if !find {
			return i
		}
	}
	return i / 2
}

// 数组升序排序
func sort(nums []int) []int {
	for i := range nums {
		minIdx := i
		for j := i + 1; j < len(nums); j++ {
			if nums[j] < nums[minIdx] {
				minIdx = j
			}
		}
		nums[minIdx], nums[i] = nums[i], nums[minIdx]
	}
	return nums
}

结果超时，通过分析发现在排序的时候超时了，说明这个方法不行。

换一种思路，不需要排序：遍历nums每个元素，找出所有是2的幂次方的数字，如果不是则忽略。
然后从1,2,4,8开始遍历，如果有一个2的幂次方数字不在上述结果中则这个数字就是所求的值。

var (
	EmptyValue = struct{}{}
)

func minImpossibleOR(nums []int) int {
	numMap := make(map[int]struct{})
	for i := range nums {
		x := calcTwo(nums[i])
		if x != -1 {
			numMap[x] = EmptyValue
		}
	}

	t := 0
	for {
		_, ok := numMap[t]
		if !ok {
			return calcN(t)
		}
		t += 1
	}
}

// 求2的n次幂
func calcN(n int) int {
	r := 1
	for i := 0; i < n; i++ {
		r *= 2
	}
	return r
}

// 求n的幂指数，如果不是2的幂次方则返回-1
func calcTwo(n int) int {
	count := 0
	for n > 0 {
		if n == 1 {
			return count
		}
		if n%2 != 0 {
			return -1
		}
		n /= 2
		count += 1
	}
	return -1
}

第四题：更新数组后处理求和查询

题目

给你两个下标从 0 开始的数组 nums1 和 nums2 ，和一个二维数组 queries 表示一些操作。总共有 3 种类型的操作：

操作类型 1 为 queries[i] = [1, l, r] 。你需要将 nums1 从下标 l 到下标 r 的所有 0 反转成 1 或将 1 反转成 0 。l 和 r 下标都从 0 开始。
操作类型 2 为 queries[i] = [2, p, 0] 。对于 0 <= i < n 中的所有下标，令 nums2[i] = nums2[i] + nums1[i] * p 。
操作类型 3 为 queries[i] = [3, 0, 0] 。求 nums2 中所有元素的和。
请你返回一个数组，包含所有第三种操作类型的答案。

 

示例 1

输入：nums1 = [1,0,1], nums2 = [0,0,0], queries = [[1,1,1],[2,1,0],[3,0,0]]
输出：[3]
解释：第一个操作后 nums1 变为 [1,1,1] 。第二个操作后，nums2 变成 [1,1,1] ，所以第三个操作的答案为 3 。所以返回 [3] 。

示例 2

输入：nums1 = [1], nums2 = [5], queries = [[2,0,0],[3,0,0]]
输出：[5]
解释：第一个操作后，nums2 保持不变为 [5] ，所以第二个操作的答案是 5 。所以返回 [5] 。  

提示

• 1 <= nums1.length,nums2.length <= 105
• nums1.length = nums2.length
• 1 <= queries.length <= 105
• queries[i].length = 3
• 0 <= l <= r <= nums1.length - 1
• 0 <= p <= 106
• 0 <= nums1[i] <= 1
• 0 <= nums2[i] <= 109

感兴趣的同学可以做一下，此次比赛在规定的时间内我只做出来了第一、第二题，第三题执行时间超时，第四题没有时间看。上述代码都是在比赛的时候写的，肯定有很多不规范的、可以优化的地方，不规范的地方不要学习。可以在评论区探讨。

总结

这次题目对于第二题，刚开始没有思路，感觉很难。后面冷静分析一下，得出3种情况，就比较简单了。总之做题千万不要一开始就写，需要先分析清楚。

leetcode上每双周的星期六晚上22:30:00-23:59:59有双周赛，每周星期日上午:10:30:00-12:00:00有单周赛，咱也不在乎名次，有时间就做一下，坚持了大半年。希望大家一起加油。