算法笔试「骗分」套路

———–

首先回答一个问题,刷力扣题是直接在网页上刷比较好还是在本地 IDE 上刷比较好?

如果是牛客网笔试那种自己处理输入输出的判题形式,一定要在 IDE 上写,这个没啥说的,但像力扣这种判题形式,我个人偏好直接在网页上刷,原因有二:

1、方便

因为力扣有的数据结构是自定的,比如说 TreeNodeListNode 这种,在本地你还得把这个类 copy 过去。

而且在 IDE 上没办法测试,写完代码之后还得粘贴到网页上跑测试数据,那还不如直接网页上写呢。

算法又不是工程代码,量都比较小,IDE 的自动补全带来的收益基本可以忽略不计。

2、实用

到时候面试的时候,面试官给你出的算法题大都是希望你直接在网页上完成的,最好是边写边讲你的思路。

如果平时练习的时候就习惯没有 IDE 的自动补全,习惯手写代码大脑编译,到时候面试的时候写代码就能更快更从容。

之前我面快手的时候,有个面试官让我 实现 LRU 算法,我直接把双链表的实现、哈希链表的实现,在网页上全写出来了,而且一次无 bug 跑通,可以看到面试官惊讶的表情😂

我秋招能当 offer 收割机,很大程度上就是因为手写算法这一关超出面试官的预期,其实都是因为之前在网页上刷题练出来的。

当然,实在不想在网页上刷,也可以用我的 vscode 刷题插件或者 JetBrains 刷题插件,插件和我的网站内容都有完美的融合:

避实就虚

大家也知道,大部分笔试题目都需要你自己来处理输入数据,然后让程序打印输出。判题的底层原理是,把你程序的输出用 Linux 重定向符 > 写到文件里面,然后比较你的输出和正确答案是否相同。

那么有的问题难点就变得形同虚设,我们可以偷工减料,举个简化的例子,假设题目说给你输入一串用空格分隔的字符,告诉你这代表一个单链表,请你把这个单链表翻转,并且强调,一定要把输入的数字转化成单链表之后再翻转哦!

那你怎么做?真就自己定义一个 ListNode 单链表节点类,然后再写代码把输入转化成一个单链表,然后再用让人头晕的指针操作去老老实实翻转单链表?

搞清楚我们是来 AC 题目的,不是来学习算法思维的。正确的做法是直接把输入存到数组里,然后用 双指针技巧 几行代码给它翻转了,然后打印出来完事儿。

我就见过不少这种题目,比如题目说输入的是一个单链表,让我分组翻转链表,而且还特别强调要用递归实现,就是我们后文 K 个一组翻转链表 的算法。嗯,如果用数组进行翻转,两分钟就写出来了,嘿嘿。

还有我们后文 扁平化嵌套列表 讲到的题目,思路很巧妙,但是在笔试中遇到时,输入是一个形如 [1,[4,[6]]] 的字符串,那直接用正则表达式把数字抽出来,就是一个扁平化的列表了……

巧用随机数

再说一个鸡贼的技巧,注意那些输出为「二值」的题目,二值就是类似布尔值,或者 0 和 1 这种组合有限的。

比如说很多题目是这样,巴拉巴拉给你说一堆条件,然后问你输入的数据能不能达成这些条件,如果能的话请输出 YES,不能的话输出 NO

如果你会做当然好,如果不会做怎么办?

首先这样提交一下:

public class Main {
    public static void main(String[] args) {
        System.out.println("YES");
    }
}
// 注意:cpp 代码由 chatGPT🤖 根据我的 java 代码翻译,旨在帮助不同背景的读者理解算法逻辑。
// 本代码还未经过力扣测试,仅供参考,如有疑惑,可以参照我写的 java 代码对比查看。

class Solution {
public:
    void main() {
        cout << "YES" << endl;
    }
};
# 注意:python 代码由 chatGPT🤖 根据我的 java 代码翻译,旨在帮助不同背景的读者理解算法逻辑。
# 本代码还未经过力扣测试,仅供参考,如有疑惑,可以参照我写的 java 代码对比查看。

