千锤百炼之每日算法(三)

题外话

不会再水了,先把算法任务完成!

正题

第一题

简写单词

规定一种对于复合词的简写方式为只保留每个组成单词的首字母,并将首字母大写后再连接在一起
比如“College English Test"可以简写成“CET",“Computer Science' 可以简写为"CS"，I am Bob”简写为“IAB"
输入一个长复合词(组成单词数sum, sum≥1且sum≤100,每个单词长度len,len≥1且len≤50)
请你输出它的简写

第一题思路

1.我们通过单词输入的时候先将字符串转换成大写形式,再通过public char charAt(0)方法,将字符串首字母拿出来即可

第一题代码详解

public void test5(String str)
{
    Scanner in = new Scanner(System.in);
    //首先判断是否还有下一个输入项也就是空格作为分隔符,检查空格后面有没有输入项
    while (in.hasNext()) {
        //将每个输入项转换成大写字母,并且将第一个字符赋值ch
        char ch=in.next().toUpperCase().charAt(0);
//输出字符即可
            System.out.print(ch);
    }
}

第二题

除2!

给一个数组,一共有n个数。
你能进行最多k次操作。每次操作可以进行以下步骤:
选择数组中的一个偶数ai,将其变成ai/2。
现在你进行不超过k次操作后，让数组中所有数之和尽可能小。请输出这个最小的和。

第二题思路

1.首先我们需要sum将所有元素和放入

2.我们每次选取除2的偶数一定是所有元素中最大的偶数,所以我们可以用大根堆,也就是优先级队列

3.我们将所有偶数放入优先级队列中,然后堆顶元素就一定是最大的偶数

4.我们让sum减去堆顶元素取出除2,再判断堆顶元素除2之后是否还是偶数,如果是偶数就放回堆中

第二题代码详解

public long Test6()
{
    Scanner in=new Scanner(System.in);
    //输入n和k
    int n=in.nextInt();
    int k=in.nextInt();

//创建大根堆,这里利用的是lambed表达式
PriorityQueue<Integer> queue=new PriorityQueue<>(( o1,o2)-> o2-o1);

    //创建sum和x注意数据类型,sum用于存放整个数据,x用于判断输入的值是不是偶数
    long sum=0;
    long x=0;

//for循环用于存放n个数据,并且用来判断输入的值是不是偶数
for (int i = 0; i < n; i++) {

//将输入的值放入x中
x = in.nextLong();

//所有元素和放在sum中
sum += x;

//判断输入数据是不是偶数
if (x % 2 == 0) {

            //是偶数放入堆中
            queue.add((int) x);
        }
    }

    //到了这里sum是n个数据的总和,大根堆中全部都是偶数,只要堆不为空并且k不为0就说明里面还有偶数并且还有除2的执行次数
      while (!queue.isEmpty()&&k--!=0)
        {
            //将堆顶元素取出除2放入t中
            long t=queue.poll()/2;

//因为t除2,所以sum要减去t
sum-=t;

            //如果t还是偶数
            if (t%2==0)
            {
                //则继续放入堆中
                queue.add((int)t);
            }
        }

//返回sum即可
return sum;
}

第三题

dd爱框框

读入n，x，给出n个数a[1],a[2],……,a[n]，求最小的区间[l, r]，
使 a[l]+a[l+1]+……+a[r] ≥ x，若存在相同长度区间，输出最小的那个

第三题思路

注意事项!

1.首先我们需要注意这里的n最大已经达到了10^7

2.有些题会造成输入输出超时,我们这里输入元素过于多,输出元素就两个

3.当我们发现输入元素超时的时候,我们就需要利用快读读入代码,大家可以看看我这篇博客

千锤百炼之算法Scanner和System.out引起超时解决办法-CSDN博客

思路

1.首先我们需要用双指针,去记录超过x大小的区间段

2.我们要找到最小超过x大小的区间段,所以还需要两个指针去不断更新超过x大小的区间段

3.如何判断新找到的超过x大小的区间段是否比上一个找到的区间小,我们就需要记录区间段大小

4.注意看我们这里数组是从1下标开始

第三题代码详解

public void test7() throws IOException {
    Read in=new Read();
    //输入n和x
    int n=in.nextInt();
    int x=in.nextInt();

//因为下标从1开始,所以数组元素数量为n+1
int[] arr=new int[n+1];

    //for循环给arr数组赋值
    for (int i=1;i<=n;i++)
    {
        arr[i]=in.nextInt();
    }

//创建双指针让left和right指向1下标
int left=1,right=1;

//创建retlet和retright,让其记录最小的长度区间
int retleft=-1,retright=-1;

//让len记录长度区间大小,先赋值数组长度
int len=n;

//创建sum,让sum进行累加判断是否超过x
int sum=0;

    //当right没有走到数组最后一个元素就继续循环
    while (right<=n)
    {
        //sum累加arr[right]
        sum+=arr[right];
        //当sum大于等于x说明找到了长度区间
        while (sum>=x)
        {
            //如果right-left+1小于len说明这个区间是目前最小长度区间
            if (right-left+1<len)
            {
                //将left下标赋值retleft
                retleft=left;
                //将right下标赋值retright
                retright=right;
                //最后更新长度区间
                len=right-left+1;
            }
            //让sum累减arr[left++],继续续循环判断sum是否仍然大于等于x
            sum-=arr[left++];
        }
       //最后right++即可
        right++;

    }
    //当right走到最后一个元素跳出循环则找到了最小区间,打印出更新的最小区间即可
    System.out.println(retleft+" "+retright);

}
class Read // 自定义快速读入
{
    StringTokenizer st = new StringTokenizer("");
    BufferedReader bf = new BufferedReader(new InputStreamReader(System.in));
    String next() throws IOException
    {
        while(!st.hasMoreTokens())
        {
            st = new StringTokenizer(bf.readLine());
        }
        return st.nextToken();
    }

    String nextLine() throws IOException
    {
        return bf.readLine();
    }

    int nextInt() throws IOException
    {
        return Integer.parseInt(next());
    }

    long nextLong() throws IOException
    {
        return Long.parseLong(next());
    }

    double nextDouble() throws IOException
    {
        return Double.parseDouble(next());
    }
}