带你刷算法——数组/字符串的完全掌握（一）

冷不防 2023-10-13 19:04 21阅读 0赞

# 前言 #

![在这里插入图片描述][0422b4369a3549b3a39da19588ab88f4.png]  
「作者主页」：[雪碧有白泡泡][Link 1]  
「个人网站」：[雪碧的个人网站][Link 2]  
「推荐专栏」：

> ★[java一站式服务][java] ★  
> ★[前端炫酷代码分享][Link 3]  
> ★ ★ [uniapp-从构建到提升][uniapp-]★  
> ★ [从0到英雄，vue成神之路][0_vue]★  
> ★ [解决算法，一个专栏就够了][Link 4]★ ★ [架构咱们从0说][0]★  
> ★ [数据流通的精妙之道][Link 5]★

![请添加图片描述][c7f3e6b8a7624a9eabbea77dbcbca119.jpeg]

### 文章目录 ###

*  前言
 *   *  1.合并两个有序数组
     *   *  示例 ：
         *  提示：
 *  题解
 *   *   *  思路一：暴力
         *  思路二：双指针
     *  2.移除元素
     *   *  说明:
         *  示例 1：
         *  示例 2：
         *  提示：
 *  题解
 *   *   *  思路一：暴力法
         *   *  优化
     *  3.删除有序数组中的重复项
     *   *  判题标准:
         *  示例 1：
         *  示例 2：
         *  提示：
 *  题解
 *   *   *  思路一：暴力法
         *  思路二：快慢指针
     *  4.多数元素
     *   *  示例 1：
         *  示例 2：
         *  提示：
 *  题解
 *   *   *  思路一：暴力解法
     *  5.买卖股票的最佳时机
     *   *  示例 1：
         *  示例 2：
         *  提示：
 *  题解
 *   *   *  思路一：暴力法
         *  思路二：一次遍历
     *  6.罗马数字转整数
     *   *  示例
         *  提示：
 *  题解
 *   *   *  思路一：暴力法
     *  7.最后一个单词长度
     *   *  示例
         *  提示：
 *  题解
 *   *   *  思路一：反向遍历
     *  8.最长公共前缀
     *   *  示例
         *  提示：
 *  题解
 *   *   *  思路一：暴力法
 *  小结
 *   *   *  1.判断数组中相同的数，并判断了几次
         *  2.判断数组中两个数的最大差值
         *  3.判断后一个数比前一个数的最大差值
         *  4.循环遍历字符串
         *  5.判断字符串中的空格符号，并将第一个空格后面设置为第二个字符串，第二个空格为第三个字符串

![在这里插入图片描述][2473abe5c8e14ff1a3f1c13863993ed3.png]

## 1.合并两个有序数组 ##

![在这里插入图片描述][f44e9abd18f14de0bd6a4f9d7c88c087.png]

> 给你两个按 非递减顺序 排列的整数数组 nums1 和 nums2，另有两个整数 m 和 n ，分别表示 nums1 和 nums2  
> 中的元素数目。
> 
> 请你 合并 nums2 到 nums1 中，使合并后的数组同样按 非递减顺序 排列。
> 
> 注意：最终，合并后数组不应由函数返回，而是存储在数组 nums1 中。为了应对这种情况，nums1 的初始长度为 m + n，其中前 m  
> 个元素表示应合并的元素，后 n 个元素为 0 ，应忽略。nums2 的长度为 n 。

### 示例 ： ###

> 输入：nums1 = \[1,2,3,0,0,0\], m = 3, nums2 = \[2,5,6\], n = 3  
> 输出：\[1,2,2,3,5,6\] 解释：需要合并 \[1,2,3\] 和 \[2,5,6\] 。 合并结果是 \[1,2,2,3,5,6\]  
> ，其中斜体加粗标注的为 nums1 中的元素。 示例 2：
> 
> 输入：nums1 = \[1\], m = 1, nums2 = \[\], n = 0 输出：\[1\] 解释：需要合并 \[1\] 和 \[\] 。  
> 合并结果是 \[1\] 。 示例 3：
> 
> 输入：nums1 = \[0\], m = 0, nums2 = \[1\], n = 1 输出：\[1\] 解释：需要合并的数组是 \[\] 和 \[1\]  
> 。 合并结果是 \[1\] 。 注意，因为 m = 0 ，所以 nums1 中没有元素。nums1 中仅存的 0  
> 仅仅是为了确保合并结果可以顺利存放到 nums1 中。

### 提示： ###

>  *  nums1.length == m + n nums2.length == n 0 <= m,
>  *  n <= 200 1 <= m + n <=200 -109 <= nums1\[i\],
>  *  nums2\[j\] <= 109

![在这里插入图片描述][3e013e2ee1334f4097fe01f55d2c987c.png]

# 题解 #

### 思路一：暴力 ###

import java.util.Arrays;
    
    public class Solution {
        
        public void merge(int[] nums1, int m, int[] nums2, int n) {
        
            // 将 nums2 合并到 nums1 的后面
            for (int i = 0; i < n; ++i) {
        
                nums1[m + i] = nums2[i];
            }
            
            // 对合并后的数组进行排序
            Arrays.sort(nums1);
        }
    }

这段代码的主要思路是将数组`nums2`合并到数组`nums1`的后面，然后对合并后的数组进行排序。

首先，通过一个循环将`nums2`中的元素逐个复制到`nums1`的末尾。循环变量`i`从0开始，每次迭代将`nums2[i]`赋值给`nums1[m + i]`，其中`m`是`nums1`中已有元素的数量。这样就完成了合并的过程。

