首页 > 试题广场 >

编码

[编程题]编码
  • 热度指数：19428 时间限制：C/C++ 1秒，其他语言2秒 空间限制：C/C++ 32M，其他语言64M
  • 算法知识视频讲解
假定一种编码的编码范围是a ~ y的25个字母，从1位到4位的编码，如果我们把该编码按字典序排序，形成一个数组如下： a, aa, aaa, aaaa, aaab, aaac, … …, b, ba, baa, baaa, baab, baac … …, yyyw, yyyx, yyyy 其中a的Index为0，aa的Index为1，aaa的Index为2，以此类推。 编写一个函数，输入是任意一个编码，输出这个编码对应的Index.

输入描述:
输入一个待编码的字符串,字符串长度小于等于100.


输出描述:
输出这个编码的index
示例1

输入

baca

输出

16331
算法知识视频讲解
添加回答
Java
黄小斜头像 黄小斜 
参考最高赞
import java.util.Scanner;
public class Main{
    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);
        String str = scanner.nextLine();
        System.out.println(encode(str));
    }
    public static int encode(String str) {
        if (str.equals("a")) {
            return 0;
        }
        if (str.equals("aa")) {
            return 1;
        }
        if (str.equals("aaa")) {
            return 2;
        }
        if (str.equals("aaaa")) {
            return 3;
        }

        int res = 0;
        int one,two,three,four;
        int mod = 25;
        one = mod * mod * mod + mod * mod + mod + 1;
        two = mod * mod + mod + 1;
        three = mod + 1;
        four = 1;
        int []arr = new int[4];
        arr[0] = one;
        arr[1] = two;
        arr[2] = three;
        arr[3] = four;

        int i = 1;
        while (i <= str.length()) {
            int cnt = Integer.parseInt(String.valueOf(str.charAt(i - 1) - 'a'));
            if (i == 1) {
                res += cnt * arr[i - 1];
            }else {
                //此处加一是因为，a = 0,aa = 1，所以除了第一位每一位都要加1
                res += cnt * arr[i - 1] + 1;
            }
            i ++;
        }
        return res;
    }
}

发表于 2018-06-05 22:04:26 回复(0)
更多回答
C/C++
卷积神经网络哦头像 卷积神经网络哦

代码很简洁 就是思路不好想 参考一楼的思路 

#include <iostream>
#include <string>
using namespace std;
const int arr[] = {16276, 651, 26, 1};
int main(){
    string s;
    cin>>s;
    int ans = 0;
    for(int i = 0; i < s.length(); i++){
        int if_1 = 1;
        if(i == 0) if_1 = 0;
        ans += (s[i]-'a') * arr[i] + if_1;
    }
    printf("%d\n", ans);
    return 0;
}
编辑于 2018-09-18 21:17:23 回复(0)
TX游戏客户端开发内推头像 TX游戏客户端开发内推

分析

举例：cbd
由于是从1到4位的编码，分析如下：
一位的情况：c-a+1
二位的情况：(c-a)*25+(b-a)+1
三位的情况：(c-a)*25*25+(b-a)*25+(d-a) 此处不用+1，因为编码从0开始，且也刚好不能取cbd
四位的情况：三位的数量*25:(c-a)*25*25*25+(b-a)*25*25+(d-a)*25
最后的编码就是上面四种情况的总数，通项已经被推出：
temp=temp*25+(str[i]-'a');由于该例子是3位的，所以一位和二位的情况，需要在末尾+1
用中间变量temp存储中间数据，可提高性能

所用数据结构： string 
#include <iostream>
#include <algorithm>
using namespace std;
int main()
{
    string str;
    while(cin>>str)
    {
        int strLength=str.length();
        int index=0;
        int temp=0;
        for(int i=0;i<strLength;++i)
        {
            temp=temp*25+(str[i]-'a');
            if(i<strLength-1)
                index+=temp+1;
            else
                index+=temp;
        }
        for(int i=strLength;i<4;++i)
        {
            temp=temp*25;
            index+=temp;
        }
        cout<<index<<endl;
    }
    return 0;
}

编辑于 2018-01-02 17:02:53 回复(0)
元气の悟空头像 元气の悟空 
//AC代码：
#include<string>
#include<vector>
#include<iostream>
#include<algorithm>
using namespace std;
string s="";
vector<string> d;
void dfs(int step){
    if(step>=4) return;
    else
        for(int i=0;i<25;i++){
            string tmp=s;
            char t='a'+i;
            s+=t,d.push_back(s);
            dfs(step+1),s=tmp;
        }
}
int main(){
    dfs(0);
    cin>>s;
    int w=lower_bound(d.begin(),d.end(),s)-d.begin();
    printf("%d\n",w>=d.size()?-1:w);
}//用dfs把所有的串打个表，再二分去搜

