【Day26】LeetCode算法刷题 [856. 括号的分数 ] [234. 回文链表]

简介: 学习LeetCode算法刷题 [856. 括号的分数 ] [234. 回文链表]。

刷题打卡,第 二十六 天


题目一、856. 括号的分数

题目二、234. 回文链表


题目一、856. 括号的分数


原题链接:856. 括号的分数


题目描述:


给定一个平衡括号字符串 S,按下述规则计算该字符串的分数:


() 得 1 分。

AB 得 A + B 分,其中 A 和 B 是平衡括号字符串。

(A) 得 2 * A 分,其中 A 是平衡括号字符串。

/

示例 1:

输入: “()”

输出: 1

/

示例 2:

输入: “(())”

输出: 2

/

示例 3:

输入: “()()”

输出: 2

/

示例 4:

输入: “(()(()))”

输出: 6

/

提示:

S 是平衡括号字符串,且只含有 ( 和 ) 。

2 <= S.length <= 50


解题思路:

我们可以借助栈结构来计算平衡括号字符串的得分。


我们首先将当前得分0入栈,准备计算平衡括号字符串s的得分:


当我们遇到左括号(,我们将当前左括号囊括范围中的平衡括号字符子串 得分0入栈,准备计算子串 的得分。


当我们遇到右括号):

①首先就说明了,当前的平衡括号字符内子串 的得分已经计算好,弹出栈顶元素,记录为v,它代表着平衡括号中子串 的得分。

②弹出子串得分后,我们再弹出栈顶元素,记作top,它代表着当前字符串的总得分,我们需要将总得分加上子串得分,获得新的总分。


– 当括号内子串为空,也就是v=0就说明当前平衡括号得分为 1 { () 得 1 分 }


–当括号内子串为空,v就代表着子串得分,那么平衡括号得分为2*v { (A) 得 2 * A 分 }


得到当前字符串总分后,将其压栈,继续遍历后续的字符串,完成字符串s的遍历后,栈顶元素就是得到的总分了,我们直接返回即可。


提交代码:

class Solution {
    public int scoreOfParentheses(String s) {
        Deque<Integer> dq = new LinkedList<>(); //创建栈结构
        dq.push(0);                             //将当前的总分0入栈
      for(int i = 0;i < s.length();++i){      //遍历平衡括号字符串s
            if(s.charAt(i) == '('){             //如果遇到左括号‘(’
                dq.push(0);                     //将0入栈,准备计算括号中平衡括号字符串的分数
            }
            else{                               //如果遇到右括号‘)’
                int v = dq.pop();               //括号中的分数记录好了,栈顶弹出,记录其值
                //栈顶弹出,获取当前总分,加上获取到的括号中的分数;
                //括号中字符串为空,v = 0,于是总分+1;不为空,总分+2v;
                int top = dq.pop() + Math.max(2*v,1);
                dq.push(top);                   //总分入栈
            }
        }
        return dq.pop();                        //栈顶元素表示的就是当前总分
    }
}

提交结果:

微信图片_20221030205814.png


题目二、234. 回文链表


原题链接:234. 回文链表


题目描述:


给你一个单链表的头节点 head ,请你判断该链表是否为回文链表。如果是,返回 true ;否则,返回 false 。

/

示例 1:

微信图片_20221030205822.png

输入:head = [1,2,2,1]

输出:true

/

示例 2:

微信图片_20221030205828.png

输入:head = [1,2]

输出:false


解题思路:

我们需要判断链表中的节点值是否为回文字,如果靠链表来遍历判断,这是十分困难的,因为链表遍历只能从头到尾,而且遍历过后就不能再遍历回当前位置之前的节点了。


如果元素都存放在数组中,我们就可以借助双指针,头位置向后遍历的同时,末尾位置向前遍历,如果两个指针遍历到的元素完全相同,我们就可以确定这是回文串了,反之就能确定不是回文串。


所以为了让判断变得简单起来,我们需要准备一个数组,通过遍历链表将链表节点按照原本的顺序存放到数组中,在对数组进行双指针遍历。


这样一来我们就可以解决这个问题啦…


提交代码:

/**
 * Definition for singly-linked list.
 * public class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode() {}
 *     ListNode(int val) { this.val = val; }
 *     ListNode(int val, ListNode next) { this.val = val; this.next = next; }
 * }
 */
class Solution {
    public boolean isPalindrome(ListNode head) {
        ArrayList<Integer> list = new ArrayList<>(); //常见数组集合list
        while(head != null){     //遍历链表
            list.add(head.val);  //链表元素存入数组集合中
            head = head.next;    //位置向后移动,遍历下一个节点
        }
       int left = 0;             //集合第一个元素下标
        int right = list.size()-1;//集合最后一个元素下标
        while(left < right){      //双指针同时遍历
            if(list.get(left) != list.get(right)) //如果遇到两个指针指向不同值的情况
            return false;         //说明不是回文串,返回false
            ++left;               //左指针后移
        --right;              //右指针前移
      }
        return true;              //指针错位前,遍历没有停止,说明为回文串
    }
}

提交结果:

微信图片_20221030205834.png


⚽求关注⚽ 作者🥇 .29. 🥇 的✔博客主页✔

⚽来刷题⚽ 记录每日LeetCode✔刷题专栏✔

您的点赞,收藏以及关注是对作者最大的鼓励喔 ~~

微信图片_20221030205840.png


目录
相关文章
|
14天前
【数据结构OJ题】链表的回文结构
牛客题目——链表的回文结构
18 0
【数据结构OJ题】链表的回文结构
|
13天前
|
存储 算法 C语言
刷题训练之链表
刷题训练之链表
11 0
|
24天前
|
算法 测试技术
力扣经典150题第五十一题:有效的括号
力扣经典150题第五十一题:有效的括号
18 0
|
29天前
|
算法 Java
Java数据结构与算法:双向链表
Java数据结构与算法:双向链表
|
29天前
|
算法 Java
Java数据结构与算法:循环链表
Java数据结构与算法:循环链表
|
29天前
|
算法
【数据结构与算法 刷题系列】求带环链表的入环节点(图文详解)
【数据结构与算法 刷题系列】求带环链表的入环节点(图文详解)
|
29天前
|
算法
【数据结构与算法 刷题系列】判断链表是否有环(图文详解)
【数据结构与算法 刷题系列】判断链表是否有环(图文详解)
|
29天前
|
算法
【数据结构与算法 经典例题】随机链表的复制(图文详解)
【数据结构与算法 经典例题】随机链表的复制(图文详解)
|
29天前
|
算法 C语言
【数据结构与算法 经典例题】链表的回文结构(图文详解)
【数据结构与算法 经典例题】链表的回文结构(图文详解)
|
7天前
|
传感器 算法
基于无线传感器网络的MCKP-MMF算法matlab仿真
MCKP-MMF算法是一种启发式流量估计方法,用于寻找无线传感器网络的局部最优解。它从最小配置开始,逐步优化部分解,调整访问点的状态。算法处理访问点的动态影响半径,根据带宽需求调整,以避免拥塞。在MATLAB 2022a中进行了仿真,显示了访问点半径请求变化和代价函数随时间的演变。算法分两阶段:慢启动阶段识别瓶颈并重设半径,随后进入周期性调整阶段,追求最大最小公平性。
基于无线传感器网络的MCKP-MMF算法matlab仿真