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

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(')()())'))

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))

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))