数组和字符串（算法）

数组和列表、集合之间有什么不同？

集合：一个比较抽象的概念，集合里元素类型不一定相同，集合里的元素没有顺序。

列表：没有索引，有顺序，类型没有限制，地址可以相邻也可以不相邻。

数组：有索引，有顺序，类型相同，地址相同

数组中的查询
按位置查询。时间复杂度：O(1)。索引＋偏移量（下标）
按值查询。时间复杂度：O(N)。计算机不知道个位置处的值信息，需要一一查询判断。
数组添加元素时间复杂度：O(n)
删除元素：时间复杂度：O(n)

处理数组常用API

Arrays类：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
//Arrays.toString(数组)方法。方法作用：快速输出数组内容。

//Arrays.sort(数组)。方法运用:给数组排序，默认升序

//Arrays.sort(数组名，起始下标，排序个数)。对字符串进行排序时，是对每一个字符比较，而不是简单的比较长度

//Arrays.equals()方法。方法作用：比较两个数组内容是否相等

//Arrays.equals()是比较数组内容，而a.equals(b) 这样的方法是比较地址值

//Arrays.binarySearh(int[] nums,int target)。方法作用：在数组中查找指定值，若找到，则返回此值的下标，若没找到，返回 -插入点-1；

//Arrays.copyOf(T[] original, int newLength)。方法作用：拷贝数组，需要注意的是返回值是一个新数组，会改变接收这个新数组的引用的一些属性 

// from 表示开始位置， to 表示结束位置  
// 复制下标为 ：[from, to)
//Arrays.copyOfRange(int[] original, int from, int to)
//Arrays.sort()降序排列
Integer[] a = {1,2,3,4,5}
Arrays.sort(a,Collections.reverseOrder())
// 输出数组的内容即为：5 4 3 2 1，这种只能对包装类排序，如果要对基本数据类型需要自定义一个方法实实现Comparator接口的compare方法
//这里可以使用匿名内部类的方法实现重写，也可以使用Lambda表达式
Arrays.sort(a,(e1,e2) -> {return e2 - e1;});

Arrays.equals()的补充

为什么 Arrays.equals(a,b) 和 a.equals(b) 不同呢

因为：

数组是Object的子类，a.equals(b) 使用的是 Object 类的 equals 方法，是比较地址值的

而 Arrays 的equals()方法与Object的不同，它能够进行数组内容的比较

List接口中常用方法：
增加：add(int index, E element)
删除：remove(int index) remove(Object o)
修改：set(int index, E element)
查看：get(int index)

list.toArray(),list.size()

Math.random随机数、Math.abs绝对值、Math.ceil向上取值、Math.floor向下取值、Math.round四舍五入,Math.max,Math.min

String[] words = s.split(“ “, -1); // 按空格拆分，保留空字符串

trim() 是 Java 中 String 类的一个方法，用于去除字符串开头和结尾的空白字符。空白字符包括空格、制表符 (\t)、换行符 (\n)、回车符 (\r) 等。

.split() 是 Java 中 String 类的一个方法，用于将字符串按照指定的分隔符拆分成一个字符串数组。它是处理字符串的常用工具，特别适合用于解析文本、分割句子或单词等场景。

image-20250311121005343

数组

例题1：1991. 找到数组的中间位置 - 力扣（LeetCode）

题解：暴力破解O（n*n）

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
class Solution {
    public int findMiddleIndex(int[] nums) {
        //中间位置 左边相加=右边相加
        //如果中间位置是0下标 左边部分定义为0 如果中间位置是数组最长 右边定义和为0
        //如果不存在 返回-1
        if(nums.length == 1){
            return 0;
        }
        //暴力破解
        int result = 0;
        int leftTotal = 0;
        int rightTotal = 0;
        // 暴力一个个试
        for(int i = result ; i<nums.length;i++){
            leftTotal = leftAdd(nums,i);
            rightTotal = rightAdd(nums,i);
            if(leftTotal == rightTotal){
                result = i;
                return result;
            }
            result++;
        }
        return -1;
    }
    // 左相加函数,从0开始一直加，加到index,不包括index本身
    public int leftAdd(int[] nums, int index) {
        int leftTotal = 0;
        if(index == 0){
            return 0;
        }
        for (int i = 0; i < index; i++) {
            leftTotal += nums[i];
        }
        return leftTotal;
    }

    // 右相加函数
    public int rightAdd(int[] nums, int index) {
        int rightTotal = 0;
        if(index  == nums.length -1){
            return 0;
        }
        for (int i = index+1; i < nums.length; i++) {
            rightTotal += nums[i];
        }
        return rightTotal;
    }
}

例题2：前缀和O（n）

前缀和就是从位置1到位置i这个区间内的所有的数字之和。

前缀和的优势：以(o1)的时间复杂度得到某块区间的总和

一维数组前缀和：开辟一个比原数组大一个内存的数组，用来存放前n个元素的和（除了自己本身）

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
class Solution {
    public int findMiddleIndex(int[] nums) {
        if(nums.length == 1){
            return 0;
        }
        //结果下标
        int result = 0;
        //总和
        int total = 0;
        //右边总和
        int rightTotal = 0;
        for (int i = 0;i<nums.length;i++){
            total += nums[i];
        }
        //前缀和
        int[] nums2 = new int[nums.length+1];
        for(int i = 0;i < nums.length;i++){
            nums2[i+1] += (nums[i] + nums2[i]);
            rightTotal = total - nums2[i] - nums[i];
            if(nums2[i] == rightTotal){
                return i;
            }
        }
        return -1;
    }
}

例题3：搜索插入位置

给定一个排序数组和一个目标值，在数组中找到目标值，并返回其索引。如果目标值不存在于数组中，返回它将会被按顺序插入的位置。

请必须使用时间复杂度为 O(log n) 的算法。
链接：https://leetcode.cn/leetbook/read/array-and-string/cxqdh/

示例 1:

输入: nums = [1,3,5,6], target = 5
输出: 2
示例 2:

输入: nums = [1,3,5,6], target = 2
输出: 1
示例 3:

输入: nums = [1,3,5,6], target = 7
输出: 4

提示:

1 <= nums.length <= 104
-104 <= nums[i] <= 104
nums 为 无重复元素 的 升序 排列数组
-104 <= target <= 104

看到无重复元素，升序排序数组，就立刻想到二分

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
class Solution {
     public int searchInsert(int[] nums, int target) {
        int left = 0, right = nums.length - 1;
        while(left <= right) {
            int mid = (left + right) / 2;
            if(nums[mid] == target) {
                return mid;
            } else if(nums[mid] < target) {
                left = mid + 1;
            } else {
                right = mid - 1;
            }
        }
        return left;
    }
}

例题4：合并区间