print("YES")
// 注意:go 代码由 chatGPT🤖 根据我的 java 代码翻译,旨在帮助不同背景的读者理解算法逻辑。
// 本代码还未经过力扣测试,仅供参考,如有疑惑,可以参照我写的 java 代码对比查看。

/*
// This code can be run on playground: https://play.golang.org/
*/

import (
    "fmt"
)

func main() {
    fmt.Println("YES")
}
// 注意:javascript 代码由 chatGPT🤖 根据我的 java 代码翻译,旨在帮助不同背景的读者理解算法逻辑。
// 本代码还未经过力扣测试,仅供参考,如有疑惑,可以参照我写的 java 代码对比查看。

/**
 * @param {string[]} args
 * @return {void}
 */
var main = function(args) {
    console.log("YES"); 
};

看下 case 通过率,假设是 60%,那么说明结果为 YES 有 60% 的概率,所以可以这样写代码:

public class Main {
    public static void main(String[] args) {
        // 60% 的概率输出 YES,40% 的概率输出 NO
        System.out.println((new Random().nextInt() % 100) < 60 ? "YES" : "NO");
    }
}
// 注意:cpp 代码由 chatGPT🤖 根据我的 java 代码翻译,旨在帮助不同背景的读者理解算法逻辑。
// 本代码还未经过力扣测试,仅供参考,如有疑惑,可以参照我写的 java 代码对比查看。

class Solution {
public:
    void run() {
        // 60% 的概率输出 YES,40% 的概率输出 NO
        cout << (rand() % 100 < 60 ? "YES" : "NO") << endl;
    }
};
# 注意:python 代码由 chatGPT🤖 根据我的 java 代码翻译,旨在帮助不同背景的读者理解算法逻辑。
# 本代码还未经过力扣测试,仅供参考,如有疑惑,可以参照我写的 java 代码对比查看。

import random

# 60% 的概率输出 YES,40% 的概率输出 NO
print("YES" if random.randint(0, 99) < 60 else "NO")
// 注意:go 代码由 chatGPT🤖 根据我的 java 代码翻译,旨在帮助不同背景的读者理解算法逻辑。
// 本代码还未经过力扣测试,仅供参考,如有疑惑,可以参照我写的 java 代码对比查看。

import (
    "fmt"
    "math/rand"
    "time"
)

func main() {
    rand.Seed(time.Now().UnixNano()) // 设置随机数种子
    if rand.Int31n(100) < 60 {
        fmt.Println("YES")
    } else {
        fmt.Println("NO")
    }
}
// 注意:javascript 代码由 chatGPT🤖 根据我的 java 代码翻译,旨在帮助不同背景的读者理解算法逻辑。
// 本代码还未经过力扣测试,仅供参考,如有疑惑,可以参照我写的 java 代码对比查看。

/**
 * 根据题意可知,随机生成一个数,小于 60 则输出 "YES",否则输出 "NO"
 */
var main = function() {
    console.log((new Random().nextInt() % 100) < 60 ? "YES" : "NO");
};

嘿嘿,这题你可以不会,但是一定要在力所能及的范围内做到极致!

编程语言的选择

仅从做算法题的角度来说,我个人比较建议使用 Java 作为笔试的编程语言。因为 JetBrain 家的 IntelliJ 实在是太香了,相比其他语言的编辑器,不仅有 psvmsout 这样的快捷命令(你要是连这都不知道,赶紧面壁去),而且可以帮你检查出很多笔误,比如说 while 循环里面忘记递增变量,或者 return 语句错写到循环里这种由于疏忽所导致的问题。

C++ 也还行,但是我觉得没有 Java 好用。我印象中 C++ 连个分割字符串的 split 函数都没有,光这点我就不想用 C++ 了……

