之前的文章提到了一道高频题：最长不重复的字串，用到动态窗口。解法就在之前的文章。这篇文章从牛客上找了一些手撕题，在这里记录分享一下。
1.将给定的字符串中的每个单词的首字母转化为大小字母【简单】
不难 就是考察你记不记得小知识点：
#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"【简单】
又是考察犄角旮旯的知识点，服了
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，可以参考
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.代码题：二叉树的最近公共祖先【中等】-不会
自从大二上完专业课后，再也没有手撕过二叉树……都忘了怎么遍历了，好像是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. 手撕 合并重叠区间[中等]-不会
有大概的思路，但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. 手撕 最大子数组和[中等]-不会
一看之前做过，不知道啥时候做得，每次都感觉自己再做就做不出来了……
囧……擦了，之前会做现在不会做了，能感觉是用动归解决，尼玛怎么就忘了呢……看了题解改了半天终于过了，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;
}
};
还有二分、冒泡等经典问题，这里不再展示。