以数组 intervals 表示若干个区间的集合，其中单个区间为 intervals[i] = [starti, endi] 。请你合并所有重叠的区间，并返回 一个不重叠的区间数组，该数组需恰好覆盖输入中的所有区间 。

链接：https://leetcode.cn/leetbook/read/array-and-string/c5tv3/

示例 1：

输入：intervals = [[1,3],[2,6],[8,10],[15,18]]
输出：[[1,6],[8,10],[15,18]]
解释：区间 [1,3] 和 [2,6] 重叠, 将它们合并为 [1,6].
示例 2：

输入：intervals = [[1,4],[4,5]]
输出：[[1,5]]
解释：区间 [1,4] 和 [4,5] 可被视为重叠区间。

提示：

1 <= intervals.length <= 104
intervals[i].length == 2
0 <= starti <= endi <= 104

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
class Solution {
    public int[][] merge(int[][] intervals) {
        if(intervals.length == 1 || intervals.length == 0){
            return intervals;
        }
        //先将二维数组的第一列进行升序排序
        Arrays.sort(intervals,(a, b) -> {return a[0] - b[0];});
        //结果数组
        List result = new ArrayList();
        //临时比较数组
        int[] temp = intervals[0];
        for(int i = 1;i<intervals.length;i++){
            if(temp[1] >= intervals[i][0]){
                temp[1] = Math.max(temp[1], intervals[i][1]);
            }else{
                result.add(temp);
                temp = intervals[i];
            }
        }
        result.add(temp);
        return (int[][])result.toArray(new int[result.size()][2]);
	}
}

二维数组

例题1：旋转图像

给定一个 n × n 的二维矩阵 matrix 表示一个图像。请你将图像顺时针旋转 90 度。

你必须在 原地 旋转图像，这意味着你需要直接修改输入的二维矩阵。请不要 使用另一个矩阵来旋转图像。

示例 1：

img

1
2
输入：matrix = [[1,2,3],[4,5,6],[7,8,9]]
输出：[[7,4,1],[8,5,2],[9,6,3]]

示例 2：

img

1
2
输入：matrix = [[5,1,9,11],[2,4,8,10],[13,3,6,7],[15,14,12,16]]
输出：[[15,13,2,5],[14,3,4,1],[12,6,8,9],[16,7,10,11]]

提示：

  • n == matrix.length == matrix[i].length
  • 1 <= n <= 20
  • -1000 <= matrix[i][j] <= 1000

方法1：辅助矩阵

如下图所示，矩阵顺时针旋转 90º 后，可找到以下规律：

「第i行」元素旋转到「第n−1−i列」元素；
「第j列」元素旋转到「第j行」元素；
因此，对于矩阵任意第i行、第j列元素matrix[i][j]，矩阵旋转 90º 后「元素位置旋转公式」为：

image-20250224182924460

根据以上「元素旋转公式」，考虑遍历矩阵，将各元素依次写入到旋转后的索引位置。但仍存在问题：在写入一个元素matrix[i][j]→matrix[j][n−1−i]后，原矩阵元素matrix[j][n−1−i]就会被覆盖（即丢失），而此丢失的元素就无法被写入到旋转后的索引位置了。

为解决此问题，考虑借助一个「辅助矩阵」暂存原矩阵，通过遍历辅助矩阵所有元素，将各元素填入「原矩阵」旋转后的新索引位置即可。

作者：Krahets
链接：https://leetcode.cn/problems/rotate-image/solutions/1228078/48-xuan-zhuan-tu-xiang-fu-zhu-ju-zhen-yu-jobi/
来源：力扣（LeetCode）

深拷贝 是指创建一个新的对象或数据结构，并将原始对象的所有内容（包括嵌套的对象或数据结构）完全复制到新对象中。深拷贝后的对象与原始对象完全独立，修改其中一个不会影响另一个。

深拷贝与浅拷贝的区别

  • 浅拷贝：只复制对象的最外层结构，如果对象内部包含其他对象（如数组、嵌套对象等），浅拷贝会共享这些内部对象的引用。因此，修改其中一个对象的内部数据会影响另一个对象。
  • 深拷贝：不仅复制最外层结构，还会递归地复制所有内部对象，确保新对象和原始对象完全独立。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
class Solution {
    public void rotate(int[][] matrix) {
        int n = matrix.length;
        int[][] temp = new int[n][];
        for(int i = 0;i < n ; i++){
            temp[i] = matrix[i].clone();                         
        }
        for(int i = 0;i<n;i++){
            for(int j = 0;j<n;j++){
                matrix[j][n-1-i] = temp[i][j];
            }
        }
    }
}

方法二：原地修改

考虑不借助辅助矩阵，通过在原矩阵中直接「原地修改」，实现空间复杂度O(1)的解法。

以位于矩阵四个角点的元素为例，设矩阵左上角元素A、右上角元素B、右下角元素C、左下角元素D。矩阵旋转 90º 后，相当于依次先后执行D→A,C→D,B→C,A→B修改元素，即如下「首尾相接」的元素旋转操作：A←D←C←B←A

image-20250224185236085

如上图所示，由于第1步D→A已经将A覆盖（导致A丢失），此丢失导致最后第4步A→B无法赋值。为解决此问题，考虑借助一个「辅助变量tmp」预先存储A，此时的旋转操作变为：

暂存 tmp=A
A←D←C←B←tmp

image-20250224185257826

image-20250224191601410

1
2
3
4
5
6
7
8
9
10
11
12
13
14
class Solution {
    public void rotate(int[][] matrix) {
        int n = matrix.length;
        for (int i = 0; i < n / 2; i++) {
            for (int j = 0; j < (n + 1) / 2; j++) {
                int tmp = matrix[i][j];
                matrix[i][j] = matrix[n - 1 - j][i];
                matrix[n - 1 - j][i] = matrix[n - 1 - i][n - 1 - j];
                matrix[n - 1 - i][n - 1 - j] = matrix[j][n - 1 - i];
                matrix[j][n - 1 - i] = tmp;
            }
        }
    }
}

例题2：零矩阵

编写一种算法，若M × N矩阵中某个元素为0，则将其所在的行与列清零。

示例 1：

输入：
[
[1,1,1],
[1,0,1],
[1,1,1]
]
输出：
[
[1,0,1],
[0,0,0],
[1,0,1]
]

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
class Solution {
    public void setZeroes(int[][] mat) {
        int h = mat.length, l = mat[0].length;
        boolean[] rows = new boolean[h], cols = new boolean[l];
        //分别用两个数组来记录行和列
        for (int i = 0; i < h; i++) {
            for (int j = 0; j < l; j++) {
                if (mat[i][j] == 0) rows[i] = cols[j] = true;
            }
        }
        
        //一次性置零
        for (int i = 0; i < h; i++) {
            for (int j = 0; j < l; j++) {
                if (rows[i] || cols[j]) mat[i][j] = 0;
            }
        }
    }
}