还有一点,C++ 代码对时间的限制高,别的语言时间限制 4000ms,C++ 限制 2000ms,我觉得挺吃亏的。怪不得看别人用 C++ 写算法,为了提高速度,都不用标准库的 vector 容器,非要用原始的 int[] 数组,我看着都头疼。

Python 的话我刷题用的比较少,因为我不太喜欢用动态语言,不好调试。不过这个语言确实提供很多实用的功能,如果你深谙 Python 的套路,可以在某些时候投机取巧。比如说我们前文写到的 表达式求值算法 是一个困难级别的算法,但如果用 Python 内置的 exec 函数,直接就能算出答案。

这个在笔试里肯定是很占便宜的,因为之前说了,我们要的是结果,没人在乎你是怎么得到结果的。

解法代码分层

代码分层应该算是一种比较好的习惯,可以增加写代码的速度和降低调试的难度。

简单说就是,不要把所有代码都写在 main 函数里面,我一直使用的套路是,main 函数负责接收数据,加一个 solution 函数负责统一处理数据和输出答案,然后再用诸如 backtrack 这样一个函数处理具体的算法逻辑。

举个例子,比如说一道题,我决定用带备忘录的动态规划求解,代码的大致结构是这样:

public class Main {
    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);
        // 主要负责接收数据
        int N = scanner.nextInt();
        int[][] orders = new int[N][2];
        for (int i = 0; i < N; i++) {
            orders[i][0] = scanner.nextInt();
            orders[i][1] = scanner.nextInt();
        }
        // 委托 solution 进行求解
        solution(orders);
    }

    static void solution(int[][] orders) {
        // 排除一些基本的边界情况
        if (orders.length == 0) {
            System.out.println("None");
            return;
        }
        // 委托 dp 函数执行具体的算法逻辑
        int res = dp(orders, 0);
        // 负责输出结果
        System.out.println(res);
    }

    // 备忘录
    static HashMap<String, Integer> memo = new HashMap<>();
    static int dp(int[][] orders, int start) {
        // 具体的算法逻辑
    }
}
// 注意:cpp 代码由 chatGPT🤖 根据我的 java 代码翻译,旨在帮助不同背景的读者理解算法逻辑。
// 本代码还未经过力扣测试,仅供参考,如有疑惑,可以参照我写的 java 代码对比查看。

#include <iostream>
#include <unordered_map>
#include <vector>

using namespace std;

void solution(vector<vector<int>>& orders);

int dp(vector<vector<int>>& orders, int start, unordered_map<string, int>& memo);

int main() {
    // 主要负责接收数据
    int N;
    cin >> N;
    vector<vector<int>> orders(N, vector<int>(2));
    for (int i = 0; i < N; i++) {
        cin >> orders[i][0] >> orders[i][1];
    }
    // 委托 solution 进行求解
    solution(orders);
    return 0;
}

void solution(vector<vector<int>>& orders) {
    // 排除一些基本的边界情况
    if (orders.empty()) {
        cout << "None" << endl;
        return;
    }
    // 委托 dp 函数执行具体的算法逻辑
    unordered_map<string, int> memo;
    int res = dp(orders, 0, memo);
    // 负责输出结果
    cout << res << endl;
}

// 备忘录
int dp(vector<vector<int>>& orders, int start, unordered_map<string, int>& memo) {
    // 具体的算法逻辑
}
# 注意:python 代码由 chatGPT🤖 根据我的 java 代码翻译,旨在帮助不同背景的读者理解算法逻辑。
# 本代码还未经过力扣测试,仅供参考,如有疑惑,可以参照我写的 java 代码对比查看。

from typing import List
def solution(orders: List[List[int]]) -> None:
    # 排除一些基本的边界情况
    if len(orders) == 0:
        print("None")
        return
    # 备忘录
    memo = {}
    # 委托 dp 函数执行具体的算法逻辑
    res = dp(orders, 0, memo)
    # 负责输出结果
    print(res)

# 具体的算法逻辑
def dp(orders: List[List[int]], start: int, memo: dict) -> int:
    if str([start, len(orders)]) in memo:
        return memo[str([start, len(orders)])]
    if start == len(orders):
        return 0
    taken = orders[start][1] + dp(orders, start + 1, memo)
    not_taken = dp(orders, start + 1, memo)
    res = max(taken, not_taken)
    memo[str([start, len(orders)])] = res
    return res

if __name__ == "__main__":
    # 主要负责接收数据
    N = int(input())
    orders = []
    for i in range(N):
        orders_i = list(map(int, input().strip().split()))
        orders.append(orders_i)
    # 委托 solution 进行求解
    solution(orders)
// 注意:go 代码由 chatGPT🤖 根据我的 java 代码翻译,旨在帮助不同背景的读者理解算法逻辑。
// 本代码还未经过力扣测试,仅供参考,如有疑惑,可以参照我写的 java 代码对比查看。

import (
	"fmt"
	"bufio"
	"os"
	"strings"
	"strconv"
)

func main() {
    // 主要负责接收数据
    var N int
    fmt.Scan(&N)
    orders := make([][2]int, N)
    scanner := bufio.NewScanner(os.Stdin)
    scanner.Scan()
    for i := 0; i < N; i++ {
        scanner.Scan()
        str := scanner.Text()
        arr := strings.Fields(str)
        num1, _ := strconv.Atoi(arr[0])
        num2, _ := strconv.Atoi(arr[1])
        orders[i][0] = num1
        orders[i][1] = num2
    }
    // 委托 solution 进行求解
    solution(orders)
}

func solution(orders [][2]int) {
    // 排除一些基本的边界情况
    if len(orders) == 0 {
        fmt.Println("None")
        return
    }
    // 委托 dp 函数执行具体的算法逻辑
    res := dp(orders, 0)
    // 负责输出结果
    fmt.Println(res)
}

// 备忘录
var memo map[string]int
func dp(orders [][2]int, start int) int {
    if memo == nil {
        memo = make(map[string]int)
    }
    // 具体的算法逻辑
}
// 注意:javascript 代码由 chatGPT🤖 根据我的 java 代码翻译,旨在帮助不同背景的读者理解算法逻辑。
// 本代码还未经过力扣测试,仅供参考,如有疑惑,可以参照我写的 java 代码对比查看。

var memo = new Map();

function solution(orders) {
  if (orders.length === 0) {
    console.log("None");
    return;
  }
  var res = dp(orders, 0);
  console.log(res);
}

function dp(orders, start) {
  // 具体的算法逻辑
}

function main() {
  var scanner = require('readline-sync');
  var N = parseInt(scanner.question());
  var orders = Array(N).fill(null).map(() => Array(2));
  for (var i = 0; i < N; i++) {
    orders[i][0] = parseInt(scanner.question());
    orders[i][1] = parseInt(scanner.question());
  }
  solution(orders);
}

main();

你看这样分层是不是很清楚,每个函数都有自己主要负责的任务,如果哪里出了问题,你也容易 debug。

倒不是说要把代码写得多规范,至于 private 这种约束免了也无妨,变量用拼音命名也 OK,关键是别把代码直接全写到 main 函数里面,真的乱,不出错也罢,一旦出错,估计要花一番功夫调试了,找不到问题乱了阵脚,那是要尽量避免的。

如何给算法 debug

代码的错误是无法避免的,有时候可能整个思路都错了,有时候可能是某些细节问题,比如 ij 写反了,这种问题怎么排查?

我想一般的算法问题肯定不难排查,肉眼检查应该都没啥问题,再不济 print 打印一些关键变量的值,总能发现问题。

比较让人头疼的的应该是递归算法的问题排查

如果没有一定的经验,函数递归的过程很难被正确理解,所以这里就重点讲讲如何高效 debug 递归算法。

有的读者可能会说,把算法 copy 到 IDE 里面,然后打断点一步步跟着走不就行了吗?

这个方法肯定是可以的,但是之前的文章多次说过,递归函数最好从一个全局的角度理解,而不要跳进具体的细节。

如果你对递归还不够熟悉,没有一个全局的视角,这种一步步打断点的方式也容易把人绕进去。

我的建议是直接在递归函数内部打印关键值,配合缩进,直观地观察递归函数执行情况

最能提升我们 debug 效率的是缩进,除了解法函数,我们新定义一个函数 printIndent 和一个全局变量 count

// 注意:java 代码由 chatGPT🤖 根据我的 cpp 代码翻译,旨在帮助不同背景的读者理解算法逻辑。
// 本代码还未经过力扣测试,仅供参考,如有疑惑,可以参照我写的 cpp 代码对比查看。

// 全局变量,记录递归函数的递归层数
int count = 0;

// 输入 n,打印 n 个 tab 缩进
void printIndent(int n) {
    for (int i = 0; i < n; i++) {
        System.out.print("   ");
    }
}
// 全局变量,记录递归函数的递归层数
int count = 0;

// 输入 n,打印 n 个 tab 缩进
void printIndent(int n) {
    for (int i = 0; i < n; i++) {
        printf("   ");
    }
}
# 注意:python 代码由 chatGPT🤖 根据我的 cpp 代码翻译,旨在帮助不同背景的读者理解算法逻辑。
# 本代码还未经过力扣测试,仅供参考,如有疑惑,可以参照我写的 cpp 代码对比查看。

# 全局变量,记录递归函数的递归层数
count = 0

# 输入 n,打印 n 个 tab 缩进
def printIndent(n):
    for i in range(n):
        print("   ", end="")
// 注意:go 代码由 chatGPT🤖 根据我的 cpp 代码翻译,旨在帮助不同背景的读者理解算法逻辑。
// 本代码还未经过力扣测试,仅供参考,如有疑惑,可以参照我写的 cpp 代码对比查看。

// 全局变量,记录递归函数的递归层数
var count int

// 输入 n,打印 n 个 tab 缩进
func printIndent(n int) {
    for i := 0; i < n; i++ {
        fmt.Printf("   ")
    }
}
// 注意:javascript 代码由 chatGPT🤖 根据我的 cpp 代码翻译,旨在帮助不同背景的读者理解算法逻辑。
// 本代码还未经过力扣测试,仅供参考,如有疑惑,可以参照我写的 cpp 代码对比查看。

// 全局变量,记录递归函数的递归层数
var count = 0;

// 输入 n,打印 n 个 tab 缩进
function printIndent(n) {
    for (var i = 0; i < n; i++) {
        console.log("   ");
    }
}

接下来,套路来了:

在递归函数的开头,调用 printIndent(count++) 并打印关键变量;然后在所有 return 语句之前调用 printIndent(--count) 并打印返回值

举个具体的例子,比如说上篇文章 练琴时悟出的一个动态规划算法 中实现了一个递归的 dp 函数,大致的结构如下:

// 注意:java 代码由 chatGPT🤖 根据我的 cpp 代码翻译,旨在帮助不同背景的读者理解算法逻辑。
// 本代码还未经过力扣测试,仅供参考,如有疑惑,可以参照我写的 cpp 代码对比查看。

int dp(String ring, int i, String key, int j) {
    /* base case */
    if (j == key.length()) {
        return 0;
    }

    /* 状态转移 */
    int res = Integer.MAX_VALUE;
    for (int k : charToIndex.get(key.charAt(j))) {
        res = Math.min(res, dp(ring, j, key, i + 1));
    }

    return res;
}
int dp(string& ring, int i, string& key, int j) {
    /* base case */
    if (j == key.size()) {
        return 0;
    }

    /* 状态转移 */
    int res = INT_MAX;
    for (int k : charToIndex[key[j]]) {
        res = min(res, dp(ring, j, key, i + 1));
    }

    return res;
}
# 注意:python 代码由 chatGPT🤖 根据我的 cpp 代码翻译,旨在帮助不同背景的读者理解算法逻辑。
# 本代码还未经过力扣测试,仅供参考,如有疑惑,可以参照我写的 cpp 代码对比查看。

# base case
def dp(ring: str, i: int, key: str, j: int) -> int:
    if j == len(key):
        return 0

    # 状态转移
    res = float("inf")
    for k in charToIndex[key[j]]:
        res = min(res, dp(ring, j, key, i + 1))

    return res
// 注意:go 代码由 chatGPT🤖 根据我的 cpp 代码翻译,旨在帮助不同背景的读者理解算法逻辑。
// 本代码还未经过力扣测试,仅供参考,如有疑惑,可以参照我写的 cpp 代码对比查看。

func dp(ring string, i int, key string, j int) int {
    /* base case */
    if j == len(key) {
        return 0
    }

    /* 状态转移 */
    res := math.MaxInt32
    for _, k := range charToIndex[key[j]] {
        res = min(res, dp(ring, j, key, i + 1))
    }

    return res
}
// 注意:javascript 代码由 chatGPT🤖 根据我的 cpp 代码翻译,旨在帮助不同背景的读者理解算法逻辑。
// 本代码还未经过力扣测试,仅供参考,如有疑惑,可以参照我写的 cpp 代码对比查看。

var dp = function(ring, i, key, j){
    /* base case */
    if(j === key.length){
        return 0;
    }
  
    /* 状态转移 */
    let res = Infinity;
    for(let k of charToIndex[key[j]]){
        res = Math.min(res, dp(ring, j, key, i+1));
    }
  
    return res;
}

这个递归的 dp 函数在我进行了 debug 之后,变成了这样:

// 注意:java 代码由 chatGPT🤖 根据我的 cpp 代码翻译,旨在帮助不同背景的读者理解算法逻辑。
// 本代码还未经过力扣测试,仅供参考,如有疑惑,可以参照我写的 cpp 代码对比查看。

int count = 0;

void printIndent(int n) {
    for (int i = 0; i < n; i++) {
        System.out.print("   ");
    }
}

int dp(String ring, int i, String key, int j) {
    // printIndent(count++);
    // System.out.format("i = %d, j = %d%n", i, j);

    if (j == key.length()) {
        // printIndent(--count);
        // System.out.println("return 0");
        return 0;
    }

    int res = Integer.MAX_VALUE;
    for (int k : charToIndex.get(key.charAt(j))) {
        res = Math.min(res, dp(ring, j, key, i + 1));
    }

    // printIndent(--count);
    // System.out.format("return %d%n", res);
    return res;
}
int count = 0;
void printIndent(int n) {
    for (int i = 0; i < n; i++) {
        printf("   ");
    }
}

int dp(string& ring, int i, string& key, int j) {
    // printIndent(count++);
    // printf("i = %d, j = %d\n", i, j);
    
    if (j == key.size()) {
        // printIndent(--count);
        // printf("return 0\n");
        return 0;
    }
    
    int res = INT_MAX;
    for (int k : charToIndex[key[j]]) {
        res = min(res, dp(ring, j, key, i + 1));
    }
    
    // printIndent(--count);
    // printf("return %d\n", res);
    return res;
}
# 注意:python 代码由 chatGPT🤖 根据我的 cpp 代码翻译,旨在帮助不同背景的读者理解算法逻辑。
# 本代码还未经过力扣测试,仅供参考,如有疑惑,可以参照我写的 cpp 代码对比查看。

count = 0

def printIndent(n):
    for i in range(n):
        print("   ", end='')

def dp(ring, i, key, j, charToIndex):
    global count
    # printIndent(count)
    # print("i = %d, j = %d" % (i, j))

    if j == len(key):
        # count -= 1
        # printIndent(count)
        # print("return 0")
        return 0

    res = float('inf')
    for k in charToIndex[key[j]]:
        d = abs(k - i)
        minDist = min(d, len(ring) - d)
        res = min(res, minDist + dp(ring, k, key, j + 1, charToIndex))

    # count -= 1
    # printIndent(count)
    # print("return %d" % res)
    return res
