LeetCode算法题---无重复字符的最长子串、寻找两个正序数组的中位数(三)

简介: LeetCode算法题---无重复字符的最长子串、寻找两个正序数组的中位数(三)

3. 无重复字符的最长子串


给定一个字符串 s ,请你找出其中不含有重复字符的 最长子串 的长度。


示例 1:

输入: s = "abcabcbb"
输出: 3 
解释: 因为无重复字符的最长子串是 "abc",所以其长度为 3。


示例 2:

输入: s = "bbbbb"
输出: 1
解释: 因为无重复字符的最长子串是 "b",所以其长度为 1。


示例 3:

输入: s = "pwwkew"
输出: 3
解释: 因为无重复字符的最长子串是 "wke",所以其长度为 3。
     请注意,你的答案必须是 子串 的长度,"pwke" 是一个子序列,不是子串。


解题代码:

class Solution {
    public int lengthOfLongestSubstring(String s) {
        int n = s.length();
        int[] cnt = new int[128];
        int ans = 0, left = 0, right = 0;
        while (right < n) {
            cnt[s.charAt(right)]++;
            while (cnt[s.charAt(right)] > 1) {
                cnt[s.charAt(left)]--;
                left++;
            }
            ans = Math.max(ans, right - left + 1);
            right++;
        }
        return ans;
    }
}


代码解析:

以上是使用字符数组来代替哈希集合、实现不含重复字符的最长子串长度问题的 Java 代码。这里是每行代码的解释:
```
class Solution {
```
这是一个类定义,名为 `Solution`。
```
public int lengthOfLongestSubstring(String s) {
```
这是一个公共方法 `lengthOfLongestSubstring`,它接受一个字符串类型的参数 `s` 作为输入,表示需要寻找最长不重复子串的字符串。方法返回一个整型的值,表示不含重复字符的最长子串长度。
```
int n = s.length();
```
获取字符串参数的长度 `n`,用于后面的循环遍历。
```
int[] cnt = new int[128];
```
创建一个长度为 128 的整型数组 `cnt`,记录每个字符最后一次在 `s` 中出现的位置。由于所给定字符串只包含 ASCII 字符,因此数组长度为 128。因为 ASCII 的编号范围是 0 ~ 127,共 128 个字符。
```
int ans = 0, left = 0, right = 0;
```
初始化最大不重复子串长度为 0,定义左指针 `left` 和右指针 `right` 的初始位置都为字符串的开头位置 0。
```
while (right < n) {
```
当 `right` 小于字符串的长度时,我们进行循环。
```
cnt[s.charAt(right)]++;
```
将当前位置的字符 `s.charAt(right)` 在数组 `cnt` 中的值增加 1。也就是记录当前对应字符在当前滑动窗口中的出现次数。
```
while (cnt[s.charAt(right)] > 1) {
    cnt[s.charAt(left)]--;
    left++;
}
```
如果当前对应字符的计数器 `cnt[s.charAt(right)]` 的值大于 1,说明当前字符在当前滑动窗口中出现了 2 次或以上,需要将 `left` 指针右移,缩小滑动窗口的大小。同时,需要将当前指向的字符 `s.charAt(left)` 在计数器 `cnt` 中的值减 1。
```
ans = Math.max(ans, right - left + 1);
```
更新最长不重复子串的长度 `ans`,值为当前滑动窗口的长度 `right - left + 1` 和 `ans` 的最大值。
```
right++;
```
右指针 `right` 向右移动一个位置,扩大滑动窗口的大小。
```
}
return ans;
}
```
返回最终求得的不含重复字符的最长子串的长度 `ans`。


4. 寻找两个正序数组的中位数


给定两个大小分别为 m 和 n 的正序(从小到大)数组 nums1 和 nums2。请你找出并返回这两个正序数组的中位数


算法的时间复杂度应该为 O(log (m+n)) 。


示例 1:

输入:nums1 = [1,3], nums2 = [2]
输出:2.00000
解释:合并数组 = [1,2,3] ,中位数 2


示例 2:

输入:nums1 = [1,2], nums2 = [3,4]
输出:2.50000
解释:合并数组 = [1,2,3,4] ,中位数 (2 + 3) / 2 = 2.5


解题代码1:

class Solution {
    public double findMedianSortedArrays(int[] nums1, int[] nums2) {
         int n1 = nums1.length, n2 = nums2.length;
        // 保证 n1 <= n2
        if (n1 > n2) {
            return findMedianSortedArrays(nums2, nums1);
        }
        // 分别找到两个数组的分割线左侧的最大值和右侧的最小值
        int k = (n1 + n2 + 1) / 2;
        int left = 0, right = n1;
        while (left < right) {
            int m1 = left + right >> 1;
            int m2 = k - m1;
            if (nums1[m1] < nums2[m2 - 1]) {
                left = m1 + 1;
            } else {
                right = m1;
            }
        }
        int m1 = left, m2 = k - m1;
        int c1 = Math.max(m1 <= 0 ? Integer.MIN_VALUE : nums1[m1 - 1],
                          m2 <= 0 ? Integer.MIN_VALUE : nums2[m2 - 1]);
        if ((n1 + n2) % 2 == 1) {
            return c1;
        }
        int c2 = Math.min(m1 >= n1 ? Integer.MAX_VALUE : nums1[m1],
                          m2 >= n2 ? Integer.MAX_VALUE : nums2[m2]);
        return (c1 + c2) / 2.0;
    }
}


解题代码2:

以下是 Java 代码实现,时间复杂度为 $O(log (m+n))$:
```
class Solution {
    public double findMedianSortedArrays(int[] nums1, int[] nums2) {
        int n1 = nums1.length, n2 = nums2.length;
        // 保证 n1 <= n2
        if (n1 > n2) {
            return findMedianSortedArrays(nums2, nums1);
        }
        // 分别找到两个数组的分割线左侧的最大值和右侧的最小值
        int k = (n1 + n2 + 1) / 2;
        int left = 0, right = n1;
        while (left < right) {
            int m1 = left + right >> 1;
            int m2 = k - m1;
            if (nums1[m1] < nums2[m2 - 1]) {
                left = m1 + 1;
            } else {
                right = m1;
            }
        }
        int m1 = left, m2 = k - m1;
        int c1 = Math.max(m1 <= 0 ? Integer.MIN_VALUE : nums1[m1 - 1],
                          m2 <= 0 ? Integer.MIN_VALUE : nums2[m2 - 1]);
        if ((n1 + n2) % 2 == 1) {
            return c1;
        }
        int c2 = Math.min(m1 >= n1 ? Integer.MAX_VALUE : nums1[m1],
                          m2 >= n2 ? Integer.MAX_VALUE : nums2[m2]);
        return (c1 + c2) / 2.0;
    }
}
```
具体地,我们将两个数组合并成一个有序数组,并且找到这个有序数组的中位数。为了使算法的时间复杂度为 $O(log (m+n))$,我们需要使用二分查找的思想进行操作。
我们先假设我们已经求出了两个数组合并后的有序数组的中位数,记为 $median$。根据中位数的定义,它将有序数组分成两个部分,左边部分的元素个数为 $(m+n+1) \div 2$。因此,我们只需要在第一个数组中找到一个位置 $m1$,使得:
1. 第一个数组中 $m1$ 左侧的元素都小于 $median$。
2. 第二个数组中 $m2=k-m1$ 左侧的元素也都小于 $median$。
根据第一个数组和第二个数组都是有序的,上述两个条件等价于:
1. 第一个数组中下标小于 $m1$ 的元素加上第二个数组中下标小于 $m2$ 的元素刚好可以凑够 $(m+n+1) \div 2$ 个元素。
2. 右侧的元素也满足条件,即第一个数组中下标 $m1$ 和第二个数组中下标 $m2$ 的元素合起来才是中位数。
因此,我们可以对第一个数组进行二分查找,找到一个位置 $m1$,使得满足上述条件。然后,我们就可以根据 $m1$ 和 $k$ 计算出 $m2$ 的值,进而确定中位数 $median$。
最后,我们计算中位数并返回即可。
上述代码中的变量解释如下:
- `n1` 和 `n2` 分别表示数组 `nums1` 和 `nums2` 的长度。
- `k` 表示合并后有序数组的中位数的下标值。
- `left` 和 `right` 分别表示二分查找的区间左右端点。
- `m1` 和 `m2` 分别表示合并后有序数组的两个部分的分割线在 `nums1` 中的下标和在 `nums2` 中的下标。
- `c1` 和 `c2` 分别表示两个有序数组在当前分割线下可能的中位数值。


目录
相关文章
|
7天前
|
存储 算法 Go
算法学习:数组 vs 链表
算法学习:数组 vs 链表
13 0
|
7天前
|
算法 Java
[Java·算法·简单] LeetCode 283. 移动零
[Java·算法·简单] LeetCode 283. 移动零
16 2
|
10天前
|
存储 算法 调度
力扣中级算法(Python)
力扣中级算法(Python)
|
10天前
|
算法 Python
力扣初级算法(Python)(二)
力扣初级算法(Python)(二)
|
10天前
|
算法 Python
力扣初级算法(Python)(一)
力扣初级算法(Python)(一)
|
11天前
|
算法
【经典LeetCode算法题目专栏分类】【第10期】排序问题、股票问题与TOP K问题:翻转对、买卖股票最佳时机、数组中第K个最大/最小元素
【经典LeetCode算法题目专栏分类】【第10期】排序问题、股票问题与TOP K问题:翻转对、买卖股票最佳时机、数组中第K个最大/最小元素
|
4天前
|
算法
【洛谷 P1003】[NOIP2011 提高组] 铺地毯 题解(数组+贪心算法)
**NOIP2011 提高组问题:铺地毯** 在第一象限的颁奖典礼场地,有$n$张地毯按编号顺序铺设。需找出覆盖特定点$(x, y)$的最上方地毯编号。输入包括地毯坐标和点坐标,输出地毯编号或-1表示未覆盖。 样例:给定3张地毯,点$(2,2)$被第3张地毯覆盖,输出3;另一样例点$(4,5)$未被覆盖,输出-1。 $30\%$数据$n\leq2$,$50\%$数据坐标$\leq100$,$100\%$数据$n\leq10^4$,坐标$\leq10^5$。 解决方法:从下到上遍历地毯,更新覆盖点的地毯编号。 AC代码略。
5 0
|
11天前
【LeetCode刷题】滑动窗口思想解决问题:长度最小的子数组、无重复字符的最长子串
【LeetCode刷题】滑动窗口思想解决问题:长度最小的子数组、无重复字符的最长子串
|
11天前
|
算法
【经典LeetCode算法题目专栏分类】【第11期】递归问题:字母大小写全排列、括号生成
【经典LeetCode算法题目专栏分类】【第11期】递归问题:字母大小写全排列、括号生成
|
11天前
|
算法
【经典LeetCode算法题目专栏分类】【第9期】深度优先搜索DFS与并查集:括号生成、岛屿问题、扫雷游戏
【经典LeetCode算法题目专栏分类】【第9期】深度优先搜索DFS与并查集:括号生成、岛屿问题、扫雷游戏