例题3：对角线遍历

给你一个大小为 m x n 的矩阵 mat ，请以对角线遍历的顺序，用一个数组返回这个矩阵中的所有元素。

image-20250224210525259

根据题目要求，矩阵按照对角线进行遍历。设矩阵的行数为 m, 矩阵的列数为 n, 我们仔细观察对角线遍历的规律可以得到如下信息:

一共有 m+n−1 条对角线，相邻的对角线的遍历方向不同，当前遍历方向为从左下到右上，则紧挨着的下一条对角线遍历方向为从右上到左下；

设对角线从上到下的编号为 i∈[0,m+n−2]：

当 i 为偶数时，则第 i 条对角线的走向是从下往上遍历；
当 i 为奇数时，则第 i 条对角线的走向是从上往下遍历；
当第 i 条对角线从下往上遍历时，每次行索引减 1，列索引加 1，直到矩阵的边缘为止：

当 i<m 时，则此时对角线遍历的起点位置为 (i,0)；
当 i≥m 时，则此时对角线遍历的起点位置为 (m−1,i−m+1)；
当第 i 条对角线从上往下遍历时，每次行索引加 1，列索引减 1，直到矩阵的边缘为止：

当 i<n 时，则此时对角线遍历的起点位置为 (0,i)；
当 i≥n 时，则此时对角线遍历的起点位置为 (i−n+1,n−1)；
根据以上观察得出的结论，我们直接模拟遍历所有的对角线即可。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
class Solution {
    public int[] findDiagonalOrder(int[][] mat) {
        int m = mat.length;
        int n = mat[0].length;
        int[] res = new int[m * n];
        int pos = 0;
        for (int i = 0; i < m + n - 1; i++) {
            if (i % 2 == 1) {
                int x = i < n ? 0 : i - n + 1;
                int y = i < n ? i : n - 1;
                while (x < m && y >= 0) {
                    res[pos] = mat[x][y];
                    pos++;
                    x++;
                    y--;
                }
            } else {
                int x = i < m ? i : m - 1;
                int y = i < m ? 0 : i - m + 1;
                while (x >= 0 && y < n) {
                    res[pos] = mat[x][y];
                    pos++;
                    x--;
                    y++;
                }
            }
        }
        return res;
    }
}

字符串

字符串有它自己的比较函数（我们将在下面的代码中向你展示比较函数的用法）。

然而，存在这样一个问题：

我们可以用 “==” 来比较两个字符串吗？

这取决于下面这个问题的答案：

我们使用的语言是否支持运算符重载？

如果答案是 yes （例如 C++、Python）。我们可以使用 == 来比较两个字符串；
如果答案是 no （例如 Java），我们可能无法使用 == 来比较两个字符串。当我们使用 == 时，它实际上会比较这两个对象是否是同一个对象。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
public class Main {
    public static void main(String[] args) {
        // 初始化
        String s1 = "Hello World";
        System.out.println("s1 是 \"" + s1 + "\"");
        String s2 = s1;
        System.out.println("s2 是 s1 的另一个引用。");
        String s3 = new String(s1);
        System.out.println("s3 是 s1 的一个副本。");

        // 使用 '==' 进行比较
        System.out.println("使用 '==' 进行比较：");
        // true，因为字符串是不可变的，且 s1 绑定到 "Hello World"
        System.out.println("s1 和 \"Hello World\": " + (s1 == "Hello World"));
        // true，因为 s1 和 s2 是同一个对象的引用
        System.out.println("s1 和 s2: " + (s1 == s2));
        // false，因为 s3 引用的是另一个新对象
        System.out.println("s1 和 s3: " + (s1 == s3));

        // 使用 'equals' 进行比较
        System.out.println("使用 'equals' 进行比较：");
        System.out.println("s1 和 \"Hello World\": " + s1.equals("Hello World"));
        System.out.println("s1 和 s2: " + s1.equals(s2));
        System.out.println("s1 和 s3: " + s1.equals(s3));

        // 使用 'compareTo' 进行比较
        System.out.println("使用 'compareTo' 进行比较：");
        System.out.println("s1 和 \"Hello World\": " + (s1.compareTo("Hello World") == 0));
        System.out.println("s1 和 s2: " + (s1.compareTo(s2) == 0));
        System.out.println("s1 和 s3: " + (s1.compareTo(s3) == 0));
    }
}

连接操作

对于不同的编程语言中，字符串可能是可变的，也可能是不可变的。不可变意味着一旦字符串被初始化，你就无法改变它的内容。

在某些语言（如 C ++）中，字符串是可变的。 也就是说，你可以像在数组中那样修改字符串。
在其他一些语言（如 Java、Python）中，字符串是不可变的。

在 字符串不可变 的语言中，进行字符串的连接操作则会带来一些问题。

显然，不可变字符串无法被修改。哪怕你只是想修改其中的一个字符，也必须创建一个新的字符串。我们以 Java 为例，来看一个在 for 循环中重复进行字符串连接的例子：

1
2
3
4
5
6
7
8
9
public class Main {
    public static void main(String[] args) {
        String s = "";
        int n = 10000;
        for (int i = 0; i < n; i++) {
            s += "hello";
        }
    }
}

然而，对于 Java来说，由于字符串是不可变的，因此在连接时首先为新字符串分配足够的空间，复制旧字符串中的内容并附加到新字符串。因此，总时间复杂度将是：𝑂(𝑁2)。

针对 Java 中出现的此问题，我们提供了以下解决方案：

如果你确实希望你的字符串是可变的，则可以使用 toCharArray 将其转换为字符数组。
如果你经常必须连接字符串，最好使用一些其他的数据结构，如 StringBuilder 。

StringBuilder类

字符串的分类：

1、不可变字符串：String

.charAt()查找改下标下的字符，toCharArray()将string变成char数组,toString()，trim()可以删除首尾空格。

2、可变字符串：StringBuilder、StringBuffer

StringBuilder常用方法：

.append增加、.delete删除、deleteCharAt()、.insert(3,”，”)插入、replace(3,5，“我好累”)替换、.substring(2,4)查找、

例题

例题1：最长公共前缀

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

如果不存在公共前缀，返回空字符串 ""。

示例 1：

输入：strs = [“flower”,”flow”,”flight”]
输出：”fl”
示例 2：

输入：strs = [“dog”,”racecar”,”car”]
输出：””
解释：输入不存在公共前缀。

提示：

