迅雷-Android补考

感谢迅雷，让我完成秋招全部AC编程题的愿望，看错时间以为是晚上9.30笔试，结果笔试过了一个小时收到提示短信，然后才匆忙做的，还好笔试不是特别难，宇宙雷估计也没有hc了

第一题：

/**
 * 题目描述：
 * 给定字符串 s 和 t ，判断 s 是否为 t 的子序列。
 * 你可以认为 s 和 t 中仅包含英文小写字母。字符串 t 可能会很长（长度 ~= 500,000），
 * 而 s 是个短字符串（长度 <=100）。
 * 字符串的一个子序列是原始字符串删除一些（也可以不删除）字符而不改变剩余字符相对位置形成的新字符串。
 * （例如，"ace"是"abcde"的一个子序列，而"aec"不是）。
 * 示例 1: s = "abc", t = "ahbgdc"
 * <p>
 * 返回 true.
 * <p>
 * 示例 2: s = "axc", t = "ahbgdc"
 * <p>
 * 返回 false
 * <p>
 * Created by XQM on 2018/10/18.
 */

public static boolean isSubsequence(String s, String t) {
        if (s.isEmpty()) {
            return false;
        }
        if (s.length() > t.length()) {
            return false;
        }
        int k = 0;
        for (int i = 0; i < s.length(); i++) {
            for (int j = k; j < t.length(); j++) {
                if (s.charAt(i) == t.charAt(j)) {
                    k = j;
                    if (i == s.length() - 1) {
                        return true;
                    }
                    break;
                }
            }
        }
        return false;
    }

第二道：

/**
 * 题目描述：
 * 如果序列 X_1, X_2, ..., X_n 满足下列条件，就说它是斐波那契式的：
 * n >= 3
 * 对于所有 i + 2 <= n，都有 X_i + X_{i+1} = X_{i+2}
 * 给定一个严格递增的正整数数组形成序列，找到 A中最长的斐波那契式的子序列的长度。如果一个不存在，返回 0 。
 * （回想一下，子序列是从原序列A中派生出来的，它从A中删掉任意数量的元素（也可以不删），
 * 而不改变其余元素的顺序。例如， [3, 5, 8] 是 [3, 4, 5, 6, 7, 8] 的一个子序列）
 * <p>
 * 示例：
 * <p>
 * 输入: [1,2,3,4,5,6,7,8]
 * <p>
 * 输出: 5
 * <p>
 * 解释:
 * <p>
 * 最长的斐波那契式子序列为：[1,2,3,5,8], 长度为5
 * Created by XQM on 2018/10/18.
 */

public static int lenLongestFibSubseq(int[] A) {
        Set<Integer> set = new HashSet<>();
        for (int item : A) {
            set.add(item);
        }

        int maxLength = 0;
        for (int i = 0; i < A.length; i++) {
            for (int j = i + 1; j < A.length; j++) {
                int firstA = A[j];
                int secondA = A[i] + A[j];
                int length = 2;

                while (set.contains(secondA)) {
                    int tmp = secondA;
                    secondA += firstA;
                    firstA = tmp;
                    maxLength = Math.max(maxLength, ++length);
                }
            }
        }

        return maxLength >= 3 ? maxLength : 0;
    }