2021(校招)アリババ7.22筆記試験(Java版)

共有を書くと幸運があるそうです!!
今日の筆記試験には参加しなかったが、問題を見て書いてみた.主にpythonとcのバージョンを見ているので、java版を出して共有したいと思っています(間違いがあれば指摘してください)
タイトル1
1つのnを与えて,[1,n]というn個の数字の配列の組み合わせがどれだけあるかを求める.条件:隣接する2つの数値の絶対値は1に等しくない.例えば:4[2,4,1,3][3,1,4,2]構想:遡及

    static List<List<Integer>> 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<Integer>());
        for(List<Integer> list : res){
            System.out.println(list);
        }
    }
    public static void judge(int n, int[] nums, int index, List<Integer> list){
        if(index == n){
            res.add(new LinkedList<Integer>(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;
            }
        }
    }

タイトル2
長さnの配列であり、配列中の各要素aは、1<=a<=nで連続区間の数を求め、要求区間中の同じ要素の数>=m例えば、5 2 1 2 1 2 1 5 2 4は4つの可能性がある:[1,3],[1,5],[2,5],[1,4]構想:mapで現在数のlist集合を保存し、行き先から遍歴し、m条件に合致するもの、対応する数をresに追加し、現在の数がm条件に合致しないと判断するために変数ptを維持するが、これまでm条件に合致する数が現れた最初の数の下付き

    public static void main(String[] args) {
        Scanner scan = new Scanner(System.in);
        int N = scan.nextInt();//  
        int m = scan.nextInt();//     
        Map<Integer, List<Integer>> 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<Integer> list = new LinkedList<>();
                list.add(i);
                map.put(num, list);
            }
            res += pt + 1;
        }
        System.out.println(res);
    }

ここにもpython版を添付しましょう(python版はこのお兄さんの)

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))

質問があればコメントに返信して、基本秒回!