百度笔试 3.22
2.包含相等0和1的最长区间
给出一个长度为n的01串，现在请你找到两个区间，使得这两个区间中0和I的个数相等。 两个区间可以相交，但是不可以完全重叠，即两个区间的左右端点不可以完全相问。 现在请你找到两个最长的区问，满足以上要求。
输入
11011
输出
1 4 2 5 //最长区间为[1,4],[2,5]
class Solution {
private static final int INF = 100005;
public int[] getIndex(String str){
int len = str.length();
int left = 0;
int right = len - 1;
int maxLen = 0;
int[] res = new int[4];
if(str.charAt(left) == str.charAt(right))
return new int[]{left + 1,right,left + 2,right + 1};
while (right > 1){
right--;
if(str.charAt(0) == str.charAt(right)){
maxLen = right;
res[0] = 1;
res[1] = right;
res[2] = 2;
res[3] = right + 1;
break;
}
}
} 3.快递耗时
牛牛是一个快递员，负责n个乡村的快递配送，乡村编号从1到n，快选站设在s号多村，牛牛将从快递站开始，依次配送q件快递到目的乡村。
乡村与乡村之间，存在着m条单向道路以及k条双向通路，已知通过每条道路所需要在费的时间，而且，任意两个乡村之间都存在至少一条通路。
每个乡村都有一个容量充足的快递柜，对于第i件快递而言，假i设到达目的乡村时用总耗时为t（包括前：i-1件快递的配送用时），如果t为奇故，牛牛就会通知收货人当面取快递（该操作耗时a个单位时间），否则牛牛就会将快递放入快递柜中（该操作耗时b个单位时间）。
不需要考虑其它任何额外因素对耗时的影响。
当这件快递安排妥当之后，即：第t+a或者第t+b时刻开始，牛牛踏上从了i件快递目的乡村前往第i+1件快递目的乡村的道路。
假设在配送路途中牛牛总是挑选的耗时最短的路径，那么，当牛牛配送完有的q件快递再回到快递站休息的总耗时是多少？
输入
3 0 3 1 1 2 3 3 2 6 1 3 9 6 3 3 1 2 3
输出
30
class Solution {
private static final int INF = 100005;
/**
* @param n 乡村数量
* @param m 单向道路数量
* @param k 双向道路数量
* @param s 快递站所在乡村编号
* @param oneRoad 单向道路代价
* @param doubleRoad 双向道路代价
* @param a 当面取件耗时
* @param b 投放快递柜耗时
* @param q 快递总数量
* @param homeNum 快递配送地点编号
* @return 所需最短时间
*/
//!可能存在重边和自环，有向图两点之间最短距离
public int sumTime(int n, int m, int k, int s, int[][] oneRoad,int[][] doubleRoad,int a,int b,int q,int[] homeNum){
int time = 0;
int station = s;
int index = s;//快递员目前所在位置
int[][] graph = buildGraph(oneRoad, doubleRoad, n);
int[][] dist = getDist(graph,n);
for (int num : homeNum){
int roadWeight = dist[index][num];
if(index == num)
roadWeight = 0;
time += roadWeight;
if(time % 2 == 1)
time += a;
else
time += b;
index = num;
}
time += dist[index][station];
return time;
}
public int[][] buildGraph(int[][] oneRoad, int[][] doubleRoad, int n){//创建图
int[][] graph = new int[n + 1][n + 1];
for (int i = 0; i < n + 1; i++) {
Arrays.fill(graph[i],INF);
}
for (int i = 0; i < oneRoad.length; i++) {
int from = oneRoad[i][0];
int to = oneRoad[i][1];
int weight = oneRoad[i][2];
graph[from][to] = Math.min(graph[from][to],weight);
}
for (int i = 0; i < doubleRoad.length; i++) {
int from = doubleRoad[i][0];
int to = doubleRoad[i][1];
int weight = doubleRoad[i][2];
graph[from][to] = Math.min(graph[from][to],weight);
graph[to][from] = Math.min(graph[to][from],weight);
}
return graph;
}
public int[][] getDist(int[][] matrix, int n){//计算最短路径长度
int len = n + 1;
int[][] dist = new int[len][len];
for(int i = 0; i < len; i++) {
for(int j = 0; j < len; j++) {
dist[i][j] = matrix[i][j]; //顶点 'i' 到 顶点 'j' 的路径长度为 'i' 到 'j'的权值
}
}
//计算最短路径
for(int i = 0; i < len; i++) {
for(int j = 0; j < len; j++) {
for(int k = 0; k < len; k++) {
//如果经过下标为k顶点路径比原两点间路径更短,则更新dist[j][k] 和 path[j][k]
int temp = (dist[j][i] == INF || dist[i][k] == INF) ? INF : (dist[j][i] + dist[i][k]);
if(dist[j][k] > temp) {
// 'j' 到 'k'最短路径 对应的值，为更小的一个(经过k)
dist[j][k] = temp;
}
}
}
}
return dist;
}
}