Java算法：牛客网快手笔试真题算法Java版1-36题_算法牛客网考试

link管理
链接快照平台
输入网页链接，自动生成快照
标签化管理网页链接
KS1 获得最多的奖金

小明在越南旅游，参加了当地的娱乐活动。小明运气很好，拿到了大奖， 到了最后的拿奖金环节。小明发现桌子上放着一列红包，每个红包上写着奖金数额。
现在主持人给要求小明在这一列红包之间“切”2刀，将这一列红包“切”成3组，并且第一组的奖金之和等于最后一组奖金和（允许任意一组的红包集合是空）。最终第一组红包的奖金之和就是小明能拿到的总奖金。小明想知道最多能拿到的奖金是多少，你能帮他算算吗。
举例解释：桌子上放了红包  1, 2, 3, 4, 7, 10。小明在“4,7”之间、“7,10” 之间各切一刀，将红包分成3组 [1, 2, 3, 4]   [7]   [10]，其中第一组奖金之和=第三组奖金之和=10，所以小明可以拿到10越南盾。
输入描述:
 
第一行包含一个正整数n，(1<=n<= 200 000)，表示有多少个红包。
第二行包含n个正整数d[i]，表示每个红包包含的奖金数额。其中1<= d[i] <= 1000 000 000
输出描述:
 
小明可以拿到的总奖金
1 3 1 1 4
[1,3,1]  [ ]   [1,4] ，其中第一组奖金和是5，等于第三组奖金和。所以小明可以拿到5越南盾
1 3 2 1 4
[1,3]   [2,1]  [4]，小明可以拿到4越南盾
####示例3
4 1 2
[ ]  [4, 1, 2] [ ] ，小明没办法，为了保证第一组第三组相等，只能都分成空的。所以小明只能拿到0越南盾。
import




    
 java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
