一、经典dp——最大子数组之和
1.链接
53. 最大子数组和 - 力扣（LeetCode）
2.描述
给你一个整数数组 nums ，请你找出一个具有最大和的连续子数组（子数组最少包含一个元素），返回其最大和。
3.思路
这是经典的动归问题，一般解决动归问题分四步：
1.描述状态：f(i) : 以第i个为子数组结尾的最大子数组之和
2.状态方程：f(i) = max（f(i-1) + arr[ i ]，arr[ i ]）
解析：我们假设第i个结尾的最大子数组之和为f（i），而我们若想知道下一个f（i+1），我们需要判断，arr[ i ] 在加上以前一个为底的最优解，也就是加上后较大还是不加较大，通过这个方式走dp就可以得到每一个为子数组底时的最优解，再其中选出一个最大的就是本题答案
3.初始状态：f（0）= arr[ 0 ]
4.dp容器：一维数组
关于本题的优化：本题中，我们实际并不需要记录每一步的最优解，只需要找到其中最大的，所以实际不需要容器去记录，只需要有一个整形去记录下最优解即可
4.参考代码
class Solution {
public:
int maxSubArray(vector<int>& nums)
{
int* dp = new int[nums.size()];
dp[0] = nums[0];
int ret = nums[0];
for(int i = 1;i<nums.size();i++)
{
dp[i] = max(nums[i]+dp[i-1],nums[i]);
if(ret < dp[i])
{
ret = dp[i];
}
}
return ret;
}
};优化后：
class Solution {
public:
int maxSubArray(vector<int>& nums)
{
int dp = nums[0];
int ret = nums[0];
for(int i = 1;i<nums.size();i++)
{
dp = max(nums[i]+dp,nums[i]);
if(ret < dp)
{
ret = dp;
}
}
return ret;
}
};二、字符串回文
1.链接
回文数索引_牛客题霸_牛客网 (nowcoder.com)
2.描述
3.思路
关于字符串回文的题目，我们要想到头尾指针的思路，回文字符串的特点就是头指针和尾指针往中间一起走，都相同，这题说一定有一个解满足条件，说明我们只需要头尾指针去扫描，当遇到不同时，删除任意一个后再判断是否回文，若不是则说明另一个下标就是要删除的
4.参考代码
#include <iostream>
using namespace std;
bool is_pal(const string& str)//判断字符串回文
{
int begin = 0;
int end = str.size()-1;
while(begin < end)
{
if(str[begin++] != str[end--])
{
return false;
}
}
return true;;
}
int main()
{
int n;
cin >> n;
string str;
while(n--)
{
cin >> str;
if(is_pal(str))//若已经是回文，则不需要判断
{
cout << -1 << endl;
}
int begin = 0;
int end = str.size()-1;
while(begin < end)
{
if(str[begin] != str[end])
{
str.erase(begin,1);
if(is_pal(str))
{
cout << begin << endl;
}
else
{
cout << end << endl;
}
break;
}
begin++;
end--;
}
}
return 0;
}三、把数组排列成最小数
1.链接
把数组排成最小的数_牛客题霸_牛客网 (nowcoder.com)
2.描述
输入一个非负整数数组numbers，把数组里所有数字拼接起来排成一个数，打印能拼接出的所有数字中最小的一个。
例如输入数组[3，32，321]，则打印出这三个数字能排成的最小数字为321323。
1.输出结果可能非常大，所以你需要返回一个字符串而不是整数
2.拼接起来的数字可能会有前导 0，最后结果不需要去掉前导 0
3.思路
这里利用sort函数去实现排序，这道题其实是贪心算法，也就是局部最优解的方式，每个相邻的两个数拼接起来都是当前最小的顺序，则可以保证整个序列拼接起来就是最小的，我们可以写一个回调函数去交给sort去排
4.参考代码
#include <string>
class Solution
{
public:
static bool cmp(int x,int y)
{
string xs = to_string(x);
string ys = to_string(y);
string A = xs;
A+=ys;
string B =ys;
B+=xs;
return A<B;
}
string PrintMinNumber(vector<int>& numbers)
{
if(numbers.empty())
{
return "";
}
sort(numbers.begin(),numbers.end(),cmp);
string ret;
for(int i =0;i<numbers.size();i++)
{
ret += to_string(numbers[i]);
}
return ret;
}
};四、单链表找公共节点
1.链接
两个链表的第一个公共结点_牛客题霸_牛客网 (nowcoder.com)
2.描述
输入两个无环的单向链表，找出它们的第一个公共结点，如果没有公共节点则返回空。（注意因为传入数据是链表，所以错误测试数据的提示是用其他方式显示的，保证传入数据是正确的）
3.思路
快慢指针，先统计两个链表的长度，然后让长链表先走他们的差距步长，然后再一起走，判断相等
4.参考代码
class Solution
{
public:
int List_len(ListNode* pHead)
{
int count = 0;
ListNode* cur = pHead;
while(cur)
{
count++;
cur = cur->next;
}
return count;
}
ListNode* FindFirstCommonNode( ListNode* pHead1, ListNode* pHead2)
{
int len1 = List_len(pHead1);
int len2 = List_len(pHead2);
int gap;
ListNode* fast;
ListNode* slow;
if(len1 >= len2)
{
gap = len1 - len2;
fast = pHead1;
slow = pHead2;
}
else
{
gap = len2 -len1;
fast = pHead2;
slow = pHead1;
}
while(gap--)//先让长的先走gap步
{
fast = fast->next;
}
while(fast && slow)//没有交点，通过这里退出
{
if(fast == slow)//找到交点，通过这里退出
{
break;
}
fast = fast->next;
slow = slow->next;
}
//此时若是有交点，则通过break退出，fast和slow同时指向公共节点
//若是没有交点，fast和slow也指向空，直接返回也可以
return fast;
}
};
五、二叉树判断深度
1.链接
二叉树的深度_牛客题霸_牛客网 (nowcoder.com)
2.描述
给一颗二叉树，要求返回二叉树的高度
3.思路
（1）递归思想
递归的往下遍历，分别得到左右子树的高度，然后比较返回大的那个，也可以是回溯算法的思想去解决
（2）层序遍历的思想
二叉树的层序遍历是利用队列的特性，将队首的节点出队列时，将其左右子树的节点放到队尾排队，从第一层开始，每次可以通过队列内的size大小得到每一层有多少个节点，因此可以分层次的将每一层的数据打印出来，因此也能够用这个办法去统计有多少层
4.参考代码
（1）递归思想
class Solution
{
public:
int TreeDepth(TreeNode* pRoot)
{
if(pRoot == nullptr)
{
return 0;
}
int Left = TreeDepth(pRoot->left) + 1;
int Right = TreeDepth(pRoot->right) + 1;
return Left > Right ? Left : Right;
}
};（2）层序遍历的思想
class Solution
{
public:
int TreeDepth(TreeNode* pRoot)
{
if(pRoot == nullptr)//为空则返回0
{
return 0;
}
int len = 0;//用来统计高度/层数
queue<TreeNode*> q;
q.push(pRoot);
while(!q.empty())
{
int size = q.size();//记录每一层的大小，每次出完一层会更新size值
for(int i = 0;i<size;i++)//将每一层的数据都遍历pop，并且把下一层的数据放到队列中
{
TreeNode* tmp = q.front();
q.pop();
if(tmp->left != nullptr)
{
q.push(tmp->left);
}
if(tmp->right != nullptr)
{
q.push(tmp->right);
}
}
len++;//每出完一层就统计一层
}
return len;
}
};总结
这次的总结里，有几题特别经典的题目，例如动归，找节点等等
