Home

Leetcode刷题总结

一般的解题思路：

1. 当问题可以分解为相同（较小规模）的子问题时，可以考虑使用递归

关于如何设计递归函数？

stackoverflow：How to perform a recursive search?

Result M(Problem prob)
{
    if (<problem can be solved easily>)
        return <easy solution>;
    // The problem cannot be solved easily.
    Problem smaller1 = <reduce problem to smaller problem>
    Result result1 = M(smaller1);
    Problem smaller2 = <reduce problem to smaller problem>
    Result result2 = M(smaller2);
    ...
    Result finalResult = <combine all results of smaller problem to solve large problem>
    return finalResult;
}

• Unique Binary Search Trees II

• 排列组合： Combinations, Permutations

• 螺旋矩阵： Spiral Matrix, Spiral Matrix II（递归的思路, 注意边界条件）

---

2. 二叉树相关的问题，一般都可以考虑使用递归

递归（recursive）与迭代（iterative）solution !

• 深度优先搜索 DFS（Depth-First Search）：非递归实现可以使用**栈（stack）**作为辅助工具

  例题：Path Sum, Path Sum II, Maximum Depth of Binary Tree, Minimum Depth of Binary Tree

• 广度优先搜索 BFS（Breadth-First Search）：非递归实现可以使用**队列（queue）**作为辅助工具

• 递归：Same Tree, Convert Sorted Array to Binary Search Tree, Convert Sorted List to Binary Search Tree

• 前序遍历（Preorder）：Binary Tree Preorder Traversal， 递归解法很简单就不说了，迭代解法借助stack来实现，也很简单，取出栈顶节点，并将其右、左子节点压栈。

• 中序遍历（Inorder）：Binary Tree Inorder Traversal， 迭代解法，不断遍历非空左子节点并压栈，然后取出栈顶节点，访问其右子节点

• 后序遍历（Postorder）：Binary Tree Postorder Traversal

---

3. 链表相关的问题

• 链表中的元素只能是顺序访问的。

  例题：Partition List （Two Pointers / 双指针问题）

  链表反转：Reverse Linked List II（仔细分析可以发现规律）

---

4. 数组相关的问题

• 数组中的元素可以根据位置下标进行随机访问。

• 删除有序数组中重复的元素：Remove Duplicates from Sorted Array, Remove Duplicates from Sorted Array II, ...

• 合并两个有序数组：Merge Sorted Array

为了避免无谓的重复移动数组元素（插入/删除某个元素时）, 可以通过数组靠后的元素逐个覆盖前面的元素（时间复杂度O（N））, 从后向前合并（时间复杂度O（M+N））

• 二分查找（Binary Search）的一种应用：Search in Rotated Sorted Array, Search in Rotated Sorted Array II

---

5. 字符串相关的问题

例如：Longest Common Prefix, Count and Say

字符串转整数：String to Integer (atoi) （去除开头的white-space字符；系统调用isdigit(), **isspace()**等）

• C/C++中字符串是以字符 '\0' 结尾，这是在字符串处理中可以加以利用的特点！

• 相同类型的问题（Hash Table, Two Pointers）：Longest Substring Without Repeating Characters, Substring with Concatenation of All Words

---

6. 动态规划 DP（Dynamic Programming）

• 比较难，关键是要能想到状态转移方程

• 动态规划：从新手到专家

  一维DP： Climbing Stairs, Unique Binary Search Trees , Unique Paths, Minimum Path Sum,

  Best Time to Buy and Sell Stock, Best Time to Buy and Sell Stock III

  二维DP： Edit Distance , Distinct Subsequences

---

7. 贪心

• 例如：Best Time to Buy and Sell Stock II

---

8. 回溯（Backtracking）

• N皇后问题（N-Queens, N-Queens II）, Sudoku Solver都是相同的解法套路！

  例题：Subsets, Subsets II

---

9. 分治

---

10. 二分/折半

• 时间复杂度O(log N)

• Binary Search（元素必须是已经排序的）：Search for a Range （两次二分）

• 求x(double)的n(int)次方：Pow(x, n)

  求平方根：Sqrt(x) （另一种数学解法：牛顿迭代）

  避免大量的重复计算，时间复杂度从O(N)降到O(lgN)

• 二分查找的应用：Median of Two Sorted Arrays, 这个问题可以延伸为 Find the k-th Smallest Element in the Union of Two Sorted Arrays

---

11. Hash表 和 Two Pointers

几道相同类型的题目：Two Sum , 3Sum , 3Sum Closest , 4Sum

Hash Table: Anagrams (关于字符串hash：各种字符串Hash函数比较)

---

12. 图

• 无向图的遍历：Clone Graph

---

13. 数据结构

• LRU Cache（Hash Map + 双向链表）

  1. 如何用C++实现一个LRU Cache
  2. Implement LRU Cache
  3. LRU cache implementation in C++

---

14. 一些常见的排序算法

Sorting Algorithm	Best	Average	Worst
QuickSort	O(nlogn)	O(nlogn)	O(n^2)
MergeSort	O(nlogn)	O(nlogn)	O(nlogn)
HeapSort	O(nlogn)	O(nlogn)	O(nlogn)

三种线性排序算法 计数排序、桶排序与基数排序

---

15. 其他一些技巧性方法

• 相同的数**异或（^）**结果为0：Single Number

• 循环获取整数的每一位：Reverse Integer

    while(x != 0) {
        int value = x % 10;
        x = x / 10;
    }
  

• double类型数据与0进行比较：

    if( fabs(double_number) < 10e-7 ) {
        ......
    }