首页 > 试题广场 >

找到指定类型的新类型字符

[编程题]找到指定类型的新类型字符
  • 热度指数:1439 时间限制:C/C++ 2秒,其他语言4秒 空间限制:C/C++ 256M,其他语言512M
  • 算法知识视频讲解
      新类型字符的定义如下:
      1.新类型字符是长度为1或者2的字符串。
      2. 表现形式可以仅是小写字母,例如,"e"; 也可以是大写字母+小写字母,例如,"Ab";还可以是大写字母+大写字母,例如,"DC"。
      现在给定一个字符串str, str 一定是若干新类型字符 正确组合的结果。比如"eaCCBi",由新类型字符"e"、"a”、"CC"和"Bi"拼成。 再给定一个整数k,代表str中的位置。请返回第k个位置的新类型字符。


输入描述:
输入包含两行,第一行两个整数n,kn代表字符串str的长度,第二行包含一个字符串,代表字符串str。


输出描述:
输出包含一个被k位置指定的新型字符。
示例1

输入

11 7
aaABCDEcBCg

输出

Ec

备注:
时间复杂度,空间复杂度
#include <stdio.h>
#include <ctype.h>

int main(void) {
    int n, k, upper_num = 0;
    char *str;
    scanf("%d%d", &n, &k);
    str = (char *) malloc(n + 1);
    scanf("%s", str);
    for (int i = k - 1; i >= 0; i--) {
        if (islower(str[i])) {
            break;
        }
        upper_num++;
    }
    if (upper_num & 1 == 1) {
        printf("%c%c\n", str[k - 1], str[k]);
    } else if (isupper(str[k])) {
        printf("%c%c\n", str[k], str[k + 1]);
    } else {
        printf("%c\n", str[k]);
    }
    free(str);
    return 0;
}

发表于 2022-02-11 21:32:46 回复(0)
时间复杂度O(1)是均摊的吗?一看到O(1)还以为能直接定位出来。先遍历字符串,遇到小写字母指针走一步(因为新型字符开头为小写时仅有小写字母组成),遇到大写字母走两步,直到指针到达或超过k。此时指针永远指向某个新型字符串的开头,而由于只有走一步或两步的情况,因此超过k的情况只可能是k+1。 
根据指针最后到达的位置分情况输出就行:
1.如果指针指向k+1,则应该输出上一个新型字符串;
2.如果指针指向k,则有两种情况
(1)如果当前为小写字符,则输出这个小写字母即可;
(2)否则输出当前大写字符和下一个大写字符。
import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.io.IOException;

public class Main {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        String[] params = br.readLine().split(" ");
        int n = Integer.parseInt(params[0]), k = Integer.parseInt(params[1]);
        String str = br.readLine().trim();
        int idx = 0;
        while(idx < k){
            char c = str.charAt(idx);
            if(c >= 'a' && c <= 'z')
                idx ++;
            else
                idx += 2;
        }
        if(idx == k + 1){
            System.out.println(str.substring(k - 1, k + 1));
            return;
        }
        char c = str.charAt(k);
        if(idx == k && c >= 'a' && c <= 'z'){
            System.out.println(str.substring(k, k + 1));
            return;
        }else{
            System.out.println(str.substring(k, k + 2));
            return;
        }
    }
}
除此之外还可以用贪婪匹配模式下的正则来做,不过时间和空间复杂度比这个高,但刚好可以把字符串按新型字符串分割成列表,比较清晰。
import re

n, k = map(int, input().split())
string = input().strip()
match_str = re.findall("(?:[a-z]|[A-Z][A-Z]|[A-Z][a-z])", string)
cal_len = 0
for substr in match_str:
    substr_len = len(substr)
    if cal_len + substr_len - 1 < k:
        cal_len += substr_len
    else:
        print(substr)
        break

发表于 2021-06-30 11:47:51 回复(0)
#include <bits/stdc++.h>
using namespace std;

int main(){
    int n, k;
    string s;
    cin>>n>>k>>s;
    for(int i=0;i<=k;){
        if(islower(s[i])){
            if(i==k)
                cout<<s[i]<<endl;
            i++;
        }else if(isupper(s[i])){
            if(i==k || i==k-1)
                cout<<s[i]<<s[i+1]<<endl;
            i += 2;
        }
    }
    return 0;
}

发表于 2020-05-14 08:26:21 回复(0)
#include<bits/stdc++.h>
using namespace std;

const int maxn = 100010;
int main(){
    int len, k;
    //char str[maxn];
    string str;
    while(cin>>len>>k>>str){
        //gets(str);
        int nums = 0;
        for(int j = k - 1; j >= 0; j--){
            if(isupper(str[j]))
                nums++;
            else
                break;
        }
        if(nums & 1 == 1)
        {
            cout<<str.substr(k-1,2);
                continue;
        }
        
        if(isupper(str[k])){
            cout<<str.substr(k,2);
        }
        else{
            cout<<str.substr(k,1);
        }
    }
    return 0;
}

发表于 2020-04-26 00:57:23 回复(1)
1. 题目描述到小写字母要么单独存在,要么得跟在大写字母后面,可以推断,只要遍历到小写字母,str[0, i]自身是完整的,只需关注下标i的后续就行
2. 题目要求下标k,从下标k-1往左走,一旦遇到小写字母就停止,统计期间有多少个大写字母。此时可以理解为" str[0,i]是完整的忽略掉,str[i+1, k-1]中全为大写字母"
3. 题目描述到大写字母必须组合存在,因此如果是统计的大写字母个数是奇数,则最后的一个大写字母(下标k-1)必须得跟下标k的字母组合,不管下标k是大写还是小写。
4. 如果统计的大写字母个数是偶数,则自个已经组合完毕了,此时忽略掉,只关注下标k的字母是大写还是小写,小写则单独输出,大写则必须跟k+1下标的字母组合输出。
#include <stdio.h>
#include <string>
#include <assert.h>
using namespace std;

