【题目】
给定一个路径数组 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];
}