杭城四少面试题

Posted on |

江董

江董上海面试题，30分钟写不出，现场代码至少一个小时(实际情况肯定要结合测试用例)，这里实现一个O(N)的版本。

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
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
package com.souche;


/**
 * 有两个字符串，开始字符串：startStr，结束字符串：endStr。
 * startStr=LRXRLLXR
 * endStr=XRRLXXLR
 * LR可转换成RL
 * RX可转换成XR
 * 实现一个方法，判断startStr是否可转换成endStr
 */
public class GuavaTest {
    public static void main(String[] args) {
        /*ThreadPoolExecutor executor =
                (ThreadPoolExecutor) Executors.newFixedThreadPool(5);
        ExecutorService executorService =
                MoreExecutors.getExitingExecutorService(executor,
                        10000, TimeUnit.MILLISECONDS);

        executorService.submit(() -> {
            while (true) {
                System.out.println(1);
            }
        });*/

        //start from here
        StringEqual stringEqualA = new StringEqual("LRRXX");
        StringEqual stringEqualB = new StringEqual("RRLXR");

        System.out.println(stringEqualA.equals(stringEqualB));
    }
}


class StringEqual extends Object {
    private String string;

    public StringEqual(String string) {
        this.string = string;
    }

    @Override
    public boolean equals(Object obj) {
        StringEqual stringEqualB = (StringEqual) obj;
        char[] charsA = string.toCharArray();
        char[] charsB = stringEqualB.string.toCharArray();

        for (int i = 0; i < charsB.length; i++) {
            //如果不想等&&未到末尾字符，尝试走转换器
            if ((charsA[i] != charsB[i]) && (i < (charsB.length - 1))) {
                String a = new Character(charsA[i]).toString() +
                    new Character(charsA[i + 1]).toString();
                String b = new Character(charsB[i]).toString() +
                    new Character(charsB[i + 1]).toString();

                if (defineEquals(a, b, charsA, charsB, i)) {
                    continue;
                } else {
                    //print一下pop的结果 转换器无法进行转换
                    System.out.println(charsA);
                    System.out.println(charsB);

                    return false;
                }
            } else if (i == (charsB.length - 1)) {
                //print一下最终的结果，最后一个字符特殊处理不用往后走转换器
                System.out.println(charsA);
                System.out.println(charsB);

                return charsB[i] == charsA[i];
            } //相等继续往下走
            else {
                continue;
            }
        }

        //print一下最终的转换结果
        System.out.println(charsA);
        System.out.println(charsB);

        return true;
    }

    /**
     * 自定义规则（自定义一个转换器）
     */
    private boolean defineEquals(String a, String b, char[] charsA,
        char[] charsB, int index) {
        //两字符串在TR组合中
        if (a.equals("LR") && b.startsWith("R")) {
            charsA[index] = 'R';
            charsA[index + 1] = 'L';

            return true;
        } else if (a.startsWith("R") && b.equals("LR")) {
            charsB[index] = 'R';
            charsB[index + 1] = 'L';

            return true;
        } //两字符串在RX组合中
        else if (a.equals("RX") && b.startsWith("X")) {
            charsA[index] = 'X';
            charsA[index + 1] = 'R';

            return true;
        } else if (a.startsWith("X") && b.equals("RX")) {
            charsB[index] = 'X';
            charsB[index + 1] = 'R';

            return true;
        } else {
            return false;
        }
    }
}

坤宝

题目：一个字符串含有空格，求非空格最长子串长度，要求时间和空间最优。例如：”aa aa aaaa aaa a a a aa aa a”；

想不出更好的，直接放弃。