人生何处不青山的主页

贪心算法基础

贪心的本质是选择每一阶段的局部最优，从而达到全局最优。

说实话贪心算法并没有固定的套路。

如何验证可不可以用贪心算法呢？

最好用的策略就是举反例，如果想不到反例，那么就试一试贪心吧。

一般数学证明有如下两种方法：

• 数学归纳法
• 反证法

看教课书上讲解贪心可以是一堆公式，估计大家连看都不想看，所以数学证明就不在我要讲解的范围内了，大家感兴趣可以自行查找资料。

面试中基本不会让面试者现场证明贪心的合理性，代码写出来跑过测试用例即可，或者自己能自圆其说理由就行了。

刷题或者面试的时候，手动模拟一下感觉可以局部最优推出整体最优，而且想不到反例，那么就试一试贪心。

贪心算法一般分为如下四步：

• 将问题分解为若干个子问题
• 找出适合的贪心策略
• 求解每一个子问题的最优解
• 将局部最优解堆叠成全局最优解

动态规划基础

动态规划，英文：Dynamic Programming，简称DP，如果某一问题有很多重叠子问题，使用动态规划是最有效的。

所以动态规划中每一个状态一定是由上一个状态推导出来的。贪心没有状态推导，而是从局部直接选最优的。

解题步骤：

1. 确定dp数组（dp table）以及下标的含义
2. 确定递推公式
3. dp数组如何初始化
4. 确定遍历顺序
5. 举例推导dp数组

如何debug：
找问题的最好方式就是把dp数组打印出来，看看究竟是不是按照自己思路推导的

回溯的基本理论

回溯是递归的产物。

回溯相当于穷举搜索。

回溯主要解决的问题：

• 组合问题：N个数里面按一定规则找出k个数的集合
• 切割问题：一个字符串按一定规则有几种切割方式
• 子集问题：一个N个数的集合里有多少符合条件的子集
• 排列问题：N个数按一定规则全排列，有几种排列方式
• 棋盘问题：N皇后，解数独等等

回溯算法抽象为树形结构，回溯法解决的是在集合中递归寻找子集，集合的大小构成树的宽度，递归的深度就是树的深度。

回溯算法模板：

• 回溯算法的返回值以及参数：返回值一般为void，但是参数需要根据逻辑来定。

  1	void backtracking(参数)

• 回溯算法终止条件：由于是树形结构，所以一般是搜索到叶子节点了，也就找到了满足条件的一个答案，将答案存储起来，结束本次递归。

  1 2 3 4

  if (终止条件) { 存放结果; return; }

• 回溯搜索的遍历过程：在集合中搜索，集合的大小就是树的宽度，递归的深度就是树的深度

  

  1 2 3 4 5

  for (选择：本层集合中元素（树中节点孩子的数量就是集合的大小）) { 处理节点; backtracking(路径，选择列表); // 递归 回溯，撤销处理结果 }

  for循环就是遍历集合区间，可以理解一个节点有多少个孩子，这个for循环就执行多少次。

  backtracking这里自己调用自己，实现递归。

  大家可以从图中看出for循环可以理解是横向遍历，backtracking（递归）就是纵向遍历，这样就把这棵树全遍历完了，一般来说，搜索叶子节点就是找的其中一个结果了。

  阅读全文 »

单调栈

每日温度

题目：739

给定一个整数数组 temperatures ，表示每天的温度，返回一个数组 answer ，其中 answer[i] 是指对于第 i 天，下一个更高温度出现在几天后。如果气温在这之后都不会升高，请在该位置用 0 来代替。

分析：

寻找后面第一个比自己高的值所在的位置.

思路1：暴力破解，外层循环遍历每一个元素，内层循环从当前元素向后遍历，寻找第一个比当前值大的元素所在位置，如果后面没有比当前值大的元素或者只有与当前值相等的元素，那么就填充0.

二叉树简介

基础概念：满二叉树、完全二叉树、二叉查找树（搜索树）、平衡二叉搜索树

二叉搜索树是一个有序树。

• 若它的左子树不空，则左子树上所有结点的值均小于它的根结点的值；
• 若它的右子树不空，则右子树上所有结点的值均大于它的根结点的值；
• 它的左、右子树也分别为二叉排序树

二叉树存储结构：顺序存储（如果双亲结点是i那么左孩子是2*i + 1，右孩子是2*i + 2)和链式存储

