2018小米软开笔试第一题

image.png
image.png

package leetcode;

/**
 * @author Yu
 * @date 2017年9月18日
 * 
 * 2018小米软开笔试第一题
 */

import java.util.Scanner;

public class Xiaomi_Main {

    private static String res = null;

    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        while (sc.hasNext()) {
            String str = sc.next();
            str = Exg(str);
            res = str.toUpperCase();
            System.out.println(res);
        }
        sc.close();
//      System.out.println(Exg("MY.ASTParser12").toUpperCase());
    }

    public static String Exg(String str) {
        if (str == null)
            return null;
        str = "_" + str + "_";
        str = str.replace('.', '_');
        char[] c = new char[str.length()+1000];
        int j = 0;
        for (int i = 0; i < str.length(); i++) {
            if ((('a' <= str.charAt(i) && str.charAt(i) <= 'z')
                    && ('A' <= str.charAt(i + 1) && str.charAt(i + 1) <= 'Z'))) {
                c[j++] = str.charAt(i);
                c[j++] = '_';
            } else if ((('A' <= str.charAt(i) && str.charAt(i) <= 'Z')
                    && ('A' <= str.charAt(i + 1) && str.charAt(i + 1) <= 'Z')
                    && ('a' <= str.charAt(i + 2) && str.charAt(i + 2) <= 'z'))) {
                c[j++] = str.charAt(i);
                c[j++] = '_';
            } else if ((('A' <= str.charAt(i) && str.charAt(i) <= 'Z')
                    || ('a' <= str.charAt(i) && str.charAt(i) <= 'z'))
                    && ('0' <= str.charAt(i + 1) && str.charAt(i + 1) <= '9')) {
                c[j++] = str.charAt(i);
                c[j++] = '_';
            } else if (('0' <= str.charAt(i) && str.charAt(i) <= '9')
                    && (('A' <= str.charAt(i + 1) && str.charAt(i + 1) <= 'Z')
                            || ('a' <= str.charAt(i + 1) && str.charAt(i + 1) <= 'z'))) {
                c[j++] = str.charAt(i);
                c[j++] = '_';
            } else {
                c[j++] = str.charAt(i);
            }
            
        }
        
        String ss = String.valueOf(c);
        ss = ss.trim();//用trim()函数去除字符串首尾的空格
        return ss;
    }
}

大佬用C++ KMP写的，膜拜下

#include <cstdio>
#include <cstring>
#include <iostream>
#include <string>
#include <algorithm>
#include <cstdlib>
#include <vector>
#include <map>

using namespace std;

const int maxn = 10007;

char s1[maxn], s2[maxn], s3[maxn];
int ne[maxn], loc[maxn];
int vis[30];
int n, l1, l2;
int ans, s, e;
void getNext() {
    int k = -1;
    ne[0] = -1;
    for (int i = 1; i < l2; i++) {
        while (k != -1 && s2[i] != s2[k + 1]) {
            k = ne[k];
        }
        if (s2[i] == s2[k + 1]) {
            k++;
        }
        ne[i] = k;
    }
}

void getAns() {
    int k = -1;
    for (int i = 0; i < n; i++) {
        while (k != -1 && s3[i] != s2[k + 1]) {
            k = ne[k];
        }
        if (s3[i] == s2[k + 1]) {
            k++;
        }
        if (k == l2 - 1) {
            int temp = loc[i] - loc[i + 1 - l2];
            if (temp < ans) {
                ans = temp;
                s = loc[i + 1 - l2];
                e = loc[i];
            }
            k = ne[k];
        }
    }
}

int main() {
//    freopen("in.txt", "r", stdin);
    while (scanf("%s%s", &s1, s2) != EOF) {
        memset(vis, 0, sizeof(vis));
        l2 = strlen(s2);
        l1 = strlen(s1);
        ans = l1 + 1;
        s = -1;
        e = -1;
        for (int i = 0; i < l2; i++) {
            vis[s2[i] - 'a'] = 1;
        }
        n = 0;
        for (int i = 0; i < l1; i++) {
            if (vis[s1[i] - 'a']) {
                s3[n] = s1[i];
                loc[n] = i;
                n++;
            }
        }
        s3[n] = '\0';
//        printf("%s\n", s3);
        getNext();
        getAns();
        printf("%d %d\n", s, e);
    }
    return 0;
}