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

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

目录


第16题. 3Sum Closest

题目描述(中等难度)

解法一 暴力解法

解法二

第17题. Letter Combinations of a Phone Number

题目描述(中等难度)

解法一 定义相乘

解法二 队列迭代

解法三 递归

第18题: 4Sum

题目描述(中等难度)

第19题: Remove Nth Node From End of List

题目描述(中等难度)

解法一

解法二 遍历一次链表

解法三

第20题 : Valid Parentheses

题目描述(简单难度)

喜欢 请点个 + 关注


第16题. 3Sum Closest

题目描述(中等难度)


35.png


上一道题很类似,只不过这个是给一个目标值,找三个数,使得他们的和最接近目标值。


解法一 暴力解法

遍历所有的情况,然后求出三个数的和,和目标值进行比较,选取差值最小的即可。本以为时间复杂度太大了,神奇的是,竟然 AC 了。

public int threeSumClosest(int[] nums, int target) {
    int sub = Integer.MAX_VALUE; //保存和 target 的差值
    int sum = 0; //保存当前最接近 target 的三个数的和
    for (int i = 0; i < nums.length; i++) {
        for (int j = i + 1; j < nums.length; j++)
            for (int k = j + 1; k < nums.length; k++) {
                if (Math.abs((nums[i] + nums[j] + nums[k] - target)) < sub) {
                    sum = nums[i] + nums[j] + nums[k];
                    sub = Math.abs(sum - target);
                }
            }
    }
    return sum;
}


时间复杂度:O(n³),三层循环。

空间复杂度:O(1),常数个。

解法二


受到上一题的启发,没有看的,推荐大家可以看一下。我们完全可以先将数组排序,然后先固定一个数字,然后利用头尾两个指针进行遍历,降低一个 O(n)的时间复杂度。


如果 sum 大于 target 就减小右指针,反之,就增加左指针。

public int threeSumClosest(int[] nums, int target) {
    Arrays.sort(nums);
    int sub=Integer.MAX_VALUE;
    int sum=0;
    for(int i=0;i<nums.length;i++){ 
        int lo=i+1,hi=nums.length-1;
        while(lo<hi){
            if(Math.abs((nums[lo]+nums[hi]+nums[i]-target))<sub){
                sum=nums[lo]+nums[hi]+nums[i];
                sub=Math.abs(sum-target);
            }
            if(nums[lo]+nums[hi]+nums[i]>target){
                hi--;
            }else{
                lo++;
            }
        }
    }
    return sum;
}

时间复杂度:如果是快速排序的 O(logn)O(log_n)O(logn) 再加上 O(n²),所以就是 O(n²)。

空间复杂度:O(1)


和上一道题非常非常的相似了,先对数组排序,然后利用两头的指针,可以说是十分的优雅了。


第17题. Letter Combinations of a Phone Number

题目描述(中等难度)


38.png

给一串数字,每个数可以代表数字键下的几个字母,返回这些数字下的字母的所有组成可能。


解法一 定义相乘

自己想了用迭代,用递归,都理不清楚,灵机一动,想出了这个算法。

把字符串 “23” 看成 [“a”,“b”,c] * [“d”,“e”,“f”] ,而相乘就用两个 for 循环实现即可,看代码应该就明白了。



public List<String> letterCombinations(String digits) {
    List<String> ans = new ArrayList<String>();
    for (int i = 0; i < digits.length(); i++) {
        ans = mul(ans, getList(digits.charAt(i) - '0'));
    }
    return ans;
}
public List<String> getList(int digit) {
        String digitLetter[] = { "", "", "abc", "def", "ghi", "jkl", "mno", "pqrs", "tuv", "wxyz" };
        List<String> ans = new ArrayList<String>();
        for (int i = 0; i < digitLetter[digit].length(); i++) {
            ans.add(digitLetter[digit].charAt(i) + "");
        }
          return ans;
    }
//定义成两个 List 相乘
public List<String> mul(List<String> l1, List<String> l2) {
    if (l1.size() != 0 && l2.size() == 0) {
        return l1;
    }
    if (l1.size() == 0 && l2.size() != 0) {
        return l2;
    }
    List<String> ans = new ArrayList<String>();
    for (int i = 0; i < l1.size(); i++)
        for (int j = 0; j < l2.size(); j++) {
            ans.add(l1.get(i) + l2.get(j));
        }
    return ans;
}

