LeetCode-Java(05)

这篇具有很好参考价值的文章主要介绍了LeetCode-Java(05)。希望对大家有所帮助。如果存在错误或未考虑完全的地方,请大家不吝赐教,您也可以点击"举报违法"按钮提交疑问。

19. 删除链表的倒数第 N 个结点

LeetCode-Java(05),LeetCode刷题,leetcode,java,算法

两个方法,方法一是先走一遍链表得出链表长度,再走第二遍,找到倒数第n个数。方法二是双指针,首先快指针就比慢指针多走n步,然后这俩指针同步走,快指针走到头了,慢指针也就指向目标节点了。

方法一:

class Solution {
    public ListNode removeNthFromEnd(ListNode head, int n) {
        ListNode dummy = new ListNode(0, head);
        int length = getLength(head);
        ListNode cur = dummy;
        for (int i = 1; i < length - n + 1; ++i) {
            cur = cur.next;
        }
        cur.next = cur.next.next;
        ListNode ans = dummy.next;
        return ans;
    }

    public int getLength(ListNode head) {
        int length = 0;
        while (head != null) {
            ++length;
            head = head.next;
        }
        return length;
    }
}

方法二:

class Solution {
    public ListNode removeNthFromEnd(ListNode head, int n) {
        ListNode dummy = new ListNode(0, head);
        ListNode first = head;
        ListNode second = dummy;
        for (int i = 0; i < n; ++i) {
            first = first.next;
        }
        while (first != null) {
            first = first.next;
            second = second.next;
        }
        second.next = second.next.next;
        ListNode ans = dummy.next;
        return ans;
    }
}

20. 有效的括号  ⭐

LeetCode-Java(05),LeetCode刷题,leetcode,java,算法

括号匹配,肯定用栈啊

class Solution {
public boolean isValid(String s) {
        if(s.isEmpty())
            return true;
        Stack<Character> stack=new Stack<Character>();
        for(char c:s.toCharArray()){
            if(c=='(')
                stack.push(')');
            else if(c=='{')
                stack.push('}');
            else if(c=='[')
                stack.push(']');
            else if(stack.empty()||c!=stack.pop())
                return false;
        }
    return stack.empty();
    }
}

给定的字符串s = "{([])()}"

  • 遇到'{'时,将对应的右括号'}'压入栈中。 栈内变化:}
  • 遇到'('时,将对应的右括号')'压入栈中。 栈内变化:},)
  • 遇到'['时,将对应的右括号']'压入栈中。 栈内变化:},),]
  • 遇到']'时,检查栈顶元素是否为']',如果不是则返回false,否则将栈顶元素弹出。 栈内变化:},)
  • 遇到')'时,检查栈顶元素是否为')',如果不是则返回false,否则将栈顶元素弹出。 栈内变化:}
  • 遇到'('时,将对应的右括号')'压入栈中。 栈内变化:},)
  • 遇到')'时,检查栈顶元素是否为')',如果不是则返回false,否则将栈顶元素弹出。 栈内变化:}
  • 遇到'}'时,检查栈顶元素是否为'}',如果不是则返回false,否则将栈顶元素弹出。 栈内变化:empty
  • 当遍历完所有字符后,如果栈为空,则说明括号是合法的,返回true;否则返回false

21. 合并两个有序链表

递归写法就是比较大小

class Solution {
    public ListNode mergeTwoLists(ListNode list1, ListNode list2) {
        if(list1 == null){
            return list2;
        }
        if(list2 == null){
            return list1;
        }
        if(list1.val <= list2.val){
            list1.next = mergeTwoLists(list1.next, list2);
            return list1;
        }else{

            list2.next = mergeTwoLists(list1, list2.next);
            return list2;
        }     
    }
}

非递归:首先判断特殊情况(为空时),定义一个newhead=初始值最小的那个,然后h1或者h2向后移位,每次比较h1和h2的大小,谁小就连谁。最后当有一个连完了,直接把另一个整个接上就行。

