【算法】【算法杂谈】一种字符串和数字的对应关系

前言

当前所有算法都使用测试用例运行过，但是不保证100%的测试用例，如果存在问题务必联系批评指正~

在此感谢左大神让我对算法有了新的感悟认识！

问题介绍

原问题
给定字符串chars = [A,B…,Z],定义一个字符串和数字之间的关系
A, B, C, D…Z, AA, AB,…,AZ,BA, BB,BC,…BZ,AAA…ZZZ
1, 2, 3, 4, … 26, 27, 28, …52
问题一：给定一个字符串str，求出该字符串代表的数字
问题二：给定一个数字，求出该数字代表的字符串

解决方案

原问题：
首先该问题通过k进制数是无法解决的，但是可以收到一些启发，使用伪进制数来解决问题
比如给定的字符集合chars = [A,B,C,D]，那么该字符集合能够做出进制为4的伪进制数，相当于"逢E进一"
因此当给定一个str = BCBD时，求对应的数值，可以从高位开始计算进制转换即可
当给定一个数值时，分以下步骤计算：
1、计算数值需要多少位来存储，通过(数值/k^n)来找到n最大能够取到多少？
2、求出位数，后面循环填充每一位的数值即可，从高位开始计算，具体看代码

代码编写

java语言版本

原问题：
方法一：

    /*** 二轮测试：给定num，获取String的值* @param num* @return*/public static String num2StringCp1(int num, char[] chars) {if (num < 0 || chars == null || chars.length == 0) {return null;}int len = chars.length;// 先判断需要多少位存储int n = 0;while((int)(num / Math.pow(len, n))!= 0) {n++;}char[] res = new char[n];// 将所有位全部置为Afor (int i = 0; i < res.length; i++) {res[i] = 'A';num -= Math.pow(len, i);}// 此时num剩下的需要进行进制转换,从最高位开始判断for (int i = 0; i < res.length; i++) {int r = (int) (num/Math.pow(len, res.length-1 - i));res[i] += r;num -= r * Math.pow(len, res.length-1 - i);}return String.valueOf(res);}/*** 二轮测试：通过字符串获取num数字* @param str* @param chars* @return*/public static int string2Num(String str, char[] chars) {if (str == null || chars == null|| str.length() == 0 || chars.length == 0) {return 0;}int len = chars.length;char[] chars1 = str.toCharArray();int res = 0;for (int i = 0; i < chars1.length; i++) {int cur = chars1[i] - 'A' + 1;res += cur * Math.pow(len, chars1.length - 1 - i);}return res;}public static void main(String[] args) {System.out.println(string2Num("BABC", new char[]{'A', 'B', 'C'}));}

进阶问题

/*** 进阶问题：如果数组中存在一个1，如何能够最快的求得答案* @param arr* @return*/public static int unformSumCp3(int[] arr){if (arr == null || arr.length == 0) {return 0;}Arrays.sort(arr);int range = 0;for (int i = 0; i < arr.length; i++) {if (arr[i] > range+1) {return range+1;}else {range += arr[i];}}return range+1;}

c语言版本

正在学习中

c++语言版本

正在学习中

思考感悟

1、首先说一下字符串转数字的过程，这个过程其实很简单，确实跟进制转换是一致的只是没有0而已，A代表1，B代表2，计算出来结果没有问题
2、在说一下数字转字符串的问题，这个按照k^n最大不超过当前num的值的方式进行计算即可，整体来讲没有难度，就是需要对转换的原理熟悉一下

写在最后

方案和代码仅提供学习和思考使用，切勿随意滥用！如有错误和不合理的地方，务必批评指正~
如果需要git源码可邮件给[e-mail]
再次感谢左大神对我算法的指点迷津！