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);
            }
        }
    }
}
全部评论

相关推荐

11-15 17:19
湖南大学 Java
成果成果成果果:这是哪个公司的hr,这么离谱吗,我没见过用性别卡技术岗的,身边女性同学拿大厂offer的比比皆是
点赞 评论 收藏
分享
扭转乾坤_:现在企业都是学华为,一直通过丢池子里,最后捞
点赞 评论 收藏
分享
3 收藏 评论
分享
牛客网
牛客企业服务