拼多多2019寻梦计划——笔试题

笔试试题类型:是1到基础题+1道搜索题+1道找规律( 数学计算 )题+1道LeetCode题( 测试用例数据规模分层 )。

第1道

读入一个数列和N值,返回按优先级排序的N个数,满足
(1)所有偶数优先级大于奇数
(2)同为偶数或同为奇数时,数值大的优先级高

输入描述:

每个测试输入的测试用例,包含一个用半角逗号(,)分开的自然数数列和1个参数N,数列和参数N用半角分号(;)隔开这里保证N小于数列的元素个数(不超过100)。

输出描述:

在一行内输出N个满足题目条件的自然数,用逗号隔开

示例1

输入:

555503,772867,756893,339138,399447,40662,859037,628085,855723,974471,599631,636153,581541,174761,948135,411485,554033,858627,402833,546467,574367,360461,566480,755523,222921,164287,420256,40043,977167,543295,944841,917125,331763,188173,353275,175757,950417,284578,617621,546561,913416,258741,260569,630583,252845;10

输出:

913416,566480,420256,339138,284578,40662,977167,974471,950417,948135
import java.util.ArrayList;
import java.util.Collections;
import java.util.List;
import java.util.Scanner;

public class Main {
    public static void main(String args[]) {
        Scanner sc = new Scanner(System.in);
        String line = sc.next();
        String[] split = line.split(";");
        int N = Integer.valueOf(split[1]);
        String[] nums = split[0].split(",");
        List<Long> nums_1 = new ArrayList<>();
        List<Long> nums_2 = new ArrayList<>();
        for (int i = 0; i < nums.length; i++) {
            long t = Long.valueOf(nums[i]);
            if (t % 2 == 0) {
                nums_2.add(t);
            } else {
                nums_1.add(t);
            }
        }
        Collections.sort(nums_1, Collections.reverseOrder());
        Collections.sort(nums_2, Collections.reverseOrder());
        List<Long> res = new ArrayList<>(N);
        for (int i = 0; i < Math.min(nums_2.size(), N); i++) {
            res.add(nums_2.get(i));
        }
        if (res.size() < N) {
            for (int i = res.size(), j = 0; i < N; i++, j++) {
                res.add(nums_1.get(j));
            }
        }
        for (int i = 0; i < N; i++) {
            if (i == 0)
                System.out.print(res.get(i));
            else
                System.out.print("," + res.get(i));
        }
    }
}

第2道

产品经理小梅喜欢和他的男朋友小白一块玩扑克游戏。每一局,小梅抽取N张扑克牌,自左向右依次排列在桌面上;小白也抽取M(8>=N>=M>=1)张扑克牌,自左向右依次排列在桌面上。
小梅需要进行N个回合,使用手中的扑克牌,组成一个新的扑克牌的序列每个回合,小梅有d、l、r三种策略
选择d时,小梅将最左边的扑克牌丢弃
选择l时,小梅将最左边的扑克牌取出,放到新的扑克牌序列的最左边
选择r时,小梅将最左边的扑克牌取出,放到的扑克牌序列的最右边
N个回合完成,新的扑克牌序列与小白的扑克牌完全样(只考虑数字,不考虑花色),则小梅胜出
小梅向程序员小岛提了一个需求,希望了解获胜的全部方法。简化起见扑克牌仅包合1-9。

输入描述:

首先,输入数字S,作为局数(1<=10)每一局,分别输入两行字符串,分别代表小梅的抽取的扑克牌(从左向右排列)和小白抽取到的扑克牌(从左向右排列)

输出描述:

对于每一局,在开始和结束,分别输出{和}输出获胜的方法,回合策略的结尾输出一个空格。若存在多个获胜方法,请按字典序的升序输出。

示例1

输入:

3
123
3
123
321
45
67

输出:

{
d d l
d d r
}
{
l l l
r l l
}
{
}

真是刷题少了,一开始都没做出来,每步“有三种策略”,这是明显的搜索题啊。暴力搜索可破。

import java.util.*;

public class Main {
    static List<String> res;
    static Queue<String> road;
    public static void main(String args[]) {
        Scanner sc = new Scanner(System.in);
        int S = sc.nextInt();
        for (int i = 0; i < S; i++) {
            String nums1 = sc.next();
            String nums2 = sc.next();
            res = new ArrayList<>();
            road = new ArrayDeque<>();
            find(nums1, "", nums2);
            printResult(res);
        }
    }

