字节飞书-测开日常实习-部分手撕代码题

之前的文章提到了一道高频题：最长不重复的字串，用到动态窗口。解法就在之前的文章。这篇文章从牛客上找了一些手撕题，在这里记录分享一下。

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;
    }
};

还有二分、冒泡等经典问题，这里不再展示。