一个数轴上共有N个点，第一个点的坐标是度度熊现在位置，第N-1个点是度度熊的家。现在他需要依次的从0号坐标走到N-1号坐标。
但是除了0号坐标和N-1号坐标，他可以在其余的N-2个坐标中选出一个点，并直接将这个点忽略掉，问度度熊回家至少走多少距离？
[编程题]度度熊回家
import java.util.Scanner;
public class Main{
public static void main(String[] argus){
Scanner sc = new Scanner(System.in);
int num = sc.nextInt();
int[] point = new int[num];
for(int i = 0; i<num; i++){
point[i] = sc.nextInt();
}
int before = 0;
int after = 0;
int Max = 0;
for(int j = 1; j<num-1; j++){
before = Math.abs(point[j-1]-point[j])+Math.abs(point[j]-point[j+1]);
after = Math.abs(point[j-1]-point[j+1]);
if(before - after > Max){
Max = before - after;
}
}
int sum = 0;
for(int k = 1; k<num; k++){
sum += Math.abs(point[k] - point[k-1]);
}
sum = sum - Max;
System.out.print(sum);
sc.close();
}
} 很简单题目
发表于 2021-09-07 22:07:08
回复(0)
o(n)的时间复杂度
public class Main {
public static void main(String[] args) {
Scanner in = new Scanner(System.in);
int n = in.nextInt();
int[] array = new int[n];
for (int i = 0; i < n; i++) {
array[i] = in.nextInt();
}
int max = 0;
int sum = 0, temp1, temp2;
for (int i = 0; i < n - 2; i++) {
temp1 = array[i + 1] - array[i];
temp2 = array[i + 2] - array[i + 1];
sum += Math.abs(temp1);
if (((temp1 ^ temp2) >>> 31) == 1) {//判断是否异号
max = Math.max(Math.abs(temp1 - temp2) - Math.abs(array[i + 2] - array[i]), max);
}
}
sum += Math.abs(array[n - 1] - array[n - 2]);//加上最后一组数据
System.out.println(sum - max);
}
}
编辑于 2019-02-22 14:26:02
回复(0)
import java.io.BufferedReader;import java.io.IOException;
import java.io.InputStreamReader;
/**
*
* @author 恒哥
*
* @date 2018年1月11日
*/
public class Main {
static int N = 0;
static int[] arr;
public static void main(String[] args) {
getArray(); // 获取控制台的数组
int maxLength = 0; // 定义中间点距离两边点的绝对值之和，设置初始和的最大值为0
int index = 0; // 定义该和的绝对值最大处的位置
// 依次从前向后计算某个点的距离前后的绝对值之和(currentLength)，直到找到最大值(maxLength)所在的点的位置(index)
for (int i = 1; i < N - 1; i++) {
int currentLength = Math.abs(arr[i - 1] - arr[i]) + Math.abs(arr[i] - arr[i + 1]);
if (currentLength > maxLength) {
maxLength = currentLength;
index = i;
}
}
// 找到之后，将这个两边距离最大的中间点的值设置为其前驱或后继的值
arr[index] = arr[index + 1];
// 调用方法打印两端的距离
System.out.println(getDistance(arr));
}
/**
* 以字符串的格式从控制台读取数组，并转化为整型数组
*/
public static void getArray() {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
try {
N = Integer.parseInt(br.readLine());
arr = new int[N];
String str = br.readLine();
String[] strArr = str.split(" ");
for (int i = 0; i < N; i++) {
arr[i] = Integer.parseInt(strArr[i]);
}
} catch (NumberFormatException e) {
e.printStackTrace();
} catch (IOException e) {
e.printStackTrace();
}
}
/**
* 计算数组的首尾距离
*/
public static int getDistance(int[] array) {
int distance = 0;
for (int i = 0; i < N - 1; i++) {
distance += Math.abs(array[i] - array[i + 1]);
}
return distance;
}
}
发表于 2018-01-11 19:57:13
回复(0)
public static void main(String[] args){
Scanner scanner=new Scanner(System.in);
int length=scanner.nextInt();
int[]arrays=new int[length];
for(int i=0;i<length;i++){
arrays[i]=scanner.nextInt();
}
int max=0;
int useless=0;
int sum=0;
for(int i=1;i<length-1;i++) {
//先计算不去掉i点时3个点之间的距离
int dis = Math.abs(arrays[i]-arrays[i-1])+Math.abs(arrays[i+1]-arrays[i]);
//顺便计算sum，未包括最后一点的距离
sum += Math.abs(arrays[i]-arrays[i-1]);
//在计算去掉i点之后两点的距离
int undis = Math.abs(arrays[i-1]-arrays[i+1]);
int d = Math.abs(dis-undis);
//差值最大的点为可去掉的点
if(d>max){
max = d;
useless = i;
}
}
if(useless!=0){
sum = sum +Math.abs(arrays[length-1]-arrays[length-2])
- Math.abs(arrays[useless]-arrays[useless-1])
-Math.abs(arrays[useless+1]-arrays[useless])
+Math.abs(arrays[useless-1]-arrays[useless+1]);
}else{
sum = sum+Math.abs(arrays[length-1]-arrays[length-2]);
}
System.out.println(sum);
}
发表于 2018-01-09 20:05:33
回复(0)
import java.util.*;
public class Main
{
public static void main(String[] args)
{int a[]=new int[50];
int max=-1000000000,n,i=0,sum=0;
Scanner read=new Scanner(System.in);
n=read.nextInt();
while(i<n)
{
a[i]=read.nextInt();
if(i>0)
sum+=Math.abs(a[i]-a[i-1]);
if(i>1)
{ int x;
x=Math.abs(a[i]-a[i-1])+Math.abs(a[i-1]-a[i-2])-Math.abs(a[i]-a[i-2]);
if(x>max) max=x;
}
i++;
}
System.out.println(sum-max);
}
}
发表于 2017-06-22 10:28:50
回复(0)
// 1.删除点的计算
// 2.计算总步数
private static int howManyStep(int n, int[] num) {
int deleteLocation = 1;
int deleteMax = 0;
int temp = 0;
// 1.删除点的计算
for (int i = 1; i < n-1; i++) {
// 1.1有i点时从i-1到i+1所需步骤，与无i点时从i-1到i+1所需步骤的差
temp = Math.abs(num[i + 1] - num[i]) + Math.abs(num[i] - num[i -
1]) - Math.abs(num[i + 1] - num[i - 1]);
temp = Math.abs(temp);
if (temp > deleteMax) {
deleteMax = temp;
deleteLocation = i;
}
}
// 2.计算总步数
int step = 0;
for (int i = 0; i < n-1; i++) {
if (i != deleteLocation - 1) {
step += Math.abs(num[i + 1] - num[i]);
} else {
step += Math.abs(num[i + 2] - num[i]);
i++;
}
}
return step;
}
}
编辑于 2017-05-15 15:59:52
回复(0)
import java.util.*;
public class Main{
public static void main(String[] args){
Scanner sc = new Scanner(System.in);
while(sc.hasNext()){
int a = sc.nextInt();
int array[] = new int[a];
for(int i = 0;i < a; i++){
array[i] = sc.nextInt();
}
int maxsum = 0;
for(int i = 0; i < a-1 ;i++){
maxsum += Math.abs(array[i+1] - array[i]);
}
if(a > 2){
int minsum = maxsum - Math.abs(array[2] -
array[1]) - Math.abs(array[0] - array[1]) + Math.abs(array[2] -
array[0]);
for(int i = 2; i < a-1 ;i++){
int d = Math.abs(array[i+1] - array[i]) +
Math.abs(array[i-1] - array[i]);
int temp = maxsum - d + Math.abs(array[i+1]
- array[i-1]);
if(temp < minsum){
minsum = temp;
}
}
System.out.print(minsum);
}
}
}
}
发表于 2017-05-09 21:51:34
回复(0)
问题信息
难度：
9条回答
258收藏
16307浏览
通过挑战的用户
-
2023-03-13 15:15:36 -
2023-03-11 16:45:39 -
2023-03-10 22:58:43
-
2023-03-06 22:30:40
-
2023-03-06 22:25:26
-
扫描二维码，关注牛客网
- 意见反馈
-
下载牛客APP，随时随地刷题
扫一扫，把题目装进口袋
- 求职之前，先上牛客
-
扫描二维码，进入QQ群
扫描二维码，关注牛客公众号
- 公司地址：北京市朝阳区北苑路北美国际商务中心K2座一层-北京牛客科技有限公司
- 联系方式：010-60728802 投诉举报电话：010-57596212（朝阳人力社保局）
- 牛客科技© All rights reserved admin@nowcoder.com
- 京ICP备14055008号-4 增值电信业务经营许可证 营业执照 人力资源服务许可证
-
京公网安备
11010502036488号
