首页 > 其他分享 >十六 1402. 星空之夜 (哈希表)

十六 1402. 星空之夜 (哈希表)

时间:2024-03-26 15:47:14浏览次数:23  
标签:星空 int double private char ++ static 哈希 1402

1402. 星空之夜 (哈希表)
image

思路:整体方法就是使用DFS找出所有星群,难点是判断星群是否相似,这里是通过累加星群内每两点之间的距离作为哈希值判断是否相似。

import java.util.*;

public class Main {
    private static final double eps = 1e-8;
    private static int W, H;
    private static char[][] g;
    private static int top = 0, cnt = 0;
    private static int[][] q = new int[160][2];
    private static double[] hashVal = new double[30];
    
    private static void dfs(int a, int b) {
        q[top++] = new int[]{a, b};
        g[a][b] = '0';
        for (int x = a - 1; x <= a + 1; x++) {
            for (int y = b - 1; y <= b + 1; y++) {
                if (x >= 0 && x < H && y >= 0 && y < W && g[x][y] == '1') {
                    dfs(x, y);
                }
            }
        }
    }
    
    private static double getDist(int[] a, int[] b) {
        double dx = a[0] - b[0];
        double dy = a[1] - b[1];
        return Math.sqrt(dx * dx + dy * dy);
    }
    
    private static double getHashVal() {
        double sum = 0;
        for (int i = 0; i < top; i++) {
            for (int j = 0; j < i; j++) {
                sum += getDist(q[i], q[j]);
            }
        }
        return sum;
    }
    
    private static char getId() {
        double val = getHashVal();
        for (int i = 0; i < cnt; i++) {
            if (Math.abs(hashVal[i] - val) < eps) {
                return (char)('a' + i);
            }
        }
        hashVal[cnt++] = val;
        return (char)('a' + cnt - 1);
    }
    
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        W = sc.nextInt();
        H = sc.nextInt();
        g = new char[H][W];
        sc.nextLine();
        for (int i = 0; i < H; i++) {
            g[i] = sc.nextLine().toCharArray();
        }
        
        for(int i = 0; i < H; i++) {
            for (int j = 0; j < W; j++) {
                if (g[i][j] == '1') {
                    top = 0;
                    dfs(i, j);
                    char id = getId();
                    for (int k = 0; k < top; k++) {
                        g[q[k][0]][q[k][1]] = id;
                    }
                }
            }
        }
        
        for (int i = 0; i < H; i++) {
            for (int j = 0; j < W; j++) {
                System.out.print(g[i][j]);
            }
            System.out.println();
        }
    }
}

标签:星空,int,double,private,char,++,static,哈希,1402
From: https://www.cnblogs.com/he0707/p/18096804/lanqiaobei16

相关文章

  • 数据结构-哈希表-007
    1哈希表-通讯录1.1哈希结点结构体定义/*=====自定义数据类型=====*/typedefstructperson_information{charname[32];charsex;intage;chartel[32];charaddr[64];}DATA_TYPE;/*=====定义一个哈希数据结点=====*/typedefstructhash_......
  • 代码随想录第六天: 哈希表(数组+HashSet+HashMap)
    语言:Java参考资料:代码随想录、ChatGPT3.5当我们遇到了要快速判断一个元素是否出现集合里的时候,就要考虑哈希法。但是哈希法也是牺牲了空间换取了时间,因为我们要使用额外的数组,set或者是map来存放数据,才能实现快速的查找。如果在做面试题目的时候遇到需要判断一个......
  • 蓝桥杯算法集训 - Week 4:BFS、并查集、Flood Fill、哈希、单调栈/队列
    蓝桥杯算法集训-Week4本系列随笔用于整理AcWing题单——《蓝桥杯集训·每日一题2024》的系列题型及其对应的算法模板。一、BFSBFS算法复习参考:BFS(Java)广度优先搜索简单介绍、模板、案例(一)Ⅰ、代码模板staticvoidbfs(Troot){//双端队列,用来存储元素D......
  • 06天【代码随想录算法训练营34期】 第三章 哈希表part01(● 242.有效的字母异位词 ●
    242.有效的字母异位词思路:26位的array,每个分别对应a,b,c...,z,如果遇到一个字母就++,如果两个array一样则为anagramhint:toinitiateanarraywithnelementscarryingvalue0:arr=[]arr=[0foriinrange(n)]print(arr)classSolution:defisAnagram(self,......
  • 数据结构(十)哈希表---以题为例
    模拟散列表维护一个集合,支持如下几种操作:Ix,插入一个整数 x;Qx,询问整数 x是否在集合中出现过;现在要进行 N 次操作,对于每个询问操作输出对应的结果。输入格式第一行包含整数 N,表示操作数量。接下来 N 行,每行包含一个操作指令,操作指令为 Ix,Qx 中的一种。输出格......
  • 哈希表及其实现
    哈希概念        顺序结构以及平衡树中,元素关键码与其存储位置之间没有对应的关系,因此在查找一个元素时,必须要经过关键码的多次比较。顺序查找时间复杂度为O(N),平衡树中为树的高度,即O(log2N),搜索的效率取决于搜索过程中元素的比较次数。        哈希方法:可......
  • 基于Python3的数据结构与算法 - 17 哈希表
    一、哈希表哈希表是一个通过哈希函数来计算数据存储位置的数据结构,通常支持如下操作:insert(key,value):插入键值对(key,value)。get(key):如果存在键值对为key的键值对则返回其value,否则返回空值。delete(key):删除键为key的键值对。1.直接寻址法当关键字的全域U比较小......
  • 星空组网:多种场景,一网打尽,开启无缝互联新纪元
    在数字化飞速发展的今天,网络连接的多样性和灵活性成为了我们日常生活和工作中不可或缺的需求。星空组网,作为新一代的网络互联平台,以其独特的云虚拟局域网与SD-WAN智能组网技术,实现了多种场景下的无缝网络连接,为用户带来了前所未有的便捷体验。无论是远程办公、在线教育,还是跨......
  • 洛谷题单指南-集合-P3370 【模板】字符串哈希
    原题链接:https://www.luogu.com.cn/problem/P3370题意解读:本题要求理解哈希的原理,自行建立哈希表解题,如果直接使用map,就不推荐。解题思路:先介绍哈希的原理1、什么是哈希?什么是哈希表?先从一个问题出发:给定不超过105个整数(取值1~109),要统计不重复整数的数量。首先,如果取值范围......
  • 哈希技术解析:从哈希函数到哈希桶迭代器的全面指南
    文章目录引言一、哈希表与哈希函数1、哈希表的基本原理2、哈希函数的作用与特点3、哈希冲突的处理方法二、哈希桶及其迭代器1、哈希桶a.定义哈希桶结构b.哈希函数c.哈希桶的插入、查找、删除2、哈希桶的迭代器a.类型定义与成员变量b.构造函数c.解引用与比较操作d.递......