每日一题（2）

2024-05-21

题目: 2769. 找出最大的可达成数字

题解与思路:

双向奔赴，每次操作时 $num+1$, $x-1$，即 $x=num+2 \times t$

func theMaximumAchievableX(num int, t int) int {  
    return num + 2*t  
}

2024-05-22

题目: 2225. 找出输掉零场或一场比赛的玩家

题解与思路:

用一个 $map$ 存储每个人输的次数，赢的玩家记为输 $0$ 次，最终将输 $0$ 次和输 $1$ 次的玩家放入数组并排序

func findWinners(matches [][]int) [][]int {
	m := make(map[int]int)
	for _, match := range matches {
		if m[match[0]] == 0 {
			m[match[0]] = 0
		}
		
		m[match[1]]++
	}
	
	res := make([][]int, 2)
	for user, count := range m {
		if count < 2 {
			res[count] = append(res[count], user)
		}
	}
	
	sort.Ints(res[0])
	sort.Ints(res[1])
	return res
}

2024-05-23

题目: 2831. 找出最长等值子数组

题解与思路:

将相同元素的下标记录到哈希表 $pos$ 中，例如示例一，元素 $3$ 对应为：$pos[3] = [1,3,5]$.

遍历 $pos$ 中每个下标的列表 $p$，使用滑动窗口，分别设左右端点为 $left$ 和 $right$。

假设等值子数组的元素下标从 $p[left]$ 到 $p[right]$ ，那么此子数组长度为 $p[right]-p[left]+1$，这个子数组中有 $right-left+1$ 个数是相同的，无需删除，需要删除的元素个数为:

$$p[right] - p[left] -(right-left)$$

如果需要删除的元素个数大于 $k$，说明需要删除的数太多了，此时移动指针 $left$，直到需要删除的元素个数小于 $k$，次数更新最大值 $right-left+1$

func longestEqualSubarray(nums []int, k int) int {  
    pos := make(map[int][]int)  
      
    for i, num := range nums {  
        pos[num] = append(pos[num], i)  
    }  
      
    res := 0  
    for _, p := range pos {  
        left := 0  
        for right := range p {  
            for p[right]-p[left]-right+left > k {  
                left++  
            }  
            res = max(res, right-left+1)  
        }  
    }  
    return res  
}

$p[right] - p[left] -(right-left)$ 可以变换一下改为 $p[right] - right -(p[left]-left)$，我们将 $p$ 中存储下标改为 $p[i]-i$，这样上述式子就可以改为：

$$p[right]-p[left]$$

func longestEqualSubarray(nums []int, k int) int {  
    pos := make(map[int][]int)  
      
    for i, num := range nums {  
        pos[num] = append(pos[num], i-len(pos[num]))  
    }  
      
    res := 0  
    for _, p := range pos {  
        left := 0  
        for right := range p {  
            for p[right]-p[left] > k {  
                left++  
            }  
            res = max(res, right-left+1)  
        }  
    }  
    return res  
}

2024-05-24

题目： 1673. 找出最具竞争力的子序列()

思路与题解

声明一个栈 $stack$，假设 $num = nums[i]$，如果栈不为空，且 $num$ 小于栈顶，且栈的大小加上剩余元素个数大于 $k$ ，则可以弹出栈顶。

如果栈大小小于 $k$，可以入栈。

func mostCompetitive(nums []int, k int) []int {  
    stack := make([]int, 0)  
    for i, num := range nums {  
        for len(stack) > 0 && num < stack[len(stack)-1] && len(stack)+len(nums)-i > k {  
            stack = stack[:len(stack)-1]  
        }  
        if len(stack) < k {  // 减少上面循环次数
            stack = append(stack, num)  
        }  
    }  
    return stack  
}

2024-05-25

题目: 2903. 找出满足差值条件的下标 I

题解与思路:

最简单的，双重循环