1 <= strs.length <= 200
0 <= strs[i].length <= 200
strs[i] 如果非空，则仅由小写英文字母组成

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
class Solution {
    public String longestCommonPrefix(String[] strs) {
        if(strs.length == 0){
            return "";
        }
        //将第一个英文当做比较，由于是找公共前缀所以找谁当第一个都可以
        String ans = strs[0];
        for(int i = 0; i < strs.length ; i++){
            int j = 0;
            for(;j < strs[i].length() && j < ans.length(); j++){
                if(ans.charAt(j) != strs[i].charAt(j)){
                    break;
                }
            }
            ans = ans.substring(0,j);
            if(ans.equals(""))
                return "";
        }
        return ans;
    }
}

例题2：最长回文子串

给你一个字符串 s，找到 s 中最长的 回文 子串。

示例 1：

输入：s = “babad”
输出：”bab”
解释：”aba” 同样是符合题意的答案。
示例 2：

输入：s = “cbbd”
输出：”bb”

提示：

1 <= s.length <= 1000
s 仅由数字和英文字母组成

解法1：暴力

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
class Solution {
    public String longestPalindrome(String s) {
        //先获取字符串的长度，如果小于2直接返回
        int len = s.length();
        if(len < 2){
            return s;
        }
        int maxLen = 1;
        int begin = 0;
        char[] charArray = s.toCharArray();
        for(int i = 0 ; i < len - 1 ; i++){
            for(int j = i + 1 ; j < len ; j ++){
                if(j - i + 1 > maxLen && valid(charArray,i,j)){
                    maxLen = j - i + 1;
                    begin = i;
                }
            }
        }
        return s.substring(begin,begin+maxLen);

    }
    //验证回文子串
    public boolean valid(char[] charArray , int left, int right){
        while(left < right){
            if(charArray[left] != charArray[right]){
                return false;
            }
            left++;
            right--;
        }
        return true;
    } 
}

解法2：动态规划

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
class Solution {
    public String longestPalindrome(String s) {
        if(s.length() < 2){
            return s;
        }
        //利用动态规划的想法
        char[] s1 = s.toCharArray();
        int len = s.length();
        int maxLen = 1;
        int begin = 0;
        //初始化表格
        boolean[][] dp = new boolean[len][len];
        for(int i = 0 ; i < len ; i++){
            dp[i][i] = true;
        }
        //画图画右上角
        for(int j = 1 ; j < len ; j++){
            for(int i = 0 ; i < j ; i ++){
                if(s.charAt(j) != s.charAt(i)){
                    dp[i][j] = false;
                }else{
                    //如果距离小于三，由于头和尾在上一个判断中已经确认相同，所以肯定是回文
                    if(j - i < 3){
                        dp[i][j] = true;
                    }else{
                        //如果距离大于3，那么就看上一步是否相等
                        //比如1和4位置相等，就要看2和3是否相等来决定是否是回文
                        dp[i][j] = dp [i+1][j-1];
                    }
                }
				//更新状态
                if(dp[i][j] && j - i + 1 > maxLen){
                    maxLen = j - i + 1;
                    begin = i;
                }
            }
        }
        return s.substring(begin,begin + maxLen);
    }
}

解法3：中心扩散法

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
public class Solution {

    public String longestPalindrome(String s) {
        if(s.length() < 2) return s;
        int len = s.length();
        //0放起始位置,1放长度
        int[] result = new int[2];
        //存放最大长度
        int maxLen = 0;
        for(int i = 0; i < len -1 ; i++){
            int[] ji = spread(s,i,i);
            int[] ou = spread(s,i,i+1);
            int[] temp = ji[1] > ou[1] ? ji : ou;
            if(temp[1] > maxLen){
                maxLen = temp[1];
                result = temp;
            }
        }
        return s.substring(result[0],result[0] + result[1]);

    }

    public int[] spread(String s,int left ,int right){
        while(left >= 0 && right < s.length()){
            if(s.charAt(left) == s.charAt(right)){
                left--;
                right++;
            }else{
                break;
            }
        }
        return new int[]{left + 1,right - left - 1};
    }
}


例题3：翻转字符串里的单词

给你一个字符串 s ，请你反转字符串中 单词 的顺序。

单词 是由非空格字符组成的字符串。s 中使用至少一个空格将字符串中的 单词 分隔开。

返回 单词 顺序颠倒且 单词 之间用单个空格连接的结果字符串。

注意：输入字符串 s中可能会存在前导空格、尾随空格或者单词间的多个空格。返回的结果字符串中，单词间应当仅用单个空格分隔，且不包含任何额外的空格。

示例 1：

输入：s = “the sky is blue”
输出：”blue is sky the”
示例 2：

输入：s = “ hello world “
输出：”world hello”
解释：反转后的字符串中不能存在前导空格和尾随空格。
示例 3：

输入：s = “a good example”
输出：”example good a”
解释：如果两个单词间有多余的空格，反转后的字符串需要将单词间的空格减少到仅有一个。

提示：

1 <= s.length <= 104
s 包含英文大小写字母、数字和空格 ‘ ‘
s 中 至少存在一个 单词

链接：https://leetcode.cn/leetbook/read/array-and-string/crmp5/

1
2
3
4
5
6
7
8
9
10
11
12
13
14
class Solution {
    public String reverseWords(String s) {
        s = s.trim();                                    // 删除首尾空格
        int j = s.length() - 1, i = j;
        StringBuilder res = new StringBuilder();
        while (i >= 0) {
            while (i >= 0 && s.charAt(i) != ' ') i--;     // 搜索首个空格
            res.append(s.substring(i + 1, j + 1) + " "); // 添加单词
            while (i >= 0 && s.charAt(i) == ' ') i--;     // 跳过单词间空格
            j = i;                                       // j 指向下个单词的尾字符
        }
        return res.toString().trim();                    // 转化为字符串并返回
    }
}

例题4：字符串匹配算法：KMP

最浅显易懂的 KMP 算法讲解_哔哩哔哩_bilibili

文字版：

字符串匹配说的是在一个S字符串判断另一个字符串T是否能成为他的子串image-20250227083733396

第一种BF就是暴力破解从第一个字符开始比较，假设S的指针i，T有个指针j，这时候i和j都从0开始，当i=4，j=4的时候不匹配，这时候i从1开始，j从=0开始继续遍历直到匹配成功，否则就匹配失败。

时间复杂度是O（m*n）

这里有个可以优化的点就是前面的A其实已经遍历过了，如何让T跳过匹配过的字符直接跳过若干个字符来进行匹配呢？

这个时候有个KMP算法：主要理念是如何不让i返回，一直线性的扫描下去。

image-20250227085658582

我们是否可以跳过前面两个字符

image-20250227085730577

这样便可以实现接下去的匹配了呢。

那这个时候我们如何来决定跳过多少个字符呢？

next数组来解决这个问题，next数组是最长公共前后缀数组。

先看一下next的功能，当最后一个字符匹配失败的时候我们会去看，最有一个匹配成功的字符的next值。比如这里C前面的B的next值是2，这样我们就将子串往后移动2个字符继续进行匹配。