接下来，使用`Arrays.sort()`方法对合并后的数组`nums1`进行升序排序。这个方法会自动对数组中的元素进行排序，使得最终的数组呈现升序排列。

需要注意的是，这种实现方式会修改原始的`nums1`数组。如果不想修改原始数组，可以先创建一个临时数组，并将`nums1`复制到临时数组中，然后在临时数组上进行合并和排序操作。

### 思路二：双指针 ###

public class Solution {
        
        public void merge(int[] nums1, int m, int[] nums2, int n) {
        
            int i = m - 1;
            int j = n - 1;
            int k = m + n - 1;
    
            while (i >= 0 && j >= 0) {
        
                if (nums1[i] > nums2[j]) {
        
                    nums1[k--] = nums1[i--];
                } else {
        
                    nums1[k--] = nums2[j--];
                }
            }
    
            while (j >= 0) {
        
                nums1[k--] = nums2[j--];
            }
        }
    }

这段代码实现的思路是将两个有序数组`nums1`和`nums2`合并为一个有序数组，并将结果存储在`nums1`中。

首先，定义三个指针`i`、`j`和`k`。`i`指向`nums1`中的最后一个元素（有效元素），`j`指向`nums2`中的最后一个元素，`k`指向合并后的结果应该存储的位置。

然后，通过一个循环遍历两个数组，从后往前比较`nums1[i]`和`nums2[j]`的大小。如果`nums1[i]`大于`nums2[j]`，就将`nums1[i]`放入合并后的结果数组的末尾（即`nums1[k]`），并将`i`和`k`分别减一。如果`nums1[i]`小于等于`nums2[j]`，就将`nums2[j]`放入合并后的结果数组的末尾，并将`j`和`k`分别减一。重复这个过程直到其中一个数组遍历完。

最后，如果`nums2`中还有剩余元素（即`j >= 0`），则将剩余元素依次放入合并后的结果数组的末尾。

这种方式不需要创建额外的数组，只需要在原始的`nums1`数组上进行操作，节省了空间复杂度。同时，由于两个数组都是有序的，所以可以通过从后往前比较的方式，避免了频繁移动元素和插入操作，提高了效率。

## 2.移除元素 ##

![在这里插入图片描述][d8ff300807f1429eb19f33df41130bf1.png]

> 给你一个数组 nums 和一个值 val，你需要 原地 移除所有数值等于 val 的元素，并返回移除后数组的新长度。
> 
> 不要使用额外的数组空间，你必须仅使用 O(1) 额外空间并 原地 修改输入数组。
> 
> 元素的顺序可以改变。你不需要考虑数组中超出新长度后面的元素。

### 说明: ###

> 为什么返回数值是整数，但输出的答案是数组呢?
> 
> 请注意，输入数组是以「引用」方式传递的，这意味着在函数里修改输入数组对于调用者是可见的。
> 
> 你可以想象内部操作如下:
> 
> // nums 是以“引用”方式传递的。也就是说，不对实参作任何拷贝 int len = removeElement(nums, val);
> 
> // 在函数里修改输入数组对于调用者是可见的。 // 根据你的函数返回的长度, 它会打印出数组中 该长度范围内 的所有元素。 for  
> (int i = 0; i < len; i++) \{  
> print(nums\[i\]); \}

### 示例 1： ###

> 输入：nums = \[3,2,2,3\], val = 3 输出：2, nums = \[2,2\] 解释：函数应该返回新的长度 2, 并且  
> nums 中的前两个元素均为 2。你不需要考虑数组中超出新长度后面的元素。例如，函数返回的新长度为 2 ，而 nums =  
> \[2,2,3,3\] 或 nums = \[2,2,0,0\]，也会被视作正确答案。

### 示例 2： ###

> 输入：nums = \[0,1,2,2,3,0,4,2\], val = 2 输出：5, nums = \[0,1,4,0,3\]  
> 解释：函数应该返回新的长度 5, 并且 nums 中的前五个元素为 0, 1, 3, 0,  
> 4。注意这五个元素可为任意顺序。你不需要考虑数组中超出新长度后面的元素。

### 提示： ###

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

![在这里插入图片描述][a98b7be399d14048849ce82e783406e1.png]

# 题解 #

### 思路一：暴力法 ###

public class Solution {
        
        public int removeElement(int[] nums, int val) {
        
            int i = 0;
            int n = nums.length;
    
            while (i < n) {
         // 当前指针位置小于数组长度时进行遍历
                if (nums[i] == val) {
         // 如果当前元素等于 val，则将最后一个元素复制到当前位置
                    nums[i] = nums[n - 1];
                    n--; // 数组长度减少1
                } else {
        
                    i++; // 否则，移动指针到下一个位置
                }
            }
    
            return n; // 返回新的数组长度
        }
    }

这段代码的主要思路是移除数组`nums`中所有值为`val`的元素，并返回新的数组长度。

首先，定义两个指针`i`和`n`。`i`表示当前遍历到的位置，`n`表示当前有效元素的数量，即数组的长度。

然后，通过一个循环遍历数组`nums`。在每次迭代中，首先检查当前位置`nums[i]`是否等于目标值`val`。如果相等，则将最后一个元素`nums[n - 1]`复制到当前位置`nums[i]`上，同时将数组长度`n`减1，表示有效元素的数量减少了1。这样就实现了将目标值移到数组末尾的操作。

如果当前位置`nums[i]`不等于目标值`val`，则直接将指针`i`向后移动一位，继续遍历下一个元素。

重复这个过程直到遍历完整个数组。最终，数组中所有值为`val`的元素都被移动到了末尾，并且数组的长度变为`n`。

最后，返回新的数组长度`n`作为结果。