func findIndices(nums []int, indexDifference int, valueDifference int) []int {
	for i := 0; i < len(nums); i++ {
		for j := i; j < len(nums); j++ {
			if j-i >= indexDifference && abs(nums[i], nums[j])>= valueDifference{
				return []int{i, j}
			}
		}
	}
	return []int{-1,-1}
}
	
func abs(a, b int) int {
	if a > b {
		return a - b
	}
	return b - a
}

通过双指针 $i$ 和 $j$ 维护一个间隔为 $indexDifference$ 的滑动窗口，初始时 $i$ 指向 $0$，$j$ 指向 $indexDifference$。

使用 $mixI$ 和 $maxI$ 维护 $nums[0, j-indexDifference]$ 区间内的最大值和最小值下标，因为 $i$ 和 $j$ 定义就满足了第一个要求，只需要厎条件二进行判断即可，即：

• $nums[maxI] - nums[j] >= valueDifference$
• $nums[j] - nums[minI] >= valueDifference$

这里不需要判断绝对值，假设 $nums[maxI] < nums[j]$ ，且 $|nums[maxI] - nums[j] | = nums[j]-nums[maxI]>=valueDifference$ 时，因为 $nums[minI] <= nums[maxI]$ 可得，$muns[j] - nums[minI] >= nums[j]-nums[maxI] >= valueDifference$，也是满足条件的，不会错过答案。

func findIndices(nums []int, indexDifference int, valueDifference int) []int {  
    minI, maxI := 0, 0  
    for j := indexDifference; j < len(nums); j++ {  
        i := j - indexDifference  
        if nums[i] < nums[minI] {  
            minI = i  
        }  
        if nums[i] > nums[maxI] {  
            maxI = i  
        }  
          
        if nums[j]-nums[minI] >= valueDifference {  
            return []int{minI, j}  
        }  
        if nums[maxI]-nums[j] >= valueDifference {  
            return []int{maxI, j}  
        }  
    }  
    return []int{-1, -1}  
}

2024-05-26

题目: 1738. 找出第 K 大的异或坐标值

题解与思路:

类似二维数组前缀和，用 $sum[i+1][j+1]$ 表示左上角在 $(0,0)$，右下角在 $(i, j)$ 的子矩阵异或和，就有：

$$sum[i+1][j+1] = sum[i+1][j]\oplus sum[i][j+1]\oplus sum[i][j] \oplus matrix[i][j]$$

因为一个数字异或自己会等于 $0$，$sum[i+1][j]\oplus sum[i][j+1]$ 会导致 $sum[i][j]$ 被清理，需要重新异或回来。

func kthLargestValue(matrix [][]int, k int) int {  
    m, n := len(matrix), len(matrix[0])  
    sum := make([][]int, m+1)  
    sum[0] = make([]int, n+1)  
    arr := make([]int, 0)  
    for i, row := range matrix {  
        sum[i+1] = make([]int, n+1)  
        for j, x := range row {  
            sum[i+1][j+1] = sum[i+1][j] ^ sum[i][j+1] ^ sum[i][j] ^ x  
        }  
        arr = append(arr, sum[i+1][1:]...)  
    }  
      
    sort.Ints(arr)  
    return arr[len(arr)-k]  
}

因为是执行顺序是从上到下，从左到右，我们定义 $cloSum[j]$，表示第 $j$ 列遍历过的元素的异或和。

那么左上角 $(0,0)$ 到右下角 $(i,j)$ 的异或和，就是：

$$colSum[0]\oplus colSum[1]\oplus \cdots \oplus colSum[j]$$

func kthLargestValue(matrix [][]int, k int) int {  
    m, n := len(matrix), len(matrix[0])  
    arr := make([]int, 0, m*n)  
    colSum := make([]int, n)  
    for _, row := range matrix {  
        sum := 0  
        for j, x := range row {  
            colSum[j] ^= x  
            sum ^= colSum[j]  
            arr = append(arr, sum)  
        }  
    }  
      
    sort.Ints(arr)  
    return arr[len(arr)-k]  
}