百科.dev
全部条目在线工具AI 编程趋势榜开源项目技术资讯提交条目
登录
< 返回工具列表
L

LeetCodeSolutions

> 编程语言
开源

LeetCode 问题的理论解决方案。

397 stars0 点赞1 次浏览
访问官网GitHub

工具介绍

LeetCode 问题的理论解决方案。

LeetCode

Introduction

Here are theoretical solutions for some interesting LeetCode problems, aiming for the best running time. The author is a TCS student who no longer frequently write codes, so if you are looking for code implementations... sorry, this might be the wrong place. There's one exception though: if an algorithm with good theoretical guarantee is also practical enough to strictly beat 100% of the submissions, I will consider to implement it. See figs/ for a list of them.

p.s. If one doesn't like my coding style, he can use the following code formatting tools: https://codebeautify.org/cpp-formatter-beautifier, http://format.krzaq.cc/, or https://github.com/akof1314/CoolFormat

For most problems we consider here, the only thing we want to optimize is the running time. Randomization is usually allowed. Sometimes we will optimize on the space complexity as well. Lower bound will be provided, if the optimality of our algorithm is not obvious. If the main source of hardness of a problem is its coding complexity rather than the algorithm (e.g. simulation problems), we will skip the solution here.

Notations

In some problems we will use the word-RAM model, where the assumption is each word has w bits and can store integers up to size W=2^w. In practice (i.e. 32-bit machines), w=32 and W=2^32. We assume the word length is w=\Omega(\log n), and the following basic word operations in the multiplicative instruction set can be executed in O(1): +, -, (*), &, |, ^, ~, >. By setting w'=\delta_0\log n for a sufficiently small constant \delta_0>0, we can simulate nonstandard word operations on w'-bit words in O(1) time by table lookup, with n^{O(\delta_0)}=o(n) preprocessing time. Theoretically speaking, you can always implement algorithms in the word-RAM model in codes.

For string, let |\Sigma| denote the alphabet size (i.e. |\Sigma|=26 for lowercase letters), and we usually assume |\Sigma| is much smaller than n. In some cases, we further make the (non-theory) assumption that |\Sigma|<=w (since 26<32). If the input is a set of strings, we will use L to denote the total length of them, and n is the number of strings. If the input is a single string, we use n to denote its length.

For trees, let h denote the height.

For graphs, let n denote the number of vertices and m denote the number of edges.

If the input is an n*m matrix, we sometimes use a single parameter n to denote max(n,m) for simplicity.

For space complexity, we use the definition which is in analogy to the following: for a TM with a (read-only) input tape, an output tape and work tapes, only the number of memory cells on work tapes counts. Here we assume the input is read-only, and for space complexity, we only count the number of memory cells on which we write. Note that this is different from the (relatively weaker) LeetCode definition, which usually allows in-place modifications to the memory cells containing the inputs. We call that definition "additional space complexity".

Unsolved Problems

Here are a list of problems for which I don't know the current best algorithm. If a problem is open but the algorithm I provide here is (almost) the current best, it is viewed as "solved" and therefore not listed below. Some NP-hard problems are also not included.

open_problems.txt

Miscellaneous Topics

Get your hands dirty: miscellaneous_topics.pdf

Stargazers over time

Issues· 1 开放

查看全部 Issues在 GitHub 打开

暂无开放 Issues,或尚未同步最近议题。

> 标签

C++algorithmsdata-structuresleetcodeleetcode-cpp

暂无评论,来聊聊你的看法吧

> 工具信息

发布日期2026年8月1日
最后更新2026年9月17日
分类编程语言
定价开源

> 相关工具

T
TypeScript
JavaScript 的超集,为前端与全栈提供静态类型
P
Python
通用编程语言,广泛用于 Web、数据与 AI
G
Go
Google 推出的简洁高效系统语言