阿里笔试
BM1 子集（最长递增子序列）
小强现在有n个物品,每个物品有两种属性xi和yi.他想要从中挑出尽可能多的物品满足以下条件:对于任意两个物品i和j,满足xi<xj且yi<yj或者xi>xj且yi>yj.问最多能挑出多少物品.
进阶：时间复杂度O(nlogn)，空间复杂度O(n)
import java.util.*;
public class Main{
public static int maxGoods(int[][] arr){
// 将attribute进行转换并排序
int n = arr.length;
// 将二维数组按第一列升序排序，第一列相同则按第二列降序排序
Arrays.sort(arr, new Comparator<int[]>() {
@Override
public int compare(int[] o1,int[] o2){
return o1[0] == o2[0] ? o2[1] - o1[1] : o1[0] - o2[0];
}
});
// 记录arr[i][1]递增的最长序列
// 取出第二列的元素，对其求最长递增子序列
int[] nums = new int[n];
for (int i = 0; i < n; i++) {
nums[i] = arr[i][1];
}
//tails[k] 的值代表长度为k+1子序列 的尾部元素值
int[] tails = new int[n];
int res = 0;// res 为 tails当前长度
for (int num : nums){
int left = 0, right = res;//right为数组的长度，而不是length-1，这点要注意
while(left < right){
int mid = left + (right - left) / 2;
if(tails[mid] < num) left = mid + 1;
else right = mid;
}
tails[left] = num;
if(right == res) res++;
}
return res;
}
public static void main(String[] args){
Scanner scanner = new Scanner(System.in);
int p = scanner.nextInt();
for(int i = 0; i < p; i++){// p组数据
int n = scanner.nextInt();// n件商品
int[][] attribute = new int[n][2];// 属性
for(int j = 0; j < 2; j++){
for(int m = 0; m < n; m++){
attribute[m][j] = scanner.nextInt();
}
}
// 处理操作
int count = maxGoods(attribute);
System.out.println(count);// 输出结果
}
}
}
BM2 小强爱数学
小强发现当已知xy=B以及x+y=A时,能很轻易的算出x^2+y^2的值.但小强想请你在已知A 和B的情况下,计算x^n+y^n出的值.因为这个结果可能很大,所以所有的运算都在模1e9+7下进行.
import java.util.*;
public class Main{
public static final int CON = 1000000007;
/*public static int math(int A, int B, int n){// 时间复杂度太高
if(n == 0) return 2;
if(n == 1) return A;
return ((A * math(A, B, n - 1)) % CON - (B * math(A, B, n - 2) + CON) % CON);
}*/
// 采用备忘录求解
public static long math(int A, int B, int n){
long dp = 0;
long dp0 = 2, dp1 = A;
if(n == 0) return dp0;
if(n == 1) return dp1;
for (int i = 2; i <= n; i++) {
// 注意这里大数取余操作！！！
dp = ((A * dp1) % CON - (B * dp0) % CON + CON) % CON;
dp0 = dp1;
dp1 = dp;
}
return dp;
}
public static void main(String[] args) {
Scanner scanner = new Scanner(System.in);
int T = scanner.nextInt();
for(int i = 0; i < T; i++) {// T组数据
int[] nums = new int[3];
for (int j = 0; j < 3; j++) {
nums[j] = scanner.nextInt();
}
System.out.println(math(nums[0], nums[1], nums[2]));
}
}
}
BM3 二叉树
小强现在有n个节点,他想请你帮他计算出有多少种不同的二叉树满足节点个数为n且树的高度不超过m的方案.因为答案很大,所以答案需要模上1e9+7后输出. 树的高度: 定义为所有叶子到根路径上节点个数的最大值. 例如: 当n=3,m=3时,有如下5种方案
import java.util.*;
public class Main{
public static final int MOD = 1000000007;
public static long schemeNumber(int n, int high){
// dp[i][j]表示i个节点最大深度为j的树数量
long[][] dp = new long[n + 1][high + 1];
Arrays.fill(dp[0], 1);
for(int i = 1; i <= n; i++) {
for(int j = 1; j <= high; j++) {
for(int k = 0; k < i; k++) {
// 左子树节点数为k，右子树节点数为i-k-1，且左右子树都要求小于等于j-1
dp[i][j] = (dp[i][j] + dp[k][j-1] * dp[i-k-1][j-1] % MOD) % MOD;
}
}
}
return dp[n][high];
}
public static void main(String[] args) {
Scanner scanner = new Scanner(System.in);
int n = scanner.nextInt();
int m = scanner.nextInt();
System.out.println(schemeNumber(n, m));
}
}
BM4
import java.util.*;
public class Main {
static int[] dx = {1, -1, 0, 0};
static int[] dy = {0, 0, 1, -1};
static int[][][] dp;
public static void main(String[] args) {
Scanner scanner = new Scanner(System.in);
String line = scanner.nextLine();
String[] tmp = line.split(" ");
int m = Integer.parseInt(tmp[0]);
int n = Integer.parseInt(tmp[1]);
char[][] map = new char[m][n];
int sx = 0, sy = 0, ex = 0, ey = 0;
for (int i = 0; i < m; i++) {
line = scanner.nextLine();
for (int j = 0; j < n; j++) {
char ch = line.charAt(j);
map[i][j] = ch;
if (ch == 'S') {
sx = i;
sy = j;
}
if (ch == 'E') {
ex = i;
ey = j;
}
}
}
bfs(map, sx, sy, ex, ey);
for (int i = 0; i < 6; i++) {
if (dp[ex][ey][i] != 0) {
System.out.println(dp[ex][ey][i]);
return;
}
}
System.out.println(-1);
}
public static void bfs(char[][] map, int sx, int sy, int ex, int ey) {
Deque<int[]> queue = new ArrayDeque<>();
int m = map.length;
int n = map[0].length;
dp = new int[m][n][6];
queue.offerFirst(new int[] {sx, sy, 0});
while (!queue.isEmpty()) {
int[] status = queue.pollLast();
int x = status[0], y = status[1], t = status[2];
int nx = 0, ny = 0, nt = 0;
for (int i = 0; i < 5; i++) {
if (i == 4) {
nx = m - 1 - x;
ny = n - 1 - y;
nt = t + 1;
} else {
nx = x + dx[i];
ny = y + dy[i];
nt = t;
}
if (nx >= 0 && nx < m && ny >= 0 && ny < n && nt < 6 && map[nx][ny] != '#' && dp[nx][ny][nt] == 0) {
dp[nx][ny][nt] = dp[x][y][t] + 1;
if (nx == ex && ny == ey) {
return;
}
queue.offerFirst(new int[] {nx, ny, nt});
}
}
}
}
}
BM5 知识竞赛
最近部门要选两个员工去参加一个需要合作的知识竞赛，每个员工均有一个推理能力值Ai ，以及一个阅读能力值Bi 。如果选择第i个人和第j个人去参加竞赛，那么他们在阅读方面所表现出的能力为X=(Bi + Bj)/2，他们在推理方面所表现出的能力为Y=(Ai+Aj)/2。 现在需要最大化他们表现较差一方面的能力，即让min(X,Y)尽可能大，问这个值最大是多少。
进阶：时间复杂度O(nlogn)，空间复杂度O(n)
import java.util.*;
public class Main{
public static double maxDiff(int[][] arr, int n){
Arrays.sort(arr,new Comparator<int[]>() {
@Override
public int compare(int[]o1,int[]o2)
{
return Math.abs(o1[0] - o1[1]) - Math.abs(o2[0] - o2[1]);
}
});
int maxX = arr[0][0];
int maxY = arr[0][1];
int maxMin = 0;
for(int i = 1;i < n; i++){
int current;
if(arr[i][0] > arr[i][1])
current = arr[i][1] + maxY;
else
current = arr[i][0] + maxX;
if(current > maxMin)
maxMin = current;
maxX = Math.max(arr[i][0], maxX);
maxY = Math.max(arr[i][1], maxY);
}
double res = maxMin / 2.0;
return res;
}
public static void main(String[] args){
Scanner scanner = new Scanner(System.in);
int n = scanner.nextInt();
int[][] arr = new int[n][2];
for(int i = 0; i < n; i++){
for(int j = 0; j < 2; j++){
arr[i][j] = scanner.nextInt();
}
}
System.out.println(maxDiff(arr, n));
}
}
BM6 树上的最短链（图论/BFS） 经典！！！
在一个地区有n个城市以及n-1条无向边，每条边的时间边权都是1 ，并且这些城市是联通的，即这个地区形成了一个树状结构。每个城市有一个等级。 现在小强想从一个城市走到另一个不同的城市，并且每条边经过至多一次，同时他还有一个要求，起点和终点城市可以任意选择，但是等级必须是相同的。 但是小强不喜欢走特别远的道路，所以他想知道时间花费最小是多少。
进阶：时间复杂度O(n^2logn)，空间复杂度O(n)
import java.util.*;
import java.math.*;
public class Main{
// 深度优先搜索
public static int BFS(int[] level, ArrayList<Integer>[] lists){
int res = Integer.MAX_VALUE;
int n = level.length;
for(int i = 0;i < n; i++){// 对于每一个城市进行深度优先搜索
Queue<Integer> queue = new LinkedList<>();
boolean[] visit = new boolean[n];// 用于标记当前城市是否走过
queue.offer(i);// 以城市i为起点
visit[i] = true;
int length = 0;// 记录走过的距离长度
while(!queue.isEmpty()){
int size = queue.size();
int flag = 0;// 用于标记是否需要继续走，当走到与起点城市级别相等的其他城市时，就停止当前行进
for(int j = 0; j < size; j++){
int temp = queue.poll();
if(temp != i && level[temp] == level[i]){// 到达相同级别其他城市
res = Math.min(res,length);// 记录最短距离
flag = 1;// 用于标记是否需要继续行进
break;
}
for(int x : lists[temp]){// 拜访其该城市连接的其他城市
if(!visit[x]){
queue.offer(x);
visit[x] = true;
}
}
}
if(flag == 1) break;
length++;
}
}
// 返回结果，若无满足要求答案，则返回-1
return res == Integer.MAX_VALUE ? -1 : res;
}
public static void main(String []args){
Scanner scanner = new Scanner(System.in);
int n = scanner.nextInt();// n个城市
int[] level = new int[n];// 城市等级
ArrayList<Integer>[] lists = new ArrayList[n];// n个链表，存储无向图
for(int i = 0;i < n; i++){
level[i] = scanner.nextInt();// 输入城市i级别
lists[i] = new ArrayList<Integer>();// 创建城市i的连接链表
}
for(int i = 0;i < n-1; i++){// n - 1条无向边连接
int x = scanner.nextInt()-1;// 城市标记为0 ~ n - 1,方便用下标索引
int y = scanner.nextInt()-1;
lists[x].add(y);// 相互连接两个城市
lists[y].add(x);
}
int res = BFS(level, lists);
System.out.println(res);
}
}
BM7 牛牛们吃糖果（并查集+0-1背包问题）
有n个牛牛一起去朋友家吃糖果，第i个牛牛一定要吃ai块糖果. 而朋友家一共只有m块糖果，可能不会满足所有的牛牛都吃上糖果。 同时牛牛们有k个约定，每一个约定为一个牛牛的编号对(i,j)，表示第i个和第j个牛牛是好朋友，他俩要么一起都吃到糖果，要么一起都不吃。 保证每个牛牛最多只出现在一个编号对中。 您可以安排让一些牛牛吃糖果，一些牛牛不吃。 要求使能吃上糖果的牛牛数量最多（吃掉的糖果总量要小于等于m），并要满足不违反牛牛们的k个约定。
import java.util.*;
// 并查集+0-1背包问题
public class Main {
public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
int n = sc.nextInt();// n 个牛牛
int m = sc.nextInt();// m 颗糖果
int[] a = new int[n];// 每个牛牛吃到的糖果 a[i]
for (int i = 0; i < a.length; i++) {
a[i] = sc.nextInt();
}
int[] v = new int[a.length];
Arrays.fill(v, 1);
int k = sc.nextInt();// k 个约定
for (int i = 0; i < k; i++) {//第 i 个牛牛与第 j 个牛牛有约定
int x = sc.nextInt();
int y = sc.nextInt();
// 将有约定的牛牛绑定在一起
a[x - 1] += a[y - 1];
v[x - 1] += 1;
v[y - 1] = 0;
}
// 用于记录m个糖果的最优分配结果
int[] opt = new int[m + 1];
Arrays.fill(opt, 0);
for (int i = 0; i < n; i++) {
if (v[i] == 0) {
continue;
}
// 这一块有点疑惑？？？
for (int j = m; j > a[i] - 1; --j) {
opt[j] = Math.max(opt[j], (opt[j - a[i]] + v[i]));
}
}
//最多能吃到糖果的牛牛个数
System.out.print(opt[opt.length - 1]);
}
}
BM8 方案数量
import java.util.Scanner;
public class Main {
static int n, m;
final static int mod = 10000;
public static void main(String[] args) {
Scanner s = new Scanner(System.in);
int T = s.nextInt();
for (int times = 0; times < T; times++) {
n = s.nextInt();
m = s.nextInt();
int[][] board = new int[n][m];
for (int i = 0; i < n; i++) {
for (int j = 0; j < m; j++) {
board[i][j] = s.nextInt();
}
}
int ans = dpHandle(board);
System.out.println(ans);
}
}
private static int dpHandle(int[][] board) {
int[][] dp = new int[n][m];
dp[0][0] = 1;
for (int i = 0; i < n; i++) {
for (int j = 0; j < m; j++) {
int energy = board[i][j];
//i：能够消耗的能量
for (int useEnergy = 1; useEnergy <= energy; useEnergy++) {
//x消耗的能量
for (int xCost = 0; xCost <= useEnergy; xCost++) {
int nx = i, ny = j;
nx += xCost;
ny += useEnergy - xCost;
if (nx >= n || ny >= m) {
continue;
}
dp[nx][ny] = (dp[nx][ny] + dp[i][j]) % mod;
}
}
}
}
return dp[n - 1][m - 1];
}
}
BM9
小强有一个长度为n的数组a和正整数m. 他想请你帮他计算数组a中有多少个连续子区间[l,r],其区间内存在某个元素出现的次数不小于次? 例如数组a=[1,2,1,2,3]且m=2,那么区间[1,3],[1,4],[1,5],[2,4],[2,5]都是满足条件的区间,但区间[3,4]等都是不满足条件的.
import java.util.*;
public class Main {
public static void main(String[] args) {
Scanner s = new Scanner(System.in);
int len = s.nextInt(), m = s.nextInt();
int[] nums = new int[len];
for (int i = 0; i < len; i++) {
nums[i] = s.nextInt();
}
int left = 0;
long ans = 0;
Map<Integer, Integer> map = new HashMap<>();
boolean find = false;
for (int right = 0; right < len; right++) {
int times = map.getOrDefault(nums[right], 0);
times++;
map.put(nums[right], times);
if (times == m) {
find = true;
}
while (find) {
ans += len - right;
int leftTimes = map.get(nums[left]);
leftTimes--;
map.put(nums[left], leftTimes);
if (nums[left] == nums[right] && leftTimes < m) {
find = false;
}
left++;
}
}
System.out.println(ans);
}
}
BM10
小强有两个序列a和b，这两个序列都是由相同的无重复数字集合组成的，现在小强想把a序列变成b序列，他只能进行以下的操作： 从序列a中选择第一个或者最后一个数字并把它插入a中的任意位置。 问小强至少需要几次操作可以将序列a变为序列b。
import java.util.HashMap;
import java.util.Map;
import java.util.Scanner;
public class Main {
public static void main(String[] args) {
Scanner cin = new Scanner(System.in);
int n = cin.nextInt();
int[] a = new int[n];
for (int i = 0; i < n; i++) {
a[i] = cin.nextInt();
}
Map<Integer,Integer> map = new HashMap<>();
for (int i = 0; i < n; i++) {
map.put(cin.nextInt(),i);
}
// 将序列表示成b的下标
for (int i = 0; i < n; i++) {
a[i] = map.get(a[i]);
}
// 求下标最长连续上升序列
int max = 1;
int cur = 1;
// 从第二个开始计算
for (int i = 1; i < a.length; i++) {
if(a[i]>a[i-1]) {
cur++;
max = Math.max(max,cur);
}else {
cur = 1;
}
}
System.out.println(n-max);
}
}
投递粉笔网等公司10个岗位 >
拼多多集团-PDD公司氛围 515人发布
