OJ细节注意事项
用C++刷题的时候，cin和cout的时间效率是不如scanf和printf的，如果输入输出的数据量非常大时，建议使用scanf和printf，不然有可能算法没问题但是还是超时了。
另外，有时候我们使用最大值或者最小值的时候，可以不用INT_MAX或者INT_MIN。有时候会导致数据溢出而报错，最大值可以使用 0x3f3f3f3f，最小值可以使用-0x3f3f3f3f。（4个3f）。
1.最小花费爬楼梯
（大部分题都可以在牛客网中直接搜到得到）
这是一道很经典且基础的动态规划的题目。
1.首先我们来分析状态表示，我们可以根据经验来发现这是一个线性dp，我们可以定义一个数组，以i位置为结尾，表示到这个位置所需要的最小花费。
2.再来分析状态转移方程，既然知道以i为结尾表示到这个位置的最小花费，那么它该怎么表示呢？据题意发现，它可以从i - 1这个位置跳上来，也可以从i - 2这个位置跳上来，一共就这两种情况，所以状态转移方程： dp[i] = min(dp[i - 1] + cost[i - 1],dp[i - 2] + cost[i - 2])。
3.注意一下填表顺序，因为我们填表的时候依赖的是 i - 1和i - 2这个位置的，所以填表顺序是从左往右。
4.初始化，因为由题意可得，我们可以从0或者1下标的台阶开始，所以dp[0]和dp[1]都可以初始化为0。
至此算法原理就到这里结束了
代码（核心代码模式）：
int minCostClimbingStairs(vector<int>& cost) {
int n = cost.size();
vector<int> dp(n + 1);
for(int i = 2; i <= n; ++i)
{
dp[i] = min(dp[i - 1] + cost[i - 1],dp[i - 2] + cost[i - 2]);
}
return dp[n];
}不过要注意，我们的dp数组要多开一个，因为我们要跳到第n个台阶才算结束。
2.数组中两个字符串的最小距离
解法一：暴力解法
直接两层for循环，进行暴力枚举，这样的话时间复杂度为O（N^2)，一般会超时。
解法二：贪心
我们可以定义两个变量，分别为prev1和prev2，分别代表从左向右遍历时，str1最后出现的位置和str2最后出现的位置，这样的话我们在遍历的时候，一边更新结果ret，一边更新str1或者str2最后出现的位置，我们把这种方式称为预处理。时间复杂度为O（N）。
代码
#include <iostream>
using namespace std;
int main()
{
int n;
string s1,s2;
string s; // 这里就不定义数组了，每输入一个就处理一个
cin >> n >> s1 >> s2;
int prev1 = -1;
int prev2 = -1;
int ret = 0x3f3f3f3f;
for(int i = 0; i < n; ++i)
{
cin >> s;
if(s == s1)
{
if(prev2 != -1)
{
ret = min(ret,i - prev2);
}
prev1 = i;
}
else if(s == s2)
{
if(prev1 != -1)
{
ret = min(ret,i - prev1);
}
prev2 = i;
}
}
cout << (ret == 0x3f3f3f3f ? -1 : ret) << endl;
return 0;
}3.dd爱框框
需要注意的是，它的下标是从1开始的。
解法一：暴力解法
定义两个指针，两层for循环，从左往右先固定left（left从0开始），向后暴力枚举，时间复杂度为O（N^2)。
解法二：滑动窗口
使用滑动窗口要特别注意，这道题所给的数组的元素的大小是大于0的！如果小于0就不能使用滑动窗口了，因为它不满足单调性了。
算法流程：
因为滑动窗口的思想是两个指针同时向右移动，当sum >= x时，left向右移，使得sum减小，当sum < x 时，right右移，使得sum增大，这样的遍历方式具有单调性，可以使用滑动窗口，但如果有元素的值小于0，那么left向右移的时候既可能增大又可能减小，不满足单调性，此时就不再适用滑动窗口了。
代码：
#include <iostream>
#include <vector>
using namespace std;
int main()
{
int n,x;
cin >> n >> x;
vector<int> v(n);
int sum = 0;
for(int i = 0; i < n; ++i)
{
cin >> v[i];
}
int l = 0,r = 0;
int left = 0,right = 0;
int ret = 0x3f3f3f3f;
while(right < n)
{
if(sum < x)
{
sum += v[right];
right++;
}
else
{
if(ret > right - left)
{
l = left;
r = right - 1;
ret = right - left;
}
sum -= v[left];
left++;
}
}
// 因为题意里的下标是从数组的1开始的
cout << (l + 1) << " " << (r + 1)<< endl; // 注意下标的映射关系
return 0;
}4.杨辉三角
这是一道很简单的线性dp问题。
解法：
状态表示：定义一个int dp[31][31]，其中dp[i][j]表示第i行第j列的值。
状态转移方程：dp[i][j] = dp[i - 1][j - 1] + dp[i - 1][j]。
初始化：可以将dp[0][0]初始化成1。
填表顺序：从上往下，从左往右。
返回值：据题意，按宽5直接打印每一行。
代码：
#include <iostream>
using namespace std;
int main()
{
int n;
cin >> n;
int dp[31][31] = {0};
dp[0][0] = 1;
for(int i = 1; i <= n; ++i)
{
for(int j = 1; j <= i; ++j)
{
dp[i][j] = dp[i - 1][j - 1] + dp[i - 1][j];
printf("%5d",dp[i][j]);
}
cout << endl;
}
return 0;
}5.孩子们的游戏
题目描述非常的繁琐，其实就是约瑟夫环问题。
解法一：模拟
我们可以用双向环形链表，非常简单就能完成。
或者也可以用一个bool数组，下标对应孩子的编号，主要也是环形数组的概念。
时间复杂度为O(n)，空间复杂度为O(n)。
解法二：动态规划
1.状态表示：可以用dp[i]表示有i个孩子围在一起，获胜的那个孩子的编号。
2.状态转移方程：
假设dp[n]，m。 首先我们找到m - 1的下标，将这个孩子删掉。然后m - 1的下一个是m。将m 的下标重新标识为0，那么m + 1 就是1，依次类推
此时孩子数变成了n - 1，所以dp[n] 与 dp[n - 1] 的关系，也就是下标的映射关系。
所以dp[n] = (dp[n - 1] + m) % n。
所以状态转移方程 dp[i] = (dp[i - 1] + m) % n。
因为dp[i]它依赖的是dp[i - 1]，所以我们可以利用空间优化，将空间复杂度降为O(1)。
代码
int LastRemaining_Solution(int n, int m) {
int f = 0;
for(int i = 1; i <= n; ++i)
{
f = (f + m) % i;
}
return f;
}6.链表相加（二）
解法：模拟
主要分为 逆序 + 高精度相加。
我们可以创建一个虚拟头结点，先将两个链表逆置一下，方便相加。然后再采用头插法将结果插入到新链表中。
代码
class Solution {
public:
ListNode* addInList(ListNode* head1, ListNode* head2) {
int t = 0;
ListNode* cur1 = ListReverse(head1);
ListNode* cur2 = ListReverse(head2);
ListNode* ret = new ListNode(-1);
while(cur1 || cur2 || t)
{
if(cur1)
{
t += cur1->val;
cur1 = cur1->next;
}
if(cur2)
{
t += cur2->val;
cur2 = cur2->next;
}
ListNode* tmp = new ListNode(t % 10);
t /= 10;
tmp->next = ret->next;
ret->next = tmp; // 直接使用头插法，完事后就可以直接返回结果
}
cur1 = ret->next;
delete ret;
return cur1;
}
ListNode* ListReverse(ListNode* head) // 头插逆置
{
ListNode* newHead = new ListNode(-1);
ListNode* cur = head;
while(cur)
{
ListNode* next = cur->next;
cur->next = newHead->next;
newHead->next = cur;
cur = next;
}
cur = newHead->next;
delete newHead;
return cur;
}
};7.大数乘法
解法：
主要还是模拟解法。需要注意的是要先无进位相乘，然后再统一作进位。
并且，我们要对每一个进位用下标进行标记，方便进行累加。
算法流程：
首先先将两个字符串进行逆置，方便相加，再创建一个数组，数组的大小是两个字符串的长度相加，这样保证了最终结果的长度不会超过数组的长度。
不过后续也要处理前导零问题。
代码：
class Solution {
public:
string solve(string s, string t) {
int n = s.size();
int m = t.size();
reverse(s.begin(),s.end());
reverse(t.begin(),t.end());
vector<int> tmp(m + n);
for(int i = 0; i < n; ++i)
{
for(int j = 0; j < m; ++j)
{
tmp[i + j] += (s[i] - '0') * (t[j] - '0');
}
}
string ret;
int c = 0;
for(auto x : tmp)
{
c += x;
ret += (c % 10) + '0';
c /= 10;
}
// 因为我们给tmp数组开的大小是m + n，因为两数相乘之后的位数绝对不会超过m + n
// 但是也有可能存在前导零，需要去除。
while(ret.size() > 1 && ret.back() == '0')
ret.pop_back(); // 因为ret还没逆置，所以如果有前导零也在末尾
reverse(ret.begin(),ret.end());
return ret;
}
};
