暑期算法打卡----第一天

1、三个数的最大乘积

题目：力扣

给你一个整型数组 nums ，在数组中找出由三个数组成的最大乘积，并输出这个乘积。

示例 1：

输入：nums = [1,2,3]
输出：6

示例 2：

输入：nums = [1,2,3,4]
输出：24

示例 3：

输入：nums = [-1,-2,-3]
输出：-6

提示：

3 <= nums.length <= 104
 -1000 <= nums[i] <= 1000

题解：

import javax.swing.plaf.basic.BasicInternalFrameTitlePane;
import javax.xml.transform.sax.SAXTransformerFactory;
import java.util.Arrays;
import java.util.Scanner;

/**
 * @author yx
 * @date 2022-07-02 10:05
 */
public class lc_628三个数的最大乘积 {
    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);
        int i=scanner.nextInt();
        int[] nums=new int[i];
        for (int j = 0; j < i; j++) {
            nums[j]=scanner.nextInt();
        }
    }
    static int  maximumProduct(int[] nums,int n) {
        Arrays.sort(nums);//sort使用的是升序排序
        System.out.print("排序后的数组：");
        for (int i = 0; i < nums.length; i++) {
            System.out.print(nums[i]+" ");
        }
        return(Math.max(nums[0]*nums[1]*nums[n-1],nums[n-1]*nums[n-2]*nums[n-3]));
    }
}

解析：

这个题目我们其实只需要考虑三种情况：

1、给的数组全是正数

 这种情况下我们直接sort排序，取末尾三个最大的数相乘就好了

2、给的数组全是负数

 这种情况我们直接sort排序，也是取末尾最大的三个数相乘

3、给的数组一半是正数一半是负数

 这种情况，可以是两个最小的负数相乘（相乘之后得到的正数为最大值），然后再乘上一个最大的正数，得到的即为为最大值

2、有多少小于当前数字的数字

题目：力扣

给你一个数组 nums，对于其中每个元素 nums[i]，请你统计数组中比它小的所有数字的数目。

换而言之，对于每个 nums[i] 你必须计算出有效的 j 的数量，其中 j 满足 j != i 且 nums[j] < nums[i]

以数组形式返回答案。

示例 1：

输入：nums = [8,1,2,2,3]
输出：[4,0,1,1,3]
解释：
对于 nums[0]=8 存在四个比它小的数字：（1，2，2 和 3）。
对于 nums[1]=1 不存在比它小的数字。
对于 nums[2]=2 存在一个比它小的数字：（1）。
对于 nums[3]=2 存在一个比它小的数字：（1）。
对于 nums[4]=3 存在三个比它小的数字：（1，2 和 2）。

示例 2：

输入：nums = [6,5,4,8]
输出：[2,1,0,3]

示例 3：

输入：nums = [7,7,7,7]
输出：[0,0,0,0]

提示：

2 <= nums.length <= 500
 0 <= nums[i] <= 100

题解：

import java.lang.reflect.Array;
import java.util.*;

/**
 * @author yx
 * @date 2022-07-02 10:51
 */
public class lc_1365有多少小于当前数字的数字 {
    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);
        int i=scanner.nextInt();
        int[] nums=new int[i];
        for (int j = 0; j < i; j++) {
            nums[j]=scanner.nextInt();
        }
        smallerNumbersThanCurrent(nums);
    }
    static public void smallerNumbersThanCurrent(int[] nums) {
        int []ans=Arrays.copyOf(nums,nums.length);
        Arrays.sort(ans);
        // 用一个hashmap存数组内容和下标
        Map<Integer,Integer> map=new HashMap<>();
        for (int i = 0; i < ans.length; i++) {
            if (!map.containsKey(ans[i])) {//解决数字出现重复的情况
                map.put(ans[i],i);
            }
        }
        for (int i = 0; i < nums.length; i++) {
            nums[i]=map.get(nums[i]);
//            System.out.print(nums[i]);
        }
    }
}

解析：

这道题目我找到了一个通俗易懂的解法，参考“代码随想录”的题解！

1、首先们先用一下Arrays的copy方法，复制一下数组

2、对数组进行排序

3、我们会发现排序完后的数组其值对应的下标也就是比它小的数值个数，所以我们直接构造一个HashMap将排序后的值保存在map中，然后通过map去搜一遍原数组nums就可以了

4、这个地方有一个关键，就是当原数组中有重复元素我们应该如何去处理，这个好办法就是不处理，把它们重复的看成一个就好了

3、使数组唯一的最小增量

题目：力扣

给你一个整数数组 nums 。每次 move 操作将会选择任意一个满足 0 <= i < nums.length 的下标 i，并将 nums[i] 递增 1。

返回使 nums 中的每个值都变成唯一的所需要的最少操作次数。

示例 1：

输入：nums = [1,2,2]
输出：1
解释：经过一次 move 操作，数组将变为 [1, 2, 3]。

示例 2：

输入：nums = [3,2,1,2,1,7]
输出：6
解释：经过 6 次 move 操作，数组将变为 [3, 4, 1, 2, 5, 7]。
可以看出 5 次或 5 次以下的 move 操作是不能让数组的每个值唯一的。
提示：

1 <= nums.length <= 105
 0 <= nums[i] <= 105

题解：

package 暑期特训__社区;

import java.util.Arrays;
import java.util.Scanner;

/**
 * @author yx
 * @date 2022-07-02 12:14
 */