这种方法通过双指针操作，避免了频繁的元素搬移，提高了效率。由于题目并未要求删除特定的元素，只需要将目标值移到数组末尾，并返回新的数组长度，所以元素的相对顺序并不重要。

#### 优化 ####

class Solution {
        
        public int removeElement(int[] nums, int val) {
        
            int left = 0;
            int right = nums.length;
            while (left < right) {
        
                if (nums[left] == val) {
        
                    nums[left] = nums[right - 1];
                    right--;
                } else {
        
                    left++;
                }
            }
            return left;
        }
    }

这段代码的主要思路与之前给出的代码类似，都是移除数组`nums`中所有值为`val`的元素，并返回新的数组长度。

首先，定义两个指针`left`和`right`。`left`表示当前遍历到的位置，`right`表示有效元素的右边界，初始时为数组的长度。

然后，通过一个循环遍历数组`nums`。在每次迭代中，首先检查当前位置`nums[left]`是否等于目标值`val`。如果相等，则将最后一个元素`nums[right - 1]`复制到当前位置`nums[left]`上，同时将有效元素的右边界`right`减1，表示有效元素的数量减少了1。这样就实现了将目标值移到数组末尾的操作。

如果当前位置`nums[left]`不等于目标值`val`，则直接将左指针`left`向后移动一位，继续遍历下一个元素。

重复这个过程直到左指针`left`与右指针`right`相遇，即遍历完整个数组。最终，数组中所有值为`val`的元素都被移动到了末尾，并且左指针`left`所指示的位置即为新的数组长度。

最后，返回左指针`left`作为结果。

这种方法同样通过双指针操作，避免了频繁的元素搬移，提高了效率。与前一个代码不同的是，这里使用了左指针和右指针，在处理元素的替换时更加简洁。

## 3.删除有序数组中的重复项 ##

![在这里插入图片描述][f0d46d2195384ae2830c8c0079a0f8a8.png]

> 给你一个 升序排列 的数组 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 已按 升序 排列

![在这里插入图片描述][1bbb38e19bfc4d7a8c33c3ffae5944d5.png]

# 题解 #

### 思路一：暴力法 ###

class Solution {
        
        public int removeDuplicates(int[] nums) {
        
            int n = nums.length;
            if (n == 0) {
        
                return 0;
            }
            int k = 1;  // 记录唯一元素的数量
            for (int i = 1; i < n; i++) {
        
                if (nums[i] != nums[i-1]) {
          // 当前元素与前一个元素不相等
                    nums[k] = nums[i];  // 将当前元素移动到正确位置
                    k++;
                }
            }
            return k;
        }
    }

这段代码使用一个指针 `k` 来记录唯一元素的数量。初始化 `k` 为 1，表示第一个元素肯定是唯一的。

然后从数组的第二个元素开始遍历，如果当前元素与前一个元素不相等，则将当前元素移动到正确的位置，即数组的第 `k` 个位置，并将 `k` 自增 1。

最后返回 `k`，即为删除重复元素后的新数组长度。

请注意，这段代码要求输入的数组 `nums` 是升序排列的，才能正确删除重复元素。

### 思路二：快慢指针 ###

class Solution {
        
        public int removeDuplicates(int[] nums) {
        
            int n = nums.length;
            if (n == 0) {
        
                return 0;
            }
            int fast = 1, slow = 1;
            while (fast < n) {
        
                if (nums[fast] != nums[fast - 1]) {
        
                    nums[slow] = nums[fast];
                    ++slow;
                }
                ++fast;
            }
            return slow;
        }
    }

这段代码的主要思路是使用双指针方法来移除已排序数组中的重复元素，并返回修改后的数组长度。

具体步骤如下：

1.  首先，获取数组的长度n。
2.  如果数组为空（即n为0），则直接返回0，因为没有重复元素需要移除。
3.  初始化两个指针：fast和slow，初始值都为1。其中，fast指针用于遍历数组，从第二个元素开始；slow指针用于记录最后一个非重复元素的位置。
4.  进入循环，遍历数组直到fast指针达到数组末尾。
5.  在每次迭代中，比较当前fast指针位置的元素与其前一个元素是否相等。如果不相等，说明找到了一个新的不重复元素。
6.  将该新的不重复元素赋值给slow指针所在的位置，覆盖掉原有的重复元素。
7.  slow指针向后移动一位，指向下一个可能的不重复元素的位置。
8.  fast指针也向后移动一位，继续遍历数组。
9.  循环结束后，返回slow指针的值，它表示修改后的数组的长度。由于slow指针记录的是最后一个非重复元素的位置，所以长度为slow表示没有重复元素的子数组的长度。

总结起来，这段代码通过快慢指针的方式，在遍历数组过程中，将不重复的元素移动到数组的前面，并且记录下不重复子数组的长度。最终实现了原地修改数组，去除重复元素的目的。

## 4.多数元素 ##

![在这里插入图片描述][14132bce94a94d69a887fdaa8297aa10.png]

> 给定一个大小为 n 的数组 nums ，返回其中的多数元素。多数元素是指在数组中出现次数 大于 ⌊ n/2 ⌋ 的元素。
> 
> 你可以假设数组是非空的，并且给定的数组总是存在多数元素。

### 示例 1： ###

> 输入：nums = \[3,2,3\] 输出：3

### 示例 2： ###

> 输入：nums = \[2,2,1,1,1,2,2\] 输出：2

### 提示： ###

>  *  n == nums.length
>  *  1 <= n <= 5 \* 104
>  *  \-109 <= nums\[i\] <= 109

![在这里插入图片描述][093463a753f34ef3952d7cc49914b9f3.png]

# 题解 #

### 思路一：暴力解法 ###