image-20250227090139211

为什么是2呢，next数组的本质是除了子串本身最长的公共前后缀

image-20250227090412599

下一个问题是next数组如何产生？

我们利用递推，假设我们比到AB的时候发现下一个字符是A还是匹配，直接最长公共前后缀长度+1即可，在下一个B和C不匹配，这时候我们在ABA里面查找是否存在更短的前后缀，因为A是有可能和下一个字符产生公共前后缀的，而前面三个已经比较过了，前后缀是1也就是A，然后继续匹配下去。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
public int[] buildNext(String needle) {
        int len = needle.length();
        if (len == 0) return new int[0]; // 如果模式串为空，返回空数组

        int[] next = new int[len]; // 初始化 next 数组
        char[] chars = needle.toCharArray();

        // 初始化 j 指向前缀末尾，i 指向后缀末尾
        int j = 0; // j 表示前缀的长度
        for (int i = 1; i < len; i++) {
            // 当前字符不匹配时，回退 j 指针
            while (j > 0 && chars[i] != chars[j]) {
                j = next[j - 1];
            }

            // 如果当前字符匹配，则更新 j
            if (chars[i] == chars[j]) {
                j++;
            }

            // 将 j 的值赋给 next[i]
            next[i] = j;
        }
        return next;
    }

完整 的KMP

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
class Solution {
    public int strStr(String haystack, String needle) {
        //haystack是主串，needle是子串
        int[] next = buildNext(needle);
        char[] chars1 = haystack.toCharArray();
        char[] chars2 = needle.toCharArray();
        int j = 0;
        int i = 0;
        while(i < chars1.length ){
            if(chars1[i] == chars2[j]){
                i++;
                j++;
                if(j == chars2.length){
                    i = i - j;
                    break;
                }
            }else{
                if(j == 0){
                    i++;
                }else{
                    j = next[j - 1];
                }
            }
        }
        return i == chars1.length ? -1 : i;
    }
    public int[] buildNext(String needle) {
        int len = needle.length();
        if (len == 0) return new int[0]; // 如果模式串为空，返回空数组

        int[] next = new int[len]; // 初始化 next 数组
        char[] chars = needle.toCharArray();

        // 初始化 j 指向前缀末尾，i 指向后缀末尾
        int j = 0; // j 表示前缀的长度
        for (int i = 1; i < len; i++) {
            // 当前字符不匹配时，回退 j 指针
            while (j > 0 && chars[i] != chars[j]) {
                j = next[j - 1];
            }

            // 如果当前字符匹配，则更新 j
            if (chars[i] == chars[j]) {
                j++;
            }

            // 将 j 的值赋给 next[i]
            next[i] = j;
        }
        return next;
    }
}

双指针

例题1：反转字符串

编写一个函数，其作用是将输入的字符串反转过来。输入字符串以字符数组 s 的形式给出。

不要给另外的数组分配额外的空间，你必须原地修改输入数组、使用 O(1) 的额外空间解决这一问题。

示例 1：

输入：s = [“h”,”e”,”l”,”l”,”o”]
输出：[“o”,”l”,”l”,”e”,”h”]
示例 2：

输入：s = [“H”,”a”,”n”,”n”,”a”,”h”]
输出：[“h”,”a”,”n”,”n”,”a”,”H”]

提示：

1 <= s.length <= 105
s[i] 都是 ASCII 码表中的可打印字符

双指针解法：

1
2
3
4
5
6
7
8
9
10
11
12
13
class Solution {
    public void reverseString(char[] s) {
        int l = 0;//左指针
        int r = s.length - 1;//右指针
        while(l <= r){
            char temp = s[l];
            s[l] = s[r];
            s[r] = temp;
            l++;
            r--;
        }
    }
}

例题2：数组的拆分

给定长度为 2n 的整数数组 nums ，你的任务是将这些数分成 n 对, 例如 (a1, b1), (a2, b2), …, (an, bn) ，使得从 1 到 n 的 min(ai, bi) 总和最大。

返回该 最大总和 。

示例 1：

输入：nums = [1,4,3,2]
输出：4
解释：所有可能的分法（忽略元素顺序）为：

  1. (1, 4), (2, 3) -> min(1, 4) + min(2, 3) = 1 + 2 = 3
  2. (1, 3), (2, 4) -> min(1, 3) + min(2, 4) = 1 + 2 = 3
  3. (1, 2), (3, 4) -> min(1, 2) + min(3, 4) = 1 + 3 = 4
    所以最大总和为 4
    示例 2：

输入：nums = [6,2,6,5,1,2]
输出：9
解释：最优的分法为 (2, 1), (2, 5), (6, 6). min(2, 1) + min(2, 5) + min(6, 6) = 1 + 2 + 6 = 9

提示：

1 <= n <= 104
nums.length == 2 * n
-104 <= nums[i] <= 104

1
2
3
4
5
6
7
8
9
10
11
class Solution {
    public int arrayPairSum(int[] nums) {
        //排序后就完成了划分;
        Arrays.sort(nums);
        int total = 0;
        for(int i = 0 ; i < nums.length - 1 ; i+=2){
            total += Math.min(nums[i],nums[i+1]);
        }
        return total;
    }
}

例题3：两数之和 II - 输入有序数组

给你一个下标从 1 开始的整数数组 numbers ，该数组已按 非递减顺序排列 ，请你从数组中找出满足相加之和等于目标数 target 的两个数。如果设这两个数分别是 numbers[index1] 和 numbers[index2] ，则 1 <= index1 < index2 <= numbers.length 。

以长度为 2 的整数数组 [index1, index2] 的形式返回这两个整数的下标 index1 和 index2。

你可以假设每个输入 只对应唯一的答案 ，而且你 不可以 重复使用相同的元素。

你所设计的解决方案必须只使用常量级的额外空间。

示例 1：

输入：numbers = [2,7,11,15], target = 9
输出：[1,2]
解释：2 与 7 之和等于目标数 9 。因此 index1 = 1, index2 = 2 。返回 [1, 2] 。
示例 2：

输入：numbers = [2,3,4], target = 6
输出：[1,3]
解释：2 与 4 之和等于目标数 6 。因此 index1 = 1, index2 = 3 。返回 [1, 3] 。
示例 3：

输入：numbers = [-1,0], target = -1
输出：[1,2]
解释：-1 与 0 之和等于目标数 -1 。因此 index1 = 1, index2 = 2 。返回 [1, 2] 。

提示：

