1、压缩字符串 -- 100%
比如“aaabbbcaaa” ,压缩成“a3b3c1a3”;
如果压缩后的长度不是小于等于原字符串长度,就返回原字符串
2、上下反转二维数组 -- 100%
比如
{[1,2,3],[4,5,6] ,[7,8,9]}
反转后为{[7,8,9],[4,5,6],[1,2,3]}
3、现在给定所有的城市和航班,以及出发城市src,你的任务是找到从 scr城市出发到其他所有城市最便宜的机票价格列表。 假设两个城市之间机票价格不会超过Integer.MAX_VALUE -- 100%
public static int[] findAllCheapestPrice(int n, int[][] flights, int src) { int[][] g = new int[n + 10][n + 10]; int[] dis = new int[n]; boolean[] st = new boolean[n + 10]; for (int i = 0; i < n; i++) { Arrays.fill(g[i], 0x3f3f3f3f); } for (int i = 0; i < flights.length; i++) { int a = flights[i][0]; int b = flights[i][1]; int c = flights[i][2]; g[a][b] = Math.min(g[a][b], c); } dijkstra(g, dis, st, src, n); for (int i = 0; i < dis.length; i ++) { if(dis[i] == 0x3f3f3f3f){ dis[i] = -1; } } return dis; } public static void dijkstra(int[][] g, int[] dis, boolean[] st, int start, int n) { Arrays.fill(dis, 0x3f3f3f3f); dis[start] = 0; for (int i = 0; i < n; i++) { int t = -1; for (int j = 0; j < n; j++) { if (!st[j] && (t == -1 || dis[t] > dis[j])) { t = j; } } st[t] = true; for (int j = 0; j < n; j++) { dis[j] = Math.min(dis[j], dis[t] + g[t][j]); } } }
全部评论
(0) 回帖