暴力解法是通过遍历数组并统计每个元素的出现次数，然后判断是否满足大于 n/2 的条件。以下是一个使用暴力解法的示例代码：

public class Solution {
        
        public int majorityElement(int[] nums) {
        
            int n = nums.length;
            for (int num : nums) {
        
                int count = 0;
                for (int i = 0; i < n; i++) {
        
                    if (nums[i] == num) {
        
                        count++;
                    }
                }
                if (count > n / 2) {
        
                    return num;
                }
            }
            return -1; // 如果输入的数组不符合题目要求，没有多数元素，则返回一个特定的值（例如 -1）
        }
    }

上述代码中，我们使用两层循环来遍历整个数组。外层循环用于遍历每个元素，内层循环用于统计该元素在数组中出现的次数。如果某个元素的出现次数大于 n/2，则返回该元素作为多数元素。

请注意，上述代码并没有对输入数组进行非空判断或检查是否存在多数元素。根据题目描述，假设输入数组是非空的，并且总是存在多数元素。但在实际应用中，需要增加相应的逻辑来处理这些边界情况。

思路二：复杂度为O(1)随机化法

class Solution {
        
        private int randRange(Random rand, int min, int max) {
        
            return rand.nextInt(max - min) + min;
        }
    
        private int countOccurences(int[] nums, int num) {
        
            int count = 0;
            for (int i = 0; i < nums.length; i++) {
        
                if (nums[i] == num) {
        
                    count++;
                }
            }
            return count;
        }
    
        public int majorityElement(int[] nums) {
        
            Random rand = new Random();
    
            int majorityCount = nums.length / 2;
    
            while (true) {
        
                int candidate = nums[randRange(rand, 0, nums.length)];
                if (countOccurences(nums, candidate) > majorityCount) {
        
                    return candidate;
                }
            }
        }
    }

这段代码的目标是找出给定整数数组中的主要元素（即出现次数超过一半的元素）。下面是该代码的思路：

1.  在 `randRange` 方法中，使用 `Random` 类生成一个介于 `min` 和 `max` 之间的随机整数。
2.  `countOccurences` 方法用于计算在给定数组 `nums` 中等于 `num` 的元素个数。
3.  `majorityElement` 方法是主要的方法，它首先创建了一个 `Random` 对象 `rand`。
4.  然后根据数组长度计算出了主要元素的最小出现次数 `majorityCount`，即数组长度的一半。
5.  使用一个无限循环，在每次迭代中选择一个随机索引，并将对应的元素赋值给 `candidate`。
6.  然后通过调用 `countOccurences` 方法来计算 `candidate` 在数组中的出现次数。
7.  如果 `candidate` 的出现次数超过了 `majorityCount`，则返回 `candidate`，因为它是主要元素。
8.  如果没有找到主要元素，则会继续循环直到找到为止。

需要注意的是，由于数组中一定存在一个主要元素，所以这个循环一定会终止并返回结果。但是，这种方法的时间复杂度可能很高，因为在每次迭代中需要遍历整个数组来计算出现次数。在某些情况下，这可能导致性能问题。

## 5.买卖股票的最佳时机 ##

![在这里插入图片描述][6414506739d843428e29f930cccc0097.png]

> 给定一个数组 prices ，它的第 i 个元素 prices\[i\] 表示一支给定股票第 i 天的价格。
> 
> 你只能选择 某一天 买入这只股票，并选择在 未来的某一个不同的日子 卖出该股票。设计一个算法来计算你所能获取的最大利润。
> 
> 返回你可以从这笔交易中获取的最大利润。如果你不能获取任何利润，返回 0 。

### 示例 1： ###

> 输入：\[7,1,5,3,6,4\] 输出：5  
> 解释：在第 2 天（股票价格 = 1）的时候买入，在第 5 天（股票价格 =6）的时候卖出，最大利润 = 6-1 = 5 。  
> 注意利润不能是 7-1 = 6, 因为卖出价格需要大于买入价格；同时，你不能在买入前卖出股票。

### 示例 2： ###

> 输入：prices = \[7,6,4,3,1\] 输出：0  
> 解释：在这种情况下, 没有交易完成, 所以最大利润为 0。

### 提示： ###

>  *  1 <= prices.length <= 105
>  *  0 <= prices\[i\] <= 104

![在这里插入图片描述][25db33807ec44c489dbda96d780a1921.png]

# 题解 #

### 思路一：暴力法 ###

暴力解法可以通过考虑每一天作为买入点，然后在之后的每一天作为卖出点，计算利润并找到最大值。以下是使用暴力解法的Java代码示例：

class Solution {
        
        public int maxProfit(int[] prices) {
        
            int maxProfit = 0;
            
            for (int i = 0; i < prices.length - 1; i++) {
        
                for (int j = i + 1; j < prices.length; j++) {
        
                    int profit = prices[j] - prices[i];
                    if (profit > maxProfit) {
        
                        maxProfit = profit;
                    }
                }
            }
            
            return maxProfit;
        }
    }

上述代码中，我们使用两个循环嵌套来遍历所有可能的买入和卖出点组合。对于每个组合，我们计算卖出价格减去买入价格得到的利润，并将其与当前的最大利润进行比较。如果新计算的利润更大，则更新最大利润。

然后返回最大利润作为结果。这种暴力解法的时间复杂度为 O(n^2)，其中 n 是数组的长度。  
![在这里插入图片描述][b8bf4a7455a642aaaab20f4280cda8ce.png]

### 思路二：一次遍历 ###

public class Solution {
        
