leetcode题目总结

LeetCode题目汇总
Top 10 algorithms in Interview Questions

数组
1. Move Zeroes 将数组中的0移到末尾？方法1：利用冒泡排序思想，将0冒到数组末尾方法2：记录0个数，将非0的元素往前移，最后补0
2. []()
  链表
3. Add Two Numbers
```
Input: (2 -> 4 -> 3) + (5 -> 6 -> 4)
Output: 7 -> 0 -> 8
```
1. Delete Node in a Linked List 删除链表中的某个节点：一般思路为找到该节点的前驱，并删除该节点；优化方法为该节点替代后继节点，并删除后继节点
2. Insertion Sort List 链表插入排序
3. Intersection of Two Linked Lists 两个链表的交集，先求长度，同时移动
4. Linked List Cycle 判断链表是否有环：两个指针移动，一个指针(慢指针)一次移动一步，另一个指针(快指针)一次移动两步，如果两个指针相遇，说明有环，否则没有环
5. Linked List Cycle II 链表找环：先判断是否有环，如果有环，则慢指针和快指针在换上相遇，假设链头到环起点的长度为a，环的长度为b，慢指针移动了x步，则快指针移动了2x=x+tb步，有x=tb，S(a+x)=S(a+tb)=S(a)，即此时慢指针和表头同时移动，这他们在环起点相遇，且移动的步数为a
6. Merge Two Sorted Lists 合并两个有序的链表(类比二路归并)
7. Palindrome Linked List 链表回文（正反一样）判断：找到中点，将链表后半部分反转，然后进行回文判断
8. Remove Duplicates from Sorted List 去除链表中值连续出现的重复节点：比较相邻两个节点，如果只重复，则去除其中一个个
9. Remove Duplicates from Sorted List II 去除链表中只连续出现的节点
10. Remove Nth Node From End of List 删除链表倒数第n个节点（链表长度小于n）
11. Reverse Linked List 反转链表
12. Reverse Linked List II 反转链表(m,n)：加个统计
13. Rotate List 旋转链表：将链表后k个进行旋转（k大于链表长度）
14. Sort List 链表排序（O(nlogn)）：归并排序（链表中点、链表合并）
15. Swap Nodes in Pairs 一对一对的交换链表的节点：1.交换两个节点的值 2.交换两个节点(两个临时指针)
  哈希表

需要借助map/unordered_map、数组实现的算法

Two Sum 求数组中和为某个值得两个元素的下标? a+b=c => b=c-a(求b是否存在) 使用map保存<元素,下标>关系
Group Anagrams
Bulls and Cows
3Sum 求数组中和为0的所有三元组? 对数组排序，利用a+b+c=0 => -c = a + b转换为求有序数组中和为-c的两个元素（夹逼定理或者哈希表）注：重复的三元组，消除方法: 当nums[i-1] == nums[i]时, 忽略i
3Sum Closest 求数组中和最接近某个值得三元组的和？数组排序+(a+b+c=d => a + b = d - c)夹逼定理，本题并没有用到哈希表
4Sum 求数组中和为某个值得四元组？是3Sum的扩展，多套一层循环（判重）即可
[]()
排序
Median of Two Sorted Arrays 找到两个有序数组的中位数（元素总数为偶数时，求均值）？归并思想
动态规划
Best Time to Buy and Sell Stock lowest表示prices[0...i]的最小值,max_profit=min(max_profit, prices[i] - lowest)
Climbing Stairs Fibonacci数列,f[0]=0, f[1] = 1, f[2] = 2, f[n] = f[n-1] + f[n-2], n >= 3

     // f[i]表示s[0...i-1]的编码方式数目
     // f[n] = {s[i] != '0'}f[n - 1] + {10 <= s[i-2][i-1] <= 26}f[n - 2]
     // f[0] = 1
     // f[1] = (s[0] == '0' ? 0 : 1)

House Robber

     // f[i]表示抢劫a[0...i]获得的钱
     // f[0] = a[0]
     // f[1] = max(a[0], a[1])
     // f[n] = max(f[n - 1], f[n - 2] + a[n])

