写点什么

2022-11-24:小团在地图上放了 3 个定位装置,想依赖他们进行定位! 地图是一个 n*n 的棋盘, 有 3 个定位装置 (x1,y1),(x2,y2),(x3,y3),每个值均在 [1,n] 内。 小团在 (a,

  • 2022-11-24
    北京
  • 本文字数:1336 字

    阅读完需:约 4 分钟

2022-11-24:小团在地图上放了3个定位装置,想依赖他们进行定位! 地图是一个n*n的棋盘, 有3个定位装置(x1,y1),(x2,y2),(x3,y3),每个值均在[1,n]内。 小团在(a,

2022-11-24:小团在地图上放了 3 个定位装置,想依赖他们进行定位!地图是一个 n*n 的棋盘,有 3 个定位装置(x1,y1),(x2,y2),(x3,y3),每个值均在[1,n]内。小团在(a,b)位置放了一个信标,每个定位装置会告诉小团它到信标的曼哈顿距离,也就是对于每个点,小团知道|xi-a|+|yi-b|求信标位置,信标不唯一,输出字典序最小的。输入 n,然后是 3 个定位装置坐标,最后是 3 个定位装置到信标的曼哈顿记录。输出最小字典序的信标位置。1 <= 所有数据值 <= 50000。来自美团。8.20 笔试。题目 2。


答案 2022-11-24:


先找半径小的,小圆周要快些,宽度优先遍历。


代码用 golang 编写。代码如下:


package main
import ( "fmt")
func main() { ans := find(3, []int{1, 1}, []int{3, 1}, []int{3, 4}, 3, 3, 2) fmt.Println(ans)}
const MAX_VALUE = 1<<31 - 1
func find(n int, a, b, c []int, ad, bd, cd int) []int { var x1 []int r1 := MAX_VALUE var x2 []int r2 := 0 var x3 []int r3 := 0 if ad < r1 { x1 = a r1 = ad x2 = b r2 = bd x3 = c r3 = cd } if bd < r1 { x1 = b r1 = bd x2 = a r2 = ad x3 = c r3 = cd } if cd < r1 { x1 = c r1 = cd x2 = a r2 = ad x3 = b r3 = bd } // x1 r1 x2 r2 x3 r3 cur := []int{x1[0] - r1, x1[1]} queue := make([][]int, 0) visited := make(map[string]struct{}) ans := make([][]int, 0) queue = append(queue, cur) visited[fmt.Sprintf("%d_%d", cur[0], cur[1])] = struct{}{}
for len(queue) > 0 { // cur x1为圆心,r1为半径的圆周上 cur = queue[0] queue = queue[1:] if cur[0] >= 1 && cur[0] <= n && cur[1] >= 1 && cur[1] <= n && distance(cur[0], cur[1], x2) == r2 && distance(cur[0], cur[1], x3) == r3 { ans = append(ans, cur) } if len(ans) == 2 { break } add(cur[0]-1, cur[1]-1, x1, r1, &queue, visited) add(cur[0]-1, cur[1], x1, r1, &queue, visited) add(cur[0]-1, cur[1]+1, x1, r1, &queue, visited) add(cur[0], cur[1]-1, x1, r1, &queue, visited) add(cur[0], cur[1]+1, x1, r1, &queue, visited) add(cur[0]+1, cur[1]-1, x1, r1, &queue, visited) add(cur[0]+1, cur[1], x1, r1, &queue, visited) add(cur[0]+1, cur[1]+1, x1, r1, &queue, visited) } if len(ans) == 1 || ans[0][0] < ans[1][0] || (ans[0][0] == ans[1][0] && ans[0][1] < ans[1][1]) { return ans[0] } else { return ans[1] }}
func add(x, y int, c []int, r int, queue *[][]int, visited map[string]struct{}) { key := fmt.Sprintf("%d_%d", x, y) _, ok := visited[key] if (distance(x, y, c) == r) && !ok { *queue = append(*queue, []int{x, y}) visited[key] = struct{}{} }}
func distance(x, y int, c []int) int { return abs(x-c[0]) + abs(y-c[1])}
func abs(a int) int { if a < 0 { return -a } else { return a }}
复制代码


执行结果如下:





左神java代码

发布于: 刚刚阅读数: 3
用户头像

还未添加个人签名 2021-02-15 加入

还未添加个人简介

评论

发布
暂无评论
2022-11-24:小团在地图上放了3个定位装置,想依赖他们进行定位! 地图是一个n*n的棋盘, 有3个定位装置(x1,y1),(x2,y2),(x3,y3),每个值均在[1,n]内。 小团在(a,_golang_福大大架构师每日一题_InfoQ写作社区