首页 > 试题广场 >

一种字符串和数字的对应关系

[编程题]一种字符串和数字的对应关系
  • 热度指数:534 时间限制:C/C++ 2秒,其他语言4秒 空间限制:C/C++ 256M,其他语言512M
  • 算法知识视频讲解
一个char类型的数组chs,其中所有的字符都不同。
例如,chs = ['A', 'B', 'C', ... 'Z'],则字符串与整数的对应关系如下:
A,  B...Z, AA, AB... AZ, BA,BB...ZZ, AAA...ZZZ,    AAAA... 
1,  2, .26,27,  28,... 52, 53. 54...702,703... 18278, 18279.
例如,chs=['A','B','C'],则字符串与整数的对应关系如下:
A, B, C, AA, AB...CC, AAA...CCC, AAAA....
1   2  3     4     5    12      13      39        40
给定一个数组chs, 实现根据对应关系完成字符串与整数相互转换的两个函数
[要求]
数字转字符串的复杂度为,字符串转数字的复杂度为

输入描述:
第一行有里两个个整数opt, base, 分别表示问题类型,chs的长度
接下来一行有base个字符表示字符数组chs。
若opt = 1,则下一行有一个整数N,分别表示对应的数字。
若opt = 2,则下一行有一个字符串,表示需要转化为数字的字符数组


输出描述:
若opt=1,输出一个字符串。否则输出一个整数
示例1

输入

1 3 
ABC
42

输出

AAAC
示例2

输入

2 3
ABC 
AAAC

输出

42
示例3

输入

1 3
ABC
36

输出

CBC
示例4

输入

2 3
ABC
CBC

输出

36

备注:
考虑到不同语言的数字运算范围差异,本题的数据范围与算法复杂度无关


保证输入合法 且 输入字符串长度不超过8 且 字符集内字符两两不同 且 均为大写字母
#include <bits/stdc++.h>
using namespace std;

int main(){
    int opt, b, x, y;
    string s, t;
    map<char, int> ch_num;
    char num_ch[9];
    cin>>opt>>b>>s;
    for(int i=0;i<s.length();i++){
        ch_num[s[i]] = (i+1);
        num_ch[(i+1)] = s[i];
    }
    if(opt==1){
        cin>>x;
        string r = "";
        while(x){
            y = x%b;
            if(y==0){
                r = num_ch[b] + r;
                x = x/b-1;
            }else{
                r = num_ch[y] + r;
                x /= b;
            }
        }
        cout<<r<<endl;
    }else if(opt==2){
        cin>>t;
        int sum = 0, w=1;
        for(int i=t.length()-1;i>=0;i--){
            sum += ch_num[t[i]]*w;
            w *= b;
        }
        cout<<sum<<endl;
    }
    return 0;
}

发表于 2020-04-04 00:35:58 回复(0)
k伪进制的转换,k伪进制数用1~k而非0~k-1表示。字符串转数字很容易,直接用k进制转十进制的套路,只是每一位从1开始而不是从0开始。需要说明的是数字转字符串,以题中的36为例:
用ABC三个字母表示,可以将其看作伪3进制,即将36转换为用1~3表示的伪3进制。从低位开始,36可以分1个30出去,还剩下35;可以再分1个31出去,还剩下32;还能再分1个32出去,剩下23。至此,无法再分出33,最高位到2结束。然后从高位2往低位0又重新分配,23可以分出2个32,还剩下5;5可以分出1个31出去,还剩下2,最后分2个30出去。因此从高位到低位依次为1+2,1+1,1+2即323,对应到ABC为CBC。
import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.io.IOException;
import java.util.ArrayList;

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 opt = Integer.parseInt(params[0]), base = Integer.parseInt(params[1]);
        char[] chrs = br.readLine().toCharArray();
        if(opt == 1){
            int num = Integer.parseInt(br.readLine().trim());
            System.out.println(num2word(num, chrs));
        }else{
            String word = br.readLine();
            System.out.println(word2num(word, chrs));
        }
    }
    
    private static String num2word(int num, char[] alphabet) {
        int base = alphabet.length;
        int index = 0;
        int init = 1;
        ArrayList<Integer> list = new ArrayList<>();
        while(num - init > 0){
            list.add(1);
            num -= init;
            init *= base;
        }
        int n = list.size();
        init = (int)Math.pow(base, n - 1);
        for(int i = 0; init > 0; i++, init /= base){
            if(num > init){
                list.set(i, list.get(i) + num / init);
                num -= num / init * init;
            }
        }
        StringBuilder sb = new StringBuilder();
        for(int k = 0; k < list.size(); k++) sb.append((char)(alphabet[0] + list.get(k) - 1));
        return sb.toString();
    }
    
    private static int word2num(String word, char[] alphabet) {
        int n = word.length();
        int p = 1, num = 0, base = alphabet.length;
        for(int i = 0; i < n; i++){
            num += (word.charAt(n - 1 - i) - alphabet[0] + 1) * p;
            p *= base;
        }
        return num;
    }
}

发表于 2021-12-03 14:58:06 回复(0)
没劲的题目
class Question1:
    def solve_mode_1(self, base:int, str_chs:str, num:int) -> str:
        len_res = 1
        while True:
            if num > base ** len_res:
                num -= base ** len_res
                len_res += 1
            else:
                break
        num -= 1  # num -> DEC to base
        res = ''
        bit = 0
        while bit < len_res:
            res += str_chs[num % (base)]
            num = num // base
            bit += 1
        return res[::-1]
    
    def solve_mode_2(self, base:int, str_chs:str, str_input:str) -> int:
        num = 0   # start from 0, n base to DEC
        for bit in range(len(str_input)):
            num += str_chs.find(str_input[::-1][bit]) * base ** bit
        for i in range(len(str_input)):
            num += base ** i
        return num


q = Question1()
        
info = list(map(int, input().split(' ')))
opt = info[0]
base = info[1]
str_chs = input()

if opt == 1:
    num = int(input())
    print(q.solve_mode_1(base, str_chs, num))
else:
    str_input = input()
    print(q.solve_mode_2(base, str_chs, str_input))


发表于 2022-09-14 16:49:53 回复(0)
#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;

int main(int argc, char** argv){
	int opt, base;
	while(cin >> opt >> base){
		string str;
		cin >> str;
		if(opt == 1){
			int num;
			cin >> num;
			int flag = 0;
			int cur;
			string ans = "";
			while(num){
				cur = num % base - flag;
				if(cur <= 0){
					flag = 1;
					ans += str[str.size() - 1 + cur];
				}
				else{
					flag = 0;
					ans += str[cur - 1];
				}
				num = num / base;
			}
			reverse(ans.begin(), ans.end());
			if(flag){
				ans = ans.substr(1);
			}
			cout << ans << endl;
		}
		if(opt == 2){
			string temp;
			cin >> temp;
			reverse(temp.begin(), temp.end());
			int ans = 0;
			int cur = 1;
			for(int i = 0; i < temp.size(); i++){
				ans += cur * (temp[i] - 'A' + 1);
				cur = cur * base;
			}
			cout << ans << endl;
		} 
	} 
	return 0;
}

发表于 2019-09-19 15:47:45 回复(0)