House Robber II 把圈破开，分为2个数组，一个一定不包含a[0]，一个一定不包含a[n-1]

Unique Binary Search Trees 求1...n构成的二叉搜索树的个数

f[0] = 1
f[1] = 1
f[2] = 2
f[i] = sum(f[j] * f[i - j - 1]), 3 <= i <= n, 0 <= j < i

Edit Distance 求两个字符串的编辑距离？已知str1[1...m], str2[1...n]，求dist[m][n], 其中
```
dist[i][0] = i, dist[0][j], 0 <= i <= m, 0 <= j <= n
dist[i][j] = min(dist[i - 1][j - 1] + (str1[i] != str2[j]), dist[i][j - 1], dist[i - 1][j])
```
查找
- 二分查找(Binary Search)需要注意的问题，以及在数据库内核中的实现
Find Minimum in Rotated Sorted Array 在旋转数组中查找最小值，使用二分查找a[left...right]，分三种情况： a)有序数组, a[left] < a[right], ret = a[left] b)旋转数组, a[left] >= a[right], mid = (left + right) / 2 i)if right - left == 2: ret = a[right] ii)if a[left] == a[mid] == a[right]: 暴力 iii)if a[left] <= a[mid]: left = mid iii)if a[mid] <= a[right]: right = mid;

Find Peak Element 查找数组(INT_MIN, a[1], a[2], ... , a[n], INT_MIN)的峰值

int i = 1;
while (i < n && a[i - 1] <= a[i]) i++;
// 结果为i - 1

二分查找

int left = 0;
int right = nums.size() - 1;
while (left < right) {
int mid = left + (right - left) / 2;
if (nums[mid] < nums[mid + 1]) {
   left = mid + 1;
} else {
   right = mid;
}
}

return left;

First Bad Version 一个版本序列中，坏的版本会影响之后的版本，找到第一个坏的版本，二分查找
Pow(x, n) 求x**n?快速幂，注意: x == 0 && n < 0和n < 0
Search for a Range 有序数组中查找值等x的区间 a)二分查找，找到最左边的数，找到最右边的数 b)STL的lower_bound和upper_bound
Search in Rotated Sorted Array 旋转数组（无重复）中查找某个值，分类二分查找，a[left] <= a[mid], a[md] <= a[right]
Search in Rotated Sorted Array II 旋转数组（有重复）中查找某个值，分类二分查找，a[left] == a[mid], a[left] <= a[mid], a[md] <= a[right]
Search Insert Position 有序数组查找第一个大于等于x的位置，二分查找，注意分情况处理： a)a[mid] == target && a[mid - 1] == a[mid]: right = mid - 1 b)target < a[mid]: right = mid c)a[mid] < target: left = mid + 1

数学

