计算题

[编程题]计算题

热度指数：2985 时间限制：C/C++ 1秒，其他语言2秒空间限制：C/C++ 64M，其他语言128M
算法知识视频讲解

给定n个非负整数表示每个宽度为1的柱子的高度题，计算按此排列的柱子，下雨之后能接多少雨水。

输入描述:

逗号分隔的整数，表示每根柱子的高度。
柱子数n<=1000000,每根柱子的高度不大于100000

输出描述:

雨水量（高度和）

示例1

输入

0,1,0,2,1,0,1,3,2,1,2,1

输出

算法知识视频讲解

Java

阿尼亚瓦库瓦库

import java.util.Scanner;

public class Main {

    // 思路：先将字符串分割，从前往后，选择第一个板作为参照，直到找到第二块比它高或者和它一样高的板在计算盛水量，
    // 记得计算损失量，将第二块板作为下一次的起始板，继续遍历；然后从后往前进行相同的遍历。
    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);

        String line = scanner.nextLine();

        String[] split = line.split(",");

        int[] arr = new int[split.length];

        for (int i = 0; i < split.length; i++) {
            arr[i] = Integer.parseInt(split[i]);
        }

        System.out.println(receiveRainwater(arr));
    }

    public static long receiveRainwater(int[] arr) {

        if (arr.length == 0) {
            return 0;
        }

        long amount = 0;
        int start = 0;
        while (true) {
            int index = start + 1;
            if (index == arr.length) {
                break;
            }
            long deBuff = 0;
            while (index < arr.length) {
                if (arr[start] <= arr[index]) {
                    break;
                }
                deBuff += arr[index];
                index++;
            }
            if (index == arr.length) {
                break;
            }
            amount += (long) (index - start - 1) * (arr[start] > arr[index] ? arr[index] : arr[start]) - deBuff;
            start = index;
        }

        int end = start - 1;
        start = arr.length - 1;
        while (true) {
            int index = start - 1;
            if (index == end) {
                break;
            }
            long deBuff = 0;
            while (index > end) {
                if (arr[start] <= arr[index]) {
                    break;
                }
                deBuff += arr[index];
                index--;
            }
            if (index == end) {
                break;
            }
            amount += (long) (start - index - 1) * (arr[start] > arr[index] ? arr[index] : arr[start]) - deBuff;
            start = index;
        }

        return amount;
    }
}

改进：

import java.io.InputStreamReader;
import java.io.BufferedReader;
import java.io.IOException;

public class Main {

    // 思路：先将字符串分割，从前往后，选择第一个板作为参照，直到找到第二块比它高或者和它一样高的板在计算盛水量，
    // 记得计算损失量，将第二块板作为下一次的起始板，继续遍历；然后从后往前进行相同的遍历。
    public static void main(String[] args) {

        BufferedReader bufferedReader = new BufferedReader(new InputStreamReader(System.in)); // bufferedraader+inputstream 更快

        String line = null;
        try {
            line = bufferedReader.readLine();
        } catch (IOException e) {
            e.printStackTrace();
        }

        String[] split = line.split(","); 

        int[] arr = new int[split.length];

        for (int i = 0; i < split.length; i++) {
            arr[i] = Integer.parseInt(split[i]);
        }

        System.out.println(receiveRainwater(arr));
    }

    public static long receiveRainwater(int[] arr) {

        if (arr.length == 0) {
            return 0;
        }

        long amount = 0;
        int start = 0;
        while (true) {
            int index = start + 1;
            if (index == arr.length) {
                break;
            }
            long deBuff = 0;
            while (index < arr.length) {
                if (arr[start] <= arr[index]) {
                    break;
                }
                deBuff += arr[index];
                index++;
            }
            if (index == arr.length) {
                break;
            }
            amount += (long) (index - start - 1) * (arr[start] > arr[index] ? arr[index] : arr[start]) - deBuff;
            start = index;
        }

        int end = start - 1;
        start = arr.length - 1;
        while (true) {
            int index = start - 1;
            if (index == end) {
                break;
            }
            long deBuff = 0;
            while (index > end) {
                if (arr[start] <= arr[index]) {
                    break;
                }
                deBuff += arr[index];
                index--;
            }
            if (index == end) {
                break;
            }
            amount += (long) (start - index - 1) * (arr[start] > arr[index] ? arr[index] : arr[start]) - deBuff;
            start = index;
        }

        return amount;
    }
}

编辑于 2021-05-06 21:13:48 回复(0)