【Q143】阿里笔试

[kangyana]

一面

[kangyana]

1. 实现 queryParse 函数，完成解析 URL 参数的功能

用法：

const href = 'https://a.b.c?name=abc&age=24&code=%E6%B5%8B%E8%AF%95#main';
const params = queryParse(href);
console.log(params); // {name: 'abc', age: 24, ...等 }

解析：此题考查 URL 结构 和 字符串操作

/**
 * 问题：实现 queryParse 函数，完成解析 URL 参数的功能
 * @param url
 * @returns object
 */
function queryParse(url) {
  // 对 url 解码
  const decodeUrl = decodeURIComponent(url);
  // 取 ? 后面的字符串
  const afterStr = decodeUrl.split("?")[1] || "";
  // 去掉 hash 值
  const paramStr = afterStr.split("#")[0];
  // 对象数组转对象
  const result = {};
  paramStr.split("&").reduce((prev, cur) => {
    const [key, value] = cur.split("=");
    prev[key] = value;
    return prev;
  }, result);
  return result;
}

// 测试用例
console.log(queryParse("https://a.b.c?name=abc&age=24&code=%E6%B5%8B%E8%AF%95#main"));

[kangyana]

2. 请实现对二叉树节点的遍历访问函数，并按要求输出log。

示例：使得二叉树如下时： 输入数据：[1, [2], [3, [4, [5], [6]], [7]]]

1
/ \
2   3
/ \
4   7
/ \
5   6

console.log 输出的顺序为：

1
2
3
4
5
6
7

解析：此题考查 实现二叉树 和 遍历算法。此处以 中序遍历 为例：

function binaryTreeAccess(arr) {
  // 创建二叉树
  var binaryTree = new BinaryTree();
  // 扁平化，遍历插入节点
  arr.flat(Infinity).forEach((item) => {
    binaryTree.insert(item);
  });
  // 遍历访问节点，并打印
  binaryTree.inOrderTraverse(console.log);
}

// 节点类
class Node {
  constructor(key) {
    this.key = key;
    this.left = null;
    this.right = null;
  }
}

// 二叉树类
class BinaryTree {
  constructor() {
    this.root = null;
  }

  // 插入
  insert(key) {
    const node = new Node(key);
    if (this.root === null) {
      this.root = node;
      return;
    }
    insertNode(this.root, node);
  }

  // 遍历
  inOrderTraverse(callback) {
    // 传 root 是因为要从根节点开始。
    inOrderTraverseNode(this.root, callback);
  }
}

// 插入节点
function insertNode(node, newNode) {
  if (newNode.key < node.key) {
    if (node.left === null) {
      node.left = newNode;
    } else {
      insertNode(node.left, newNode);
    }
  } else {
    if (node.right === null) {
      node.right = newNode;
    } else {
      insertNode(node.right, newNode);
    }
  }
}

// 中序遍历
function inOrderTraverseNode(node, callback) {
  if (node === null) return;
  inOrderTraverseNode(node.left, callback);
  callback(node.key);
  inOrderTraverseNode(node.right, callback);
}

// 测试用例;
binaryTreeAccess([1, [2], [3, [4, [5], [6]], [7]]]);

[kangyana]

3. 实现一个分组批量执行的任务调度函数 shipTasks

使得任务队列里面的N条任务以每组 3 条异步并发执行，任务先进先出，每个分组依次串行执行 注意：（后一组等前一组异步任务执行完之后才执行）

解析：此题考查 Promise.all

function mockTaskFn(task) {
  // 假设这里做了网络请求
  return Promise.resolve({
    name: task.name,
    data: {
      status: 200,
      x: Math.random(),
    },
  });
}

const mockTaskPool = [
  { name: "task1" },
  { name: "task2" },
  { name: "task3" },
  { name: "task4" },
  { name: "task5" },
  { name: "task6" },
  { name: "task7" },
  { name: "task8" },
  { name: "task9" },
  { name: "task10" },
];

async function shipTasks(tasks, amount = 3) {
  const result = [];
  // step 为 3
  for (let i = 0; i < tasks.length; i += amount) {
    await Promise.all(tasks.slice(i, i + amount))
      .then((res) => {
        console.log("批次成功：", res);
        result.push([...res]);
      })
      .catch((err) => {
        console.log("加载失败：", err);
      });
  }
  return result;
}

// 输出任务mock返回值数组
const testFn = async () => {
  const result = await shipTasks(mockTaskPool);
  console.log("全部完毕：", result);
};

// 测试用例
testFn();

[kangyana]

4. 实现 compareVersion 方法，用于比较两个版本号（version1、version2）

如果version1 > version2，返回1； 如果version1 < version2，返回-1； 其他情况，返回0。 版本号规则x.y.z，xyz均为大于等于0的整数，至少有x位。 示例：compareVersion('0.1', '1.1.1'); // 返回-1 compareVersion('13.37', '1.2 '); // 返回1 compareVersion('1.1', '1.1.0'); // 返回0 compareVersion('1.1', '1.1.1'); // 返回-1

解析：双指针

function compareVersion(version1, version2) {
  // 版本号转位数组
  let v1 = version1.split('.');
  let v2 = version2.split('.');
  let index = 0;
  while (index < v1.length || index < v2.length) {
    // 版本号长度补0
    if (!v2[index]) {
      v2[index] = 0;
    }
    if (!v1[index]) {
      v1[index] = 0;
    }
    // 比较版本号大小
    if (+v1[index] < +v2[index]) {
      return -1;
    } else if (+v1[index] > +v2[index]) {
      return 1;
    } else {
      index++;
    }
  }
  return 0;
}

// 测试用例
console.log(compareVersion('0.1', '1.1.1')); // 返回-1
console.log(compareVersion('13.37', '1.2 ')); // 返回1
console.log(compareVersion('1.1', '1.1.0')); // 返回0
console.log(compareVersion('1.1', '1.1.1')); // 返回-1

[kangyana]

5. 井字棋游戏

输入一个二维数组代表棋盘，其中『1』代表当前玩家的棋子，『0』代表没有棋子，『-1』代表对方玩家的棋子。 若一方棋子在横、竖、斜方向连成排则为获胜，返回当前玩家是否胜出。 示例：入参为 [[1,0,1],[1,-1,-1],[1,-1,0]] 时，返回 true

解析：双循环暴力破解

function gameCheck(arr) {
  const len = arr.length; // 棋盘的长度
  let sum1 = 0; // 横向
  let sum2 = 0; // 纵向
  let sum3 = 0; // 主对角线
  let sum4 = 0; // 副对角线
  // 一行一行画
  for (let i = 0; i < len; i++) {
    // 重画
    sum1 = 0;
    sum2 = 0;
    // 计算对角线
    sum3 += arr[i][i];
    sum4 += arr[i][len - 1 - i];
    for (let j = 0; j < len; j++) {
      sum1 += arr[i][j];
      sum2 += arr[j][i];
    }
    // 赢的条件（三点成线）
    const isWin = sum1 === len || sum2 === len || sum3 === len || sum4 === len;
    if (isWin) return true;
  }
  return false;
}

// 测试用例
console.log(
  gameCheck([
    [1, 0, 1],
    [1, -1, -1],
    [1, -1, 0],
  ]),
); // true