主要总结自己做过的题的知识点。
解释：
★：需要再次看
❤：做了很久
▲：没做出来
相关文章：
- Java-String
- 算法-Trie树
- 算法-并查集
- 算法-堆
- 算法-DP
- Post not found: Java-Map Java-Map
- 算法-DFS
- 算法-二分查找
- 算法-二叉树与分治
- 算法-链表
| 题 | 题意 | 知识点 |
|---|---|---|
| Implement Trie (Prefix Tree) | 实现 Trie的insert、search、prefix（判断是否是前缀） | Trie |
| Add and Search Word - Data structure design | 实现str的add与search，其中str'.'代表任意字符 | Trie |
| Top K Frequent Words | 给一组str[]，统计频率最高的k个str | Trie+HashHeap |
| Map Sum Pairs | 实现insert(str,val)和sum(str)，使得sum(str)能输出以str为前缀的所有单词的价值和 | Trie |
| Word Search | 给char[][] board和str word。判断word是否被包含在board中 |
DFS |
| Word Search II | 给char[][] board和str[] words。从words中找到被包含在board中的单词 |
Trie+DFS |
| Replace Words | 给一个词根表str[] dict = ["cat", "bat", "rat"] ，和sentence = "the cattle was rattled by the battery"。替换句子为"the cat was rat by the bat"| Trie+String的操作 | | Number of Islands | 给一个二维数组，元素为1/0。判断岛屿的个数 | 并查集/dfs | | Number of Islands II | 上题二维数据改成动态的 | 并查集 | | Graph Valid Tree | 给一个无向连通图，判断是不是一棵树 | 并查集 | | Number of Connected Components in an Undirected Graph | 给一个无向连通图，判断有几个联通块 | 并查集 | | Friend Circles | 有n个人，矩阵M表示n个人互相的关系。求这n个人一共有多少个朋友圈 | 并查集 | | Surrounded Regions | 给一个矩阵，里面元素是X或O。如果一个O的连通块被X完全围住，就将O全部改成X。输出改之后的矩阵 | 并查集/dfs | | Redundant Connection | 给一个无向连通图。要从中取出一条边，使得它成为一棵树。 如果有多个解，输出input中最后一个出现的边 | 并查集 | | Longest Consecutive Sequence | 给一个数组int[] nums = {100,4,200,1,3,2}，输出连续数字的最大个数——4 | 并查集/先sort后遍历 | | Top K Frequent Elements | 给一个int[],输出频率最高的k个数字 | 堆 | | ★Kth Smallest Element in a Sorted Matrix | 给一个 *n* x *n*的数组，行列都有序（即A[i][j]<A[i+1][j]且A[i][j]<A[i][j+1]）。找到第K小的元素 | 堆/二分 | | Find K Pairs with Smallest Sums | 给定两个数组nums1和nums2，找到nums1[i] + nums2[i] 的从最小到第k小的对(i,j) | 堆 | | ★Merge k Sorted Lists | 给了k个链表ListNode[k] lists。每个链表都已排序。将这k个链表merge为一个有序链表 | 堆（注意将listNode视为整体的技巧）/ 链表分治 | | Design Twitter | 设计一个twitter类，实现发微博、关注、取关，拉取关注好友列表的最近10条信息流 | 堆（与上一题一个技巧） | | ❤Split Array into Consecutive Subsequences | 给一个数组[1,2,3,3,4,5]，问它能不能分成多个长度大于3的连续子数组[1,2,3]和[3,4,5] | HashMap+堆 | | ▲The Skyline Problem | 题意：给一些大楼int[][] build，每个楼是三元组[left,right,h]。求这些大楼的关键点 | 堆 | | Trapping Rain Water | Given[0,1,0,2,1,0,1,3,2,1,2,1],输出它能乘的最大雨水数量6| 双指针 | | Trapping Rain Water II | 给一个二维数组，假设这是一个台子。边界没有挡板。求问这个台子最多能乘多少雨水 | 堆 | | ★Sort Characters By Frequency | 给一个字符串”tree”，按照字母频率输出“eetr”或”eert” | HashMap的排序/**桶排序**/堆 | | ★Maximum Subarray | 输出数组的连续子数组的最大和 | DP | | Triangle | 给一个三角形，找到从上到下最短路径和 | 坐标DP | | Climbing Stairs | 有一个楼梯，一步只能跨1/2步。问从0走到n层有多少层方案 | 坐标DP | | Unique Paths | m×n格子，从左上走到右下，有多少种走法（只能向下或向右走） | 坐标DP | | Unique Paths II | 格子里可能有障碍物，还有多少种走法 | 坐标DP | | Minimum Path Sum | 找到路径权重最小的路 | 坐标DP | | Jump Game | 给一个数组A,A[i]表示在这里时最多可以跳A[i]步。只能向前跳。从数组A的第0位置出发，能不能跳到末尾 | 坐标DP/贪心 | | Jump Game II | 给一个数组A,A[i]表示在这里时最多可以跳A[i]步。只能向前跳。从数组A的第0位置出发，问最少的跳的次数。 | 坐标DP/贪心 | | Longest Increasing Subsequence | 求最长严格递增的子序列（子序列：可以跳着选） | 坐标DP/二分 | | Arithmetic Slices | 给一个序列。求这个序列有多少个等差数列（至少三个元素才算等差数列） | 坐标DP | | Perfect Squares | 给一个数字，求它被拆成平方和的最少平方和个数 | 坐标DP | | ★Maximal Square | 给一个0/1矩阵。找到最大全1方阵，返回方阵元素个数 | 单序列DP | | ★Best Time to Buy and Sell Stock | 给一个int[] prices表示股票价格。求出最好的买卖方式的钱 | DP | | ★Word Break | 给一个str s和一个str[] dict，判断s是否能被dict中的单词组成 | 单序列DP | | Palindrome Partitioning II | 一个str最少被切割几次可以切割为都是回文串 | 单序列DP | | House Robber | 给一个数组int[] nums，表示每个商店的价值。要抢劫，但抢劫时必须至少隔一个商铺抢。问能抢到的最大价值 | 单序列DP | | House Robber II | 给一个数组int[] nums，表示每个商店的价值。商店是成环的，即首尾相接。要抢劫，但抢劫时必须至少隔一个商铺抢。问能抢到的最大价值。 | 单序列DP | | Paint House | 给一个二维数组cost[][]，大小为n×3。其中cost[i][q]表示第i个房子涂上第q种颜色时的造价。一共有3种颜色。要求两个相邻房子不可以同色。求涂色最小造价 | 单序列DP | | Longest Common Subsequence | 最长公共子序列 | 双序列DP | | Edit Distance | 将第一个字符串最少改动，变成第二个字符串 | 双序列DP | | Distinct Subsequences | 从S=”rabbbit”挑出T = “rabbit”有几种挑法 | 双序列DP | | Interleaving String | 给了三个字符串s1,s2,s3.判断s3是否是由s1和s2交替组成（按顺序，且可交替着挑） | 双序列DP | | Dungeon Game | 英雄救美：给一个矩阵int[][] dungegon`，每个格子正数代表能量加成，负数代表减弱能量。英雄要从左上走到右下，要求每一时刻英雄的能量不低于1.问英雄初始时最少需要多少能量 |
双序列DP |
| ▲Paint Fence | https://segmentfault.com/a/1190000003790650 | |
| ▲Ugly Number | 给一个数num，判断它是不是ugly数——它的质因数只能说是2、3、5 | DP |
| ★Range Sum Query - Immutable | 给一个数组，输出指定i，j之间的和 | DP |
| ▲Word Break II | 给一个str s和一个str[] dict,输出所有s可能被dict拼接的组合 | DFS |
| Binary Tree Preorder Traversal | 实现二叉树的前序遍历 | 递归/栈 |
| Binary Tree Inorder Traversal | 实现二叉树的中序遍历 | 递归/栈 |
| Validate Binary Search Tree | 验证一个二叉树是不是搜索二叉树 | 中序遍历 |
| Find Mode in Binary Search Tree | 给一个有重的BST。其中左子树小于等于本身，右子树大于本身。统计最多次数出现的数字 | BST + 中序遍历 |
| Binary search Tree Iterator | 按照中序遍历方式将二叉树元素一个一个输出（要一个给一个） | 栈的中序遍历 |
| Convert Sorted List to Binary Search Tree | 将有序链表转化为平衡BST | 中序+递归+BST |
| Convert Sorted Array to Binary Search Tree | 将有序数组转化为平衡BST | 中序+二分+BST |
| Kth Smallest Element in a BST | BST中第K小的数 | 中序+BST |
| Delete Node in a BST | 删除BST中某个节点 | BST |
| Binary Tree Postorder Traversal | 实现二叉树的后序遍历 | 递归/栈/双栈 |
| Maximum Depth of Binary Tree | 求二叉树的最大深度 | 递归+分治 |
| Binary Tree Maximum Path Sum | 给一个二叉树，找到从any node 到 any node最大路径和。路径可以在任何地方被结束掉 | 递归+分治 |
| Balanced Binary Tree | 判断一个树是不是平衡二叉树 | 递归+分治 |
| Lowest Common Ancestor | 求一颗二叉树中两个点a,b的最近公共祖先 | 递归+分治 |
| Binary Tree Level Order Traversal | 输出二叉树的层序遍历 | 队列 |
| Binary Tree Level Order Traversal II | 输出二叉树的层序遍历，要从下往上输出 | 队列+LinkedList |
| Binary Search | 给一个int[] nums,找到target第一次出现的index。没找到就返回-1. | 二分 |
| Search for a range | 给一个int[] nums = {5,7,7,8,8,10],找到target=8出现的范围[3,4]。没找到就返回[-1,-1]. | 二分 |
| Search Insert Position | 给一个有序无重数组nums = [1,3,5,6],把target=5插入，问插入的位置=2 | 二分 |
| Search a 2D Matrix | 给一个严格递增的矩阵，寻找是否存在target | 二分 |
| Search a 2D Matrix II | 给一个非严格递增的矩阵，寻找是否存在target | 巧妙的遍历 |
| First Bad Version | 代码库的版本号是从 1 到 n 的整数。某一天，有人提交了错误版本的代码，因此造成自身及之后版本的代码在单元测试中均出错。请找出第一个错误的版本号 | 二分 |
| Find Peak Element | 给一个数组。找峰值。相邻两个数都不一样。如果有多个峰值，就随便输出一个 | 二分 |
| Find Minimum in rotated sorted array | 找有序旋转数组（首位相接）中的最小值。数组中不存在重复元素 | 二分 |
| Find Minimum in rotated sorted array II | 找有序旋转数组（首位相接）中的最小值。数组中可能存在重复元素 | 遍历/二分 |
| Search in Rotated Sorted Array | 从有序旋转数组（首位相接）中找target。数组中不存在重复元素 | 二分 |
| Search in Rotated Sorted Array II | 从有序旋转数组（首位相接）中找target。数组中可能存在重复元素。 | 遍历/二分 |
| Median of two Sorted Arrays | 找到两个有序数组的中位数 | 二分 |
| Remove Duplicates from Sorted List | 将有序链表去重 | 链表 |
| Remove Duplicates from Sorted List II | 将有序链表中的全部重复元素删除 | 链表+dummy |
| Remove Linked List Elements | 删除链表中的某个节点 | 链表+dummy |
| Reverse Linked List | 将链表反转 | 链表 |
| Reverse Linked List II | 将一个链表的m到n反转 | 链表+dummy |
| Reverse Nodes in k-Group | 将链表按照k大小的组，反转。如果最后不够k个，则保持原样 | 链表+dummy |
| Partition List | 要求把小于x的元素放到链表前面 | 链表+dummy |
| Sort List | 用O(nlogn)的时间和空间复杂度排序链表 | 链表+取中点+快排/归并 |
| Reorder List | 将链表 L0→L1→…→Ln-1→Ln, 重排序为L0→L*n→L1→L*n-1→L2→L*n*-2→… | 链表+取中点+反转 |
| Linked List Cycle | 判断链表里有没有环形 | 链表+fast-slow |
| Linked List Cycle II | 如果有环，找到环的入口 | 链表+fast-slow |
| Rotate List | 将链表循环移动k个 | 链表+fast-slow |
| Merge k Sorted Lists | 将k个有序链表合并 | 堆+链表 |
| Delete Node in a Linked List | 从链表中删除某个Node | 神奇的后移 |
| Palindrome Linked List | 判断一个list是不是回文串 | 链表反转 |
| Odd Even Linked List | 将链表的奇数位放前面，偶数位放后面 | 链表 |
| Split Linked List in Parts | 将一个链表分为k个部分，每个部分的长度差不得超过1，且前面的长度不得小于后面的长度 | 链表 |
| Insertion Sort List | 实现链表的插入排序 | 链表 |
| Copy List with Random Pointer | 深拷贝一个带有random指针的链表 | 链表+三步走 |