京东笔试第四批笔试题解 8/31

T1

题意: 给定字符串s，找到与s长度相同，但是字典序比s大的最小字符串

模拟进位，全是z则无解，相当于一个26进制数+=1

O(n)

T2

给一个数组进行排序

操作一，选择下标i ，交换a[i],a[i+1]

操作二，选择下表i，使a[i],a[i+1],a[i+2]，变成a[i+2],a[i+1],a[i]

发现操作二是对奇偶位置分开排序，那么对原数组进行排序，发现最后位置与自身初始位置奇偶结果不同则计数cnt+=1，操作一则是使一个错误的奇数位和错误的偶数位恢复正确奇偶性的位置，答案就是cnt/2

O(n)

T3

给定一个2xN的矩阵a，有两名玩家轮流移动棋子，玩家1希望最大化得分，玩家二希望最小化得分。

玩家一初始把棋子放在了1，1的位置上面，得分为走过路径所有格点的和。

数据范围

N<=1e5

-1e5<=a[i][j]<=1e5

dfs搜索状态，定义状态 dp[x][y][now][flag]为，当前位置在x行y列，同时轮到now进行操作，flag为能否上下移动的标志。

定义now==1需要最小化结果，now==0需要最大化结果，1先手（题目这里比较坑人，玩家1的先手用于走到初始位置了）

if(now==1)
{
	res=INF;
  //我是从0，0,走到1,n-1，如果你是1，1到2，n就y!=n
	if(y!=n-1){
		res=min(res,dfs(x,y+1,now^1,1)+a[x][y+1]);
	}
	if(flag){
		res=min(res,dfs(x,y^1,now^1,0)+a[x][y^1];
	}
}

需要注意的是我们得走到(2,n)这个位置，那么我们递归终止条件就是x==2，y==n

额外需要注意的就是在（1,n）这个位置不能往右走了

最大化的情况和最小化就是把min换成max

复杂度O(n*8)