LeetCode 1-5题 详解 Java版 (三万字 图文详解 LeetCode 算法题1-5 =====>>> <建议收藏>)

简介: LeetCode 1-5题 详解 Java版 (三万字 图文详解 LeetCode 算法题1-5 =====>>> <建议收藏>)

目录


第一题:TWO SUM

1. 题目描述 (简单难度)

2. 解法一

3. 解法二

4. 解法三

5. 总结

第二题: Add-Two-Numbers

1. 题目描述(中等难度)

2. 图示

3. 思路

4. 代码

5. 扩展

6. 迭代思想

7. 迭代代码

8. 递归思想

9. 代码

第三题: Longest Substring Without Repeating Characters

1. 题目描述(中等难度)

2. 解法一

3. 解法二

4. 解法三

5. 解法四

6. 总结

第四题 :Median of Two Sorted Arrays

1. 题目描述(困难难度)

2. 解法一

3. 代码

4. 解法二

5. 代码

6. 解法三

7. 代码

8. 解法四

9. 总结

第五题: Longest Palindromic Substring

1. 题目描述(中等难度)

2. 解法一 暴力破解

3. 解法二 最长公共子串

4. 解法三 暴力破解优化

5. 解法四 扩展中心

6. 解法五 Manacher's Algorithm 马拉车算法。

7. 求原字符串下标

8. 求每个 P [ i ]

8.1. 1. 超出了 R

8.2. 2. P [ i_mirror ] 遇到了原字符串的左边界

8.3. 3. i 等于了 R

9. 考虑 C 和 R 的更新

10. 总结

喜欢 请点个 + 关注


第一题:TWO SUM

1. 题目描述 (简单难度)


39.jpg


给定一个数组和一个目标和,从数组中找两个数字相加等于目标和,输出这两个数字的下标


2. 解法一


简单粗暴些,两重循环,遍历所有情况看相加是否等于目标和,如果符合直接输出。

public int[] twoSum(int[] nums, int target) {
    int []ans=new int[2];
    for(int i=0;i<nums.length;i++){
        for(int j=(i+1);j<nums.length;j++){
            if(nums[i]+nums[j]==target){
                ans[0]=i;
                ans[1]=j;
                return ans;
            }
        }
    }
    return ans;
}


时间复杂度:两层 for 循环,O(n²)

空间复杂度:O(1)


3. 解法二


在上边的解法中看下第二个 for 循环步骤。