        public int maxProfit(int prices[]) {
        
            int minprice = Integer.MAX_VALUE;
            int maxprofit = 0;
            for (int i = 0; i < prices.length; i++) {
        
                if (prices[i] < minprice) {
        
                    minprice = prices[i];
                } else if (prices[i] - minprice > maxprofit) {
        
                    maxprofit = prices[i] - minprice;
                }
            }
            return maxprofit;
        }
    }

1.  初始化`minprice`为整数的最大值，`maxprofit`为0。`minprice`用于记录迄今为止最低的股票价格，`maxprofit`用于记录迄今为止最大的利润。
2.  遍历给定的股票价格数组`prices`，从索引0开始到数组末尾。
3.  对于每个价格`prices[i]`，首先检查它是否比当前的`minprice`更低。如果是，则更新`minprice`为`prices[i]`，因为我们找到了一个更低的购买价格。
4.  如果`prices[i]`不是比当前的`minprice`更低，那么我们计算以当前价格卖出时的利润。将`prices[i] - minprice`与当前的`maxprofit`进行比较，如果大于`maxprofit`，则更新`maxprofit`为`prices[i] - minprice`，因为我们找到了一个更大的利润。
5.  完成遍历后，`maxprofit`中存储的就是股票买卖的最大利润。

该算法的时间复杂度为O(n)，其中n是股票价格数组的长度。

## 6.罗马数字转整数 ##

![在这里插入图片描述][81ebb88063064134b37a756917cfe567.png]  
罗马数字包含以下七种字符: I， V， X， L，C，D 和 M。

字符 数值

I             1
    V             5
    X             10
    L             50
    C             100
    D             500
    M             1000

例如， 罗马数字 2 写做 II ，即为两个并列的 1 。12 写做 XII ，即为 X + II 。 27 写做 XXVII, 即为 XX + V + II 。

通常情况下，罗马数字中小的数字在大的数字的右边。但也存在特例，例如 4 不写做 IIII，而是 IV。数字 1 在数字 5 的左边，所表示的数等于大数 5 减小数 1 得到的数值 4 。同样地，数字 9 表示为 IX。这个特殊的规则只适用于以下六种情况：

>  *  I 可以放在 V (5) 和 X (10) 的左边，来表示 4 和 9。
>  *  X 可以放在 L (50) 和 C (100) 的左边，来表示 40 和 90。
>  *  C 可以放在 D (500) 和 M (1000) 的左边，来表示 400 和 900。
>  *  给定一个罗马数字，将其转换成整数。

### 示例 ###

> 输入: s = “III” 输出: 3
> 
> 输入: s = “IV” 输出: 4
> 
> 输入: s = “IX” 输出: 9 :
> 
> 输入: s = “LVIII” 输出: 58 解释: L = 50, V= 5, III = 3.
> 
> 输入: s = “MCMXCIV” 输出: 1994 解释: M = 1000, CM = 900, XC = 90, IV = 4.

### 提示： ###

>  *  1 <= s.length <= 15
>  *  s 仅含字符 (‘I’, ‘V’, ‘X’, ‘L’, ‘C’, ‘D’, ‘M’)
>  *  题目数据保证 s 是一个有效的罗马数字，且表示整数在范围 \[1, 3999\] 内
>  *  题目所给测试用例皆符合罗马数字书写规则，不会出现跨位等情况。
>  *  IL 和 IM 这样的例子并不符合题目要求，49 应该写作 XLIX，999 应该写作 CMXCIX 。
>  *  关于罗马数字的详尽书写规则，可以参考 罗马数字 - Mathematics 。

![在这里插入图片描述][6e603b2530ef44d08dafc94072cfad93.png]

# 题解 #

### 思路一：暴力法 ###

class Solution {
        
        Map<Character, Integer> symbolValues = new HashMap<Character, Integer>() {
        {
        
            put('I', 1);
            put('V', 5);
            put('X', 10);
            put('L', 50);
            put('C', 100);
            put('D', 500);
            put('M', 1000);
        }};
    
        public int romanToInt(String s) {
        
            int ans = 0;
            int n = s.length();
            for (int i = 0; i < n; ++i) {
        
                int value = symbolValues.get(s.charAt(i));
                if (i < n - 1 && value < symbolValues.get(s.charAt(i + 1))) {
        
                    ans -= value;
                } else {
        
                    ans += value;
                }
            }
            return ans;
        }
    }

通常情况下，罗马数字中小的数字在大的数字的右边。若输入的字符串满足该情况，那么可以将每个字符视作一个单独的值，累加每个字符对应的数值即可。

例如 XXVII\\texttt\{XXVII\}XXVII 可视作 X+X+V+I+I=10+10+5+1+1=27\\texttt\{X\}+\\texttt\{X\}+\\texttt\{V\}+\\texttt\{I\}+\\texttt\{I\}=10+10+5+1+1=27X+X+V+I+I=10+10+5+1+1=27。

若存在小的数字在大的数字的左边的情况，根据规则需要减去小的数字。对于这种情况，我们也可以将每个字符视作一个单独的值，若一个数字右侧的数字比它大，则将该数字的符号取反。

例如 XIV\\texttt\{XIV\}XIV 可视作 X−I+V=10−1+5=14\\texttt\{X\}-\\texttt\{I\}+\\texttt\{V\}=10-1+5=14X−I+V=10−1+5=14。

## 7.最后一个单词长度 ##

![在这里插入图片描述][4bfacaa91e71471a8a91e7a875fa1bec.png]

> 给你一个字符串 s，由若干单词组成，单词前后用一些空格字符隔开。返回字符串中 最后一个 单词的长度。
> 
> 单词 是指仅由字母组成、不包含任何空格字符的最大子字符串。

### 示例 ###