    private static void find(String origin, String now, String target) {
        if (target.equals(now)) {
            if (origin.length() >= 0) {
                for (int i = 0; i < origin.length(); i++) {
                    road.offer("d");
                }
            }
            res.add(String.join(" ",road));
            return;
        }
        if (origin == null || origin.length() == 0) {
            return;
        }

        String left = String.valueOf(origin.charAt(0));
        String norigin = origin.substring(1);

        road.offer("d");
        find(norigin, now, target);
        road.poll();

        road.offer("l");
        find(norigin, left + now, target);
        road.poll();

        road.offer("r");
        find(norigin, now + left, target);
        road.poll();
    }

    private static void printResult(List<String> res) {
        System.out.println("{");
        if (res == null || res.size() == 0) {
            System.out.println("}");
            return;
        } else {
            Collections.sort(res, (o1, o2) -> o1.compareTo(o2));
            for (int i = 0; i < res.size(); i++) {
                String s = res.get(i);
                System.out.println(String.join(" ", s));
            }
        }
        System.out.println("}");
    }
}

第3道

扔n个般子,第i个骰子有可能投掷出Xi种等概率的不同的结果,数字从1到Xi。所有般子的结果的最大值将作为最终结果。求最终结果的期望。

输入描述:

第一行一个整数n,表示有n个骰子。(1<=n<=50)
第二行n个整数,表示每个骰子的结果数xi。(2<=Xi<=50)

输出描述:

输出最终结果的期望,保留两位小数

示例1

输入:

2
2 2

输出:

1.75

这道计算题的技巧是,如计算f(3),将f(2)、f(1)的概率也囊括了进来,从整体上再将先前计算的f(2)、f(1)减去。

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

public class Main {
    static HashMap<Integer, Long> map;
    static int n;
    static int[] a;
    static double[] p;
    public static void main(String args[]) {
        Scanner sc = new Scanner(System.in);
        n = sc.nextInt();
        a = new int[n];
        for (int i = 0; i < n; i++) {
            a[i] = sc.nextInt();
        }
        Arrays.sort(a);
        p = new double[a[a.length - 1] + 1];
        int begin = 0;
        for (int max = 1; max <= a[a.length - 1]; max++) {
            while (a[begin] < max)
                begin ++;
            double p_max = 1.0;
            for (int i = begin; i < n; i++) {
                p_max *= max / (double)a[i];
            }
            p_max -= Arrays.stream(p).sum();
            p[max] = p_max;
        }
        double EX = 0;
        for (int X = 1; X <= a[a.length - 1]; X++) {
            EX += X * p[X];
        }
        System.out.printf("%.2f",EX);
    }
}

第4道

在一块长为n,宽为m的场地上,有n X m个1 X 1的单元格。每个单元格上的数字就是按照从1到n和1到m中的数的乘积。具体如下:
n = 3, m = 3
1 2 3
2 4 6
3 6 9
给出一个查询的值K,求出按照这个方式列举的的数中第k大的值v例如上面的例子里,从大到小为(9,6,6,4,3,3,2,2,1)
k=1,v=9
K=2,v=6
K=3,v=6
...
k=8,v=2
k=9,V=1

输入描述:

只有一行是3个数n,m,k表示场地的宽高和需要查询的k。使用空格隔开

输出描述:

给出第k大的数的值。

示例1

输入:

3 3 4

输出:

4

备注:

【数据范围】
100%的效据
1 <= n,m <= 40000
1 <= k <= n*m
30%的数据
1 <= n, m <= 1000

原是LeetCode改编,668. 乘法表中第k小的数

  • 先用一个数组把所有数存起来,然后用找第K大的方法去算(剑指offer方法),会报内存溢出,超出内存限制。
    • 时间复杂度:O((mn)) 创建表,然后 O(mn log(mn)) 对其进行排序。
    • 空间复杂度:O(mn)存储乘法表。
  • 建堆,会超出时间限制。k和mn的规模达到16*10^8,线性解法也会失效。那就只能log(N)了,这么明显的二分查找
    • 时间复杂度:O(mnlog(k))
    • 空间复杂度:O(k)
    • 有基于堆的改造算法,时间复杂度O(n^2 mlog(n))
  • 从矩阵的对角线入手,从右下角开始z字扫描;当时有这个想法,但自觉笔试时间内还不能达到精细的逻辑控制能力。
  • 现在复盘,猛然醒悟,这不是改造二分查找吗!真想抽自己。
public class Main {
    public static void main(String args[]) {
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt();
        int m = sc.nextInt();
        int k = sc.nextInt();
        int low = 1, high = m * n;
        while (low < high) {
            int mid = (low + high) / 2;
            int cnt = 0;
            for (int i = 1; i <= n; i++) {
                cnt += (mid / i > m) ? 0 : m - mid / i;
            }
            if (cnt < k) high = mid;
            else low = mid + 1;
        }
        System.out.println(low);
    }
}

发布者

jahentao

挖掘概念,创造工具