2 <= numbers.length <= 3 * 104
-1000 <= numbers[i] <= 1000
numbers 按 非递减顺序 排列
-1000 <= target <= 1000
仅存在一个有效答案

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
class Solution {
    public int[] twoSum(int[] numbers, int target) {
        // 思想首部尾部相加，如果小于目标值，首部后移，如果等于直接返回，如果小于，尾部前移
        int[] result = new int[2];
        int len = numbers.length;
        int temp = numbers[0] + numbers[len - 1];
        if (temp == target) {
            result[0] = 1;
            result[1] = len;
            return result;
        }
        int l = 0;//左指针
        int r = len - 1;//右指针
        while(temp != target) {
            while(temp < target) {
                // 首部后移
                l++;
                temp = numbers[l] + numbers[r];
                if (temp == target) {
                    result[0] = l + 1;
                    result[1] = r + 1;
                    return result;
                }
            }
            while(temp > target) {
                // 尾部前移
                r--;
                temp = numbers[l] + numbers[r];
                if (temp == target) {
                    result[0] = l + 1;
                    result[1] = r + 1;
                    return result;
                }
            }
        }
        return result;
    }
}

双指针之快慢针

有时，我们可以使用两个不同步的指针来解决问题，即快慢指针。与情景一不同的是，两个指针的运动方向是相同的，而非相反。

让我们从一个经典问题开始：

给你一个数组 nums 和一个值 val，你需要 原地 移除所有数值等于 val 的元素，并返回移除后数组的新长度。

如果我们没有空间复杂度上的限制，那就更容易了。我们可以初始化一个新的数组来存储答案。如果元素不等于给定的目标值，则迭代原始数组并将元素添加到新的数组中。

image-20250228180003527

实际上，它相当于使用了两个指针，一个用于原始数组的迭代，另一个总是指向新数组的最后一个位置。

考虑空间限制
如果我们不使用额外的数组，只是在原数组上进行操作呢？

此时，我们就可以采用快慢指针的思想：初始化一个快指针 fast 和一个慢指针 slow，fast 每次移动一步，而 slow 只当 fast 指向的值不等于 val 时才移动一步。

例题1：移出元素

给你一个数组 nums 和一个值 val，你需要 原地 移除所有数值等于 val 的元素。元素的顺序可能发生改变。然后返回 nums 中与 val 不同的元素的数量。

假设 nums 中不等于 val 的元素数量为 k，要通过此题，您需要执行以下操作：

更改 nums 数组，使 nums 的前 k 个元素包含不等于 val 的元素。nums 的其余元素和 nums 的大小并不重要。
返回 k。

用户评测：

评测机将使用以下代码测试您的解决方案：

int[] nums = […]; // 输入数组
int val = …; // 要移除的值
int[] expectedNums = […]; // 长度正确的预期答案。
// 它以不等于 val 的值排序。

int k = removeElement(nums, val); // 调用你的实现

assert k == expectedNums.length;
sort(nums, 0, k); // 排序 nums 的前 k 个元素
for (int i = 0; i < actualLength; i++) {
assert nums[i] == expectedNums[i];
}
如果所有的断言都通过，你的解决方案将会 通过。

示例 1：

输入：nums = [3,2,2,3], val = 3
输出：2, nums = [2,2,,]
解释：你的函数函数应该返回 k = 2, 并且 nums 中的前两个元素均为 2。
你在返回的 k 个元素之外留下了什么并不重要（因此它们并不计入评测）。
示例 2：

输入：nums = [0,1,2,2,3,0,4,2], val = 2
输出：5, nums = [0,1,4,0,3,,,_]
解释：你的函数应该返回 k = 5，并且 nums 中的前五个元素为 0,0,1,3,4。
注意这五个元素可以任意顺序返回。
你在返回的 k 个元素之外留下了什么并不重要（因此它们并不计入评测）。

提示：

0 <= nums.length <= 100
0 <= nums[i] <= 50
0 <= val <= 100

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
class Solution {
    public int removeElement(int[] nums, int val) {
        int fast = 0;//初始化快指针
        int slow = 0;//初始化慢指针
        int len = nums.length;
        while(fast < len){
            if(nums[slow] != val){
                slow++;
                fast++;
                if(fast == len){
                    return slow;
                }
            }
            if(nums[slow] == val){
                while(nums[fast] == val ){
                    fast++;
                    if(fast == len){
                        return slow;
                    }
                    if(nums[fast] != val){
                        int temp = nums[fast];
                        nums[fast] = nums[slow];
                        nums[slow] = temp;
                        fast = slow;
                        break;
                    }
                }
            }
        }
        return slow;
    }
}

例题2：最大连续的1的个数

给定一个二进制数组 nums ， 计算其中最大连续 1 的个数。

示例 1：

输入：nums = [1,1,0,1,1,1]
输出：3
解释：开头的两位和最后的三位都是连续 1 ，所以最大连续 1 的个数是 3.
示例 2:

输入：nums = [1,0,1,1,0,1]
输出：2

提示：

1 <= nums.length <= 105
nums[i] 不是 0 就是 1.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
class Solution {
    public int findMaxConsecutiveOnes(int[] nums) {
        //int fast = 0;
        int needle = 0;
        int temp = 0;
        int result = 0;
        //如果指针小于数组长度
        while(needle < nums.length) {
            //遇到0前面的1
            while(nums[needle] == 1) {
                needle++;
                temp++;
                if(needle == nums.length) {
                    // 更新结果
                    result = Math.max(temp, result);
                    return result;
                }
            }
            // 更新结果
            result = Math.max(temp, result);
            // 遇到0
            if(nums[needle] == 0) {
                needle++;
                temp = 0;
            }
        }
        return result;
    }
}

例题3：长度最小的子数组

给定一个含有 n 个正整数的数组和一个正整数 target 。

找出该数组中满足其总和大于等于 target 的长度最小的 子数组 [numsl, numsl+1, …, numsr-1, numsr] ，并返回其长度。如果不存在符合条件的子数组，返回 0 。

示例 1：

输入：target = 7, nums = [2,3,1,2,4,3]
输出：2
解释：子数组 [4,3] 是该条件下的长度最小的子数组。
示例 2：

输入：target = 4, nums = [1,4,4]
输出：1
示例 3：

输入：target = 11, nums = [1,1,1,1,1,1,1,1]
输出：0

提示：

1 <= target <= 109
1 <= nums.length <= 105
1 <= nums[i] <= 104

进阶：

如果你已经实现 O(n) 时间复杂度的解法, 请尝试设计一个 O(n log(n)) 时间复杂度的解法。

暴力破解：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
class Solution {
    public int minSubArrayLen(int target, int[] nums) {
        int temp = 0;
        int result = Integer.MAX_VALUE;
        int len = 0;
        for(int i = 0; i < nums.length ; i++ ){
            temp = 0;
            len = 0;
            for(int j = i; j < nums.length ; j++){
                temp += nums[j];
                len++;
                if(temp >= target){
                    result = Math.min(len,result);
                    break;   //  跳出当前循环
                }
            }
        }
        if(result == Integer.MAX_VALUE){
            return 0;
        }else{
            return result;
        }
    }
}

