【数据结构与算法之面试题】数组和字符串类面试题

Love The Way You Lie 2024-03-25 20:47 53阅读 0赞

#### 【数据结构与算法之面试题】数组和字符串类面试题 ####

#### 文章目录 ####

*   *   *  【数据结构与算法之面试题】数组和字符串类面试题
         *   *   *  1 数组元素的奇偶重排
                 *  2 不改变顺序的数组元素奇偶重排
                 *  3 有序数组的两数之和
                 *  4 三数之和
                 *  5 两个有序数组的交集
                 *  6 最长公共前缀问题
                 *  7 最长公共子串问题
                 *  8 长度最小的连续子数组
                 *  9 最长无重复子串
                 *  10 删除字符数组中的特定字符
                 *  11 最短连续子数组问题
                 *  12 字符数组的内容重排
                 *  13 字符串数组类面试题解题技巧
                 *   *  【1】双指针法
                     *  【2】锁定起点和滑动窗口
                     *  【3】字符串函数和容器类
                     *  【4】排序算法

###### 1 数组元素的奇偶重排 ######

题目描述：给定一个存放整数的数组，重新排列数组元素使得数组左边为奇数、右边为偶数。

要求：空间复杂度 O ( 1 ) O(1) O(1)，时间复杂度 O ( n ) O(n) O(n)

【思路分析】这道题其实有点像快速排序，在快速排序的一趟排序中，首先指定一个基准点，然后利用两个指针(数组下标) 实现数组元素的一次划分，将小于基准点的元素移动到基准点之前，将大于基准点的元素移动到基准点之后。

利用这种思想，实现奇偶划分。

Java 实现描述：

/**
     * @Projectname: JavaData_StructureAndAlgorithm
     * @Classname: ParityRearrangement
     * @Author: Ding Jiaxiong
     * @Data:2023/3/15 13:36
     */
    
    public class ParityRearrangement {
        
    
        public static void reArrange(int[] array) {
        
    
            int low = 0, high = array.length - 1;
    
            while (true) {
        
                while (!isEvenNumber(array[low]) && low < high) {
        
                    low++; // 循环, 使得low指向第一个偶数元素
                }
                while (isEvenNumber(array[high]) && low < high) {
        
                    high--;  //循环, 使得high指向第一个奇数元素
                }
    
                if (low >= high) {
        
                    return;
                } else {
        
                    swap(array, low, high);
                    low++;
                    high--;
                }
            }
        }
    
        private static boolean isEvenNumber(int e) {
         // 判断一个数是否是偶数
            return (e % 2 == 0) ? true : false;
        }
    
        private static void swap(int[] array, int low, int high) {
        
            int tmp;
            tmp = array[low];
            array[low] = array[high];
            array[high] = tmp;
        }
    
        public static void main(String[] args) {
        
    
            int[] array = {
        1, 2, 3, 4, 5, 6, 7, 8, 9, 10};
            System.out.println("原数组: ");
            for (int i : array) {
        
                System.out.print(i + " ");
            }
    
            reArrange(array);
            System.out.println("\n奇偶重排后的数组: ");
            for (int i : array) {
        
                System.out.print(i + " ");
            }
    
        }
    
    }

运行结果

![在这里插入图片描述][d548bde265f64a01ac7b38d66cf4238a.png_pic_center]

这道题采用的是处理数组、字符串类问题的常用方法 —— 双指针法。双指针法通常用于数组元素按值有序的情况，也可用于数组内容重排、数组内容逆置等问题。

###### 2 不改变顺序的数组元素奇偶重排 ######

题目描述：还是给定一个整数数组，重新排列数组使得数组左边为奇数，右边为偶数。要求不改变数据在数组中的先后次序。

例如，数组初始状态为\{1,2,3,4,5,6,7,8,9,10\}，重排后的数组应该是\{1,3,5,7,9,2,4,6,8,10\}。

【方法一】暴力枚举

定义一个与原数组等长的数组B，然后扫描原始数组A，将里面的奇数逐一读出，保存在数组B中，然后再扫描一遍原始数组A，将里面的偶数逐一读出，保存在数组B的后半部分。

Java 实现：

/**
     * @Projectname: JavaData_StructureAndAlgorithm
     * @Classname: ParityRearrangementV2
     * @Author: Ding Jiaxiong
     * @Data:2023/3/15 13:48
     */
    
    public class ParityRearrangementV2 {
        
    
        public static void reArrange(int[] array) {
        
    
            int i, j;
            int[] tmp_array = new int[array.length];
    
            // 第一遍扫描，得到所有奇数
            for (i = 0, j = 0; i < array.length; i++) {
        
                if (!isEvenNumber(array[i])) {
        
                    tmp_array[j] = array[i];
                    j++;
                }
            }
    
            // 第二遍扫描
            for (i = 0; i < array.length; i++) {
        
                if (isEvenNumber(array[i])) {
        
                    tmp_array[j] = array[i];
                    j++;
                }
            }
    
            // 将tmp_array数组中的内容复制回原数组
            for (i = 0; i < array.length; i++) {
        
                array[i] = tmp_array[i];
            }
    
    
        }
    
        private static boolean isEvenNumber(int e) {
         // 判断一个数是否是偶数
            return (e % 2 == 0) ? true : false;
        }
    
        public static void main(String[] args) {
        
    
            int[] array = {
        1, 2, 3, 4, 5, 6, 7, 8, 9, 10};
            System.out.println("原数组: ");
            for (int i : array) {
        
                System.out.print(i + " ");
            }
    
            reArrange(array);
            System.out.println("\n奇偶重排后的数组: ");
            for (int i : array) {
        
                System.out.print(i + " ");
            }
    
        }
    
    }

运行结果

![在这里插入图片描述][36f4bc7174c34cd1af44a2447ad0c3fe.png_pic_center]

这样子实现虽然满足了算法要求，且时间复杂度为 O(n)，但是空间复杂度有点大了，达到了O(n)，因为我们多开了一个数组作为缓冲区。

