刚睡醒的番茄

V1

2022/12/01阅读:25主题:蔷薇紫

前端小白的力扣打卡日常-1779

前言

本人身为一个前端小白,一开始就没怎么接触过算法。想着做前端应该也不太需要去学算法,但是最近看到各种面试经历的文章以及身边一些人的面试经历,都说明了算法的重要性,从现在开始我也要慢慢来,先从打卡力扣每日一题开始!

题目内容

1779. 找到最近的有相同 X 或 Y 坐标的点

给你两个整数 x 和 y ,表示你在一个笛卡尔坐标系下的 (x, y) 处。同时,在同一个坐标系下给你一个数组 points ,其中 points[i] = [ai, bi] 表示在 (ai, bi) 处有一个点。当一个点与你所在的位置有相同的 x 坐标或者相同的 y 坐标时,我们称这个点是 有效的 。

请返回距离你当前位置 曼哈顿距离 最近的 有效 点的下标(下标从 0 开始)。如果有多个最近的有效点,请返回下标 最小 的一个。如果没有有效点,请返回 -1 。

两个点 (x1, y1) 和 (x2, y2) 之间的 曼哈顿距离 为 abs(x1 - x2) + abs(y1 - y2) 。

输入:x = 3, y = 4, points = [[1,2],[3,1],[2,4],[2,3],[4,4]] 输出:2 解释:所有点中,[3,1],[2,4] 和 [4,4] 是有效点。有效点中,[2,4] 和 [4,4] 距离你当前位置的曼哈顿距离最小,都为 1 。[2,4] 的下标最小,所以返回 2 。

今天的这个题属于简单题,解法的话无非就是暴力枚举去匹配.那就直接上代码

var nearestValidPoint = function (x, y, points{
  // 记录下标
  let point = -1;
  //记录最短的曼哈顿距离
  let Distance = Number.MAX_VALUE;

  for (let i = 0; i < points.length; i++) {
    if (points[i][0] == x || points[i][1] == y) {
      // 匹配到跟起始位置坐标一致,距离为0必定最短直接返回
      if (points[i][0] == x && points[i][1] == y) {
        return i;
      }

      let distance =
        Math.abs(points[i][0] - x) + Math.abs(points[i][1] - y);
      if (distance < Distance) {
        // 距离比记录的距离短不用比较下标
        Distance = distance;
        point = i;
      } else if ((distance = Distance)) {
        // 只有当距离一致时我们才需要比较下标,返回最小的
        point = Math.min(point, i);
      }
    }
  }

  return point;
};

我们来看一下官方的解法

var nearestValidPoint = function(x, y, points{
    const n = points.length;
    let best = Number.MAX_VALUE, bestid = -1;
    for (let i = 0; i < n; ++i) {
        const px = points[i][0], py = points[i][1];
        if (x === px) {
            const dist = Math.abs(y - py);
            if (dist < best) {
                best = dist;
                bestid = i;
            }
        } else if (y === py) {
            const dist = Math.abs(x - px);
            if (dist < best) {
                best = dist;
                bestid = i;
            }
        }
    }
    return bestid;
};

因为要求中是要x和y符合一个就可以计算曼哈顿距离,所以每次计算只需要比较计算另一个坐标的差距,官方的这种写法也不需要像我的写法一样去好几层判断,而且在距离一样时判断下标小的操作其实是没有必要的.因为我们是顺序去比较的,只有当距离小时我们才记录这样后面距离相等时我们完全没必要管,而且一旦比较,那么他必定是距离最小并且下标最小的.

总结

这题虽然不难,但从跟官方的题解进行比较还是不难发现我的思路还是停留在最最原始的暴力法上,有很多不必要的操作代码的整体质量就明显不如官方的.不仅仅是算法还是代码质量上我都还有很长的路要走啊.

分类:

前端

标签:

数据结构与算法

作者介绍

刚睡醒的番茄
V1