刷爆TOP100热题-day8 Leetcode19、20

持续刷题第8天 !

 今天我们继续刷Leetcode 热题 HOT 100,日复一日,相信自己,一定会有进步。如果一个人刷题太孤独了, 欢迎加群 每日一题算法群 ,让我们大家一起监督,一起成长。

Leetcode - 19.删除链表的第N个结点

题目描述:

给定一个链表,删除链表的倒数第  个节点,并且返回链表的头结点。

进阶:

你能尝试使用一趟扫描实现吗?

示例:

给定一个链表: 1->2->3->4->5, 和 n = 2.


当删除了倒数第二个节点后,链表变为 1->2->3->5.

解题思路:

怎么解呢?

这道题就是普通的链表题,首先我们还是要了解一下链表是一种什么样的数据结构.

我们要删除倒数第n个节点,那么链表它的长度,我们是无法通过一些独特的函数得到的,必须通过遍历才能得到。那么在链表中比较有特点的一个方法,就是双指针法, 双指针法 就是得到列表的一个长度,还有得到倒数第n个节点,还有解决环问题等有用。

我们可以设置快慢指针快指针真先走n步,然后慢指针跟快指针在同时走,快指针到达链表的尾部的时候慢指针指的就是倒数第n个节点。

我们应当考虑这道题的边界情况,有可能删除的节点中包含了第一个节点,那么这个时候我们再加一个 头节点 ,当快指针遍历到最后一个结点的时候弹出,让慢指针执行删除操作即可。

/**
 * Definition for singly-linked list.
 * public class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode(int x) { val = x; }
 * }
 */
class Solution {
    public ListNode removeNthFromEnd(ListNode head, int n) {
        ListNode res=new ListNode(-1);//添加头结点 防止删除第一个结点的情况发生
        res.next=head;
        ListNode p=res;
        ListNode q=res;
        while(n-->0)
            q=q.next;//快指针先走
        while(q.next!=null)
        {
            p=p.next;
            q=q.next;
        }//直到快指针遍历到最后一个结点 
        p.next=p.next.next;//执行删除结点操作,
        return res.next;
    }
}

Leetcode - 20.有效的括号

题目描述:

给定一个只包括 '(',')','{','}','[',']' 的字符串,

判断字符串是否有效。

有效字符串需满足:

左括号必须用相同类型的右括号闭合。

左括号必须以正确的顺序闭合。

注意空字符串可被认为是有效字符串。

示例:

输入: "()"

输出: true

输入: "{[]}"

输出: true

解题思路:

怎么解呢?

这道题我们用到了栈,由于每次我们结束一个括号的使用的时候,都是要找离他最近的对应的一个括号,那么他们之中是 不可以有未结束的括号 ,也就是说,离他最近的元素其实是先进后出的一个概念,就是说当我们先遇到这个号的时候,到最后我们才把它进行匹配,那么后面遇到的括号,我们是要先匹配的

重点也就是匹配的时候,中间不能有其他的未结束的括号。

其实就可以把它看成三个任务,每个任务结束的时候,中间是不能有其他任务未结束的,相当于我们要知道栈顶元素的值,进行比较。

import java.util.*;
class Solution {
    public boolean isValid(String s) {
        Stack<Integer> mapA=new Stack<>();
        Stack<Integer> mapB=new Stack<>();
        Stack<Integer> mapC=new Stack<>();
        mapA.push(-1);
        mapB.push(-1);
        mapC.push(-1);
        for(int i=0;i<s.length();i++){
            if(s.charAt(i)=='(')
                mapA.push(i);
            else if(s.charAt(i)=='{')
                mapB.push(i);
            else if(s.charAt(i)=='[')
                mapC.push(i);
            else if(s.charAt(i)==')')
            {
                if(mapA.size()==1 ||(mapA.peek()<mapB.peek() || mapA.peek()<mapC.peek()))
                    return false;
                else
                    mapA.pop();
            }
            else if(s.charAt(i)=='}')
            {
                if(mapB.size()==1 ||(mapB.peek()<mapA.peek() || mapB.peek()<mapC.peek()))
                    return false;
                else 
                    mapB.pop();
            }
            else{
                if(mapC.size()==1 || (mapC.peek()<mapB.peek() || mapC.peek()<mapA.peek()))
                    return false;
                else
                    mapC.pop();
            }
        }
        if(mapC.size()==1 && mapC.size()==mapB.size() && mapA.size()==mapC.size())
            return true;
        return false;
    }
}

往期回顾

LeetCode day 1 题号1、2(两数之和,两数相加)

LeetCode day 2 题号 3、4 (最长无重复子串,两个有序数组的中位数)

LeetCode day3 题号5 (最长回文子串)

LeetCode day 4  10.正则匹配

LeetCode day 5 盛最多水的容器(双指针)

LeetCode day 6 三数之和=两数之和plus

扫码加入我们

我来评几句
登录后评论

已发表评论数()

相关站点

热门文章