如果我们用时间换空间，可以这样做：

import java.util.logging.Level;
    
    /**
     * @Projectname: JavaData_StructureAndAlgorithm
     * @Classname: ParityRearrangementV3
     * @Author: Ding Jiaxiong
     * @Data:2023/3/15 13:55
     */
    
    public class ParityRearrangementV3 {
        
    
        public static void reArrange(int[] array) {
        
            int i, j, k;
            int tmp_elem;
    
            for (i = 0; i < array.length; i++) {
        
                if (isEvenNumber(array[i])) {
        
                    break; // 找到数组中的第一个偶数
                }
            }
    
            for (j = i + 1; j < array.length; j++) {
        
                if (!isEvenNumber(array[j])) {
        
                    tmp_elem = array[j];
                    for (k = j - 1; k >= i; k--) {
        
                        array[k + 1] = array[k];
                    }
    
                    array[i] = tmp_elem;
                    i = i + 1;
                }
            }
    
        }
    
    
        private static boolean isEvenNumber(int e) {
         // 判断一个数是否是偶数
            return (e % 2 == 0) ? true : false;
        }
    
        public static void main(String[] args) {
        
    
            int[] array = {
        1, 2, 3, 4, 5, 6, 7, 8, 9, 10};
            System.out.println("原数组: ");
            for (int i : array) {
        
                System.out.print(i + " ");
            }
    
            reArrange(array);
            System.out.println("\n奇偶重排后的数组: ");
            for (int i : array) {
        
                System.out.print(i + " ");
            }
    
        }
    
    }

运行结果

![在这里插入图片描述][eee20fa439d943389c4f3783ce9a2c0a.png_pic_center]

可以看到这样也可以实现奇偶重排，但是时间复杂度来到了O( n 2 n^2 n2)，但是空间复杂度很低。

###### 3 有序数组的两数之和 ######

【题目描述】给定一个已按照升序排列的有序数组，找到两个数，使得它们的和等于目标数target。算法函数返回下标值index1 和 index2，且index1必须小于index2 。

【举个栗子】一个升序排序的数组 array\[5\] = \{1,2,3,4,5\}，target = 8，得到的结果应该是 index1 = 2，index2 = 4.

最容易想到的当然是穷举法，将数组中任意两个元素的组合枚举出来，计算它们的和是否等于目标数。但是这种方法的时间复杂度已经达到了 O( 2 n 2^n 2n) 级别。这样排不排好序就没差了。

我们可以使用双指针法解决，使用两个数组下标index1 和 index2，一个从前向后扫描，一个从后向前扫描。初始化index1 = 0，index2 = array.length - 1 。然后按照下面的步骤进行：

1.  如果index1 ≥ index2则返回null，否则判断array\[index1\] + array\[index2\] 是否等于目标数target，如果相等返回组合，否则进步骤2
2.  如果array\[index1\] + array\[index2\] > 目标数，则先执行index2 = index2 - 1操作，再回到1，否则进步骤3
3.  如果array\[index1\] + array\[index2\] < 目标数，则先执行index1 = index1 + 1操作，再回到1

Java 算法实现：

import sun.applet.Main;
    
    import java.util.ArrayList;
    
    /**
     * @Projectname: JavaData_StructureAndAlgorithm
     * @Classname: TheSumOfTwoNumbersInAnOrderedArray
     * @Author: Ding Jiaxiong
     * @Data:2023/3/15 14:13
     */
    
    public class TheSumOfTwoNumbersInAnOrderedArray {
        
    
        public static ArrayList<int[]> getTwoNumber(int[] array, int sum) {
        
    
            int index1 = 0;
            int index2 = array.length - 1;
    
            ArrayList<int[]> result = new ArrayList<int[]>();
    
            while (index1 < index2) {
        
                if (array[index1] + array[index2] < sum) {
        
                    index1++;
                } else if (array[index1] + array[index2] > sum) {
        
                    index2--;
                } else {
        
                    int[] oneRes = new int[2];
                    oneRes[0] = index1;
                    oneRes[1] = index2;
                    result.add(oneRes);
                    index1++;
                    index2--;
                }
            }
    
            if (result.size() > 0) {
        
                return result;
            }
    
            return null;
    
        }
    
        public static void main(String[] args) {
        
    
            int[] array = {
        1, 2, 4, 5, 8, 13, 17, 21, 36};
            int target = 21;
    
            ArrayList<int[]> res = getTwoNumber(array, target);
            for (int[] entry : res) {
        
                System.out.println("array[" + entry[0] + "] + array[" + entry[1] + "] = " + target);
            }
    
        }
    
    }

运行结果

![在这里插入图片描述][7fcbd872d47f4fdbb22f6a21979c7023.png_pic_center]

###### 4 三数之和 ######

【题目描述】给定一个包含n 个整数的数组nums，判断nums 中是否存在元素a、b、c，使得a + b + c = 0，打印出所有满足条件且不重复的三元组。要求不能重复。

当然这道题第一眼最先想到的解决办法肯定也是暴力枚举，在枚举的过程中判断三个元素的和是否等于0。如果等于那就是本题的一个答案。

根据排列组合知识可知，这种穷举方式的解空间大小为 C(n , 3)，从n 个中取3个，这样的时间复杂度会来到  o ( n 3 ) o(n^3) o(n3) 级别。【那就不用用了】

还有一种巧妙又高效的办法，利用“数组排序 + 双指针法”。这种方法的时间复杂度为  O ( n l o g n ) + O ( n 2 ) O(nlogn) + O(n^2) O(nlogn)\+O(n2)

这种方法的执行步骤：

首先将数组nums\[\] 从小到大排序，并将排序后的数组元素保存到数组sorted\[\] 中，然后在排序后的数组sorted\[\] 中从左到右定位元素，最后找出符合题目要求的三元组。

`具体操作步骤`