解法二 队列迭代

参考这里,果然有人用迭代写了出来。主要用到了队列。

public List<String> letterCombinations(String digits) {
        LinkedList<String> ans = new LinkedList<String>();
        if(digits.isEmpty()) return ans;
        String[] mapping = new String[] {"0", "1", "abc", "def", "ghi", "jkl", "mno", "pqrs", "tuv", "wxyz"};
        ans.add("");
        for(int i =0; i<digits.length();i++){
            int x = Character.getNumericValue(digits.charAt(i));
            while(ans.peek().length()==i){ //查看队首元素
                String t = ans.remove(); //队首元素出队
                for(char s : mapping[x].toCharArray())
                    ans.add(t+s);
            }
        }
        return ans;
    }

假如是 “23” ,那么


第 1 次 for 循环结束后变为 a, b, c;


第 2 次 for 循环的第 1 次 while 循环 a 出队,分别加上 d e f 然后入队,就变成 b c ad ae af


第 2 次 for 循环的第 2 次 while 循环 b 出队,分别加上 d e f 然后入队,就变成 c ad ae af bd be bf


第 2 次 for 循环的第 3 次 while 循环 c 出队,分别加上 d e f 然后入队,就变成 ad ae af bd be bf cd ce cf


这样的话队列的元素长度再也没有等于 1 的了就出了 while 循环。


解法三 递归

参考这里

private static final String[] KEYS = { "", "", "abc", "def", "ghi", "jkl", "mno", "pqrs", "tuv", "wxyz" };
public List<String> letterCombinations(String digits) {
    if(digits.equals("")) {
        return new ArrayList<String>();
    }
    List<String> ret = new LinkedList<String>();
    combination("", digits, 0, ret);
    return ret;
}
private void combination(String prefix, String digits, int offset, List<String> ret) {
    //offset 代表在加哪个数字
    if (offset == digits.length()) {
        ret.add(prefix);
        return;
    }
    String letters = KEYS[(digits.charAt(offset) - '0')];
    for (int i = 0; i < letters.length(); i++) {
        combination(prefix + letters.charAt(i), digits, offset + 1, ret);
    }
}

39.png

从 a 开始 ,然后递归到 d ,然后 g ,就把 adg 加入,然后再加入 adh,再加入 adi … 从左到右,递归到底之后就将其加入。

这种题的时间复杂度和空间复杂度自己理的不太清楚就没有写了。


第18题: 4Sum

题目描述(中等难度)


41.png

3Sum类似,只不过是找四个数,使得和为 target,并且不能有重复的序列。

如果之前没有做过3Sum可以先看看,自己在上边的基础上加了一个循环而已。

public List<List<Integer>> fourSum(int[] num, int target) {
    Arrays.sort(num);
    List<List<Integer>> res = new LinkedList<>();
    //多加了层循环
    for (int j = 0; j < num.length - 3; j++) {
        //防止重复的
        if (j == 0 || (j > 0 && num[j] != num[j - 1]))
            for (int i = j + 1; i < num.length - 2; i++) {
                //防止重复的,不再是 i == 0 ,因为 i 从 j + 1 开始
                if (i == j + 1 || num[i] != num[i - 1]) {
                    int lo = i + 1, hi = num.length - 1, sum = target - num[j] - num[i];
                    while (lo < hi) {
                        if (num[lo] + num[hi] == sum) {
                            res.add(Arrays.asList(num[j], num[i], num[lo], num[hi]));
                            while (lo < hi && num[lo] == num[lo + 1])
                                lo++;
                            while (lo < hi && num[hi] == num[hi - 1])
                                hi--;
                            lo++;
                            hi--;
                        } else if (num[lo] + num[hi] < sum)
                            lo++;
                        else
                            hi--;
                    }
                }
            }
    }
    return res;
}

时间复杂度:O(n³)。

空间复杂度:O(N),最坏情况,即 N 是指 n 个元素的排列组合个数,即 N=Cn4N=C^4_nN=Cn4,用来保存结果。