for(int j=(i+1);j<nums.length;j++){
    if(nums[i]+nums[j]==target){


我们换个理解方式:

for(int j=(i+1);j<nums.length;j++){ 
    sub=target-nums[i]
     if(nums[j]==sub){


第二层 for 循环无非是遍历所有的元素,看哪个元素等于 sub ,时间复杂度为 O(n)。


有没有一种方法,不用遍历就可以找到元素里有没有等于 sub 的?


hash table !!!


我们可以把数组的每个元素保存为 hash 的 key,下标保存为 hash 的 value 。


这样只需判断 sub 在不在 hash 的 key 里就可以了,而此时的时间复杂度仅为 O(1)!


需要注意的地方是,还需判断找到的元素不是当前元素,因为题目里讲一个元素只能用一次。


public int[] twoSum(int[] nums, int target) {
    Map<Integer,Integer> map=new HashMap<>();
    for(int i=0;i<nums.length;i++){
        map.put(nums[i],i);
    }
    for(int i=0;i<nums.length;i++){
        int sub=target-nums[i];
        if(map.containsKey(sub)&&map.get(sub)!=i){
            return new int[]{i,map.get(sub)};
        }
    }
    throw new IllegalArgumentException("No two sum solution");
}


时间复杂度:比解法一少了一个 for 循环,降为 O(n)

空间复杂度:所谓的空间换时间,这里就能体现出来, 开辟了一个 hash table ,空间复杂度变为 O(n)


4. 解法三


看解法二中,两个 for 循环,他们长的一样,我们当然可以把它合起来。复杂度上不会带来什么变化,变化仅仅是不需要判断是不是当前元素了,因为当前元素还没有添加进 hash 里。

public int[] twoSum(int[] nums, int target) {
    Map<Integer,Integer> map=new HashMap<>();
    for(int i=0;i<nums.length;i++){
        int sub=target-nums[i];
        if(map.containsKey(sub)){
            return new int[]{i,map.get(sub)};
        }
        map.put(nums[i], i);
    }
    throw new IllegalArgumentException("No two sum solution");
}


5. 总结


题目比较简单,毕竟暴力的方法也可以解决。唯一闪亮的点就是,时间复杂度从 O(n²)降为 O(n) 的时候,对 hash 的应用,有眼前一亮的感觉。


第二题: Add-Two-Numbers

1. 题目描述(中等难度)


40.jpg

就是两个链表表示的数相加,这样就可以实现两个很大的数相加了,无需考虑数值 int ,float 的限制了。

由于自己实现的很乱,直接按答案的讲解了。


2. 图示

41.jpg

链表最左边表示个位数,代表 342 + 465 =807 。


3. 思路


首先每一位相加肯定会产生进位,我们用 carry 表示。进位最大会是 1 ,因为最大的情况是无非是 9 + 9 + 1 = 19 ,也就是两个最大的数相加,再加进位,这样最大是 19 ,不会产生进位 2 。下边是伪代码。


初始化一个节点的头,dummy head ,但是这个头不存储数字。并且将 curr 指向它。


初始化进位 carry 为 0 。


初始化 p 和 q 分别为给定的两个链表 l1 和 l2 的头,也就是个位。


循环,直到 l1 和 l2 全部到达 null 。


设置 x 为 p 节点的值,如果 p 已经到达了 null,设置 x 为 0 。


设置 y 为 q 节点的值,如果 q 已经到达了 null,设置 y 为 0 。


设置 sum = x + y + carry 。


更新 carry = sum / 10 。


创建一个值为 sum mod 10 的节点,并将 curr 的 next 指向它,同时 curr 指向变为当前的新节点。


向前移动 p 和 q 。


判断 carry 是否等于 1 ,如果等于 1 ,在链表末尾增加一个为 1 的节点。


返回 dummy head 的 next ,也就是个位数开始的地方。


初始化的节点 dummy head 没有存储值,最后返回 dummy head 的 next 。这样的好处是不用单独对 head 进行判断改变值。也就是如果一开始的 head 就是代表个位数,那么开始初始化的时候并不知道它的值是多少,所以还需要在进入循环前单独对它进行值的更正,不能像现在一样只用一个循环简洁。


4. 代码


class ListNode {
    int val;
    ListNode next;
    ListNode(int x) { val = x; }
}
public ListNode addTwoNumbers(ListNode l1, ListNode l2) {
    ListNode dummyHead = new ListNode(0);
    ListNode p = l1, q = l2, curr = dummyHead;
    int carry = 0;
    while (p != null || q != null) {
        int x = (p != null) ? p.val : 0;
        int y = (q != null) ? q.val : 0;
        int sum = carry + x + y;
        carry = sum / 10;
        curr.next = new ListNode(sum % 10);
        curr = curr.next;
        if (p != null) p = p.next;
        if (q != null) q = q.next;
    }
    if (carry > 0) {
        curr.next = new ListNode(carry);
    }
    return dummyHead.next;
}


时间复杂度:O(max(m,n)),m 和 n 代表 l1 和 l2 的长度。

空间复杂度:O(max(m,n)),m 和 n 代表 l1 和 l2 的长度。而其实新的 List 最大长度是 O(max(m,n))+ 1,因为我们的 head 没有存储值。


5. 扩展


43.jpg


如果链表存储的顺序反过来怎么办?

我首先想到的是链表先逆序计算,然后将结果再逆序呗,这就转换到我们之前的情况了。不知道还有没有其他的解法。下边分析下单链表逆序的思路。


6. 迭代思想

首先看一下原链表。44.jpg


总共需要添加两个指针,pre 和 next。初始化 pre 指向 NULL 。4.jpg


然后就是迭代的步骤,总共四步,顺序一步都不能错。

  • next 指向 head 的 next ,防止原链表丢失
    46.jpg
  • head 的 next 从原来链表脱离,指向 pre 。47.jpg
  • pre 指向 head48.jpg
  • head 指向 next49.jpg
  • 一次迭代就完成了,如果再进行一次迭代就变成下边的样子。50.jpg

可以看到整个过程无非是把旧链表的 head 取下来,添加的新的链表上。代码怎么写呢?

next = head -> next; //保存 head 的 next , 以防取下 head 后丢失
head -> next = pre; //将 head 从原链表取下来,添加到新链表上
pre = head;// pre 右移
head = next; // head 右移

接下来就是停止条件了,我们再进行一次循环。51.jpg

可以发现当 head 或者 next 指向 null 的时候,我们就可以停止了。此时将 pre 返回,便是逆序了的链表了。


7. 迭代代码

public ListNode reverseList(ListNode head){
        if(head==null) return null;
        ListNode pre=null;
        ListNode next;
        while(head!=null){
            next=head.next;
            head.next=pre;
            pre=head;
            head=next;
        }
        return pre;
    }


8. 递归思想


首先假设我们实现了将单链表逆序的函数,ListNode reverseListRecursion(ListNode head) ,传入链表头,返回逆序后的链表头。


接着我们确定如何把问题一步一步的化小,我们可以这样想。


把 head 结点拿出来,剩下的部分我们调用函数 reverseListRecursion ,这样剩下的部分就逆序了,接着我们把 head 结点放到新链表的尾部就可以了。这就是整个递归的思了。52.jpg


head 结点拿出来

53.jpg

剩余部分调用逆序函数 reverseListRecursion ,并得到了 newhead

54.jpg



将 2 指向 1 ,1 指向 null,将 newhead 返回即可

55.jpg


找到递归出口


当然就是如果结点的个数是一个,那么逆序的话还是它本身,直接 return 就够了。怎么判断结点个数是不是一个呢?它的 next 等于 null 就说明是一个了。但如果传进来的本身就是 null,那么直接找它的 next 会报错,所以先判断传进来的是不是 null ,如果是,也是直接返回就可以了。


9. 代码

public ListNode reverseListRecursion(ListNode head){ 
        ListNode newHead;
        if(head==null||head.next==null ){
            return head;
        }
        newHead=reverseListRecursion(head.next); //head.next 作为剩余部分的头指针
        head.next.next=head; //head.next 代表新链表的尾,将它的 next 置为 head,就是将 head 加到最后了。
        head.next=null;
        return newHead;
    }


第三题: Longest Substring Without Repeating Characters

1. 题目描述(中等难度)


56.jpg


给定一个字符串,找到没有重复字符的最长子串,返回它的长度。


2. 解法一


简单粗暴些,找一个最长子串,那么我们用两个循环穷举所有子串,然后再用一个函数判断该子串中有没有重复的字符。

public int lengthOfLongestSubstring(String s) {
    int n = s.length();
    int ans = 0;//保存当前得到满足条件的子串的最大值
    for (int i = 0; i < n; i++)
        for (int j = i + 1; j <= n; j++) //之所以 j<= n,是因为我们子串是 [i,j),左闭右开
            if (allUnique(s, i, j)) ans = Math.max(ans, j - i); //更新 ans
    return ans;
}
public boolean allUnique(String s, int start, int end) {
    Set<Character> set = new HashSet<>();//初始化 hash set
    for (int i = start; i < end; i++) {//遍历每个字符
        Character ch = s.charAt(i);
        if (set.contains(ch)) return false; //判断字符在不在 set 中
        set.add(ch);//不在的话将该字符添加到 set 里边
    }
    return true;
}

时间复杂度:两个循环,加上判断子串满足不满足条件的函数中的循环,O(n³)。


空间复杂度:使用了一个 set,判断子串中有没有重复的字符。由于 set 中没有重复的字符,所以最长就是整个字符集,假设字符集的大小为 m ,那么 set 最长就是 m 。另一方面,如果字符串的长度小于 m ,是 n 。那么 set 最长也就是 n 了。综上,空间复杂度为 O(min(m,n))。


3. 解法二


遗憾的是上边的算法没有通过 leetCode,时间复杂度太大,造成了超时。我们怎么来优化一下呢?


上边的算法中,我们假设当 i 取 0 的时候,


j 取 1,判断字符串 str[0,1) 中有没有重复的字符。


j 取 2,判断字符串 str[0,2) 中有没有重复的字符。


j 取 3,判断字符串 str[0,3) 中有没有重复的字符。


j 取 4,判断字符串 str[0,4) 中有没有重复的字符。


做了很多重复的工作,因为如果 str[0,3) 中没有重复的字符,我们不需要再判断整个字符串 str[0,4) 中有没有重复的字符,而只需要判断 str[3] 在不在 str[0,3) 中,不在的话,就表明 str[0,4) 中没有重复的字符。


如果在的话,那么 str[0,5) ,str[0,6) ,str[0,7) 一定有重复的字符,所以此时后边的 j 也不需要继续增加了。i ++ 进入下次的循环就可以了。


此外,我们的 j 也不需要取 j + 1,而只需要从当前的 j 开始就可以了。


综上,其实整个关于 j 的循环我们完全可以去掉了,此时可以理解变成了一个「滑动窗口」。57.jpg


整体就是橘色窗口在依次向右移动。


判断一个字符在不在字符串中,我们需要可以遍历整个字符串,遍历需要的时间复杂度就是 O(n),加上最外层的 i 的循环,总体复杂度就是 O(n²)。我们可以继续优化,判断字符在不在一个字符串,我们可以将已有的字符串存到 Hash 里,这样的时间复杂度是 O(1),总的时间复杂度就变成了 O(n)。

public class Solution {
    public int lengthOfLongestSubstring(String s) {
        int n = s.length();
        Set<Character> set = new HashSet<>();
        int ans = 0, i = 0, j = 0;
        while (i < n && j < n) {
            if (!set.contains(s.charAt(j))){
                set.add(s.charAt(j++));
                ans = Math.max(ans, j - i);
            }
            else {
                set.remove(s.charAt(i++));
            }
        }
        return ans;
    }
}

时间复杂度:在最坏的情况下,while 循环中的语句会执行 2n 次,例如 abcdefgg,开始的时候 j 一直后移直到到达第二个 g 的时候固定不变 ,然后 i 开始一直后移直到 n ,所以总共执行了 2n 次,时间复杂度为 O(n)。


空间复杂度:和上边的类似,需要一个 Hash 保存子串,所以是 O(min(m,n))。


4. 解法三


继续优化,我们看上边的算法的一种情况。

57.jpg


当 j 指向的 c 存在于前边的子串 abcd 中,此时 i 向前移到 b ,此时子串中仍然含有 c,还得继续移动,所以这里其实可以优化。我们可以一步到位,直接移动到子串 c 的位置的下一位!

58.jpg


实现这样的话,我们将 set 改为 map ,将字符存为 key ,将对应的下标存到 value 里就实现了。

public class Solution {
    public int lengthOfLongestSubstring(String s) {
        int n = s.length(), ans = 0;
        Map<Character, Integer> map = new HashMap<>(); 
        for (int j = 0, i = 0; j < n; j++) {
            if (map.containsKey(s.charAt(j))) {
                i = Math.max(map.get(s.charAt(j)), i); 
            }
            ans = Math.max(ans, j - i + 1);
            map.put(s.charAt(j), j + 1);//下标 + 1 代表 i 要移动的下个位置
        }
        return ans;
    }
}

与解法二相比


由于采取了 i 跳跃的形式,所以 map 之前存的字符没有进行 remove ,所以 if 语句中进行了Math.max ( map.get ( s.charAt ( j ) ) , i ),要确认得到的下标不是 i 前边的。


还有个不同之处是 j 每次循环都进行了自加 1 ,因为 i 的跳跃已经保证了 str[ i , j] 内没有重复的字符串,所以 j 直接可以加 1 。而解法二中,要保持 j 的位置不变,因为不知道和 j 重复的字符在哪个位置。


最后个不同之处是, ans 在每次循环中都进行更新,因为 ans 更新前 i 都进行了更新,已经保证了当前的子串符合条件,所以可以更新 ans 。而解法二中,只有当当前的子串不包含当前的字符时,才进行更新。


时间复杂度:我们将 2n 优化到了 n ,但最终还是和之前一样,O(n)。


空间复杂度:也是一样的,O(min(m,n))。


5. 解法四


和解法三思路一样,区别的地方在于,我们不用 Hash ,而是直接用数组,字符的 ASCII 码值作为数组的下标,数组存储该字符所在字符串的位置。适用于字符集比较小的情况,因为我们会直接开辟和字符集等大的数组。

public class Solution {
    public int lengthOfLongestSubstring(String s) {
        int n = s.length(), ans = 0;
        int[] index = new int[128];   
        for (int j = 0, i = 0; j < n; j++) {
            i = Math.max(index[s.charAt(j)], i);
            ans = Math.max(ans, j - i + 1);
            index[s.charAt(j)] = j + 1;//(下标 + 1) 代表 i 要移动的下个位置
        }
        return ans;
    }
}

和解法 3 不同的地方在于,没有了 if 的判断,因为如果 index[ s.charAt ( j ) ] 不存在的话,它的值会是 0 ,对最终结果不会影响。

时间复杂度:O(n)。

空间复杂度:O(m),m 代表字符集的大小。这次不论原字符串多小,都会利用这么大的空间。


6. 总结


综上,我们一步一步的寻求可优化的地方,对算法进行了优化。又加深了 Hash 的应用,以及利用数组巧妙的实现了 Hash 的作用。



目录
相关文章
|
5月前
|
负载均衡 算法 关系型数据库
大数据大厂之MySQL数据库课程设计:揭秘MySQL集群架构负载均衡核心算法:从理论到Java代码实战,让你的数据库性能飙升!
本文聚焦 MySQL 集群架构中的负载均衡算法,阐述其重要性。详细介绍轮询、加权轮询、最少连接、加权最少连接、随机、源地址哈希等常用算法,分析各自优缺点及适用场景。并提供 Java 语言代码实现示例,助力直观理解。文章结构清晰,语言通俗易懂,对理解和应用负载均衡算法具有实用价值和参考价值。
大数据大厂之MySQL数据库课程设计:揭秘MySQL集群架构负载均衡核心算法:从理论到Java代码实战,让你的数据库性能飙升!
|
5月前
|
存储 缓存 监控
上网行为监控系统剖析:基于 Java LinkedHashMap 算法的时间序列追踪机制探究
数字化办公蓬勃发展的背景下,上网行为监控系统已成为企业维护信息安全、提升工作效能的关键手段。该系统需实时记录并深入分析员工的网络访问行为,如何高效存储和管理这些处于动态变化中的数据,便成为亟待解决的核心问题。Java 语言中的LinkedHashMap数据结构,凭借其独有的有序性特征以及可灵活配置的淘汰策略,为上网行为监控系统提供了一种兼顾性能与功能需求的数据管理方案。本文将对LinkedHashMap在上网行为监控系统中的应用原理、实现路径及其应用价值展开深入探究。
105 3
|
5月前
|
人工智能 算法 NoSQL
LRU算法的Java实现
LRU(Least Recently Used)算法用于淘汰最近最少使用的数据,常应用于内存管理策略中。在Redis中,通过`maxmemory-policy`配置实现不同淘汰策略,如`allkeys-lru`和`volatile-lru`等,采用采样方式近似LRU以优化性能。Java中可通过`LinkedHashMap`轻松实现LRUCache,利用其`accessOrder`特性和`removeEldestEntry`方法完成缓存淘汰逻辑,代码简洁高效。
194 0
|
4月前
|
存储 算法 安全
Java中的对称加密算法的原理与实现
本文详细解析了Java中三种常用对称加密算法(AES、DES、3DES)的实现原理及应用。对称加密使用相同密钥进行加解密,适合数据安全传输与存储。AES作为现代标准,支持128/192/256位密钥,安全性高;DES采用56位密钥,现已不够安全;3DES通过三重加密增强安全性,但性能较低。文章提供了各算法的具体Java代码示例,便于快速上手实现加密解密操作,帮助用户根据需求选择合适的加密方案保护数据安全。
345 58
|
3月前
|
存储 负载均衡 算法
我们来说一说 Java 的一致性 Hash 算法
我是小假 期待与你的下一次相遇 ~
104 1
|
3月前
|
存储 监控 算法
企业上网监控场景下布隆过滤器的 Java 算法构建及其性能优化研究
布隆过滤器是一种高效的数据结构,广泛应用于企业上网监控系统中,用于快速判断员工访问的网址是否为违规站点。相比传统哈希表,它具有更低的内存占用和更快的查询速度,支持实时拦截、动态更新和资源压缩,有效提升系统性能并降低成本。
73 0
|
6月前
|
存储 机器学习/深度学习 监控
如何监控员工的电脑——基于滑动时间窗口的Java事件聚合算法实现探析​
在企业管理场景中,如何监控员工的电脑操作行为是一个涉及效率与合规性的重要课题。传统方法依赖日志采集或屏幕截图,但数据量庞大且实时性不足。本文提出一种基于滑动时间窗口的事件聚合算法,通过Java语言实现高效、低资源占用的监控逻辑,为如何监控员工的电脑提供一种轻量化解决方案。
134 3
|
Unix Shell Linux
LeetCode刷题 Shell编程四则 | 194. 转置文件 192. 统计词频 193. 有效电话号码 195. 第十行
本文提供了几个Linux shell脚本编程问题的解决方案,包括转置文件内容、统计词频、验证有效电话号码和提取文件的第十行,每个问题都给出了至少一种实现方法。
188 6
LeetCode刷题 Shell编程四则 | 194. 转置文件 192. 统计词频 193. 有效电话号码 195. 第十行
|
Python
【Leetcode刷题Python】剑指 Offer 32 - III. 从上到下打印二叉树 III
本文介绍了两种Python实现方法,用于按照之字形顺序打印二叉树的层次遍历结果,实现了在奇数层正序、偶数层反序打印节点的功能。
140 6
|
搜索推荐 索引 Python
【Leetcode刷题Python】牛客. 数组中未出现的最小正整数
本文介绍了牛客网题目"数组中未出现的最小正整数"的解法,提供了一种满足O(n)时间复杂度和O(1)空间复杂度要求的原地排序算法,并给出了Python实现代码。
305 2