剑指offer经典题目整理（七）
一、经典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;}
};总结
这次的总结里，有几题特别经典的题目，例如动归，找节点等等