class Solution {
    public ListNode mergeTwoLists(ListNode pHead1, ListNode pHead2) {
        if (pHead1 == null) return pHead2;
        else if (pHead2 == null) return pHead1;
        else {
            ListNode newhead=new ListNode(-1);
            ListNode p = newhead;
            while (pHead1 != null && pHead2 != null) {
                if (pHead1.val < pHead2.val) {
                    p.next = pHead1;
                    p=p.next;
                    pHead1 = pHead1.next;
                } else {
                    p.next = pHead2;
                    p=p.next;
                    pHead2 = pHead2.next;
                }
            }
            if(pHead1==null) p.next=pHead2;
            else p.next=pHead1;
            return newhead.next;
        }
    }
}

22. 括号生成  ⭐⭐

LeetCode-Java(05),LeetCode刷题,leetcode,java,算法

LeetCode-Java(05),LeetCode刷题,leetcode,java,算法

  • 当前左右括号都有大于 000 个可以使用的时候,才产生分支;
  • 产生左分支的时候,只看当前是否还有左括号可以使用;
  • 产生右分支的时候,还受到左分支的限制,右边剩余可以使用的括号数量一定得在严格大于左边剩余的数量的时候,才可以产生分支;
  • 在左边和右边剩余的括号数都等于 000 的时候结算。
import java.util.ArrayList;
import java.util.List;

public class Solution {

    // 做加法

    public List<String> generateParenthesis(int n) {
        List<String> res = new ArrayList<>();
        // 特判
        if (n == 0) {
            return res;
        }

        dfs("", 0, 0, n, res);
        return res;
    }

    /**
     * @param curStr 当前递归得到的结果
     * @param left   左括号已经用了几个
     * @param right  右括号已经用了几个
     * @param n      左括号、右括号一共得用几个
     * @param res    结果集
     */
    private void dfs(String curStr, int left, int right, int n, List<String> res) {
        if (left == n && right == n) {
            res.add(curStr);
            return;
        }

        // 剪枝
        if (left < right) {
            return;
        }

        if (left < n) {
            dfs(curStr + "(", left + 1, right, n, res);
        }
        if (right < n) {
            dfs(curStr + ")", left, right + 1, n, res);
        }
    }
}

优化一下文章来源地址https://www.toymoban.com/news/detail-628347.html

class Solution {
    public List<String> generateParenthesis(int n) {
        List<String> res = new ArrayList<>();
        backtracking(res, new StringBuilder(), 0, 0, n);
        return res;
    }

    public void backtracking(List<String> res, StringBuilder cur, int open, int close, int max) {
        if (cur.length() == max*2) {
            res.add(cur.toString());
            return;
        }

        if (open < max) {
            cur.append('(');
            backtracking(res, cur, open+1, close, max);
            cur.deleteCharAt(cur.length()-1);
        }

        if (close < open) {
            cur.append(')');
            backtracking(res, cur, open, close+1, max);
            cur.deleteCharAt(cur.length()-1);
        }
    }
}

到了这里,关于LeetCode-Java(05)的文章就介绍完了。如果您还想了解更多内容,请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章,希望大家以后多多支持TOY模板网!

本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如若转载,请注明出处: 如若内容造成侵权/违法违规/事实不符,请点击违法举报进行投诉反馈,一经查实,立即删除!

领支付宝红包 赞助服务器费用

