S2青铜局第一场 做题记录

S2青铜局做题记录
t1

    public int minDifference (int[] a) {
        Arrays.sort(a);
        int res = Integer.MAX_VALUE;
        for(int i=1;i<a.length;++i){
            //先确认这两个相减不越界
            if(a[i]-a[i-1] >=0){
                res = Math.min(res,a[i]-a[i-1]);
            }
        }
        return res;
    }

t2 主要是越界

    public  long tree4(long n) {
        // write code here
        int mod = 998244353;
        long res = 0;
        long deep = 1;
        long cur = 1;

        while(cur<=n){
            long start = cur;
            long end =Math.min(n,(long)Math.pow(2,deep)-1);
            long num = Math.min(n-start+1,end-start+1);
            //这个地方三次取余
            long tmp = ((end + start) * num / 2)% mod;
            res += (tmp*deep) % mod;
            res=res%mod;
            cur=end+1;
            deep++;
        }
        return (long)res;
    }

t3 就是个字符串加法。。。 排序折腾了半天 最后干脆自己写了个逆序....

    public String Maxsumforknumers (String x, int k) {
        char[] str =x.toCharArray();
        Arrays.sort(str);
        reverse(str,0,str.length-1);

        if(str.length ==k){
            return new String(str);
        }else{

            String one = new String(str,0,str.length-(k-1));

            int otherNum=0;
            for(int cur=str.length-(k-1);cur<str.length;++cur){
                otherNum+= str[cur]-'0';
            }
            return addStrings(one,otherNum+"");
        }

    }

    public String addStrings(String num1, String num2) {
        StringBuilder sb = new StringBuilder();
        int carry = 0, i = num1.length()-1, j = num2.length()-1;
        while(i >= 0 || j >= 0 || carry != 0){
            if(i>=0) carry += num1.charAt(i--)-'0';
            if(j>=0) carry += num2.charAt(j--)-'0';
            sb.append(carry%10);
            carry /= 10;
        }
        return sb.reverse().toString();
    }
    private void reverse(char[] str, int head,int tail){
        while(head <tail){
            swap(str,head,tail);
            head++;
            tail--;
        }
    }

    private void swap(char[] str,int a ,int b){
        char temp =str[a];
        str[a] = str[b];
        str[b]=temp;
    }