剑指Offer之Java算法习题精讲 - 数组查找与字符串交集

一、本章介绍

本章将会对“剑指Offer”系列书籍中有关数组查找与字符串交集的核心算法习题进行总结和分析。我们将会结合具体的算法样例进行讲解，并且会针对其中涉及到的算法思想与编程技巧进行加深细致的探讨。

二、数组查找

1. 二维数组中的查找

题目描述：

在一个二维数组中，每一行都按照从左到右递增的顺序排序，每一列都按照从上到下递增的顺序排序。请完整实现一个函数，输入这样的一个二维数组和一个整数，判断数组中是否含有该整数，并返回一个 boolean 值。

算法思路：

从矩阵右上角的元素开始，如果该元素等于目标值，则返回 true；如果该元素大于目标值，则剔除该元素所在列；如果该元素小于目标值，则剔除该元素所在行。以此类推，直到找到目标值或到达矩阵边界。

代码示例：

public static boolean findInPartiallySortedMatrix(int[][] matrix, int target) {
    if (matrix == null || matrix.length == 0 || matrix[0].length == 0) {
        return false;
    }
    int row = 0;
    int col = matrix[0].length - 1;
    while (row < matrix.length && col >= 0) {
        if (matrix[row][col] == target) {
            return true;
        } else if (matrix[row][col] > target) {
            col--;
        } else {
            row++;
        }
    }
    return false;
}

2. 旋转数组的最小数字

题目描述：

把一个数组最开始的若干个元素搬到数组的末尾，我们称之为旋转。求一个非递减数组的旋转数组的最小数字。例如，数组 {3,4,5,1,2} 为 {1,2,3,4,5} 的一个旋转，该数组的最小值为1。

算法思路：

考虑使用二分查找算法。对于一个排序的数组，使用二分查找算法的时间复杂度为 O(log n)。但是此处的数组是一个旋转数组，因此需要更改查找算法的判断条件。对于一个数组，以最后一个元素为分界点将其分为两个有序的子数组，旋转数组的最小数字即为后半部分的首个元素。每一次查找后，可以通过比较中间元素与区间边界元素的大小来确定需要继续加载左半部分还是右半部分。

代码示例：

public static int minNumberInRotateArray(int[] array) {
    if (array == null || array.length == 0) {
        return 0;
    }
    int left = 0;
    int right = array.length - 1;
    while (left < right) {
        int mid = (left + right) / 2;
        if (array[mid] > array[right]) {
            left = mid + 1;
        } else if (array[mid] == array[right]) {
            right--;
        } else {
            right = mid;
        }
    }
    return array[left];
}

三、字符串交集

1. 字符串排列

题目描述：

输入一个字符串，打印出该字符串中字符的所有排列。例如，输入字符串 abcd，则输出由字符 a、b、c、d 所能排列出来的所有字符串：abcd、abdc、acbd、acdb、adbc、adcb、bacd、badc、bcad、bcda、bdac、bdca、cabd、cadb、cbad、cbda、cdab、cdba、dabc、dacb、dbac、dbca、dcab、dcba。

算法思路：

本题可以使用递归算法解决。固定第一个字符，对剩余字符进行排列。依次枚举第一个字符，再求后面的字符串的排列。当字符串只有一个字符时，其返回值为该字符本身。

代码示例：

public static ArrayList<String> permutation(String string) {
    ArrayList<String> result = new ArrayList<>();
    if (string == null || string.length() == 0) {
        return result;
    }
    char[] chars = string.toCharArray();
    recursion(result, chars, 0);
    Collections.sort(result); // 排序
    return result;
}

private static void recursion(ArrayList<String> result, char[] chars, int i) {
    if (i == chars.length - 1) {
        result.add(String.valueOf(chars));
    } else {
        Set<Character> set = new HashSet<>();
        for (int j = i; j < chars.length; j++) {
            if (!set.contains(chars[j])) {
                set.add(chars[j]);
                swap(chars, i, j);
                recursion(result, chars, i + 1);
                swap(chars, i, j);
            }
        }
    }
}

private static void swap(char[] chars, int i, int j) {
    char temp = chars[i];
    chars[i] = chars[j];
    chars[j] = temp;
}

2. 字符串转换成整数

题目描述：

将一个字符串转换成一个整数，该字符串一定表示一个正整数，例如输入字符串 "345"，则输出数字 345。

算法思路：

本题可以使用从左到右遍历字符串，累加每个字符对应的数字，最终得到该字符串所表示的整数的值。需要注意参数合法性边界和数字溢出问题。

代码示例：

public static int strToInt(String str) {
    if (str == null || str.length() == 0) {
        return 0;
    }
    int sign = 1; // 标记正负
    int sum = 0; // 累加和
    int i = 0;
    char[] chars = str.toCharArray();
    if (chars[0] == '+' || chars[0] == '-') {
        if (chars[0] == '-') {
            sign = -1;
        }
        i++;
    }
    for (; i < chars.length; i++) {
        // 检查字符是否合法
        if (chars[i] < '0' || chars[i] > '9') {
            return 0;
        }
        // 检查数字是否溢出
        if (sum > Integer.MAX_VALUE / 10 || (sum == Integer.MAX_VALUE / 10 && (chars[i] - '0') > Integer.MAX_VALUE % 10)) {
            return 0;
        }
        sum = sum * 10 + (chars[i] - '0');
    }
    return sign * sum;
}

四、小结

通过本章的学习，我们不仅对数组查找和字符串交集的核心算法有了更为深入的认识，同时也熟悉了在Java中实现各种不同类型算法的代码操作技巧。我们希望这些经验能够为读者在今后的编程实践中提供帮助与指导。