微众银行秋招笔试真题解析

文章正文
发布时间:2024-07-17 12:52

微众银行秋招笔试真题解析

2023-09-09 10:02

发布于:河北省

大家好,我是吴师兄,关注我,每周更新大厂最新笔试题解析。

题目描述

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

输入描述

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

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

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

输出描述

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

示例一输入5

1 2 3 3 4

输出3

说明

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

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

解题思路

题目乍一看是LeetCode3、无重复字符的最长子串原题,但要注意审题和题目场景,还挺坑的。

题目要求只能从糖果的前端出发开始切一刀,所以无需进行滑窗,只需要判断从起始位置开始的最长无重复子数组即可,故直接使用哈希集合即可完成。

代码# 题目:【哈希集合】微众银行2023秋招-切糖果

# 作者:闭着眼睛学数理化

# 算法:哈希集合

# 代码有看不懂的地方请直接在群上提问

n = int(input)

nums = list(map(int, input.split))

hash_set = set

# 遍历数组nums中的每一个元素num

fornum innums:

# 若num从未出现过,则加入哈希集合中

ifnum notinhash_set:

hash_set.add(num)

# 若num出现过,则直接退出循环

else:

break

# 退出循环后,哈希集合的长度即为答案

print(len(hash_set))

Javaimportjava.util.HashSet;

importjava.util.Scanner;

importjava.util.Set;

publicclassMain{

publicstaticvoidmain(String[] args){

Scanner scanner = newScanner(System.in);

intn = scanner.nextInt;

int[] nums = newint[n];

for(inti = 0; i < n; i++) {

nums[i] = scanner.nextInt;

}

Set<Integer> hashSet = newHashSet<>;

intcount = 0;

for(intnum : nums) {

if(!hashSet.contains(num)) {

hashSet.add(num);

count++;

} else{

break;

}

}

System.out.println(count);

}

}

C++#include<iostream>

#include<unordered_set>

#include<vector>

usingnamespacestd;

intmain{

intn;

cin>> n;

vector<int> nums(n);

for(inti = 0; i < n; i++) {

cin>> nums[i];

}

unordered_set<int> hashSet;

intcount = 0;

for(intnum : nums) {

if(hashSet.find(num) == hashSet.end) {

hashSet.insert(num);

count++;

} else{

break;

}

}

cout<< count << endl;

return0;

}

时空复杂度

时间复杂度:O(N)。最差的情况是遍历整个数组。

空间复杂度:O(N)。哈希集合所需空间。

小结

不知道怎么样开始刷 LeetCode ,那么可以参考我整理的这个刷题路线,历时两年,经历了上千个同学的实操检验。

LeetCode 刷题顺序,看这一篇就够了

看了很多算法视频、参加了很多算法训练营,还是感觉很难入门,那么可以尝试看动画刷 LeetCode 。

看动画刷 LeetCode

刷了很多 LeetCode ,面对大厂的算法真题却一筹莫展,那么建议你提前了解大厂算法面试真题的特点,搭配专属 OJ 平台,有针对性的练习,点击阅读原文一键直达。

OJ 平台:https://oj.algomooc.com/返回搜狐,查看更多

责任编辑: