分类： LeetCode笔记

题目描述

逆波兰式，更为人所知的名字是 “后缀表达式”。所谓后缀就是指运算算符写在操作数后面，我们平时习惯的 “中缀表达式” 是将运算符写在两个操作数之间。由于计算机内部就是采用后缀表达式的算法来计算表达式的值，所以实现此算法有着很高的现实意义。

阅读全文

题目描述

本题依然是使用 KMP 算法中 next 数组（最长相等前后缀）来解决。设字符串长度为 n，根据 next 数组的定义，next[i] 记录的是字符串 s[0...n-1] 的子串 s[0...i] 最长相同前后缀的长度。根据这个定义，字符串 s 的最长相等前后缀的长度为 next[n - 1]。

阅读全文

题目描述

本题实际上就是实现字符串匹配的 KMP 算法。与暴力匹配算法不同，KMP 算法在匹配模式串时主串的指针不会回溯。实现 KMP 算法的关键是求 next 数组，笔者在生成 next 数组时采用了将前缀表整体左移、next[0] 赋值 -1 的策略（如模式串为aabaaf，生成的 next 数组为 {-1, 0, 1, 0, 1, 2}），这样若模式串在 j 处不匹配时就通过 j = next[j] 回溯。

阅读全文

题目描述

本题的思路和 “三数之和” 完全一致，只需要在其基础上多套一层循环即可（理论上五数之和、六数之和都能通过加一层循环实现）。此外，由于 target 不再是 0，有一些额外的细节要注意。

阅读全文