【错题集-编程题】添加字符(字符串)

简介: 【错题集-编程题】添加字符(字符串)

牛客对应题目链接:添加字符_牛客笔试题_牛客网 (nowcoder.com)


一、分析题目

简单的两层 for 循环暴力枚举。


二、代码

//值得学习的代码
#include <iostream>
#include <string>
 
using namespace std;
 
string a, b;
 
int main()
{
    cin >> a >> b;
    int m = a.size(), n = b.size();
    int ret = m;
 
    for(int i = 0; i <= n - m; i++) // 枚举 b 的起始位置
    {
        int tmp = 0;
        for(int j = 0; j < m; j++)
        {
            if(a[j] != b[i + j])
            {
                tmp++;
            }
        }
        ret = min(tmp, ret);
    }
 
    cout << ret << endl;
 
    return 0;
}

三、反思与改进

这道题目的正确思路并不复杂,就是一个简单的两层 for 循环暴力枚举(可以通过题目所给的数据量大胆尝试)。我原先用的是双指针来写这道题目,遇到不同的字符就 diff++,然后指向字符串 b 的指针就往后移动一步(排除头尾两部分),但只能通过 60% 的测试用例,还是想复杂了,其实本质上就是求最大重合字符的个数。

注意:除了短的字符串内部不能更换,两边的都可以添加成重复字符,所以结果就是字符串 a 的长度 - 相同位数,就可以得到不相同的位数了。


相关文章
|
1月前
|
算法 前端开发 数据处理
小白学python-深入解析一位字符判定算法
小白学python-深入解析一位字符判定算法
47 0
|
5月前
|
C语言
C语言学习记录——鹏哥字符分类函数、字符转换函数
C语言学习记录——鹏哥字符分类函数、字符转换函数
852 2
|
6月前
|
C语言
C语言期末习题之统计大写字母,数字和其他字符的个数
C语言期末习题之统计大写字母,数字和其他字符的个数
43 0
|
6月前
|
机器人 Java
每日一刷《剑指offer》字符串篇之第一个只出现一次的字符
每日一刷《剑指offer》字符串篇之第一个只出现一次的字符
70 0
每日一刷《剑指offer》字符串篇之第一个只出现一次的字符
|
6月前
|
Java
每日一刷《剑指offer》字符串篇之正则表达式匹配
每日一刷《剑指offer》字符串篇之正则表达式匹配
72 0
每日一刷《剑指offer》字符串篇之正则表达式匹配
|
算法 搜索推荐 程序员
C语言第十六练——数字组合匹配
C语言第十六练——数字组合匹配
118 0
|
C语言
【c语言】【典例】将字符串中指定字符删除
【c语言】【典例】将字符串中指定字符删除
269 0
|
小程序 C语言
【C】C语言实现数字字母雨小程序
【C】C语言实现数字字母雨小程序
|
C语言
C语言:统计一串字符
题目:输入一行字符,分别统计其中英文字母,空格,数字和其它字符的个数。
88 0