本文首发于稀土掘金。该平台的作者 逐光而行 也是本人。
前言
几个星期没打周赛，手感生疏了好多，果然算法题还是得勤加练习，多找适应比赛的感觉。
同时，第二、三题都是图和树相关的内容，像我这种对这个专题还不熟的也可以借此机会巩固一下。
数组中不等三元组的数目
给你一个下标从 0 开始的正整数数组
nums。请你找出并统计满足下述条件的三元组(i, j, k)的数目：
0 <= i < j < k < nums.length
nums[i]、nums[j]和nums[k]两两不同 。
- 换句话说：
nums[i] != nums[j]、nums[i] != nums[k]且nums[j] != nums[k]。返回满足上述条件三元组的数目 。
这题直接三重for循环暴力求解是最直接的方式，我周赛时也是这么用的。
class Solution {
public int unequalTriplets(int[] nums) {
//三重循环暴力破解
int cnt=0;
int n=nums.length;
for(int i=0;i<n;i++){
for(int j=i+1;j<n;j++){
for(int k=j+1;k<n;k++){
if(nums[i] != nums[j]&&nums[i] != nums[k]&&nums[k] != nums[j]) cnt++;
}
}
}
return cnt;
}
}上述解法的时间复杂度是O(N^3)。
有一种能把时间复杂度降到O(N)的方法（排序后用下标规律找）
class Solution {
public int unequalTriplets(int[] nums) {
Arrays.sort(nums);
int ans = 0, start = 0, n = nums.length;
for (int i = 0; i < n - 1; i++) {
if (nums[i + 1] != nums[i]) {
ans += start * (i - start + 1) * (n - 1 - i);
start = i + 1;
}
}
return ans;
}
}二叉搜索树最近结点查询
给你一个 二叉搜索树 的根节点
root，和一个由正整数组成、长度为n的数组queries。请你找出一个长度为
n的 二维 答案数组answer，其中answer[i] = [mini, maxi]：
mini是树中小于等于queries[i]的 最大值 。如果不存在这样的值，则使用-1代替。maxi是树中大于等于queries[i]的 最小值 。如果不存在这样的值，则使用-1代替。返回数组
answer。
我竞赛时的做法是：得到树的中序遍历数组inor；对于目标数组内的每一个元素，尝试从inor中确认它的左右边界。这个方法总是卡在某些测试样例。
注释掉的是尝试的第一种方法，没注释的是第二种方法。它们有一个共同的特点：
if else太多了，没能准确找出左右边界，且通用性不强，这些语句之间稍微变换一下位置结果就又不同。
所以无论怎么调它都很难调好，只能换种思路寻找突破。
/**
* Definition for a binary tree node.
* public class TreeNode {
* int val;
* TreeNode left;
* TreeNode right;
* TreeNode() {}
* TreeNode(int val) { this.val = val; }
* TreeNode(int val, TreeNode left, TreeNode right) {
* this.val = val;
* this.left = left;
* this.right = right;
* }
* }
*/
class Solution {
List<Integer> inor;
public List<List<Integer>> closestNodes(TreeNode root, List<Integer> queries) {
//按中序遍历BST可得到一个升序数组
inor=new ArrayList<>();
inorder(root);
int m=inor.size();
List<List<Integer>> res=new ArrayList<>();
int n=queries.size();
for(int i=0;i<n;i++){
List<Integer> tmp=new ArrayList<>();
for(int j=0;j<m;j++){
// //特殊情况
// if(queries.get(i)<inor.get(0)){
// tmp.add(-1);
// tmp.add(inor.get(0));
// break;
// }
// else if(queries.get(i)>inor.get(m-1)){
// tmp.add(inor.get(m-1));
// tmp.add(-1);
// break;
// }
// else if(queries.get(i)==inor.get(j)){
// tmp.add(inor.get(j));
// tmp.add(inor.get(j));
// break;
// }
// else{
// if(queries.get(i)>inor.get(j)&&queries.get(i)<inor.get(j+1)){
// tmp.add(inor.get(j));
// tmp.add(inor.get(j+1));
// break;
// }
// }
if(queries.get(i)==inor.get(j)){
tmp.add(inor.get(j));
tmp.add(inor.get(j));
break;
}
else if(queries.get(i)<inor.get(j)){
if(j-1>=0){
tmp.add(inor.get(j-1));
}
else{
tmp.add(-1);
}
tmp.add(inor.get(j));
break;
}
else if(j==m-1){
tmp.add(inor.get(m-1));
tmp.add(-1);
break;
}
else if(queries.get(i)>inor.get(j)) continue;
}
res.add(tmp);
}
return res;
}
public void inorder(TreeNode root){
if(root==null) return ;
inorder(root.left);
inor.add(root.val);
inorder(root.right);
}
}赛后看到一位大佬的题解，用的是TreeSet,突然感觉这个数据结构正好符合我的设想！
所以我又自己写了一遍。
/**
* Definition for a binary tree node.
* public class TreeNode {
* int val;
* TreeNode left;
* TreeNode right;
* TreeNode() {}
* TreeNode(int val) { this.val = val; }
* TreeNode(int val, TreeNode left, TreeNode right) {
* this.val = val;
* this.left = left;
* this.right = right;
* }
* }
*/
class Solution {
TreeSet<Integer> nums;
int n,m;
public List<List<Integer>> closestNodes(TreeNode root, List<Integer> queries) {
nums=new TreeSet<>();
inorder(root);
n=queries.size();
m=nums.size();
List<List<Integer>> res=new ArrayList<>();
for(int i=0;i<n;i++){
int q=queries.get(i);
Integer a=nums.floor(q);
Integer b=nums.ceiling(q);
List<Integer> tmp=new ArrayList<>();
if(a==null) tmp.add(-1);
else tmp.add(a);
if(b==null) tmp.add(-1);
else tmp.add(b);
res.add(tmp);
}
return res;
}
public void inorder(TreeNode root){
if(root==null) return ;
inorder(root.left);
nums.add(root.val);
inorder(root.right);
}
}TreeSet毕竟是树形的结构，效率肯定不如HashSet，但是用来对这道题进行模拟还是足够的。
到达首都的最小油耗
给你一棵n个节点的树（一个无向、连通、无环图），每个节点表示一个城市，编号从0到n - 1，且恰好有n - 1条路。0是首都。给你一个二维整数数组roads，其中roads[i] = [ai, bi]，表示城市ai和bi之间有一条 双向路 。每个城市里有一个代表，他们都要去首都参加一个会议。
每座城市里有一辆车。给你一个整数
seats表示每辆车里面座位的数目。城市里的代表可以选择乘坐所在城市的车，或者乘坐其他城市的车。相邻城市之间一辆车的油耗是一升汽油。
请你返回到达首都最少需要多少升汽油。
这道题主要就是利用roads来建图。
class Solution {
List<Integer> [] graph;
int seats;
long res;
public long minimumFuelCost(int[][] roads, int seats) {
this.seats=seats;
res=0;
//路数
int n=roads.length;
//点数 n+1 范围从0到n
//建图
graph=new List [n+1];
for(int i=0;i<=n;i++){
graph[i]=new ArrayList<>();
}
//存图
for(int [] road:roads){
graph[road[0]].add(road[1]);
graph[road[1]].add(road[0]);
}
dfs(0,-1);
return res;
}
public int dfs(int cur,int des){
int size=1;
//对于当前结点在图上的每一个相邻结点
for(int node:graph[cur]){
if(node!=des){
//如果还没到达目的地
size+=dfs(node,cur);
}
}
if(cur>0) res+=(size+seats-1)/seats;
return size;
}
}至于算消耗汽油数，要理解什么情况下才能消耗最少？
把所有城市抽象成图上的点，首都就是图中的树的根。一位乘客坐当前结点上的车或者在它之下的点的顺风车是最好的；但如果ta坐着的车又往下接其他人，再回到该点，就走了重复的路线，耗费了汽油，这不是最优的选择。
因此，算汽油数就是在算所有结点经过的总的路径长度，只是中间需要一个小的转化$size/seats$。
总的路径长度可以用dfs求得。