inline bool isSmallLetter(const char c)
{
    return c <= 'z' && c >= 'a';
}

inline bool isOdd(const int num)
{
    return num % 2 == 1;
}

string func(const string& str, const int k)
{
    if(k >= str.size())  assert(false);
    int capitalNum = 0;
    for(int i=k-1; i>=0; i--)
    {
        if(isSmallLetter(str[i]))  break;
        capitalNum++;
    }
    if(isOdd(capitalNum))  return str.substr(k-1, 2);
    if(!isSmallLetter(str[k]))  return str.substr(k, 2);
    return string(1, str[k]);
}

int main()
{
    int strLen, k;
    scanf("%d %d", &strLen, &k);
    char str[strLen+1];
    scanf("%s", str);
    printf("%s", func(str, k).c_str());
    return 0;
}


发表于 2023-08-10 14:44:07 回复(0)
import java.util.*;

public class Main{
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt();
        int k = sc.nextInt();
        sc.nextLine();
        String s = sc.nextLine();
      //  System.out.println(findSubString(s, k));
        System.out.println(findSub2(s, k));
    }
    
    //笨方法
    public static String findSubString(String s, int k) {
        if (s == null || s.length() == 0 || k < 0 || k >= s.length())
            return null;
        char[] res = new char[2];
        int i = 0;
        while (i < s.length()) {
            res = new char[2];
            if (s.charAt(i) >= 'a' && s.charAt(i) <= 'z') {
                res[0] = s.charAt(i);
                i++;
            }
            else {
                res[0] = s.charAt(i);
                res[1] = s.charAt(i+1);
                i+=2;
            }
            if (i > k)
                break;
        }
        return res[1] == '\u0000' ? String.valueOf(res[0]) : String.valueOf(res);
    }
    
    //从k-1位置向左统计左边有几个大写字母,为奇数个时,返回str[k-1...k]
    //为偶数时,若当前str[k]为大写字母,返回str[k...k+1]; 小写则返回str[k]
    public static String findSub2(String s, int k) {
        if (s == null || s.length() == 0 || k < 0 || k >= s.length())
            return null;
        int count = 0;
        char[] res = new char[2];
        for (int i = k-1; i >= 0 && s.charAt(i) >= 'A' && s.charAt(i) <= 'Z'; i--) {
            count++;
        }
        if (count % 2 != 0) {
            res[0] = s.charAt(k-1);
            res[1] = s.charAt(k);
            return String.valueOf(res);
        }
        else {
            if (s.charAt(k) >= 'A' && s.charAt(k) <= 'Z') {
                res[0] = s.charAt(k);
                res[1] = s.charAt(k+1);
                return String.valueOf(res);
            }
            else
                return String.valueOf(s.charAt(k));
        }
    }
}

发表于 2021-08-02 15:39:44 回复(0)
void findNewTypeChar(const string& s, int k) {
    if (k >= s.size()) 
        return;
    // 题目定义,新类型字符若包含大写,长度必为2,且字串一定以大写为开头
    // 目标:计算在位置k之前有多少个大写字符
    int i = k-1;
    // 从k往前推算,在遇到第一个小写字母之前,有奇数个大写字母,那麽s[k]必须补上,所以回传s[k-1..k]
    // 若有偶数个大写字母,则检查s[k]是小写还是大写,大写开头则回传字串长度为2的子字串,小写开头就回传长度为1的子字串
    while (i >= 0 && isupper(s[i--]));
    int upper_len = k-i-2;
    if (upper_len % 2) {
        cout << s.substr(k-1, 2) << endl;
    }
    else {
        cout << (!isupper(s[k]) ? s.substr(k, 1) : s.substr(k, 2)) << endl;
    }
}
编辑于 2021-03-13 17:08:45 回复(0)
#include<cstdio>
char str[100010];
int main(){
    int n,k;
    while(~scanf("%d %d",&n,&k)){
        int i=0;
        scanf("%s",str);
        while(i<=k){
            if(str[i]>='a'&&str[i]<='z'){
                if(i==k)
                    printf("%c\n",str[i]);
                i++;
            }
            else if(str[i]>='A'&&str[i]<='Z'){
                if(i==k-1||i==k){
                    printf("%c%c\n",str[i],str[i+1]);
                }
                i=i+2;
            }
        }
    }
    return 0;
}

发表于 2020-04-09 17:36:06 回复(0)
import sys
l , k = sys.stdin.readline().split(" ")
k = int(k)
input_str = sys.stdin.readline()
i = 0
while True:
    if 65 <= ord(input_str[i]) <= 90 :
        if i == k - 1:
            print(input_str[k-1:k+1])
            break
        elif i == k:
            print(input_str[k:k+2])
            break
        i += 2
        
    else:
        if i == k:
            print(input_str[k])
            break
        i += 1

发表于 2020-03-05 01:46:38 回复(0)
这个代码是不是有点错误? 原题的话,第6个位置上应该是CD,但是这个代码的结果是Ec
发表于 2020-03-02 20:12:20 回复(1)

问题信息

上传者:小小
难度:
10条回答 3533浏览

热门推荐

通过挑战的用户

查看代码