第一题
问题简述
从n个人中选择任意数量的人员组成一支队伍，然后从一支队伍中选出一位队长，不同的队长算不同的组合，问这样的组合的数量对取模（还是取余来着？）是多少
解决思路
本质：纯数学题
其实组合数量可以直接通过组合公式得到，如下所示
然后，让 倒转并相加，即
然后，根据组合公式的对称性，即，公式可简化为
最后，根据定理，所以组合数量：
所以，整道题的答案就是。
目前，整道题最大的瓶颈在于「如何快速求出」
// 基于二分求幂
// O(log(n))
public static double power(double base, int exponent){
double res = 1;
while (exponent > 0){
if (exponent % 2 == 1)
res *= base;
base *= base; // 翻倍
exponent >>= 1; //相当于除2
}
return res;
}
代码实现
申明，这个代码是笔试结束后写的，所以并没有跑笔试中的测试用例
// 时间复杂度==power中的 O(log(n))
public long f(int n){
return (n*power(2, n-1)) % 100000007;
}
参考
[1] 阿里笔试讨论（3.23场)（附两道题AC的方法或代码）技术交流牛客网
[2] 快速求幂算法Java实现Java白衣-CSDN博客
第二题
问题简述
一个地图n*m，包含1个起点，1个终点，其他点包括可达点和不可达点。
每一次可以：上下左右移动，或使用1点能量从（i,j)移动到（n-1-i, m-1-j)，最多可以使用5点能量。
解题思路
本质是一个迷宫问题。迷宫问题的解题思路有
- 深度遍历
- 广度遍历。其中广度遍历的最大好处就是找到的第一条路径就是最短路径。
与普通迷宫问题的区别在于“本题允许进行 5 次对称跳跃”。
代码实现
/*
AC 代码
空间复杂度O(m*n*6), 时间复杂度O(m*n*6)
考试时写的比较草率，没有好好做函数化，简单加点注释供讨论
简单来说思路是类似于广度优先搜索的，但也写成了偏dp的样子……
dp[i][j][k]：用了k次飞行器时，达到这个位置(i,j)最小需要的步数
用队列来进行访问：
1. 首先把起点坐标放入队列
2. 每一次访问队头元素，观察其1步可以到达的（上、下、左、右、中心对称位）的坐标：
如果该坐标当前记录的某一种飞行器使用次数k下的值>当前值+1，则更新该值，把这一坐标加入队列
（注意，上、下、左、右是同k值比较，中心对称位需要使用一次飞行器，所以是k+1和K比较）
3. 队列清空，更新完成
给出终点目前记录的步数，即为结果
*/
/*
可能的优化：
因为队列入队时，肯定越到后面步数需要越多，所以其实第一次访问到终点坐标就可以跳出了，
不过已经AC了就不想改了……
*/
#include<iostream>
#include<queue>
#include<math.h>
using namespace std;
//定义坐标点
struct pos{
int x;
int y;
};
int main() {
int n,m;
cin>>n>>m;
vector<vector<char> > M;
vector<char> vtmp;
queue<pos> q1;
pos ps, pe, ptmp;
char ctmp;
int dp[n][m][6];
bool flag;
int i,j, k;
//先把每个位置设置一个大值
for(i = 0; i < n; i++) {
for(j = 0; j < m; j++) {
for(k = 0; k < 6; k++) {
dp[i][j][k] = n*m+1;
}
}
}
//输入 && 记录起点、终点
for(i = 0; i < n; i++) {
for(j = 0; j < m; j++) {
cin>>ctmp;
vtmp.push_back(ctmp);
if(ctmp == 'S') {
ps.x = i;
ps.y = j;
q1.push(ps);
for(k = 0; k < 6; k++) {
dp[i][j][k] = 0;
}
}
else if(ctmp == 'E') {
pe.x = i;
pe.y = j;
}
}
M.push_back(vtmp); // 起点入队
vtmp.clear();
}
//类似广度优先遍历的走完地图
while(!q1.empty()) {
ptmp = q1.front();
// 尝试向上走
if(ptmp.x > 0 && M[ptmp.x - 1][ptmp.y] != '#') {
flag = 0;
for(k = 0; k < 6; k++) {
// 更新dp数组。在k相同的条件下，如果当前格的上面一格的dp值大于当前格直接向上走得到的步数，就需要更新dp[上面一个][k]
if(dp[ptmp.x-1][ptmp.y][k] > dp[ptmp.x][ptmp.y][k] + 1) {
dp[ptmp.x-1][ptmp.y][k] = dp[ptmp.x][ptmp.y][k] + 1;
flag = 1;
}
}
// dp[i][j][k]记录的是用了k次飞行器时，达到这个位置(i,j)最小需要的步数
// flag==1,说明：当前格直接向上走产生的步数小于之前记录的dp值，只有这种才有必要把当前格的上面一格压入队列。
if(flag == 1) {
ps.x = ptmp.x-1;
ps.y = ptmp.y;
q1.push(ps);
}
}
// 尝试向下走
if(ptmp.y > 0 && M[ptmp.x][ptmp.y - 1] != '#') {
flag = 0;
for(k = 0; k < 6; k++) {
if(dp[ptmp.x][ptmp.y-1][k] > dp[ptmp.x][ptmp.y][k] + 1) {
dp[ptmp.x][ptmp.y-1][k] = dp[ptmp.x][ptmp.y][k] + 1;
flag = 1;
}
}
if(flag == 1) {
ps.x = ptmp.x;
ps.y = ptmp.y-1;
q1.push(ps);
}
}
// 尝试向右走
if(ptmp.x < n-1 && M[ptmp.x + 1][ptmp.y] != '#') {
flag = 0;
for(k = 0; k < 6; k++) {
if(dp[ptmp.x+1][ptmp.y][k] > dp[ptmp.x][ptmp.y][k] + 1) {
dp[ptmp.x+1][ptmp.y][k] = dp[ptmp.x][ptmp.y][k] + 1;
flag = 1;
}
}
if(flag == 1) {
ps.x = ptmp.x+1;
ps.y = ptmp.y;
q1.push(ps);
}
}
// 尝试向左走
if(ptmp.y < m-1 && M[ptmp.x][ptmp.y +1] != '#') {
flag = 0;
for(k = 0; k < 6; k++) {
if(dp[ptmp.x][ptmp.y+1][k] > dp[ptmp.x][ptmp.y][k] + 1) {
dp[ptmp.x][ptmp.y+1][k] = dp[ptmp.x][ptmp.y][k] + 1;
flag = 1;
}
}
if(flag == 1) {
ps.x = ptmp.x;
ps.y = ptmp.y+1;
q1.push(ps);
}
}
//尝试中心对称走，k->k+1更新
if(M[n - 1 - ptmp.x][m - 1 - ptmp.y] != '#') {
flag = 0;
for(k = 0; k < 5; k++) {
if(dp[n - 1 - ptmp.x][m - 1 - ptmp.y][k+1] > dp[ptmp.x][ptmp.y][k] + 1) {
dp[n - 1 - ptmp.x][m - 1 - ptmp.y][k+1] = dp[ptmp.x][ptmp.y][k] + 1;
flag = 1;
}
}
if(flag == 1) {
ps.x = n - 1 - ptmp.x;
ps.y = m - 1 - ptmp.y;
q1.push(ps);
}
}
q1.pop();
}
if(dp[pe.x][pe.y][5] == n*m+1) {
cout<<-1<<endl;
}
else {
cout<<dp[pe.x][pe.y][5]<<endl;
}
return 0;
}
网友评论