【题目】

给定一个路径数组 paths，表示一张图。paths[i]==j 代表城市 i 连向城市 j，如果 paths[i]==i， 则表示 i 城市是首都，一张图里只会有一个首都且图中除首都指向自己之 外不会有环。 例如， paths=[9,1,4,9,0,4,8,9,0,1]， 由数组表示的图可以知道，城市 1 是首都，所以距离为 0，离首都距离为 1 的城市只有城 市 9，离首都距离为 2 的城市有城市 0、3 和 7，离首都距离为 3 的城市有城市 4 和 8， 离首都 距离为 4 的城市有城市 2、5 和 6。所以距离为 0 的城市有 1 座，距离为 1 的 城市有 1 座，距离 为 2 的城市有 3 座，距离为 3 的城市有 2 座，距离为 4 的城市有 3 座。

那么统计数组为nums=[1,1,3,2,3,0,0,0,0,0]，nums[i]==j 代表距离为 i 的城市有 j 座。

要求实现一个 void 类型的函 数，输入一个路径数组 paths，直接在原数组上调整， 使之变为 nums 数组，即 paths=[9,1,4,9,0,4,8,9,0,1]经过这个函数处理后变成 [1,1,3,2,3,0,0,0,0,0]。

【要求】 如果 paths 长度为 N，请达到时间复杂度为 O(N)，额外空间复杂度为 O(1)。

【思路】

思路：本题非常复杂。

直接在原数据上进行修改，使用start，next，last三个指针。

start记录起始城市，next记录下标i连接的path[i]城市序号，last表示之前的一个城市序号，从0位置开始，只要还没找到首都就不断以path[i]作为下标去寻找，然后记下跳转了多少次，以负数的形式将跳转数写进path[i]，因为负数可以表示当前城市到首都的路程已经被遍历过。然后就能形成一个每个位置到首都的距离的数组。

在此数组上继续执行下一个流程统计每个距离的城市数量。比如当前0位置，path[0] = -3,证明0距离首都的距离是3，先将3位置对应path值记下，再将3位置对应path置为1，

往下顺序重复执行如上操作。即可得到nums数组。

【Code】

public static void pathsToNums(int[] paths) {
        if (paths == null || paths.length == 0) {
            return;
        }
        // citiesPath -> distancesArray
        pathsToDistans(paths);

        // distancesArray -> numArray
        distansToNums(paths);
    }

    public static void pathsToDistans(int[] paths) {
        int cap = 0;
        for(int i = 0;i !=paths.length;i++)
        {
            if(path[i] == i)
                cap = i;
            else if(path[i] > -1)//当前城市到首都的路径还没被遍历过
            {
                int curI = paths[i];
                paths[i] = -1;
                int preI = i;
                while(path[curI] != curI)//如果还没找到首都一直找下去
                {
                    if(path[curI] > -1)//找路径未被遍历过的
                    {
                        int nextI = paths[curI];
                        paths[curI] = preI;
                        preI = curI;
                        curI = nextI;                        
                    }
                    else 
                        break;
                }
                int value = paths[curI] == curI ? 0:paths[curI];
                //顺着路上存的线索一步步回退
                while(paths[curI] != -1)
                {
                    int lastPreI = paths[preI];//下一个线索
                    paths[preI] = --value;//当前preI对应的path[]里的线索已经用了，所以置为到首都的距离
                    curI = preI;//当前指针
                    preI = lastPreI;//继续回退pre指针
                }
                paths[preI] = --value;
            }
        }
        paths[cap] =0; // 首都位置做特别处理
    }

    public static void distansToNums(int[] disArr) {
        for(int i = 0;i != disArr.length;i++)
        {
            int index = disArr[i];
            if(index < 0)//证明还未统计过距离首都i长度的城市数量
            {
                disArr[i] = 0;
                while(true)
                {
                    index = -index;
                    if(disArr[index] > -1)
                    {
                        disArr[index]++;
                        break;
                    }
                    else{
                        int nextIndex = disArr[index];
                        disArr[index] = i;
                        index = nextIndex;
                    }
                }
            }
        }
}

【题目】

给定两个有序数组arr1和arr2，再给定一个整数k，返回来自arr1和arr2的两个数相加和最 大的前k个，两个数必须分别来自两个数组。 【举例】 arr1=[1,2,3,4,5]，arr2=[3,5,7,9,11]，k=4。 返回数组[16,15,14,14] 【要求】 时间复杂度达到 O(klogk)

【思路】

1、设计一个新的对象结构，包含两个下标和两个下标在数组中对应的数相加的值

2、设计一个大根堆结构，按照该对象包含的值元素进行排序

3、先将两个数组的length-1下标与对应值包装成对象丢进堆里（这个对象包含的值一定是答案中最大的）

4、再出堆顶对象，丢进该对象的（length-1，length-2）和（length-2，length-1）

5、循环直到出堆顶了K个对象结束