1.  定位sorted\[i\] 元素(最初i = 0)，即将sorted\[i\] 作为结果三元组中的一个元素
2.  在sorted\[i\] 元素右边的子数组中寻找另外两个元素。寻找的方法是利用两个指针，low 指向子数组中最小的元素\[最左\]，high指向子数组中最大的元素\[最右\]，判断sorted\[i\] + sorted\[low\] + sorted\[high\] 是否等于0，如果等于，即是一个答案，可将其输出
    
    如果不等于，分两种情况考虑：
    
     *  如果sorted\[i\] + sorted\[low\] + sorted\[high\] < 0，则low++，重复步骤2
     *  如果sorted\[i\] + sorted\[low\] + sorted\[high\] > 0，则high–，重复步骤2
3.  当high < low时，表示sorted\[i\] 右边子数组的元素已经全部遍历，此时可能找到了一些解，也可能没找到。这个时候 i ++，回到步骤1，继续定位

Java 实现：

import java.util.ArrayList;
    import java.util.Arrays;
    
    /**
     * @Projectname: JavaData_StructureAndAlgorithm
     * @Classname: SumOfThreeNumbers
     * @Author: Ding Jiaxiong
     * @Data:2023/3/15 14:39
     */
    
    public class SumOfThreeNumbers {
        
    
        public static void threeNumberSum(int[] array) {
        
    
            int[] sorted = new int[array.length];
            System.arraycopy(array, 0, sorted, 0, array.length);
    
            Arrays.sort(sorted);
    
            for (int i = 0; i <= sorted.length - 3 && sorted[i] <= 0; i++) {
        
                if (i != 0 && sorted[i] == sorted[i - 1]) {
        
                    // 出现重复元素, 过滤掉，不作为定位元素
                    continue;
                }
    
                int low = i + 1; // 指向子数组中最小元素
                int high = sorted.length - 1;  // 指向子数组中的最大元素
    
                while (low < high) {
        
    
                    if (sorted[i] + sorted[low] + sorted[high] > 0) {
        
                        high--;
                    } else if (sorted[i] + sorted[low] + sorted[high] < 0) {
        
                        low++;
                    } else {
        
                        // 合适的
                        System.out.println(sorted[i] + " + " + sorted[low] + " + " + sorted[high] + " = 0");
    
                        do {
        
                            low++;
                            high--;
                        } while (sorted[low] == sorted[low - 1] && sorted[high] == sorted[high + 1] && low < high);
                    }
                }
    
            }
        }
    
        public static void main(String[] args) {
        
    
            int[] array = {
        -1, 0, 1, 2, -1, -4};
            threeNumberSum(array);
    
        }
    
    }

运行结果

![在这里插入图片描述][855ea62ee2244f72a21a0b51b8869b33.png_pic_center]

###### 5 两个有序数组的交集 ######

【题目描述】给定两个有序整型数组array\_1 和 array\_2，数据元素递增且不重复，计算array\_1 和 array\_2 的交集。

这道题一上来，还是可以直接暴力，不过时间复杂度就O(n^2) 了。没有利用有序递增且不重复的条件。

同样，我们使用双指针法来解决这个为，两个指针分别在两个数组中移动，用变量i 指向array\_1 的array\_1\[0\]，变量j指向array\_2\[0\]，然后执行下面的操作：

1.  如果array\_1\[i\] = array\_2\[j\]，则该元素是交集元素，放到结果数组，i++，j++
2.  如果array\_1\[i\] > array\_2\[j\]，则j++，继续比较
3.  如果array\_1\[i\] < array\_2\[j\]，则i++，继续比较
4.  一旦i 等于数组 array\_1 的长度，或者j 等于array\_2 的长度，就终止循环。

Java 实现：

import java.util.Arrays;
    
    /**
     * @Projectname: JavaData_StructureAndAlgorithm
     * @Classname: TheIntersectionOfTwoOrderedArrays
     * @Author: Ding Jiaxiong
     * @Data:2023/3/15 15:05
     */
    
    public class TheIntersectionOfTwoOrderedArrays {
        
    
        public static int[] getIntersection(int[] array_1, int[] array_2) {
        
    
            int i = 0;
            int j = 0;
            int k = 0;
            int len = array_1.length > array_2.length ? array_2.length : array_1.length;
    
            int[] tmp = new int[len];
    
            while (i < array_1.length && j < array_2.length) {
        
                if (array_1[i] == array_2[j]) {
        
                    tmp[k] = array_1[i];
                    i++;
                    j++;
                    k++;
                }
    
                if (array_1[i] > array_2[j]) {
        
                    j++;
                }
                if (array_1[i] < array_2[j]) {
        
                    i++;
                }
            }
    
    
            int[] intersection = Arrays.copyOf(tmp, k);
            return intersection;
        }
    
        public static void main(String[] args) {
        
    
            int[] array_1 = {
        1, 2, 3, 5, 8, 9, 13};
            int[] array_2 = {
        2, 3, 9, 15, 19};
            int[] intersection = getIntersection(array_1, array_2);
    
            for (int i : intersection) {
        
                System.out.print(i + " ");
            }
        }
    
    }

运行结果

![在这里插入图片描述][8feeb5ec8e45400aad25b5ee9582f544.png_pic_center]

这样的双指针适用于一般情况下的求解两个有序数组的交集，其实如果两个数组长度相差悬殊，还有更好的办法，因为如果array\_1 里面只有3个元素\{1,100,10000\}，array\_2 里面有10000个元素\{1,2,3,…,9999,10000\}，如果直接用双指针，array\_2 会被整个儿遍历，但其实它们只有3个交集元素。

【更好的办法】实际上我们可以先遍历较小的数组，再将访问到的元素在长数组中进行二分查找。

Java实现如下：

