Python每日一练(20230428) 最长有效括号、矩阵最长递增路径、回文链表

简介: Python每日一练(20230428) 最长有效括号、矩阵最长递增路径、回文链表

1. 最长有效括号

给你一个只包含 '('')'字符串,找出最长有效(格式正确且连续)括号子串的长度。

示例 1:

输入:s = "(()"

输出:2

解释:最长有效括号子串是 "()"

示例 2:

输入:s = ")()())"

输出:4

解释:最长有效括号子串是 "()()"

示例 3:

输入:s = ""

输出:0


提示:

  • 0 <= s.length <= 3 * 10^4
  • s[i]'('')'

以下程序实现了这一功能,请你填补空白处内容:

```python
class Solution(object):
    def longestValidParentheses(self, s):
        ls = len(s)
        stack = []
        data = [0] * ls
        for i in range(ls):
            curr = s[i]
            if curr == '(':
                stack.append(i)
            else:
                __________________;
        tep, res = 0, 0
        for t in data:
            if t == 1:
                tep += 1
            else:
                res = max(tep, res)
                tep = 0
        return max(tep, res)
if __name__ == '__main__':
    s = Solution()
    print(s.longestValidParentheses(')()())'))
```

出处:

https://edu.csdn.net/practice/26740290

代码:

class Solution(object):
    def longestValidParentheses(self, s):
        ls = len(s)
        stack = []
        data = [0] * ls
        for i in range(ls):
            curr = s[i]
            if curr == '(':
                stack.append(i)
            else:
                if len(stack) > 0:
                    data[i] = 1
                    data[stack.pop(-1)] = 1
        tep, res = 0, 0
        for t in data:
            if t == 1:
                tep += 1
            else:
                res = max(tep, res)
                tep = 0
        return max(tep, res)
if __name__ == '__main__':
    s = Solution()
    print(s.longestValidParentheses(')()())'))

输出:

4


2. 矩阵中的最长递增路径

给定一个 m x n 整数矩阵 matrix ,找出其中 最长递增路径 的长度。

对于每个单元格,你可以往上,下,左,右四个方向移动。 你 不能对角线 方向上移动或移动到 边界外(即不允许环绕)。

示例 1:

输入:matrix = [[9,9,4],[6,6,8],[2,1,1]]

输出:4

解释:最长递增路径为 [1, 2, 6, 9]。

示例 2:

输入:matrix = [[3,4,5],[3,2,6],[2,2,1]]

输出:4

解释:最长递增路径是 [3, 4, 5, 6]。注意不允许在对角线方向上移动。


示例 3:

输入:matrix = [[1]]

输出:1


提示:

  • m == matrix.length
  • n == matrix[i].length
  • 1 <= m, n <= 200
  • 0 <= matrix[i][j] <= 2^31 - 1

出处:

https://edu.csdn.net/practice/26740291

代码:

class Solution:
    def longestIncreasingPath(self, matrix):
        """
        :type matrix: List[List[int]]
        :rtype: int
        """
        a = len(matrix)
        dic = {}
        nums_max = 1
        if a == 0:
            nums_max = 0
        else:
            b = len(matrix[0])
            for i in range(a):
                for j in range(b):
                    dic[(i,j)] = matrix[i][j]
            v =  dic.keys()
            nums1 = [[1 for i in range(b)] for j in range(a)]        
            dic = sorted(dic.items(),key = lambda x:x[1])
            for k in dic:
                i = k[0][0]
                j = k[0][1]
                if (i+1,j) in v and matrix[i+1][j]<matrix[i][j] and nums1[i][j]<nums1[i+1][j]+1:
                    nums1[i][j] = nums1[i+1][j] + 1
                if (i,j+1) in v and matrix[i][j+1]<matrix[i][j] and nums1[i][j]<nums1[i][j+1]+1:
                    nums1[i][j] = nums1[i][j+1] +1
                if (i-1,j) in v and matrix[i-1][j]<matrix[i][j] and nums1[i][j]<nums1[i-1][j]+1:
                    nums1[i][j] = nums1[i-1][j] +1
                if (i,j-1) in v and matrix[i][j-1]<matrix[i][j] and nums1[i][j]<nums1[i][j-1]+1:
                    nums1[i][j] = nums1[i][j-1] + 1    
                nums_max = max(nums_max,nums1[i][j])              
        return nums_max
