发表于 | 分类于 ， | 浏览 次
字数统计: 1,910 | 阅读时长 ≈ 7

leetcode刷题总结

题目 题意 知识点 思路
208.Implement Trie (Prefix Tree) 实现一个Trie树模板，支持插入、搜索、前缀搜索操作 Trie
211.Add and Search Word - Data structure design 实现Trie树的插入、搜索，支持搜索”a.b”格式，”.”表示通配符 Trie+DFS
677.Map Sum Pairs 单词有权重，输入前缀词，给出所有以此为前缀的词的权重之和 Trie+DFS
200.Number of Islands 统计中有0,1，相邻1为island，统计island个数(连通子图) 并查集、DFS
305.Number of Islands II 初始矩阵为0，每次随机将某一位改变成1，统计每一时刻island个数 并查集
130.Surrounded Regions “XXOO”将被X包围的O改成X，处于边界的O不算被包围 DFS、并查集
261.Graph Valid Tree 给定点集和边集，判断此图是否为树 并查集
323.Number of Connected Components in an Undirected Graph 给定点集和边集，返回连通子图个数 并查集
79.Word Search 给一个字母矩阵和一个单词，查找字母矩阵中是否有该单词 回溯+BFS
212.Word Search II 给一个字母矩阵和一个单词数组，返回数组，里面包含出现在矩阵中的所有单词 Trie+DFS
lintcode391. 数飞机 给定一些区间，求同一时刻空中最多有多少飞机 扫描线
252.Meeting Rooms 给定一些区间，判断是否可以参加所有会议（所有会议没有冲突） 排序扫描/扫描线
253.Meeting Rooms II 给定一些区间，求最多需要多少间会议室（最多有多少会议同时开） 扫描线
42.Trapping Rain Water 一维接雨水 双指针
407.Trapping Rain Water II 二维接雨水 堆
62.Unique Paths 从网格左上角走到右下角有多少种方案 DP
63.Unique Paths II 从网格左上角走到右下角有多少种方案，有一些障碍点 DP
120.Triangle 给定一个三角形，求从顶端走到最下面的最短路径 DP
70.Climbing Stairs 爬楼梯，每次只可以爬一步或者两步，求爬到顶有多少种方案 DP
55.Jump Game 贪心法
45.Jump Game II
145.Binary Tree Postorder Traversal 二叉树的后续遍历 DFS、递归、回溯
94.Binary Tree Inorder Traversal 二叉树的中续遍历 DFS、递归、回溯
144.Binary Tree Preorder Traversal 二叉树的前续遍历 DFS、递归、回溯
226.Invert Binary Tree 二叉树对称翻转 分治法、递归
100.Same Tree 判断两个二叉树是否相同 递归
236.Lowest Common Ancestor of a Binary Tree 求二叉树中两个节点的最近公共祖先 分治法、递归
110.Balanced Binary Tree 给定一个二叉树，判断是否是平衡二叉树 递归 额外resultTypt判断是否平衡以及最大深度差
104.Maximum Depth of Binary Tree 给定二叉树，求其最大深度 分治法、递归
97.Interleaving String 给定三个字符串s1,s2,s3,返回s3是否能够由s1和s2组成，s1,s2中字母顺序不变 序列型DP
115.Distinct Subsequences 给定字符串S和T，从S中选取字母构成T共有多少种方案 序列型DP
72.Edit Distance 给定两字符串s1,s2和三种操作：插入、删除、替换，最少经过多少步操作可以使得s1和s2一样 序列型DP
647.Palindromic Substrings 给定一个字符串，返回其中回文串个数 序列型DP
132.Palindrome Partitioning II 给定一个字符串，最少切几刀可以使每一段都是回文串 序列型DP
139.Word Break 给定一个字符串和一个单词表，返回字符串是否可以切割成全部由单词表中的单词组成 序列型DP
334.Increasing Triplet Subsequence 给定一个数组，返回是否有递增的三元组 两指针
300.Longest Increasing Subsequence 给定一个序列，求其最长递增子序列的长度 坐标型DP
题目 题意 知识点 备注
50.Pow(x, n) 求x的n次方 二分法+递归 int ->long
29.Divide Two Integers 求两个数相除a/b 二分搜索。找到最大的x：x*b <= a 边界条件-2147483648/-1
287.Find the Duplicate Number

