解题思路

这是一个字符串编码问题的优化解法。具体要求：

  1. 编码范围是a~y的25个字母
  2. 编码长度是1到4位
  3. 按字典序排列所有可能的编码
  4. 计算给定编码的索引位置

解决方案：

  1. 预计算每个位置的权重系数：
    • 第一位：
    • 第二位：
    • 第三位：
    • 第四位：
  2. 对每个位置，计算：(字母-'a') * 权重 + 位置修正
  3. 位置修正：除第一位外每个位置都要加1

代码

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

int main() {
    // 预计算的权重数组
    const int weights[] = {16276, 651, 26, 1};
    
    string s;
    cin >> s;
    
    int index = 0;
    for(int i = 0; i < s.length(); i++) {
        // 计算位置修正值
        int correction = (i == 0) ? 0 : 1;
        
        // 计算当前位置的贡献
        index += (s[i] - 'a') * weights[i] + correction;
    }
    
    cout << index << endl;
    return 0;
}

import java.util.Scanner;

public class Main {
    public static void main(String[] args) {
        // 预计算的权重数组
        final int[] weights = {16276, 651, 26, 1};
        
        Scanner sc = new Scanner(System.in);
        String s = sc.next();
        
        int index = 0;
        for(int i = 0; i < s.length(); i++) {
            // 计算位置修正值
            int correction = (i == 0) ? 0 : 1;
            
            // 计算当前位置的贡献
            index += (s.charAt(i) - 'a') * weights[i] + correction;
        }
        
        System.out.println(index);
    }
}

def calculate_index(s: str) -> int:
    # 预计算的权重数组
    weights = [16276, 651, 26, 1]
    
    index = 0
    for i in range(len(s)):
        # 计算位置修正值
        correction = 0 if i == 0 else 1
        
        # 计算当前位置的贡献
        index += (ord(s[i]) - ord('a')) * weights[i] + correction
    
    return index

def main():
    s = input().strip()
    print(calculate_index(s))

if __name__ == "__main__":
    main()

算法及复杂度

  • 算法：预计算 + 线性扫描
  • 时间复杂度： - 为输入字符串的长度（最大为 ）
  • 空间复杂度： - 只需要常数空间存储权重数组