leetcodeSolution 题号 解答 [1]两数之和 1. umap.find(target - nums[i])2. umap.count(target-nums[i]) 👍 [46]全排列 1. 递归. 分层布局。1.交换第一个数字。2.第一个数固定。后面的排列。3.交换归位。 2. 递归。回溯。填空格法。访问数组标记。 [47]全排列ii set。去重。递归。交换。 [51]n皇后 回溯。排序。基于条件对string进行排序。H [52] N皇后 II 回溯。计数。跟51题一样。 [53] 最大子序和 1. 2*O(n/2)+O(1)=O(n)。分治法。max(divide,merge)。2. O(n)。Kadane's algorithm。DP。分为子问题。 [77] 组合 1. 公式法:C(K,N)=C(K-1,N-1)+C(K,N-1)。2. 回溯法。递归+循环。M [94] 二叉树的中序遍历 1. 中序遍历。递归。E2. 中序遍历。1个栈。M。👍3. 中序遍历。O1,非递归+不用栈。线索二叉树。H。 [104] 二叉树的最大深度 dfs.递归。E [105] 从前序与中序遍历序列构造二叉树 递归。二分查找。mid.start.end. pos=distance(.begin,find( , , )) [111] 二叉树的最小深度 dfs.递归。E [138] 复制带随机指针的链表 链表/复制原始(copy,link,next)/复制随机(copy,next)/分离。M [144] 二叉树的前序遍历 1. 递归2. 迭代+栈👍 [145] 二叉树的后序遍历 1. 递归2. 迭代+1个栈👍3. 迭代+2个栈 [169] 求众数 1. 快排。找中位数。O(nlogn)2. 不修改数组的方法O(n) 👍 [172] 阶乘后的零 1. 数学。递归。2. 数学。迭代。 [215] 数组中的第K个最大元素 1. O(nlogn)。快排sort()。reverse()。会修改数组。2. O(n)。快排in-place partition/one way。会修改数组。3. O(nlogk)。priorityqueue-default-maxheap。基于堆。所有元素放入pq,弹出k-1次堆顶,返回pq.top()。不需要修改数组,适用于处理海量数据。4. O(nlogk)。multiset-default-minheap。基于rbt,设置一个大小为k的最小堆。最后弹出*set.begin()。不需要修改数组,适用于处理海量数据。 [233] 数字1的个数 数学。T:O(logn),S:O(1)1. 公式法:n/(10*d)*d + min(d,max(0,n%(10d)-d+1))2.划分法。满二进一位(满载),如果量级的最后一位是1,要加上余数+1 [295] 数据流的中位数 1. 增删O(logn),查O(1).maxheap,两个stl::pq,一个放前一半大的数,一个放后一半大的负数。2. AVL。maxheap和minheap。优先队列。 [297] 二叉树的序列化与反序列化 1. bfs/queue/stringstream2. dfs递归/stringstream in(str)/obj.str()返回值 [426]把二叉搜索树转化为有序双向链表 分治法。递归。指针引用。中序遍历。M [463] 岛屿的周长 1. 岛屿边界处:在数组最左边,或者左边格子没有岛屿2. 先假设算4个边,判断左边和上边是否有岛屿 👍 [700] 二叉搜索树的查找 1. 递归。BST。E2. 迭代。BST。E。 [701] 二叉搜索树的插入 1. 递归。BST。2. 迭代。BST。break。 [705] 设计哈希集合 hashset。二维数组。value=0或者1.代表集合中是否存在。E。 [706] 设计哈希映射 hashmap。key-value。映射。初值为-1。E。 [804] 国际摩尔斯密码 unordered_set。hash。E。 @Lightmare 3/13/19