import java.awt.dnd.InvalidDnDOperationException;
    import java.util.Arrays;
    
    /**
     * @Projectname: JavaData_StructureAndAlgorithm
     * @Classname: TheIntersectionOfTwoOrderedArraysV2
     * @Author: Ding Jiaxiong
     * @Data:2023/3/15 15:15
     */
    
    public class TheIntersectionOfTwoOrderedArraysV2 {
        
    
        public static int[] getIntersection(int[] array_1, int[] array_2) {
        
    
            int i, index, k = 0;
            int[] array_short;
            int[] array_long;
    
            if (array_1.length < array_2.length) {
        
                array_short = array_1;
                array_long = array_2;
            } else {
        
                array_short = array_2;
                array_long = array_1;
            }
    
            int[] tmp = new int[array_short.length];
    
            for (i = 0; i < array_short.length; i++) {
        
                index = binarySearch(array_long, array_short[i]);
                if (index != -1) {
        
                    tmp[k] = array_short[i];
                    k++;
                }
            }
    
            int[] intersection = Arrays.copyOf(tmp, k);
            return intersection;
    
        }
    
        private static int binarySearch(int[] array, int elem) {
        
    
            int low = 0, high = array.length - 1, mid;
            while (low <= high) {
        
    
                mid = (low + high) / 2;
                if (array[mid] == elem) {
        
                    return mid;
                } else if (elem > array[mid]) {
        
                    low = mid + 1;
                } else {
        
                    high = mid - 1;
                }
            }
    
            return -1; // 查找失败返回-1
        }
    
        public static void main(String[] args) {
        
    
            int[] array_1 = {
        1, 100, 10000};
    
            int[] array_2 = new int[10000];
            for (int i = 0; i < array_2.length; i++) {
        
                array_2[i] = i + 1;
            }
    
            int[] intersection = getIntersection(array_1, array_2);
            for (int i : intersection) {
        
                System.out.print(i + " ");
            }
        }
    
    }

运行结果

![在这里插入图片描述][f5b414486ecb4f3f807b6f2d96c28fd3.png_pic_center]

###### 6 最长公共前缀问题 ######

【问题描述】编写一个函数来查找字符串数组的最长公共前缀，如果不存在，则返回空字符串。

例如：\{“flower”,“flow”,“flight”\} ，函数返回"fl"

【思路分析】

*  如果只有两个字符串，那就将字符串从左往右一一比较，直到遇到不相同的字符，比较过的部分就是它们的最长公共前缀。
 *  如果有3个字符串，可以先计算第1个和第二个的最长公共前缀，再将得到的最长 公共前缀与第3个比，最后得到的就是这3个字符串的最长公共前缀。
 *  如果有更多的，相同方式划分下去

/**
     * @Projectname: JavaData_StructureAndAlgorithm
     * @Classname: LongestCommonPrefix
     * @Author: Ding Jiaxiong
     * @Data:2023/3/15 15:33
     */
    
    public class LongestCommonPrefix {
        
    
        public static String getLongestCommonPrefix(String[] array) {
        
            if (array.length == 1) {
        
                return array[0];
            }
    
            String commonPrefix = getCommonPrefix(array[0], array[1]);
            for (int i = 2; i < array.length; i++) {
        
                commonPrefix = getCommonPrefix(commonPrefix, array[i]);
            }
    
            return commonPrefix;
        }
    
        private static String getCommonPrefix(String str1, String str2) {
        
    
            StringBuffer res = new StringBuffer();
            for (int i = 0; i < Math.min(str1.length(), str2.length()); i++) {
        
                if (str1.charAt(i) == str2.charAt(i)) {
        
                    res.append(str1.charAt(i));
                } else {
        
                    return res.toString();
                }
            }
    
            return res.toString();
        }
    
        public static void main(String[] args) {
        
    
            String[] array = {
        "flower", "flow", "flight"};
            System.out.println(getLongestCommonPrefix(array));
    
        }
    
    }

运行结果

![在这里插入图片描述][538f1b20f5aa49e3a1f9d73e64773fb8.png_pic_center]

当然其实这个问题有着非常 明显的递归特性，递归实现如下：

/**
     * @Projectname: JavaData_StructureAndAlgorithm
     * @Classname: LongestCommonPrefixV2
     * @Author: Ding Jiaxiong
     * @Data:2023/3/15 15:40
     */
    
    public class LongestCommonPrefixV2 {
        
    
        public static String getLongestCommonPrefix(String[] array) {
        
            if (array.length == 1) {
        
                return array[0];
            }
    
            String[] subarray = new String[array.length - 1];
            System.arraycopy(array, 1, subarray, 0, array.length - 1);
    
            return getCommonPrefix(array[0], getLongestCommonPrefix(subarray));
        }
    
        private static String getCommonPrefix(String str1, String str2) {
        
    
            StringBuffer res = new StringBuffer();
            for (int i = 0; i < Math.min(str1.length(), str2.length()); i++) {
        
                if (str1.charAt(i) == str2.charAt(i)) {
        
                    res.append(str1.charAt(i));
                } else {
        
                    return res.toString();
                }
            }
    
            return res.toString();
        }
    
        public static void main(String[] args) {
        
    
            String[] array = {
        "flower", "flow", "flight"};
            System.out.println(getLongestCommonPrefix(array));
    
        }
    
    }

运行结果

![在这里插入图片描述][5eb418ccf0aa46eda908f2104c092285.png_pic_center]

###### 7 最长公共子串问题 ######

【问题描述】编写一个程序，再两个字符串中找出最长公共子串。

例如：A = “abcdefg”，B = “cdeab”，则最长公共子串为 “cde”，如果没有则返回null。这里约定两个字符串最多只有一个最长公共子串。

我们可以从较短的字符串出发，找出它的全部子串，然后在较长的字符串中查找是否存在这些子串。

在寻找子串的过程中，要本着“由长到短、逐步递减” 的原则，这样可以保证第 1 次得到的公共子串就是两字符串的最长公共子串。

Java 实现描述：

