wordpress整站搬家,人力管理系统,门户设计模板,百度经验悬赏令通过万岁#xff01;#xff01;#xff01;
题目#xff1a;给你一个n*2的数组#xff0c;然后第i行表示第i个点的坐标#xff0c;然后还给你了一个字符串s#xff0c;s[i]则表示第i个点的名称。然后让你找一个中心是#xff08;0,0#xff09;的正方形#xff0c;…通过万岁
题目给你一个n*2的数组然后第i行表示第i个点的坐标然后还给你了一个字符串ss[i]则表示第i个点的名称。然后让你找一个中心是0,0的正方形正方形中尽可能包含多的点但是里面的点的名称不能重复。即所有的点不存在s[i]s[j]的情况。思路下面的点我们先都以第一象限来考虑然后写代码的时候加个绝对值就好了。首先是构建一个map然后key是名称value是点的list。如果list的长度大于1就对list进行排序排序的规则就是坐标轴x或者y最大的那个点在后面即切比雪夫距离也就是max(|x|,|y|)。然后我们找正方形边长的一半这里叫他minWidth就好了因为这个list的长度大于1我们要让正方形尽可能的大list是排序过的所以不包含第二点暂记为a,b就好了也就是minWidthmax(a,b)-1但是minWidth还要与之前的minWidth取最小值所以最终公式为minWidthmax(minWidth,max(a,b)-1)。拿到宽度以后我们再遍历map然后记录有多少个点再minWidth的范围之内就好了。进阶思路我的代码时间复杂度有点高因为涉及到了排序。然后我看了下网上大佬们的思路其实不用排序的我们只需要遍历字符串找到s[i]的这些点中第二小的切比雪夫距离。技巧排序
java代码
class Solution {public int maxPointsInsideSquare(int[][] points, String s) {MapCharacter, Listint[] map new HashMap();for (int i 0; i s.length(); i) {Listint[] list map.getOrDefault(s.charAt(i), new ArrayList());list.add(points[i]);map.put(s.charAt(i), list);}// 对list进行排序int minWidth Integer.MAX_VALUE;for (Map.EntryCharacter, Listint[] entry : map.entrySet()) {Listint[] value entry.getValue();if (value.size() 2) {// 坐标最大的那个放在后面value.sort(Comparator.comparingInt(o - Math.max(Math.abs(o[0]), Math.abs(o[1]))));// 获取第二个点int[] point value.get(1);// 不能包含第二个点minWidth Math.min(minWidth, Math.max(Math.abs(point[0]), Math.abs(point[1])) - 1);}}int ret 0;for (Map.EntryCharacter, Listint[] entry : map.entrySet()) {Listint[] value entry.getValue();int[] point value.getFirst();if (Math.abs(point[0]) minWidth Math.abs(point[1]) minWidth) {ret;}}return ret;}
}java代码——进阶
class Solution {public int maxPointsInsideSquare(int[][] points, String s) {MapCharacter, Integer map new HashMap();// 正方形的宽度的一半int minWidth Integer.MAX_VALUE;for (int i 0; i s.length(); i) {int temp Math.max(Math.abs(points[i][0]), Math.abs(points[i][1]));// s[i]的宽度Integer siWidth map.getOrDefault(s.charAt(i), Integer.MAX_VALUE);if (temp siWidth) {// 因为已经有比siWidth小的点了siWidth可能是第二小的点minWidth Math.min(minWidth, siWidth);// 当前这个点的坐标会更小我们要保留这个点map.put(s.charAt(i), temp);} else if (temp minWidth) {// temp这个可能是不是s[i]中更小的但是他比minWidth小minWidth temp;}}int ret 0;for (Map.EntryCharacter, Integer entry : map.entrySet()) {if (entry.getValue() minWidth) {ret;}}return ret;}
}总结题目还是有点难度的主要是这里的切比雪夫距离。
