头像

gyh


访客:16030

在线 



gyh
3天前

题目描述

给你一个房屋数组 houses 和一个整数 k ,其中 houses[i] 是第 i 栋房子在一条街上的位置,现需要在这条街上安排 k 个邮筒。

请你返回每栋房子与离它最近的邮筒之间的距离的 最小 总和。

答案保证在 32 位有符号整数范围以内。

样例1

输入:houses = [1,4,8,10,20], k = 3
输出:5
解释:将邮筒分别安放在位置 3, 9 和 20 处。
每个房子到最近邮筒的距离和为 |3-1| + |4-3| + |9-8| + |10-9| + |20-20| = 5 。

样例2

输入:houses = [2,3,5,12,18], k = 2
输出:9
解释:将邮筒分别安放在位置 3 和 14 处。
每个房子到最近邮筒距离和为 |2-3| + |3-3| + |5-3| + |12-14| + |18-14| = 9 。

样例3

输入:houses = [7,4,6,1], k = 1
输出:8
示例 4:

样例4

输入:houses = [3,6,14,10], k = 4
输出:0

限制

  • n == houses.length
  • 1 <= n <= 100
  • 1 <= houses[i] <= 10^4
  • 1 <= k <= n
  • 数组 houses 中的整数互不相同。

算法

