1. 题目
今天学习0304专业级第二题
|
某运营商客户基于其通讯能力提供了地震预警服务，假设视某地震多发区域为一个正方形地图，如下所示：
· 区域左上角单元格位置为[0, 0] 当发生地震时（震源是区域内某个单元格），地震预警按照如下通知模型通知用户： · 以栅格为单位进行通知，仅通知「栅格通知范围」为指定值radius内（含）、且有用户的栅格； 「栅格通知范围」：栅格中心点与震源点之间的曼哈顿距离。现约定栅格边长为奇数，即必有一个单元格作为栅格中心点； · 按照栅格通知范围由近及远依次通知栅格内用户； · 栅格通知范围相同时，优先通知栅格用户量较多的； · 栅格用户量也相同时，优先通知栅格编号较小的。 现已知震源位置以及区域内所有用户位置，请按照通知模型依次输出通知的栅格编号。 输入 首行三个正整数 mapSideLen gridSideLen radius，分别表示地图边长、栅格边长、栅格通知范围 1 <= gridSideLen <= mapSideLen <= 8192，输入保证gridSideLen为奇数 第二行两个整数row col，表示震源发生的单元格位置 一个单元格内可以有多个用户。 输出 一个整数序列，表示待通知的栅格编号。如果没有符合条件的栅格，请输出空序列 [] 样例 输入样例 1
9 3 6 3 2 6 3 5 7 4 6 5 5 7 2 5 5 7 输出样例 1
[5 2 6 8] 提示样例 1 输入数据表示的内容参考上图： 与震源距离小于等于通知范围6的栅格编号为1、2、4、5、6、7、8 号；其中有用户的栅格为 2、5、6、8号，与震源的曼哈顿距离分别为 4、3、6、6。 首先按由近及远通知，先通知5号、2号；对于6号和8号，依次比较距离和用户数，都相同，则按栅格编号从小到大先通知 6号。 输入样例 2
3 1 3 0 0 1 2 2
输出样例 2 [] 提示样例 2 没有符合条件的栅格，输出空序列 提示：点P1位置(x1,y1)与点P2坐标(x2,y2)曼哈顿距离=|x1-x2|+|y1-y2| |
2. 题目分析
题目理解：
这是一道模拟题，需要找出距离震源位置最近的栅格，并输出这些栅格的编号。
以样例1为例：
1) 输出栅格的中心点到地震源的曼哈顿距离必须是小于等于栅格通知半径（distance <= radius）
2) 输出栅格必须是有用户的，没有用户的不输出
3) 排序条件：
l 按照每个栅格的中心点坐标到地震源的曼哈顿距离升序
l 如果距离相同则按照用户数降序（即用户多的栅格排在前面）
l 如果用户数仍然相同，则按照栅格编号升序
思路解析：
在得到有序栅格数据的前提是要先进行预处理，所以总体步骤是：预处理 + 排序
1) 预处理数据之建模
预处理的关键是先建模，题目已经提供了地图边长、栅格边长、通知半径、震源点位置、所有用户的位置信息，需要计算的信息有：
l 每个用户所属的栅格的编号、每个栅格内有多少用户
l 每个栅格中心点位置、每个栅格中心点位置和震源点之间的距离
建模可以分为两层：
Ø 第一层：多个栅格对象和单个栅格对象之间的关系
核心的数据结构是栅格，其类图可以表示为：
对多个栅格对象的管理需要两个关键变量：
² 为了方便根据栅格编号找到栅格对象，通常用一个hash/map/dict变量来组织。
² 又由于需要对多个符合条件的栅格排序，所以通常还要用一个数组变量管理多个栅格对象。
Ø 第二层：单个栅格对象内部的模型
可以用一个结构体，也可以用数组、vector、List等
2) 预处理数据的方法
l 方法一：暴力遍历所有栅格，计算每个栅格的中心点位置以及和震源点之间的距离
栅格的数量级是8192*8192，有超时的风险
l 方法二：遍历所有用户，根据用户位置得到栅格的中心点位置
由于用户数不超过1000，有点类似稀疏矩阵，所以遍历用户这种方法计算量比较小。
经过对数据量的分析，需要选择方法二，即从用户入手进行预处理数据。
3. 员工1-C代码:40行（不包括框架代码，下同）、最大圈复杂度7
/*
* Copyright (c) Huawei Technologies Co., Ltd. 2019-2021. All rights reserved.
* Description: 上机编程认证
* Note: 缺省代码仅供参考，可自行决定使用、修改或删除
*/
#include <stdio.h>
#include "securec.h"
#define MAX_USER_COUNT 1000
#define MAX_OUTPUT_SIZE 1000
typedef struct {
int dis;
int index;
int num;
} sGrid;
int cmp(const void *_a, const void *_b) {
sGrid *a = (sGrid*)_a;
sGrid *b = (sGrid*)_b;
if (a->dis != b->dis) {
return a->dis - b->dis;
}
if (a->num != b->num) {
return b->num - a->num;
}
return a->index - b->index;
}
// 待实现函数，在此函数中填入答题代码。
// 返回的数据填充到outBuf中，maxOutBufLen是outBuf最大长度，实际长度通过返回值返回。
static int GetNotificationOrder(int mapSideLen, int gridSideLen, int radius, int row, int col,
int usersNum, int **userArray, int *outBuf, int maxOutBufLen)
{
int count = 0;
int width = mapSideLen / gridSideLen;
int *nums = (int*)malloc(sizeof(int) * width * width);
for (int i = 0; i < width * width; i++) {
nums[i] = 0;
}
for (int i = 0; i < usersNum; i++) {
int index = userArray[i][0] / gridSideLen * width + userArray[i][1] / gridSideLen;
nums[index]++;
}
sGrid *ret = (sGrid*)malloc(sizeof(sGrid) * MAX_OUTPUT_SIZE);
for (int i = 0; i < width * width; i++) {
int rowcen = i / width * gridSideLen + gridSideLen / 2; // 2为一半
int colcen = i % width * gridSideLen + gridSideLen / 2; // 2为一半
int dis = abs(rowcen - row) + abs(colcen - col);
if (dis <= radius && nums[i] != 0) {
sGrid s = {dis, i, nums[i]};
ret[count++] = s;
}
}
qsort(ret, count, sizeof(sGrid), cmp);
for (int i = 0; i < count; i++) {
outBuf[i] = ret[i].index + 1;
}
return count;
}
int main(void)
{
int mapSideLen;
int gridSideLen;
int radius;
if (scanf_s("%d%d%d", &mapSideLen, &gridSideLen, &radius) != 3) { return -1; }
int row;
int col;
int usersNum;
if (scanf_s("%d%d%d", &row, &col, &usersNum) != 3) { return -1; }
int buf[MAX_USER_COUNT][2];
int *userArray[MAX_USER_COUNT];
for (int i = 0; i < usersNum; i++) {
if (scanf_s("%d %d", &buf[i][0], &buf[i][1]) != 2) { return -1; }
userArray[i] = buf[i];
}
int outBuf[MAX_OUTPUT_SIZE];
int size = GetNotificationOrder(mapSideLen, gridSideLen, radius, row, col,
usersNum, userArray, outBuf, MAX_OUTPUT_SIZE);
printf("[");
for (int i = 0; i < size; i++) {
printf("%s%d", ((i == 0) ? "" : " "), outBuf[i]);
}
printf("]");
return 0;
}
该解法为栅格定义了一个结构体：sGrid，包括三个成员变量：
typedef struct {
int dis; 栅格中心点与震源点之间的曼哈顿距离
int index; 栅格编号
int num; 栅格内用户数
} sGrid;
|
关键变量 |
作用 |
|
整型数组int *nums； |
数组当hash，记录每个栅格内的用户数 |
|
sGrid *ret |
栅格对象数组，排序需要 |
Ø 第一步：遍历所有用户位置，得到每个栅格内的用户数
int width = mapSideLen / gridSideLen;这句代码是计算栅格的宽度（即行数和列数），样例1中width=9/3=3
int index = userArray[i][0] / gridSideLen * width + userArray[i][1] / gridSideLen;这句代码的作用是计算栅格的编号。
每一个用户的位置，格式同震源位置：row col，例如第一个用户：3 5，计算后index=3/3*3+5/3=4 表示第5号栅格，如下图黄底的格子：
Ø 第二步：遍历所有栅格，计算每个栅格中心点与震源点之间的曼哈顿距离
如果距离满足<=「栅格通知半径」并且栅格内用户数大于0，则添加到数组ret中
Ø 第三步：按要求对所有栅格进行多维排序
通过qsort函数+自定义比较函数cmp来完成排序
思路清晰，数据结构设计合理，代码简洁易懂，值得大家学习。
7. 员工5-GO代码：52行、最大圈复杂度8
/*
* Copyright (c) Huawei Technologies Co., Ltd. 2019-2021. All rights reserved.
* Description: 上机编程认证
* Note: 缺省代码仅供参考，可自行决定使用、修改或删除
* 只能import Go标准库
*/
package main
import (
"bufio"
"fmt"
"math"
"io"
"os"
"sort"
"strconv"
"strings"
)
type earthquakeInfo struct {
rowIdx int
colIdx int
radius int
}
type gridNode struct {
gridIdx int
userNum int
distance int
}
func getNotificationOrder(mapSideLen int, gridSideLen int, earthquake earthquakeInfo, userArray [][]int) []int {
gridSize := mapSideLen / gridSideLen
gridMap := map[int]*gridNode{}
gridSlice := []*gridNode{}
res := []int{}
for _, v := range userArray {
gidx := getGridIdx(v[0], v[1], gridSize,gridSideLen)
if _, ok := gridMap[gidx]; ok {
gridMap[gidx].userNum++
} else {
flg, distance := checkDistance(gidx, gridSize, earthquake,gridSideLen)
if flg == true {
gnode := &gridNode{gidx, 1, distance}
gridMap[gidx] = gnode
gridSlice = append(gridSlice, gnode)
}
}
}
sort.Slice(gridSlice, func(i, j int) bool {
if gridSlice[i].distance == gridSlice[j].distance {
if gridSlice[i].userNum == gridSlice[j].userNum {
return gridSlice[i].gridIdx < gridSlice[j].gridIdx
}
return gridSlice[i].userNum > gridSlice[j].userNum
}
return gridSlice[i].distance < gridSlice[j].distance
})
for _, v := range gridSlice {
res = append(res, v.gridIdx)
}
return res
}
func checkDistance(gidx, gridSize int, earthquake earthquakeInfo ,gridSideLen int) (bool, int) {
delta := (gridSideLen - 1) / 2
gridCenterRow := ((gidx-1)/gridSize)*gridSideLen + delta
gridCenterCol := ((gidx-1)%gridSize)*gridSideLen + delta
distance := int(math.Abs(float64(gridCenterRow)-float64(earthquake.rowIdx)) +
math.Abs(float64(gridCenterCol)-float64(earthquake.colIdx)))
if distance <= earthquake.radius {
return true, distance
}
return false, -1
}
func getGridIdx(row, col, gridSize int, gridLen int) int {
rowA := row / gridLen
colA := col / gridLen
return rowA*gridSize + colA + 1
}
func main() {
reader := bufio.NewReader(os.Stdin)
var mapSideLen, gridSideLen, radius int
if _, err := fmt.Fscanf(reader, "%d %d %d\n", &mapSideLen, &gridSideLen, &radius); err != nil {
fmt.Println(err.Error())
return
}
var rowIdx, colIdx int
if _, err := fmt.Fscanf(reader, "%d %d\n", &rowIdx, &colIdx); err != nil {
fmt.Println(err.Error())
return
}
userArray := readInputIntArrayFromNlines(reader)
result := getNotificationOrder(mapSideLen, gridSideLen, earthquakeInfo{rowIdx, colIdx, radius}, userArray)
fmt.Print("[")
for ind, val := range result {
fmt.Print(val)
if ind != len(result)-1 {
fmt.Print(" ")
}
}
fmt.Print("]")
}
func readInputIntArrayFromNlines(reader *bufio.Reader) [][]int {
var row int
if _, err := fmt.Fscanf(reader, "%d\n", &row); err != nil {
fmt.Println(err.Error())
return nil
}
if row <= 0 {
return [][]int{}
}
result := make([][]int, 0, row)
for i := 0; i < row; i++ {
lineBuf, err := reader.ReadString('\n')
if err != nil && err != io.EOF {
fmt.Println(err.Error())
return nil
}
lineBuf = strings.TrimRight(lineBuf, "\r\n")
lineBuf = strings.TrimSpace(lineBuf)
ints := map2IntArray(lineBuf, " ")
if len(ints) != 2 {
fmt.Println("col len is not 2")
return nil
}
result = append(result, ints)
}
return result
}
func map2IntArray(str string, dem string) []int {
tempArray := strings.Split(str, dem)
result := make([]int, len(tempArray))
for index, value := range tempArray {
value = strings.TrimSpace(value)
intVal, err := strconv.Atoi(value)
if err == nil {
result[index] = intVal
}
}
return result
}
该解法为栅格定义一个结构体gridNode，然后定义以map变量gridMap，key=栅格编号，value=gridNode指针。
因为要排序，所以额外定义了一个切片对象gridSlice := []*gridNode{}，每个元素是一个gridNode指针，和gridMap的value指向同一个内存地址。
|
关键变量 |
作用 |
|
gridMap := map[int]*gridNode{} |
根据栅格编号找到栅格对象 |
|
gridSlice := []*gridNode{} |
栅格对象切片，排序需要 |
处理步骤也是分为两步：
Ø 第一步：遍历所有用户位置，得到每个栅格内的用户数、计算每个栅格中心点与震源点之间的曼哈顿距离
在函数checkDistance内就顺便校验了曼哈顿距离，如果大于「栅格通知半径」则不添加到gridMap和gridSlice中。
Ø 第二步：按要求对所有栅格进行多维排序
注意多维排序有很多种写法，员工1-C代码那种写法比较好：圈复杂度只有2，嵌套深度只有1。
待改进之处：
有违反编程规范建议项，例如36/37行：G.TYP.07 避免使用短声明定义一个空的slice（不扣分）
9. 总结
1) 本题的处理步骤
2) 两层模型具体的数据结构表达
从展示代码可以看到，两个关键数据主要有下面几种数据结构设计方法（前者是根据栅格编号找到栅格、后者是用于排序）：
3) 多维排序
排序是编程基础知识之一，工作中用的较多，需要熟练掌握。
多维排序又叫多条件排序，参考之前的案例：
【案例开放030】上机编程字典序排序总结 http://3ms.huawei.com/km/groups/3803117/blogs/details/10172393?l=zh-cn
【案例开放035】0521上机编程“租房信息查询系统”学习交流 http://3ms.huawei.com/km/groups/3803117/blogs/details/10397189
4) 直角坐标系和矩阵的区别
直角坐标系通常是以一象限的方式呈现，而矩阵通常是从上到下、从左到右的方式，如下图所示：
直角坐标系的坐标(2,3)的位置见左图红色圆圈，矩阵的位置[2,3]见右图右下角的斜格。
我们通常用矩阵来表示一个二维数组：最上面一行为第0行、最左侧列为第0列。
在编程时注意不要混淆了。
欢迎大家分享工作中遇到的数据结构和算法应用问题及其案例。
认证以考促学，重点是持续不断自我学习和能力提升，不断进阶，成为优化代码性能、驾驭CleanCode的王者！
扩展学习：
l 前期开放的案例见3ms社区合集：http://3ms.huawei.com/km/groups/3803117/blogs/details/9595962
l 心声社区合集：http://xinsheng.huawei.com/cn/index.php?app=space&mod=Index&act=view&maskId=2119419
l 软件开发能力认证-上机编程科目FAQ（外部LeetCode）：http://3ms.huawei.com/km/groups/3803117/blogs/details/7887463?l=zh-cn
l 软件开发能力认证-上机编程科目FAQ（ilearning）：http://3ms.huawei.com/km/groups/3803117/blogs/details/7878885?l=zh-cn
l 上机编程（OJ）认证开放试题列表汇总：http://3ms.huawei.com/km/groups/3803117/blogs/details/9606176
l 软件开发上机编程认证介绍与交流（2021-11-30直播回放）https://inner.welink.huawei.com/newlive/vod/v1/8151669797783011328