前言

当前所有算法都使用测试用例运行过，但是不保证100%的测试用例，如果存在问题务必联系批评指正~

在此感谢左大神让我对算法有了新的感悟认识！

问题介绍

原问题
给定一个数组arr，其中该arr[i] = j表示区域i直接连接的区域是区域j，如下图所示:
在这里插入图片描述

其中arr[3] = 1,arr[6] = 1,arr[2] = 1,其中arr[1] = 0代表 1是首都
现在要求：
1、不使用新数组
2、时间复杂度在O（n）
3、将arr[i] = j代表的意义转换成到1的距离为i的节点数有几个，如上图 arr[1] = 3
已知：路径图不会成环并且都最终通往首都

解决方案

原问题：
1、不是用新数组，那么就只能使用arr这个入参提供的空间
2、时间复杂度控制在O(n)也就是只能最多使用一层循环，避免循环嵌套
3、解决该问题：arr需要经历2个周期转换，第一个周期转换为：将arr[i] = j 代表 i指向j 转换为 arr[i] = j 代表 i到首都的距离为j
第二个周期转换为： arr[i] = j 代表 i到首都的距离为j 转换为 arr[i] = j 代表到首都的距离为i的节点数有几个

其中转换周期1的方法：
从arr[0]开始遍历，取出arr[0]，代表下一个节点j，arr[0]是起点，所以先让arr[0]为0，之后看arr[j]，将arr[j]的下一个节点暂存后，再将arr[j]设置为0，代表j节点的上一个节点是节点0，如此往复一定会查到首都节点，此时将首都设置为0,开始往回走，每回去一个节点该节点的数值更新为上一个节点-1，直到回到起点为止。形象一点如下：
去过程：原2节点现在指向节点0，当遇到节点1时发现1是首都，次时往回走，看回过程
在这里插入图片描述
回过程：当从1回到2的时候，arr[1]为0，所以arr[2] = arr[1] - 1，最终这条路径变成负数路径

转换周期二：距离数组转统计数组
到这里arr = [-2, 0, -1, -1, -2, -2, -1]
现在开始转换成统计数组，首先不能使用多余的空间，所以我们还是需要在该数组上做转换
arr[0] = -2 说明0节点到首都的距离为2，此时判断arr[2] 是否大于0，如果小于0，说明当前位置并没有被统计过，所以暂存，改为0，然后+1。如果大于0 ，说明已经统计过，此时直接+1即可，被统计过的arr[0]此时已经统计过，但是暂时没有人距离为0（首都没遍历到），所以arr[0]变为0
一轮交换转换之后统计数组即可出现。

代码编写

java语言版本

原问题：

    /*** 二轮测试：从arr[i] = j 代表数值i的结点指向j含义转化为 arr[i]代表到首都的距离为i的结点数量* 时间复杂度O(N)，空间复杂度O(1)* @param arr* @return*/public static int[] path2NumsCp1(int[] arr) {if (arr == null) {return null;}else if (arr.length == 0) {return new int[]{0};}// 在原arr的基础上直接计算每一个点到首都的距离int cap = convertPath2Length(arr);arr = convertLength2Nums(arr, cap);return arr;}/*** 将代表path的arr转换成距离首都的距离（用负数表达）* @param arr*/private static int convertPath2Length(int[] arr) {// 记录一下首都的indexint capIndex = -1;for (int i = 0; i < arr.length; i++) {// 首先判断i是否已经计算过if (arr[i] < 0 || i == capIndex) {continue;}// 记录一下起点,标记起点为-1int cur = i;// next代表下一跳int next = arr[cur];arr[cur] = -1;while (arr[next] >= 0 && next != capIndex) {// 先判断是否是首都if (arr[next] == next) {// 首都直接返回,并且首都到首都的距离是0arr[next] = 0;capIndex = next;break;}// 需要跳跃int temValue = arr[next];// 记录回去的路arr[next] = cur;cur = next;next = temValue;}// 到这里next可能代表首都，也可能arr[next]已经计算过,cur代表着上一个节点的index// 所以从这里开始往回更新距离了while (arr[cur] != -1) {// 暂存一下下一个的位置int tem = arr[cur];// 上一个距离-1arr[cur] = arr[next] - 1;// 更新游标next = cur;cur = tem;}// 最后再更新一下arr[cur]arr[cur] = arr[next] - 1;}return capIndex;}/*** 从长度到统计数组的转换* @param arr* @return*/private static int[] convertLength2Nums(int[] arr, int cap) {for (int i = 0; i < arr.length; i ++) {if (arr[i] >= 0 && i != cap) {// 大于0的说明统计过了continue;}// 到这里的都要进行统计// 首先拿出来arr[i],取相反数才是真的lenint cur = arr[i];arr[i] = 0;boolean flag = false;while (cur <= 0) {// 当前位置距离首都的距离int len = -cur;if (arr[len] >= 0) {arr[len] ++;flag = true;break;}else {// 说明了需要循环替换int next = arr[len];// 替换arr[len] = 0;arr[len] ++;// 下一个游标cur = next;}}if (!flag) {arr[cur] ++;}}return arr;}public static void main(String[] args) {CommonUtils.printArr(path2NumsCp1(new int[]{9,1,4,9,0,4,8,9,0,1}));}

c语言版本

正在学习中

c++语言版本

正在学习中

思考感悟

这道题很考验大脑的寄存器，，，
首先记录数组的变化非常绕，不让使用多余空间时，就要在一个数组上面进行交换和更新，其中需要注意的两个点：
1、用负数处理非常巧妙的将数组当做两个数组来用
2、0这个位置和0这个值非常特殊，因为其代表首都也代表距离，容易搞混，所以需要有一个变量专门标注首都以备后面判断使用。
总之需要好好体会数组的转换，并且如果限制了空间，可以使用正负数的方式将数组进行界线分割，其次，回溯的过程也很巧妙，用于路径数组变成长度数组时使用。