(贪心 + 动态规划) $O(n² · m)$
  1. 枚举所有邮箱放的位置会有达到 $C_{n}^{k}$ 种结果。所以我们采取另一种策略,先找出所有房子的势力范围,在势力范围内再定位邮箱放的位置。
  2. acwing. 1478.jpg
  3. 分析思路:
    • 当只有 1 个邮箱的时候,邮箱放在放在所有房子的正中间会使得所有房子到邮箱的距离最短;
    • 当有 2 个邮箱的时候,邮箱会放在某 2 个区间内 [0, x][x+1, n], 其中 0 < x < n。 因此这 2 个邮箱会分别放在[0, x]的正中间位置 和 [x+1, n] 的正中间位置上,使得房子到邮箱的距离和最小。
    • 当有 k个邮箱的时候,我们就可以将所有房子划分成k个区间(相当于划分为k个势力范围),每个区间求出最短距离和相加,就能求出k个邮箱与所有房子的最短距离和
  4. 分析初始化:
    • 由于最终答案要求的是min, 首先初始化全部为无穷大,像 MAX_INF0x3f3f3f3f等等。
    • 表示的无穷大还可以更精细一些,根据题目给的数据范围,房子数量最多是1e4, 那任意2个房子中放1个邮箱的最大距离和是1e4, 最多是100个邮箱,所以这个无穷大可以是1e4 * 100=1e6来表示
    • 然后考虑,对f[0][i]f[i][0]进行初始化
      • f[0][i] 表示只有1个房子且最多i个势力范围,自然是将邮箱就放在房子的位置距离最小为0;
      • f[i][0] 表示有i个房子且0`个势力范围,这是无解的情况,初始化为无穷大来表示无解;
    • 初学者可能不知道接着要做什么:
      • 因为我们已经对边界f[0][i]、f[i][0]初始化好了,所以dp过程要从1开始,而不是从0开始
      • 初始化不一定非要写在dp过程外面,也可以写在dp过程里面的,只要能满足效果代码可以自由发挥~
  5. 为什么状态表示的第二维要定义是 最多 j个势力范围?
    • 一开始状态表示可以随便想一个 至少、恰好、最多,看看能不能做出来,如果做不出来再换一个,毕竟就这3个;
    • 其实邮箱提供得越多,房子到邮箱距离和会更小:当有n个房子和n个邮箱,每个房子各一个邮箱,这样距离和就是0了,所以最终答案f[n-1][k] 就是题目所求。
    • 下面会给出 最多、恰好j个势力范围的代码hh

时间复杂度

  • 状态数是二维状态 f[i, j] $O(n · m)$
  • 状态计算需要的时间是 $O(n)$
  • 故总的时间复杂度是 $O(n² · m)$

空间复杂度

  • 二维状态 f[i, j] 需要额外的空间是 $O(n · m)$
  • 预处理所有[i, j]区间的距离和,需要额外的空间是 $O(n²)$
  • 故总的空间复杂度是 $O(n · m) + O(n²)$

其他

Go 代码1

  • f[i, j]的集合表示:从前i个房子里选,且能放置最多 j个邮箱的最小距离和的所有方案
func abs(x int) int {
    if x < 0 {
        return -x
    }
    return x
}

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

func minDistance(hs []int, m int) int {
    sort.Ints(hs[:])
    n := len(hs)

    const INF int = 1e6 + 10 // 1e4 * 100 = 1e6

    f := make([][]int, n)
    for i := 0; i < n; i ++ {
        f[i] = make([]int, m + 1)
    }

    cost := make([][]int, n)
    for i := 0; i < n; i ++ {
        cost[i] = make([]int, n)
    }

    for i := 0; i < n; i ++ {
        for j := i; j < n; j ++ {
            for k := i; k <= j; k ++ {
                cost[i][j] += abs(hs[k] - hs[i + (j - i + 1) / 2])
            }
        }
    }

    // 从前i个房子选且势力划分最多为j的最小距离和
    for i := 0; i < n; i ++ {
        f[i][0] = INF
    }

    // f[0][i] = 0, 只有1个房子不管多少势力, 距离和是0

    // 倒数第1个房子的势力是[1~k] 来划分
    for i := 1; i < n; i ++ {
        for j := 1; j <= m; j ++ {
            f[i][j] = INF
            for k := 0; k <= i; k ++ {
                t := 0
                if k > 0 {
                    t = f[k - 1][j - 1]
                }
                f[i][j] = min(f[i][j], t + cost[k][i])
            }
        }
    }

    return f[n - 1][m]
}

Go 代码2

  • f[i, j]的集合表示:从前i个房子里选,且能放置恰好 j个邮箱的最小距离和的所有方案
  • 和代码1唯一不同的是f[i, j]初始化的代码
func abs(x int) int {
    if x < 0 {
        return -x
    }
    return x
}

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

func minDistance(hs []int, m int) int {
    sort.Ints(hs[:])
    n := len(hs)

    const INF int = 1e6 + 10 // 1e4 * 100 = 1e6

    f := make([][]int, n)
    for i := 0; i < n; i ++ {
        f[i] = make([]int, m + 1)
    }

    cost := make([][]int, n)
    for i := 0; i < n; i ++ {
        cost[i] = make([]int, n)
    }

    for i := 0; i < n; i ++ {
        for j := i; j < n; j ++ {
            for k := i; k <= j; k ++ {
                cost[i][j] += abs(hs[k] - hs[i + (j - i + 1) / 2])
            }
        }
    }

    // 从前i个房子选且势力划分恰好为j的最小距离和.
    for i := 0; i < n; i ++ {
        for j := 0; j <= m; j ++ {
            f[i][j] = INF
        }
    }
    f[0][1] = 0

    // 倒数第1个房子的势力是[1~k] 来划分
    for i := 1; i < n; i ++ {
        for j := 1; j <= m; j ++ {
            for k := 0; k <= i; k ++ {
                t := 0
                if k > 0 {
                    t = f[k - 1][j - 1]
                }
                f[i][j] = min(f[i][j], t + cost[k][i])
            }
        }
    }

    return f[n - 1][m]
}


活动打卡代码 LeetCode 1478. 安排邮筒

gyh
4天前

绝对值不等式 + dp

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

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

func minDistance(hs []int, m int) int {
    sort.Ints(hs[:])
    n := len(hs)

    const INF int = 1e6 + 10 // 1e4 * 100 = 1e6

    f := make([][]int, n)
    for i := 0; i < n; i ++ {
        f[i] = make([]int, m + 1)
    }

    cost := make([][]int, n)
    for i := 0; i < n; i ++ {
        cost[i] = make([]int, n)
    }

    for i := 0; i < n; i ++ {
        for j := i; j < n; j ++ {
            for k := i; k <= j; k ++ {
                cost[i][j] += abs(hs[k] - hs[i + (j - i + 1) / 2])
            }
        }
    }

    // 从前i个房子选且势力划分最多为j的最小距离和
    for i := 0; i < n; i ++ {
        f[i][0] = INF
    }

    // f[0][i] = 0, 只有1个房子不管多少势力, 距离和是0

    // 倒数第1个房子的势力是[1~k] 来划分
    for i := 1; i < n; i ++ {
        for j := 1; j <= m; j ++ {
            f[i][j] = INF
            for k := 0; k <= i; k ++ {
                t := 0
                if k > 0 {
                    t = f[k - 1][j - 1]
                }
                f[i][j] = min(f[i][j], t + cost[k][i])
            }
        }
    }

    return f[n - 1][m]
}



gyh
4天前

记忆化

  • f[i] : 记录以i为下标的[i, j]区间和为 target 的长度
  • 所有数都是正数,所以区间和只会越加越大~,所以可以从左到右只扫描一遍找所有的[i, j]区间和为target的方案
func min(a, b int) int {
    if a > b {
        return b
    }
    return a
}

func minSumOfLengths(arr []int, target int) int {
    n := len(arr)
    const INF int = 1e8

    f := make([]int, n + 1)
    for i := 0; i <= n; i ++ {
        f[i] = INF
    }

    res := INF
    for i, j, sum := 0, 0, 0; i < n; i ++ {
        sum += arr[i]
        for ; sum > target ; {
            sum -= arr[j]
            j ++
        }

        if sum == target {
            if j > 0 {
                res = min(res, i - j + 1 + f[j - 1])
            }
            f[i] = i - j + 1
        }

        if i > 0 {
            f[i] = min(f[i], f[i - 1])
        }
    }

    if res > n {
        res = -1
    }

    return res
}


活动打卡代码 LeetCode 1476. 子矩形查询

gyh
4天前
type SubrectangleQueries struct {
    rectangle [][]int
}


func Constructor(rectangle [][]int) SubrectangleQueries {
    return SubrectangleQueries{rectangle : rectangle}
}


func (this *SubrectangleQueries) UpdateSubrectangle(row1 int, col1 int, row2 int, col2 int, newValue int)  {
    for i := row1; i <= row2; i ++ {
        for j := col1; j <= col2; j ++ {
            this.rectangle[i][j] = newValue
        }
    }
}


func (this *SubrectangleQueries) GetValue(row int, col int) int {
    return this.rectangle[row][col];
}


/**
 * Your SubrectangleQueries object will be instantiated and called as such:
 * obj := Constructor(rectangle);
 * obj.UpdateSubrectangle(row1,col1,row2,col2,newValue);
 * param_2 := obj.GetValue(row,col);
 */


活动打卡代码 LeetCode 1494. 并行课程 II

gyh
5天前
func min(a, b int) int {
    if a > b {
        return b
    }
    return a
}

var f []int
const INF int = 10000

func minNumberOfSemesters(n int, deps [][]int, k int) int {
    f = make([]int, 1 << n)
    for i := 0; i < 1 << n; i ++ {
        f[i] = INF
    }

    f[0] = 0
    for i, _ := range deps {
        deps[i][0] --
        deps[i][1] --
    }

    for i := 0; i < 1 << n; i ++ {
        st := make([]bool, n)
        for _, dep := range deps {
            x, y := dep[0], dep[1]
            if i >> x & 1 == 0 { // 找出不能上的课y标记为true
                st[y] = true
            }
        }

        state := 0
        for j := 0; j < n; j ++ {
            if !st[j] && i >> j & 1 == 0 { // 如果j可以上,必能且j未上过
                state += 1 << j
            }
        }

        dfs(n, k, i, state, 0, 0)
    }
    return f[(1 << n) - 1]
}

func dfs(n, k, i, state, now, start int) {
    if k <= 0 || state == 0 { // 如果这学期上完了所有课 或者 没有别的课能上
        f[i | now] = min(f[i | now], f[i] + 1)
        return
    }

    for j := start; j < n; j ++ {
        if state >> j & 1 == 1 { // 如果j可以上
            dfs(n, k - 1, i, state - (1 << j), now + (1 << j), j + 1)
        }
    }
}



gyh
5天前
func min(a, b int) int {
    if a > b {
        return b
    }
    return a
}

func minCost(hs []int, cost [][]int, m int, n int, target int) int {
    const INF int = 1e8
    f := make([][][]int, m)
    for i := 0; i < m; i ++ {
        f[i] = make([][]int, m + 1)
        for j := 0; j <= m; j ++ {
            f[i][j] = make([]int, n + 1)
            for k := 0; k <= n; k ++ {
                f[i][j][k] = INF
            }
        }
    }

    if hs[0] != 0 {
        f[0][1][hs[0]] = 0
    } else {
        for k := 1; k <= n; k ++ {
            f[0][1][k] = cost[0][k - 1]
        }
    }

    for i := 1; i < m; i ++ {
        for j := 1; j <= target; j ++ {
            if hs[i] != 0 {
                k := hs[i]
                for u := 1; u <= n; u ++ {
                    if u == k {
                        f[i][j][k] = min(f[i][j][k], f[i - 1][j][u])
                    } else {
                        f[i][j][k] = min(f[i][j][k], f[i - 1][j - 1][u])
                    }
                }
            } else {
                for k := 1; k <= n; k ++ {
                    for u := 1; u <= n; u ++ {
                        if u == k {
                            f[i][j][k] = min(f[i][j][k], f[i - 1][j][u] + cost[i][k - 1])
                        } else {
                            f[i][j][k] = min(f[i][j][k], f[i - 1][j - 1][u] + cost[i][k - 1])
                        }
                    }
                }
            }
        }
    }

    res := INF
    for i := 1; i <= n; i ++ {
        res = min(res, f[m - 1][target][i])
    }

    if res == INF {
        res = -1
    }

    return res
}



gyh
6天前
func max(a, b int) int {
    if a > b {
        return a
    }
    return b
}

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

type BrowserHistory struct {
    cur int
    list []string
}


func Constructor(homepage string) BrowserHistory {
    return BrowserHistory{cur : 0, list : []string{homepage}}
}


func (this *BrowserHistory) Visit(url string)  {
    this.list = this.list[ : this.cur + 1]
    this.list = append(this.list, url)
    this.cur ++
}


func (this *BrowserHistory) Back(steps int) string {
    this.cur = max(0, this.cur - steps)
    return this.list[this.cur]
}


func (this *BrowserHistory) Forward(steps int) string {
    this.cur = min(len(this.list) - 1, this.cur + steps)
    return this.list[this.cur]
}


/**
 * Your BrowserHistory object will be instantiated and called as such:
 * obj := Constructor(homepage);
 * obj.Visit(url);
 * param_2 := obj.Back(steps);
 * param_3 := obj.Forward(steps);
 */



gyh
6天前
import "sort"

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

func getStrongest(arr []int, k int) []int {
    n := len(arr)
    sort.Ints(arr[:])
    m := arr[(n - 1) / 2]
    sort.Slice(arr, func(i, j int) bool {
        if abs(arr[i] - m) != abs(arr[j] - m) {
            return abs(arr[i] - m) > abs(arr[j] - m)
        }
        return arr[i] > arr[j]
    })

    return arr[:k]
}



gyh
6天前
func shuffle(nums []int, n int) []int {
    res := []int{}

    for i := 0; i < n; i ++ {
        res = append(res, nums[i])
        res = append(res, nums[i + n])
    }

    return res
}


活动打卡代码 AcWing 1455. 招聘

gyh
10天前
package main

import "fmt"

const N int = 1010

var (
    n, m, T int
    a [N]int
)

func main(){
    fmt.Scanf("%d", &T)


    for ; T > 0; T -- {
        fmt.Scanf("%d", &n)
        fmt.Scanf("%d", &m)

        for i := 0; i < m; i ++ {
            fmt.Scanf("%d", &a[i])
        }

        res := 0
        for i, j := 1, (n - 1) % m; i < n; i ++ {
            j --

            if (j < 0) {
                j = m - 1
            }

            res = (res + a[j]) % (i + 1)
        }

        fmt.Printf("%d\n", res)
    }
}