牛客编程巅峰赛S2第1场 - 青铜&白银&黄金，进阶白银

比赛过程中无法调试，的确很难受
比赛中所有题目都有思路，AC一道，比赛结束后全部AC

A 最小差值
差值的绝对值最小，数组排序，最小差值一定在相邻数的差值中

import java.util.Arrays;

public class Solution {
    // 最小差值
    public int minDifference (int[] a) {
        int res = Integer.MAX_VALUE;
        Arrays.sort(a);
        for(int i = 1; i < a.length; i++) {
            if(a[i] - a[i - 1] < res) {
                res = a[i] - a[i - 1];
            }
        }
        return res;
    }
}

测试用例更改了，只能AC90%
一样的思路，考虑int类型计算的溢出
我以byte类型举例说明计算溢出的原因，-8, -1, 7
7 - (-1) = 8, -1 - (-8) = 7，因此正确结果应该为7，
但是8在byte中溢出为-1，最终结果就会变为-1
注：题目中只说明最终结果在int范围内

import java.util.Arrays;

public class Solution {
    // 最小差值
    public int minDifference (int[] a) {
        // write code here
        long res = Integer.MAX_VALUE;
        Arrays.sort(a);
        for(int i = 1; i < a.length; i++) {
            // 转换为long，保存结果
            long sub = (long)a[i] - (long)a[i - 1];
            if(sub < res) {
                res = sub;
            }
        }
        return (int)res;
    }
}

B Tree IV
考察完全树的基本概念
题目中层数从1计数
第i层共个结点，结点值为到

public class Solution02 {
    public static long tree4 (long n) {
        // write code here
        final int c = 998244353;
        long res = 0;
        int level = 0;
        long node = 0;
        // count level
        while(node <= n) {
            level++;
            node += (long)Math.pow(2, level - 1);
        }
        node = 0;
        // 计算第1层到第i层所有结点的价值
        for(int i = 1; i < level; i++) {
            res = (res + countLevel(i)) % c;
            node += (long)Math.pow(2, i - 1);
        }
        // 计算第node+1到第n个结点的价值
        for(long i = node + 1; i <= n; i++) {
            res = (res + i * level) % c;
        }
        return res;

    }

    // 计算第i层所有结点的价值
    public static long countLevel(int i) {
        final int c = 998244353;
        long base = (long)Math.pow(2, i - 1);
        long res = (2 * base - 1 + base) * base / 2 * i % c;
        return res;
    }

    // 测试用例
    public static void main(String[] args) {
        long n = 2;
        System.out.println(tree4(n)); // 5

        n = 5;
        System.out.println(tree4(n)); // 38
    }
}

C 牛牛组数
取最大的n-(k - 1)字符组成一个数，其余剩余全为一位数，相加即为结果
基数排序

import java.util.Arrays;

public class Solution {
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     * 返回最大和的字符串
     * @param x string字符串 即题目描述中所给字符串
     * @param k int整型 即题目描述中所给的k
     * @return string字符串
     */
    public static String Maxsumforknumers (String x, int k) {
        // write code here
        int[] arr = new int[10];
        for(int i = 0; i < x.length(); i++) {
            arr[x.charAt(i) - '0']++;
        }
        System.out.println(x);
        int idx = 9;
        int[] nums = new int[x.length() - (k - 1) + 1];
        int start = 1;
        for(int j = 1; j <= x.length() - (k - 1); j++) {
            while(arr[idx] == 0) {
                idx--;
            }
            nums[start] = idx;
            arr[idx]--;
            start++;
        }
        System.out.println(Arrays.toString(nums));
        for(int i = 1; i <= k - 1; i++) {
            while(arr[idx] == 0) {
                idx--;
            }
            int add = idx;
            for (int j = nums.length - 1; j >= 0 ; j--) {
                add = add + nums[j];
                nums[j] = add % 10;
                if (add >= 10) {
                    add /= 10;
                } else {
                    break;
                }
            }
            arr[idx]--;
        }
        StringBuilder sb = new StringBuilder();
        if (nums[0] != 0) {
            sb.append(nums[0]);
        }
        for (int i = 1; i < nums.length; i++) {
            sb.append(nums[i]);
        }
        return sb.toString();
    }

    // 测试用例
    public static void main(String[] args) {
        String x = "345";
        int k = 2;
        System.out.println(Maxsumforknumers (x, k)); // 57

        x = "233333";
        k = 3;
        System.out.println(Maxsumforknumers (x, k)); // 3338

        x = "111222333444555666777888999";
        k = 1;
        System.out.println(Maxsumforknumers (x, k)); // 999888777666555444333222111

        x = "999";
        k = 2;
        System.out.println(Maxsumforknumers (x, k)); // 108
    }
}

欢迎各位同学一起讨论！