public class lc_945使数组唯一的最小增量 {
    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);
        int n=scanner.nextInt();
        int[] nums=new int[n];
        for (int i = 0; i < n; i++) {
            nums[i]=scanner.nextInt();
        }
        minIncrementForUnique(nums);
    }
    static public void minIncrementForUnique(int[] nums) {
        int ans=0;//记录操作次数
        Arrays.sort(nums);
        for (int i = 1; i < nums.length; i++) {
            if(nums[i]<=nums[i-1]){
                ans+=nums[i-1]-nums[i]+1;
                nums[i]=nums[i-1]+1;
            }
        }
        System.out.println(ans);
    }
}

解析：

1、首先将数组进行排序，然后从左到右遍历数组

2、如果当前元素大于上一个元素，保持不变
3、如果当前元素小于等于上一个元素，就需要增加当前元素的值+1，比前一个数大1就好，这个时候ans操作次数要记录下当前值前后变化的差值，存入ans，逐一往后遍历，累计差值，最后输出即可

4、B. Rising Sand

题目：Problem - B - Codeforces

B. Rising Sand

time limit per test

1 second

memory limit per test

256 megabytes

input

standard input

output

standard output

There are n

piles of sand where the i-th pile has ai blocks of sand. The i-th pile is called too tall if 1<i<n and ai>ai−1+ai+1

. That is, a pile is too tall if it has more sand than its two neighbours combined. (Note that piles on the ends of the array cannot be too tall.)

You are given an integer k

. An operation consists of picking k consecutive piles of sand and adding one unit of sand to them all. Formally, pick 1≤l,r≤n such that r−l+1=k. Then for all l≤i≤r, update ai←ai+1

.

What is the maximum number of piles that can simultaneously be too tall after some (possibly zero) operations?

Input

The input consists of multiple test cases. The first line contains an integer t

(1≤t≤1000

) — the number of test cases. The description of the test cases follows.

The first line of each test case contains two integers n

and k (3≤n≤2⋅105; 1≤k≤n

) — the number of piles of sand and the size of the operation, respectively.

The second line of each test case contains n

integers a1,a2,…,an (1≤ai≤109

) — the sizes of the piles.

It is guaranteed that the sum of n

over all test cases does not exceed 2⋅105

.

Output

For each test case, output a single integer — the maximum number of piles that are simultaneously too tall after some (possibly zero) operations.

Example

Input

Copy

3
5 2
2 9 2 4 1
4 4
1 3 2 1
3 1
1 3 1

Output

Copy

2
0
1

Note

In the first test case, we can perform the following three operations:

• Add one unit of sand to piles 1

and 2: [3,10,2,4,1]

• .
• Add one unit of sand to piles 4
• and 5: [3,10,2,5,2]
• .
• Add one unit of sand to piles 3
• and 4: [3,10,3,6,2] - . Now piles 2 and 4 are too tall, so in this case the answer is 2. It can be shown that it is impossible to make more than 2 piles too tall. In the second test case, any operation will increase all piles by 1 unit, so the number of too tall piles will always be 0 .In the third test case, we can increase any pile by 1 unit of sand. It can be shown that the maximum number of too tall piles is 1.

题解：

package 暑期特训__社区;

import java.util.Scanner;

/**
 * @author yx
 * @date 2022-07-02 16:07
 */
public class cf_B_RisingSand {
        public static void main (String[]args){
            Scanner scanner = new Scanner(System.in);
            int t = scanner.nextInt();
            for (int j = 0; j < t; j++) {
                int n = scanner.nextInt();
                int k = scanner.nextInt();
                int[] a = new int[n];
                for (int i = 0; i < n; i++) {
                    a[i] = scanner.nextInt();
                }
                if (k == 1) {
                    System.out.println((n - 1) / 2);
                    continue;
                }
                int ans = 0;
                for (int i = 1; i < n - 1; i++) {
                    if (a[i] > a[i - 1] + a[i + 1]) ans++;
                }
                System.out.println(ans);
            }
        }
}

解析：

首先，这个题目来源于codeforce，老毛子搭的网站，面向全世界的算法爱好者，题目很棒，但是因为是英文的看的我着实头疼，大家可以借用谷歌翻译或者查字典（狗头保命），有要参加ICPC的小伙伴可以提前适应起来了

1、先给大家翻译一下原题吧，让大家好理解一些，这个地方引用一下梗子的翻译理解，我觉得很棒：

“第四题题意：给你n个柱子，如果一个柱子旁边两个柱子加起来都没它高，说明它是一个特别高的柱子，你会魔法，可以将连续k个柱子都变高1米，魔法不限次数，问你最多能让数组出现多少个特别高的柱子”

2、这道题目最关键的点就是k，当k=1时特判一下即可，把数字可以直接全部变成ABABABA类型（B>A），这个时候特别高的柱子数量为3

3、当k≠1时，直接不操作，在原数组上判断有多少个特别高的柱子即可，至于为什么直接不操作做呢，这个地方还是引用梗子的证明：

“k个柱子都+1了，先考虑中间被加的柱子，它加了1，但是它相邻的也都+1，导致它更加不可能大于相邻的和。再考虑k个柱子头尾的柱子，它加了1，但它旁边也有一根+1了，所以和相邻的柱子的和差不会改变”

说在最后✏️

算法暑期打卡快乐每一天，如果觉得我的题解对您有帮助的话，欢迎一键三联！