算法通关之路：数学之美

2024-04-26 2025-04-08 约 700 字预计阅读 2 分钟 - 次阅读 - 条评论

最接近的三数之和

1
2
3
4
5
6
7
8
9


func main() {
    nums := []int{-1, 2, 1, -4}
    target := 1
    r := threeSumClosest(nums, target)
    fmt.Println(r) // 2
}
func threeSumClosest(nums []int, target int) int {
    // ......
}

答案

本题和三数之和的思路一样，先将数组nums排序，然后固定一个数，后面两个数变化。

先计算前三个数之和 sum 与 target 的差值 diff。

如果 sum==target，直接返回 target。

如果和与 target 的差值 diff 小于之前的 diff，则更新 diff 的值。

如果 sum 小于 target，则将左边的指针往右移，如果 sum 大于 target，则将右边的指针往左移。

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31


func threeSumClosest(nums []int, target int) int {
    sort.Ints(nums)
    n := len(nums)
    sum := 0
    res := nums[0] + nums[1] + nums[2]
    for i := 0; i < n; i++ {
       l := i + 1
       r := n - 1
       for l < r {
          sum = nums[i] + nums[l] + nums[r]
          if sum == target {
             return target
          }
          if abs(sum-target) < abs(res-target) {
             res = sum
          }
          if sum < target { // 左指针右移
             l++
          } else if sum > target { // 右指针左移
             r--
          }
       }
    }
    return res
}
func abs(a int) int {
    if a < 0 {
       return -a
    }
    return a
}

最大数

179. 最大数

1
2
3
4
5
6
7
8


func main() {
    nums := []int{3, 30, 34, 5, 9}
    r := largestNumber(nums)
    fmt.Println(r) // "9534330"
}
func largestNumber(nums []int) string {
    // ......
}

答案

先将数组进行排序，排序规则为最高位值的大小。如果高位相同，则比较次高位，依次递推，但是这样不好确定每一个数字的位数。

我们需要改一下排序规则：相邻的两个数a、b进行组合，如果a（字符串）组合上 b 的值大于 b 组合上 a 的值，那么 a 就应该排在 b 前面。

本思想参考：算法通关之路。

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16


func largestNumber(nums []int) string {
	sort.Slice(nums, func(i, j int) bool {
		// 字符串也可以比较大小，字符串的大小关系就是数字的大小关系。
		strNum1 := strconv.Itoa(nums[i])
		strNum2 := strconv.Itoa(nums[j])
		return strNum1+strNum2 > strNum2+strNum1
	})
    if nums[0] == 0 {  // 如果排序后的数组第0个元素是“0”，那么说明后面全是0
       return "0"
    }
    res := ""
    for i := 0; i < len(nums); i++ {
       res += strconv.Itoa(nums[i])
    }
    return res
}

收录于合集・算法通关之路 1