LinkedList

题目 题意 知识点 思路 难易
328.Odd Even Linked List 给定链表，将偶数位放置在链表后，奇数位偶数位数字相对位置保持不变 链表 简单
234Palindrome Linked List 判断链表是否是回文串 回文，链表 1.找到链表中位数，将后半段反转，对比前后元素是否一致
2.利用stack，将前一半存起来，继续 向后扫描与stack中元素对比		 难
160.Intersection of Two Linked Lists 找到两链表AA和B相交的位置 链表 两个指针分别遍历，一个先A后B，一个先B后A，两指针指向节点相等即为相交处 技巧题
147.Insertion Sort List 链表的插入排序 链表、插入排序 建dummy节点，原链表元素按序插入dummy节点开头的链表 技巧+中等
24.Swap Nodes in Pairs 从前向后，两两交换链表节点 链表、交换 从前向后遍历，两两交换 简单
203.Remove Linked List Elements 给定链表和val，删除链表中所有值为val的元素 链表、删除节点 遍历，删除 简单
2.Add Two Numbers 给定两个链表表示两个数字，位数由低到高，返回链表表示两个链表的和 链表 遍历相加，记录进位 简单
445.Add Two Numbers II 给定两个链表表示两个数字，位数由高到低，返回链表表示两个链表的和 链表、反转 反转->相加->反转 简单
109.Convert Sorted List to Binary Search Tree 难
369.Plus One Linked List 给定链表代表一个数字，由高位到低位，返回该数字+1链表 链表、反转 1.反转->相加->反转
2.递归
3.技巧：找从后向前第一个不为9的元素+1，后面9置0		 简单+技巧
725.Split Linked List in Parts 给定一个链表和数字k，将链表分为k段，每段长度差不大于1，长的放前面 链表 1.求链表长度len
2.m = len/k,n = len%k
3.前n个链表长度为m+1，其余长度为m		 简单
25.Reverse Nodes in k-Group 给定链表和数字k，将链表分组，每组k个元素，按组反转 链表、反转 两指针指向分组头和尾，将头和尾之间的链表反转 简单
109.Convert Sorted List to Binary Search Tree 链表转为高度平衡搜索二叉树 链表、二叉搜索树 递归，中点做为root，对左链表和右链表递归调用构建BST 中等

Array

题目 题意 知识点 思路 难易
88.Merge Sorted Array 合并两个有序数组到第一个数组 数组 从后向前遍历，比较大小依次从后向前插入nums1 简单
349.Intersection of Two Arrays 找两个数组交集，去重 排序、hashmap 1.排序
2.两指针遍历		 简单
350.Intersection of Two Arrays II 找两个数组交集 排序、hashmap 1.排序
2.两指针遍历		 简单
311.Sparse Matrix Multiplication

Two Pointers

题目 题意 知识点 思路 难易
360.Sort Transformed Array 给定有序数组，计算ax^2+bx+c，返回结果依然有序 two pointers 根据二次函数性质，a>0先减后增，比较两指针，从后向前插入，a<0反之 简单
485.Max Consecutive Ones 给定数组有0有1，返回连续1的最大长度 two pointers 两指针滑窗，记录当前最大长度，遇到0跳过重新开始 简单
487.Max Consecutive Ones II 给定数组有0有1，最多可以把一个0变成1，返回连续1的最大长度 two pointers 两指针滑窗，记录窗口内0的个数，超过1缩小窗口大小，记录滑窗最大长度 简单