魔改题：

一个二维数组，每行和每一列都有序，但整体无序，求数组中的前k个最小值

思路：与上面一样，只不过此时找最小值，起点为(0,0)，加入小根堆，然后把(0,1),(1,0)加入小根堆，再根据哪个点大，将该点下方和右方的点值加入小根堆，直至出了k个元素就可以了。

【Code】

public static class Node
    {
        public int index1;//arr1中的位置
        public int index2;//arr2中的位置
        public int value;//arr1[index1] + arr2[index2] 的值

        public Node(int i1,int i2,int sum)
        {
            index1 = i1;
            index2 = i2;
            value = sum;
        }
    }

    //生成大根堆的比较器
    public static class MaxHeapComp implements Comparator<Node>
    {
        @Override
        public int compare(Node o1,Node o2)
        {
            return o2.value - o1.value;
        }
    }

    public static int[] topKSum(int[] arr1,int[] arr2,int topK)
    {
        if(arr1 == null || arr2 == null || topK < 1)
        {
            return null;
        }
        topK = Math.min(topK, arr1.length * arr2.length);
        int[] res = new int[topK];
        int resIndex = 0;//已经出堆的个数
        PriorityQueue<Node> maxHeap = new PriorityQueue<>(new MaxHeapComp());
        HashSet<String> positionSet = new HashSet<String>();
        int i1 = arr1.length-1;
        int i2 = arr2.length-1;
        maxHeap.add(new Node(i1, i2, arr[i1]+arr[i2]));//先将右下角位置丢进堆
        positionSet.add(String.valueOf(i1+"_"+i2));
        while(resIndex!=topK)
        {
            Node curNode = maxHeap.poll();
            res[resIndex++] = curNode.value;
            i1 = curNode.index1;
            i2 = curNode.index2;
            //先检测该位置是否已被丢进过，不重复丢进堆里
            if(!positionSet.contains(String.valueOf((i1-1) + "_" + i2)))
            {
                positionSet.add(String.valueOf((i1-1) + "_" + i2));
                maxHeap.add(new Node(i1-1, i2, arr1[i1-1] + arr2[i2]));
            }
            if(!positionSet.contains(String.valueOf(i1 + "_" + (i2-1))))
            {
                positionSet.add(String.valueOf(i1 + "_" +(i2-1)));
                maxHeap.add(new Node(i1, i2-1, arr[i1] + arr2[i2-1]));
            }
        }
        return res;
    }

【题目】

给定三个字符串str1、str2和aim，如果aim包含且仅包含来自str1和str2的所有字符， 而且在aim中属于str1的字符之间保持原来在str1中的顺序，属于str2的字符之间保持 原来在str2中的顺序，那么称aim是str1和str2的交错组成。实现一个函数，判断aim是 否是str1和str2交错组成 【举例】 str1="AB"，str2="12"。那么"AB12"、"A1B2"、"A12B"、"1A2B"和"1AB2"等都是 str1 和 str2 的 交错组成。

【思路】

动态规划：构建一张二维表dp，dp[i][j]代表以str1从0~i的字串 + str2从0~j的字串是否能交错组合成 aim从0~i+j的字串。这张表的右下角位置dp[str1.length-1][str2.length-1]就是答案。

常规位置的求法：求两种情况其中之一为true就true

1、aim子串以str1 i-1位置结尾并且dp[i-1][j]为true

aim子串以str2 j-1位置结尾并且dp[i][j-1]为true

【Code】

public static boolean isCross(String str1,String str2,String aim)
    {
        if(str1 == null || str2 == null || aim == null)
            return false;
        char[] ch1 = str1.toCharArray();
        char[] ch2 = str2.toCharArray();
        char[] chaim =  aim.toCharArray();
        if(chaim.length != ch1.length + ch2.length)
            return false;
        //构建二维表，预留一个位置0作为当一个str为0时另一个str能单独组成aim的值
        boolean[][] dp = new boolean[ch1.length+1][ch2.length+1];
        dp[0][0] = true;//str1和str2都是"".aim以0截止是"" 自然一样

        //分别构建第一行和第一列
        for(int i = 1;i <= ch1.length;i++)
        {
            if(ch1[i-1] != chaim[i-1])//如果不相等则不用往后比对了
                break;
            dp[i][0] = true;
        }
        for(int j = 1;j<ch2.length;j++)
        {
            if(ch2[j-1] != chaim[j-1])
                break;
            dp[j][0] = true;
        }
        for(int i = 1;i <= ch1.length;i++)
        {
            for(int j = 1;j<ch2.length;j++)
            {
                if( (ch1[i-1] == chaim[i+j-1] && dp[i-1][j])
                || (ch2[j-1] == chaim[i+j-1] && dp[i][j-1]))
                {
                    dp[i][j] = true;
                }
            }
        }
        return dp[ch1.length][ch2.length];
    }