2021-9-29

编程题两道： 输入描述: 一个只包含a,b字符的字符串，长度不超过100000。 输出描述: 最小的操作次数。结果对1000000007取模。 牛客链接：

参考其他人的思想:

从后往前遍历字符串，遍历的过程中我们记录一下当前位置及其右边所有字符中b的个数： （1）遇到b字符其计数就自增1； （2）遇到a字符就进行一次逻辑上的“替换”操作。 遇到a的时候相当于遇到了一次ab子串，这时候将其“替换”为bba就会使得b字符增加一个。因此，替换操作的次数只与b字符的数量相关，替换一次，就增加一个b，所以操作数每次加上b的个数即可。而此时将a移动到了右边去，可能右边还会存在ab子串，因此右边还需要继续进行替换操作。 在向右替换的过程中，这个a字符需要不断地通过替换操作向右传递，直到自己的右边已经全部是a，这时候它已经经过了之前右边所有的b字符，而每经过一次b字符，就因为替换操作使得b字符增加一个，因此当它无法再往右边移动时，总共使得右边b字符的数量翻了一番。

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

public class Main {
    static final int MOD = 1000000007;
    
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        char[] str = br.readLine().trim().toCharArray();
        int countB = 0;
        int res = 0;
        for(int i = str.length - 1; i >= 0; i--){
            if(str[i] == 'b'){
                countB ++;
            }else{
                // 此时需要替换
                res = (res + countB) % MOD;
                countB = countB * 2 % MOD;
            }
        }
        System.out.println(res);
    }
}

另外一道编程题： leetcode 链接 最远建筑物

给你一个整数数组 heights ，表示建筑物的高度。另有一些砖块 bricks 和梯子 ladders 。

你从建筑物 0 开始旅程，不断向后面的建筑物移动，期间可能会用到砖块或梯子。

当从建筑物 i 移动到建筑物 i+1（下标 从 0 开始 ）时：

如果当前建筑物的高度 大于或等于 下一建筑物的高度，则不需要梯子或砖块 如果当前建筑的高度 小于 下一个建筑的高度，您可以使用 一架梯子 或 (h[i+1] - h[i]) 个砖块 如果以最佳方式使用给定的梯子和砖块，返回你可以到达的最远建筑物的下标（下标 从 0 开始 ）。

class Solution {
    public int furthestBuilding(int[] heights, int bricks, int ladders) {
        int n = heights.length, sum = 0;
        Queue<Integer> queue = new PriorityQueue<>();
        for(int i = 1; i < heights.length; i++) {
            int diff = heights[i] - heights[i - 1];
            if(diff > 0) {
                queue.offer(diff);
                if(queue.size() > ladders) {
                    sum += queue.poll();
                }
                if(sum > bricks)
                    return i - 1;
            }
        }
        return n - 1;
    }
}