2021 阿里巴巴编程题

import java.util.*;
import java.lang.*;

public class Main {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int t = sc.nextInt();
        for (int k = 0; k < t; k++) {
            int n = sc.nextInt();
            int[][] nums = new int[n][2];
            for (int i = 0; i < n; i++) {
                nums[i][0] = sc.nextInt();
            }
            for (int i = 0; i < n; i++) {
                nums[i][1] = sc.nextInt();
            }
            Arrays.sort(nums, (o1, o2) -> o1[0]==o2[0]? o2[1]-o1[1]:o1[0]-o2[0]);

            System.out.println(solve(nums));
        }
    }
    
    public static int solve(int[][] nums) {
        int n = nums.length;
        int[] dp = new int[n+1];    // dp[i]表示长度为i的LIS子序列最后一位的值
        int maxLen = 1;
        dp[1] = nums[0][1];
        for (int i = 1; i < n; i++) {
            if (nums[i][1] > dp[maxLen]) {
                maxLen++;
                dp[maxLen] = nums[i][1];
            } else {
                int idx = find(dp, maxLen, nums[i][1]);
                dp[idx] = nums[i][1];
            }
        }
        return maxLen;
    }
    
    // >=
    public static int find(int[] dp, int maxLen, int target) {
        int left = 1, right = maxLen;
        while (left <= right) {
            int mid = left + ((right - left) >> 1);
            if (dp[mid] < target) {
                left = mid + 1;
            } else {
                right = mid - 1;
            }
        }
        return left;
    }
}

https://www.nowcoder.com/test/question/a55198d2e65746009110226f2f6c8533?pid=30440638&tid=52108831

import java.util.*;
import java.lang.*;

public class Main {
    static int[][] dirs = {{1,0}, {-1,0}, {0,1}, {0,-1}};
    static class node {
        int x, y, cnt, used;
        node(int xx, int yy, int count, int num) {
            x = xx; y = yy; cnt = count; used = num;
        }
    }
    
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt();
        int m = sc.nextInt();
        char[][] board = new char[n][m];
        int sx = 0, sy = 0, ex = 0, ey = 0;
        for (int i = 0; i < n; i++) {
            String row = sc.next();　　// 注意：不要用nextLine，next只取到有效字符
            for (int j = 0; j < row.length(); j++) {
                board[i][j] = row.charAt(j);
                if (board[i][j] == 'S') {
                    sx = i; sy = j;
                }
                if (board[i][j] == 'E') {
                    ex = i; ey = j;
                }
            }
        }
        int[][] vis = new int[n][m];
        Deque que = new LinkedList<>();
        que.offer(new node(sx, sy, 0, 5));
        vis[sx][sy] = 1;
        boolean flag = false;;
        while (!que.isEmpty()) {
            node cur = que.poll();
            if (cur.x == ex && cur.y == ey) {
                System.out.println(cur.cnt);
                flag = true;
                break;
            }
            for (int[] dir: dirs) {
                int xx = cur.x + dir[0], yy = cur.y + dir[1];
                if (!inBoard(n, m, xx, yy) || board[xx][yy] == '#' || vis[xx][yy] == 1) continue;
                que.offer(new node(xx, yy, cur.cnt + 1, cur.used));
                vis[xx][yy] = 1;
            }
            // 中心对称
            int x1 = n -1 - cur.x, y1 = m - 1 - cur.y;
            if (cur.used > 0 && inBoard(n, m, x1, y1) && board[x1][y1] != '#' && vis[x1][y1] == 0) {
                que.offer(new node(x1, y1, cur.cnt + 1, cur.used-1));
                vis[x1][y1] = 1;
            }
        }
        if (!flag) System.out.println(-1);
    }
    public static boolean inBoard(int n, int m, int x, int y) {
        if (x < 0 || x >= n || y < 0 || y >= m) return false;
        return true;
    }
}

https://blog.csdn.net/qq_37702890/article/details/122846069?utm_medium=distribute.pc_relevant.none-task-blog-2~default~baidujs_title~default-0.pc_relevant_paycolumn_v3&spm=1001.2101.3001.4242.1&utm_relevant_index=2