if __name__ == '__main__':
    s = Solution()
    matrix = [[9,9,4],[6,6,8],[2,1,1]]
    print(s.longestIncreasingPath(matrix))
    matrix = [[3,4,5],[3,2,6],[2,2,1]]
    print(s.longestIncreasingPath(matrix))

输出:

4

4


3. 回文链表

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

示例 1:

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

输出:true


示例 2:

输入:head = [1,2]

输出:false


提示:

  • 链表中节点数目在范围[1, 10^5]
  • 0 <= Node.val <= 9

进阶:你能否用 O(n) 时间复杂度和 O(1) 空间复杂度解决此题?

出处:

https://edu.csdn.net/practice/26740292

代码:

class ListNode:
    def __init__(self, x):
        self.val = x
        self.next = None
class Solution:
    def isPalindrome(self, head: ListNode) -> bool:
        lst = []
        node = head
        while node:
            lst.append(node.val)
            node = node.next
        start = 0
        end = len(lst) - 1
        while start < end:
            if lst[start] != lst[end]:
                return False
            start += 1
            end -= 1
        return True
def createList(lst):
    if not lst:
        return None
    head = ListNode(lst[0])
    curr = head
    for i in range(1, len(lst)):
        curr.next = ListNode(lst[i])
        curr = curr.next
    return head
if __name__ == '__main__':
    s = Solution()
    nums = [1,2,2,1]
    head = createList(nums)
    print(s.isPalindrome(head))
    nums = [1,2]
    head = createList(nums)
    print(s.isPalindrome(head))

输出:

True

False


🌟 每日一练刷题专栏 🌟

持续,努力奋斗做强刷题搬运工!

👍 点赞,你的认可是我坚持的动力!

🌟 收藏,你的青睐是我努力的方向!

评论,你的意见是我进步的财富!  

主页:https://hannyang.blog.csdn.net/


目录
相关文章
|
16天前
|
IDE 开发工具 Python
python语法中括号不匹配处理
【7月更文挑战第8天】
13 2
|
14天前
【数据结构OJ题】链表的回文结构
牛客题目——链表的回文结构
18 0
【数据结构OJ题】链表的回文结构
|
1月前
|
机器学习/深度学习 数据处理 索引
Python遍历矩阵的技巧与实践
Python遍历矩阵的技巧与实践
28 2
|
1月前
|
计算机视觉 Python
Python矩阵转灰度图技术解析
Python矩阵转灰度图技术解析
18 1
|
15天前
|
Python
打印9*9乘法表(递归或压缩矩阵)python
打印9*9乘法表(递归或压缩矩阵)python
|
1月前
|
存储 算法 Unix
掌握Unix路径简化:五种有效算法比较【python力扣71题】
掌握Unix路径简化:五种有效算法比较【python力扣71题】
|
1月前
|
存储 算法 机器人
路径规划的艺术:不同路径 II 的算法深掘【python力扣63题】
路径规划的艺术:不同路径 II 的算法深掘【python力扣63题】
|
1月前
|
SQL 算法 数据可视化
LeetCode题目92:反转链表ll 【python 递归与迭代方法全解析】
LeetCode题目92:反转链表ll 【python 递归与迭代方法全解析】
|
1月前
|
存储 算法 数据挖掘
穿越障碍:最小路径和的高效算法比较【python力扣题64】
穿越障碍:最小路径和的高效算法比较【python力扣题64】
|
1月前
|
存储 算法 机器人
LeetCode 题目 62:不同路径【python】
LeetCode 题目 62:不同路径【python】