相关文章

  • LeetCode-Java:26.删除有序数组的重复项

    给你一个 非严格递增排列 的数组 nums ,请你 原地 删除重复出现的元素,使每个元素 只出现一次 ,返回删除后数组的新长度。元素的 相对顺序 应该保持 一致 。然后返回 nums 中唯一元素的个数。 考虑 nums 的唯一元素的数量为 k ,你需要做以下事情确保你的题解可以被通过

    2024年02月05日
    浏览(44)
  • Java算法 leetcode简单刷题记录4

    买卖股票的最佳时机: https://leetcode.cn/problems/best-time-to-buy-and-sell-stock/ 笨办法: 记录当天的值及之后的最大值,相减得到利润; 所有的天都计算下,比较得到利润最大值; 会超时 记录过程中遇到的最低值,每当有利润大于0及大于上一个利润值的情况,赋值; 最小和分割:

    2024年01月23日
    浏览(43)
  • Java算法 leetcode简单刷题记录6

    环和杆: https://leetcode.cn/problems/rings-and-rods/ 统计范围内的元音字符串数: https://leetcode.cn/problems/count-the-number-of-vowel-strings-in-range/ 最长平衡子字符串: https://leetcode.cn/problems/find-the-longest-balanced-substring-of-a-binary-string/ K 个元素的最大和: https://leetcode.cn/problems/maximum-sum-with-exa

    2024年01月24日
    浏览(44)
  • java数据结构与算法刷题-----LeetCode283. 移动零

    java数据结构与算法刷题目录(剑指Offer、LeetCode、ACM)-----主目录-----持续更新(进不去说明我没写完): https://blog.csdn.net/grd_java/article/details/123063846 解题思路 双指针,用right和left两个指针,将非0元素,全部按顺序换到数组前面。left指向左边非0元素应该插入的位置,right找到非

    2024年01月21日
    浏览(47)
  • java数据结构与算法刷题-----LeetCode566. 重塑矩阵

    java数据结构与算法刷题目录(剑指Offer、LeetCode、ACM)-----主目录-----持续更新(进不去说明我没写完): https://blog.csdn.net/grd_java/article/details/123063846 代码:时间复杂度O(r*c).除题目要求外,算法本身没有需要额外空间,空间复杂度O(1) 从0开始算,一个3列n行矩阵中,每行就有3个元

    2024年01月21日
    浏览(43)
  • java数据结构与算法刷题-----LeetCode287. 寻找重复数

    java数据结构与算法刷题目录(剑指Offer、LeetCode、ACM)-----主目录-----持续更新(进不去说明我没写完): https://blog.csdn.net/grd_java/article/details/123063846 解题思路 弗洛伊德判圈法,也就是快慢指针判圈法(龟兔赛跑算法),此算法分为两个步骤 判断是否有环,并得到快慢指针相遇

    2024年01月24日
    浏览(38)
  • java数据结构与算法刷题-----LeetCode766. 托普利茨矩阵

    java数据结构与算法刷题目录(剑指Offer、LeetCode、ACM)-----主目录-----持续更新(进不去说明我没写完): https://blog.csdn.net/grd_java/article/details/123063846 解题思路 这道题只要换一种理解方式,瞬间就会变的很简单。 题目描述是每个元素左上和右下对角线元素都相同。但是,我们发

    2024年01月25日
    浏览(45)
  • java数据结构与算法刷题-----LeetCode667. 优美的排列 II

    java数据结构与算法刷题目录(剑指Offer、LeetCode、ACM)-----主目录-----持续更新(进不去说明我没写完): https://blog.csdn.net/grd_java/article/details/123063846 解题思路 题目要求我们返回一个数组长度为n的数组,必须含有1~n的所有数,并且从左到右,相邻的元素依次相减,它们的差,必

    2024年01月25日
    浏览(48)
  • java数据结构与算法刷题-----LeetCode240. 搜索二维矩阵 II

    java数据结构与算法刷题目录(剑指Offer、LeetCode、ACM)-----主目录-----持续更新(进不去说明我没写完): https://blog.csdn.net/grd_java/article/details/123063846 解题思路 法一:把整个数组遍历一遍,时间复杂度O(m*n) 法二:每一行用二分搜索,那么时间复杂度就是O(m * l o g 2 n log_2{n} l o g

    2024年01月22日
    浏览(56)
  • java数据结构与算法刷题-----LeetCode209. 长度最小的子数组

    java数据结构与算法刷题目录(剑指Offer、LeetCode、ACM)-----主目录-----持续更新(进不去说明我没写完): https://blog.csdn.net/grd_java/article/details/123063846 解题思路 代码:时间复杂度O(n).空间复杂度O(1)

    2024年01月21日
    浏览(48)

觉得文章有用就打赏一下文章作者

支付宝扫一扫打赏

博客赞助

微信扫一扫打赏

请作者喝杯咖啡吧~博客赞助

支付宝扫一扫领取红包,优惠每天领

二维码1

领取红包

二维码2

领红包