阿里灵犀互娱 4-19 算法笔试答案

1 找缺失的数字，使用哈希表进行记录，数组中不存在那么k就-1

 public static int findMissingNum(int[] nums, int k) {
        HashSet<Integer> set = new HashSet<>();
        for (int num : nums) {
            set.add(num);
        }
        int start = nums[0];
//        int ans = start + 1;
        while (k > 0) {
            start++;
            if (!set.contains(start)) {
                k--;
            }
        }
        return start;
    }

2 二叉树求根节点到叶子节点的和

隔壁 112. 路径总和 原题

public boolean hasPathSum(TreeNode root, int sum) {
        if (root == null) return false;
        if (root.val == sum) {
            if (root.left == null && root.right == null) return true;
        }
        boolean left = false;
        if (root.left != null) {
            left = hasPathSum(root.left, sum - root.val);
        }
        boolean right = false;
        if (root.right != null) {
            right = hasPathSum(root.right, sum - root.val);
        }
        return left || right;
    }

3 在一个长字符串中寻找特定的字符串

使用系统api就行，我用的是Java的String的contain

 public int[][] indexPairs(String text, String[] words) {
        ArrayList<int[]> temp = new ArrayList<>();
        for (int i = 0; i < words.length; i++) {
            String word = words[i];
            String tempText = text;
            while (tempText.contains(word)) {
                int start = tempText.indexOf(word);
                int[] index = new int[]{start, start + word.length() - 1};
                temp.add(index);
                char[] cs = tempText.toCharArray();
				//不知道这里为啥是-1 但是这样就能过100%了
                for (int j = start; j < start + word.length()-1; j++) {
                    cs[j] = '7';
                }
                tempText = String.valueOf(cs);
//                tempText.in
//                tempText = tempText.replace(word, String.valueOf(Math.pow(10, words.length)));
//                tempText = tempText.substring(start + word.length());
            }


        }
        temp.sort((o1, o2) -> {
            if (o1[0] != o2[0]) {
                return o1[0] - o2[0];

            } else {
                return o1[1] - o2[1];
            }
        });

        int[][] ans = new int[temp.size()][];
        for (int i = 0; i < temp.size(); i++) {
            ans[i] = temp.get(i);
        }
        return ans;
    }

不知道这次为啥给双非都发笔试了，之前都是直接简历挂