welcome to my blog
程序员代码面试指南第二版 11.可见的山峰对数量(普通和进阶)
题目描述
题目描述
一个不含有负数的数组可以代表一圈环形山，每个位置的值代表山的高度。比如，{3,1,2,4,5}，{4,5,3,1,2}或{1,2,4,5,3}都代表同样结构的环形山。
3->1->2->4->5->3 方向叫作 next 方向(逆时针)，3->5->4->2->1->3 方向叫作 last 方向(顺时针)。
山峰 A 和 山峰 B 能够相互看见的条件为:
1. 如果 A 和 B 是同一座山，认为不能相互看见。
2. 如果 A 和 B 是不同的山，并且在环中相邻，认为可以相互看见。
3. 如果 A 和 B 是不同的山，并且在环中不相邻，假设两座山高度的最小值为 min。如果 A 通过 next 方向到 B 的途中没有高度比 min 大的山峰，或者 A 通过 last 方向到 B 的途中没有高度比 min 大的山峰，认为 A 和 B 可以相互看见。
问题如下：
给定一个不含有负数且没有重复值的数组 arr，请问有多少对山峰能够相互看见？
输入描述:
第一行一个整数 T，表示测试数据的组数。
每组数据的第一行有三个数字 n, p, m，其中 n 表示 山峰的数量，
山峰的高度数组等于 1 - p 的 p! 个全排列按字典序排序后的第 m 个全排列的前 n 项。
输出描述:
输出一行一个整数表示答案。
示例1
输入
1
5 5 2
输出
7
说明
1-5 的全排列排序后的第二个排列 为 1 2 3 5 4
第一次做, 找到数学规律即可, 当山峰数大于2时, 结果为(n-2)*2+1= 2n-3; 山峰数等于2时, 结果为1; 山峰数为1时,结果为0
/*
没用到p和m, 但是还要接受p,m的值
*/
import java.util.Scanner;
public class Main{
public static void main(String[] args){
Scanner sc = new Scanner(System.in);
int T = Integer.parseInt(sc.nextLine());
for(int i=0; i<T; i++){
String curr = sc.nextLine();
int n = Integer.parseInt(curr.split(" ")[0]),
p = Integer.parseInt(curr.split(" ")[1]),
m = Integer.parseInt(curr.split(" ")[2]);
if(n<2)
System.out.println(0);
else{
System.out.println((n-2)*2+1);
}
}
}
}
题目描述
一个不含有负数的数组可以代表一圈环形山，每个位置的值代表山的高度。比如，{3,1,2,4,5}，{4,5,3,1,2}或{1,2,4,5,3}都代表同样结构的环形山。
3->1->2->4->5->3 方向叫作 next 方向(逆时针)，3->5->4->2->1->3 方向叫作 last 方向(顺时针)。
山峰 A 和 山峰 B 能够相互看见的条件为:
1. 如果 A 和 B 是同一座山，认为不能相互看见。
2. 如果 A 和 B 是不同的山，并且在环中相邻，认为可以相互看见。
3. 如果 A 和 B 是不同的山，并且在环中不相邻，假设两座山高度的最小值为 min。如果 A 通过 next 方向到 B 的途中没有高度比 min 大的山峰，
或者 A 通过 last 方向到 B 的途中没有高度比 min 大的山峰，认为 A 和 B 可以相互看见。
问题如下：
给定一个含有负数可能有重复值的数组 arr，请问有多少对山峰能够相互看见？
输入描述:
第一行给出一个整数 n，表示山峰的数量。
以下一行 n 个整数表示各个山峰的高度。
输出描述:
输出一行表示答案。
示例1
输入
5
3 1 2 4 5
输出
7第一次做; 核心:1)小找大; 2)带重复值的单调栈结构(重复值累加次数), 遍历阶段, 清算阶段; 3)先找到数组的最大值, 从最大值开始, 将最大值入栈, 这样遍历阶段不会出现栈空的情况; 在遍历阶段能和清算阶段的规律如下:
在遍历阶段能和清算阶段的规律:
遍历阶段, 某个记录(x,k)从栈中弹出, 产生可见山峰对的数量为: 2*k + C(2,k)对 k==1时, C(2,k)=0; k>1时, C(2,k)=k*(k-1)/2
清算阶段, 某个记录(x,K)从栈中弹出, 产生可见山峰对的数量为:
1) (x,k)不是栈的倒数第二个元素, 也不是栈的倒数第一个元素, 此时产生2*k+C(2,k)个, k==1时, C(2,k)=0; k>1时, C(2,k)=k*(k-1)/2
2) (x,k)是栈的倒数第二个元素, 此时产生可见山峰对的数量取决于栈底元素的个数
2.1) 如果栈底元素出现1次, 此时产生可见山峰对的数量为: k+C(2,k)个, k==1时, C(2,k)=0; k>1时, C(2,k)=k*(k-1)/2
2.2) 如果栈底元素出现大于1次, 此时产生可见山峰对的数量为: 2*k+C(2,k)个, k==1时, C(2,k)=0; k>1时, C(2,k)=k*(k-1)/2
3) (x,k)是栈的倒数第一个元素, 此时产生可见山峰对的数量为: C(2,k)个, k==1时, C(2,k)=0; k>1时, C(2,k)=k*(k-1)/2
import java.util.Scanner;
import java.util.Stack;
public class Main{
public static void main(String[] args){
Scanner sc = new Scanner(System.in);
int n = Integer.parseInt(sc.nextLine());
String[] str = sc.nextLine().split(" ");
int[] arr = new int[n];
for(int i=0; i<n; i++)
arr[i] = Integer.parseInt(str[i]);
/*
先遍历一遍数组找到最大值, 之后使用单调栈结构时, 先将最大值入栈, 这样做的好处时, 在单调栈的遍历阶段结束时,
栈底的最大值会一直存在, 就不用担心处理前面的元素时, 栈为空的情况了
*/
int maxIndex = 0;
for(int i=1; i<n; i++){
if(arr[i] > arr[maxIndex])
maxIndex = i;
}
//把最大值放在数组开头; 不能这样, 这样做破坏了数据分布!!!
//int temp = arr[0];
//arr[0] = arr[maxIndex];
//arr[maxIndex] = temp;
//单调栈(带重复值, 重复值需合并): 遍历阶段; 清算阶段
//本题:栈底到栈顶递减
Stack<Record> s = new Stack<Record>();
//initialize
s.push(new Record(arr[maxIndex]));
Record curr;
int res = 0, i = maxIndex+1 == n ? 0 : maxIndex + 1;
//遍历阶段
//循环转一圈
while(i != maxIndex){
if(arr[i] < s.peek().height){
s.push(new Record(arr[i]));
}
else if(arr[i] == s.peek().height){
s.peek().num++;
}
//arr[i] > s.peek().height
else{
//栈不会空! 因为栈底是最大值, 在遍历阶段不会弹出, 只有比栈顶元素大时, 才会弹出栈顶
while( arr[i] > s.peek().height){
//不用担心pop()之后栈为空, 因为一定不会为空, 因为栈底有最大值, 最大值是不会弹出的, 只能在清算阶段处理
curr = s.pop();
res += curr.num*2 + curr.num*(curr.num-1)/2;
}
if(arr[i] == s.peek().height)
s.peek().num++;
else
s.push(new Record(arr[i]));
}
i = i + 1 == n ? 0 : i + 1;
}
//清算阶段
/*
清算阶段有三种情况,
1.curr不是倒数第一个元素也不是倒数第二个元素
2.curr是倒数第二个元素(此时要特别注意栈底元素的出现次数, 分成1和不是1两种情况讨论)
3.curr是倒数第一个元素
*/
while(!s.isEmpty()){
curr = s.pop();
//1.curr不是倒数第一个也不是倒数第二个元素
if(s.size()>=2){
res += curr.num*2 + curr.num*(curr.num-1)/2;
}
//2.curr是倒数第二个元素
else if(s.size()==1){
res += (s.peek().num==1? curr.num : curr.num*2) + curr.num*(curr.num-1)/2;
}
//3. curr是倒数第一个元素
else{
res += curr.num*(curr.num-1)/2;
}
}
System.out.println(res);
}
public static class Record{
int height;
int num;
Record(int height){
this.height = height;
this.num = 1;
}
}
}