第一题

题目描述:

小美想要买糖果店的一根长长的糖果，糖果店顾客可以从中选取一个位置然后老板会在那切断，糖果前端到那个切断位置的糖果就会出售给这位顾客。这个糖果其实不同段有着不同的口味，小美希望她选出来的糖果中各个段有着不同的口味，在这基础上希望能选出尽可能长的糖果。小美想知道她能买到最长多长的糖果，请你帮帮她。

输入描述

第一行1个整数n，表示糖果的长度。

第二行n个整数a1a2...an，其中ai表示从糖果前端开始第i段的口味，每段均1为单位长度。

对于100%的数据，1<=n<=50000，1<=ai<=50000

输出描述

输出一行一个整数表示能买到的糖果的最长长度，且其中不包含相同口味.

样例输入

1 2 3 3 4

样例输出

提示

如果我们买长度为4的糖果，包含的口味为[1,2,3,3]，存在了重复。

而长度为3时，包含的口味为[1,2,3]，不存在重复。因此长度3为最长的不存在重复口味糖果长度。

思路：哈希解法去重即可，理解清楚题目，不要被绕进去就行，可能会理解错成滑动窗口题目

public static void main(String[] args) {

//1.不同段有不同的口味

//2.选尽可能长的糖果

//3.最多能买多长的糖果(价格最优，口味不能重复)

Scanner sc = new Scanner(System.in);

int arrayLength = sc.nextInt();

int i = 0;

int [] array = new int[arrayLength];

while (i<arrayLength){

array[i] = sc.nextInt();

i++;

}

int maxLength=0;

Map<Integer,Boolean> map = new HashMap<>();

for (int j = 0; j < array.length; j++) {

if (!map.containsKey(array[j])) {

map.put(array[j],true);

maxLength++;

}else {

break;

}

System.out.println(maxLength);

}

第二题

题目描述:

酷酷的小明准备和小伙伴们展示他捏出来的超酷的橡皮泥士兵。在展示之前，小明发现有些橡皮泥士兵大小十分相似甚至相同，这让小明感觉不是很酷，因为小明想要他的橡皮泥作品都有自己的风格，即使是大小也要有区别。小明的n个橡皮泥士兵的大小分别为a1,a2...an，小明可以通过给某个士兵加一单位皮泥来使得其大小增加一单位。小明想知道如果他想要让所有的橡皮泥士兵大小都不相同，至少需要一共加多少单位橡皮泥。

输入描述

第一行1个整数n，表示小明的橡皮泥士兵数量.

第二行n个整数a1a2...an，分别表示小明的橡皮泥士兵的大小。

对于100%的数据，1<=n<=50000,1<=ai<=100000

输出描述

输出一行一个整数表示总共至少加多少单位的橡皮泥.

样例输入

1 1 2 3 3

样例输出

提示

我们给一个大小为1的橡皮泥士兵增加4单位像皮泥，大小变为5;

再给一个大小为3的橡皮泥士兵增加1单位像皮泥，大小变为4。

此时橡皮泥士兵们的大小分别为1、2、3、4、5，没有两个橡皮泥士兵拥有相同大小了。

可以证明没有更优方案。

思路：同样是哈希思想，把重复的橡皮泥士兵单独拿出来累加橡皮泥单位，然后统计次数即可

public static void main(String[] args) {

//1.通过给所有橡皮泥士兵加单位橡皮泥从而实现不同橡皮泥不同的风格

//2.至少需要加多少单位橡皮泥才能实现这个目标

Scanner sc = new Scanner(System.in);

int arrayLength = sc.nextInt();

int i = 0;

int [] array = new int[arrayLength];

while (i<arrayLength){

array[i] = sc.nextInt();

i++;

}

//通过Map获取重复大小的橡皮泥,重复大小的橡皮泥就是要变化大小的橡皮泥

int mixNum=0;

List<Integer> list = new ArrayList<>();

Map<Integer,Boolean> map = new HashMap<>();

for (int j = 0; j < array.length; j++) {

if (map.containsKey(array[j])){

list.add(array[j]);

}else {

map.put(array[j],true);

}

for (int k = 0; k < list.size(); k++) {

Integer item = list.get(k);

while (map.containsKey(item)){

item = item+1;

mixNum++;

}

//已经累加到不重复的橡皮泥要加入到map集合中

map.put(item,true);

}

System.out.println(mixNum);

}

第三题

题目描述:

小明有一个数组。他挑选了一个有理数u/v，现在他想知道这个数组有多少个子区间的平均值恰好等于u/v。数组的子区间即是数组中连续的一段区间，如数组[4,2,6]有6个子区间[4],[2],[6],[4,2],[2,6],[4,2,6]。

输入描述

第一行有三个整数n,u,v(1<=n,v<=100000,1<=u<=n*v)，代表数组的长度，小明选择的有理数的分子和分母。输入保证u和v的最大公因数是1，即u/v是最简分数。

第二行有n个绝对值不超过1000000的整数，代表数组中的元素。

数字间两两有空格阳开。

输出描述

输出一个非负整数，代表所求的答案

样例输入

6 5 2

2 4 1 3 2 3

样例输出

思路：暴力获取所有连续子区间，然后子区间内部累加判断，但不知道为什么AC率只有18%，有木有懂哥指点一下

我的代码

public static void main(String[] args) {

Scanner sc = new Scanner(System.in);

int arrayLength = sc.nextInt();

double u = sc.nextDouble();

double v = sc.nextDouble();

double result = u/v;

int i = 0;

int [] array = new int[arrayLength];

while (i<arrayLength){

array[i] = sc.nextInt();

i++;

}

double numLength=1;

double sum=0;

int record=0;

//暴力获取所有连续子区间，子区间的长度为1开始，逐渐累加到数组的长度

for (int j = 0; j < array.length && numLength<=array.length; j++) {

int num = 0;

for (int k =0; k < array.length; k++) {

sum = sum+array[k];

num++;

//拼凑出一个子区间则计算其平均值

if (num == numLength){

if (sum/numLength == result){

record++;

}

num=0;

sum = 0;

if (numLength>=2){

k--;

}

sum=0;

j=0;

numLength++;

}

System.out.println(record);

}

微众银行笔试

第一题

第二题

第三题