By Long Luo
最近面试时遇到一个算法题:
仿照Excel的列编号,给出一个数字,输出该列编号字符串。
例如:A对应1,Z对应26,AA对应27,AZ对应52 …
这个题目是一个典型的26进制思路去处理,一个整数除26然后但是这个题目里面有很多陷阱,在1, 26, 52等特殊情况进行考虑,经过晚上接近半个多小时的编写,完成的代码如下:
C++
C++实现如下所示:
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85
| #include <iostream> #include <string.h>
using namespace std;
void itos(int num, char *pcout ) { char *res = new char[255]; int m = 0, n = 0; while((num >= 1) && (n < 255)) { m = num % 26; if (m != 0) { res[n] = 'A' + m - 1; } else { res[n] = 'Z'; num--; } num /= 26; n++; }
for(m = n; m > 0; m--) { pcout[n - m] = res[m - 1]; }
pcout[n] = '\0'; delete[] res;
return; }
int stoi(char *cha) { int m = 0, n = 0, i = 0, val = 0, a = 0; char *pc = cha ;
while(*pc != '\0' ) { pc++; n++; } for(i = 1; i <= n; i++) { pc--; a = i; m = 1; while(a > 1) { m *=26; a--; } m *= (*pc - 'A' +1); val += m; } return val; }
int main() { char out[255] = {0}; printf( "out = %s\n", out); itos(32, out); printf( "out = %s\n", out);
getchar();
return true ; }
|
Java
Java代码如下所示:
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66
| package com.Algorithms.excelrow;
public class ExcelRow { public static void main(String args[]) {
System.out.println("25=" + int2Str(5) + ",28=" + int2Str(28) + ",123=" + int2Str(123)); System.out.println("C=" + str2Int("C") + ",ZA" + str2Int("ZA") + ",AAF=" + str2Int("AAF")); }
public static int str2Int(String input) { int val = 0; int len = input.length(); int mul = 0;
for (int i = len - 1, j = 0; i >= 0; i--, j++) { mul = 1;
int temp = input.charAt(i) - 'A' + 1; double weiquan = Math.pow(10, j); mul = (int) (temp * weiquan); val += mul;
System.out.println("temp=" + temp + ",weiquan=" + weiquan + ",mul=" + mul + ",val=" + val); }
return val; }
public static String int2Str(int rowNum) { StringBuffer temp = new StringBuffer(255); char ch;
while (rowNum >= 1) {
int i = rowNum % 26; if (i != 0) { ch = (char) ('A' + i - 1); temp = temp.append(ch); } else { ch = 'Z'; temp = temp.append(ch); rowNum--; }
System.out.println("temp=" + temp + ",ch=" + ch + ",rowNum=" + rowNum); rowNum /= 26; }
return temp.reverse().toString(); }
}
|
以上代码均测试通过。
如有不当错误之处,敬请批评指正,如有更好的方法,也请共同探讨, Thx:-)
---------- Updated at 2022.04.21 ----------
这篇文章写于2014年,其实这个题就是Leetcode 171. Excel 表列序号 ,解决方法见Base Conversion 2 Solutions: Left to Right and Right to Left。
Long Luo Created at PM22:25 ~ 22:40 @May 02nd, 2014 at Shenzhen, China.
Updated By Long Luo at 2022年4月21日 14点51分 @Shenzhen, China.