起初这道题，我的思路是建立一个动态数组或者链表，每有一个新的record进来，我先判断位置再放入，但是考虑到有的record没有先验的位置信息，所以这种方法被pass了。
接着考虑新的数据结构，由于之前也刷过一些数据结构的题，这题我们已知一些钻石的重量关系，那么以每个编号的钻石为key，以小于该编号钻石重量的钻石存储的链表为value，这样每扫描到一个编号的钻石就能直观的知道有哪些钻石重量小于它。
初始版本1（能通过AC，但是实际上还是没考虑到所有情况）：
import java.util.*;
public class Cmp {
public int cmp(int g1, int g2, int[][] records, int n) {
// write code here
HashMap<Integer, ArrayList<Integer>> map = new HashMap<Integer, ArrayList<Integer>>();
for(int i = 0; i < 100; ++i)
map.put(i + 1, new ArrayList<Integer>());
for(int i = 0; i < records.length; ++i){
int key = records[i][0];
int value = records[i][1];
ArrayList<Integer> list = map.get(key);
list.add(value);
map.put(key, list);
}
ArrayList<Integer> list1 = map.get(g1);
ArrayList<Integer> list2 = map.get(g2);
/*
考虑g1>g2的情况，扫描key为g1的list，如果存在value==g2，就直接返回1；如果key为g1的list的子list中的value==g2，也返回1
*/
for(int i = 0; i < list1.size(); ++i){
int key = list1.get(i);
if(key == g2 || map.get(key).contains(g2)){
return 1;
}
}
/*
考虑g2>g1的情况，扫描key为g2的list，如果存在value==g1，就直接返回-1；如果key为g2的list的子list中的value==g1，也返回-1
*/
for(int i = 0; i < list2.size(); ++i){
int key = list2.get(i);
if(key == g1 || map.get(key).contains(g1)){
return -1;
}
}
return 0;
}
}修改版本2（本地可以AC，但在平台上会报错）：
import java.util.*;
public class Cmp {
public boolean isFound = false;
public int cmp(int g1, int g2, int[][] records, int n) {
// write code here
HashMap<Integer, ArrayList<Integer>> map = new HashMap<Integer, ArrayList<Integer>>();
for (int i = 0; i < n; i++) {
int key = records[i][0];
int value = records[i][1];
if (map.containsKey(key)) {
map.get(key).add(value);
} else {
ArrayList<Integer> list = new ArrayList<>();
list.add(value);
map.put(key, list);
}
}
if(map.isEmpty())
return 0;
findRelation(g1, g2, map);
if(isFound)
return 1;
findRelation(g2, g1, map);
if(isFound)
return -1;
return 0;
}
public void findRelation(int g1, int g2, HashMap<Integer, ArrayList<Integer>> map){
if(!map.containsKey(g1)){
isFound = false;
}
else{
ArrayList<Integer> list = map.get(g1);
for(int value : list){
if(value == g2){
isFound = true;
return;
}
else{
findRelation(value, g2, map);
}
}
}
}
}这是对版本1的改进，但是由于可能存在循环，所以一直会报错，还没有解决，有大佬可以帮忙看看。
![图片说明]
(https://uploadfiles.nowcoder.com/images/20201225/231587798_1608879258581/475FE358B19CBF83051568DE361DE158 "图片标题")
这道题首先梳理思路，首先要找到权值最大的叶节点和权值最小的叶节点，然后要找到一条路径使两个节点之间的路径长度最短，而对于一棵树而言，就是需要求出两个节点的最近公共祖先。
对于树的题最好的地方就是可以递归。（这里代码参考了其他大佬的）
import java.util.*;
/*
public class TreeNode {
int val = 0;
TreeNode left = null;
TreeNode right = null;
public TreeNode(int val) {
this.val = val;
}
}*/
public class Tree {
private TreeNode maxNode = new TreeNode(Integer.MIN_VALUE);
private TreeNode minNode = new TreeNode(Integer.MAX_VALUE);
public int getDis(TreeNode root) {
// write code here
getMaxMin(root);//找到最大最小叶子节点
TreeNode lcaNode = getLCA(root);//找LCA
int a = getNodeDis(lcaNode, maxNode);//最大值叶子节点到LCA的距离；
int b = getNodeDis(lcaNode, minNode);//最小值叶子节点到LCA的距离；
return a+b;
}
// 先找到最大最小叶子节点
public void getMaxMin(TreeNode root) {
if (root == null) {
return;
}
if (root.left == null && root.right == null) {
if (root.val > maxNode.val) {
maxNode = root;
} else if (root.val < minNode.val) {
minNode = root;
}
}
getMaxMin(root.left);
getMaxMin(root.right);
}
// LCA最近公共祖先
public TreeNode getLCA(TreeNode root) {
if (root == null) {// 说明是空树
return null;
}
if (root.val == maxNode.val || root.val == minNode.val) {// 在当前树的根节点上找到两个节点之一
return root;
}
TreeNode leftNode = getLCA(root.left);// 左子树中的查找两个节点并返回查找结果
TreeNode rightNode = getLCA(root.right);// 右子树中查找两个节点并返回查找结果
if (leftNode == null) {// 左子树中没找到，则一定在右子树上
return rightNode;
} else if (rightNode == null) {// 右子树没找到一定在左子树上
return leftNode;
} else {// 左右子树均找到一个节点，则根节点为最近公共祖先
return root;
}
}
//获取叶子节点到LCA距离
public int getNodeDis(TreeNode lcaNode, TreeNode node){
if(lcaNode==null){
return -1;
}
if(lcaNode.val==node.val){
return 0;
}
//三种情况：两个均在左子树；两个均在右子树；一左一右，所以不能用if-elseif结构
int distance = getNodeDis(lcaNode.left, node);//左子树未找到两个节点之一
if(distance==-1){
distance = getNodeDis(lcaNode.right, node);
}
if(distance!=-1){
return distance+1;
}
return -1;
}
}
之前一直觉得求topK问题就考虑堆排序，现在意识到快排也可以。
快排就是利用某一个数作为基准点进行分区，通常来说基准点左边的数都小于基准点，基准点右边的数都大于基准点。这样来看，不难发现，K的值和基准点的下标有关。
import java.util.*;
public class Finder {
public int findKth(int[] a, int n, int K) {
// write code here
int left = 0;
int right = n - 1;
int p = -1;//p保存的是基准点在一次调整后的下标，由于下标和K是差一的关系，所以这里初始化为-1，而出口是比较K与p+1
while(K != p + 1){
//如果K比当前下标+1大，说明需要求的数在该下标后边
if(K > p + 1)
left = p + 1;
//如果K比当前下标+1小，说明需要求的数在该下标前边
else if(K < p + 1)
right = p - 1;
p = partition(a, left, right);
}
return a[p];
}
//类似快排，以最右边的数作为阈值，然后从最左边开始替换值
public int partition(int[] a, int left, int right){
int pivot = a[right];
int sortIndex = left;
for(int aIndex = sortIndex; aIndex < right; ++aIndex){
if(a[aIndex] > pivot){
swap(a, aIndex, sortIndex);
sortIndex++;
}
}
swap(a, sortIndex, right);
return sortIndex;
}
//进行数组中的两个数的交换
public void swap(int[] a, int i, int j){
if(i == j) return;
int temp = a[i];
a[i] = a[j];
a[j] = temp;
}
}
京公网安备 11010502036488号