发布于2020-11-19 20:52 阅读(603) 评论(0) 点赞(28) 收藏(2)
给出 R 行 C 列的矩阵,其中的单元格的整数坐标为 (r, c),满足 0 <= r < R 且 0 <= c < C。
另外,我们在该矩阵中给出了一个坐标为 (r0, c0) 的单元格。
返回矩阵中的所有单元格的坐标,并按到 (r0, c0) 的距离从最小到最大的顺序排,其中,两单元格(r1, c1) 和 (r2, c2) 之间的距离是曼哈顿距离,|r1 - r2| + |c1 - c2|。(你可以按任何满足此条件的顺序返回答案。)
来源:力扣(LeetCode)
链接:https://leetcode-cn.com/problems/matrix-cells-in-distance-order
著作权归领扣网络所有。商业转载请联系官方授权,非商业转载请注明出处。
我认为自己写的这个更容易明白其中的道理,性能上应该差不多,所以就自己可贴出来分享一下,也可以先看这一部分代码,然后再去看官方的答案,有助于理解
-
- public static int[][] allCellsDistOrder4(int R, int C, int r0, int c0) {
-
- int[][] ret = new int[R * C][];
- int index = 0;
- //添加第一个元素
- ret[index++] = new int[]{r0, c0};
- //确认一个最远距离,有多远就需要生成多少个正方形
- int maxDistance = Math.max(r0, R - 1 - r0) + Math.max(c0, C - 1 - c0);
- for (int distance = 1; distance <= maxDistance; distance++) {
- //由{row,c0}作为起点,正方形的四个顶点落在由row=r0,col = c0 组成的轴上
- int moveRow = r0 - distance;
- int moveCol = c0;
- //一共四条边
- //第一条边,右上
- while (true) {
- if (moveRow >= 0 && moveRow < R && moveCol >= 0 && moveCol < C) {
- ret[index++] = new int[]{moveRow, moveCol};
- }
- moveRow = moveRow + 1;
- moveCol = moveCol + 1;
- if (moveRow == r0) {
- break;
- }
- }
- //第二条边,左上
- while (true) {
- if (moveRow >= 0 && moveRow < R && moveCol >= 0 && moveCol < C) {
- ret[index++] = new int[]{moveRow, moveCol};
- }
- moveRow = moveRow + 1;
- moveCol = moveCol - 1;
- if (moveCol == c0) {
- break;
- }
- }
- //第三条边,左下
- while (true) {
- if (moveRow >= 0 && moveRow < R && moveCol >= 0 && moveCol < C) {
- ret[index++] = new int[]{moveRow, moveCol};
- }
- moveRow = moveRow - 1;
- moveCol = moveCol - 1;
- if (moveRow == r0) {
- break;
- }
- }
- //第四条边,右下
- while (true) {
- if (moveRow >= 0 && moveRow < R && moveCol >= 0 && moveCol < C) {
- ret[index++] = new int[]{moveRow, moveCol};
- }
- moveRow = moveRow - 1;
- moveCol = moveCol + 1;
- if (moveCol == c0) {
- break;
- }
- }
-
- }
-
- return ret;
- }
这个是力扣给的答案,看了半天才明白在说什么:
-
- public static int[][] allCellsDistOrder3(int R, int C, int r0, int c0) {
-
- int[] dr = {1, 1, -1, -1};
- int[] dc = {1, -1, -1, 1};
- //到四个顶点的最大距离
- int maxDist = Math.max(r0, R - 1 - r0) + Math.max(c0, C - 1 - c0);
- int[][] ret = new int[R * C][];
- //起始点座标
- int row = r0, col = c0;
- int index = 0;
- //添加起始点
- ret[index++] = new int[]{row, col};
- for (int dist = 1; dist <= maxDist; dist++) {
- //行减一
- row--;
- //取得四个点,每一次循环完毕,还会回到起始点,方便row再一次减减
- for (int i = 0; i < 4; i++) {
- //i确定一条边,直到遇到下一个端点时停止(数组与i共同确定了边的走向)
- //如果i是2的整数倍,且跟原点不在同一行
- //如果i不是2的整数倍,且跟原点不在同一列
- while ((i % 2 == 0 && row != r0) || (i % 2 != 0 && col != c0)) {
- //如果行大于0,且行小于最大值,且列大于0,且列小于最大值
- if (row >= 0 && row < R && col >= 0 && col < C) {
- //返回值赋值为当前结点
- ret[index++] = new int[]{row, col};
- }
- //在这条边上,运动方向是同向的(只朝一个方向)
- row += dr[i];
- col += dc[i];
- }
- }
- }
- return ret;
- }
-
作者:javagogogo
链接:http://www.javaheidong.com/blog/article/1042/688b6434cd2414743641/
来源:java黑洞网
任何形式的转载都请注明出处,如有侵权 一经发现 必将追究其法律责任
昵称:
评论内容:(最多支持255个字符)
---无人问津也好,技不如人也罢,你都要试着安静下来,去做自己该做的事,而不是让内心的烦躁、焦虑,坏掉你本来就不多的热情和定力
Copyright © 2018-2021 java黑洞网 All Rights Reserved 版权所有,并保留所有权利。京ICP备18063182号-2
投诉与举报,广告合作请联系vgs_info@163.com或QQ3083709327
免责声明:网站文章均由用户上传,仅供读者学习交流使用,禁止用做商业用途。若文章涉及色情,反动,侵权等违法信息,请向我们举报,一经核实我们会立即删除!