算法总结
贪心算法
贪心算法（又称贪婪算法）是指，在对问题求解时，总是做出在当前看来是最好的选择。也就是说，不从整体最优上加以考虑，算法得到的是在某种意义上的局部最优解 。
例题1.跳跃游戏
给定一个非负整数数组 nums ，你最初位于数组的 第一个下标 。
数组中的每个元素代表你在该位置可以跳跃的最大长度。
判断你是否能够到达最后一个下标。
算法：
设想一下，对于数组中的任意一个位置 y，我们如何判断它是否可以到达？根据题目的描述，只要存在一个位置 x、，它本身可以到达，并且它跳跃的最大长度为 x +nums[x]，这个值大于等于 y，即 x +nums[x]≥y，那么位置 y 也可以到达。
换句话说，对于每一个可以到达的位置 x，它使得 x+1, x+2,?,x+nums[x] 这些连续的位置都可以到达。 这样以来，我们依次遍历数组中的每一个位置，并实时维护 最远可以到达的位置。对于当前遍历到的位置 x，如果它在 最远可以到达的位置 的范围内，那么我们就可以从起点通过若干次跳跃到达该位置，因此我们可以用 x +nums[x] 更新 最远可以到达的位置。
在遍历的过程中，如果 最远可以到达的位置 大于等于数组中的最后一个位置，那就说明最后一个位置可达，我们就可以直接返回 True 作为答案。反之，如果在遍历结束后，最后一个位置仍然不可达，我们就返回 False 作为答案。
数据结构：
矢量vector
代码实现：
class Solution {
public:
bool canJump(vector<int>& nums) {
int n = nums.size();
int rightmost = 0;
for (int i = 0; i < n; ++i) {
//i一定是可达范围内
if (i <= rightmost) {
rightmost = max(rightmost, i + nums[i]);
if (rightmost >= n - 1) {
return true;
}
}
}
return false;
}
};
例题2.加油站
在一条环路上有 N 个加油站，其中第 i 个加油站有汽油 gas[i] 升。你有一辆油箱容量无限的的汽车，从第 i 个加油站开往第 i+1 个加油站需要消耗汽油 cost[i] 升。你从其中的一个加油站出发，开始时油箱为空。如果你可以绕环路行驶一周，则返回出发时加油站的编号，否则返回 -1。
说明:
如果题目有解，该答案即为唯一答案。
输入数组均为非空数组，且长度相同。
输入数组中的元素均为非负数。
算法：
首先如果总油量减去总消耗大于等于零那么一定可以跑完一圈，说明 各个站点的加油站 剩油量rest[i]相加一定是大于等于零的。
每个加油站的剩余量rest[i]为gas[i] - cost[i]。
i从0开始累加rest[i]，和记为curSum，一旦curSum小于零，说明[0, i]区间都不能作为起始位置，起始位置从i+1算起，再从0计算curSum。
那么局部最优：当前累加rest[j]的和curSum一旦小于0，起始位置至少要是j+1，因为从j开始一定不行。全局最优：找到可以跑一圈的起始位置。
数据结构：
矢量vector
代码实现
class Solution {
public:
int canCompleteCircuit(vector<int>& gas, vector<int>& cost) {
int curSum = 0;
int totalSum = 0;
int start = 0;
for (int i = 0; i < gas.size(); i++) {
curSum += gas[i] - cost[i];
totalSum += gas[i] - cost[i];
if (curSum < 0) { // 当前累加rest[i]和 curSum一旦小于0
start = i + 1; // 起始位置更新为i+1
curSum = 0; // curSum从0开始
}
}
if (totalSum < 0) return -1; // 说明怎么走都不可能跑一圈了
return start;
}
};
回溯算法
广度优先算法BFS
广度优先搜索算法（Breadth-First Search，BFS）是一种盲目搜寻法，目的是系统地展开并检查图中的所有节点，以找寻结果。换句话说，它并不考虑结果的可能位置，彻底地搜索整张图，直到找到结果为止。
例题1.从上到下打印二叉树
从上到下打印出二叉树的每个节点，同一层的节点按照从左到右的顺序打印。
例如:
给定二叉树: [3,9,20,null,null,15,7],
返回：
[3,9,20,15,7]
算法：
1.特例处理： 当树的根节点为空，则直接返回空列表 [] ；
2.初始化： 打印结果列表 res = [] ，包含根节点的队列 queue = [root] ；
3.BFS 循环：
当队列 queue 为空时跳出；
出队： 队首元素出队，记为 node；
打印： 将 node.val 添加至列表 tmp 尾部；
添加子节点： 若 node 的左（右）子节点不为空，则将左（右）子节点加入队列 queue ；
4.返回值： 返回打印结果列表 res 即可。
实现代码：
class Solution {
public:
vector<int> levelOrder(TreeNode* root) {
vector<int> res;
if(!root) return res;
queue<TreeNode*> que;
que.push(root);
while(!que.empty()){
TreeNode* node = que.front();
que.pop();
res.push_back(node->val);
if(node->left) que.push(node->left);
if(node->right) que.push(node->right);
}
return res;
}
};
深度优先算法
例题1.中序遍历二叉树
给定一个二叉树的根节点 root ，返回它的 中序 遍历。
算法
首先我们需要了解什么是二叉树的中序遍历：按照访问左子树——根节点——右子树的方式遍历这棵树，而在访问左子树或者右子树的时候我们按照同样的方式遍历，直到遍历完整棵树。因此整个遍历过程天然具有递归的性质，我们可以直接用递归函数来模拟这一过程。
定义 inorder(root) 表示当前遍历到root 节点的答案，那么按照定义，我们只要递归调用 inorder(root.left) 来遍历root 节点的左子树，然后将 root 节点的值加入答案，再递归调用inorder(root.right) 来遍历 root 节点的右子树即可，递归终止的条件为碰到空节点。
数据结构
矢量vector
代码实现
class Solution {
public:
void inorder(TreeNode* root, vector<int>& res) {
if (!root) {
return;
}
inorder(root->left, res);
res.push_back(root->val);
inorder(root->right, res);
}
vector<int> inorderTraversal(TreeNode* root) {
vector<int> res;
inorder(root, res);
return res;
}
};
动态规划
动态规划，英文是Dynamic Programming，简称DP，擅长解决“多阶段决策问题”，利用各个阶段阶段的递推关系，逐个确定每个阶段的最优决策，并最终得到原问题的最优决策。
例题1.最长回文字符串
给你一个字符串 s，找到 s 中最长的回文子串。
思路与算法
p(i,j)表示字符串索引值 i 到 j 的字符串，s[ i ]表示字符串索引 i 对应的字符。
p( i, j) = 1 表示字符串是回文串，否则不是。
初始条件：
P( i, i) = 1, P(i, i+1) = 1 && s[ i ] = s[i+1]
转移方程：
P( i, j ) = P( i - 1, j + 1) && s[ i ] = s[j]
代码实现
class Solution {
public:
string longestPalindrome(string s) {
int len=s.size();
if(len==0||len==1)
return s;
int start=0;//回文串起始位置
int max=1;//回文串最大长度
vector<vector<int>> dp(len,vector<int>(len));//定义二维动态数组
for(int i=0;i<len;i++)//初始化状态
{
dp[i][i]=1;
if(i<len-1&&s[i]==s[i+1])
{
dp[i][i+1]=1;
max=2;
start=i;
}
}
for(int l=3;l<=len;l++)//l表示检索的子串长度，等于3表示先检索长度为3的子串
{
for(int i=0;i+l-1<len;i++)
{
int j=l+i-1;//终止字符位置
if(s[i]==s[j]&&dp[i+1][j-1]==1)//状态转移
{
dp[i][j]=1;
start=i;
max=l;
}
}
}
return s.substr(start,max);//获取最长回文子串
}
};