import sun.rmi.runtime.Log;
    
    /**
     * @Projectname: JavaData_StructureAndAlgorithm
     * @Classname: LongestCommonSubstring
     * @Author: Ding Jiaxiong
     * @Data:2023/3/15 16:06
     */
    
    public class LongestCommonSubstring {
        
    
        public static String getLongestCommonSubstring(String str1, String str2) {
        
    
            String longerStr, shorterStr, subStr;
    
            int i, j;
            if (str1 == null || str2 == null) {
        
                return null;
            }
            if (str1.length() <= str2.length()) {
        
                shorterStr = str1;
                longerStr = str2;
            } else {
        
                shorterStr = str2;
                longerStr = str1;
            }
    
            for (i = shorterStr.length(); i >= 1; i--) {
        
                for (j = 0; j <= shorterStr.length() - i; j++) {
        
                    subStr = shorterStr.substring(j, j + i);
    
                    if (longerStr.indexOf(subStr) != -1) {
        
                        return subStr;
                    }
                }
            }
    
            return null;
        }
    
        public static void main(String[] args) {
        
    
            String str1 = "abcdefg";
            String str2 = "acdef";
    
            System.out.println(getLongestCommonSubstring(str1, str2));
    
        }
    }

运行结果

![在这里插入图片描述][8187940cc96e47cc8b3fd29eac1be0e1.png_pic_center]

###### 8 长度最小的连续子数组 ######

【题目描述】给定一个含有n 个正整数的数组和一个正整数s，找出该数组中满足其和大于或等于 s 的长度最小的连续子数组。如果不存在，返回null。

例如：s = 7，nums = \{2,3,1,2,4,3\}，输出应该为\{4,3\}。

【方法一：锁定起点法】

在数组中锁定不同的元素，然后以该元素为起点向右扫描后续数组元素，并且在扫描过程中将数组元素累加求和。当和sum 大于或等于s 时就停止扫描，此时就找到了一个符合要求的子数组。全部扫描完成后，拿出长度最短的，即最终结果。

Java 实现：

import java.util.HashMap;
    import java.util.HashSet;
    
    /**
     * @Projectname: JavaData_StructureAndAlgorithm
     * @Classname: TheSmallestContinuousSubarray
     * @Author: Ding Jiaxiong
     * @Data:2023/3/15 16:21
     */
    
    public class TheSmallestContinuousSubarray {
        
    
        public static HashMap getMinSubArray(int s, int[] nums) {
        
    
            int start, end;
            int sum = 0;
    
            int minLen = nums.length + 1;
    
            HashMap<String, Integer> map = new HashMap<String, Integer>();
    
            for (start = 0; start < nums.length; start++) {
        
                sum = 0;
                for (end = start; end < nums.length && sum < s; end++) {
        
                    sum = nums[end] + sum;
                }
                end--;
    
                if (sum >= s && end - start + 1 < minLen) {
        
                    // 找到一个可能的解
                    minLen = end - start + 1;
                    map.put("start", start);
                    map.put("end", end);
                    map.put("length", minLen);
                }
            }
    
            if (minLen == nums.length + 1) {
        
                return null;
            }
    
            return map;
        }
    
        public static void main(String[] args) {
        
    
            int s = 7;
            int[] nums = {
        2, 3, 1, 2, 4, 3};
    
            System.out.println(getMinSubArray(s, nums));
    
        }
    
    }

运行结果：

![在这里插入图片描述][8fc92b12d669431ea39a771f37a135f1.png_pic_center]

当然其实这种办法的执行效率并不高，以我们这个栗子说明，nums = \{2,3,1,2,4,3\}, s =7，当 start = 1时，累加计算3 + 1+ 2 +4 = 10 > 7，但是其实在start = 0的时候，我们就已经算过了，2 + 3 + 1+ 2 = 8>7，就是说 3+ 1+2这部分重复计算了。这是影响算法性能的关键。

为了减少重复计算，使得算法执行效率更高，【滑动窗口】 来了。

所谓滑动窗口，就是利用指针(数组下标) start和end 分别框定一个窗口，让这个窗口按照一定的规律在数组或字符串上滑动，在滑动的过程中该窗口的宽度会不断调整，最终从字符串或者数组中找到符合要求的子串。

滑动窗口算法有固定的执行步骤，可以解决很多同类问题：

设置两个变量start 和 end，用这两个变量在数组( 或字符串)中框定一个窗口，只需要判断这个窗口的子数组( 或子串)是否满足条件：

1.  如果不满足，end 就一直递增，每次循环都要判断当前框定的子数组是否满足条件，如果满足，end就停止递增。
2.  start递增。每次循环都判断当前框定的子数组是否满足条件，如果不满足，start停止递增。
3.  重复1,2，直到start 遍历到数组末尾。

举个例子：nums = \{2,3,1,2,4,3\}，sum = 7。使用滑动窗口判断过程如下：

![在这里插入图片描述][f6bf68652058444a8de1006a1d00e098.png_pic_center]

最终minLen = 2，说明满足要求的最小子数组的长度为2，起始下标为4，终点下标为5.得到子数组为\{4,3\}

Java 代码实现：

