python leetcode简单练习(2)

20 有效括号

方法思路

要判断一个仅由括号组成的字符串是否有效，可以使用栈这一数据结构。核心思路是遍历字符串中的每个字符，遇到左括号时压入栈中，遇到右括号时检查栈顶的左括号是否匹配。若匹配则弹出栈顶元素，否则返回false。最终，若栈为空则说明所有括号正确闭合。

class Solution:
    def isValid(self,s):
        class Solution:
            def isValid(self,s):
                dic = {')':'(',']':'[','}':'{'}
                stack = []
                for i in s:
                    if i in dic:
                        if not stack or dic[i] != stack[-1]:
                            return False
                        stack.pop()
                    else:
                        stack.append(i)
                return not stack

 21. 合并两个有序链表

方法思路

合并两个有序链表可以通过逐个比较节点值并逐步构建新链表来实现。使用虚拟头节点简化初始条件处理，然后用指针依次连接较小值的节点，直到其中一个链表遍历完毕，最后将剩余链表直接接上。

class ListNode:
    def __init__(self,val=0,next=None):
        self.val = val
        self.next = next
class Solution:
    def mergeTwoLists(self,list1,list2):
        LNode = ListNode()
        p = LNode #虚拟指针
        while list1 and list2:
            if list1.val <= list2.val:
                p.next = list1
                list1 = list1.next
            else:
                p.next = list2
                list2 = list2.next
            p = p.next
        p.next = list1 if list1 else list2
        return LNode.next

26. 删除有序数组中的重复项

但实际上题目只要求前k个元素正确，后面的元素无关紧要。

方法思路

使用双指针法，快指针遍历数组，慢指针记录当前有效位置。由于数组已排序，重复元素必然相邻，遇到不同元素时将其移至慢指针位置，最后返回慢指针位置+1即为新数组长度。

#k是慢指针，用来记录我们想要的数组真正的下标，i是快指针用来遍历数组
class Solution:
    def removeDuplicates(self,nums):
        if not nums:
            return 0
        k = 0
        for i in range(1,len(nums)):
            if nums[i] != nums[k]:
                k += 1
                nums[k] = nums[i]
        return k+1

27.移除元素

但实际上题目只要求前k个元素正确，后面的元素无关紧要。

使用双指针法，快指针遍历数组，慢指针记录有效位置。将非目标值的元素移至数组前部，最后返回有效长度。

class Solution:
    def removeElement(self,nums,val):
        if not nums:
            return 0
        k = 0
        for i in range(0,len(nums)):
            if nums[i] != val:
                nums[k] = nums[i]
                k += 1
        return k