但是会超时。

所以用其他方法。

滑动窗口方法。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
class Solution {
    public int minSubArrayLen(int s, int[] nums) {
        int n = nums.length;
        if (n == 0) {
            return 0;
        }
        int ans = Integer.MAX_VALUE;
        int start = 0, end = 0;
        int sum = 0;
        while (end < n) {
            sum += nums[end];
            while (sum >= s) {
                ans = Math.min(ans, end - start + 1);
                sum -= nums[start];
                start++;
            }
            end++;
        }
        return ans == Integer.MAX_VALUE ? 0 : ans;
    }
}

小结

例题1：杨辉三角

给定一个非负整数 numRows，生成「杨辉三角」的前 numRows 行。

在「杨辉三角」中，每个数是它左上方和右上方的数的和。

示例 1:

输入: numRows = 5
输出: [[1],[1,1],[1,2,1],[1,3,3,1],[1,4,6,4,1]]
示例 2:

输入: numRows = 1
输出: [[1]]

提示:

1 <= numRows <= 30

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
class Solution {
    public List<List<Integer>> generate(int numRows) {
        //这个很像动态规划，结果由上一步决定,所以其实就是画表格
        //先初始化
        List<List<Integer>> dp = new ArrayList<>();
        for (int i = 0; i < numRows; i++) {
            dp.add(new ArrayList<>()); // 为每一行添加一个新的子列表
            for (int j = 0; j <= i; j++) {
                if (j == 0 || j == i) {
                    // 每一行的开头和末尾都是 1
                    dp.get(i).add(1);
                } else {
                    // 中间的值由上一行的两个值相加得到
                    int value1 = dp.get(i - 1).get(j - 1);
                    int value2 = dp.get(i - 1).get(j);
                    dp.get(i).add(value1 + value2);
                }
            }
        }
        return dp;
    }
}

上面的解法和下面的一样，只是下面的会快一点，思路是先用int数组解决，再一个个赋值给结果

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
class Solution {
    public List<List<Integer>> generate(int numRows) {
		List<List<Integer>> result=new ArrayList<List<Integer>>();
		int[][] dp=new int[numRows][numRows];
		dp[0][0]=1;
		for (int i = 1; i < numRows; i++) {
			for (int j = 0; j <=i; j++) {
				if(j==0)dp[i][j]=1;
				else dp[i][j]=dp[i-1][j-1]+dp[i-1][j];
			}
		}
		for (int i = 0; i < dp.length; i++) {
			List<Integer> tmp=new ArrayList<>();
			for (int j = 0; j < dp.length; j++) {
				if(dp[i][j]==0) break;
				tmp.add(dp[i][j]);
			}
			result.add(new ArrayList<>(tmp));
		}
		
		return result;
    }
}

例题2：杨辉三角2

给定一个非负索引 rowIndex，返回「杨辉三角」的第 rowIndex 行。

在「杨辉三角」中，每个数是它左上方和右上方的数的和。

示例 1:

输入: rowIndex = 3
输出: [1,3,3,1]
示例 2:

输入: rowIndex = 0
输出: [1]
示例 3:

输入: rowIndex = 1
输出: [1,1]

提示:

0 <= rowIndex <= 33

解法一就是把整个画出来然后提取该行，解法二就是只用一个长度为rowIndex + 1的数组存储即可

image-20250301155135866

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
//这里传进来的rowIndex至少是1
    public List<Integer> getRow(int rowIndex) {
        List<Integer> result = new ArrayList<>(rowIndex + 1);
        for (int i = 0; i <= rowIndex; i++) {
            result.add(1); // 初始化列表为 [1, 1, 1, ..., 1]
        }

        for (int i = 1; i <= rowIndex; i++) {
            for (int j = i - 1; j > 0; j--) {
                result.set(j, result.get(j) + result.get(j - 1));
            }
        }

        return result;
    }

递归版本最快

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
class Solution {
    
    public static List<Integer> getRow(int rowIndex) {
        List<Integer> result = new ArrayList<>(rowIndex + 1);
        for (int i = 0; i <= rowIndex; i++) {
            result.add(1); // 初始化列表为 [1, 1, 1, ..., 1]
        }
        generate(result, rowIndex); // 调用递归函数
        return result;
    }

    private static void generate(List<Integer> result, int rowIndex) {
        if (rowIndex == 0) {
            return; // 递归终止条件
        }
        generate(result, rowIndex - 1); // 递归生成上一行
        for (int j = rowIndex - 1; j > 0; j--) {
            result.set(j, result.get(j) + result.get(j - 1)); // 更新当前行的值
        }
    }
}

例题3：反转字符串中的单词3

给定一个字符串 s ，你需要反转字符串中每个单词的字符顺序，同时仍保留空格和单词的初始顺序。

示例 1：

输入：s = “Let’s take LeetCode contest”
输出：”s’teL ekat edoCteeL tsetnoc”
示例 2:

输入： s = “Mr Ding”
输出：”rM gniD”

提示：

1 <= s.length <= 5 * 104
s 包含可打印的 ASCII 字符。
s 不包含任何开头或结尾空格。
s 里 至少 有一个词。
s 中的所有单词都用一个空格隔开。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
class Solution {
    public String reverseWords(String s) {
        String[] words = s.split(" ", -1); // 按空格拆分，保留空字符串
        StringBuilder result = new StringBuilder();
        for (int i = 0; i < words.length; i++) {
            // 反转每个单词
            String reversedWord = reverseWord(words[i]);
            result.append(reversedWord);
            // 如果不是最后一个单词，添加空格
            if (i < words.length - 1) {
                result.append(" ");
            }
        }
        return result.toString();
    }

    // 反转单个单词的方法
    public static String reverseWord(String s) {
        char[] s2 = s.toCharArray();
        int l = 0;
        int r = s2.length - 1;
        while (l < r) {
            char temp = s2[l];
            s2[l] = s2[r];
            s2[r] = temp;
            l++;
            r--;
        }
        return new String(s2);
    }
}

这里也能使用双指针来进行原地反转

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
public class Solution {
    public String reverseWords(String s) {
        char[] array = s.toCharArray();
        int start = 0;
        for (int i = 0; i < array.length; i++) {
            if (array[i] == ' ') {
                reverse(array, start, i - 1);
                start = i + 1; // 更新start为下一个单词的左索引
                continue;
            }
            if (i == array.length - 1) {
                reverse(array, start, i);
            }
        }
        return new String(array);
    }

    private void reverse(char[] array, int l, int r) {
        while (l < r) {
            char temp = array[l];
            array[l] = array[r];
            array[r] = temp;
            l += 1;
            r -= 1;
        }
    }
}

