拼多多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);
    }
}

[搜索]奥特曼打怪兽

题目描述

奥特曼是正义的化身,现在奥特曼需要消灭地图中所有怪鲁,该地图由一个M×M的矩阵组成,地图中的怪兽有不同的难度级别。
0表示陷阱,不能进入
1表示陆地,可以通过
大于等于2的正整数表示各种级别的怪兽,数字越大表示怪兽越强。
现在奥特曼需要按照级别从弱到强消灭地图中所有的怪兽,怪兽一旦被消灭,怪兽所在的地方就变回为陆地。
奥特曼从原地开始(0,0)行动,在地图中只能上下左右移动,那么奥特曼最少需要走多少步才能消灭所有怪兽, 如果无法消灭所有怪曽返回-1。
约束:
1.地图中不会有级别一样的怪兽
2.不允许宾特曼经过一个怪兽而不消灭它
输入描述:
一个由M×M构成的炬阵,3≤M≤50,该矩阵每行数字之间用空格隔开
输出描述:
如果奥特曼能够依次消灭所有怪兽,输出最小步数,如果无法全部消灭输出-1。

输入样例

1 2 0
0 3 4
0 6 5

输出样例

5

思路描述

乍一看,是到搜索题。

等我跑步回来写……

方法一:BFS

#include <bits/stdc++.h>
using namespace std;
class Point{
public:
	int i, j;
	int num;
	Point(int i, int j, int num) {
		this->i = i;
		this->j = j;
		this->num = num;
	}
	Point() {}
	bool operator < (const Point& p) const {
		return num < p.num;
	}
};
int main() {
    freopen("./1.input.txt","r",stdin);
	vector<Point> points;
	Point temp;
	while (cin >> temp.num) {
		points.push_back(temp);
	}
	int m = sqrt(points.size());
	vector<vector<int>> matrix(m, vector<int>(m, 0));
	for (int i = 0; i < m; i++) {
		for (int j = 0; j < m; j++) {
			matrix[i][j] = points[i * m + j].num;
			points[i * m + j].i = i;
			points[i * m + j].j = j;
		}
	}
	sort(points.begin(), points.end());
	temp.num = 1;
	int index = upper_bound(points.begin(), points.end(), temp) - points.begin();
	if (index == points.size()) {
		printf("0\n");
	} else {
		int dir[][2] = { 0, 1, 0, -1, 1, 0, -1, 0 };
		int res = 0;
		Point curPoint{ 0, 0, 0 };
		for (int pIndex = index; pIndex < points.size(); pIndex++) {
			Point &nextPoint = points[pIndex];
			matrix[nextPoint.i][nextPoint.j] = 1;
			queue<Point> que;
			que.push(curPoint);
			vector<vector<bool>> isVis(m, vector<bool>(m, false));
			bool isFind = false;
			while (!que.empty()) {
				Point p = que.front();
				que.pop();
				if (p.i == nextPoint.i && p.j == nextPoint.j) {
					res += p.num;
					isFind = true;
					break;
				}
				for (int i = 0; i < 4; i++) {
					int ii = p.i + dir[i][0];
					int jj = p.j + dir[i][1];
					if (ii >= 0 && ii < matrix.size() && jj >= 0 && jj < matrix[0].size()
						&& matrix[ii][jj] == 1 && isVis[ii][jj] == false) {
						isVis[ii][jj] = true;
						que.push({ ii, jj, p.num + 1 });
					}
				}
			}
			if (isFind == false) {
				res = -1;
				break;
			}
			curPoint.i = nextPoint.i;
			curPoint.j = nextPoint.j;
		}
		printf("%d\n", res);
	}
	return 0;
}

方法二:DFS

#include <bits/stdc++.h>
using namespace std;
class Point {
public:
    int i, j;
    int num;
    Point() {}
    Point(int i, int j, int num) {
        this->i = i;
        this->j = j;
        this->num = num;
    }
    bool operator < (const Point& p) const {
        return num < p.num;
    }
};
const int X[4] = {0, 0, 1, -1};
const int Y[4] = {1, -1, 0, 0};
vector<vector<int> > c;
int m;
void dfs(Point& in, Point& out, int v, int& minv,  vector<vector<bool> >& vis) {
    if(in.i == out.i && in.j == out.j) {
        if(v < minv) {
            minv = v;
            return;
        }
    }
    vis[in.i][in.j] = true;
    for(int i=0; i<4; i++) {
        int ni = in.i + X[i];
        int nj = in.j + Y[i];
        if (ni>=0 && nj>=0 && ni<m && nj<m && c[ni][nj]==1 && !vis[ni][nj]) {
            Point next;
            next.i = ni, next.j = nj;
            next.num = in.num + 1;
            dfs(next, out, v+1, minv, vis);
        }
    }
    vis[in.i][in.j] = false;
}
int main(void) {
    freopen("./1.input.txt","r",stdin);
    vector<Point> points;
    Point tmp;
    const int M = 55;
    char l[M];
    int i=0, j=0;
    while(fgets(l,M,stdin)!=NULL) {
        j = 0;
        char *p = strtok(l, " ");
        vector<int> tp;
        while(p) {
            int t = stoi(p);
            tp.push_back(t);
            tmp.i = i, tmp.j = j, tmp.num = t;;
            points.push_back(tmp);
            p = strtok(NULL, " ");
            j++;
        }
        c.push_back(tp);
        i++;
    }
    m = c.size();
    int total = 0;
    int MAX = 1<<30;
    sort(points.begin(), points.end());
    tmp.num = 1;
    int index = upper_bound(points.begin(), points.end(), tmp) - points.begin();
    if (index == points.size()) {
        printf("0\n");
    } else {
        Point curPoint{ 0, 0, 0 };
        for (int pIndex = index; pIndex < points.size(); pIndex++) {
            Point &nextPoint = points[pIndex];
            c[nextPoint.i][nextPoint.j] = 1;
            vector<vector<bool> > vis(m, vector<bool>(m, false));
            int res = MAX;
            dfs(curPoint, nextPoint, 0, res, vis);
            if(res == -1 || res == MAX) {
                printf("-1\n");
                return 0;
            } else {
                total += res;
            }
            curPoint = nextPoint;
        }
    }
    printf("%d\n", total);
    return 0;
}

测试输入用例(不全)

1 2 0
0 3 4
0 6 7
1 2 0
0 3 4
8 0 0
1 2 5 0
0 3 4 1
0 8 0 6
0 0 0 7

总结

  • 无论是BFS还是DFS都不适用于地图变化的情形,所以要转换为地图不变的问题来处理。比如,明确“起点”、“终点”。
  • 明确好“岔道口”和“死胡同”在题目中的指代,即可转换为搜索问题。当然这道题还算明显。