Count Primes 判断素数，根据定义(IsPrime，O(n**1.5))或打表(O(n)，额外的内存开销)
Add Binary 二进制加法（进位carry），从低位到高位
Add Digits 公式：1+(n-1)%9
Add Two Numbers 链表实现加法（从链表头部到尾部，地位到高位）
Basic Calculator 栈，先做括号里的，再做括号外的，忽略空格
Basic Calculator II 栈，先做乘除，再做加减
Divide Two Integers 参考a**n的求法 a/b => a = b + b + ... + b => a = 2**n * b + 2**(n-1) * b + ... + b
Excel Sheet Column Number 进制转换：26进制转10进制
Excel Sheet Column Title 进制转换：10进制转26进制
Factorial Trailing Zeroes n!尾部0的个数，n!/10，10=25，由于2的个数>5的个数，只需要考虑5的个数，`for (long i = 5; i <= n; i = 5) ret += n / i;`
Fraction to Recurring Decimal 分数（分子/分母）转浮点，符号+整数+小数点+小数，小数=分子*10/分母，分子更新：分子=分子%/10
Integer to Roman 罗马数字的表示:I, II, III, IV, V, VI, VII, VIII, IX, X
Multiply Strings 大数乘法：大数_大数={大数+大数，大数_小数}
Number of Digit One 一次迭代：(a + 8) / 10 * m + (a % 10 == 1) * (b + 1);
Palindrome Number 回文数字：负数、0、正数
Perfect Squares 动态规划：d[x]表示x的Perfect Squares，d[] = INT_MAX, d[ii] = 1, d[i + j * j] = min(di[i] + 1, d[i + j \ j])
Permutation Sequence 无重复数字序列的全排列，非递归，下一个全排列(next_permutation)
Plus One 对大数digits[]加1，digits[0]为高位
Power of Two 判断n=2**x，n & (n - 1) == 0
Pow(x, n) 幂运算a**n，快速幂运算，注：n为正数，0，负数
Rectangle Area 求两个矩形合并的面积，矩形A+矩形B-重叠的面积
Reverse Integer 正数反转，注：正数、负数和0，越界
Roman to Integer 罗马数字转10进制，从低有效位到高有效位，注：I, II, III, IV, V, VI, VII, VIII, IX
Sqrt(x) x开根：（1）二分查找x的根（2）牛顿迭代法，float last, val, 其中val=(last + x / val) / 2.0，注：x小于等于0
String to Integer atoi实现：高有效位到低有效位，注：正负号（+，-），非法字符，0，越界（INT_MAX）
Ugly Number 丑数：x分解为2,3,5的乘积，根据定义判断
Ugly Number II 找到从2开始的第n个丑数，ugly[i]表示第i个丑数,ugly[i+1] = min(ugly[i2] * 2, ugly[i3] * 3, ugly[i5] * 5)
Valid Number 浮点数的检查，包括：数字、小数点、指数（e）、正负号（+，-），规则为：数字为（0-9），小数点之前必须有数字且不能有小数点，指数（e）前必须有数字且不能有质数（e），正负号前不能有数字和正负号
Combination Sum 求数组(无重复元素)中所有和为某个值的组合(元素可以多次出现)？递归+回溯
Combination Sum II 求数组(有重复元素)中所有和为某个值的组合?递归+回溯
Combination Sum III 求1-9中选k个(无重复)和为n的所有组合?递归+回溯
Lexicographical Numbers 1-n按字典序排序，找规律，如1-20: 1,10,11,12,13,14,15,16,17,18,19,2,20
Intersection of Two Arrays 求两个数组的交集
Intersection of Two Arrays II 求两个数组的交集（允许重复的元素）
Happy Number 将数字n分解为十进制各位平方的和，直到n=1或者出现循环，两种方法： (1)哈希表+分解定义+结束条件 (2)分解定义+环的判定(快慢两个指针)+结束条件
Number of 1 Bits 无符号整数的二进制表示中1的个数（汉明权重）：n=n&(n-1)
Power of Two 判断一个数是否是2的幂，利用n&(n-1)进行判断，注：本题n<=0不是2的幂
Power of Three 判断一个数是否是3的幂，利用3**m=n => m = ceil(log(n)/log(3))进行判断，注：本题n<=0不是3的幂
Majority Element 数组中出现次数超过一半的元素，两种方法： (1)利用快排思想找到中位数，然后根据中位数出现的次数判断 (2)根据定义
Nim Game 一堆石子，每次取1-3个，你先去，问如何取必胜？必胜策略
Sum of Two Integers 求两个数的和？使用^和&实现
Single Number 数组中只出现一次的数字（其他数字出现两次）？利用位运算(^)实现

字符串

Implement Trie (Prefix Tree) 字典树（前缀树）：添加、查找、公共前缀
Add and Search Word - Data structure design 字典树：添加、正则查找（.）
Count and Say 描述：第<=0个的描述为"1", 第1个的描述为"1"，第2个的描述为"11"，第3个的描述为"21"，以此类推
Length of Last Word 字符串中最后一个单词的长度（单词之间通过空格分隔）：去除字符串末尾空白，计算最后一个单词的长度
First Unique Character in a String 查找字符串中第一个不重复重现的字符，哈希表(hash[256])实现
Reverse String 字符串反转
Find the Difference 字符串t有洗牌后的字符串s插入一个字符得到，找到该插入的字符？哈希表实现

二叉树

