又到了一年一度的校招干饭环节,本人不得已以应届生的身份卷入了这场洪流,让我们各自加油吧!
xx机考编程题
输入两个整数 n和 m,输出一个 n 行 m 列的矩阵,将数字 1到 n×m按照回字蛇形填充至矩阵中。
具体矩阵形式可参考样例。
输入共一行,包含两个整数 n 和 m。
输出满足要求的矩阵。
矩阵占 n 行,每行包含 m 个空格隔开的整数。
1≤n,m≤100
思路:
导入Java的Scanner类,以便从标准输入中获取用户输入。
在
main
方法中,首先通过Scanner
获取输入的两个整数n
和m
,分别表示矩阵的行数和列数。创建一个二维数组
a
,用于存储填充后的矩阵。初始化四个边界指针:
l
(左边界)、r
(右边界)、t
(上边界)、d
(下边界),并初始化计数器cnt
为 1。使用一个循环,当
l <= r
且t <= d
时,进行如下操作,这是一个螺旋填充的核心逻辑:
- 从左到右,填充第
t
行,列从l
到r
。- 递增
t
,缩小上边界。- 从上到下,填充第
r
列,行从t
到d
。- 递减
r
,缩小右边界。- 从右到左,填充第
d
行,列从r
到l
。- 递减
d
,缩小下边界。- 从下到上,填充第
l
列,行从d
到t
。- 递增
l
,扩大左边界。在循环结束后,矩阵
a
中已经填充完毕。使用嵌套的循环遍历矩阵
a
,并使用System.out.print
打印每个元素,每行元素之间用空格分隔,每行结束时用System.out.println
换行。总体思路是通过四个指针和循环实现螺旋填充,将数字从1递增填充到矩阵中的各个位置。这种方法可以确保按照螺旋的方式填充矩阵,最终输出完整的螺旋矩阵。
代码:
- package com.company;
-
- import java.util.Scanner;
-
- public class Main {
- public static void main(String[] args) {
- Scanner scanner = new Scanner(System.in);
- int n = scanner.nextInt();
- int m = scanner.nextInt();
- int[][] a = new int[n][m];
- int l = 0, r = m - 1, t = 0, d = n - 1, cnt = 1;
- while (l <= r || t <= d) {
- for (int i = l; i <= r && t <= d; i++) a[t][i] = cnt++;
- t++;
- for (int i = t; i <= d && l <= r; i++) a[i][r] = cnt++;
- r--;
- for (int i = r; i >= l && t <= d; i--) a[d][i] = cnt++;
- d--;
- for (int i = d; i >= t && l <= r; i--) a[i][l] = cnt++;
- l++;
- }
- for (int i = 0; i < n; i++) {
- for (int j = 0; j < m; j++) {
- System.out.print(a[i][j] + " ");
- }
- System.out.println();
- }
- }
- }
-
测试结果:
思路:
导入Java的Scanner类,以便从标准输入中获取用户输入。
在
main
方法中,首先通过Scanner
获取输入的两个整数n
和m
,分别表示矩阵的行数和列数。创建一个二维数组
a
,用于存储填充后的矩阵。定义两个数组
dx
和dy
,分别表示四个方向的水平和垂直移动。例如,dx[0]
和dy[0]
表示向右移动,dx[1]
和dy[1]
表示向下移动,以此类推。初始化变量
x
和y
,表示当前位置的行和列,以及变量u
,表示当前的方向。使用一个循环,从1到
n * m
遍历填充矩阵的数字。循环内部的操作如下:
- 将当前位置
(x, y)
填充为当前数字i
。- 根据当前方向
u
计算下一个位置(newX, newY)
。- 检查下一个位置是否越界或已经被填充,如果是,则更改方向
u
为下一个方向,并重新计算新的位置(newX, newY)
。- 更新当前位置
(x, y)
为新的位置(newX, newY)
。循环结束后,矩阵
a
中已经填充完毕。使用嵌套的循环遍历矩阵
a
,并使用System.out.print
打印每个元素,每行元素之间用空格分隔,每行结束时用System.out.println
换行。
总体思路是通过四个方向的移动来实现螺旋填充,将数字从1递增填充到矩阵的各个位置。在填充过程中,根据当前方向和位置的情况来判断是否需要更改方向,以确保按照螺旋的方式填充矩阵。最终输出完整的螺旋矩阵。
代码:
- import java.util.Scanner;
-
- public class Main {
- public static void main(String[] args) {
- Scanner scanner = new Scanner(System.in);
- int n = scanner.nextInt();
- int m = scanner.nextInt();
- int[][] a = new int[n][m];
- int[] dx = {0, 1, 0, -1};
- int[] dy = {1, 0, -1, 0};
- int x = 0, y = 0, u = 0;
-
- for (int i = 1; i <= n * m; i++) {
- a[x][y] = i;
- int newX = x + dx[u];
- int newY = y + dy[u];
-
- if (newX < 0 || newY < 0 || newX >= n || newY >= m || a[newX][newY] != 0) {
- u = (u + 1) % 4;
- newX = x + dx[u];
- newY = y + dy[u];
- }
-
- x = newX;
- y = newY;
- }
-
- for (int i = 0; i < n; i++) {
- for (int j = 0; j < m; j++) {
- System.out.print(a[i][j] + " ");
- }
- System.out.println();
- }
- }
- }
输入测试:
旷视面试题
给定一个单链表,请使用快速排序算法对其排序。
要求:期望平均时间复杂度为 O(nlogn),期望额外空间复杂度为 O(logn)。
思考题: 如果只能改变链表结构,不能修改每个节点的val值该如何做呢?
链表中的所有数大小均在 int 范围内,链表长度在 [0,10000]。
本题数据完全随机生成。
思路与普通的快排基本一致,将链表根据一个val分成小于val、等于val、大于val三段,再对前后两段递归进行快排,对于排序完的三段从前到后进行拼接即可完成。
代码:
- import java.util.Scanner;
-
- public class Main {
- public static void main(String[] args) {
- Scanner scanner = new Scanner(System.in);
- int n = scanner.nextInt();
- int m = scanner.nextInt();
- int[][] result = generateSpiralMatrix(n, m);
-
- // 打印生成的螺旋矩阵
- for (int i = 0; i < n; i++) {
- for (int j = 0; j < m; j++) {
- System.out.print(result[i][j] + " ");
- }
- System.out.println();
- }
- }
-
- public static int[][] generateSpiralMatrix(int n, int m) {
- int[][] matrix = new int[n][m];
- int top = 0, bottom = n - 1, left = 0, right = m - 1;
- int num = 1;
-
- while (num <= n * m) {
- for (int i = left; i <= right && num <= n * m; i++) {
- matrix[top][i] = num++;
- }
- top++;
-
- for (int i = top; i <= bottom && num <= n * m; i++) {
- matrix[i][right] = num++;
- }
- right--;
-
- for (int i = right; i >= left && num <= n * m; i--) {
- matrix[bottom][i] = num++;
- }
- bottom--;
-
- for (int i = bottom; i >= top && num <= n * m; i--) {
- matrix[i][left] = num++;
- }
- left++;
- }
-
- return matrix;
- }
- }
输入测试: