2020牛客寒假算法基础集训营5 H-Hash题解
Hash
http://www.nowcoder.com/questionTerminal/5e806b54a0234b1a886cc11231e33ebf
题意
由题目的意思可得,他是将一个6位字符串转化为一个数字,然后再取mod。
观察主要的公式:res = (res * 26 + str[i] - 'a') % mod;
是不是和字符串转化为数字的公式似曾相识呢。
平时我们转化一个字符串的时候正是使用类似的方法:
string str = "123"; int ans = 0; for (int i = 0;str[i] != 0;i ++) { ans = ans * 10 + str[i] - '0'; }
同样的,对于这个res = (res * 26 + str[i] - 'a') % mod;
公式来说,也是一个字符串转化成数字的过程,唯一的不同是,我们写的是10进制的,他这个公式是26进制的,所以,我们需要写一个转化。
同hash值
既然要相同的hash值,由于他是取余数的,并且要最小的字典序,那么只要把转化好的数值加上mod
的值就行。
实现
由于java的大数BigInteger
可以很方便的处理别的进制,所以我偷了个懒,直接用java的大数来处理了,C++实现起来也很方便的。
由于真实的26进制是从0开始的,所以我们只要将['a','j']
这个区间里面所有的字母对应到[0,9]
,余下的减去10即可。
由此可以写出代码:
for (int i = 0; i < str.length(); i ++) { if (str.charAt(i) <= 'j') k += (char) (str.charAt(i) - 'a' + '0'); else k += (char) (str.charAt(i) - 10); }
处理完毕直接丢给BigInteger即可。
BigInteger a = new BigInteger(k, 26); // 注意:加上radix: 26,代表他是26进制
之后我们直接让他加上我们的mod即可
BigInteger b = new BigInteger(String.valueOf(mod)); // 把mod转化成大数 String v = a.add(b).toString(26); // 相加,并转化成26进制的字符串
之后,再把v
用之前的方法的逆运算,转换回原来的字符串即可。
for (int i = 0; i < v.length(); i++) { if (v.charAt(i) <= '9') ans += (char) (v.charAt(i) - '0' + 'a'); else ans += (char) (v.charAt(i) + 10); }
最后,处理下小细节,由于可能ans
是不到6位的,这时候需要补前导0,由于转化好之后是a,所以直接补a即可。
同时ans
也可能超过6位,这时候直接输出-1就行。
if (ans.length() > 6) System.out.println(-1); else { while (ans.length() < 6) ans = 'a' + ans; System.out.println(ans); }
AC代码
import java.math.BigInteger; import java.util.Scanner; public class Main { public static void main(String[] args) { Scanner scanner = new Scanner(System.in); while (scanner.hasNext()) { String str = scanner.next(); int mod = scanner.nextInt(); String k = ""; for (int i = 0; i < str.length(); i++) { if (str.charAt(i) <= 'j') k += (char) (str.charAt(i) - 'a' + '0'); else k += (char) (str.charAt(i) - 10); } BigInteger a = new BigInteger(k, 26); BigInteger b = new BigInteger(String.valueOf(mod)); String v = a.add(b).toString(26); String ans = ""; for (int i = 0; i < v.length(); i++) { if (v.charAt(i) <= '9') ans += (char) (v.charAt(i) - '0' + 'a'); else ans += (char) (v.charAt(i) + 10); } if (ans.length() > 6) System.out.println(-1); else { while (ans.length() < 6) ans = 'a' + ans; System.out.println(ans); } } } }