文章目录
- 攀登者问题
- 停车场
- 最短路径
攀登者问题
24/03/09 20:50~23:10
攀登者喜欢寻找各种地图，并且尝试攀登到最高的山峰。地图表示为一维数组，数组的索引代表水平位置，数组的元素代表相对海拔高度。其中数组元素0代表地面。一个山脉可能有多座山峰(高度大于相邻位置的高度，或在地图边界且高度大于相邻的高度)。登山者想要知道一张地图中有多少座山峰。
例如[0,1,2,4,3,1,0,0,1,2,3,1,2,1,0], 代表如下图所示的地图，地图中有两个山脉位置分别为 1,2,3,4,5和8,9,10,11,12,13，最高峰高度分别为 4,3。最高峰位置分别为3,10。
一个山脉可能有多座山峰(高度大于相邻位置的高度，或在地图边界且高度大于相邻的高度)。
java"> /**
* 返回地图中山峰的数量
*
* @param hill_map int整型一维数组 地图数组(长度大于1)
* @return int整型
*/
public int count_peaks(int[] hill_map) {
// write code here 双指针
int result = 0;
if (hill_map.length == 0) {
return result;
} else if (hill_map.length == 1) {
return 1;
}
for (int i = 0; i < hill_map.length; i++) {
if (i > 0 && i < hill_map.length - 1) {
// 处理非边界元素
if (hill_map[i] > hill_map[i - 1] && hill_map[i] > hill_map[i + 1]) {
result++;
}
} else if (i == 0 && hill_map[i] > hill_map[i + 1]) {
// 处理左边界元素
result++;
} else if (i == hill_map.length - 1 && hill_map[i] > hill_map[i - 1]) {
// 处理右边界元素
result++;
}
}
return result;
}
// 100%
停车场
停车场有一横排车位，0代表没有停车，1代表有车。至少停了一辆车在车位上，也至少有一个空位没有停车为了防剐蹭，需为停车人找到一个车位，使得距停车人的车最近的车辆的距离是最大的，返回此时的最大距离。
- 特定大小的停车场，数组cars[]表示，其中1表示有车，0表示没车。
- 车辆大小不一，小车占一个车位（长度1），货车占两个车位（长度2），卡车占三个车位（长度3），统计停车场最少可以停多少辆车，返回具体的数目。
输入描述
1.一个用半角逗号分割的停车标识字符串，停车标识为0或1，0为空位，1为已停车。
2.停车位最多100个。
输出描述
最少可以停多少辆车
eg1：
- 输入 1,0,1
- 输出 2
- 说明 1个小车占第1个车位，第二个车位空，1个小车占第3个车位，最少有两辆车
eg2：
- 输入 1,1,0,0,1,1,1,0,1
- 输出 3
- 说明 1个货车占第1、2个车位；第3、4个车位空；1个卡车占第5、6、7个车位；第8个车位空；1个小车占第9个车位；最少3辆车
java"> public static void main(String[] args) {
Scanner in = new Scanner(System.in);
// 注意 hasNext 和 hasNextLine 的区别
String carsLine = in.nextLine();
int[] cars = new int[0];
String[] split = carsLine.split(",");
if (split.length > 0) {
cars = new int[split.length];
for (int i = 0; i < split.length; i++) {
if (Objects.equals(split[i], "0") || Objects.equals(split[i], "1")) {
cars[i] = Integer.parseInt(split[i]);
}
}
}
int i = parkingCount(cars);
System.out.println(i);
}
public static int parkingCount(int[] car) {
int result = 0;
int count = 0;
for (int i = 0; i < car.length; i++) {
if (car[i] == 1) {
// 记录停车位大小
count++;
if (count == 1) {
// 停车位大小为1，就可以停一辆车
result++;
} else if (count == 3) {
// 停车位大小为3，到达最大车位，需要重新统计。
count = 0;
}
} else {
// 没有连续车位，停车位大小归0
count = 0;
}
}
return result;
}
// 100%
最短路径
给定两个字符串，分别为字符串A与字符串B。例如A字符串为ABCABBA，B字符串为CBABAC。可以得到m*n的二维数组，定义原点为(0,0)，终点为(m,n)，水平与垂直的每一条边距离为1,从原点(0,0)到(0,A)为水平边，距离为1，从(0,A)到(A,C)为垂直边，距离为1; 假设两个字符串同一位置的两个字符相同则可以作一个斜边、如(A.C)到.B)最短距离为斜边，距离同样为1。作出所有的斜边，则有(0.0)到(B.B)的距离为 1个水平边+1个垂直边+1个斜边 =3。
根据定义可知，原点到终点的最短距离路径如下图红线标记，最短距离为9;
路径为(0,0)->(A,0)->(A,C)->(B,B)->(C,B)->(A,A)->(B,B)->(B,B)->(A,A)->(A,C)
19% 没做出来