完全是按照 3Sum 的思路写的,比较好理解。


第19题: Remove Nth Node From End of List

题目描述(中等难度)


41.png

给定一个链表,将倒数第 n 个结点删除。


解法一

删除一个结点,无非是遍历链表找到那个结点前边的结点,然后改变下指向就好了。但由于它是链表,它的长度我们并不知道,我们得先遍历一遍得到它的长度,之后用长度减去 n 就是要删除的结点的位置,然后遍历到结点的前一个位置就好了。


public ListNode removeNthFromEnd(ListNode head, int n) {
    int len = 0;
    ListNode h = head;
    while (h != null) {
        h = h.next;
        len++;
    }
    //长度等于 1 ,再删除一个结点就为 null 了
    if (len == 1) {
        return null;
    }
    int rm_node_index = len - n;
    //如果删除的是头结点
    if (rm_node_index == 0) {
        return head.next;
    }
    //找到被删除结点的前一个结点
    h = head;
    for (int i = 0; i < rm_node_index - 1; i++) {
        h = h.next;
    }
    //改变指向
    h.next = h.next.next;
    return head;
}


时间复杂度:假设链表长度是 L ,那么就第一个循环是 L 次,第二个循环是 L - n 次,总共 2L - n 次,所以时间复杂度就是 O(L)。


空间复杂度:O(1)。


我们看到如果长度等于 1 和删除头结点的时候需要单独判断,其实我们只需要在 head 前边加一个空节点,就可以避免单独判断


public ListNode removeNthFromEnd(ListNode head, int n) {
    ListNode dummy = new ListNode(0);
    dummy.next = head;
    int length  = 0;
    ListNode first = head;
    while (first != null) {
        length++;
        first = first.next;
    }
    length -= n;
    first = dummy;
    while (length > 0) {
        length--;
        first = first.next;
    }
    first.next = first.next.next;
    return dummy.next;
}



解法二 遍历一次链表


上边我们遍历链表进行了两次,我们如何只遍历一次呢。


看了 leetcode 的讲解。


想象一下,两个人进行 100m 赛跑,假设他们的速度相同。开始的时候,第一个人就在第二个人前边 10m ,这样当第一个人跑到终点的时候,第二个人相距第一个人依旧是 10m ,也就是离终点 10m。


对比于链表,我们设定两个指针,先让第一个指针遍历 n 步,然后再让它俩同时开始遍历,这样的话,当第一个指针到头的时候,第二个指针就离第一个指针有 n 的距离,所以第二个指针的位置就刚好是倒数第 n 个结点。

public ListNode removeNthFromEnd(ListNode head, int n) {
    ListNode dummy = new ListNode(0);
    dummy.next = head;
    ListNode first = dummy;
    ListNode second = dummy;
    //第一个指针先移动 n 步
    for (int i = 1; i <= n + 1; i++) {
        first = first.next;
    } 
    //第一个指针到达终点停止遍历
    while (first != null) {
        first = first.next;
        second = second.next;
    }
    second.next = second.next.next;
    return dummy.next;
}

时间复杂度:


第一个指针从 0 到 n ,然后「第一个指针再从 n 到结束」和「第二个指针从 0 到倒数第 n 个结点的位置」同时进行。


而解法一无非是先从 0 到 结束,然后从 0 到倒数第 n 个结点的位置。


所以其实它们语句执行的次数其实是一样的,从 0 到倒数第 n 个结点的位置都被遍历了 2 次,所以总共也是 2L - n 次。只不过这个解法把解法一的两次循环合并了一下,使得第二个指针看起来是顺便遍历,想法很 nice。


所以本质上,它们其实是一样的,时间复杂度依旧是 O(n)。


空间复杂度:O(1)。


解法三

没看讲解前,和室友讨论下,如何只遍历一次链表。室友给出了一个我竟然无法反驳的观点,哈哈哈哈。

第一次遍历链表确定长度的时候,顺便把每个结点存到数组里,这样找结点的时候就不需要再遍历一次了,空间换时间???哈哈哈哈哈哈哈哈哈。


