首页 > 2021(校招)阿里巴巴 7.22 笔试(Java版)
头像
i`mNB
编辑于 2020-07-22 19:49
+ 关注

2021(校招)阿里巴巴 7.22 笔试(Java版)

听说写分享可以有好运!!

虽然没有参加今天的笔试,但是看到题目写了一下。
主要是看到都是python和c的版本,所以想发一个java版给大家分享(如有错误请指出)

题目一

给定一个n,求 [1,n] 这 n 个数字的排列组合有多少个。
条件:相邻的两个数字的绝对值不能等于1.
例如:
4
[2, 4, 1, 3]
[3, 1, 4, 2]
思路:回溯

    static List> res;
    public static void main(String[] args) {
        res = new LinkedList();
        // write your code here
        Scanner scan = new Scanner(System.in);
        int N = scan.nextInt();
        scan.close();
        int nums[] = new int[N];
        judge(N, nums, 0, new LinkedList());
        for(List list : res){
            System.out.println(list);
        }
    }
    public static void judge(int n, int[] nums, int index, List list){
        if(index == n){
            res.add(new LinkedList(list));
            return;
        }
        for (int i = 1; i <= n; i++) {
            if(nums[i-1] == 0 && (list.size() == 0 || Math.abs(list.get(list.size()-1)-i) != 1)){
                list.add(i);
                nums[i-1] = 1;
                judge(n, nums, index+1, list);
                list.remove(list.size()-1);
                nums[i-1] = 0;
            }
        }
    }

题目二

长度为 n 的数组,数组中每个元素 a 满足:1<=a<=n
求连续区间的数量,要求区间中相同元素的数量 >=m
例如:
5 2
1 2 1 5 2
4
可以有4种可能:[1,3],[1,5],[2,5],[1,4]
思路:用map存一个当前数的list集合,从前往后遍历,符合m条件的,则将对应数量添加到res
并且维护一个变量pt,用来判断当前数不符合m条件,但之前有符合m条件的数出现过的首个数的下标

    public static void main(String[] args) {
        Scanner scan = new Scanner(System.in);
        int N = scan.nextInt();//数量
        int m = scan.nextInt();//相同的个数
        Map> map = new HashMap();
        int res = 0;
        int pt = -1;//记录当前元素num前,存在m个相同元素a的第一个元素的下标。不存在则为-1
        for (int i = 0; i < N; i++) {
            int num = scan.nextInt();
            if(map.containsKey(num)){
                map.get(num).add(i);
                if(map.get(num).size() >= m){
                    int pre = map.get(num).get(map.get(num).size() - m);
                    pt = Math.max(pt, pre);
                }
            }else{
                List list = new LinkedList();
                list.add(i);
                map.put(num, list);
            }
            res += pt + 1;
        }
        System.out.println(res);
    }

这里也附上一个python版吧(python版参考这位老哥的)
https://www.nowcoder.com/discuss/457028?type=post&order=time&pos=&page=1&channel=666&source_id=search_post

import sys
def f(a, m):
    pt = -1
    ans = 0
    pos = [[] for i in range(len(a)+111)]
    for i in range(len(a)):
        v = a[i]
        pos[v].append(i)
        if len(pos[v]) >= m:
            pre_m = pos[v][-m]
            pt = max(pt, pre_m)
        ans += pt+1
    return ans
while True:
    iline = sys.stdin.readline()
    if iline == "":
        break
    n, m = list(map(int, iline.strip().split()))
    a = list(map(int, sys.stdin.readline().strip().split()))
    print(f(a, m))

全部评论

(3) 回帖
加载中...
话题 回帖

相关热帖

历年真题 真题热练榜 24小时
技术(软件)/信息技术类
查看全部

近期精华帖

热门推荐