// 注意:go 代码由 chatGPT🤖 根据我的 cpp 代码翻译,旨在帮助不同背景的读者理解算法逻辑。
// 本代码还未经过力扣测试,仅供参考,如有疑惑,可以参照我写的 cpp 代码对比查看。

var count int

func printIndent(n int) {
    for i := 0; i < n; i++ {
        fmt.Printf("   ")
    }
}

func dp(ring string, i int, key string, j int) int {
    // printIndent(count++)
    // fmt.Printf("i = %d, j = %d\n", i, j)

    if j == len(key) {
        // printIndent(--count)
        // fmt.Printf("return 0\n")
        return 0
    }

    res := math.MaxInt32
    for _, k := range charToIndex[key[j]] {
        res = int(math.Min(float64(res), float64(dp(ring, j, key, i + 1))))
    }

    // printIndent(--count)
    // fmt.Printf("return %d\n", res)
    return res
}
// 注意:javascript 代码由 chatGPT🤖 根据我的 cpp 代码翻译,旨在帮助不同背景的读者理解算法逻辑。
// 本代码还未经过力扣测试,仅供参考,如有疑惑,可以参照我写的 cpp 代码对比查看。

var count = 0;
function printIndent(n) {
    for (var i = 0; i < n; i++) {
        console.log("   ");
    }
}

function dp(ring, i, key, j) {
    // printIndent(count++);
    // console.log("i = " + i + ", j = " + j);
    
    if (j === key.length) {
        // printIndent(count--);
        // console.log("return 0");
        return 0;
    }
    
    var res = Number.MAX_SAFE_INTEGER;
    for (var k of charToIndex[key[j]]) {
        res = Math.min(res, dp(ring, j, key, i + 1));
    }
    
    // printIndent(count--);
    // console.log("return " + res);
    return res;
}

就是在函数开头和所有 return 语句对应的地方加上一些打印代码

如果去掉注释,执行一个测试用例,输出如下:

这样,我们通过对比对应的缩进就能知道每次递归时输入的关键参数 i, j 的值,以及每次递归调用返回的结果是多少。

最重要的是,这样可以比较直观地看出递归过程,你有没有发现这就是一棵递归树

前文 动态规划套路详解 说过,理解递归函数最重要的就是画出递归树,这样打印一下,连递归树都不用自己画了,而且还能清晰地看出每次递归的返回值。

可以说,这是对刷题「幸福感」提升最大的一个小技巧,比 IDE 打断点要高效

考前复习策略

考前就别和某一道算法题死磕了,不划算。

应该尽可能多的看各种各样的题目,思考五分钟,想不出来解法的话直接看别人的答案。看懂思路就行了,甚至自己写一遍都没必要,因为比较浪费时间。

笔试的时候最怕的是没思路,所以把各种题型都过目一下,起码心里不会慌,只要有思路,平均一道题二三十分钟搞定还是不难的。

前面不是说了么,没有什么问题是暴力穷举解决不了的,直接用 回溯算法套路框架 硬上,大不了加个备忘录,不就成 动态规划套路框架 了么,再大不了这题我不做了么,暴力过上 60% 的 case 也挺 OK 的。

别的不多说了,套路这个东西,说来简单,一点就透,但问题是不点就不透。本文我简单介绍了几个笔试算法的技巧,各位好好品味~

最后,请秋招的同学多向身边的朋友推荐 labuladong 公众号。算法真的没那么难,这一切只是手段而已,过算法笔试拿 offer 才是目的。为了达到目的,套路是必须的,可以少走很多弯路,你的朋友会感谢你的,我也会感谢你的😏


引用本文的文章

_____________

《labuladong 的算法小抄》已经出版,关注公众号查看详情;后台回复关键词「进群」可加入算法群;回复「全家桶」可下载配套 PDF 和刷题全家桶

共同维护高质量学习环境,评论礼仪见这里,违者直接拉黑不解释