美团笔试,字符串距离非暴力做法思路及实现

写的时候是暴力,后来浏览帖子发现了一个好思路
图片说明

思路是可以的,细节方面做了点完善,实现了。

后面扩展:可以继续稍作修改,解决的问题可以不仅限于字符串里只有a b(现在还没写)

既然是从牛客得到的灵感,下面代码(还是只是处理只有a b 的)供大家飨之,欢迎讨论,以增进厨艺(滑稽)。


import java.util.Scanner;

/**
 * Created with IDEA
 * User : 点到维止
 * Date : 2018/3/22
 */
public class Test {

    public static void main(String[] args) {
        Scanner in = new Scanner(System.in);
        while (in.hasNextLine()) {
            String S = in.nextLine();
            String T = in.nextLine();

            int[][] count = new int[S.length()][256];
            int a = 0;
            int b = 0;
            for (int i = 0; i < S.length(); i++) {
                if(S.charAt(i) == 'a'){
                    count[i][(int) 'a'] = ++a;
                    count[i][(int) 'b'] = b;
                } else {
                    count[i][(int) 'a'] = a;
                    count[i][(int) 'b'] = ++b;
                }
            }

            int sum = 0;
            int offset = S.length() - T.length();
            if(S.charAt(0) == 'a'){
                sum += count[0 + offset]['b'];
            } else {
                sum += count[0 + offset]['a'];
            }
            for(int i = 1; i < T.length(); i++) {
                if(S.charAt(i) == 'a'){
                    sum += count[i + offset]['b'] -  count[i - 1]['b'] ;
                } else {
                    sum += count[i + offset]['a'] -  count[i - 1]['a'] ;
                }
            }
            System.out.println(sum);
        }
    }
}
#笔试题目##Java##美团#
全部评论

相关推荐

05-16 11:16
已编辑
东华理工大学 Java
牛客737698141号:盲猜几十人小公司,庙小妖风大,咋不叫她去4️⃣呢😁
点赞 评论 收藏
分享
评论
点赞
收藏
分享

创作者周榜

更多
牛客网
牛客网在线编程
牛客网题解
牛客企业服务