记录一下5道Java笔试算法题

以下逻辑题，用Java编程语言，并尽量考虑时间和空间优化

1、实现以下2个接口不能使用语言的基本分割组合函数(如Java的String.split,php的explode和implode)

(1）字符串拆分成数组，如“ab&&2”通过”&&“做分隔符，分割得到字符串数组[“b”，“2”]

public static List<String> splitString(String s, String delim) {
    List<String> res = new ArrayList<>();
    int start = 0;
    for (int i = 0; i < s.length(); i++) {
        if (i + delim.length() <= s.length() && s.substring(i, i + delim.length()).equals(delim)) {
            res.add(s.substring(start, i));
            start = i + delim.length();
        }
    }
    res.add(s.substring(start));
    return res;
}
1
2
3
4
5
6
7
8
9
10
11
12

示例

System.out.println(splitString("ab&&2", "&&")); // ["ab", "2"]
System.out.println(splitString("hello world", " ")); // ["hello", "world"]
System.out.println(splitString("hello||world||java", "||")); // ["hello", "world", "java"]
System.out.println(splitString("abcde", "||")); // ["abcde"]
1
2
3
4

(2）实现字符串组合，如[“ab”，”2”]通过“&&"分隔符，组合成字符串"ab&&2”

public static String joinString(List<String> strList, String delim) {
    StringBuilder sb = new StringBuilder();
    if (strList.size() > 0) {
        sb.append(strList.get(0));
    }
    for (int i = 1; i < strList.size(); i++) {
        sb.append(delim);
        sb.append(strList.get(i));
    }
    return sb.toString();
}
1
2
3
4
5
6
7
8
9
10
11

示例

System.out.println(joinString(Arrays.asList("ab", "2"), "&&")); // "ab&&2"
System.out.println(joinString(Arrays.asList("hello", "world"), " ")); // "hello world"
System.out.println(joinString(Arrays.asList("hello", "world", "java"), "||")); // "hello||world||java"
System.out.println(joinString(Arrays.asList("abcde"), "||")); // "abcde"
1
2
3
4

2、找出不大于n的最大质数

public static int findLargestPrime(int n) {
    int largestPrime = 2;    // 2是质数，所有的偶数(除了2)都不是质数
    for (int i = 3; i <= n; i += 2) {
        boolean isPrime = true;
        for (int j = 2; j <= Math.sqrt(i); j++) {
            if (i % j == 0) {
                isPrime = false;
                break;
            }
        }
        if (isPrime && i <= n) {
            largestPrime = i;
        }
    }
    return largestPrime;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16

示例

System.out.println(findLargestPrime(10));    // 7
System.out.println(findLargestPrime(15));    // 13
System.out.println(findLargestPrime(100));   // 97
System.out.println(findLargestPrime(2));     // 2
1
2
3
4

3、1000个数范围是[0,999]，有2个相同的数,请设计算法找出来

public static int[] findDuplicate(int[] nums) {
    int sum = 0, sumSet = 0;
    Set<Integer> set = new HashSet<>();
    for (int num : nums) {
        sum += num;
        if (set.contains(num)) {
            return new int[]{num, sum - (1 + nums.length) * nums.length / 2};
        }
        set.add(num);
    }
    return new int[0];
}
1
2
3
4
5
6
7
8
9
10
11
12

示例

System.out.println(Arrays.toString(findDuplicate(new int[]{1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 10, 11, 12, 13, 14, 15, 16, 17, 18, 19, 20})));
// [10, 10]
1
2

4、n个人（编号1~n）围成一圈从编号为1的开始报数，从1报数到m，报到m的人出来，下一个人继续重新从1开始报数，编程求最后一个留下的人的编号如 n=3，m=4 第一次出队：1，第二次出队：3，最后留下：2

public static int lastRemaining(int n, int m) {
    List<Integer> numbers = new ArrayList<>();
    for (int i = 1; i <= n; i++) {
        numbers.add(i);
    }
    int idx = 0;
    while (numbers.size() > 1) {
        idx = (idx + m - 1) % numbers.size();
        numbers.remove(idx);
    }
    return numbers.get(0);
}
1
2
3
4
5
6
7
8
9
10
11
12

示例

System.out.println(lastRemaining(3, 4));    // 2
System.out.println(lastRemaining(5, 3));    // 4
1
2

5、有26个字母a-z，找出所有字母的组合，a、b、c、ab、abc、a~z都是一个组合

public static List<String> letterCombinations() {
    String letters = "abcdefghijklmnopqrstuvwxyz";
    List<String> res = new ArrayList<>();
    dfs(res, new char[letters.length()], letters, 0);
    return res;
}

private static void dfs(List<String> res, char[] path, String letters, int pos) {
    if (pos == letters.length()) {
        res.add(new String(path));
        return;
    }
    for (int i = 0; i < letters.length(); i++) {
        path[pos] = letters.charAt(i);
        dfs(res, path, letters, pos + 1);
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17

示例

System.out.println(letterCombinations());
// ["a", "b", "c", ..., "abc...w", "abc...x", "abc...y", "abc...z", ..., "abcdefghijklmnopqrstuvwxyz"]
1
2