public class Main {
    public static void main(String[] args) throws IOException {
        BufferedReader bf = new BufferedReader(new InputStreamReader(System.in));
        int n = Integer.parseInt(bf.readLine());
        String[] line2 = bf.readLine().split(" ");
        int[] nums = new int[n];
        for (int i = 0; i < n; i++) {
            nums[i] = Integer.parseInt(line2[i]);
        int left = 0, right = n - 1;
        long left_sum = nums[left], right_sum = nums[right], max_sum = 0;
        while (left < right) {
            if (left_sum == right_sum) {
                max_sum = left_sum;
                left_sum += nums[++left];
                right_sum += nums[--right];
            } else if (left_sum > right_sum) {
                right_sum += nums[--right];
            } else {
                left_sum += nums[++left];
        System.out.println(max_sum);
KS2 将满二叉树转换为求和树
 
给出满二叉树，编写算法将其转化为求和树
什么是求和树：二叉树的求和树， 是一颗同样结构的二叉树，其树中的每个节点将包含原始树中的左子树和右子树的和。
    /      \
  -2        6
 /   \     /  \ 
8    -4   7    5
    20(4-2+12+6)
      /      \
  4(8-4)      12(7+5)
  /   \      /  \ 
0      0    0    0
二叉树给出前序和中序输入，求和树要求中序输出；
所有处理数据不会大于int；
输入描述:
 
2行整数，第1行表示二叉树的前序遍历，第2行表示二叉树的中序遍历，以空格分割
输出描述:
 
1行整数，表示求和树的中序遍历，以空格分割
10 -2 8 -4 6 7 5
8 -2 -4 10 7 6 5
0 4 0 20 0 12 0
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.Arrays;
public class Main {
    public static void main(String[] args) throws IOException {
        BufferedReader bufferedReader = new BufferedReader(new InputStreamReader(System.in));
        String s1 = bufferedReader.readLine();
        String s2 = bufferedReader.readLine();
        String[] preOrder = s1.split(" ");
        String[] inOrder = s2.split(" ");
        int[] res = new int[inOrder.length];
        for (int i = 0; i < inOrder.length; i++) {
            res[i] = Integer.parseInt(inOrder[i]);
        dfs(res, 0, inOrder.length - 1);
        for (int r : res) System.out.print(r + " ");
    private static int dfs(int[] res, int left, int right) {
        if (left == right) {
            int temp = res[left];
            res[left] = 0;
            return temp;
        int mid = (right - left) / 2 + left;
        int leftSum = dfs(res, left, mid - 1);
        int rightSum = dfs(res, mid + 1, right);
        int temp = res[mid];
        res[mid] = leftSum + rightSum;
        return res[mid] + temp;
KS3 搭积木
 
小明有一袋子长方形的积木，如果一个积木A的长和宽都不大于另外一个积木B的长和宽，则积木A可以搭在积木B的上面。好奇的小明特别想知道这一袋子积木最多可以搭多少层，你能帮他想想办法吗？
定义每一个长方形的长L和宽W都为正整数，并且1 <= W <= L <= INT_MAX, 袋子里面长方形的个数为N, 并且 1 <= N <= 1000000.
假如袋子里共有5个积木分别为 (2, 2), (2, 4), (3, 3), (2, 5), (4, 5), 则不难判断这些积木最多可以搭成4层, 因为(2, 2) < (2, 4) < (2, 5) < (4, 5)。
输入描述:
 
第一行为积木的总个数 N
之后一共有N行，分别对应于每一个积木的宽W和长L
输出描述:
 
输出总共可以搭的层数
import




    
 java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.*;
public class Main {
    public static void main(String[] args) throws IOException {
        BufferedReader bf = new BufferedReader(new InputStreamReader(System.in));
        int n = Integer.parseInt(bf.readLine());
        int[][] arr = new int[n][2];
        for (int i = 0; i < n; i++) {
            String[] s = bf.readLine().split(" ");
            arr[i][0] = Integer.parseInt(s[0]);
            arr[i][1] = Integer.parseInt(s[1]);
        bf.close();
        if (n == 1) {
            System.out.println(1);
            return;
        Arrays.sort(arr, Comparator.comparingInt(o -> o[0]));
        int[] dp = new int[n];
        dp[0] = 1;
        int count = 0;
        for (int i = 0; i < n; i++) {
            int val = arr[i][1];
            int l = 0;
            int r = count;
            while (l < r) {
                int mid = l + (r - l) / 2;
                if (dp[mid] > val)
                    r = mid;
                    l = mid + 1;
            if (l == count)
                count++;
            dp[l] = val;
        System.out.println(count);
KS4 最少数量货物装箱问题
 
有重量分别为3，5，7公斤的三种货物，和一个载重量为X公斤的箱子（不考虑体积等其它因素，只计算重量）
需要向箱子内装满X公斤的货物，要求使用的货物个数尽可能少（三种货物数量无限）
输入描述:
 
输入箱子载重量X(1 <= X <= 10000)，一个整数。
输出描述:
 
如果无法装满，输出 -1。
如果可以装满，输出使用货物的总个数。
使用1个5公斤，1个3公斤货物
import java.io.*;
public class Main {
    public static void main(String[] args) throws IOException {
        BufferedReader bf = new BufferedReader(new InputStreamReader(System.in));
        int X = Integer.parseInt(bf.readLine());
        int[] w = new int[]{3, 5, 7};
        int[] dp = new int[X + 1];
        for (int k : w) {
            for (int j = k; j <= X; j++) {
                if (j % k == 0) {
                    dp[j] = dp[j - k] + 1;
                } else if (dp[j - k] != 0) {
                    dp[j] = dp[j - k] + 1;
        System.out.println(dp[X] == 0 ? -1 : dp[X]);
KS5 回文子串
 
给定一个字符串，你的任务是计算这个字符串中有多少个回文子串。
("回文串”是一个正读和反读都一样的字符串，比如“level”或者“noon”等等就是回文串。)
具有不同开始位置或结束位置的子串，即使是由相同的字符组成，也会被计为是不同的子串。
可用C++,Java,C#实现相关代码逻辑
输入描述:
 
输入一个字符串S 例如“aabcb”(1 <= |S| <= 50), |S|表示字符串S的长度。
输出描述:
 
符合条件的字符串有"a","a","aa","b","c","b","bcb"
所以答案:7
aabcb
import java.io.*;
public class Main {
    public static void main(String[] args) throws IOException {
        BufferedReader bf = new BufferedReader(new InputStreamReader(System.in));
        String s = bf.readLine




    
();
        int count = 0, len = s.length();
        for (int i = 0; i < len; i++) {
            for (int j = i + 1; j <= len; j++) {
                if (same(s.substring(i, j))) {
                    count++;
        System.out.print(count);
    // 判断是否为回文串
    private static boolean same(String s) {
        char[] chars = s.toCharArray();
        int left = 0, right = chars.length - 1;
        while (left < right) {
            if (chars[left++] != chars[right--]) {
                return false;
        return true;
KS6 字符串长度最大乘积
 
已知一个字符串数组words，要求寻找其中两个没有重复字符的字符串，使得这两个字符串的长度乘积最大，输出这个最大的乘积。如：
words=["abcd","wxyh","defgh"], 其中不包含重复字符的两个字符串是"abcd"和"wxyh"，则输出16
words=["a","aa","aaa","aaaa"], 找不到满足要求的两个字符串，则输出0
输入描述:
 
Input:
["a","ab","abc","cd","bcd","abcd"]
输出描述:
 
Output:
["a","ab","abc","cd","bcd","abcd"]
Input中，不包含相同字符的有三对：
"ab"和"cd"
"a"和"cd"
"a"和"bcd"
所以字符串长度乘积的最大值是4
import java.io.*;
public class Main {
    public static void main(String[] args) throws IOException {
        BufferedReader reder = new BufferedReader(new InputStreamReader(System.in));
        String inputStr = reder.readLine();
        String[] strs = inputStr.substring(1, inputStr.length() - 1).split(",");
        int max = 0;
        for (int i = 0; i < strs.length; i++) {
            for (int j = i + 1; j < strs.length; j++) {
                max = Math.max(compute(strs[i], strs[j]), max);
        System.out.println(max);
    public static int compute(String strs1, String strs2) {
        for (int i = 1; i < strs1.length() - 1; i++) {
            for (int j = 1; j < strs2.length() - 1; j++) {
                if (strs1.charAt(i) == strs2.charAt(j)) {
                    return 0;
        return (strs1.length() - 2) * (strs2.length() - 2);
KS7 今年的第几天
 
输入年、月、日，计算该天是本年的第几天。 
包括三个整数年(1<=Y<=3000)、月(1<=M<=12)、日(1<=D<=31)。 
输入可能有多组测试数据，对于每一组测试数据， 
输出一个整数，代表Input中的年、月、日对应本年的第几天。
输入描述:
 
输入：1990 9 20
输出描述:
 
输入：263
2000 5 1 
####备注:
注意闰年的判定方式
import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.io.IOException;
public class Main {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        String[] a = br.readLine().split(" ");
        int year = Integer.parseInt(a[0]);
        int month = Integer.parseInt(a[1]);
        int day = Integer.parseInt(a[2]);
        int[] md = {31, 28, 31, 30, 31, 30, 31, 31, 30, 31, 30, 31};
        if ((year % 4 == 0 && year % 100 != 0




    
) || year % 400 == 0) {
            md[1]++;
        for (int i = 0; i < month - 1; i++) {
            day += md[i];
        System.out.println(day);
KS8 数字序列第n位的值
 
有一个无限长的数字序列1，2，2，3，3，3，4，4，4，4，5，5，5，5，5。。。（数字序列从1开始递增，且数字k在该序列中正好出现k次），求第n项是多少
输入描述:
 
输入为一个整数n
输出描述:
 
输出一个整数，即第n项的值
如：输入为3，有序数列第3项的值为2，则输出为2
import java.io.*;
import java.util.*;
public class Main {
    public static void main(String[] args) throws IOException {
        BufferedReader reader = new BufferedReader(new InputStreamReader(System.in));
        int num = Integer.parseInt(reader.readLine());
        System.out.print(getN(num));
    public static int getN(int num) {
        int sum = 0;
        int i = 1;
        while (sum < num) {
            sum += i;
            i++;
        return i - 1;
KS9 字符串排序
 
月神拿到一个新的数据集，其中每个样本都是一个字符串（长度小于100），样本的的后六位是纯数字，月神需要将所有样本的后六位数字提出来，转换成数字，并排序输出。
月神要实现这样一个很简单的功能确没有时间，作为好朋友的你，一定能解决月神的烦恼，对吧。
输入描述:
 
每个测试用例的第一行是一个正整数M（1<=M<=100)，表示数据集的样本数目
接下来输入M行，每行是数据集的一个样本，每个样本均是字符串，且后六位是数字字符。
输出描述:
 
对每个数据集，输出所有样本的后六位构成的数字排序后的结果（每行输出一个样本的结果）
abc123455
boyxx213456
cba312456
cdwxa654321
123455
213456
312456
654321
import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.io.IOException;
import java.util.Arrays;
public class Main {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int n = Integer.parseInt(br.readLine());
        int[] arr = new int[n];
        for (int i = 0; i < n; i++) {
            String s = br.readLine();
            arr[i] = Integer.parseInt(s.substring(s.length() - 6));
        Arrays.sort(arr);
        for (int i = 0; i < n; i++) {
            System.out.println(arr[i]);
KS10 回文字符串
 
最大回文子串是被研究得比较多的一个经典问题。最近月神想到了一个变种，对于一个字符串，如果不要求子串连续，那么一个字符串的最大回文子串的最大长度是多少呢。
输入描述:
 
每个测试用例输入一行字符串（由数字0-9，字母a-z、A-Z构成），字条串长度大于0且不大于1000.
输出描述:
 
输出该字符串的最长回文子串的长度。（不要求输出最长回文串，并且子串不要求连续）
adbca
因为在本题中，不要求回文子串连续，故最长回文子串为aba(或ada、aca)
####备注:
因为不要求子串连续，所以字符串abc的子串有a、b、c、ab、ac、bc、abc7个
import java.io.*;
public class Main {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        char[] c = br.readLine().toCharArray();
        int len = c.length;
        int[][] dp = new int[len][len];
        for (int i = 0; i < len; i++) {
            dp[i][i] = 1;
        for (int i = len - 2; i >= 0; i--) {
            for (int j = i + 1; j < len; j++) {
                if (c[i] == c[j]) {
                    dp[i][j] = dp[i + 1][j - 1] + 2;
                } else dp[i][j] = Math.max(dp[i + 1][j], dp[i][j - 1]);
        System.




    
out.println(dp[0][len - 1]);
KS11 latex爱好者
 
latex自然是广大研究人员最喜欢使用的科研论文排版工具之一。
月神想在iPhone 上查阅写好的paper，但是无赖iPhone 上没有月神喜欢使用的阅读软件，于是月神也希望像tex老爷爷Donald Knuth那样自己动手do it yourself一个。
在DIY这个阅读软件的过程中，月神碰到一个问题，已知iPhone屏幕的高为H，宽为W，若字体大小为S(假设为方形），则一行可放W / S(取整数部分）个文字，一屏最多可放H / S （取整数部分）行文字。
已知一篇paper有N个段落，每个段落的文字数目由a1, a2, a3,...., an表示，月神希望排版的页数不多于P页（一屏显示一页），那么月神最多可使用多大的字体呢？
1 <= W, H, ai <= 1000
1 <= P <= 1000000
输入描述:
 
每个测试用例的输入包含两行。
第一行输入N,P,H,W
第二行输入N个数a1,a2,a3,...,an表示每个段落的文字个数。
输出描述:
 
对于每个测试用例，输出最大允许的字符大小S
1 10 4 3 10 2 10 4 3 10 10
import java.io.*;
public class Main {
    public static void main(String[] args) throws Exception {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        String[] str1 = br.readLine().split(" ");
        int P = Integer.parseInt(str1[1]);
        int H = Integer.parseInt(str1[2]);
        int W = Integer.parseInt(str1[3]);
        String[] str2 = br.readLine().split(" ");
        int totalNum = 0;
        for (String s : str2) {
            totalNum += Integer.parseInt(s);
        System.out.println(process(P, H, W, totalNum));
    public static int process(int P, int H, int W, int totalNum) {
        int perPaperNum = (totalNum + P - 1) / P;
        int left = 1;
        int right = Math.min(H, W);
        while (left <= right) {
            int mid = left + (right - left) / 2;
            int num = (H / mid) * (W / mid);
            if (num >= perPaperNum) {
                left = mid + 1;
            } else {
                right = mid - 1;
        return right;
KS12 游戏海报
 
小明有26种游戏海报，用小写字母"a"到"z"表示。小明会把游戏海报装订成册（可能有重复的海报），册子可以用一个字符串来表示，每个字符就表示对应的海报，例如abcdea。小明现在想做一些“特别版”，然后卖掉。特别版就是会从所有海报（26种）中随机选一张，加入到册子的任意一个位置。
那现在小明手里已经有一种海报册子，再插入一张新的海报后，他一共可以组成多少不同的海报册子呢？
输入描述:
 
海报册子的字符串表示，1 <= 字符串长度<= 20
输出描述:
 
一个整数，表示可以组成的不同的海报册子种类数
我们可以组成 'ab','ac',...,'az','ba','ca',...,'za' 还有 'aa', 一共 51 种不同的海报册子。
import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.io.IOException;
import java.util.HashSet;
public class Main {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        String str = br.readLine();
        int count = (str.length() + 1) * 26 - str.length();
        System.out.println(count);
KS13 合并数组
 
请实现一个函数，功能为合并两个升序数组为一个升序数组
输入描述:
 
输入有多个测试用例，每个测试用例有1-2行，每行都是以英文逗号分隔从小到大排列的数字
输出描述:
 
输出一行以英文逗号分隔从小到大排列的数组
1,5,7,9
2,3,4,6,8,10
1,2,3,4,5,6,7,8,9,10
不允许使用原生的 sort、concat 等函数
import java.util.*;
import java.io.*;
public class Main {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        String line1 = br.readLine();
        String line2 = br.readLine();
        if (line2 == null) {
            System.out.println(line1);
            return;
        String[] strs1 = line1.split(",");
        String[] strs2 = line2.split(",");
        StringBuilder sb = new StringBuilder();
        int p1 = 0, p2 = 0;
        while (p1 < strs1.length && p2 < strs2.length) {
            if (Integer.parseInt(strs1[p1])




    
 < Integer.parseInt(strs2[p2])) {
                sb.append(strs1[p1++]);//p++;
            } else {
                sb.append(strs2[p2++]);//q++;
            sb.append(",");
        while (p1 < strs1.length) {
            sb.append(strs1[p1++]).append(",");
        while (p2 < strs2.length) {
            sb.append(strs2[p2++]).append(",");
        System.out.println(sb.substring(0, sb.length() - 1).toString());
KS14 字符串包含
 
我们定义字符串包含关系：字符串A=abc，字符串B=ab，字符串C=ac，则说A包含B，A和C没有包含关系。
输入描述:
 
两个字符串，判断这个两个字符串是否具有包含关系，测试数据有多组，请用循环读入。
输出描述:
 
如果包含输出1，否则输出0.
abc ab
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
public class Main {
    public static void main(String[] args) throws IOException {
        BufferedReader bf = new BufferedReader(new InputStreamReader(System.in));
        String str;
        //只要较长的字符串能包含较短的字符串就行
        while ((str = bf.readLine()) != null) {
            String[] s = str.split(" ");
            System.out.println((s[0].length() > s[1].length() ? s[0].contains(s[1]) : s[1].contains(s[0])) ? 1 : 0);
KS15 魔法深渊
 
前几个月放映的头号玩家简直火得不能再火了，作为一个探索终极AI的研究人员，月神自然去看了此神剧。
由于太过兴奋，晚上月神做了一个奇怪的梦，月神梦见自己掉入了一个被施放了魔法的深渊，月神想要爬上此深渊。
已知深渊有N层台阶构成（1 <= N <= 1000)，并且每次月神仅可往上爬2的整数次幂个台阶(1、2、4、....)，请你编程告诉月神，月神有多少种方法爬出深渊
输入描述:
 
输入共有M行，(1<=M<=1000)
第一行输入一个数M表示有多少组测试数据，
接着有M行，每一行都输入一个N表示深渊的台阶数
输出描述:
 
输出可能的爬出深渊的方式
为了防止溢出，可将输出对10^9 + 3取模
import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.io.IOException;
public class Main {
    static int mod = (int) (1e9 + 3);
    static public void main(String[] args) throws IOException {
        BufferedReader reader = new BufferedReader(new InputStreamReader(System.in));
        int m = Integer.parseInt(reader.readLine());
        int[] ni = new int[m];
        int maxN = 0;
        for (int i = 0; i < m; i++) {
            ni[i] = Integer.parseInt(reader.readLine());
            if (ni[i] > maxN) {
                maxN = ni[i];
        reader.close();
        int[] count = new int[maxN + 1];
        count[0] = 1;
        for (int step = 1; step < maxN + 1; step++) {
            int diff = 1;
            while (step >= diff) {
                count[step] += count[step - diff];
                count[step] %= mod;
                diff <<= 1;
        for (int i = 0; i < m; i++) {
            System.out.println(count[ni[i]]);
KS16 善变的同伴
 
又到了吃午饭的时间，你和你的同伴刚刚研发出了最新的GSS-483型自动打饭机器人，现在你们正在对机器人进行功能测试。
为了简化问题，我们假设午饭一共有N个菜，对于第i个菜，你和你的同伴对其定义了一个好吃程度（或难吃程度，如果是负数的话……）A[i]，
由于一些技（经）术（费）限制，机器人一次只能接受一个指令：两个数L, R——表示机器人将会去打第L~R一共R-L+1个菜。
本着不浪费的原则，你们决定机器人打上来的菜，含着泪也要都吃完，于是你们希望机器人打的菜的好吃程度之和最大
然而，你善变的同伴希望对机器人进行多次测试（实际上可能是为了多吃到好吃的菜），他想知道机器人打M次菜能达到的最大的好吃程度之和
当然，打过一次的菜是不能再打的，而且你也可以对机器人输入-1, -1，表示一个菜也不打
输入描述:
 
第一行：N, M
第二行：A[1], A[2], ..., A[N]
输出描述:
 
一个数字S，表示M次打菜的最大好吃程度之和
1 2 3 -2 3 -10 3
[1 2 3 -2 3] -10 [3]
1 2 3 -2 3 -10 3
[1 2 3] -2 [3] -10 [3]
第四次给机器人-1, -1的指令
N <= 10^5 = 100000
|A[i]| <= 10^4 = 10000
10%数据M = 1
50%数据M <= 2
80%数据M <= 100
100%数据M <= 10^4 = 10000
import




    
 java.io.*;
import java.util.*;
t3 (t3 > t2, 合并 b2 至 t3, 合并后如果次数还有多，就要把合并损失的还回去，记录栈内所有 bi-1 - ti)
*        t1           /\
*   t0   /\     t2   /
*    \  /  \    /\  /
*     \/    \  /  \/
*     b1     \/   b3
*            b2 (b2 < b1, 截断 t1 至 b2部分，因为这段负数影响已经大于之前的总和，记录栈内所有 ti - bi)
public class Main {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        String[] line = br.readLine().split(" ");
        int N = Integer.parseInt(line[0]);
        int M = Integer.parseInt(line[1]);
        line = br.readLine().split(" ");
        int[] dish = new int[N + 1];
        for (int i = 1; i <= N; i++) {
            dish[i] = dish[i - 1] + Integer.parseInt(line[i - 1]);
        PriorityQueue<Integer> maxHeap = new PriorityQueue<>((n1, n2) -> n2 - n1);
        Deque<Integer> bs = new LinkedList<>();
        Deque<Integer> ts = new LinkedList<>();
        int n = N + 1, b, t = 0, res = 0;
        while (t < n) {
            while (!bs.isEmpty() && dish[b] < dish[bs.peek()]) {
                maxHeap.add(dish[ts.pop() - 1] - dish[bs.pop()]);
            bs.push(b);
            ts.push(t);
        while (M-- > 0 && !maxHeap.isEmpty()) {
            res += maxHeap.poll();
        System.out.println(res);
KS17 字符串归一化
 
通过键盘输入一串小写字母(a~z)组成的字符串。
请编写一个字符串归一化程序，统计字符串中相同字符出现的次数，并按字典序输出字符及其出现次数。
例如字符串"babcc"归一化后为"a1b2c2"
输入描述:
 
每个测试用例每行为一个字符串，以'\n'结尾，例如cccddecca
输出描述:
 
输出压缩后的字符串ac5d2e
dabcab
a2b2c1d1
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
/*本题想到了用StringBuilder输出以及比较ASCII码的值来统计数目*/
public class Main {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        String str = br.readLine().trim();
        char[] arr = str.toCharArray();
        int[] a = new int[26];
        for (char c : arr) {
            // 这一步是总体思路
            a[c - 'a']++;
        StringBuilder sb = new StringBuilder();
        for (int i = 0; i < a.length; i++) {
            if (a[i] != 0) {
                sb.append((char) (i + 'a'));
                sb.append(a[i]);
        System.out.println(sb.toString());
KS18 a/b
 
求a/b的小数表现形式。如果a可以整除b则不需要小数点。如果是有限小数，则可以直接输出。如果是无限循环小数，则需要把小数循环的部分用"()"括起来。
输入描述:
 
两个整数a和b，其中
0 <= a <= 1000 000
1 <= b <= 10 000
输出描述:
 
一个字符串，该分数的小数表现形式
10/1 = 10
1/2 = 0.5
####示例3
0.(3)
1/3 = 0.333333...
0.1(6)
1/6 = 0.16666666....
0.(142857)
1 / 7 = 0.1428571428...
import java.io.




    
BufferedReader;
import java.io.InputStreamReader;
import java.io.IOException;
import java.util.HashMap;
public class Main {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        String[] strArr = br.readLine().trim().split(" ");
        int a = Integer.parseInt(strArr[0]);
        int b = Integer.parseInt(strArr[1]);
        StringBuilder sb = new StringBuilder();
        sb.append(a / b);
        if (a % b != 0) {
            a %= b;
            sb.append(".");
            HashMap<Integer, Integer> map = new HashMap<>();
            while (a != 0) {
                a *= 10;
                if (map.containsKey(a)) {
                    // 这个被除数出现过，循环开始
                    sb.insert(map.get(a), "(");     // 在这个数最初出现的位置前面加上左括号
                    sb.append(")");                 // 在当前位置加上右括号
                    break;
                // 被除数没出现过，记录该数及其位置
                map.put(a, sb.length());
                sb.append(a / b);     // 加入商
                a %= b;               // 继续计算余数
        System.out.println(sb.toString());
KS19 最小代价爬楼梯
 
你需要爬上一个N层的楼梯，在爬楼梯过程中， 每阶楼梯需花费非负代价，第i阶楼梯花费代价表示为cost[i]， 一旦你付出了代价，你可以在该阶基础上往上爬一阶或两阶。
你可以从第 0 阶或者 第 1 阶开始，请找到到达顶层的最小的代价是多少。
N和cost[i]皆为整数，且N∈[2,1000]，cost[i]∈ [0, 999]。
输入描述:
 
输入为一串半角逗号分割的整数，对应cost数组，例如
10,15,20
输出描述:
 
输出一个整数，表示花费的最小代价
1,100,1,1,1,100,1,1,100,1
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
public class Main {
    public static void main(String[] args) throws IOException {
        BufferedReader reader = new BufferedReader(new InputStreamReader(System.in));
        String[] num = reader.readLine().split(",");
        int[] dp = new int[num.length];
        dp[0] = Integer.parseInt(num[0]);
        dp[1] = Integer.parseInt(num[1]);
        for (int i = 2; i < dp.length; i++) {
            int c = Integer.parseInt(num[i]);
            dp[i] = Math.min(dp[i - 1] + c, dp[i - 2] + c);
        System.out.println(Math.min(dp[num.length - 1], dp[num.length - 2]));
KS20 字符串压缩
 
对字符串进行RLE压缩，将相邻的相同字符，用计数值和字符值来代替。例如：aaabccccccddeee，则可用3a1b6c2d3e来代替。
输入描述:
 
输入为a-z,A-Z的字符串，且字符串不为空，如aaabccccccddeee
输出描述:
 
压缩后的字符串，如3a1b6c2d3e
aaabccccccdd
3a1b6c2d
import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.io.IOException;
public class Main {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        String str;
        while ((str = br.readLine()) != null) {
            str = str.trim();
            int count = 1;
            StringBuilder result = new StringBuilder();
            for (int i = 1; i < str.length(); i++) {
                if (str.charAt(i) == str.charAt(i - 1))
                    count++;
                else {
                    result.append(count).append(str.charAt(i - 1));
                    count = 1;
            result.append(count).append(str.charAt(str.length() - 1));
            System.out.println(result.toString());
KS21 解析加减法运算
 
解析加减法运算
输入字符串："1+2+3" 输出："6"
输入字符串："1+2-3" 输出："0"
输入字符串："-1+2+3" 输出："4"
输入字符串："1" 输出："1"
输入字符串："-1" 输出："-1"
已知条件：输入的运算都是整数运算，且只有加减运算
要求：输出为String类型，不能使用内建的eval()函数
输入描述:
 
输入字符串："1+2+3"
输出描述:
 
输出："6"
1+2+3
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.*;
public class Main {
    public static void main(String[] args) throws IOException {
        BufferedReader bf = new BufferedReader(new InputStreamReader(System.in));
        String str = bf.readLine();
        bf.close();
        int res = 0, start = 0, pos = 1;
        for (; pos < str.length(); pos++) {
            if (str.charAt(pos) == '+' || str.charAt(pos) == '-') {
                res += Integer.parseInt(str.substring(start, pos));
                start = pos;
        res += Integer.parseInt(str.substring(start, pos));
        System.out.println(res);
KS22 求连续子数组的最大和
 
一个非空整数数组，选择其中的两个位置，使得两个位置之间的数和最大。
如果最大的和为正数，则输出这个数；如果最大的和为负数或0，则输出0
输入描述:
 
3,-5,7,-2,8
输出描述:
 
-6,-9,-10
import java.util.Scanner;
import java.util.*;
import java.io.*;
// 注意类名必须为 Main, 不要有任何 package xxx 信息
public class Main {
    public static void main(String[] args) throws IOException {
        BufferedReader bf = new BufferedReader(new InputStreamReader(System.in));
        String[] str = bf.readLine().split(",");
        int max = 0;
        int cur = 0;
        for (String s : str) {
            cur = Math.max(Integer.parseInt(s) + cur, 0);
            max = Math.max(max, cur);
        System.out.println(max);
KS23 非递减序列
 
对于一个长度为n的整数序列，你需要检查这个序列是否可以是非递减序列，假如你最多可以改变其中的一个数。
非递减序列的定义是：array[i]<=array[i+1], for 1<=i<n;