百度笔试 3.22

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件快递目的乡村的道路。

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;
    }


}