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) 回帖