阅读量:0
解题思路：自己：先把points里的点拿来求出坐标系的离原点最远的点，然后根据最远距离新建一个数组，然后把points的点都在新建的数组上标记出来。然后再便利从边长为0的正方形开始，里面是否有重复的标签。但是代码写不出来。
class Solution { public int maxPointsInsideSquare(int[][] points, String s) { // int[] arr = new int[s.length()]; // int length = points.length; // int center = // for(int i =0 ;i<points.length;i++){ int max =0; for(int i=0;i<points.length;i++){ int max_index = Math.abs(points[i][0]) > Math.abs(points[i][1]) ? Math.abs(points[i][0]) : Math.abs(points[i][1]); int max = max_index>max?max_index:max; } int[] arr = new int[max*2+1][max*2+1]; for(int i =0 ;i<points.length;i++){ arr[points[i][0]+max][points[i][1]+max]=i+1;//通过赋值来表示第几个点 } for(int i=0;i<max;i++){ } } 看过官方提示之后：
但是运行不通过。
import java.lang.Math; class Solution { public int maxPointsInsideSquare(int[][] points, String s) { // int[] arr = new int[s.length()]; // int length = points.length; // int center = // for(int i =0 ;i<points.length;i++){ char[] s_arr = s.toCharArray(); for(int i =0;i<points.length-1;i++){ for(int j=i;j<points.length-1;j++){ if(Math.max(Math.abs(points[j][0]),Math.abs(points[j][1]))>Math.max(Math.abs(points[j+1][0]),Math.abs(points[j+1][1]))){ int[][] index = new int[1][2]; index[0] = points[j]; points[j]=points[j+1]; points[j+1]=index[0]; char index_s =s_arr[j]; s_arr[j]=s_arr[j+1]; s_arr[j+1]=index_s; } } } int re=0; for(int i=0 ;i<Math.max(Math.abs(points[points.length-1][0]),Math.abs(points[points.length-1][1]));i++){ ArrayList<Character> list = new ArrayList<>(); for(int j=0;j<points.length;j++){ if(i<Math.max(Math.abs(points[points.length-1][0]),Math.abs(points[points.length-1][1]))){ if((list.indexOf(s_arr[j]))!=-1){ return i; }else{ list.add(s_arr[j]); } }else{ break; } } } return Math.max(Math.abs(points[points.length-1][0]),Math.abs(points[points.length-1][1])); } } 他人思路：
对于一个点 (x,y)，我们可以将其映射到以原点为中心的第一象限，即 (max(∣x∣,∣y∣),max(∣x∣,∣y∣))。这样，我们就可以将所有的点映射到第一象限，然后按照点到原点的距离进行排序。我们可以使用哈希表 g 来存储所有点到原点的距离，然后按照距离进行排序。对于每个距离 d，我们将所有距离为 d 的点放在一起，然后遍历这些点，如果有两个点的标签相同，那么这个正方形是不合法的，直接返回答案。否则，我们将这些点加入到答案中。
链接：https://leetcode.cn/problems/maximum-points-inside-the-square/solutions/1/python3javacgotypescript-yi-ti-yi-jie-ha-vsvi/
class Solution { public int maxPointsInsideSquare(int[][] points, String s) { TreeMap<Integer, List<Integer>> g = new TreeMap<>(); for (int i = 0; i < points.length; ++i) { int x = points[i][0], y = points[i][1]; int key = Math.max(Math.abs(x), Math.abs(y)); g.computeIfAbsent(key, k -> new ArrayList<>()).add(i); //这段代码的作用是，如果g这个Map中不存在某个key， //则使用k -> new ArrayList<>()这个函数创建一个新的ArrayList并将其赋值给这个key； //如果key已经存在，则直接在对应的ArrayList中添加元素i。 } boolean[] vis = new boolean[26]; int ans = 0; for (var idx : g.values()) {//通过g.values()提取出来每个key对应的多个标签的在s中的位置。 for (int i : idx) {//针对idx这个key有很多标签，便利每个标签 int j = s.charAt(i) - 'a'; if (vis[j]) { return ans; } vis[j] = true; } ans += idx.size(); } return ans; } } 