import java.util.HashMap;
    
    /**
     * @Projectname: JavaData_StructureAndAlgorithm
     * @Classname: TheSmallestContinuousSubarrayV2
     * @Author: Ding Jiaxiong
     * @Data:2023/3/15 18:54
     */
    
    public class TheSmallestContinuousSubarrayV2 {
        
    
        public static HashMap<String, Integer> getMinSubArray(int s, int[] nums) {
        
            int start = 0, end = -1; //初始化start=0，end=-1
            int sum = 0;
            int minLen = nums.length + 1;
            HashMap<String, Integer> map = new HashMap<String, Integer>();
    
            while (start < nums.length) {
        
                if (end < nums.length - 1 && sum < s) {
        
                    //不满足sum>=s，并且end下标未到达数组尾部
                    end++;
                    sum = sum + nums[end];
                } else {
        
                    //满足了sum>=s，或者end已到数组尾部，则start开始向右移动
                    //直到不满足sum>=s或者start到达了数组尾部（left==nums.length）为止
                    sum = sum - nums[start];
                    start++;
                }
                if (sum >= s) {
        
                    //如果满足条件，则判断当前滑动窗口中子数组的长度
                    //是否比minLen还小，如果小于minLen则更新minLen的值
                    if (end - start + 1 < minLen) {
        
                        //找到了一个更小长度的结果，将子数组的起始坐标和长度更新到map中
                        minLen = end - start + 1;
                        map.put("start", start);
                        map.put("end", end);
                        map.put("length", minLen);
                    }
                }
            }
            if (minLen == nums.length + 1) {
        
                //没有找到答案,返回null
                return null;
            }
            return map;
        }
    
        public static void main(String[] args) {
        
            int[] nums = {
        2, 3, 1, 2, 4, 3};
            HashMap<String, Integer> map = getMinSubArray(7, nums);
            if (map != null) {
        
                System.out.println("The start index of subarray : " + map.get("start"));
                System.out.println("The end index of subarray : " + map.get("end"));
                System.out.println("The length of the subarray: " + map.get("length"));
            }
    
        }
    
    }

运行结果

![在这里插入图片描述][a84c7f87db0b42c28feb27816c3fa6dc.png_pic_center]

没问题。

###### 9 最长无重复子串 ######

【题目描述】给定一个字符串，找出不含有重复字符的最长子串的长度。

例如：

*  字符串"abcabcbb"，没有重复字符的最长子串是"abc"或者"bca"或者"cab"，长度为3
 *  字符串"bbbbb"，没有重复字符的最长子串是"b"，长度为1
 *  字符串"pwwkew"，没有重复字符的最长子串是"wke"，长度为3

其实这个问题和连续子数组特别像，都可以用滑动窗口的思想来做，时间复杂度为 O ( n ) O(n) O(n) 级别。

首先设置变量start 和 end，将end 和 start 初始化为0，然后判断由start 和 end框定的窗口中的子串是否满足条件。【满足条件：由start 和 end 框定的窗口中出现了重复的字符，当不满足条件时需要调整窗口的大小 end ++】

辅助变量：

*  HashSet set：一个Hash对象，用于存放子串元素并判断子串中是否有重复元素
 *  int maxLen：用于保存无重复子串的最大长度，这个值会随着无重复子串长度的变化而更新。

按照下面的步骤进行操作：

1.  如果不满足条件，即由start 和 end 框定的窗口中没有重复字符，则end 不断 + 1(将end 指向的字符加入滑动窗口)，同时将end 指向的字符str.charAt(end) 加入HashSet。当HashSet.add(str.charAt(end)) 返回值为false的时候，表示当前要加入HashSet 的字符与HashSet 中已有的字符重复，end 停止 +1
2.  将start 循环 + 1(将start 指向的字符从滑动窗口中移出)，同时将start 指向的字符 str.charAt(start) 从HashSet中移除。每执行一次循环操作，就试探地执行 HashSet.add(str.charAt(end))，当HashSet.add(str.charAt(end))的返回值为true时，表示再次不满足条件，start此时停止 +1.
3.  重复1,2，直到start 指向字符串的尾部。

Java 实现滑动窗口解法：

import java.util.HashMap;
    import java.util.HashSet;
    
    /**
     * @Projectname: JavaData_StructureAndAlgorithm
     * @Classname: LongestNon_repeatingSubstring
     * @Author: Ding Jiaxiong
     * @Data:2023/3/15 19:59
     */
    
    public class LongestNon_repeatingSubstring {
        
    
        public static int getSubstringLength(String str) {
        
    
            int start = 0;
            int end = 0;
    
            HashSet<Character> set = new HashSet<Character>();
            int maxLen = 0;
    
            while (start < str.length()) {
        
                if (end < str.length() && set.add(str.charAt(end))) {
        
                    // 不满足条件[没出现重复的字符], 则end 向右移动, 同时更新maxLen
                    if (end - start + 1 > maxLen) {
        
                        maxLen = end - start + 1;
                    }
                    end++;
                } else {
        
                    // end已经指向字符串尾部, 或者已经满足条件[出现重复的字符], 此时将start 指向的字符移出滑动窗口, 同时将该字符移出set
                    set.remove(str.charAt(start));
                    start++;
                }
            }
    
            return maxLen;
    
        }
    
        public static void main(String[] args) {
        
    
            String str = "abcdefgfabcdertqa";
            System.out.println(getSubstringLength(str));
    
        }
    
    }

运行结果

![在这里插入图片描述][19759789be4942dc91bec01741aaadba.png_pic_center]

这个字符串中的最长无重复子串为 “gfabcdertq”，长度为10

###### 10 删除字符数组中的特定字符 ######

【题目描述】编写一个效率尽可能高的函数，删除字符数组中的指定字符。函数的接口定义如下：

int removeChars(char[] srcStr, char[] removeStr)

*  srcStr：源字符数组
 *  removeStr：要从strStr中删除的字符组成的数组【不能有重复】
 *  返回值是删除后srcStr 的长度

这道题最直观最容易想到的做法是：扫描源字符数组srcStr，每当访问到strSrc中的一个字符时，都在字符数组 removeStr 中查找是否包含该字符。如果包含，就删掉，不包含，就继续扫描下一个字符。

当然我们这里就不讨论这种做法了，时间复杂度 O ( n 2 m ) O(n^2 m) O(n2m) 级别。

一种更为高效的删除字符串中特定字符的方法，算法核心思想就是只考虑将不需要删除的字符一次性的移动到它最终的位置上，而不考虑要删除的那些字符。

算法需要两个指针dst和src ，dst 指向该字符数组中字符最终要移动到的位置，src则指向当前正在扫描的字符。

