LeetCode Practice Guide
本站所有的例题、习题都选自 力扣/LeetCode 的公开免费题目,并给出题目的链接,你可以直接跳转到官网进行练习。
为了照顾初学者,下面快速介绍一下 力扣/LeetCode 上提交代码的注意事项。
核心代码模式
在 力扣/LeetCode 上刷题,就是给你一个函数框架,你需要实现函数逻辑,这种模式一般称之为核心代码模式。
比如力扣第一题两数之和,就是让你实现这样一个 twoSum
函数:
class Solution {
public int[] twoSum(int[] nums, int target) {
}
}
class Solution:
def twoSum(self, nums: List[int], target: int) -> List[int]:
/**
* @param {number[]} nums
* @param {number} target
* @return {number[]}
*/
var twoSum = function(nums, target) {
};
class Solution {
public:
vector<int> twoSum(vector<int>& nums, int target) {
}
};
func twoSum(nums []int, target int) []int {
}
意思就是给你输入数组 nums
和目标值 target
,你需要实现算法逻辑,最后计算返回一个数组。
你的解法代码提交到后台,它会给这个 twoSum
函数传入若干预定义的测试用例,对比你的返回值和正确答案,以此判断你的代码是否正确。
Tips
对于 Java/C++,有些标准库会默认导入,你不需要显式导入就可以直接用一些常用的标准库数据结构,比如 Java 的 ArrayList
,C++ 的 vector
等。因为在网页上刷题时没有类似 IDE 的自动导入功能,所以这样还是比较省事的。
当然,如果你想要自动补全功能,可以考虑使用本站配套的 Jetbrains IDE 插件 或 vscode 插件。
ACM 模式
从用户角度来说,核心代码模式应该是最方便的形式,因为你只需要专心写好算法逻辑就行了。目前大部分刷题平台和技术面试/笔试场景都是核心代码模式。但是以防万一,这里还是要介绍一下 ACM 模式。
简单说,ACM 模式就是更麻烦一些,题目给你输入的是特定格式的字符串,你需要自己解析这个字符串,然后把计算结果输出到标准输出。
你的代码提交到后台后,系统会把每个测试用例(字符串)用标准输入传给你的程序,然后对比你程序的标准输出和预期输出是否相同,以此判断你的代码是否正确。
比如牛客网就提供这种 ACM 模式,我随便截个图你看看,代码编辑框没有任何初始代码,你需要从头自己写:
对于 ACM 模式,一个技巧就是要对代码分层,把对字符串输入的处理逻辑和真正的算法逻辑分开,类似这样:
public class Main {
public static void main(String[] args) {
Scanner scanner = new Scanner(System.in);
// mainly responsible for receiving and processing input data, constructing input cases
int[] nums;
int target;
int N = scanner.nextInt();
...
// call the algorithm logic to solve
System.out.println(twoSum(nums, target));
}
public static int[] twoSum(int[] nums, int target) {
// convert to core code mode, write algorithm logic here
}
}
这样看起来就很清晰,输入处理的逻辑可以作为模板直接复制粘贴,最终转化成核心代码模式,就和你在力扣上刷题就没什么区别了。
我的建议是,平时学习时,用核心代码形式就行了,简单方便。到了面试/笔试前夕,花上一个小时就能熟悉 ACM 模式了。我记得牛客网有专门练习这种 ACM 模式的例题,你自己搜索一下即可。
提交代码可能出现的错误
如果提交的代码可以通过后台的所有测试用例,则称为提交成功,我们也常说 AC(Accepted)。
如果提交的代码不能通过所有测试用例,则称为提交失败,常见的失败原因有以下几种:
编译错误(Compile Error)
代码无法通过编译,这种错误一般是语法错误,比如拼写错误、缺少分号等。一般网页上手搓代码容易出现这种错误,使用本站配套 Jetbrains IDE 插件 或 vscode 插件 的话,编辑器会有基本的语法检查功能,一般不会出现这种错误。
运行错误(Runtime Error)
代码可以编译通过,但是在运行时出现了数组越界、空指针异常等错误。这种错误一般是由于边界条件处理不当,你需要留意边界条件、特殊测试用例(也叫做 Corner case,比如输入为空等情况)。
答案错误(Wrong Answer)
代码可以编译通过,也可以运行,但是某些测试用返回的结果和正确答案不一致。这种错误一般是因为你的算法有问题,需要你根据出错的用例反思,甚至可能整个思路都错了,需要你推倒重来。
超时(Time Limit Exceeded,常简称为 TLE)
代码逻辑正确,也可以得到正确结果,但是运行时间超过了系统规定的时间限制,一般原因是算法的时间复杂度太高,需要查看是否有冗余计算,是否有更高效的解法思路。
内存超限(Memory Limit Exceeded,常简称为 MLE)
代码逻辑正确,也可以得到正确结果,但是运行时占用的内存超过了系统规定的内存限制,一般原因是算法的空间复杂度太高,需要查看是否有过多的空间占用,是否混淆了传值和传引用,是否有更高效的解法思路。
力扣提交代码的注意事项
对于初次使用力扣刷题的读者,我这里再介绍几个初学者容易踩的坑。
不要用文件级别的全局变量
前面说了力扣这种核心代码模式,会给你的算法代码输入若干预定义的测试用例,然后比较你的返回值和正确答案,那么就有很重要的一点:
你的代码不要用文件级别的全局变量,否则不同的测试用例之间可能会相互影响。力扣官网对于这个问题也有说明:https://support.leetcode.cn/hc/kb/article/1194344/
有些读者说他提交的解法通过不了,但是把出错的测试用例单独拎出来运行就是对的,一提交就错了,都是因为这个原因。你单独拎出来的时候只运行了一个测试用例,但提交后多个测试用例之间的数据产生了影响,就可能出错。
我在本站的教程中,尤其是讲解递归算法的部分,会经常提到「全局变量」这个词,但我指的全局变量并不是指文件级别的全局变量,而是类级别的全局变量。
具体举例说明吧,就比如二叉树的前序遍历这道题,题目输入一个二叉树的根节点,让你返回二叉树的前序遍历结果,你可以这样写:
class Solution {
// correct example, class-level global variable
LinkedList<Integer> res = new LinkedList<>();
public List<Integer> preorderTraversal(TreeNode root) {
traverse(root);
return res;
}
void traverse(TreeNode root) {
if (root == null) {
return;
}
// other functions within the class can access res
res.add(root.val);
traverse(root.left);
traverse(root.right);
}
}
// Incorrect example, do not define global variables at the file level
// vector<int> res;
class Solution {
public:
// Correct example, class-level global variable
vector<int> res;
vector<int> preorderTraversal(TreeNode* root) {
traverse(root);
return res;
}
void traverse(TreeNode* root) {
if (!root) {
return;
}
// Other functions within the class can access res
res.push_back(root->val);
traverse(root->left);
traverse(root->right);
}
};
// Incorrect example, do not define global variables at the file level
// var res []int
func preorderTraversal(root *TreeNode) []int {
// Correct example, use closure to allow the traverse function to also access the res variable
var res []int
var traverse func(*TreeNode)
traverse = func(root *TreeNode) {
if root == nil {
return
}
// Access and modify the res variable
res = append(res, root.Val)
traverse(root.Left)
traverse(root.Right)
}
traverse(root)
return res
}
# Wrong example, do not define global variables at the file level
# res = []
class Solution:
def preorderTraversal(self, root: TreeNode) -> List[int]:
# Correct example, class-level global variable
self.res = []
self.traverse(root)
return self.res
def traverse(self, root):
if not root:
return
# Other functions within the class can access res
self.res.append(root.val)
self.traverse(root.left)
self.traverse(root.right)
// Incorrect example, do not define global variables at the file level
// let res = [];
/**
* @param {TreeNode} root
* @return {number[]}
*/
var preorderTraversal = function(root) {
// Correct example, use closure to allow the traverse function to access the res variable internally
let res = [];
var traverse = (root) => {
if (!root) {
return;
}
// Access and modify the res variable
res.push(root.val);
traverse(root.left);
traverse(root.right);
}
traverse(root);
return res;
};
对于 Java/C++/Python 这种给了一个 Solution
类的情况,你就把需要共享访问的变量定义在类里面,对于 Go/JavaScript 这种没有类的情况,你可以定义高阶函数,运用闭包的特性,让内部函数也可以访问到共享变量。
或者,你可以把这个变量作为函数的参数传递,这样也是一种解决方案:
class Solution {
public List<Integer> preorderTraversal(TreeNode root) {
// correct example, passed as an argument to other functions
LinkedList<Integer> res = new LinkedList<>();
traverse(root, res);
return res;
}
void traverse(TreeNode root, LinkedList<Integer> res) {
if (root == null) {
return;
}
// access and modify the res variable
res.add(root.val);
traverse(root.left, res);
traverse(root.right, res);
}
}
// Incorrect example, do not define global variables at the file level
// vector<int> res;
class Solution {
public:
vector<int> preorderTraversal(TreeNode* root) {
// Correct example, pass as a parameter to other functions
vector<int> res;
traverse(root, res);
return res;
}
void traverse(TreeNode* root, vector<int>& res) {
if (!root) {
return;
}
// Access and modify the res variable
res.push_back(root->val);
traverse(root->left, res);
traverse(root->right, res);
}
};
// Wrong example, do not define global variables at the file level
// var res []int
func preorderTraversal(root *TreeNode) []int {
// Correct example, pass as a parameter to other functions
var res []int
traverse(root, &res)
return res
}
func traverse(root *TreeNode, res *[]int) {
if root == nil {
return
}
// Access and modify the res variable
*res = append(*res, root.Val)
traverse(root.Left, res)
traverse(root.Right, res)
}
# Wrong example, do not define global variables at the file level
# res = []
class Solution:
def preorderTraversal(self, root: TreeNode) -> List[int]:
# Correct example, pass as a parameter to other functions
res = []
self.traverse(root, res)
return res
def traverse(self, root, res):
if not root:
return
# Access and modify the res variable
res.append(root.val)
self.traverse(root.left, res)
self.traverse(root.right, res)
// Wrong example, do not define global variables at the file level
// let res = [];
/**
* @param {TreeNode} root
* @return {number[]}
*/
var preorderTraversal = function(root) {
// Correct example, pass it as a parameter to other functions
let res = [];
traverse(root, res);
return res;
}
var traverse = (root, res) => {
if (!root) {
return;
}
// Access and modify the res variable
res.push(root.val);
traverse(root.left, res);
traverse(root.right, res);
}
Important
对于这种方案,你要注意编程语言的特性,函数参数到底应该传值还是传引用/指针,否则会出现效率问题,甚至出错。
提交时清除标准输出
在运行测试用例时,力扣会把你的算法的标准输出返回给你,也就是说你可以通过 print 打印一些数据来调试代码。这里注意,准备提交代码前一定要把所有的打印语句注释掉。
因为标准输出是 IO 操作,非常消耗时间。如果包含了打印语句,也许你的算法代码本身就是最优解,但提交后发现执行效率非常差,甚至因为超时而无法通过。
好了,其他没啥了,开始学习吧!