This is the multi-page printable view of this section. Click here to print.

Return to the regular view of this page.

1500-1999

Solutions to LeetCode Problems 1500-1999.

1 - 1758.生成交替二进制字符串的最少操作数

方法一：简单模拟

时间复杂度 $O(n)$，空间复杂度 $O(1)$。

func minOperations(s string) int {
	cnt := 0
	for i, c := range s {
		cnt += int(c-'0') ^ (i & 1)
	}
	if cnt < len(s)-cnt {
		return cnt
	}
	return len(s) - cnt
}

2 - 1774.最接近目标价格的甜点成本

方法一：回溯

暴力回溯，设 baseCosts 长度为 n，toppingCosts 长度为 m，则时间复杂度 $O(n \times 3^m)$，空间复杂度 $O(m)$。

func min(a, b int) int {
	if a < b {
		return a
	}
	return b
}

func abs(a int) int {
	if a < 0 {
		return -a
	}
	return a
}

func closestCost(baseCosts []int, toppingCosts []int, target int) int {
	ans, m := 10001, len(toppingCosts)
	// 此处使 ans 为 baseCosts 的最小值的原因是：
	// 若 ans ≥ target，则无论我们是否添加配料都不会使甜品制作的开销与目标价格 target 的距离缩小，所以此时直接返回此最小的基料开销即可
	for _, v := range baseCosts {
		ans = min(v, ans)
	}
	var backtrack func(start, sum int)
	backtrack = func(start, sum int) {
		if abs(ans-target) >= abs(sum-target) {
			if abs(ans-target) > abs(sum-target) {
				ans = sum
			} else {
				ans = min(ans, sum)
			}
		} else if abs(ans-target) < sum-target {
			return
		}
		if start >= m {
			return
		}

		backtrack(start+1, sum)
		backtrack(start+1, sum+toppingCosts[start])
		backtrack(start+1, sum+toppingCosts[start]*2)
	}
	for _, v := range baseCosts {
		backtrack(0, v)
	}
	return ans
}

3 - 1779.找到最近的有相同 X 或 Y 坐标的点

方法一：遍历

时间复杂度 $O(n)$，空间复杂度 $O(1)$，n 表示数组 points 的长度。

func nearestValidPoint(x int, y int, points [][]int) int {
	ans, minLen := -1, 1<<31-1
	for i := 0; i < len(points); i++ {
		a, b := points[i][0], points[i][1]
		if (a == x || b == y) && abs(x, y, a, b) < minLen {
			ans, minLen = i, abs(x, y, a, b)
		}
	}
	return ans
}

func abs(x, y, a, b int) int {
	ans1, ans2 := x-a, y-b
	if ans1 < 0 {
		ans1 = -ans1
	}
	if ans2 < 0 {
		ans2 = -ans2
	}
	return ans1 + ans2
}

4 - 1796.字符串中第二大的数字

方法一：遍历

时间复杂度 $O(n)$，空间复杂度 $O(1)$。

func secondHighest(s string) int {
	nums := [10]bool{}
	for i := range s {
		if s[i] >= '0' && s[i] <= '9' {
			nums[s[i]-'0'] = true
		}
	}
	c := 0
	for i := 9; i >= 0; i-- {
		if nums[i] {
			c++
		}
		if c == 2 {
			return i
		}
	}
	return -1
}