LeetCode

(1)栈和队列

 栈，先进后出。   队列，先进先出。

具体算法题训练：

• 利用栈(一个数据栈一个字符栈)和状态机实现一个简单计算器（”+”,”-“,”(“)—-224(hard)
• 利用最大堆和最小堆寻找中位数—-295(hard)
• 利用最大堆求一个数组中第k个大的元素—-215(median)

  (2)链表

  struct ListNode{
    int val;                  \\链表数字域
    ListNode *next;       \\链表指针域
    ListNode(int x) : val(x), next(NULL) {} 
  }

具体算法题训练：

使用temp和记录节点值去进行链表逆序。

• 链表逆序（不可申请额外空间）—-206(easy)
• 链表逆序b(不申请额外的空间）,从m到n逆序。—-92（medium）
• 求两个链表的交点,已知headA和headB。—-160（easy）
• 链表求环，（快慢指针）给定一个链表，判断其中是否有环—-141(easy)
• 链表划分，将小于x的放在大于x的节点前，且保持相对位置—-86（medium）
• 复制带随机指针的链表，节点中存在指向任意节点的随机指针—-138（hard）
• 排序链表的合并，合并两个已排序的链表，合并后也有序。—->21(easy)
• k个排序链表的合并，合并后任然有序。 —->23(hard)

(3)贪心算法

具体算法题训练：

• 分糖果，需求因子和糖果大小 —->455(easy)
• 摇摆序列，求序列的最长摇摆子序列的长度—->376(medium)
• 移除k个数字，str中移除k个数字使得剩下的最小—->402(medium)
• 跳跃游戏，数组中每个元素代表可以跳跃的长度—->55(medium)
• 跳跃游戏||，数组中每个元素代表可以跳跃的长度，最少跳跃—->55(medium)
• 射击气球，至少多少个弓箭手才能打爆全部气球。 —->452(Medium)
• 最优加油方法，以最低加油次数到达目的地。 —->871(hard)

(4)递归、回溯与分治

递归：函数Func(Type a,……)直接或间接调用函数本身，则该函数称为递归函数。
回溯：回溯算法实际上一个类似枚举的搜索尝试过程，主要是在搜索尝试过程中寻找问题的解，当发现已不满足求解条件时，就“回溯”返回，尝试别的路径。
分治：
剪枝：剪掉一些不必要的运算。

具体算法题训练：

• 求子集，返回一个数组（无重复元素）的所有子集。 —->78(Medium)
• 求子集||，返回数组（有重复）的所有子集（无重复元素）。 —->90(Medium)
• 组合数之和，求所有子集中和为target的无重复子集。 —->40(Medium)

  (5)二叉树与图

  二叉树：每个节点最多有两个子树，这两个子树有左右之分，次序不可颠倒。

前序遍历：先访问自己，再访问左子树，最后右子树
中序遍历：先访问左子树，再访问自己，最后右子树
后序遍历：先访问左子树，再访问右子树，最后自己

图：1.深搜 2.广搜

具体算法题训练：

• 路径之和，求所有从跟节点到叶节点路径之和为sum的组合 —->113(Medium)
• 最近的公共祖先，给两个节点，求公共祖先，越深越好 —->236(Medium)
• 二叉树转链表，给定一个二叉树，原地将它展开为链表。 —->114(Medium)
• 二叉树的右视图。返回右侧能看到的节点值 —->199(Medium)
• 课程安排。有依赖关系 —->207(Medium)

(6)二分查找和二叉排序树

二叉排序树：

1.若左子树不空，则左子树上所有结点的值均小于或者等于它的根结点的值。
2.若右子树不空，则右子树上所有结点的值均大于或者等于它的根结点的值。
3.左右子树也分别为二叉排序树。
4.等于的情况只能出现在左子树和右子树的某一侧。
 中序遍历是从小到大的。

具体算法题训练：

• 插入位置，在一个排序数组中查找target —->35(easy)
• 区间查找，有重复元素，返回target的左右点下标 —->34(medium)
• 旋转数组查找，在一个旋转的数组中查找一个数 —->33(medium)
• 序列化和反序列化二叉搜索树，string和二叉树转换 —->449(medium)
• 计算右侧小于当前元素的个数，已知nums数组求count —->315(medium)

(7)哈希表与字符串

  给定表M，存在函数f(key），可以根据任意的key求出表中的地址，称表M为哈希（Ha h）表。

  任意元素的映射：
  将关键字key（大整数，字符串，浮点数等）转化为整数，再对表长取余，从而关键字值被转换为哈希表的表长范围内的整数。

  拉链法解决冲突，构造哈希表：
  将所有的哈希函数结果相同的结点连接在同一个单链表中，如图所示。

具体算法题训练：

• 最长回文串，求构造的最长回文串 —->409(easy)
• 词语模式，确认str和pattern是否匹配 —->290(easy)
• 字母异位词分组，字母相同，但排列不同的字符串 —->49(medium)
• 无重复的最长子串，不含有重复字符的 最长子串 的长度 —->3(medium)
• 重复的DNA序列，查找序列中所有出现超过一次10子串—->187(medium)

(8)搜索

搜索思想
DFS（Deep First Search）深度优先搜索
BFS（Breath First Search）广度优先搜索

具体算法题训练：

• 岛屿数量，求一个二维数组中所有的连通域 —->200(medium)
• 单词接龙，找到从 begin 到 end 的最短转换序列的长度 —->127(medium)
• 单词接龙2，找到所有最短转换序列 —-> 126(hard)

(9)动态规划

1.确认原问题和子问题
2.确定状态，第i个状态
3.确认边界状态的值
4.确定转移状态方程

具体算法题训练：

• 爬楼梯，有多少不同的方式爬上楼顶 —-> 70(easy)
• 打家劫舍，相邻的屋子不能用一天被盗—-> 198(easy)
• 找零钱，计算可以凑成总金额所需的最少的硬币个数—-> 322(medium)
• 三角形最小路径之和，自顶向下最小路径之和—-> 120(medium)

• 最长上升子序列，给定一个无序的整数数组，找到其中最长上升子序列的长度。—-> 300 (medium)

  (10)每日一题

• 水壶问题，x升 和 y升 的水壶得到z 升的水—->365(medium)

 做不出来，两种解法：
  (1)、深度优化搜索
  (2)、数学，贝祖定理

• 链表的中间节点，返回一个链表的中间节点—->876(easy)
• 旋转图像，给定一个n*n的二维矩阵表示一个图像，旋转90度 —->48(medium)