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
