之前的文章提到了一道高频题：最长不重复的字串，用到动态窗口。解法就在之前的文章。这篇文章从牛客上找了一些手撕题，在这里记录分享一下。
1.将给定的字符串中的每个单词的首字母转化为大小字母【简单】
首字母大写__牛客网 不难 就是考察你记不记得小知识点：
小写字母-32=大写字母 //注意-32 32不用引号 同时是32不是26，
又是这种犄角旮旯知识点
#include <iostream>
#include <vector>
#include <bits/stdc++.h>
using namespace std;int main() {string s;getline(cin,s);if(s[0]>='a'&&s[0]<='z'){s[0]=s[0]-32;}for(int i=1;i<s.length();i++){if(s[i-1]==' '||s[i-1]=='\t'||s[i-1]=='\r'||s[i-1]=='\n'){if(s[i]>='a'&&s[i]<='z'){s[i]=s[i]-32;}}}cout<<s;return 0;
}
2.写一个函数，对字符串进行压缩，例如将“aaaabbbbccce”压缩为"a4b4c3e1"【简单】
. - 力扣（LeetCode）
又是考察犄角旮旯的知识点，服了
ans+=to_string(sum); //数字要通过to_string转为字符串，用+方法放后面
正常的char用push_back就行，这种题纯考冷门知识点记忆力啊……
class Solution {
public:string compressString(string S) {string ans;ans.push_back(S[0]);int sum=1;for(int i=1;i<S.length();i++){if(S[i-1]!=S[i]){ans+=to_string(sum);ans.push_back(S[i]);sum=1;}else{sum++;}if(i==S.length()-1){ans+=to_string(sum);}}if(ans.length()<S.length()){
return ans;}else{return S;}}
};3.代码题：对一个字符串进行翻转【入门】
入门题不多说字符串反转_牛客题霸_牛客网
#include <iostream>
using namespace std;
int main() {string s;getline(cin,s);string ans=s;for(int i=0;i<s.length();i++){ans[s.length()-1-i]=s[i];}cout<<ans;
}4.代码题：统计一个字符串中个数最多的字符以及返回个数【中等】
类似于蔚来测开手撕题的7，可以参考蔚来汽车-测开日常实习-部分手撕代码题_蔚来四面手撕代码-CSDN博客
5.手撕代码：最大数组差----还有没有其他方法【中等，没写出来】
左右最值最大差__牛客网 搜了一下 不知道是不是这种，两边各挑最大的数，互减得到最大值。
自己第一遍没写出来，看了题解不由得感叹大佬的强大：
除去首尾，找最大值，对比一下首位哪个小，减去那个小的即可。
class MaxGap
{
public:int findMaxGap(vector<int> A, int n) {int m=-100;for(int i=0;i<n;i++){m=max(m,A[i]);}int min1=min(A[0],A[n-1]);return m-min1;}
};至于其他方法，搜了下有桶排序的思想方法。将数组分成若干个区间（桶），每个桶记录该区间内的最大值和最小值。最后，我们遍历这些桶，计算相邻桶之间的最大差距。
6.代码题：二叉树的最近公共祖先【中等】-不会
. - 力扣（LeetCode）自从大二上完专业课后，再也没有手撕过二叉树……都忘了怎么遍历了，好像是dfs？回头再研究研究吧
class Solution {
public:TreeNode* ans;bool dfs(TreeNode* root, TreeNode* p, TreeNode* q) {if (root == nullptr) return false;bool lson = dfs(root->left, p, q);bool rson = dfs(root->right, p, q);if ((lson && rson) || ((root->val == p->val || root->val == q->val) && (lson || rson))) {ans = root;} return lson || rson || (root->val == p->val || root->val == q->val);}TreeNode* lowestCommonAncestor(TreeNode* root, TreeNode* p, TreeNode* q) {dfs(root, p, q);return ans;}
};7. 手撕 合并重叠区间[中等]-不会
. - 力扣（LeetCode）有大概的思路，但vector的语法不太会写，比如咋合并，push_back到一个新vector里面大概。
看了看题解，重要知识点是ans.back()访问vector的最后一个元素，不知道这个知识点做起来就有点麻烦。
class Solution {
public:vector<vector<int>> merge(vector<vector<int>>& intervals) {if (intervals.size() == 0) {return {};}sort(intervals.begin(), intervals.end());vector<vector<int>> merged;for (int i = 0; i < intervals.size(); ++i) {int L = intervals[i][0], R = intervals[i][1];if (!merged.size() || merged.back()[1] < L) {merged.push_back({L, R});}else {merged.back()[1] = max(merged.back()[1], R);}}return merged;}
};
8. 手撕 最大子数组和[中等]-不会
. - 力扣（LeetCode）一看之前做过，不知道啥时候做得，每次都感觉自己再做就做不出来了……
囧……擦了，之前会做现在不会做了，能感觉是用动归解决，尼玛怎么就忘了呢……看了题解改了半天终于过了，md
class Solution {
public:int maxSubArray(vector<int>& nums) {int max1=-10000000;int dp[100000];dp[0]=nums[0];max1=max(max1,dp[0]);for(int i=1;i<nums.size();i++){dp[i]=max(dp[i-1]+nums[i],nums[i]);max1=max(dp[i],max1);}return max1;}
};还有二分、冒泡等经典问题，这里不再展示。
