机试day6

首字母大写

首字母大写_牛客题霸_牛客网 (nowcoder.com)

描述

对一个字符串中的所有单词，如果单词的首字母不是大写字母，则把单词的首字母变成大写字母。 在字符串中，单词之间通过空白符分隔，空白符包括：空格(' ')、制表符('t')、回车符('r')、换行符('n')。

输入描述：

输入一行：待处理的字符串（长度小于100）。

输出描述：

可能有多组测试数据，对于每组数据， 输出一行：转换后的字符串。

输入：
if so, you already have a google account. you can sign in on the right.
输出：
If So, You Already Have A Google Account. You Can Sign In On The Right.

思路：设置flag位，初始为1，表示句子首字母得大写；如果碰到空白符（使用isspace判断），则flag置1，否则置0；这样碰到flag=1表明上一个字符位空白符，此字符该大写了

#include <cstdio>
#include <iostream>
#include <string>
#include <cctype>
using namespace std;

int main() {
    string s;
    while (getline(cin ,s)) {
        int flag = 1;
        for (int i = 0; i < s.size(); i++) {
            if (isspace(s[i])) {
                flag = 1;
                printf("%c", s[i]);
            } else {
                if (flag && 'a' <= s[i] && s[i] <= 'z') {
                    printf("%c", s[i] + 'A' - 'a');
                } else {
                    printf("%c", s[i]);
                }
                flag = 0;
            }          
        } 
    }
}

也可以直接toupper转换

浮点数加法

浮点数加法_牛客题霸_牛客网 (nowcoder.com)

描述

求2个浮点数相加的和 题目中输入输出中出现浮点数都有如下的形式： P1P2...Pi.Q1Q2...Qj 对于整数部分，P1P2...Pi是一个非负整数 对于小数部分，Qj不等于0

输入描述：

对于每组案例，每组测试数据占2行，分别是两个加数。

输出描述：

每组案例是n行，每组测试数据有一行输出是相应的和。 输出保证一定是一个小数部分不为0的浮点数

输入：
0.111111111111111111111111111111
0.111111111111111111111111111111
输出：
0.222222222222222222222222222222

思路：难点在于小数点前后位数不同的情况下得补0，因此采用了获取小数点位置，然后分别计算前后带0的数目。选取带0最多的作为标准，少的补0。然后视为字符串一位位相加，如果大于10，则flag置1并加到下一位

#include <iostream>
#include <string>
#include <math.h>
using namespace std;

int main() {
    string a, b;
    while (cin >> a >> b) {
        int pos1 = a.find('.');
        int pos2 = b.find('.');
        int num1 = max(pos1, pos2);
        int num2 = max(a.size()-pos1-1, b.size()-pos2-1);
        a.insert(0, num1-pos1, '0');
        b.insert(0, num1-pos2, '0');
        a.insert(a.size(), num1+num2+1-a.size(), '0');
        b.insert(b.size(), num1+num2+1-b.size(), '0');
        int sum = 0, flag = 0;
        for (int i = a.size() - 1; i >= 0; i--) {
            if (a[i] != '.') {
                sum = (a[i] - '0') + (b[i] - '0') + flag;
                a[i] = sum % 10 + '0';
                flag = sum / 10;
            }          
        }
        cout << a << endl;
    }
}

后缀子串排序

描述

对于一个字符串，将其后缀子串进行排序，例如grain 其子串有： grain rain ain in n 然后对各子串按字典顺序排序，即： ain,grain,in,n,rain

输入描述：

每个案例为一行字符串。

输出描述：

将子串排序输出

输入：
grain
输出：
ain
grain
in
n
rain

思路：使用algorithm库的sort来排序，传入两个字符串比较第一位、第二位直到两个字符不同，返回较小的排前面

#include <iostream>
#include <string>
#include <algorithm>
using namespace std;

bool compare(string x, string y) {
    int i = 0;
    while (1) {
        if (x[i] == y[i]) {
            i++;
            continue;
        } else {
            return x[i] < y[i];
        }
    }
}

int main() {
    string s;
    while (cin >> s) {
        string ss[s.size()];
        for (int i = 0; i < s.size(); i++) {
            ss[i] = s.substr(i, s.size());
        }
        sort(ss, ss+s.size(), compare);
        for (int i = 0; i < s.size(); i++) {
            cout << ss[i] << endl;
        }
    }
}

汗！！！发现不用写compare，sort会自动排序，修改后如下

#include <iostream>
#include <string>
#include <algorithm>
using namespace std;

int main() {
    string s;
    while (cin >> s) {
        string ss[s.size()];
        for (int i = 0; i < s.size(); i++) {
            ss[i] = s.substr(i, s.size());
        }
        sort(ss, ss+s.size());
        for (int i = 0; i < s.size(); i++) {
            cout << ss[i] << endl;
        }
    }
}

字符串变形

字符串变形_牛客题霸_牛客网 (nowcoder.com)

描述

对于一个长度为 n 字符串，我们需要对它做一些变形。

首先这个字符串中包含着一些空格，就像"Hello World"一样，然后我们要做的是把这个字符串中由空格隔开的单词反序，同时反转每个字符的大小写。

比如"Hello World"变形后就变成了"wORLD hELLO"。

数据范围: $1\le n\le 10^6$ , 字符串中包括大写英文字母、小写英文字母、空格。

进阶：空间复杂度 $O(n)$ ， 时间复杂度 $O(n)$

输入描述：

