Java工程师丨面试真题（9）
一、最大差值
描述
有一个长为 n 的数组 A ，求满足 0 ≤ a ≤ b < n 的 A[b] - A[a] 的最大值。
给定数组 A 及它的大小 n ，请返回最大差值。
数据范围： 2<n≤2∗105 2 < n \le 2*10^5\ 2<n≤2∗105 ，数组中的值满足 0≤∣val∣≤5∗108 0 \le |val| \le 5*10^8 \ 0≤∣val∣≤5∗108
示例1
输入：
[5,1],2返回值：
0示例2
输入：
[5,6],2返回值：
1
题解：
import java.util.*;
public class Solution {
/**
* 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
*
*
* @param A int整型一维数组
* @param n int整型
* @return int整型
*/
public int getDis (int[] A, int n) {
// write code here
int res = 0;
int min = Integer.MAX_VALUE;
for (int i = 0; i < n; i++) {
min = Math.min(min, A[i]);
res = Math.max(res, A[i] - min);
}
return res;
}
}
二、棋子翻转
描述
在 4x4 的棋盘上摆满了黑白棋子，黑白两色棋子的位置和数目随机，其中0代表白色，1代表黑色；左上角坐标为 (1,1) ，右下角坐标为 (4,4) 。
现在依次有一些翻转操作，要对以给定翻转坐标(x,y)（也即第x行第y列）为中心的上下左右四个棋子的颜色进行翻转。
给定两个数组 A 和 f ，分别代表 初始棋盘 和 哪些要进行翻转的位置(x,y) ，请返回经过所有翻转操作后的棋盘。
例如输入[[0,0,1,1],[1,0,1,0],[0,1,1,0],[0,0,1,0]],[[2,2],[3,3],[4,4]]时，初始键盘如下图所示：
对应的输出为[[0,1,1,1],[0,0,1,0],[0,1,1,0],[0,0,1,0]]，如下图所示：
示例1
输入：
[[0,0,1,1],[1,0,1,0],[0,1,1,0],[0,0,1,0]],[[2,2],[3,3],[4,4]]返回值：
[[0,1,1,1],[0,0,1,0],[0,1,1,0],[0,0,1,0]]
题解：
import java.util.*;
public class Solution {
/**
* 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
*
*
* @param A int整型二维数组
* @param f int整型二维数组
* @return int整型二维数组
*/
public int[][] flipChess (int[][] A, int[][] f) {
// write code here
int m = A.length;
int n = A[0].length;
for(int i = 0; i < f.length; i++) {
int x = f[i][0] - 1, y = f[i][1] - 1;
if(x > 0) A[x - 1][y] = 1 - A[x - 1][y];
if(y > 0) A[x][y - 1] = 1 - A[x][y - 1];
if(x + 1 < m) A[x + 1][y] = 1 - A[x + 1][y];
if(y + 1 < n) A[x][y + 1] = 1 - A[x][y + 1];
}
return A;
}
}
三、拜访
描述
现在有一个城市销售经理，需要从公司出发，去拜访市内的某位商家，已知他的位置以及商家的位置，但是由于城市道路交通的原因，他每次移动只能在左右中选择一个方向 或 在上下中选择一个方向，现在问他有多少种最短方案到达商家地址。
给定一个地图 CityMap 及它的 行长度 n 和 列长度 m ，其中1代表经理位置， 2 代表商家位置， -1 代表不能经过的地区， 0 代表可以经过的地区，请返回方案数，保证一定存在合法路径。保证矩阵的长宽都小于等于 10。
注意：需保证所有方案的距离都是最短的方案
数据范围：2≤n,m≤102 \leq n,m \leq 102≤n,m≤10
例如当输入为[[2,0,0,0],[0,-1,-1,0],[0,-1,1,0],[0,0,0,0]],4,4时，对应的4行4列CityMap如下图所示：
经理的位置在(2,2)，商家的位置在(0,0)，经分析，经理到达商家地址的最短方案有两种，分别为：
(2,2)->(2,3)->(1,3)->(0,3)->(0,2)->(0,1)->(0,0)
和
(2,2)->(3,2)->(3,1)->(3,0)->(2,0)->(1,0)->(0,0)，所以对应的返回值为2
示例1
输入：
[[0,1,0],[2,0,0]],2,3返回值：
2
题解：
import java.util.*;
public class Solution {
/**
* 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
*
*
* @param CityMap int整型二维数组
* @param n int整型
* @param m int整型
* @return int整型
*/
int[][] directions = new int[][]{{1,0}, {-1, 0}, {0,1}, {0, -1}};
public int countPath (int[][] CityMap, int n, int m) {
// write code here
int ans = 0;
Queue<int[]> queue = new LinkedList<>();
int[][] dist = new int[n][m];
int[][] dp = new int[n][m];
boolean[][] visited = new boolean[n][m];
for(int i=0; i<n; i++){
for(int j=0; j<m; j++){
if(CityMap[i][j]==1){ //确认出发点
queue.offer(new int[]{i,j});
dist[i][j] = 1; //出发点距离为1
dp[i][j] = 1; //出发点的最短路径数为1
}
}
}
while(!queue.isEmpty()){
int[] p = queue.poll();
int x = p[0], y = p[1];
if(CityMap[x][y]==2){
return dp[x][y];
}
CityMap[x][y] = -1;
for(int[] direction : directions){
int newx = x + direction[0];
int newy = y + direction[1];
if(newx>=n || newx<0 || newy<0 || newy>=m || CityMap[newx][newy]==-1){ //判断不可达
continue;
}
if(dist[newx][newy]==0 || dist[newx][newy]==dist[x][y]+1){ //dist[newx][newy]为0或当前访问点加1，则说明可以通过当前访问点到达目标点，且为最短路径
dp[newx][newy] += dp[x][y];
dist[newx][newy] = dist[x][y] + 1;
}
if(!visited[newx][newy]){ //通过visited数组防止重复加入访问队列
queue.offer(new int[]{newx, newy});
visited[newx][newy] = true;
}
}
}
return -1;
}
}
四、直方图内最大矩形
描述
给定一个数组heights，长度为n，height[i]是在第i点的高度，那么height[i]表示的直方图，能够形成的最大矩形是多少?
1.每个直方图宽度都为1
2.直方图都是相邻的
3.如果不能形成矩形，返回0即可
4.保证返回的结果不会超过231-1
数据范围:
0<=heights[i]<=1040 <= heights[i] <= 10^40<=heights[i]<=104
0<=heights.length<=1050 <= heights.length <=10^50<=heights.length<=105
如输入[3,4,7,8,1,2]，那么如下:
示例1
输入：
[3,4,7,8,1,2]返回值：
14
示例2
输入：
[1,7,3,2,4,5,8,2,7]返回值：
16
题解：
import java.util.*;
public class Solution {
/**
* 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
*
*
* @param heights int整型一维数组
* @return int整型
*/
public int largestRectangleArea (int[] heights) {
//总宽度
int n=heights.length;
//新建单调栈
ArrayDeque<Integer> stack=new ArrayDeque<>();
int res=0;
for(int i=0;i<n;i++){
//只要栈顶元素比当前大，则可以统计以栈顶元素为高的最大面积
while(!stack.isEmpty()&&heights[stack.peek()]>heights[i]){
//由于单调栈内元素是单调不递减的，L到i-1之间的高度一定大于等于curHeight
int curHeight=heights[stack.pop()];
//如果栈中元素为空，说明0到i-1之间的高度均大于等于curHeight
int L=stack.isEmpty()?0:stack.peek()+1;
res=Math.max(res,(i-L)*curHeight);
}
stack.push(i);
}
//如果遍历完之后，单调栈还不为空，则继续统计可能的最大面积
while(!stack.isEmpty()){
int curHeight=heights[stack.pop()];
int L=stack.isEmpty()?0:stack.peek()+1;
res=Math.max(res,(n-L)*curHeight);
}
return res;
}
}
- 点赞
- 收藏
- 关注作者
评论（0）