目录
1. 最长有效括号 🌟🌟🌟
2. 矩阵中的最长递增路径 🌟🌟🌟
3. 回文链表 🌟
1. 最长有效括号
给你一个只包含 '(' 和 ')' 的字符串，找出最长有效（格式正确且连续）括号子串的长度。
示例 1：
输入：s = "(()" 输出：2 解释：最长有效括号子串是 "()"
示例 2：
输入：s = ")()())" 输出：4 解释：最长有效括号子串是 "()()"
示例 3：
输入：s = "" 输出：0
提示：
0 <= s.length <= 3 * 10^4s[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.lengthn == matrix[i].length1 <= m, n <= 2000 <= 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/