LeetCode整理【上】
资源
近期需要做的工作
- 整理C++的map
继续刷题,整理做过的题:
要求:
- 看到题没有思路的,要自己再写一遍
- 自己写的方法笨拙的,要跟别人对比
- 保证每一道题都是正确的,通过的
- 将本文列出的内容和工程匹配
牢记
复盘比实战更重要
已经做过的题目
按照大类进行划分,依次是【1】题目的leetcode地址【2】我的github上的解法【3】别人的解法或者总结
没有解决的问题
- http://oj.leetcode.com/problems/median-of-two-sorted-arrays/
【老树盘根】
- 将排序数组转换成BST······Convert Sorted Array to Binary Search Tree
- 计算有n个节点的搜索树能有多少种不同的形式······Unique Binary Search Trees
- 构建全部二叉搜索树······Unique Binary Search Trees II
- 树的最大深度······Maximum Depth of Binary Tree
- 树的最小深度······Minimum Depth of Binary Tree
- 树的先序遍历······Binary Tree Preorder Traversal·非递归讲解
- 树的中序遍历······Binary Tree Inorder Traversal
- 树的后续遍历······Binary Tree Postorder Traversal
- 树按层次遍历······Binary Tree Level Order Traversal,留待填写
- 树逆层次遍历······Binary Tree Level Order Traversal II 留待填写······仙人指路
- Zigzag遍历······Binary Tree Zigzag Level Order Traversal
- 判断两棵树是否是一样的树······Same Tree
- 验证一颗树是否是BST······Validate Binary Search Tree
- 二叉树变链表······Flatten Binary Tree to Linked List
- 树的修复······Recover Binary Search Tree
- 判断是否对称······Symmetric Tree
- 判断是同样的树······Same Tree
- 最大路径和······Binary Tree Maximum Path Sum
- 判断树是否是平衡的······Balanced Binary Tree
- 排序数组生成BST······Convert Sorted Array to Binary Search Tree
- 排序链表生成BST······Convert Sorted List to Binary Search Tree······仙人指路
- 中序结果+前序结果生成BST······Construct Binary Tree from Preorder and Inorder Traversal
- 中序结果+后序结果生成BST······Construct Binary Tree from Inorder and Postorder Traversal
【排列组合]:
排列组合是一大类问题,经典的思想是使用回溯法,看着三篇文章就够了
题目
- 排列······Permutations
- 重复数的排列······Permutations II
- 查找下一个排列(字典法)······Next Permutation
- 找n全排列的第x个数······Permutation Sequence
- 列举一个集合的全部子集······Subsets
- 包含重复元素的集合的全部子集······Subsets II
- 找所有加起来是某一个值的所有组合(同一个元素可使用多次)······Combination Sum
- 找所有加起来是某一个值的所有组合(同一个元素只能使用一次)······Combination Sum II
链表:
链表是最常用的数据结构之一,也是面试中最愿意考察的,注意的是二级指针的使用可以有效的节省代码,不用担心头结点是否存在这一类问题,具体请参见CoolShell上翻译的Linus:利用二级指针删除单向链表 (我认为记录的是头结点的指针的地址,这相当于隐式的在前面加了一个dummy node)
【注】@号表示使用了二级指针
- @链表合并Merge Two Sorted Lists
- 深度拷贝一颗特别链表······Copy List with Random Pointer······仙人指路·哈希实现
- 检查链表是否有环······Linked List Cycle
- 找出有环链表的入口节点······linked list cycle ii
- 合并k个排序好的链表······Merge k Sorted Lists
- @两个链表表示的逆序整数相加返回一个新的链表······Add Two Numbers
- 交换链表的相邻俩数······Swap Nodes in Pairs
- 链表划分······Partition List
- 删除排序数组的重复元素······Remove Duplicates from Sorted List
- @删除重复元素,保留distinct元素······Remove Duplicates from Sorted List II······仙人指路·重要
- 删除倒数第x个数······Remove Nth Node From End of List
- @链表部分反转······Reverse Linked List II
kSum系列
这篇讨论求和问题总结总结的全面
其它:
- 整数反转·······Reverse Integer
- 查找只出现一次的数字······Single Number
- 查找single Number出现3次······Single Number II
- 装水问题······Container With Most Water······仙人指路······仙人指路2
- 删除某一元素······Remove Element
- 计算一个三角形的最短路径······Triangle
DFS
- 树的根节点与叶子节点路径相加和······Path Sum
- 树的根节点与叶子节点路径相加和······Path Sum
- 树的根节点与叶子节点路径相加和······Path Sum II
查找
- 查找区间······Search for a Range
- 查找旋转数组······Search in Rotated Sorted Array
- 查找旋转数组II 基本上是CtCI的11.3······Search in Rotated Sorted Array II
- 整数开方······Sqrt(x)
- 二分查找······Search Insert Position
动态规划
- 矩阵头到尾路径数量······Unique Paths
- 矩阵头到尾路径数量(带路障)······Unique Paths II
- 正则表达式匹配······Regular Expression Matching仙人指路
- 新浪iOS面试题查找最大子数组······ maximum-subarray
- 在方格内找左上到右下的最短路径长度
- 在Histomgram中找最大矩形······Largest Rectangle in Histogram······仙人指路1仙人指路2
- 最大矩形······Maximal Rectangle仙人指路
- [最大矩形2]附加题:矩阵中充满了正负数,找到这样一个子矩阵,这个矩阵元素和最大!
字符串操作
- 经典的ascii to integer······String to Integer (atoi)
- 最长非重复子串······Longest Substring Without Repeating Characters
- ZigZag转换······ZigZag Converision
- 最长公共前缀······Longest Common Prefix
- 单词链接······Substring with Concatenation of All Words······仙人指路
- 判断括号是否匹配······Valid Parentheses
- 找到最长的匹配的括号······Longest Valid Parentheses
- 子串窗口查找······Minimum Window Substring······仙人指路
- 大数乘法······Multiply Strings
- 【威哥探讨】拆分单词拼合成一句······Word Break
- 拆分单词拼合成一句2······Word Break II······仙人指路
- 单词搜索······Word Search