Aczy156

Algorithm1.0 字符串基本

[TOC]

字符串基本

数字字符串的排序 (直接用数字排序即可)

https://www.luogu.com.cn/problem/P3955

思路：首先按照长度排序，然后如果长度相等了，在直接字符串比较大小

#include <iostream>
using namespace std;
const int maxn = 1e3+9;
int n, q, l;
string s[maxn], sq;
#include <algorithm>

bool cmp(string s1, string s2) {
    if (s1.length() == s2.length()) return s1 < s2;
    return s1.length() < s2.length();
}

int main() {
    scanf("%d%d", &n, &q);
    for (int i = 1; i <= n; ++i) cin>>s[i];
    sort(s+1, s+1+n, cmp);
    for (int i = 1; i <= q; ++i) {
        cin>>l>>sq;
        int fd = 0;
        for (int j = 1; j <= n; ++j) {
            if (l > s[j].length()) continue;
            else {
                int flag = 1;
                for (int k = 0; k < l; ++k)
                    if (sq[l-k-1] != s[j][s[j].length()-k-1]) {flag = 0;break;}
                if (flag) {fd = 1;cout<<s[j]<<endl;break;}
            }
        }
        if (fd) continue;
        else puts("-1");
    }
    return 0;
}

结合拼接的排序

将字符串进行拼接的操作进行排序，保证按照将拼接之后的字串值最大作为顺序

https://www.luogu.com.cn/problem/P1012

题目大意：给出若干个字符串（长度不等长），要求拼接出一个字符串，这个字符串所代表的数最大。

1、单个字符串和单个字符串之间不好比较，转换成(单个字符串a+单个字符串b)与(单个字符串b+单个字符串a)的比较，这样就方便比较两个字符串拼接顺序，拼接无非就是先a后b或者先b后a，所以这样固定住了。

2、结合sort直接对string strs[maxn];进行排序即可。封装好bool cmp()函数。

#include <iostream>
using namespace std;
int n;
#define maxn 25
string strs[maxn];
#include <algorithm>

bool cmp(string a, string b){
    return a+b > b+a;
}

int main() {
    scanf("%d", &n);
    for (int i = 0; i < n; ++i) cin>>strs[i];
    sort(strs, strs+n, cmp);
    for (int i = 0; i < n; ++i) cout<<strs[i];
    return 0;
}

回文串

题目链接：valid-palindrome

C/C++ - basic

利用toupper()、tolower()转换大小写

bool isPalindrome(string s) {
    // remove invalid char and transform to lower case
    string str = "";
    for(int i = 0; i < s.length(); i++)
        if (s[i] <= 'Z' && s[i] >= 'A' || s[i] <= 'z' && s[i] >= 'a' || s[i] <= '9' && s[i] >= '0')
            str += tolower(s[i]);
    // check 
    int l = str.size();
    for (int i = 0; i < str.length()/2; ++i)
        if (str[i] != str[l-1-i])
            return false;
    return true;
}

C/C++ - 利用字符串函数

isalnum()来check 当前的字符串是否是数字和字母，isalpha()是否是字母、isdigit()是否为数字

bool isPalindrome(string s) {
    // remove invalid char and transform to lower case
    string str = "";
    for(int i = 0; i < s.length(); i++)
        if (isalnum(s[i]))
            str += tolower(s[i]);
    // check 
    int l = str.size();
    for (int i = 0; i < str.length()/2; ++i)
        if (str[i] != str[l-1-i])
            return false;
    return true;
}

C/C++ - 利用string的倒序rbegin()、rend()

原字符串倒转，看是否等于原字符串=>string rev_str(str.rbegin(), str.rend());

string sgood_rev(sgood.rbegin(), sgood.rend());
        return sgood == sgood_rev;

bool isPalindrome(string s) {
    // remove invalid char and transform to lower case
    string str = "";
    for(int i = 0; i < s.length(); i++)
        if (isalnum(s[i]))
            str += tolower(s[i]);
    // check 
    string rev_str(str.rbegin(), str.rend())
    return rev_str == str;
}

Python

思路：

1、用filter(target_char, str)来提取s中所需要的目标字符

2、然后目标字符就是str.isalnum标准字符串中是数字和字母的一个属性中的所有元素，

3、利用lower()来将字符串给转换成小写

4、利用s[::-1]来倒序

bool isPalindrome(string s):
  # remove invalid char and transform to lower case
  s = ''.join(filter(str.isalnum, s)).lower()
  # check
  return s == s[::-1]
Posted on Feb 1, 2021