【LeetCode算法题库】Day7:Remove Nth Node From End of List & Valid Parentheses & Merge Two Lists
2024-09-27 21:42:33
【Q19】
Given a linked list, remove the n-th node from the end of list and return its head.
Example:
Given linked list: 1->2->3->4->5, and n = 2. After removing the second node from the end, the linked list becomes 1->2->3->5.
Note:
Given n will always be valid.
Follow up:
Could you do this in one pass?
# Definition for singly-linked list.
# class ListNode:
# def __init__(self, x):
# self.val = x
# self.next = None class Solution:
def removeNthFromEnd(self, head: 'ListNode', n: 'int') -> 'ListNode': cur = head
length = 0
while cur!=None:
cur = cur.next
length += 1 if length==0:
return head
else:
idx = 0
if length-n==0:
return head.next
else:
cur = head
while idx<length-n-1:
cur = cur.next
idx += 1
cur.next = cur.next.next
return head
【Q20】
Given a string containing just the characters '('
, ')'
, '{'
, '}'
, '['
and ']'
, determine if the input string is valid.
An input string is valid if:
- Open brackets must be closed by the same type of brackets.
- Open brackets must be closed in the correct order.
Note that an empty string is also considered valid.
Example 1:
Input: "()"
Output: true
Example 2:
Input: "()[]{}"
Output: true
Example 3:
Input: "(]"
Output: false
Example 4:
Input: "([)]"
Output: false
Example 5:
Input: "{[]}"
Output: true 解法:用堆栈。遍历字符串数组,把左括号全部压栈,遇到右括号时,判断与栈顶的左括号是否为一对,若是,则令栈顶的左括号出栈,判断遍历完毕的栈是否为空。若是,则返回True,否则返回False。
详解(直接看最后的solution):https://leetcode.com/problems/valid-parentheses/solution/
class Solution:
def isValid(self, s: 'str') -> 'bool': charmap = {')':'(',']':'[','}':'{'}
if s==None:
return True if len(s)%2!=0:
return False stack = []
for i in range(len(s)):
if i==0:
stack.append(s[i])
elif s[i] in charmap:
c = stack.pop()
if c!=charmap.get(s[i]):
return False
else:
stack.append(s[i])
return not stack
【Q21】
Merge two sorted linked lists and return it as a new list. The new list should be made by splicing together the nodes of the first two lists.
Example:
Input: 1->2->4, 1->3->4
Output: 1->1->2->3->4->4 注意保存链表头!
# Definition for singly-linked list.
# class ListNode:
# def __init__(self, x):
# self.val = x
# self.next = None class Solution:
def mergeTwoLists(self, l1: 'ListNode', l2: 'ListNode') -> 'ListNode': head = l = ListNode(None) while l1 and l2:
if l1.val<l2.val:
l.next = l1
l1 = l1.next
else:
l.next = l2
l2 = l2.next
l = l.next
if not l1:
l.next = l2
else:
l.next = l1
return head.next
最新文章
- 设计模式之美:Interpreter(解释器)
- RCP:如何把Preferences中的项从一个类别移动到另一个类别
- C++中智能指针的设计和使用
- MapView
- opencv 手写选择题阅卷 (一)表格设计与识别
- Vigen&#232;re Cipher 维吉尼亚加解密算法
- The FastCGI process exited unexpectedly
- Linux系统编程——进程调度浅析
- 学习json-rpc
- 第八十六节,html5+css3pc端固定布局,网站结构,CSS选择器,完成导航
- 【将txt文本转图片】
- Java 通过Xml导出Excel文件,Java Excel 导出工具类,Java导出Excel工具类
- apache tomcat的下载 安装 配置
- HTML+CSS之盒子模型
- 配置国内 Docker Registry Mirror
- move UVs of a texture
- python基础知识回顾之列表
- pop3_用Java发送图文并茂的HTML邮件
- [数学] 将长为L的木棒随机折成3段,则3段构成三角形的概率
- 【Django】【五】开发Web接口
热门文章
- python and、or以及and-or
- Python之美[从菜鸟到高手]--2+2=5
- P2619 [国家集训队2]Tree I
- Hadoop学习之路(九)HDFS深入理解
- Python文件和流
- 1549: Navigition Problem (几何计算+模拟 细节较多)
- “unauthorized: authentication required” -- openshift3.9 docker push 报错
- Windows App开发之应用布局与基本导航
- Linux开机自启动脚本
- 微信支付JsApi 40163错误