牛客网算法——名企高频面试题143题（2）

题目描述

从0,1,2,...,n这n+1个数中选择n个数，组成有序数组，找出这n个数中缺失的那个数，要求O(n)尽可能小。

package 名企高频面试题143;

import org.junit.Test;

/**
 * @Classname 缺失的数字
 * @Description TODO 从0,1,2,...,n这n+1个数中选择n个数，组成有序数组，找出这n个数中缺失的那个数，要求O(n)尽可能小。
 * @Date 2020/12/8 12:33
 * @Created by xjl
 */
public class 缺失的数字 {

    public int solve(int[] a) {
        int sum = 0;
        int n = a.length;
        for (int i = 0; i < n; i++) {
            if (sum == a[i]) {
                sum += 1;
            } else {
                break;
            }
        }
        return sum;
    }

    /**
     * @description TODO 使用的是二分法的来实现
     * @param: a
     * @date: 2020/12/8 12:51
     * @return: int
     * @author: xjl
     */
    int solve3(int[] a) {
        int l = 0, r = a.length - 1;
        while (l < r) {
            //表示除以二
            int mid = l + ((r - l) >> 1);
            if (mid == a[mid])
                l = mid + 1;
            else
                r = mid - 1;
        }
        return l == a[l] ? l + 1 : l;
    }

    /**
     * @description TODO 使用的是位运算
     * @param: a
     * @date: 2020/12/8 13:00
     * @return: int
     * @author: xjl
     */
    public int solve2(int[] a) {
        int res = a.length;
        for (int i = 0; i < a.length; i++) {
            res ^= i ^ a[i];
            System.out.println(res);
        }
        return res;
    }

    @Test
    public void test() {
        int i = solve2(new int[]{0, 1, 2, 3, 4, 5, 7});
        System.out.println(i);
    }
}

题目描述

编写一个函数来查找字符串数组中的最长公共前缀。

package 名企高频面试题143;

import org.junit.Test;

/**
 * @Classname 最长公共前缀
 * @Description TODO
 * @Date 2020/12/8 13:17
 * @Created by xjl
 */
public class 最长公共前缀 {

    @Test
    public void test() {
        String s = longestCommonPrefix(new String[]{"abca", "abc", "abca", "abc", "abcc"});
        System.out.println(s);
    }

    /**
     * @description TODO 采用的是最长公共前缀的就是采用是遍历的方式来判断一次判断
     * @param: strs
     * @date: 2020/12/8 13:20
     * @return: java.lang.String
     * @author: xjl
     */
    public String longestCommonPrefix(String[] strs) {
        //判断数组安全
        if (strs.length == 0) {
            return "";
        }
        String res = strs[0];
        for (int i = 1; i < strs.length; i++) {
            res = fit(res, strs[i]);
        }
        return res;
    }

    /**
     * @description TODO 表示的两个字符串的相同的部分前缀
     * @param: res
     * @param: str
     * @date: 2020/12/8 13:22
     * @return: java.lang.String
     * @author: xjl
     */
    private String fit(String res, String str) {
        //判断短的字符是哪一个 res 是短的 str是长的
        if (res.length() > str.length()) {
            String tmp = res;
            res = str;
            str = tmp;
        }
        for (int i = res.length() - 1; i >= 0; i--) {
            if (str.contains(res.substring(0, i + 1))) {
                return res.substring(0, i + 1);
            }
        }
        return "";
    }
}

 方法一是横向扫描，依次遍历每个字符串，更新最长公共前缀。另一种方法是纵向扫描。纵向扫描时，从前往后遍历所有字符串的每一列，比较相同列上的字符是否相同，如果相同则继续对下一列进行比较，如果不相同则当前列不再属于公共前缀，当前列之前的部分为最长公共前缀。

 public String longestCommonPrefix2(String[] strs) {
        if (strs.length == 0 || strs == null) {
            return "";
        }
        StringBuilder sb = new StringBuilder();
        for (int i = 0; i < strs[0].length(); i++) {
            char ch = strs[0].charAt(i);
            for (int j = 1; j < strs.length; j++) {
                if (strs[j].length() = 0; j--) {
                if (array[i] > array[j]) {
                    count++;
                }
            }
        }
        return count % 1000000007;
    }

    /**
     * @description TODO 采用了的数组归并的方式来实现的
     * @param: nums
     * @date: 2020/12/8 15:31
     * @return: int
     * @author: xjl
     */
    public int reversePairs(int[] nums) {
        int len = nums.length;
        if (len < 2) {
            return 0;
        }
        int[] copy = new int[len];
        for (int i = 0; i < len; i++) {
            copy[i] = nums[i];
        }
        int[] temp = new int[len];
        return reversePairs(copy, 0, len - 1, temp);
    }

    /**
     * nums[left..right] 计算逆序对个数并且排序
     *
     * @param nums
     * @param left
     * @param right
     * @param temp
     * @return
     */
    private int reversePairs(int[] nums, int left, int right, int[] temp) {
        if (left == right) {
            return 0;
        }
        int mid = left + (right - left) / 2;
        int leftPairs = reversePairs(nums, left, mid, temp);
        int rightPairs = reversePairs(nums, mid + 1, right, temp);
        if (nums[mid]