编辑于 2017-10-22 18:52:55 回复(1)
Java
编程卖土豆头像 编程卖土豆

import java.util.Scanner;
public class Main {
    public static void main(String[] args) {
        Scanner in = new Scanner(System.in);
        String b = in.next();
        int res = codeindex(b);
        System.out.println(res);
    }

    public static int codeindex(String code) {
        int factor[] = {1+25+25*25+25*25*25, 1+25+25*25, 1+25, 1};
        char[] codearr = code.toCharArray();
        int index = 0;
        int len = 0;
        for(int i = 0;i < codearr.length; i++){
            index += factor[len++] * (codearr[i] - 'a');
        }
        return index + (len - 1);
    }
}
发表于 2017-06-25 20:55:28 回复(0)
DevilyrCyaM头像 DevilyrCyaM
坑啊，做了半天发现是25个字母不是26的举个手
发表于 2017-06-26 10:06:15 回复(4)
whisky_头像 whisky_ 
//一个递归
#include<iostream>
#include<string>
#include<math.h>
using namespace std;
int nums_less_than(string s, int digits){
    if(s.size()==1&&digits==1)
        returns[0]-'a';
    if(s.size()==1&&digits>1)
        return(s[0]-'a')*pow(25, digits-1);
    if(s.size()>1&&digits==1)
        returns[0]-'a'+1;
    return (s[0]-'a')*pow(25, digits-1)+nums_less_than(s.substr(1), digits-1);
}
int main(){
    string s;
    int index=0;
    cin>>s;
    for(int i=1;i<=4;)
        index+=nums_less_than(s, i++);
    cout<<index;
    return 0;
}

编辑于 2017-06-23 20:31:00 回复(1)
rs勿忘初心头像 rs勿忘初心
http://blog.csdn.net/sinat_33718563/article/details/77170549
发表于 2017-08-14 22:02:45 回复(0)
念辰六头像 念辰六 
s = list(input())
dic = dict(zip(list("abcdefghijklmnopqrstuvwxy"), range(25)))
n = len(s)
index = n - 1
try:
    index += dic[s[0]] + dic[s[0]] * 25 + dic[s[0]] * 25 ** 2 + dic[s[0]] * 25 ** 3
    index += dic[s[1]] + dic[s[1]] * 25 + dic[s[1]] * 25 ** 2
    index += dic[s[2]] + dic[s[2]] * 25
    index += dic[s[3]]
except IndexError:
    pass
print(index)
思路很简单，假设第一个字母是c，所有只要计算所有c前面字母为第一位，也就是a或b为第一位的，长度为1、2、3、4的字符串
若第二个字母是d，就在上一步的基础上，再加上所有d前面字母为第一位，长度为1、2、3的字符串
以此类推
这样会漏掉长度-1个字符，再加回去就可以了
发表于 2019-09-20 02:56:57 回复(0)
Victor201808031155173头像 Victor201808031155173
s=input()
# tree=[]
count=0
fori inrange(25):
    str=chr(97+i)
    # tree.append(str)
    if(str==s):
        print(count)
    count+=1
    forj inrange(25):
        str=chr(97+i)+chr(97+j)
        # tree.append(str)
        if(str==s):
            print(count)
        count +=1
        fork inrange(25):
            str=chr(97+i) +chr(97+j)+chr(97+k)
            # tree.append(str)
            if(str==s):
                print(count)
            count +=1
            fory inrange(25):
                str=chr(97+i) +chr(97+j) +chr(97+k) +chr(97+y)
                # tree.append(str)
                if(str==s):
                    print(count) 
                count +=1

发表于 2019-04-06 20:30:42 回复(0)
2019眷顾我头像 2019眷顾我 
#include <iostream>
#include <math.h>
using namespace std;
int main(){
    string s;
    while(cin>>s){
        int result=0;
        for(int i=0;i<s.size();i++){
            int temp=s[i]-'a';
            int cnt=i;
            while(cnt<4){
                result+=pow(25,3-cnt)*temp;
                cnt++;
            }
        }
        // cout<<result<<endl;
        result+=s.size()-1;
        cout<<result<<endl;
    }
    return 0;
}
发表于 2018-10-11 12:23:43 回复(0)
米缸没米了头像 米缸没米了 
我以为考的是 字符组合问题呢？字符组合的答案如下。
#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
class Solution {
private:
    vector<string> res;
    void generatePermutation(const vector<string>& nums, int index,int val, string s1){

        if(index == val){
            res.push_back(s1);
            return;
        }
        for(int i = 0 ; i < nums.size() ; i ++)
        {
            s1 += nums[i];
            generatePermutation(nums, index + 1, val,s1);
            s1.pop_back();
        }
        return;
    }
public:
    vector<string> permute(vector<string>& nums,int val) {
        res.clear();
        generatePermutation(nums, 0, val,"");
        return res;
    }
};

int main() {
    vector<string> base{"a","b","c","d","e","f","g","h","i",
                        "j","k","l","m","n","o","p","q","r",
                        "s","t","u","v","w","x","y"};
    vector<string> ans;
    for(int i = 1;i <= 4;i++){
        vector<string> res = Solution().permute(base,i);
        ans.insert(ans.end(),res.begin(),res.end());
    }
    sort(ans.begin(),ans.end());
    string s1;
    cin>>s1;
    for(int i = 0;i < ans.size();i++){
        if(ans[i] == s1)
            cout<<i<<endl;
    }
    return 0;
}


发表于 2018-08-11 14:15:18 回复(0)
乌邦图头像 乌邦图 
/* AC 代码，+1主要考虑第二、三、四位可能没有字符的情况，25代表这一位可能取的情况有25种*/
#include<iostream>
#include<string>
using namespace std;
int main()
{
      string str;
      cin>>str;
      int len=str.size(),num=0;
      if(len>=1)
         num += (str[0] - 'a')*(1 + 25 * (1 + 25 * ( 1 + 25)));
     if(len>=2)
         num += (str[1] - 'a')*(1 + 25 * (1 + 25)) + 1;
      if(len>=3)
          num += (str[2] - 'a')*(1 + 25) + 1;
      if(len>=4)
          num += str[3] - 'a' + 1;
      cout << num << endl;
      return 0;
}

发表于 2018-04-03 15:36:52 回复(0)
星星的小孩头像 星星的小孩

import java.util.*;

public class Main {
    public static void main(String[] args) {
        Scanner in =  new Scanner(System.in);
        StringBuilder sb = new StringBuilder();
        String s =in.nextLine();
        int result = 0;
        for(int i = 0; i < s.length(); i++) {
            int x = s.charAt(i) - 'a';
            int y = 0;
            for(int j = i ; j < 4 ; j++)
                y += (int)Math.pow(25, 4- 1 - j);
            result += (x * y) + 1;
        }
        System.out.println(result - 1);
    }

}

发表于 2018-03-27 17:13:12 回复(0)
C/C++
nbgao头像 nbgao 
#include <iostream>
#include <cmath>
using namespace std;

int main()
{     string s;     cin>>s;     int l = s.length();     int index = l-1;     for(int i=0;i<4;i++)     {         int x = s[i]-'a';         if(x>0)             for(int j=0;j<4-i;j++)                 index += x*pow(25,j);     }     cout<<index<<endl;     return 0;
}

发表于 2018-01-13 01:06:29 回复(0)
C/C++
邹金标头像 邹金标
#include<stdio.h>
#include<string.h>
#include<math.h>
//#define N 100
int main()
{
char A[100];
int i,index=0;
scanf("%s",A);
int len;
len = strlen(A);
for(i=0;i<len;i++)
{
index+=(A[i]-'a')*(pow(25,4-i)-1)/24;
}
index+=len-1;
printf("%d",index);
return 0;
}
编辑于 2018-01-04 10:24:52 回复(0)
C/C++
卡玛酱头像 卡玛酱 
#include <iostream>
#include <string>
#include <cmath>
using namespace std;
inline int p(int n){     long rsl=0;int base=25;     while(n>=0){         rsl+=pow(base,n);         n--;     }     return rsl;
}
int main(){
    string s;     int weight[4]={p(3),p(2),p(1),p(0)};
    while(cin>>s){         string::iterator it;         int* p=weight;         long idx=0;         for(it=s.begin();it!=s.end();++it){             idx+=((int)(*it)-(int)'a')*(*p);             if(it!=s.begin()) idx++;             p++;         }         cout<<idx<<endl;
    }
    return 0;
}

发表于 2017-09-21 21:45:20 回复(0)
usosst头像 usosst
看见题目说字符串长度不超过100，还以为是求任意长度 
char s[105];

scanf("%s", s); int n = strlen(s);
long long ans = n - 1;
n = 4;  // 没有这一句就是对任意长度的编码求index
for (int i = 0; i < n; ++i) {
	int x = s[i] - 'a';
	if (x > 0) {
		for (int j = 0; j < n - i; ++j)
			ans += x * pow(25, j);
	}
}
cout << ans << endl;

编辑于 2017-08-30 12:34:41 回复(0)
niutor头像 niutor 
#include <iostream>
#include <cstring>