如果当前正在扫描的字符srcStr\[src\] 不需要被删除，那就将srcStr\[src\] 赋值给srcStr\[dst\]，表示将字符srcStr\[src\] 移动到它最终的位置上，然后执行 dst++和src++，继续扫描数组中的下一个字符，如果当前正在扫描的字符srcStr\[src\] 需要被删除，则只执行src++，表示当前扫描的这个字符不会被移动到 srcStr\[dst\] 位置上，忽略它继续扫描下一个字符。

这样的算法时间复杂度仅为 O ( n ) O(n) O(n) 是比较理想的。

Java 实现：

import java.util.HashSet;
    
    /**
     * @Projectname: JavaData_StructureAndAlgorithm
     * @Classname: DeletesASpecificCharacterFromACharacterArray
     * @Author: Ding Jiaxiong
     * @Data:2023/3/15 20:29
     */
    
    public class DeletesASpecificCharacterFromACharacterArray {
        
    
        public static int removeChars(char[] srcStr, char[] removeStr) {
        
    
            int src = 0, dst = 0;
            HashSet set = new HashSet<Character>();
    
            for (int i = 0; i < removeStr.length; i++) {
        
                set.add(removeStr[i]); // 将removeStr 中的元素保存到HashSet
            }
    
            for (src = 0; src < srcStr.length; src++) {
        
                if (set.add(srcStr[src])) {
        
                    // srcStr[src]可以加入HashSet, 说明srcStr[src] 与 removeStr里面的元素不重复, 所以不需要删除
                    srcStr[dst] = srcStr[src];  // 将srcStr[src] 移动到最终位置上
                    dst++;
                    set.remove(srcStr[src]);
                }
            }
    
            return dst;
        }
    
        public static void main(String[] args) {
        
    
            char[] srcStr = {
        'a', 'e', 'a', 'b', 'f', 'e'};
            char[] removeStr = {
        'e', 'a'};
    
            int len = removeChars(srcStr, removeStr);
            System.out.println("删除后的结果如下: ");
    
            for (int i = 0; i < len; i++) {
        
                System.out.print(srcStr[i] + " ");
            }
    
        }
    
    }

运行结果

![在这里插入图片描述][db943c08fd58477a84f00cde944f2ef5.png_pic_center]

###### 11 最短连续子数组问题 ######

【题目描述】给定一个整数数组，请寻找一个连续的子数组，如果对这个子数组进行升序排列，那么整个数组都会变为升序排列，要求找到的子数组最短并输出它的长度。

例如，array\[7\] = \{2,4,7,6,11,8,19\}，输出的结果应该是4，因为最短连续子数组为\{7,6,11,8\}，如果将其升序排列后可得到\{6,7,8,11\}，这样整个数组就变为 \{2,4,6,7,8,11,19\}。

【思路分析】其实这个问题我们可以把这个数组看成三个部分，最左边都是小于【子数组】的而且递增的，最右边都是大于【子数组】的而且递增的，这样当我们把【子数组】中的元素从小到大排序后，整个数组就都会变得有序。

其实做法比较简单，我们只需要先将整个数组从小到大排列，再与原数组中的元素进行比较就可以找出最短连续子数组了。

Java 实现：

import java.util.Arrays;
    
    /**
     * @Projectname: JavaData_StructureAndAlgorithm
     * @Classname: ShortestContinuousSubarrayProblem
     * @Author: Ding Jiaxiong
     * @Data:2023/3/15 20:45
     */
    
    public class ShortestContinuousSubarrayProblem {
        
    
        public static int getContinuousSubArray(int[] array) {
        
    
            int[] tmpArray = new int[array.length];
            int start = 0;
            int end = 0;
    
            System.arraycopy(array, 0, tmpArray, 0, array.length);
            Arrays.sort(tmpArray);
    
            // 寻找起点
            for (int i = 0; i < array.length; i++) {
        
                if (array[i] != tmpArray[i]) {
        
                    start = i;
                    break;
                }
            }
            // 寻找终点
            for (int i = array.length - 1; i >= 0; i--) {
        
                if (array[i] != tmpArray[i]) {
        
                    end = i;
                    break;
                }
            }
    
            if (end == 0 && start == 0) {
        
                return 0;
            }
    
            return (end - start + 1);
        }
    
        public static void main(String[] args) {
        
            int[] a = {
        2, 4, 7, 6, 11, 8, 19};
    
            System.out.println(getContinuousSubArray(a));
    
        }
    
    }

运行结果

![在这里插入图片描述][d75c857980c14c9dbded9650ed07136c.png_pic_center]

没问题。

###### 12 字符数组的内容重排 ######

【题目描述】给定一个字符数组，数组中包括英文字母、数字、符号3类元素。要求在不额外开辟数组的前提下，将字符数组中的内容进行重新排列，经过处理后字符数组中的内容按照字母、数字、符号的顺序存放。另外要求稳定，即不改变同类在数组中的顺序。

