3.22 百度笔试B
A了 1 2，第三题超时只通过16%
第一题 放大图像
import java.util.Scanner;
public class Baidu_01 {
public static void main(String[] args) {
Scanner in = new Scanner(System.in);
int n = in.nextInt();
int k=in.nextInt();
int[][] originImage=new int[n][n];
for(int i=0;i<n;i++){
for(int j=0;j<n;j++){
originImage[i][j]=in.nextInt();
}
}
largerImage(originImage,k);
}
public static void largerImage(int[][] original,int k){
int n=original.length;
int newLength=n*k;
for(int i=0;i<newLength;i++){
for(int j=0;j<newLength;j++){
if(j==newLength-1){
System.out.print(original[i / k][j / k]);
System.out.println();
}
else{
System.out.print(original[i / k][j / k]+" ");
}
}
}
}
} 第二题 最长的字串 import java.util.Scanner;
public class Baidu_02 {
public static void main(String[] args) {
Scanner in = new Scanner(System.in);
String s = in.nextLine();
int begin=0,end=s.length()-1;
int[] longSubLeft;
int[] longSubRight;
while(s.charAt(begin)!=s.charAt(end)) begin++;
longSubLeft=new int[]{begin,end-1,begin+1,end};
begin=0;end=s.length()-1;
while(s.charAt(begin)!=s.charAt(end)) end--;
longSubRight=new int[]{begin,end-1,begin+1,end};
int[] ret=longSubLeft[1]-longSubLeft[0]>=longSubRight[1]-longSubRight[0]?longSubLeft:longSubRight;
for (int i = 0; i < 4; i++) ret[i]++;
System.out.print(ret[0] + " " + ret[1] + " " + ret[2] + " " + ret[3]);
}
} 第三题 用的floyd算法求得个节点最短路径 时间复杂度到了n^3 所以超时了 求大佬讲讲更简单的思路 import java.util.Arrays;
import java.util.Scanner;
public class Baidu_03 {
public static void main(String[] args) {
Scanner in = new Scanner(System.in);
int n = in.nextInt();//乡村数量
int m = in.nextInt();//单向道路数量
int k = in.nextInt();//双向道路数量
int s = in.nextInt() - 1;//快递站所在编号
int[][] singlePathLoad = new int[m][3];
int[][] doublePathLoad = new int[k][3];
for (int i = 0; i < m; i++) {
for (int j = 0; j < 3; j++) singlePathLoad[i][j] = in.nextInt();
}
for (int i = 0; i < k; i++) {
for (int j = 0; j < 3; j++) doublePathLoad[i][j] = in.nextInt();
}
int a = in.nextInt();//当面取件耗时，t为奇数
int b = in.nextInt();//快递柜耗时,t为偶数
int q = in.nextInt();//快递数量
int[] bags = new int[q];
for (int i = 0; i < q; i++) bags[i] = in.nextInt() - 1;
int[][] minPath = prim(singlePathLoad, doublePathLoad, n);
System.out.println(timeNeeded(minPath, a, b, bags, s));
}
public static int timeNeeded(int[][] path, int a, int b, int[] bags, int s) {
int from = s;
int time = 0;
int cost;
for (int i = 0; i < bags.length; i++) {
int to = bags[i];
cost = path[from][to];
time += cost;
if (time % 2 == 0) time += b;
else time += a;
from = to;
}
time += path[from][s];
return time;
}
public static int[][] prim(int[][] singlePath, int[][] doublePath, int n) {
int[][] path = new int[n][n];
for (int[] Spath : singlePath) {
int from = Spath[0] - 1, to = Spath[1] - 1, weight = Spath[2];
if (from != to && path[from][to] == 0) {
path[from][to] = weight;
}
if (path[from][to] > weight) path[from][to] = weight;
}
for (int[] Dpath : doublePath) {
int dist1 = Dpath[0] - 1, dist2 = Dpath[1] - 1, weight = Dpath[2];
if (dist1 != dist2) {
if (path[dist1][dist2] == 0 || path[dist1][dist2] > weight) path[dist1][dist2] = weight;
if (path[dist2][dist1] == 0 || path[dist2][dist1] > weight) path[dist2][dist1] = weight;
}
}
for (int i = 0; i < n; i++) {
for (int j = 0; j < n; j++) {
if (i == j) continue;
else if (path[i][j] == 0) path[i][j] = 100000;
}
}
for (int i = 0; i < n; i++) {
for (int j = 0; j < n; j++) {
if (i == j) continue;
for (int k = 0; k < n; k++) {
if (k == j || k == i) continue;
path[j][k] = Math.min(path[j][k], path[j][i] + path[i][k]);
}
}
}
return path;
}
}