例题4：寻找旋转排序数组中的最小值

已知一个长度为 n 的数组，预先按照升序排列，经由 1 到 n 次 旋转 后，得到输入数组。例如，原数组 nums = [0,1,2,4,5,6,7] 在变化后可能得到：

  • 若旋转 4 次，则可以得到 [4,5,6,7,0,1,2]
  • 若旋转 7 次，则可以得到 [0,1,2,4,5,6,7]

注意，数组 [a[0], a[1], a[2], ..., a[n-1]] 旋转一次 的结果为数组 [a[n-1], a[0], a[1], a[2], ..., a[n-2]] 。

给你一个元素值 互不相同 的数组 nums ，它原来是一个升序排列的数组，并按上述情形进行了多次旋转。请你找出并返回数组中的 最小元素 。

你必须设计一个时间复杂度为 O(log n) 的算法解决此问题。

示例 1：

1
2
3
输入：nums = [3,4,5,1,2]
输出：1
解释：原数组为 [1,2,3,4,5] ，旋转 3 次得到输入数组。

示例 2：

1
2
3
输入：nums = [4,5,6,7,0,1,2]
输出：0
解释：原数组为 [0,1,2,4,5,6,7] ，旋转 4 次得到输入数组。

示例 3：

1
2
3
输入：nums = [11,13,15,17]
输出：11
解释：原数组为 [11,13,15,17] ，旋转 4 次得到输入数组。

提示：

  • n == nums.length
  • 1 <= n <= 5000
  • -5000 <= nums[i] <= 5000
  • nums 中的所有整数 互不相同
  • nums 原来是一个升序排序的数组，并进行了 1 至 n 次旋转
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
class Solution {
    public int findMin(int[] nums) {
        int left = 0;
        int right = nums.length - 1;                /* 左闭右闭区间，如果用右开区间则不方便判断右值 */ 
        while (left < right) {                      /* 循环不变式，如果left == right，则循环结束 */
            int mid = left + (right - left) / 2;    /* 地板除，mid更靠近left */
            if (nums[mid] > nums[right]) {          /* 中值 > 右值，最小值在右半边，收缩左边界 */ 
                left = mid + 1;                     /* 因为中值 > 右值，中值肯定不是最小值，左边界可以跨过mid */ 
            } else if (nums[mid] < nums[right]) {   /* 明确中值 < 右值，最小值在左半边，收缩右边界 */ 
                right = mid;                        /* 因为中值 < 右值，中值也可能是最小值，右边界只能取到mid处 */ 
            }
        }
        return nums[left];    /* 循环结束，left == right，最小值输出nums[left]或nums[right]均可 */     
    }
}

为什么这样计算 mid？

1. 避免整数溢出：

  • 如果直接使用 (left + right) / 2，当 left 和 right 都很大时，left + right 可能会导致整数溢出。
  • 例如，如果 left = 2_000_000_000，right = 2_000_000_001，那么 left + right = 4_000_000_001，这超出了 int 类型的最大值（2_147_483_647），会导致溢出。
  • 使用 left + (right - left) / 2 可以避免这个问题，因为 right - left 的值通常较小。

2. 确保 mid 位于 left 和 right 之间：

  • (right - left) / 2 计算的是 left 和 right 之间距离的一半。
  • 加上 left 后，mid 的值会位于 left 和 right 之间。

3. 为什么 mid 更接近 left？

这是因为 整数除法是向下取整（地板除）。具体来说：

  • 如果 (right - left) 是偶数，(right - left) / 2 会精确地计算出中间位置。
  • 如果 (right - left) 是奇数，(right - left) / 2 会向下取整，导致 mid 更靠近 left。

例题5：删除排序数组中的重复项

给你一个 非严格递增排列 的数组 nums ，请你 原地 删除重复出现的元素，使每个元素 只出现一次 ，返回删除后数组的新长度。元素的 相对顺序 应该保持 一致 。然后返回 nums 中唯一元素的个数。

考虑 nums 的唯一元素的数量为 k ，你需要做以下事情确保你的题解可以被通过：

更改数组 nums ，使 nums 的前 k 个元素包含唯一元素，并按照它们最初在 nums 中出现的顺序排列。nums 的其余元素与 nums 的大小不重要。
返回 k 。
判题标准:

系统会用下面的代码来测试你的题解:

int[] nums = […]; // 输入数组
int[] expectedNums = […]; // 长度正确的期望答案

int k = removeDuplicates(nums); // 调用

assert k == expectedNums.length;
for (int i = 0; i < k; i++) {
assert nums[i] == expectedNums[i];
}
如果所有断言都通过，那么您的题解将被 通过。

示例 1：

输入：nums = [1,1,2]
输出：2, nums = [1,2,_]
解释：函数应该返回新的长度 2 ，并且原数组 nums 的前两个元素被修改为 1, 2 。不需要考虑数组中超出新长度后面的元素。
示例 2：

输入：nums = [0,0,1,1,1,2,2,3,3,4]
输出：5, nums = [0,1,2,3,4]
解释：函数应该返回新的长度 5 ， 并且原数组 nums 的前五个元素被修改为 0, 1, 2, 3, 4 。不需要考虑数组中超出新长度后面的元素。

提示：

1 <= nums.length <= 3 * 104
-104 <= nums[i] <= 104
nums 已按 非严格递增 排列

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
class Solution {
    public int removeDuplicates(int[] nums) {
        //双指针的方法解决
        int fast = 0;
        int slow = 0;
        
        int len = nums.length;
        
        int result = 1;
        while(fast < len){
            if(nums[slow] == nums[fast]){
                fast++;
            }else{
                slow++;
            nums[slow] = nums[fast];
            fast++;
            result++;
            }
            
        }
        return result;
    }
}

例题6：移动零

给定一个数组 nums，编写一个函数将所有 0 移动到数组的末尾，同时保持非零元素的相对顺序。

请注意 ，必须在不复制数组的情况下原地对数组进行操作。

示例 1:

输入: nums = [0,1,0,3,12]
输出: [1,3,12,0,0]
示例 2:

输入: nums = [0]
输出: [0]

提示:

1 <= nums.length <= 104
-231 <= nums[i] <= 231 - 1

进阶：你能尽量减少完成的操作次数吗？

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
class Solution {
    public void moveZeroes(int[] nums) {
        int len = nums.length;
        //还是能用双指针
        if(len <= 1){
            return;
        }
        int fast = 0;
        int slow = 0;
        while(fast < len){
            if(nums[slow] == 0 && nums[fast] != 0){
                int temp = nums[slow];
                nums[slow] = nums[fast];
                nums[fast] = temp;
                slow++;
                fast++;
            }else if(nums[slow] != 0){
                slow++;
                fast++;
            }else{
                fast++;
            }
            
        }
        
        
    }
}