例如：数组\{‘A’,‘$’,‘b’,‘3’,‘1’,‘\#’\}，重排后的数组为：\{‘A’,‘b’,‘3’,‘1’,‘$’,‘\#’\}

这里直接先给出一种非常巧妙的方法来解决，接着进行讲解。

/**
     * @Projectname: JavaData_StructureAndAlgorithm
     * @Classname: TheContentsOfTheCharacterArrayAreRearranged
     * @Author: Ding Jiaxiong
     * @Data:2023/3/15 20:55
     */
    
    public class TheContentsOfTheCharacterArrayAreRearranged {
        
    
        public static void parseCharArray(char[] array) {
        
    
            boolean changed = false;
            int n = array.length;
    
            do {
        
                changed = false;
                for (int i = 1; i < n; i++) {
        
                    if (compare(array[i - 1], array[i]) < 0) {
        
    
                        changed = true;
                        char tmp = array[i - 1];
                        array[i - 1] = array[i];
                        array[i] = tmp;
                    }
                }
                n--;
            } while (changed);
        }
    
        private static int compare(char a, char b) {
        
            if (isAlpha(a)) {
        
                if (isAlpha(b)) {
        
                    // a 和 b 都是字母, 返回0
                    return 0;
                } else {
        
                    // a 是字母, b 不是字母, 返回1
                    return 1;
                }
            } else if (isDigit(a)) {
        
                if (isAlpha(b)) {
        
                    // a是数字, b 是字母, 返回-1
                    return -1;
                } else if (isDigit(b)) {
        
                    // a数字,b数字, 返回0
                    return 0;
                } else {
        
                    // a数字,b 其他符号, 返回1
                    return 1;
                }
            } else {
        
                if (isAlpha(b) || isDigit(b)) {
        
                    return -1;  // a是其他, b是字母或数字, 返回-1
                } else {
        
                    return 0; // a是其他, b是其他, 返回0
                }
            }
        }
    
        private static boolean isAlpha(char c) {
         // 判断c 是否是字母
            if ((c >= 'a' && c <= 'z') || (c >= 'A' && c <= 'Z')) {
        
                return true;
            } else {
        
                return false;
            }
        }
    
        private static boolean isDigit(char c) {
         // 判断c是否是数字字符
            if (c >= '0' && c <= '9') {
        
                return true;
            } else {
        
                return false;
            }
        }
    
        public static void main(String[] args) {
        
    
            char[] array = {
        '1', 'w', '3', '5', 'a', 'b', '#', '&', '2', '$', 'p', '0'};
            parseCharArray(array);
    
            System.out.println(array);
    
        }
    
    }

运行结果

![在这里插入图片描述][7636c9d81a154619a0c990c8cefc7efd.png_pic_center]

实现是实现了，看着好像也不难，

其中compare 函数的比较规则如下表：

其实整个算法借鉴了冒泡排序，每一次内层的for循环都相当于冒泡排序中的一次排序过程。

当compare 返回-1时，交换字符a、b的位置，这样每次的内层for 循环都尽量将字母字符交换到数组的前端，将数字字符交换到数组中间，将其他字符交换到数组的后端。如果比较是同类，即返回0，就不动

###### 13 字符串数组类面试题解题技巧 ######

###### 【1】双指针法 ######

利用两个指针(数组下标)对数组进行遍历，应用场景：

*  数组元素的逆置问题
 *  基于元素有序的数组问题
 *  判断数组元素的对称性

###### 【2】锁定起点和滑动窗口 ######

从一个数组或字符串中找到某个符合要求的子数组或子串的问题。解决这类问题的常规方法就是锁定起点和滑动窗口。

*  锁定起点法：在数组中锁定不同的元素，然后以锁定的元素为起点向后扫描。即便是改进后的锁定起点，时间复杂度也是 O ( n 2 ) O(n^2) O(n2)
 *  滑动窗口：关注由起点start 和 终点end 框定的窗口内的子数组，当滑动窗口的长度发生改变时，判断当前子数组是否满足条件。所以滑动窗口的时间复杂度为 O ( n ) O(n) O(n)

###### 【3】字符串函数和容器类 ######

任何编程语言都会提供一些高效的字符串处理函数，利用好这些函数，可以写出简洁高效的代码。

还有就是容器类，像HashSet、HashMap，灵活利用，我们的程序可以更加的高效健壮。

###### 【4】排序算法 ######

当数组处于无序状态时，有些问题是很难解决的，所以要想得到、具有排序的思想。

[d548bde265f64a01ac7b38d66cf4238a.png_pic_center]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/25/a57f486833904fdaa8b3fca739cf2196.png
[36f4bc7174c34cd1af44a2447ad0c3fe.png_pic_center]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/25/afeeb02f5dc8470196511e7b0b3d22f1.png
[eee20fa439d943389c4f3783ce9a2c0a.png_pic_center]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/25/6ac5c7b634214080a06eb5dff80dd40b.png
[7fcbd872d47f4fdbb22f6a21979c7023.png_pic_center]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/25/11f2db3e1c4940e9beb765f26a745fff.png
[855ea62ee2244f72a21a0b51b8869b33.png_pic_center]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/25/5219bb5abaf4496c8e1dae86a7115a92.png
[8feeb5ec8e45400aad25b5ee9582f544.png_pic_center]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/25/ff384ccd217845a690503b0d7de9a0ae.png
[f5b414486ecb4f3f807b6f2d96c28fd3.png_pic_center]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/25/ef71ab25878a4030bca884f748872bdb.png
[538f1b20f5aa49e3a1f9d73e64773fb8.png_pic_center]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/25/a3dd3c8ca6fa4e2f9f78bfeac15e5273.png
[5eb418ccf0aa46eda908f2104c092285.png_pic_center]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/25/124d7817bf0e48cbbc41fea7f787b1e0.png
[8187940cc96e47cc8b3fd29eac1be0e1.png_pic_center]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/25/bcf0c440ee7c4cfa9f08f7c73902946f.png
[8fc92b12d669431ea39a771f37a135f1.png_pic_center]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/25/2cef9cefd20f4f22a2bededef31c56e7.png
[f6bf68652058444a8de1006a1d00e098.png_pic_center]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/25/a17d0c6793204d689114bd20c87908b8.png
[a84c7f87db0b42c28feb27816c3fa6dc.png_pic_center]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/25/8f77705d35244ee0a2d47dd3bb9c6564.png
[19759789be4942dc91bec01741aaadba.png_pic_center]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/25/60821c324ea54dab942cad906b3cfcdd.png
[db943c08fd58477a84f00cde944f2ef5.png_pic_center]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/25/0b63650d988d43afb88f605c0e1a0df1.png
[d75c857980c14c9dbded9650ed07136c.png_pic_center]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/25/51714e4fe7634fb881c0626820d61f07.png
[7636c9d81a154619a0c990c8cefc7efd.png_pic_center]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/25/15de0cd37fc94729b93f88c4b22f1ba9.png