解释以下这段代码并说出他的计算复杂度import java.util.*; public class 1806 { static int n; static int[] t = new int[10]; static int[] telegraph = new int[50005]; static int[] dis = new int[50005]; static int[] pre = new int[50005]; static boolean[] vis = new boolean[50005]; static ArrayList<Integer> path = new ArrayList<Integer>(); public static void main(String[] args) { Scanner sc = new Scanner(System.in); n = sc.nextInt(); for (int i = 0; i < 10; i++) { t[i] = sc.nextInt(); } for (int i = 1; i <= n; i++) { telegraph[i] = sc.nextInt(); } dijkstra(1); if (dis[n] == Integer.MAX_VALUE) { System.out.println("-1"); } else { System.out.println(dis[n]); getPath(n); System.out.println(path.size()); for (int i = 0; i < path.size(); i++) { System.out.print(path.get(i) + " "); } } } private static void dijkstra(int s) { Arrays.fill(dis, Integer.MAX_VALUE); dis[s] = 0; for (int i = 1; i <= n; i++) { pre[i] = i; } for (int k = 0; k < n; k++) { int u = -1; int minDis = Integer.MAX_VALUE; for (int i = 1; i <= n; i++) { if (!vis[i] && dis[i] < minDis) { u = i; minDis = dis[i]; } } if (u == -1) { break; } vis[u] = true; for (int i = 1; i <= n; i++) { if (!vis[i]) { int w = getWeight(telegraph[u], telegraph[i]); if (dis[u] + w < dis[i]) { dis[i] = dis[u] + w; pre[i] = u; } } } } } private static int getWeight(int a, int b) { int weight = 0; String s1 = String.valueOf(a); String s2 = String.valueOf(b); int len = Math.min(s1.length(), s2.length()); for (int i = 0; i < len; i++) { if (s1.charAt(i) != s2.charAt(i)) { weight = t[i]; break; } } return weight; } private static void getPath(int u) { if (u != 1) { getPath(pre[u]); } path.add(u); } }
时间: 2024-04-27 21:23:40 浏览: 13
这段代码实现了一个基于Dijkstra算法的最短路径问题。其中,telegraph数组存储了n个节点的电报号码,t数组存储了电报号码每一位的开销,dis数组存储了每个节点到源节点的最短距离,pre数组存储了每个节点的前驱节点,vis数组表示每个节点是否已经被访问过。getPath方法用来获取从源节点到目标节点的最短路径,path存储了路径上的所有节点。
计算复杂度为O(n^2),因为算法中有两个循环嵌套。其中,第一个循环是n次的,第二个循环最多也是n次的,所以总共的时间复杂度为O(n^2)。
相关问题
import java.util.Arrays; import java.util.Scanner; public class 1726 { public static void main(String[] args) { Scanner sc = new Scanner(System.in); int n = sc.nextInt(); int[]x=new int[n]; int[]y=new int[n]; for (int i = 0; i < n; i++) { x[i]=sc.nextInt(); y[i]=sc.nextInt(); } Arrays.sort(x); Arrays.sort(y); long sum=0; long temp; for (int i = 0; i < n-1; i++) { temp=(x[i+1]-x[i]+y[i+1]-y[i]); temp*=i+1; temp*=n-i-1; sum+=temp*2; } long result=sum/n/(n-1); System.out.println(result); } }解释这段代码并说出他的计算复杂度
这段代码实现的功能是计算平面上n个点两两之间的曼哈顿距离的平均值。其中,曼哈顿距离指两点在一个矩形网格中沿网格线行走的距离。
代码中首先通过Scanner读入n个点的坐标,并分别将所有点的x坐标和y坐标分别存储在x数组和y数组中。然后分别对x数组和y数组进行排序,以方便后续的计算。接着,通过两层循环遍历所有点对,计算出每对点之间的曼哈顿距离,并将每对点的贡献乘上该点在所有点中的排名和剩余点数的乘积,最终将所有点对的贡献相加得到总和sum。最后,将sum除以n*(n-1)即可得到所求的平均值。
代码的时间复杂度为O(nlogn+n^2),其中排序的时间复杂度为O(nlogn),计算曼哈顿距离的时间复杂度为O(n^2),因此总的时间复杂度为O(nlogn+n^2)。
import java.util.ArrayList; import java.util.Arrays; import java.util.Scanner; public class 1322 { public static void main(String[] args) { Scanner sc = new Scanner(System.in); int n = sc.nextInt(); String str = sc.next(); char []chars=str.toCharArray(); char []result=spy(n,chars); System.out.println(result); } public static char[] spy(int n,char[] chars){ int len=chars.length; ArrayList<Integer>[] ch = new ArrayList[128]; for (int i = 0; i < 128; i++) { ch[i] = new ArrayList<Integer>(); } for (int i = 0; i < chars.length; i++) { ch[chars[i]].add(i); } int[]next=new int[len]; int count=0; for (int i = 0; i < 128; i++) { for (int num : ch[i]) { next[count++]=num; } } char[] result=new char[len]; int index=n-1; for (int i = 0; i < len; i++) { result[i] = chars[index=next[index]]; } return result; } }解释这段代码并说出他的计算复杂度
这段代码实现了一种加密算法,输入一个整数n和一个字符串str,输出将str按照一定规则加密后的结果。具体实现是将字符串中的每个字符按照ASCII码值存储在一个ArrayList数组中,然后按照存储顺序重新排列,最后按照一定规则依次取出字符形成加密后的结果。
计算复杂度:
1. 输入和初始化操作的时间复杂度为O(1)。
2. 将字符串中的每个字符按照ASCII码值存储在ArrayList数组中,时间复杂度为O(n)。
3. 将存储在ArrayList数组中的字符重新排列,时间复杂度为O(n)。
4. 依次取出字符形成加密后的结果,时间复杂度为O(n)。
综上,该算法的时间复杂度为O(n)。
相关推荐
![docx](https://img-home.csdnimg.cn/images/20210720083331.png)
![docx](https://img-home.csdnimg.cn/images/20210720083331.png)
![docx](https://img-home.csdnimg.cn/images/20210720083331.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)