二叉树的遍历方式：

• 深度优先遍历

  • 前序遍历（递归法，迭代法）
  • 中序遍历（递归法，迭代法）
  • 后序遍历（递归法，迭代法）

• 广度优先遍历

  • 层次遍历（迭代法）

  栈其实就是递归的一种实现结构，也就说前中后序遍历的逻辑其实都是可以借助栈使用递归的方式来实现的。

  广度优先遍历的实现一般使用队列来实现，这也是队列先进先出的特点所决定的，因为需要先进先出的结构，才能一层一层的来遍历二叉树。

  二叉树节点定义：

  1 2 3 4 5 6

  struct TreeNode { int val; TreeNode *left; TreeNode *right; TreeNode(int x) : val(x), left(NULL), right(NULL) {} };

栈与队列理论基础

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

在C++中，栈与队列是底层容器双端队列的适配器。详细可参看博客中关于STL源码的解析。

总结

通过两个指针在一个for循环下完成两个for循环的工作。

双指针法将时间复杂度：O(n^2)的解法优化为 O(n)的解法。也就是降一个数量级。

字符串基本理论

字符串看作是所有元素都是字符的线性表。

在C++种std::string表示字符串类型。

如果库函数仅仅是 解题过程中的一小部分，并且你已经很清楚这个库函数的内部实现原理的话，可以考虑使用库函数。

哈希表理论基础

哈希表就是利用一个hash函数，将元素的值value映射到一个索引范围内。比如通过取模运算将任意整数 X 映射到 [0, TableSize - 1]，那么 TableSize 是哈希表的大小，索引范围就是 [0, TableSize - 1]。

根据元素的值就能实现常数级的查找。

主要用于需要判断一个元素是否存在一个集合中。

哈希函数的问题是：如果元素的取值空间远大于索引的取值空间，那么有可能会导致不同的元素被映射到相同的位置，也就是发生了碰撞。对于碰撞的处理有以下几种处理方式：线性探测、二次探测、开链等。

常用的哈希结构：

• 数组
• set （集合）
• map(映射)

在C++的STL中提供基于不同底层数据结构的set和map，详细内容可见个人博客：https://guomw.net/

对于set来说，底层实现和优劣对比如下：（此处省略了unordered_multiset）

底层数据结构是红黑树的set，由于红黑树是一种平衡二叉树，是根据key值进行排序，所以key值不能修改。只能删除和增加。

对于map来说，底层实现和优劣对比如下：

综上，如果想要使用哈希表解决哈希问题，优先使用底层实现为hash table的unordered_set和unordered_map。

哈希表是使用空间换取时间的数据结构，set的元素是一个值，map个每个元素是键值对。

链表理论基础

链表在逻辑结构上是线性表，在存储结构上是链式存储结构，即由一个个节点组成。

对应了STL中的vector。

链表的类型：

单链表、双链表、循环链表

链表的定义：

数据+指针

1
2
3
4
5
6

// 单链表
struct ListNode {
    int val;  // 节点上存储的元素
    ListNode *next;  // 指向下一个节点的指针
    ListNode(int x) : val(x), next(NULL) {}  // 节点的构造函数
};

链表的主要操作：

1.删除节点：需要一个临时指针指向被删除的节点，然后令前面的next指针指向被删除节点的next。

2.插入节点：先上链（令新节点的next指向后者），再断链（令前者的next指向新节点）