给定一个字符串s以及它的长度n(1 ≤ n ≤ 10^6)

返回值描述：

请返回变形后的字符串。题目保证给定的字符串均由大小写字母和空格构成。

输入：
"This is a sample",16
返回值：
"SAMPLE A IS tHIS"
输入：
"nowcoder",8
返回值：
"NOWCODER"

法1：先大小写转换，再逆向整个，最后逆向单词

思路：可以设置一个reverse函数用来反转一个单词/句子，对于如何根据空格划分单词，使用start接收一个单词开始位置，碰到空格记录i，即可截取句子中的单词（注意，最后一个单词需要判断是否到结尾，再起一个分支来处理）

#include <cctype>
#include <string>

string reverse(string s) {
    char c;
    for (int i = 0, j = s.size() - 1; i < j; i++, j--) {
        c = s[i];
        s[i] = s[j];
        s[j] = c;
    }
    return s;
}

class Solution {
  public:
    string trans(string s, int n) {
        for (int i = 0; i < n; i++) {
            if (isupper(s[i])) {
                s[i] = tolower(s[i]);
            } else if (islower(s[i])) {
                s[i] = toupper(s[i]);
            }
        }
        s = reverse(s);
        int start = 0;
        string new_s;
        for (int i = 0; i < n; i++) {
            if (isspace(s[i])) {
                new_s = reverse(s.substr(start, i - start));
                s.erase(start, i - start);
                s.insert(start, new_s);
                start = i + 1;
            } else if (i == n - 1) {
                new_s = reverse(s.substr(start, i + 1 - start));
                s.erase(start, i + 1 - start);
                s.insert(start, new_s);
            }
        }
        return s;
    }
};

其中reverse函数可以由algorithm的reverse替换

ps：经法2启发，在结尾加个空格会更简单

class Solution {
  public:
    string trans(string s, int n) {
        for (int i = 0; i < n; i++) {
            if (isupper(s[i])) {
                s[i] = tolower(s[i]);
            } else if (islower(s[i])) {
                s[i] = toupper(s[i]);
            }
        }
        s = reverse(s);
        s += ' ';
        int start = 0;
        string new_s;
        for (int i = 0; i < n + 1; i++) {
            if (isspace(s[i])) {
                new_s = reverse(s.substr(start, i - start));
                s.erase(start, i - start);
                s.insert(start, new_s);
                start = i + 1;
            }
        }
        s.erase(n, 1);
        return s;
    }
};

法2：栈！

思路：

  1. 使用栈stack，定义数据类型为string
  2. 使用str接收每个单词，同时s后加一个空格好判断
  3. 栈先入后出，因此可以实现句子单词逆序，而不需要反转单词本身，快了很多
#include <cctype>

class Solution {
  public:
    string trans(string s, int n) {
        stack<string> sk;
        string str;
        s.push_back(' ');    // s后加空格
        for (int i = 0; i <= n; i++) {
            if (s[i] == ' ') {
                sk.push(str);
                str = "";
            } else {
                if (s[i] >= 'a' && s[i] <= 'z') {
                    str += (s[i] - 'a' + 'A');
                } else {
                    str += (s[i] - 'A' + 'a');
                }
            }
        }
        string ans;
        while (!sk.empty()) {
            ans += sk.top();    // 取栈顶值
            sk.pop();            // 弹出栈顶
            ans.push_back(' '); // 加空格
        }
        ans.pop_back();    // 去除最后的空格
        return ans;
    }
};

法3：超级无敌改进法1

思路：就是reverse，使用官方库好了，甚至不需要加空格，以及不需要开辟新空间接收反转的字符串

#include <cctype>

class Solution {
  public:
    string trans(string s, int n) {
        reverse(s.begin(), s.end());
        int i = 0, j = 0;
        while (i < n) {
            j = i;
            while (j < n && s[j] != ' ') {
                if (isupper(s[j])) {
                    s[j] = tolower(s[j]);
                } else if (islower(s[j])) {
                    s[j] = toupper(s[j]);
                }
                j++;
            }
            reverse(s.begin() + i, s.begin() + j);
            i = j + 1;
        }
        return s;
    }
};

最长公共前缀

描述

给你一个大小为 n 的字符串数组 strs ，其中包含n个字符串 , 编写一个函数来查找字符串数组中的最长公共前缀，返回这个公共前缀。

数据范围： $0\le n\le 5000$， $0\le len(strs_i)\le 5000$

进阶：空间复杂度 $O(1)$，时间复杂度 $O(n∗len)$

输入：
["abca","abc","abca","abc","abcc"]
返回值：
"abc"
输入：
["abc"]
返回值：
"abc"

思路：以第一个作为参照一个个比

class Solution {
public:
    /**
     * 
     * @param strs string字符串vector 
     * @return string字符串
     */
    string longestCommonPrefix(vector<string>& strs) {
        string s;
        if (!strs.size())
            return "";
        for (int i = strs[0].size(); i >= 0; i--) {
            int flag = 0;
            for (int j = 0; j < strs.size(); j++) {
                if (i > strs[j].size() || strs[0].substr(0, i) != strs[j].substr(0, i)) {
                    flag = 0;
                    break;
                } else {
                    flag = 1;
                }
            }
            if (flag)
                return strs[0].substr(0, i);
        }
        return "";
    }
};

nice！看了下和官方思路差不多，大多数思路差不多

最后修改：2023 年 06 月 04 日
© 允许规范转载
如果觉得我的文章对你有用，请随意赞赏