Convert Sorted List to Binary Search Tree 将有序链表转换为二叉搜索树，找到链表的中位数(快指针和慢指针)，左边为左子树，右边为右子树，中位数为根
Balanced Binary Tree 平衡二叉树：它是一棵空树或它的左右子树的高度差不超过1，且它的左右子树都是平衡二叉树根据定义，递归实现
Binary Tree Inorder Traversal 二叉树中序遍历：递归，注：用vector保存结果
Binary Tree Preorder Traversal 二叉树先序遍历：递归
Binary Tree Postorder Traversal 二叉树后序遍历：递归
Binary Tree Level Order Traversal 二叉树层次遍历：队列
Binary Tree Level Order Traversal II 二叉树Special层次遍历：队列（从下到上，从左往右）
Binary Tree Paths 路径：从根到叶子经过的节点构成了路径二叉树所有的路径：递归+回溯
Binary Tree Right Side View 二叉树的右视图：队列，只需要保存每层最右边的节点
Binary Tree Zigzag Level Order Traversal zigzag: 奇数行从左往右，偶数行从右往左二叉树层次遍历
Construct Binary Tree from Inorder and Postorder Traversal 根据中序遍历和后序遍历重构二叉树：递归，后序遍历的最后一个元素为根节点
Construct Binary Tree from Preorder and Inorder Traversal 根据先序遍历和中序遍历重构二叉树：递归，先序遍历的第一个元素为根节点注：已知先序、后序，并不一定能重构二叉树
Convert Sorted Array to Binary Search Tree 有序数组构建二叉搜索树：数组的中点为二叉搜索树的根节点
Count Complete Tree Nodes 完全二叉树：只有最下面2层节点的度小于2，且最下面1层的所有节点都位于最左边满二叉树：除了叶子节点外，所有节点的度等于2 满二叉树的节点数：2**h - 1, h为树的深度递归：利用满二叉树的节点数公式快速求解，只用递归或层次遍历可能会超时
Flatten Binary Tree to Linked List 利用先序遍历将二叉树转换为链表(right=next)，记录上一个节点
Invert Binary Tree 二叉树镜像（二叉树反转），递归，先序遍历，swap(root->left, root->right)
Kth Smallest Element in a BST 二叉搜索树中第k小的数：二叉搜索树的中序遍历->有序数组->第k个元素即为所求
Lowest Common Ancestor of a Binary Search Tree 二叉搜索树中两个节点最低公共祖先：先序遍历，如果根节点的值大于一个节点的值，且小于另一个节点的值二叉树中两个节点的最低公共祖先：a. 找到两个节点的路径 b. 求两个链表的第一个公共节点
Maximum Depth of Binary Tree 二叉树的最大深度：递归，叶子节点检查
Minimum Depth of Binary Tree 二叉树的最小深度：递归，叶子节点检查
Path Sum 二叉树中是否存在长度为n的路径，先序遍历，边界
Path Sum II 二叉树中所有长度为n的而路径，先序遍历，边界，路径保存
Validate Binary Search Tree 判断二叉搜索树：(1)根据定义，左子树的值小于等于根的值，右子树的值大于等于根的值，维护min_val和max_val (2)二叉搜索树的中序遍历结果是一个有序数组，以此为依据进行判断
Populating Next Right Pointers in Each Node 二叉树中，同一层的相邻的节点通过next指针连接起来：递归
Same Tree 判断两个二叉树是否一样（相等）：递归
Symmetric Tree 判断是不是中心对称的二叉树<->一个二叉树的两个子树互为镜像，递归比较两棵子树
Serialize and Deserialize Binary Tree 二叉树的序列化和反序列化：(1)先序遍历，用#表示子树为空 (2)层次遍历，用#表示空子树
Sum Root to Leaf Numbers 求二叉树所有路径构成数字的和

Unique Binary Search Trees II 求1...n构成的所有二叉搜索树：递归

for (int i = begin; i < end; i++) {
// 生成左子树集
// 生成右子树集
}

Sum of Left Leaves 求二叉树最左叶子节点的和？递归求解+最左叶子节点的判断(root->left&&!root->left->left&&!root->left->right)

zixie1991 / cplusplus-exercise

leetcode题目总结 #4

leetcode题目总结

数组

链表

哈希表

排序

动态规划

查找

数学

字符串

二叉树