四个复杂度

• 时间复杂度（核心）
• 空间复杂度（次要）
• 编程复杂度
• 思维复杂度

时间复杂度

P问题 Polynomial (多项式问题) O(n), O(n^2), …, O(n^k) O(sqrt(n)), O(1) O(log(n)), O(nlog(n))

NP问题 Non-deterministic Polynomial (非确定性多项式问题), 不能在多项式时间内解决 O(2^n), O(n!), O(n^n)

时间复杂度为 O(N) 的算法: 双指针，单调栈算法

双指针算法

• 相向双指针（判断回文串）
  • reverse 型
    • 翻转字符串
    • 判断回文串
  • two sume 两数、三数之和
  • partition 快速排序，颜色排序
• 背向双指针（最长回文串）
• 同向双指针

判断回文字符串，判断字符的函数很重要

c.isdigit()
c.isalpha()

c.lower()
c.upper()

Character.isLetter(c)
Character.isDigit(c)
Character.isLetterOrDigit(c)

Character.toLowerCase(c)
Character.toUpperCase(c)