> 输入：s = “Hello World” 输出：5 解释：最后一个单词是“World”，长度为5。
> 
> 输入：s = " fly me to the moon " 输出：4 解释：最后一个单词是“moon”，长度为4。
> 
> 输入：s = “luffy is still joyboy” 输出：6 解释：最后一个单词是长度为6的“joyboy”。

### 提示： ###

> 1 <= s.length <= 104  
> s 仅有英文字母和空格 ’ ’ 组成  
> s 中至少存在一个单词

![在这里插入图片描述][b6252a336433473faa31d61e26f046bd.png]

# 题解 #

### 思路一：反向遍历 ###

class Solution {
        
        public int lengthOfLastWord(String s) {
        
            int end = s.length() - 1;
            while (end >= 0 && s.charAt(end) == ' ') end--;
            if (end == -1) return 0;
            int start = end;
            while (start >= 0 && s.charAt(start) != ' ') start--;
            return end - start;
        }
    }

## 8.最长公共前缀 ##

![在这里插入图片描述][d2ed0d418d6448ca9ff422db90a6299a.png]

> 编写一个函数来查找字符串数组中的最长公共前缀。
> 
> 如果不存在公共前缀，返回空字符串 " "。

### 示例 ###

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

### 提示： ###

>  *  1 <= strs.length <= 200
>  *  0 <= strs\[i\].length <= 200
>  *  strs\[i\] 仅由小写英文字母组

![在这里插入图片描述][bc7c203911aa4593935b0c211c5b8383.png]

# 题解 #

### 思路一：暴力法 ###

class Solution {
        
        public String longestCommonPrefix(String[] strs) {
        
            if (strs == null || strs.length == 0) {
        
                return "";
            }
            int length = strs[0].length();
            int count = strs.length;
            for (int i = 0; i < length; i++) {
        
                char c = strs[0].charAt(i);
                for (int j = 1; j < count; j++) {
        
                    if (i == strs[j].length() || strs[j].charAt(i) != c) {
        
                        return strs[0].substring(0, i);
                    }
                }
            }
            return strs[0];
        }
    }

上述代码使用了水平扫描法来找到最长公共前缀。以下是该算法的思路：

1.  首先，检查输入的字符串数组是否为空或长度为0，如果是的话，直接返回空字符串。
2.  初始化变量 `length` 为第一个字符串的长度，表示最长公共前缀的可能长度。
3.  初始化变量 `count` 为字符串数组的长度，表示需要比较的字符串数量。
4.  使用外层循环遍历第一个字符串的每个字符（索引从0到`length-1`）。
5.  在每次循环中，用变量 `c` 存储当前字符。
6.  使用内层循环遍历从第二个字符串到最后一个字符串（索引从1到`count-1`）。
7.  在每次内层循环中，首先检查索引 `i` 是否超出了字符串的长度，或者当前字符串的字符与第一个字符串的字符不相等，如果是的话，说明当前字符不属于公共前缀，直接返回第一个字符串的子串从索引0到`i-1`的部分。
8.  如果内层循环结束时没有返回，说明当前字符在所有字符串中都相等，继续下一个字符的比较。
9.  如果外层循环结束时都没有返回，说明第一个字符串就是最长公共前缀，直接返回第一个字符串。

这种方法通过逐个字符的比较来寻找最长公共前缀，当遇到不相等的字符或字符串长度超出时即可得到结果。

# 小结 #

### 1.判断数组中相同的数，并判断了几次 ###

以下是一个使用Java的示例代码来判断数组中相同的数，并计算它们出现的次数：

import java.util.HashMap;
    import java.util.Map;
    
    public class CountDuplicateNumbers {
        
        public static void main(String[] args) {
        
            int[] numbers = {
        1, 2, 3, 4, 5, 1, 3, 2, 4, 1};
    
            Map<Integer, Integer> countMap = new HashMap<>();
            for (int num : numbers) {
        
                if (countMap.containsKey(num)) {
        
                    countMap.put(num, countMap.get(num) + 1);
                } else {
        
                    countMap.put(num, 1);
                }
            }
    
            System.out.println("Duplicate numbers and their counts:");
            for (Map.Entry<Integer, Integer> entry : countMap.entrySet()) {
        
                if (entry.getValue() > 1) {
        
                    System.out.println(entry.getKey() + " - " + entry.getValue() + " times");
                }
            }
        }
    }

这段代码使用了`HashMap`来存储每个数字及其出现的次数。首先，我们遍历数组中的每个元素，如果`countMap`中已经包含该数字，则将其对应的值加1；否则，在`countMap`中添加该数字并设置初始值为1。最后，我们遍历`countMap`并打印出现次数大于1的数字及其出现次数。

在上述示例中，输入的数组为`{1, 2, 3, 4, 5, 1, 3, 2, 4, 1}`，输出结果为：

Duplicate numbers and their counts:
    1 - 3 times
    2 - 2 times
    3 - 2 times
    4 - 2 times

### 2.判断数组中两个数的最大差值 ###

以下是使用Java编写的示例代码，用于找到数组中两个数的最大差值：

public class MaxDifference {
        
        public static void main(String[] args) {
        
            int[] numbers = {
        2, 5, 9, 3, 1, 12, 6, 8};
    
            int maxDifference = findMaxDifference(numbers);
            System.out.println("Maximum difference: " + maxDifference);
        }
    
        public static int findMaxDifference(int[] numbers) {
        
            if (numbers == null || numbers.length < 2) {
        
                throw new IllegalArgumentException("Array must contain at least 2 numbers");
            }
    
            int minNumber = numbers[0];
            int maxDifference = numbers[1] - minNumber;
    
            for (int i = 2; i < numbers.length; i++) {
        
                if (numbers[i - 1] < minNumber) {
        
                    minNumber = numbers[i - 1];
                }
    
                int currentDifference = numbers[i] - minNumber;
                if (currentDifference > maxDifference) {
        
                    maxDifference = currentDifference;
                }
            }
    
            return maxDifference;
        }
    }

