迅雷-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;
    }
#迅雷##Android##笔试题目#
全部评论
dalao666666a
点赞 回复
分享
发布于 2018-10-18 16:46

相关推荐

点赞 收藏 评论
分享
牛客网
牛客企业服务