LeetCode总结【转】

转自：http://blog.csdn.net/lanxu_yy/article/details/17848219

版权声明：本文为博主原创文章，未经博主允许不得转载。

最近完成了www.leetcode.com的online judge中151道算法题目。除各个题目有特殊巧妙的解法以外，大部分题目都是经典的算法或者数据结构，因此做了如下小结，具体的解题思路可以搜索我的博客：LeetCode题解

题目 算法 数据结构 注意事项
Clone Graph BFS 哈希表
Word Ladder II BFS 哈希表
Surrounded Regions BFS 矩阵
Word Ladder BFS N/A
Binary Tree Level Order Traversal BFS|前序遍历 队列
Binary Tree Level Order Traversal II BFS|前序遍历 队列
Binary Tree Zigzag Level Order Traversal  BFS|前序遍历 队列 每一层顺序分别对待
Implement strStr() KMP算法 N/A
Copy List with Random Pointer N/A 哈希表
Remove Duplicates from Sorted Array N/A 哈希表
Remove Duplicates from Sorted Array II N/A 哈希表
Set Matrix Zeroes N/A 哈希表
Anagrams N/A 哈希表
First Missing Positive N/A 哈希表
Two Sum N/A 哈希表
Evaluate Reverse Polish Notation N/A 堆栈
Largest Rectangle in Histogram N/A 堆栈 记录重要位置
Minimum Window Substring N/A 堆栈
Simplify Path N/A 堆栈
Longest Valid Parentheses N/A 堆栈
Valid Parentheses N/A 堆栈 词法分析
Container With Most Water N/A 堆栈 记录重要位置
Reverse Words in a String N/A 堆栈 翻转字符串
Best Time to Buy and Sell Stock N/A 数组
Best Time to Buy and Sell Stock II N/A 数组
Best Time to Buy and Sell Stock III N/A 数组
Length of Last Word N/A 数组
Search Insert Position N/A 数组
Search for a Range N/A 数组
Spiral Matrix N/A 矩阵 简化为子问题
Spiral Matrix II N/A 矩阵 简化为子问题
LRU Cache N/A 链表
Reorder List N/A 链表 快慢指针&链表倒序
Linked List Cycle N/A 链表 快慢指针
Linked List Cycle II N/A 链表 快慢指针
Reverse Linked List II N/A 链表
Partition List N/A 链表
Remove Duplicates from Sorted List N/A 链表
Remove Duplicates from Sorted List II N/A 链表
Merge Two Sorted Lists N/A 链表
Rotate List N/A 链表 快慢指针
Reverse Nodes in k-Group N/A 链表
Swap Nodes in Pairs N/A 链表
Remove Nth Node From End of List N/A 链表 快慢指针
Text Justification N/A 队列
Candy N/A N/A 简化为子问题
Valid Palindrome N/A N/A 首尾指针
Plus One N/A N/A 模拟加法运算
Valid Number N/A N/A 词法分析
Add Binary N/A N/A 模拟加法运算
Insert Interval N/A N/A
Merge Intervals N/A N/A
Multiply Strings N/A N/A 模拟乘法运算
Trapping Rain Water N/A N/A
Valid Sudoku N/A N/A
Roman to Integer N/A N/A
Integer to Roman N/A N/A
Palindrome Number N/A N/A
Reverse Integer N/A N/A
ZigZag Conversion N/A N/A
Add Two Numbers N/A N/A 模拟加法运算
Median of Two Sorted Arrays N/A N/A
String to Integer (atoi) STL函数 N/A
Next Permutation STL经典算法 N/A
Recover Binary Search Tree 中序遍历 二叉树
3Sum 二分查找 N/A
3Sum Closest 二分查找 N/A
4Sum 二分查找 N/A
Single Number 位运算 N/A
Single Number II 位运算 N/A
Construct Binary Tree from Preorder and Inorder Traversal 前序中序遍历 N/A
Binary Tree Preorder Traversal 前序遍历 二叉树
Flatten Binary Tree to Linked List 前序遍历 二叉树
Interleaving String 动态规划 二叉树
Unique Binary Search Trees 动态规划 二叉树
Word Break 动态规划 N/A
Word Break II 动态规划 N/A
Palindrome Partitioning 动态规划 N/A
Palindrome Partitioning II 动态规划 N/A
Triangle 动态规划 N/A
Distinct Subsequences 动态规划 N/A
Decode Ways 动态规划 N/A
Scramble String 动态规划 N/A
Maximal Rectangle 动态规划 N/A
Edit Distance 动态规划 N/A
Climbing Stairs 动态规划 N/A
Minimum Path Sum 动态规划 N/A
Unique Paths 动态规划 N/A
Unique Paths II 动态规划 N/A
Jump Game 动态规划 N/A
Jump Game II 动态规划 N/A
Maximum Subarray 动态规划 N/A
Wildcard Matching 动态规划 N/A
Substring with Concatenation of All Words 动态规划 N/A
Sort List 合并排序 链表 快慢指针
Merge Sorted Array 合并排序 N/A
Construct Binary Tree from Inorder and Postorder Traversal 后序中序遍历 N/A
Binary Tree Postorder Traversal 后续遍历 二叉树
Combinations 回溯 N/A
Permutation Sequence 回溯 N/A
N-Queens 回溯 N/A
N-Queens II 回溯 N/A
Permutations 回溯 N/A
Permutations II 回溯 N/A
Combination Sum 回溯 N/A
Combination Sum II 回溯 N/A
Sudoku Solver 回溯 N/A
Longest Substring Without Repeating Characters 回溯 N/A
Max Points on a Line 循环遍历 N/A 排除相同的点
Longest Common Prefix 循环遍历 N/A
Longest Palindromic Substring 循环遍历 N/A
Insertion Sort List 插入排序 链表
Rotate Image 矢量旋转与平移 N/A
Longest Consecutive Sequence 类BFS 哈希表
Search in Rotated Sorted Array 类二分查找 N/A
Search in Rotated Sorted Array II 类二分查找 N/A 特殊考虑相等数据
Sqrt(x) 类二分查找 N/A
Pow(x, n) 类二进制 N/A
Divide Two Integers 类二进制 N/A
Gas Station 类合并排序 N/A
Merge k Sorted Lists 类外排序 N/A
Sort Colors 类快速排序 N/A
Remove Element 类快速排序 N/A
Search a 2D Matrix 类杨氏矩阵 N/A
Restore IP Addresses 背包问题 N/A
Sum Root to Leaf Numbers 递归 二叉树
Binary Tree Maximum Path Sum 递归 二叉树
opulating Next Right Pointers in Each Node 递归 二叉树
Populating Next Right Pointers in Each Node II 递归 二叉树
Path Sum 递归 二叉树
Path Sum II 递归 二叉树
Maximum Depth of Binary Tree  递归 二叉树
Minimum Depth of Binary Tree 递归 二叉树
Balanced Binary Tree 递归 二叉树
Symmetric Tree 递归 二叉树
Same Tree  递归 二叉树
Validate Binary Search Tree 递归 二叉树
Unique Binary Search Trees II 递归 二叉树
Binary Tree Inorder Traversal 递归 二叉树
Pascal's Triangle 递归 N/A
Pascal's Triangle II 递归 N/A
Convert Sorted List to Binary Search Tree 递归 N/A 快慢指针&反中序遍历
Convert Sorted Array to Binary Search Tree 递归 N/A 反中序遍历
Subsets 递归 N/A
Subsets II 递归 N/A
Gray Code 递归 N/A
Word Search 递归 N/A
Count and Say 递归 N/A
Generate Parentheses 递归 N/A
Letter Combinations of a Phone Number 递归 N/A
Regular Expression Matching 递归 N/A
时间： 2024-11-16 06:02:10