在上述示例中，我们定义了一个`findMaxDifference`方法，该方法接受一个整数数组作为输入，并返回数组中两个数的最大差值。首先，我们检查数组是否为空或长度小于2，如果是，则抛出`IllegalArgumentException`异常。

然后，我们初始化`minNumber`为数组的第一个元素，将`maxDifference`初始化为第二个元素减去`minNumber`。接下来，我们遍历数组从索引2开始的每个元素。如果当前元素之前的最小数字`minNumber`大于当前元素的前一个元素，则更新`minNumber`为前一个元素的值。

然后，我们计算当前元素与`minNumber`之间的差值，并将其存储在`currentDifference`变量中。如果`currentDifference`大于`maxDifference`，则更新`maxDifference`为`currentDifference`。

最后，我们返回`maxDifference`作为结果。

在上述示例中，输入的数组为`{2, 5, 9, 3, 1, 12, 6, 8}`，输出结果为：

Maximum difference: 11

这表示数组中的最大差值为11，即12减去1。

### 3.判断后一个数比前一个数的最大差值 ###

以下是使用Java编写的示例代码，用于找到数组中后一个数比前一个数的最大差值：

public class MaxDifference {
        
        public static void main(String[] args) {
        
            int[] numbers = {
        2, 5, 9, 3, 1, 12, 6, 8};
    
            int maxDifference = findMaxDifference(numbers);
            System.out.println("Maximum difference between consecutive numbers: " + maxDifference);
        }
    
        public static int findMaxDifference(int[] numbers) {
        
            if (numbers == null || numbers.length < 2) {
        
                throw new IllegalArgumentException("Array must contain at least 2 numbers");
            }
    
            int maxDifference = Integer.MIN_VALUE;
    
            for (int i = 1; i < numbers.length; i++) {
        
                int currentDifference = numbers[i] - numbers[i - 1];
                if (currentDifference > maxDifference) {
        
                    maxDifference = currentDifference;
                }
            }
    
            return maxDifference;
        }
    }

在上述示例中，我们定义了一个`findMaxDifference`方法，该方法接受一个整数数组作为输入，并返回数组中后一个数比前一个数的最大差值。首先，我们检查数组是否为空或长度小于2，如果是，则抛出`IllegalArgumentException`异常。

然后，我们初始化`maxDifference`为`Integer.MIN_VALUE`，这是一个较小的初始值，确保可以正确比较和更新最大差值。

接下来，我们遍历数组从索引1开始的每个元素。通过计算当前元素与其前一个元素的差值，并将其存储在`currentDifference`变量中。如果`currentDifference`大于`maxDifference`，则更新`maxDifference`为`currentDifference`。

最后，我们返回`maxDifference`作为结果。

在上述示例中，输入的数组为`{2, 5, 9, 3, 1, 12, 6, 8}`，输出结果为：

Maximum difference between consecutive numbers: 11

这表示数组中后一个数比前一个数的最大差值为11，即12减去1。

### 4.循环遍历字符串 ###

以下是使用Java编写的示例代码，用于循环遍历字符串并打印每个字符：

public class LoopString {
        
        public static void main(String[] args) {
        
            String str = "Hello, World!";
    
            // 使用for循环遍历字符串
            System.out.println("Using for loop:");
            for (int i = 0; i < str.length(); i++) {
        
                char ch = str.charAt(i);
                System.out.println(ch);
            }
    
            // 使用增强型for循环遍历字符串
            System.out.println("Using enhanced for loop:");
            for (char ch : str.toCharArray()) {
        
                System.out.println(ch);
            }
    
            // 使用while循环遍历字符串
            System.out.println("Using while loop:");
            int index = 0;
            while (index < str.length()) {
        
                char ch = str.charAt(index);
                System.out.println(ch);
                index++;
            }
        }
    }

在上述示例中，我们使用三种不同的循环方式来遍历字符串`"Hello, World!"`。

首先，我们使用`for`循环来遍历字符串。通过获取字符串的长度`str.length()`，我们可以使用索引从0到字符串长度减1的范围来依次访问每个字符。使用`charAt()`方法，我们可以获取指定索引位置的字符，并将其打印出来。

然后，我们使用增强型`for`循环（也称为`foreach`循环）来遍历字符串。通过调用`toCharArray()`方法，我们可以将字符串转换为一个字符数组。这样，我们就可以直接遍历字符数组的每个元素，并将其打印出来。

最后，我们使用`while`循环来遍历字符串。通过定义一个索引变量`index`，并在每次迭代后递增它，我们可以依次访问字符串中的每个字符。在循环体中，我们使用`charAt()`方法获取指定索引位置的字符，并将其打印出来。

以上三种循环方式都会输出相同的结果，即遍历字符串并打印每个字符。

在上述示例中，输出结果为：

Using for loop:
    H
    e
    l
    l
    o
    ,
     
    W
    o
    r
    l
    d
    !
    Using enhanced for loop:
    H
    e
    l
    l
    o
    ,
     
    W
    o
    r
    l
    d
    !
    Using while loop:
    H
    e
    l
    l
    o
    ,
     
    W
    o
    r
    l
    d
    !

### 5.判断字符串中的空格符号，并将第一个空格后面设置为第二个字符串，第二个空格为第三个字符串 ###

以下是使用Java编写的示例代码，用于判断字符串中的空格符号，并将第一个空格后面的内容设置为第二个字符串，第二个空格后面的内容设置为第三个字符串：