int main() {
	char buf[101];
	scanf("%s", buf);
	int len = strlen(buf);
	int h = 0;
	while (len < 4) {
		buf[len] = 'a';
		++len;
		++h;
	}
	int index = 0;
	int help[4] = {1, 26, 651, 16276};
	for (int i = 0; i < len; ++i) {
		index += (buf[i] - 'a') * help[len-1-i] + 1;
	}
	std::cout << index-1-h;
}
发表于 2017-08-28 10:46:11 回复(0)
夕一啊头像 夕一啊
题目还是有依据的：
五笔的编码范围是a到y的25个字母，从1位到4位的编码，
如果将五笔的编码按字典序排序，形成数组如下：a, aa, aaa, aaaa, aaab, aaac, ..., b, ba, baa, baaa, baab...yyyx, yyyy
-------------
不过还是有些难懂，这个字典序
首先可以分成25个大块，每块是以字母a-y开头（不是x是叉，代表空，不满四个字符）

第一大块包含多少个呢？如果长度是4，说明都不包含空（x）第一位已经确定，就是a还有三位可选（选25个字母之一），就是25*25*25，长度是3说明有一个空，25*25,长度为2，两个空只剩一个位置可以是25个字母中任意一个，25，长度是1，那就只有a自己了。所以一共是  25^3+25^2+25+1
--------
例：bcd
第一位是b所以处在第二大块，result += 1 *  (25^3+25^2+25+1) 
第二位是c， result += 2 *（25^2+25+1）+1
第三位是d， result += 3* （25+1）+1  （加一是因为最前面有个空）
第四位是空，不管，因为空就是第一个
result = 17658
--------
例：defc
第一位是d所以处在第四大块，result += 3 *  (25^3+25^2+25+1) 
第二位是e， result += 4 *（25^2+25+1）+1
第三位是 f， result += 5* （25+1）+1
第四位是c， result += 2* （1）+1
result = 51567
编辑于 2017-07-25 09:56:47 回复(27)
forevergorilla头像 forevergorilla 

	importjava.util.*;





	publicclassMain{





	        publicstaticvoidmain(String[] args) {





	        Scanner scanner = newScanner(System.in);





	        while(scanner.hasNext()) {





	            String string = scanner.nextLine();





	            String alphabet = "abcdefghijklmnopqrstuvwxy";





	            TreeMap<String, Object> map = newTreeMap<String, Object>();





	            // 1位的





	            for(inti = 0; i < alphabet.length(); i++) {





	                map.put(String.valueOf(alphabet.charAt(i)), 0);





	            }





	            // 2位的





	            for(inti = 0; i < alphabet.length(); i++) {





	                for(intj = 0; j < alphabet.length(); j++) {





	                    map.put(String.valueOf(alphabet.charAt(i)) + String.valueOf(alphabet.charAt(j)), 0);





	                }





	            }





	            // 3位的





	            for(inti = 0; i < alphabet.length(); i++) {





	                for(intj = 0; j < alphabet.length(); j++) {





	                    for(intm = 0; m < alphabet.length(); m++) {





	                    map.put(String.valueOf(alphabet.charAt(i)) + String.valueOf(alphabet.charAt(j))+String.valueOf(alphabet.charAt(m)), 0);





	                    }





	                }





	            }





	            // 4位的





	            for(inti = 0; i < alphabet.length(); i++) {





	                for(intj = 0; j < alphabet.length(); j++) {





	                    for(intm = 0; m < alphabet.length(); m++) {





	                        for(intn = 0; n < alphabet.length(); n++) {





	                    map.put(String.valueOf(alphabet.charAt(i)) + String.valueOf(alphabet.charAt(j))+String.valueOf(alphabet.charAt(m))+String.valueOf(alphabet.charAt(n)), 0);





	                        }





	                    }





	                }





	            }





	            Object[] objects=map.keySet().toArray();





	            for(inti=0;i<objects.length;i++)





	            {





	                if(string.equals(objects[i]))System.out.println(i);





	            }





	        }





	    }





	}
这个题是不是没做时间限制啊？我本来以为过不了的居然过了= =
啥都懒得考虑直接全部遍历出来扔到TreeMap里面去。keyset就是字典排序好了的
然后遍历找到是第几个= =投机取巧了
发表于 2019-07-09 21:03:57 回复(0)
提交观点

问题信息

C++工程师 golang工程师 2017 iOS工程师 安卓工程师 字符串 运维工程师 前端工程师 算法工程师 测试工程师 PHP工程师 腾讯 模拟 Java工程师
难度：
135条回答 27470浏览

热门推荐

通过挑战的用户

查看代码

相关试题

编码

扫一扫，把题目装进口袋

求职之前，先上牛客

扫描二维码，进入QQ群

扫描二维码，关注牛客公众号