LeetCode总结【转】的相关文章

代码分析-leetcode:Scramble String问题

问题描述 leetcode:Scramble String问题 题目:Given a string s1 we may represent it as a binary tree by partitioning it to two non-empty substrings recursively. Below is one possible representation of s1 = ""great"": great / gr eat / / g r e at /

c++-leetcode Median of Two Sorted Arrays

问题描述 leetcode Median of Two Sorted Arrays class Solution { public: double findMedianSortedArrays(vector& nums1, vector& nums2) { if(nums1.size()==0){ if(nums2.size()%2==0)return ((double)nums2[nums2.size()/2]+nums2[nums2.size()/2-1])/2.0; else ret

[LeetCode]61.Rotate List

[题目] Given a list, rotate the list to the right by k places, where k is non-negative. For example: Given 1->2->3->4->5->NULL and k = 2, return 4->5->1->2->3->NULL. [题意] 给定一个链表,向右旋转k个位置,其中k是非负的. [分析] 先遍历一遍,得出链表长度 len,注意 k 可能大于

[LeetCode]91.Decode Ways

题目 A message containing letters from A-Z is being encoded to numbers using the following mapping: 'A' -> 1 'B' -> 2 - 'Z' -> 26 Given an encoded message containing digits, determine the total number of ways to decode it. For example, Given encode

LeetCode总结之二分查找篇

二分查找算法虽然简单,但面试中也比较常见,经常用来在有序的数列查找某个特定的位置.在LeetCode用到此算法的主要题目有: Search Insert Position Search for a Range Sqrt(x) Search a 2D Matrix Search in Rotated Sorted Array Search in Rotated Sorted Array II 这类题目基本可以分为如下四种题型: 1. Search Insert Position和Search fo

Restore IP Addresses：LeetCode

原题链接: http://oj.leetcode.com/problems/restore-ip-addresses/ 这道题的解法非常接近于NP问题,也是采用递归的解法.基本思路就是取出一个合法的数字,作为IP地址的一项,然后递归处理剩下的项.可以想象出一颗树,每个结点有三个可能的分支(因为范围是0-255,所以可以由一位两位或者三位组成).并且这里树的层数不会超过四层,因为IP地址由四段组成,到了之后我们就没必要再递归下去,可以结束了.这里除了上述的结束条件外,另一个就是字符串读完了.可以看

Simplify Path：LeetCode

原题链接: http://oj.leetcode.com/problems/simplify-path/ 这道题目是Linux内核中比较常见的一个操作,就是对一个输入的文件路径进行简化.思路比较明确,就是维护一个栈,对于每一个块(以'/'作为分界)进行分析,如果遇到'../'则表示要上一层,那么就是进行出栈操作,如果遇到'./'则是停留当前,直接跳过,其他文件路径则直接进栈即可.最后根据栈中的内容转换成路径即可(这里是把栈转成数组,然后依次添加).时间上不会超过两次扫描(一次是进栈得到简化路径,

4Sum：LeetCode

这道题要求跟3Sum差不多,只是需求扩展到四个的数字的和了.我们还是可以按照3Sum中的解法,只是在外面套一层循环,相当于求n次3Sum.我们知道3Sum的时间复杂度是O(n^2),所以如果这样解的总时间复杂度是O(n^3).代码如下: public ArrayList<ArrayList<Integer>> fourSum(int[] num, int target) { ArrayList<ArrayList<Integer>> res = new Ar

Distinct Subsequences -- LeetCode

原题链接: http://oj.leetcode.com/problems/distinct-subsequences/ 这道题应该很容易感觉到是动态规划的题目.还是老套路,先考虑我们要维护什么量.这里我们维护res[i][j],对应的值是S的前i个字符和T的前j个字符有多少个可行的序列(注意这道题是序列,不是子串,也就是只要字符按照顺序出现即可,不需要连续出现).下面来看看递推式,假设我们现在拥有之前的历史信息,我们怎么在常量操作时间内得到res[i][j].假设S的第i个字符和T的第j个字符

Word Search -- LeetCode

原题链接: http://oj.leetcode.com/problems/word-search/ 这道题很容易感觉出来是图的题目,其实本质上还是做深度优先搜索.基本思路就是从某一个元素出发,往上下左右深度搜索是否有相等于word的字符串.这里注意每次从一个元素出发时要重置访问标记(也就是说虽然单次搜索字符不能重复使用,但是每次从一个新的元素出发,字符还是重新可以用的).深度优先搜索的算法就不再重复解释了,不了解的朋友可以看看wiki - 深度优先搜索.我们知道一次搜索的复杂度是O(E+V),