public class SplitString {
        
        public static void main(String[] args) {
        
            String str = "Hello, World! This is a test.";
    
            // 使用split()方法分割字符串
            String[] parts = str.split("\\s+", 3);
    
            if (parts.length >= 3) {
        
                String firstString = parts[0];
                String secondString = parts[1];
                String thirdString = parts[2];
    
                System.out.println("First string: " + firstString);
                System.out.println("Second string: " + secondString);
                System.out.println("Third string: " + thirdString);
            } else {
        
                System.out.println("The input string does not contain enough spaces.");
            }
        }
    }

在上述示例中，我们首先定义了一个输入字符串`"Hello, World! This is a test."`。

然后，我们使用`split()`方法对输入字符串进行分割。`split()`方法以指定的正则表达式作为分隔符来拆分字符串。在这里，我们使用正则表达式`\\s+`，表示一个或多个连续的空白字符（包括空格、制表符、换行符等）作为分隔符。第二个参数`3`表示最大分割成三部分。

接下来，我们检查分割后的结果数组`parts`的长度是否大于等于3。如果是，则表示输入字符串中至少有两个空格符号。

然后，我们提取数组`parts`中的第一个、第二个和第三个元素作为相应的字符串变量：`firstString`、`secondString`和`thirdString`。

最后，我们打印输出每个字符串的内容。

在上述示例中，输出结果为：

First string: Hello,
    Second string: World!
    Third string: This is a test.

这表示输入字符串中的第一个空格后面的内容被设置为第二个字符串（“World!”），第二个空格后面的内容被设置为第三个字符串（“This is a test.”）。

[0422b4369a3549b3a39da19588ab88f4.png]: https://img-blog.csdnimg.cn/0422b4369a3549b3a39da19588ab88f4.png
[Link 1]: https://blog.csdn.net/Why_does_it_work?spm=1011.2415.3001.5343
[Link 2]: https://sprite.inscode.cc/
[java]: https://blog.csdn.net/why_does_it_work/category_12379581.html
[Link 3]: https://blog.csdn.net/why_does_it_work/category_12378617.html
[uniapp-]: https://blog.csdn.net/why_does_it_work/category_12363697.html
[0_vue]: https://blog.csdn.net/why_does_it_work/category_12376654.html
[Link 4]: https://blog.csdn.net/why_does_it_work/category_12381051.html
[0]: https://blog.csdn.net/why_does_it_work/category_12381055.html
[Link 5]: https://blog.csdn.net/why_does_it_work/category_12381058.html
[c7f3e6b8a7624a9eabbea77dbcbca119.jpeg]: https://img-blog.csdnimg.cn/c7f3e6b8a7624a9eabbea77dbcbca119.jpeg
[2473abe5c8e14ff1a3f1c13863993ed3.png]: https://img-blog.csdnimg.cn/2473abe5c8e14ff1a3f1c13863993ed3.png
[f44e9abd18f14de0bd6a4f9d7c88c087.png]: https://img-blog.csdnimg.cn/f44e9abd18f14de0bd6a4f9d7c88c087.png
[3e013e2ee1334f4097fe01f55d2c987c.png]: https://img-blog.csdnimg.cn/3e013e2ee1334f4097fe01f55d2c987c.png
[d8ff300807f1429eb19f33df41130bf1.png]: https://img-blog.csdnimg.cn/d8ff300807f1429eb19f33df41130bf1.png
[a98b7be399d14048849ce82e783406e1.png]: https://img-blog.csdnimg.cn/a98b7be399d14048849ce82e783406e1.png
[f0d46d2195384ae2830c8c0079a0f8a8.png]: https://img-blog.csdnimg.cn/f0d46d2195384ae2830c8c0079a0f8a8.png
[1bbb38e19bfc4d7a8c33c3ffae5944d5.png]: https://img-blog.csdnimg.cn/1bbb38e19bfc4d7a8c33c3ffae5944d5.png
[14132bce94a94d69a887fdaa8297aa10.png]: https://img-blog.csdnimg.cn/14132bce94a94d69a887fdaa8297aa10.png
[093463a753f34ef3952d7cc49914b9f3.png]: https://img-blog.csdnimg.cn/093463a753f34ef3952d7cc49914b9f3.png
[6414506739d843428e29f930cccc0097.png]: https://img-blog.csdnimg.cn/6414506739d843428e29f930cccc0097.png
[25db33807ec44c489dbda96d780a1921.png]: https://img-blog.csdnimg.cn/25db33807ec44c489dbda96d780a1921.png
[b8bf4a7455a642aaaab20f4280cda8ce.png]: https://img-blog.csdnimg.cn/b8bf4a7455a642aaaab20f4280cda8ce.png
[81ebb88063064134b37a756917cfe567.png]: https://img-blog.csdnimg.cn/81ebb88063064134b37a756917cfe567.png
[6e603b2530ef44d08dafc94072cfad93.png]: https://img-blog.csdnimg.cn/6e603b2530ef44d08dafc94072cfad93.png
[4bfacaa91e71471a8a91e7a875fa1bec.png]: https://img-blog.csdnimg.cn/4bfacaa91e71471a8a91e7a875fa1bec.png
[b6252a336433473faa31d61e26f046bd.png]: https://img-blog.csdnimg.cn/b6252a336433473faa31d61e26f046bd.png
[d2ed0d418d6448ca9ff422db90a6299a.png]: https://img-blog.csdnimg.cn/d2ed0d418d6448ca9ff422db90a6299a.png
[bc7c203911aa4593935b0c211c5b8383.png]: https://img-blog.csdnimg.cn/bc7c203911aa4593935b0c211c5b8383.png