public ListNode removeNthFromEnd(ListNode head, int n) {
    List<ListNode> l = new ArrayList<ListNode>();
    ListNode h = head;
    int len = 0;
    while (h != null) {
        l.add(h);
        h = h.next;
        len++;
    }
    if (len == 1) {
        return null;
    }
    int remove = len - n;
    if (remove == 0) {
        return head.next;
    }
    //直接得到,不需要再遍历了
    ListNode r = l.get(remove - 1);
    r.next = r.next.next;
    return head;
}

时间复杂度:O(L)。

空间复杂度:O(L)。

利用两个指针先固定间隔,然后同时遍历,真的是很妙!另外室友的想法也很棒,哈哈哈哈哈。


第20题 : Valid Parentheses

题目描述(简单难度)


42.png

括号匹配问题。


如果只有一种括号,我们完全可以用一个计数器 count ,遍历整个字符串,遇到左括号加 1 ,遇到右括号减 1,遍历结束后,如果 count 等于 0 ,则表示全部匹配。但如果有多种括号,像 ( [ ) ] 这种情况它依旧会得到 0,所以我们需要用其他的方法。


栈!


遍历整个字符串,遇到左括号就入栈,然后遇到和栈顶对应的右括号就出栈,遍历结束后,如果栈为空,就表示全部匹配。


public boolean isValid(String s) {
    Stack<Character>  brackets  = new Stack<Character>(); 
    for(int i = 0;i < s.length();i++){
        char c = s.charAt(i);
        switch(c){
            case '(':
            case '[':
            case '{':
                brackets.push(c); 
                break;
            case ')':
                if(!brackets.empty()){
                    if(brackets.peek()== '('){
                        brackets.pop();
                    }else{
                        return false;
                    }
                }else{
                    return false;
                }
                break;
            case ']':
                if(!brackets.empty()){
                    if(brackets.peek()=='['){
                        brackets.pop();
                    }else{
                        return false;
                    }
                }else{
                    return false;
                }
                break;
            case '}':
                if(!brackets.empty()){
                    if(brackets.peek()=='{'){
                        brackets.pop();
                    }else{
                        return false;
                    }
                }else{
                    return false;
                }
        }
    }
    return brackets.empty();
}

时间复杂度:O(n)。

空间复杂度:O(n)。

如果学过数据结构,一定写过计算器,括号匹配问题一定遇到过的。

今天我们一起学习了LeetCode 题的算法分析,感谢大家阅读,觉得不错记得收藏哦!


喜欢 请点个 + 关注

目录
相关文章
|
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
|
8月前
|
存储 算法 Java
解锁“分享文件”高效密码:探秘 Java 二叉搜索树算法
在信息爆炸的时代,文件分享至关重要。二叉搜索树(BST)以其高效的查找性能,为文件分享优化提供了新路径。本文聚焦Java环境下BST的应用,介绍其基础结构、实现示例及进阶优化。BST通过有序节点快速定位文件,结合自平衡树、多线程和权限管理,大幅提升文件分享效率与安全性。代码示例展示了文件插入与查找的基本操作,适用于大规模并发场景,确保分享过程流畅高效。掌握BST算法,助力文件分享创新发展。
|
9月前
|
存储 人工智能 算法
解锁分布式文件分享的 Java 一致性哈希算法密码
在数字化时代,文件分享成为信息传播与协同办公的关键环节。本文深入探讨基于Java的一致性哈希算法,该算法通过引入虚拟节点和环形哈希空间,解决了传统哈希算法在分布式存储中的“哈希雪崩”问题,确保文件分配稳定高效。文章还展示了Java实现代码,并展望了其在未来文件分享技术中的应用前景,如结合AI优化节点布局和区块链增强数据安全。
|
7天前
|
存储 编解码 算法
【多光谱滤波器阵列设计的最优球体填充】使用MSFA设计方法进行各种重建算法时,图像质量可以提高至多2 dB,并在光谱相似性方面实现了显著提升(Matlab代码实现)
【多光谱滤波器阵列设计的最优球体填充】使用MSFA设计方法进行各种重建算法时,图像质量可以提高至多2 dB,并在光谱相似性方面实现了显著提升(Matlab代码实现)