# PTA题解 - JavaScript实现

**Repository Path**: springmorningcxx/pta-solution-javascript

## Basic Information

- **Project Name**: PTA题解 - JavaScript实现
- **Description**: 📌 使用JavaScript语言实现拼题A（PTA）平台的题目
- **Primary Language**: JavaScript
- **License**: Not specified
- **Default Branch**: main
- **Homepage**: None
- **GVP Project**: No

## Statistics

- **Stars**: 2
- **Forks**: 0
- **Created**: 2025-07-12
- **Last Updated**: 2025-07-22

## Categories & Tags

**Categories**: Uncategorized

**Tags**: JavaScript, Nodejs, PTA, Algorithm, 春晓

## README

# PTA题解 - JavaScript实现

一个专注于在PTA使用 JavaScript (Node.js) 解题的代码库。

[![License](https://img.shields.io/badge/许可证-春晓PSL-84dd84)](LICENSE)

## 目录结构
```bash
.
├── solution/                          # 题解目录（按题号组织）
│   ├── 1001害死人不偿命的(3n+1)猜想.js
│   ├── 1002写出这个数.js
│   └── ...                            # 其他题解
│
└── template/                          # 模板目录
    ├── async_template.js                  # 异步输入模板
    └── sync_template.js                   # 同步输入模板（推荐）
```

## 模板说明
模板提供了三个输入函数
- `input()`用于读取一行字符串
- `number()`用于读取一行中的单个数字
- `numbers()`用于读取一行中，按空格分割后转为数字数组

### 同步输入模板（推荐）⭐️
同步输入模板性能更高，推荐所有PTA题目使用。
```javascript
"use strict";
const data = require("fs").readFileSync(0, "utf-8").trimEnd().split("\n");
let line = 0;
const input = () => data[line++] || "";
const number = () => +input();
const numbers = () => input().split(" ").map(Number);

// ================ 题目解答区域 ================
// 在此处编写解题代码

// 示例：
// const n = number();
// const arr = numbers();
// console.log(arr.reduce((a, b) => a + b, 0));

// ============================================
```

### 异步输入模板
异步输入模板只在输入数据量极大（>100MB）时使用，但针对PTA场景，更推荐同步模板。
```javascript
"use strict";
(async () => {
  const chunks = [];
  for await (const chunk of process.stdin) chunks.push(chunk);
  const data = Buffer.concat(chunks).toString().trimEnd().split("\n");
  let line = 0;
  const input = () => data[line++] || "";
  const number = () => +input();
  const numbers = () => input().split(" ").map(Number);

  // ================ 题目解答区域 ================
  // 在此处编写解题代码
  
  // 示例：
  // const n = number();
  // const arr = numbers();
  // console.log(arr.reduce((a, b) => a + b, 0));
  
  // ============================================
})().catch(console.error);
```

**特点**：
- 流式处理输入
- 内存占用更稳定
- 兼容性更好

**适用场景**：
- 输入数据量极大（>100MB）
- 需要处理实时输入流的场景
- 其他非PTA平台的编程挑战

## 刷题指南
本仓库基于[PTA程序设计类实验辅助平台](https://pintia.cn)中的[PAT考试题目集](https://pintia.cn/problem-sets/994805260223102976/exam/problems/type/7)，如使用其它平台，请确保你使用的OJ平台支持NodeJS环境

### 环境配置
建议使用VSCode编译器
PTA中NodeJS版本为`12.22.12`，需要安装对应版本的`@types/node`开启VSCode代码提示
[npm仓库](https://www.npmjs.com/package/@types/node?activeTab=versions) 中没有这个版本，我们装一个最接近的`12.20.55`版本即可
```bash
npm i @types/node@12.20.55
```
> 注意：类型定义安装是可选的，仅用于获得更好的代码提示，不影响实际解题

### 基础步骤
1. 创建js文件：在本地创建`solution.js`文件
2. 粘贴模板：根据需求复制同步/异步模板到文件中（推荐同步模板）
3. 编写逻辑：在题目解答区域编写解题代码
4. 测试运行：`node solution.js`
>  重要！不同于C++标准输入的自动结束，本地调试时输入结束方式如下：
> - Windows: Ctrl+Z → Enter
> - Linux/Mac: Ctrl+D
> 
> 如果你不喜欢需要手动输入结束符的控制台输入，也可采用文件输入
> - `node solution.js < input.txt`

### 输入输出要点
|操作类型  | 推荐方法 |示例 |
|--|--|--|
| 单数字输入 |number()	  |let n = number() |
| 多数字输入 |numbers()+解构赋值 |let [a, b] = numbers(); |
| 数字数组输入 |numbers() |const arr = numbers() |
| 格式化输出 |模板字符串 |console.log(`${a} ${b}`)|
| 数组输出 |内置join()函数 |console.log(arr.join(" "))|
| 高性能输出 |数组收集+单次process.stdout.write() |关键优化！见下方优化示例❗|


## 常见问题解决
### 为什么在PTA上超时？
**PTA平台使用NodeJS刷题在算法优化到极限仍超时的情况客观存在**，由以下两点原因导致
- PTA并未针对不同语言做出不同的时空限制，时空限制是基于C/C++的，存在算法优化到极限仍超时的现象
- 此外，PTA的评测环境NodeJS版本为`12.22.12`，版本较低，优化可能不足。
👇 先不要气馁，建议尝试以下优化：
1. 将同步模板的`trimEnd()`去掉（只有少数题目输入样例尾随空白字符需要`trimEnd()`）
2. 将函数内联（特别是循环内的函数，注意别忘了同步模板的函数也能改为内联）
3. 减少不必要的字符串操作
4. 使用`"use strict";`开启严格模式，提升V8优化
5. 减少高级特性的使用（如箭头函数、解构赋值、`for...of`循环等），这些特性在低版本Node中可能性能不足
6. 使用`new Array(n)`代替`[]`预分配内存
7. 标准输入优化，变多次输出为单次输出，使用数组收集结果后单次输出（1045快速排序采用此项优化后直接从TLE超时变为99msAC）
8. 使用`process.stdout.write`代替`console.log`

可以参考我在[1015德才论.js](./solution/1015德才论.js)和[1025反转链表.js](./solution/1025反转链表.js)的优化方法

### 遇到内存不足错误？
作出以下优化：
1. 确保使用同步模板
2. 避免创建超大数组
3. 使用Map代替大数组存储稀疏数据

### 确认自己的方法没错却总有测试点报错？ 
对于非C/C++/Java写题目的同学，这个问题客观存在，我在[1010一元多项式求导](./solution/1010一元多项式求导.js)、[1055集体照](./solution/1055集体照.js)、[1066图像过滤](./solution/1066图像过滤.js)均发现了这种情况
#### 问题原因❗❗❗
测试用例给错了，**多了空白符**（因为题目都是基于C/C++测试的，C++的`cin>>x`会自动过滤空白符，C语言、Java也类似，所以PTA平台只保证C/C++不会出问题）
  1. 有的测试用例分隔符会有多个空格或为其他空白符，尝试将`split(" ")`改为`split(/\s+/)`，使用正则分割处理连续空格
  2. 整个输入会有前导和尾随空格，把模板中`trimEnd()`改成`trim()`
  3. 每行输入都可能会有前导和尾随空格，需要在`input()`后面加上`trim()`

你可以参考我下面的题解自行修正模板，我个人认为这种情况比较少，没有在模板中加入
#### 1066 图像过滤
[https://pintia.cn/problem-sets/994805260223102976/exam/problems/type/7?problemSetProblemId=994805266514558976&page=0](https://pintia.cn/problem-sets/994805260223102976/exam/problems/type/7?problemSetProblemId=994805266514558976&page=0)
```javascript
"use strict";
// 修复 改为.trim()
const data = require("fs").readFileSync(0, "utf-8").trim().split("\n");
let line = 0;
// 修复 加入.trim()
const input = () => data[line++].trim() || "";
const number = () => +input();
// 修复 改为.split(/\s+/)
const numbers = () => input().split(/\s+/).map(Number);

// ================ 题目解答区域 ================
let [n, m, a, b, g] = numbers();
for (let i = 0; i < n; i++) {
    let parts = numbers().map((v) => {
        return (v >= a && v <= b ? g : v).toString().padStart(3, "0");
    });
    console.log(parts.join(" "));
}
```
### 确实无解（仅一题有这种情况）
[1052 卖个萌](https://pintia.cn/problem-sets/994805260223102976/exam/problems/type/7?problemSetProblemId=994805273883951104&page=0)
编码格式的问题，输入输出需要用GBK编码
我尝试过实现轻量级的编码器，但是PTA平台的NodeJS环境的`TextDecode()`API不支持GBK编码  
而在PTA平台代码长度16KB的限制下自己实现`TextDecode()`完全不现实（至少得上百K）

![PTA1052](./docs/pta1052.png)

**确认问题和编码器的实现参考了如下参考博客：**
[https://www.acwing.com/solution/content/171720/](https://www.acwing.com/solution/content/171720/)
[https://www.cnblogs.com/index-html/p/js-str-to-gbk-ultra-lite.html](https://www.cnblogs.com/index-html/p/js-str-to-gbk-ultra-lite.html)


## 优化实例
### PTA1025反转链表
以 [PTA1025反转链表](https://pintia.cn/problem-sets/994805260223102976/exam/problems/type/7?problemSetProblemId=994805296180871168&page=0) 为例，我在**算法已经达到最优解依然超时**的情况下做出如下优化，在`用时378 / 400 ms`的情况下成功压线AC
![PTA1025](./docs/pta1025.png)

### PTA1045快速排序
这题比较特殊，时间限制只有`200 ms`，只对Java的放宽限制到`800ms`，很明显对NodeJS这种动态语言不公平，原先我的算法已经是最优却依然超时，但我对**标准输出进行优化后**，直接获得了由TLE到`用时99 / 200 ms`成功AC的**巨幅提升**

![PTA1045](./docs/pta1045.png)
我原先的标准输出如下

```javascript
console.log(cnt);
for (let i = 0; i < cnt; i++) {
    if(i != 0) process.stdout.write(" ");
    process.stdout.write(v[i].toString());
}
console.log();
```

我把在循环中多次调用输出函数改为先将结果收集到result数组中统一输出，并统一用`process.stdout.write`，成功AC（从OJ反馈结果看至少有两倍以上的性能提升）

```javascript
process.stdout.write(`${cnt}\n`);
const result = []
for (let i = 0; i < cnt; i++) {
    result.push(v[i].toString());
}
process.stdout.write(`${result.join(" ")}\n`);
```

## 致谢
- 感谢[小深](https://chat.deepseek.com/)在项目开发中对我的技术与情感支持🩷   
- 感谢[PTA平台](https://pintia.cn)提供的评测环境和题目  

如果本仓库对您有帮助，欢迎 ⭐ Star 支持！(๑•̀ㅂ•́)و✧